

On 10/13/19 5:56 AM, Warren wrote:
> Hello/Hi,
>
> 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:
> https://en.wikipedia.org/wiki/Newton%27s_method
>
> 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 shortish answer for POVRay as I understand it today.

With univariate polynomial equations (raysurface intersection/root
equations):
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/regulafalsi solver.
Sturm 'mostly' for single root isolation, then regulafalsi 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 POVRay(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 raysurface intersection values.
So... Might be we have bisection or solversother floating around I've
not seen  or recognized  for what they are.
Bill P.
(2)  Beyond POVRay's implemented root finding methods, you find there
are a mindblowing 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 POVRay originally had no such resource.
Post a reply to this message

