









 
 


From: William F Pokorny
Subject: Old media blob issue leading to a look at sturm / polysolve.
Date: 30 Mar 2018 12:21:48
Message: <5abe2bdc$1@news.povray.org>



 
 


In continuing to look at media I returned to a 'blobmedia' issue Gail
Shaw originally posted back in 2005. The bright spots at the very edge
are indeed caused by the 'intersection depth < small_tolerance' or
missed intersection issue as Slime guessed at the time.
However, the sturm result Gail showed never made any sense unless sturm
is broken for blobs. Gail's original belief something changed 3.5 to 3.6
was correct. Optimizations were done involving bounding and polynomial
reformulation for 3.6 which occasionally inhibit 4th to 3rd order
reduction(1). The bright spots not on the edge happen where
Solve_Polynomial passes the original 4th order blob equation to
polysolve and we get bad roots back.
(1)  Happens mostly with transparency.
In the lower left in the attached image I hacked the code to prevent
order reduction with blobs. Surprised to find it looks like blobs only
work as formulated due order reduction  even in v3.5.
All got me digging again into the solver code. Since v1.0 there has been
a regula_falsa function called once the rule of signs stuff has
determined a subinterval contains a single root. The regula_falsa is
buggy once polynomial order is >= 4 given how many of our polynomials
are formulated  the evaluated values can be very small.
I've coded up a branch modifying the regula_falsa function so it sanity
checks the root found is a real root  within some tolerance  otherwise
it invalidates the root and tosses control back to the interval
bisection code.
Branch fixes this blob issue, the lathe issue #335 from last fall and
many remaining #147 (sphere_sweep) solver issues  except one b_spline /
orthogonal camera case. The patch also fixes or makes better many of the
accuracy issues I have in hand, however, I have too still some scenes
with 'accuracy' issues to dig through. The work is tedious and I need a
break  so putting out the fix I have.
A branch of master with the code update is available at:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
for those compiling their own POVRay versions. I plan to create a pull
request once I've looked at some of the remaining accuracy issues.
Aside: The regula_falsa function isn't strictly needed for root finding,
but the solver runs faster with it than not.
Bill P.
Post a reply to this message
Attachments:
Download 'blobsturmbroken.jpg' (129 KB)
Preview of image 'blobsturmbroken.jpg'


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 3 Apr 2018 17:27:03
Message: <5ac3b967@news.povray.org>



 
 


On 03/30/2018 08:21 AM, William F Pokorny wrote:
>
> Branch fixes this blob issue, the lathe issue #335 from last fall and
> many remaining #147 (sphere_sweep) solver issues  except one b_spline /
> orthogonal camera case. The patch also fixes or makes better many of the
> accuracy issues I have in hand, however, I have too still some scenes
> with 'accuracy' issues to dig through. The work is tedious and I need a
> break  so putting out the fix I have.
>
> A branch of master with the code update is available at:
>
> https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
>
> for those compiling their own POVRay versions. I plan to create a pull
> request once I've looked at some of the remaining accuracy issues.
>
I've run down another type of solver issues related to our sor object.
In this case the problem is with the sor polynomial set up often not
crossing through 0.0 which is a requirement for the sturm / polysolve
methods.
The ray / sor set up sometimes creates sets of coefficients which are
are all positive or negative which sturm / polysolve sees as meaning
there are no roots to find. The fix is to perturb the direction vector
by +EPSILON during the set up which is in my testing enough to get the
crossing 0.0 criteria always.
I started with a sor scene shown in the top row of the attached image
which Severi Salminen posted in 2004. v381 shown on the left and the fix
on the right.
(The remaining three rows show differences at 4x the real magnitude.)
The second row is our shipped sor1 sample scene which doesn't use sturm
at all. I expected no difference, but the 'sturm off', solve_cubic()
function is also failing to find roots on reflected rays which I didn't
previously notice. The +EPSILON change perturbs these noisy solution
regions.
The third row is the same sor1 scene, but with sturm turned on for all
sor objects meaning polysolve gets used. The difference on the right of
row 3 shows how a noisy original solution is cleaned up with the fix.
The last row shows the updated code's solve_cubic solution vs the 'sturm
on' / polysolve solution. Note that 'sturm on' is needed for clean
roots & a clean sor1.pov image.
Aside: Yes, it's looking like continued rays whether transmitted or
reflected tend to be harder for the solvers to handle. This echoes back
to early lemon issues with noise when the texture had a reflective
component. Also true errors in continued rays are often harder to see
given the contributions are mixed with any ambient or diffuse components.
I've more solver accuracy issues to run down, but I've updated the
branch at:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
with this sor polynomial set up fix for those interested.
Bill P.
Post a reply to this message
Attachments:
Download 'sorsoverstory.jpg' (317 KB)
Preview of image 'sorsoverstory.jpg'


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 26 Apr 2018 12:35:58
Message: <5ae1c7ae@news.povray.org>



 
 


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 POVRay 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 rework 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 56 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 810 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 nonsturm 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'


 
 




 
 


