|
 |
On 03/30/2018 08:21 AM, William F Pokorny wrote:
> ...
>
> A branch of master with the code update is available at:
>
> https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
>
> for those compiling their own POV-Ray versions. I plan to create a pull
> request once I've looked at some of the remaining accuracy issues.
> ...
I've continued to work on the polysolve 'sturm' solver in recent weeks
and another set of updates is available at:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
A couple quick notes followed at the bottom by more detailed change and
performance information. With respect especially to sphere_sweeps these
changes fix a number of bad or slightly bad root issues, but do not fix
missing root issues as shown in the attached image.
Another recent revelation has to do with the previous observation
continued rays seem to be more difficult for the sturm solver. There are
two major reasons for this.
One. The regula falsi method, while usually performing better than
bisection and guaranteeing a solution on proper set up, can - with
certain equations - be very, very slow to converge. Our transmitted,
internally reflected and self shadowing test rays all tend to create
polynomials which are a struggle for the regula_falsa() code.
Two. The polysolve code was always set up to jump to regula_falsa() once
it was known only one root existed on a 'ray' interval. The ray types
mentioned previously start with only one root as do rays with respect to
some surfaces. In these situations we do the work to set up the sturm
chain, use it to verify there is just one root - and immediately hand
often difficult to solve equations to regula_falsa() with the original
0.0 to MAX_DISTANCE interval. In these cases we are really using the
regula falsi method.
The changes below re-work things enough so as to be able to eliminate
the previously added sanity check at the end of regula_falsa(). Other
updates in the works.
Bill P.
Performance info:
------------ /usr/bin/time povray -j -wt2 -fn -p -d lemonSturm.pov
0) master 30.29user 0.02system 0:15.83elapsed
0) 3f2e1a9 30.31user 0.00system 0:15.81elapsed
1) 7be07ff 29.99user 0.01system 0:15.65elapsed -1.02%
2) 7f7eddd 29.91user 0.01system 0:15.61elapsed
3) a621c04 19.63user 0.01system 0:10.45elapsed -34.46%
4) b2042e6 19.67user 0.02system 0:10.45elapsed
5) 58a1933 20.36user 0.01system 0:10.80elapsed +3.51%
5a) 1c13a17 20.24user 0.00system 0:10.75elapsed
6) 7258366 19.33user 0.02system 0:10.31elapsed -5.06%
7) f313a5b 19.19user 0.02system 0:10.25elapsed -0.72%
8) cbd3af5 19.34user 0.01system 0:10.30elapsed +0.78%
9) 687f57b 19.16user 0.01system 0:10.21elapsed -0.93% -36.77%
1) Fix for earlier regula_falsa sturm chain based sanity check where the
sturm chain was shortened during set up and the sanity check was using
the full length.
2) Removed a normalization of the base polynomial added in the late 90s.
3) Delaying regula_falsa use until ray domain range < 1.0.
Important particularly where only 1 root. Previously the sturm chain
used only to verify the single root after which regula_falsa was called
with an initial range of 0 to MAX_DISTANCE.
4) Updating regula_falsa to remove two initial SMALL_ENOUGH fast paths.
These filters return quickly where the regula_falsa method performs
poorly - very small values at one end of the range and much larger at
the other. However, the cost is the roots often being very inaccurate
where the polynomial values are small over more than one end of the range.
5) Updating regula_falsa to use ray domain for the RELERROR conditions.
Previously a mix but primarily the polynomial value domain. Led to
different root values at about 5-6 digits in the ray domain depending
upon whether sturm chain bisection came up with the root or regula_falsa
did. With update results identical out to 8-10 digits.
5a) Adding missing else condition in previous commit.
6) Removing regula_falsa root sanity check.
With changes in recent commits the sanity check is no longer needed.
7) Increasing the MAX_ITERATIONS limits in sbisect and regula_falsa.
Even with recent updates found in practice sbisect sometimes needs
nearly 60 iterations and regula_falsa just over 100. Previously used
identical limits of 50. Now 65 and 130 respectively.
8) Update sbisect to return no roots when ray domain range is tiny.
Roots being very closely packed as happens most often when a ray is
nearly tangent to a surface cause instability in the sturm change sign
counting (numchanges) results. The instability, if not avoided, leads to
incomplete and sometimes inaccurately ordered roots. One of the triggers
for the CEY patch added in 1997 and where we get the diagonal lines of
no roots in certain objects.
9) Update sbisect to return a single root with closely spaced roots.
This is the current practice in the non-sturm chain based solvers and
expected by at least some primitive objects. Root returned is the middle
of the tiny range at which we stop bisection.
Post a reply to this message
Attachments:
Download 'lipka_gh147_fs81.png' (50 KB)
Preview of image 'lipka_gh147_fs81.png'
|
|
