raymarching optimization using golden ratio ...

[cKleinhuis]

hi there, i dunno if someone has tried this for optimizing the inside/outside zero point search on raymarching, but
according to this wikipedia entry:
http://en.wikipedia.org/wiki/Golden_section_search

it should find the zero point faster and more exact, perhaps someone would like to try it out and make a speed comparison !?

[hobold]

The usual refinement with recursive bisection is already optimal for the special case of "polishing" the precision of bracketed intersection points.

This Golden Section search might be interesting in cases when there is no intersection point (between a ray and some fractal object) - it could find the point of smallest distance (i.e. of closest approach). But like most numerical algorithms, it relies on fairly strong constraints, i.e. some prior knowledge about the unknown function within a known interval. These guarantees are usually hard to come by; running the refinement algorithm is really the easy part.

[cKleinhuis]

in the german wikipedia they state:
http://de.wikipedia.org/wiki/Goldener_Schnitt#Verfahren_des_Goldenen_Schnittes
"Wird angenommen, dass jeder Punkt in jedem Intervall mit gleicher Wahrscheinlichkeit Extrempunkt sein kann, führt dies bei Unbestimmtheitsintervallen dazu, dass das Verfahren des Goldenen Schnittes z. B. um 14 % effektiver ist als die Intervallhalbierungsmethode. Im Vergleich zu diesem und weiteren sequentiellen Verfahren ist es – mathematisch gesehen – das für allgemeine Funktionen effektivste Verfahren; nur im Fall differenzierbarer Funktionen ist es der direkten mathematischen Lösung unterlegen.[9]"

and this is translated via google translate to english:
"It is assumed that each point in each interval may be associated with the same probability extreme point, this results in uncertainty intervals mean that the method is more effective the golden section by 14%, for example, than the interval bisection method. In comparison to this and other sequential process, it is - mathematically - the most effective method for general functions, except in the case of differentiable functions, it is inferior to the direct mathematical solution."


and they talk something about a 14 percent increase of effectiveness, are you aware of that ?! cause i dont really understand it, but
they say if we know that it is an equal property possibility on an interval to have a zero point inbetween it is 14 percent more effective
... so, you say this would not increase rendering time or accuracy when applied to our raymarching problem

[hobold]

... so, you say this would not increase rendering time or accuracy when applied to our raymarching problem

Yes, that's what I am saying. The Golden Section search is optimal for a more general case. But the fractals of interest here usually have a signed distance estimate. So there is no need to guess on which side of the intersection point we are. Improvements to that particular guess are just not relevant.

[cKleinhuis]

but we are not always using the distance estimators
brute force is widely used not only for global illumation but for zero point finding as well, at least in fragmentarium