William F Pokorny <ano### [at] anonymousorg> wrote:
[Quite a lot of stuff]
First of all  great work!
I can appreciate how much you need to pick and poke and test and plow through in
order to unravel the source code, design test objects, and tease out the little
problematic details and then conceive of and implement solutions.
This is definitely where Stephen shall christen this work as the plural MATHS.
I only have the most rudimentary and tenuous grasp of what you're working on,
having never been taught these methods [that I can recall], and only getting a
sample of how they're used from the many and varied excursions into math videos
on the web.
I went to an American public indoctrination center. You should see the
abomination they call "common core". It's worse than the New Math.
https://thefederalistpapers.org/education2/kidlookslikeageniusshowsexactlywhycommoncoremathdoesntaddup
https://www.youtube.com/watch?v=UIKGV2cTgqA
Just for clarification, POVRay uses:
bisection
regula falsa
Newton's method, and
the Sturmian method
?
Or are some of those the same?
and  where is this all located in the source code?
Because I'm a hopeless intellectual masochist like that.
Post a reply to this message


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 27 Apr 2018 13:25:43
Message: <5ae324d7$1@news.povray.org>



 
 


On 04/26/2018 10:16 AM, Bald Eagle wrote:
> William F Pokorny <ano### [at] anonymousorg> wrote:
>
...
>
> Just for clarification, POVRay uses:
> bisection
> regula falsa
> Newton's method, and
> the Sturmian method
> ?
> Or are some of those the same?
>
> and  where is this all located in the source code?
> Because I'm a hopeless intellectual masochist like that.
>
Thanks. Suppose I've been exposed to some of the concepts in the past,
but trust me, I'm climbing the learning curve/mountain(a) with this
stuff. There is much I don't understand. My standard set of test scenes
number a 195 at present which have corrected many of my missteps.
You can find most of the code in source/core/math/polynomialsolver.cpp.
There are three custom solvers in solve_quadratic(), solve_cubic() and
solve_quartic() for orders 2 through 4. I've hardly looked at these.
In polysolve / 'sturm'  a sturm chain based bisection method is used in
combination with regula_falsa(). Value based bisection isn't used at
all. Newton–Raphson isn't used at all  though the first two equations
in the sturm chain are, in my present version, the original and it's
normalized derivative. Who knows, might play with it as an alternative
or adjunct to regula_falsa(). The spin is it's really fast when it works
 but sometimes it doesn't.
Near term looking more at the missing root issue  some(b) of which was
addressed with (9), but the rest comes to the roots having collapsed
toward each other so severely the sturm chain root counting / isolation
falls apart. Not looking like it will be easy to mitigate...
Bill P.
(a)  Trying to get out of the media whirlpool! :)
(b)  Where the sturm chain root counting and isolation stuff still
works despite how close the roots are.
Post a reply to this message


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 29 Apr 2018 20:52:54
Message: <5ae630a6$1@news.povray.org>



 
 


