Logo by Tglad - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Visit us on facebook
 
*
Welcome, Guest. Please login or register. February 23, 2019, 04:51:44 AM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: raymarching optimization using golden ratio ...  (Read 1793 times)
0 Members and 1 Guest are viewing this topic.
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« on: December 27, 2012, 04:52:36 PM »

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 !?
huh?
Logged

---

divide and conquer - iterate and rule - chaos is No random!
hobold
Fractal Bachius
*
Posts: 573


« Reply #1 on: December 28, 2012, 01:32:16 AM »

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.
Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #2 on: December 28, 2012, 03:27:00 AM »

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 huh?

Logged

---

divide and conquer - iterate and rule - chaos is No random!
hobold
Fractal Bachius
*
Posts: 573


« Reply #3 on: December 29, 2012, 03:42:18 AM »

... so, you say this would not increase rendering time or accuracy when applied to our raymarching problem huh?
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.
Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #4 on: December 29, 2012, 12:21:32 PM »

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

---

divide and conquer - iterate and rule - chaos is No random!
Pages: [1]   Go Down
  Print  
 
Jump to:  


Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.108 seconds with 27 queries. (Pretty URLs adds 0.005s, 2q)