The Universe whispers, "You're working in a ray tracer." Ray tracing 
equation generation, root isolation and root finding should be one 
integral process.

Back in March I closed out the thread at:

http://news.povray.org/povray.binaries.images/thread/%3C5abe2bdc%241%40news.povray.org%3E/?ttop=427346&toff=150

after working a year on and off with POV-Ray's solvers. The updated 
solvers were at a state where accuracy was as good as I thought it could 
be. The plan was to work with the updates for a time while getting back 
ray tracing and other ideas. I'd keep my eyes open for additional issues.

Those - few I suspect - following the solver related work and comments 
at: https://github.com/POV-Ray/povray/pull/358 know I immediately found 
an issue with photons and the diffuse_back.pov scene. The issue led me 
to create similar photon test scenes for most shapes.

For shapes of equation orders > 2, the disheartening result was the new, 
improved, accurate as can be solvers were not enough where rays start 
far from the surface. With floats, on float hardware, surface root 
accuracy from afar is ugly.

Thankfully, I created a polynomial torus test with major accuracy issues 
while a similar scene using the regular torus object was OK. It's the 
case that torus.cpp has a patch which, sometimes, moves the ray origin 
closer to the first surface before calculating coefficients. This 
greatly improves the accuracy of the ray-surface equation.

The patch isn't general to secondary rays, it's discontinuous in 
application to outside, first surface rays and the effectiveness 
degrades on other factors. Still, it often saves the day. I was looking 
for something more general without luck, when it hit me: POV-Ray creates 
the polynomial equations!

Today, we create coefficients for ray-surface equations and throw them 
at various solvers. The solvers work on these equations blind to what 
process created them and without ability to ask for better.

With respect to accuracy on float hardware, it's not the best approach. 
Equation generation, root isolation and root finding should be one 
mechanism.

Ray tracers can replace the mobius transformations used in Vincent, 
Akritas, et al type solvers with ray-surface equation generation and 
sign evaluation. Ray tracers - knowing the shape - can also jump to 
conclusions without the need to isolate single roots. Odd root counts 
for an even order shape mean we are inside the shape, for example.

The current approach isn't that pure and uses foreknowledge about the 
shape to quickly localize and set intervals while creating additional 
equations. I have a working TCL implementation for the torus.

For the results below, the torus is sitting in the xz plane with the ray 
origin -1370.0 in x to the left and the ray direction to right (left 
handed).

P = <-1370.0 0.0 0.0>
D = <1.0 0.0 0.0>
MajorRadius = <0.35>
MinorRadius = <0.2>

The ray-surface equation created is:

t^4 - 5480.0*t^3 + 11261399.675*t^2 - 10285411109.5*t + 3522753000007.5063

Using a couple solvers, we come up with four roots indicative of results 
seen inside POV-Ray. For ray tracing purposes they're not very good and 
we have limited ability to polish the roots due the created equation(a).

TCL quartic:

<1369.4485149222974 1369.8555365457344
1370.1444769215443 1370.5514716104242>

Sage's .roots (Berstein basis / de Casteljau...)

[(1369.45309378556, 1), (1369.83907617961, 1),
(1370.16093129266, 1), (1370.54689874217, 1)]

The new approach uses a quadratic solver to find ray-sphere 
intersections bounding the torus. These are used to create a second 
ray-torus equation for the same torus at the first intersection. A Sturm 
chain related analysis gets done - one not requiring polynomial 
evaluations - to set the number of roots at 0, 2 or 4. Knowing the root 
count simplifies downstream code.

The rest leans on many solver techniques. The key extension being the 
use of existing ray-surface equation generation to create multiple ray 
equations shooting forward and backward from sample points along the 
ray. Decisions about how to isolate roots are based on the coefficient 
sign changes alone. The best part is the much more accurate, root-unique 
equations are used when finding each root.

Torus results with new method:

1369.45, 1369.85, 1370.15, 1370.55    <--- Exact roots!

I'm encouraged. I think we've got a path to as much accuracy as float 
based coefficient creation and calculation allow. I'm posting ahead of 
an in POV-Ray implementation due being away for the next few weeks.

Might we make use of a, "regenerate coefficients and root polish" 
technique too? Yes, I think we might as a near term(1) improvement.

Bill P.

(1) - The torus.cpp patch aside; At a distance of around 1400 to a unit 
sized torus at the origin, today's solvers don't 'see' the correct 
number of roots a surprising 4-5% of the time(a). Solvers usually see 
roots exist and so find a first root to some rough value - and often 
additional roots. This means the shape shows up - but with surfaces not 
quite right. Plus, 1-2% of the time with near tangents, solvers miss 
real roots. Rays deriving from inaccurate first intersections are worse 
being based upon inaccurate first ray result.

(a) - It's not a solver problem! The accuracy isn't intrinsic to the 
generated polynomial. In other words, available steps/precision are 
today being wasted on empty distance to and between roots.

Post a reply to this message