On 03/30/2018 08:21 AM, William F Pokorny wrote:
>
...
> Bill P.
While studying the missing root problem I finished off some initial
lower and upper root bound estimation code aimed at polysolve()
performance. The update is at:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
The update is directly related to a subdiscussion of issue:
https://github.com/POVRay/povray/issues/236
Currently the upper bound method(d) is hard coded to run always. Longer
term, and given I've found some POVRay objects such as blob already
calculate a 'max_bounds' value, I'm thinking about a change to the
Solve_Polynomial(), polysolve() calls to add a parameter where :
a) if > 0 value, we'd be passing a known upper bound for all roots.
b) if == 0, we'd do what we do today.
c) if == 1, we'd run the original Cauchy's bound estimate method good
for the lowest value root. In some applications, that first root might
be all we need.
d) if == 2, we'd run an estimator based on Cauchy's method from a 2009
paper(z) found via:
https://en.wikipedia.org/wiki/Properties_of_polynomial_roots#Other_bounds
and good for the upper bound of all roots.
There are better bound estimators, but all I've looked at are more
complex  and several I don't understand. In any case I doubt we'd buy
back the performance given our equation orders are tiny compared to that
aimed at by the more generic solvers for which these better estimator
were created. Many others also use complex numbers.
Bill P.
(z)  Had to tweak it slightly due two sor fails in testing. Due the
surprise with sturmcubic it's on my list to enable sturmquadratic in
Solve_Poly() to do some more testing.
Performance info:
 /usr/bin/time povray j wt1 fn p d c lemonSturm.pov
0) master 30.22user 0.04system 0:30.89elapsed
9) 687f57b 19.44user 0.01system 0:20.06elapsed 35.67%
10) 0f6afcc 14.77user 0.02system 0:15.36elapsed 24.02% 51.13%
Post a reply to this message


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 8 May 2018 13:11:34
Message: <5af1a206$1@news.povray.org>



 
 


On 03/30/2018 08:21 AM, William F Pokorny wrote:
>....
Sturm / polysove() investigation. Chapter ??. Corruption of the Sturm Chain.
Let me start this post with the news I found something amiss in the
recent bound estimate code recently added to:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
despite having run 200 plus scenes and image compares without a difference.
Caught the issue while playing with the idea of trading off the one root
vs all roots method automatically. Not trusting the implementation;
added an autobound check for lost roots and an assert and BOOM. So, I
have more to do there even if at worst it's leaving a sanity check in
place that resorts to an upper bound of MAX_DISTANCE. Back to that later.

