The Universe whispers, "You're working in a ray tracer." Ray tracing
equation generation, root isolation and root finding should be one
Back in March I closed out the thread at:
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
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
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).
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.
(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