In continuing to look at media I returned to a 'blob-media' 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 sub-interval 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 POV-Ray 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'

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 POV-Ray 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'

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'

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/education-2/kid-looks-like-a-genius-shows-exactly-why-common-core-math-doesnt-add-up

https://www.youtube.com/watch?v=UIKGV2cTgqA

Just for clarification, POV-Ray 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

On 04/26/2018 10:16 AM, Bald Eagle wrote:
> William F Pokorny <ano### [at] anonymousorg> wrote:
> 
...
> 
> Just for clarification, POV-Ray 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 

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

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 sub-discussion of issue:

https://github.com/POV-Ray/povray/issues/236

Currently the upper bound method(d) is hard coded to run always. Longer 
term, and given I've found some POV-Ray 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 sturm-cubic it's on my list to enable sturm-quadratic 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

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 auto-bound 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 1e-20. In the 
days of single floats likely meant lots of looping and looking while 
doing little. As of POV-Ray v3.0 'SMALL_ENOUGH' was drastically 
increased to 1e-10.

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 
ray-surface 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 ill-formed 
equations, the value used should be right at the best accuracy for the 
floating point type. This would be 1e-7 for floats, 1e-15 for doubles 
and 1e-33 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 ray-surface equations.

So, why is that 'SMALL_ENOUGH' value sitting at a much larger 1e-10 
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 ill-formed 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 regula-falsi 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 1e-10 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 1e-33. This orthographic case falls apart 
showing the underlying ill-formed 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 1-3 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 ill-formed 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 
grid-axis 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'

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 POV-Ray 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 re-directed 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/POV-Ray/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 1e-4 for a long time in my 
personal version of POV-Ray 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 difficult-coefficient 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 
POV-Ray 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 1e-5. 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_<sub-element> functions using 
 >0.0 as was already the subsurface feature. Anything more opens up gaps 
or jumps where the sub-element 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 1e-2 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'

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 re-directed 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