On 10/13/19 5:56 AM, Warren wrote:
> I remember in school my mathematics teacher told me that for the equation of 6th
> degrees and above it was impossible to find roots with a perfect method (that
> characteristic has been demonstrated). The functions in isosurface primitive can
> use any degree equation (the parametric function which indicates that for any
> (x,y,z) set, we are on volume surface if it is equal to zero, if the result is
> negative we are inside or outside if positive. So in povray, the point is to
> find roots (zero equality) for intersections. This said, how can POVRay find
> roots of 6th and above degree equations ?
> The isosurface uses the Newton's approximation to find roots of the isosurface:
> This last method while not perfect (some equations tend to give almost infinite
> results the closer you are from a x value and since Newton's method is an
> approximation this can take a very long time to find the root), so to not spend
> a very long time testing value for intersections the 'accuracy' parameter of
> isosurface can be set to something like 0.0001 for example to abort further
> approximation of a single root if Newton's method find a result of 0.0001 or
> less (not perfectly 0 I mean).
> My english is not perfect, I apologize for any writing error. :-D
A short-ish answer for POV-Ray as I understand it today.
With univariate polynomial equations (ray-surface intersection/root
There are fixed solvers for orders one through four.
I've heard there is now a fixed solver method for quintics based on
changing the form of the polynomial via elliptical functions - or
something. I don't understand the method at all, and it's not
implemented. Those in the know don't recommend it computationally over
root isolation and iterative methods.
For orders 2 through 35(1) there is a common sturm/regula-falsi solver.
Sturm 'mostly' for single root isolation, then regula-falsi to get to
the actual root values.
(1) - Practically I'd be surprised if much past order 15 is stable, but
maybe, in special cases.
With functions in general (isosurfaces for example):
There are various iterative solvers based roughly upon sampling of the
function values and it's derivative values (or estimations thereof) at
points along the ray (or at or about some fulcrum).
Aside: I've been playing seriously with solvers and solver techniques
the past couple years. Still, I've not taken detailed looks at all the
solvers that exist in POV-Ray(2)! In addition to the common solvers,
custom solvers - or parts of certain solver techniques - can be found
throughout the shape code. For example, I don't know what solver
technique(s) the isosurface shape uses by name (Steffenson's?) - though
it's on my list to look at that one it in detail someday. I've not
looked at the parametric's code aside from a problem with the shape code
returning negative ray-surface intersection values.
So... Might be we have bisection or solvers-other floating around I've
not seen - or recognized - for what they are.
(2) - Beyond POV-Ray's implemented root finding methods, you find there
are a mind-blowing number of techniques and tweaks to existing methods
for finding roots. I've found Wikipedia good for the overviews and
pointers for digging into solvers. Amazed when I think how those coding
up POV-Ray originally had no such resource.
Post a reply to this message