Today let us elsewhere ponder. The function modp() does the bulk of the
sturm chain set up. At the end of modp is this bit of code:
k = v>ord  1;
while (k >= 0 && fabs(r>coef[k]) < SMALL_ENOUGH)
{
r>coef[k] = 0.0;
k;
}
r>ord = (k < 0) ? 0 : k;
It individually prunes equations in the sturm chain at a depth of >= 2
where the leading coefficients are small.
In Mr. Enzmann's original 1.0 code, 'SMALL_ENOUGH' was 1e20. In the
days of single floats likely meant lots of looping and looking while
doing little. As of POVRay v3.0 'SMALL_ENOUGH' was drastically
increased to 1e10.
Over the past week or more I've been looking again at achieving better
accuracy. Tried quite a lot of things finally coding up a __float128
version of polysolve all aiming at more accuracy. Finally realized the
remaining issues are far from all about accuracy. Sometimes the
raysurface equation coming in is simply messed up with respect to any
sign change based methods for isolating the roots  unless we cheat.
For best accuracy while avoiding spurious roots with illformed
equations, the value used should be right at the best accuracy for the
floating point type. This would be 1e7 for floats, 1e15 for doubles
and 1e33 for 128 bit floats. With well behaved equations with no zero,
near zero or cross term zero terms during the creation of the sturm
chain equations can support much smaller minimum values, but in a
raytracer we cannot count on the good behavior of the raysurface equations.
So, why is that 'SMALL_ENOUGH' value sitting at a much larger 1e10
value for doubles. My guess is someone understood or stumbled upon a
wonderful bit of serendipity in how the pruning of the sturm chain
equations effectively work. Namely, when we have illformed equations
with respect to sign chain based root isolation, the pruning value can
be adjusted upward and by 'magic' some or all of the 'ill' in the
incoming equation is pruned and the root isolation works well enough to
hand the regulafalsi method a problem it can solve.
The downside is you cannot universally set this value above the minimum
for the float size when you have well behaved incoming equations or you
prune off sign change information you need to accurately see the
intervals in which roots exist. We are using a fixed value today.
To better demonstrate attaching two images. In both the left column is
what the current master renders. The remaining columns to the right are
rendered with a float128 version of polysolve to better drive home the
point it our primary need isn't better overall accuracy, but more
accurate root isolation.
In the latheQuadratic.png image the top row is the point set from last
falls lathe issue used in a quadratic spline. The top row is a
perspective camera but zoomed way out and using a camera angle of 2. The
bottom row is the same input except with an orthographic camera set
up(1). In the middle column is what the current patched branch renders
using the SMALL_ENOUGH 1e10 value. The value has been set so as to
behave well for the orthographic case, but this causes issues for the
perspective case. In the right column SMALL_ENOUGH has been set to
float128's minimum value of 1e33. This orthographic case falls apart
showing the underlying illformed for sign change isolation problem 
while the perspective camera case is OK.
In the sphere_sweeps.png image showing the same progression(2) in
columns 13 but in column 4 we dial in a higher SMALL_ENOUGH value which
prunes off just the right about of the sturm chain for the root
isolation to work well.
I'm busy with real life for a while starting later today, but I think we
likely have a path to cleaner renders in these fringe cases given our
sturm chain based method.
We're working in a ray tracer and it is the ray's dx,dy,dz going to zero
which primarily causes the illformed for sign base root isolation
issue. We'll need to detect problem directions in the object's code and
create some calculation(3) which we'd pass all the way into the modp()
pruning. Possible I think.
Bill P.
(1)  It's not just the orthographic camera which tends to pull out the
worst case solver issues. Shadow rays with cylindrical and parallel
lights too. There are too the occasional rays which line up orthogonally
in one or compound dimensions.
(2)  Except running with jitter off. Our AA implementations are grid
based which unfortunately tends to line up with the compound (diagonal
type) missing root issues. Thinking something like a Halton sequence
based AA never keeping the center pixel might really help in these cases
by getting the samples more often off the problem ray / surface
gridaxis alignments.
(3)  Perhaps coupled with some ability for users to apply a multiplier
from the SDL?
Post a reply to this message
Attachments:
Download 'lathequadratic.png' (17 KB)
Download 'sphere_sweeps.png' (63 KB)
Preview of image 'lathequadratic.png'
Preview of image 'sphere_sweeps.png'


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 18 May 2018 17:00:10
Message: <5aff069a@news.povray.org>



 
 


