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 short-ish answer for POV-Ray as I understand it today.

---
With univariate polynomial equations (ray-surface 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/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.

Bill P.

(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