

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 POVRay'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/POVRay/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 raysurface 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: POVRay creates
the polynomial equations!
Today, we create coefficients for raysurface 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 raysurface 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 raysurface 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 POVRay. 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 raysphere
intersections bounding the torus. These are used to create a second
raytorus 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 raysurface 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, rootunique
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 POVRay 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 45% 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, 12% 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