On 03/30/2018 08:21 AM, William F Pokorny wrote:
....
Sturm / polysove() investigation. Those Difficult Coefficients.
When we have 4th order equations we are today running this piece of code:
/* Test for difficult coeffs. */
if (difficult_coeffs(4, c))
{
sturm = true;
}
in the Solve_Polynomial wrapper for sturm/polysolve() and three specific
solvers including the one for 4th order equations in solve_quartic().
The difficult_coeffs() function scans the coefficients looking for large
differences in values. If found, user end up running sturm for some rays
no matter what was specified in the scene SDL. The code existed in the
original POVRay 1.0, but in a slightly modified form and used with an
older version of solve_quartic().
I've had the feeling for a while the code was probably doing nothing
useful for us today. I was almost completely right. Close enough it's
going into the bit bucket with this set of commits.
The code was set up to crash anytime difficult_coeffs() returned true.
Scanned hundreds of scenes. Turned up helix.pov and a handful of scenes
with blobs. Ran those hard coded to use only solve_quartic() and not a
single difference in result. Changed the code above to return
immediately with no roots on difficult_coeffs() returning true. The
helix scene was unchanged as the 'rays' were not part of the resultant
shape.
The blobs were a different story. Many rays are being redirected to
sturm / polysolve for no benefit given the current solve_quartic code.
To oblivion with that code you all say!
I thought the same, but remembered we have known blob accuracy issues in
https://github.com/POVRay/povray/issues/187, maybe half a dozen related
problem scenes in my test space. Plus to support the subsurface feature
Chrisoph added this bit of code in blob.cpp to avoid visible seams:
DBL depthTolerance = (ray.IsSubsurfaceRay()? 0 : DEPTH_TOLERANCE);
I've been running with DEPTH_TOLERANCE at 1e4 for a long time in my
personal version of POVRay which fixes all the blob accuracy issues
except for the subsurface one.
Given difficult_coeffs() is almost exclusively active with blobs,
updated blob.cpp to run with accuracy addressing the issues in the
previous paragraph. With this update in place, we do occasionally see
cases where the bump into to sturm / polysolve method is necessary.
However, the automatic difficult_coeffs() method doesn't currently catch
all of the fringe case rays.
It could be adjusted so as to push more solve_quartic rays into sturm /
polysolve, but it's aleady the case most difficultcoefficient rays are
unnecessarily run in sturm / polysolve when solve_quartic would work
just fine. The right thing to do is let users decide when to use 'sturm'
and this set of commit dumps the difficult_coeffs() code.
Examples.
The attached image is a scene originally created to explore default
texturing related to negative blobs, but it demonstrates nicely the
issues described above.
In the top row we have on the left the image rendered with the blob
accuracy unmodified and all the difficult_coeffs() code running as it
does today. In the middle image the 'if difficult_coeffs()' test has
been hard coded to return no roots. On the right the difference image
shows all the rays running in the sturm / polysolve method which all run
fine  and faster given the blob set up  with solve_quartic().
In the second row we are running with the new more accurate blob.cpp.
Further, the blobs in the scene have been changed to have a threshold of
0.001 instead of 0.1  values this low are not common because you don't
get much blobbing.
The first column of the second row was rendered with a version of
POVRay compiled to always force the use of solve_quartic(). The middle
column restores the 'if difficult_coeffs()' test and internal swap to
sturm / polysolve. It does help as shown in column 3. However column 2
shows the already too aggressive use of sturm / polysolve with blobs is
not enough to automatically 'fix' all the solve_quartic issues. Running
with sturm is clean in all cases.
Aside: The potentials as glows image I did sometime back had what I
thought were media related speckles. I applied very aggressive and
expensive AA to hide them as I usually do with media. Turns out using
sturm would have been the better choice. I wanted no blobbing for the
blob cylinders and used a threshold of 1e5. It was a case of outrunning
the effectiveness of the 'if difficult_coeffs() patch' with existing
blob accuracy, but I didn't realize it at the time.
Updates at:
https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy
Performance and specific commit details below.
Bill P.
Performance info:
 /usr/bin/time povray j wt1 fn p d c lemonSturm.pov
0) master 30.22user 0.04system 0:30.89elapsed
10) 0f6afcc 14.77user 0.02system 0:15.36elapsed 51.13%
11) 0f9509b 14.77user 0.01system 0:15.36elapsed
12) c590c0e 15.08user 0.01system 0:15.71elapsed +2.10%
13) 4ab17df 14.88user 0.02system 0:15.51elapsed 1.33% 50.76%
14) 78e664c  NA 
15) 5d8cedc  NA 
16) 21387e2  NA 
 povray subsurface.pov p +wt2 j d c fn
master sturm on 540.89user 0.06system 4:31.15elapsed
21387e2 sturm on 347.29user 0.07system 2:54.42elapsed 35.79%
master sturm off 286.99user 0.06system 2:24.28elapsed
21387e2 sturm off 278.54user 0.05system 2:20.12elapsed 2.94%
If blob container needs sturm. 278.54 > 347.29 +24.68%
11) Changing polysolve visible_roots and numchanges zero test to <=0.
Depending upon value used for reducing and trimming the sturm chain
equations in modp, the sphere_sweep b_spline functions can return
negative root counts when there are no roots.
12) Adding sanity test of upper bound Cauchy method result.
In practice have occasionally found roots slightly above upper bound.
Perhaps related to how sturm chain is tweaked during pruning. Sort it later.
13) Removing pointless operations in polysolve and Solve_Polynomial.
visible_roots() passed a couple integer pointers which it set prior to
return but the values were never used in polysolve itself.
When fourth order equations seen a test call to difficult_coeffs() was
made which if true would set sturm true  even when sturm was already true.
14) Updating blob accuracy so better synchronized with other shapes.
Fix for GitHub issue #187
Returned minimum intersection depths now set to MIN_ISECT_DEPTH.
Internal determine_influences() intersect_<subelement> functions using
>0.0 as was already the subsurface feature. Anything more opens up gaps
or jumps where the subelement density influences are added too late or
dropped too earlier. The change does create ray equations slighly more
difficult to solve which was likely the reason for the original,
largish, v1.0 1e2 value. The sturm / polysolve solver is sometimes
necessary over solve_quartic().
15) Removing difficult_coeffs() and related code in Solve_Polynomial().
Code not completely effective where sturm / polysolve needed and very
costly in most scenes with 4th order equations due use of sturm over
solve_quartic() where solver_quartic works fine and is much faster.
16) Reversing change to sor.cpp as unneeded with updated polysolve().
Not verified, but suspect bump made in commit 3f2e1a9 to get sign change
was previously needed where regula_falsa() handed single root problem
with 0 to MAX_DISTANCE range. In any case, the patch is no longer needed
with updated polysolve() code.
Post a reply to this message
Attachments:
Download 'storydifficultcoeff.png' (110 KB)
Preview of image 'storydifficultcoeff.png'


 
 


From: William F Pokorny
Subject: Re: Old media blob issue leading to a look at sturm / polysolve.
Date: 18 May 2018 17:10:55
Message: <5aff091f$1@news.povray.org>



 
 


On 05/18/2018 01:00 PM, William F Pokorny wrote:
> On 03/30/2018 08:21 AM, William F Pokorny wrote:
> ....
>
> Sturm / polysove() investigation. Those Difficult Coefficients.
>
I'll add quickly this set of updates fixes the remaining media speckles
for the scene which started this thread  see attached image. The
general media speckling issue is better with more accurate roots, but
not completely fixed.
Bill P.
Post a reply to this message
Attachments:
Download 'gailshawexampleclean.png' (167 KB)
Preview of image 'gailshawexampleclean.png'


 
 




 
 


William F Pokorny <ano### [at] anonymousorg> wrote:
> On 03/30/2018 08:21 AM, William F Pokorny wrote:
>
[snip]
> I've had the feeling for a while the code was probably doing nothing
> useful for us today. I was almost completely right. Close enough it's
> going into the bit bucket with this set of commits.
> ...
>
> The blobs were a different story. Many rays are being redirected to
> sturm / polysolve for no benefit given the current solve_quartic code.
> To oblivion with that code you all say!
>
[snip]
Your detailed research into these arcane issues is really appreciated. I can't
say I understand some of it (most of it!), but we are all lucky to have your
keen eye probing the code.
Post a reply to this message


 
 




 

