Logo by yv3 - 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: Follow us on Twitter
 
*
Welcome, Guest. Please login or register. March 29, 2024, 12:21:11 PM


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] 2   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: New binary searching algorithm  (Read 795 times)
0 Members and 1 Guest are viewing this topic.
khyperia
Guest
« on: May 30, 2012, 05:05:01 PM »

Goal of algorithm: Have every point on the screen be "distance" away from the fractal, instead of the randomness generated by 'stepping until you're closer than distance'.

Old Binary Search algorithm: Step back and forth by halving or doubling distance, may take a long time, I don't really understand how it works.

My new algorithm: Use the DE to find this optimal distance. I'll let the code speak for itself. (hlsl, although probably very easy to port, seeing as its 2 lines of code)

Code:
void BinarySearch(inout float3 p, float3 look, float distance)
{
for (int i = 0; i < 5; i++)
p += mul(look, DE(p) - distance);
}

Now, what's going on here? 'p' is the last position in this ray. 'look' is the normalized direction the ray was heading. 'distance' is the distance you WANT the point to be away from the fractal.
Then comes a for loop. Duh.
Now, the actual algorithm. First, lets look at 'DE(p) - distance'. This value very well may be negative, meaning we actually have to 'step back' to get to the optimal distance away. Multiply this by 'look' to get our movement for this step, and then apply (add) it to 'p'.

There, no more massively complex, time-consuming Binary Searching algorithms. I have been using this algorithm for a long time, and it has been working very well for me. Increase or decrease iterations for accuracy, I almost arbitrarily chose 5.
Logged
eiffie
Guest
« Reply #1 on: May 30, 2012, 05:35:59 PM »

We call this ray marching not binary searching if I am understanding you correctly. "distance" is usually an estimated pixel scale which varies with the length travelled.
Logged
khyperia
Guest
« Reply #2 on: May 30, 2012, 09:38:52 PM »

We call this ray marching not binary searching if I am understanding you correctly. "distance" is usually an estimated pixel scale which varies with the length travelled.

No, no, no, this is AFTER the ray marching step, once you have "hit" the fractal. The problem with ending there is that every single pixel is a random amount away from the fractal (under the 'hit distance', of course), which can cause unwanted noise (usually in the form of banding).
You want every single pixel to be exactly 'x' distance away from the fractal (or as close to x as sanely possible) to ensure a smooth look.

Example is attached, the bottom one is without this binary searching formula, top is with. The only difference in the programs are two forward slashes commenting out the call to the binary search, that is it. (ignore the jpg artifacts, had to fit in the 256kb file limit)


* both.jpg (240.82 KB, 853x960 - viewed 58 times.)
Logged
eiffie
Guest
« Reply #3 on: May 30, 2012, 10:27:44 PM »

OK, I see but its still raymarching smiley You are making sure the result is signed and does not hit the surface since your DE function does not return a signed result. That part confused me because I use a signed DE. I would call it signed raymarching with a few extra steps. I've only used one extra step so maybe I will try this approach.
Logged
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #4 on: May 30, 2012, 10:35:20 PM »

Isn't this what the 'stepcount for binary search' does in Mandelbulb 3D?
Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #5 on: May 30, 2012, 10:45:56 PM »

Isn't this what the 'stepcount for binary search' does in Mandelbulb 3D?

Seems closer to secant/Newton's method, but it's clearly a refinement procedure.

There does seem to be some lost detail however...
« Last Edit: May 30, 2012, 10:48:05 PM by lycium » Logged

Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #6 on: May 30, 2012, 11:06:47 PM »

Ah, now I see the method tries to stop 'minDistance' short of the surface.

But why not use binary search to instead find the exact surface position (if you move minDistance forward, you should be inside the fractal, and can do binary partition - I imagine that is what M3D does)?

Wrt banding, that might be caused by the normal gradient difference points being evaluated inside the fractal if you are too close to the surface. I always move back a little on the camera ray when evaluating the normal to prevent this.
Logged
lycium
Fractal Supremo
*****
Posts: 1158



WWW
« Reply #7 on: May 30, 2012, 11:14:54 PM »

I agree, and would rather use a binary/secant search (with a potential function) to find the "true" surface, not a Minkowski-fattened version smiley
Logged

khyperia
Guest
« Reply #8 on: May 31, 2012, 02:10:22 AM »

The problem with binary searching to find the exact fractal boundary is that shading/coloring/aftereffects/etc generate way too much noise at that level, aka pixels are not related to each other. Its like zooming in, more detail is revealed when you're closer, and generating high-detail data at a far away distance results in noise. I don't get the purpose of finding the true boundary, it seems pointless.
if you move minDistance forward, you should be inside the fractal, and can do binary partition
No. If the ray direction was, say, 45 degree angle to the fractal, then the distance along the ray direction until hitting the fractal is different then if you were at a 90 degree angle.
The banding is not caused by taking 'normal gradient difference points' inside the fractal. It is caused by different pixels being different distances away from the fractal at normal evaluation time. I don't even use difference points for normals, I use dual numbers, which do not include an arbitrary step distance and instead determine the gradient at a single point.
Just a little question, what are the secant/newtons method you are talking about?
Also, what is a 'signed DE'?
I like how you're questioning my ideas, it makes me look at them in a different light.
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #9 on: May 31, 2012, 03:56:21 AM »

Binary stepping *after stepping to within a given threshold distance* works fine for then finding the coord. that's as close as possible to the threshold distance but setting the threshold distance to zero and expecting a binary search to work in that instance is a non-starter for exactly the reason already mentioned - at zero distance the detail level is literally infinite so it doesn't matter how high a resolution you use or how accurate the maths is (e.g. arbitrary accuracy) trying to get the perfect boundary at zero DE will always introduce randomness/aliasing etc.

As for generally using binary stepping to find a boundary either at a given DE threshold or given iteration level, most fractal ray-steppers have done that since around 2000 wink

For a given DE threshold the accuracy is directly proportional to the bailout (the exact proportionality I think depending on the degree/power factor of the formula concerned i.e. depending on the amount of divergence) and the same applies to a certain extent to using iteration boundaries instead though of course in the case of iteration boundaries there's always a massive variation in detail/business of the surface from one area to another so you either suffer areas with little detail or areas having too much detail thus causing aliasing.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
khyperia
Guest
« Reply #10 on: May 31, 2012, 04:59:00 AM »

As for generally using binary stepping to find a boundary either at a given DE threshold or given iteration level, most fractal ray-steppers have done that since around 2000 wink

And that is exactly what this formula does, finds a boundary at a DE threshold- and it does it faster and more efficiently than binary searching. The resulting point is within a very small margin of error away from the "desired distance" after only a few iterations.
This formula uses the DE result in the calculation, doing a 'smart step' to the desired distance, instead of doing a blind do-nothing-or-halve-the-distance jump that binary stepping does.

Edit: I just realized I'm arguing over fractals with guys like Makin and Syntopia. I'm a little shy to admit it, but I seriously look up to people like you, a lot. Sorry if I'm sounding rude... *nervous laughter*
« Last Edit: May 31, 2012, 05:04:34 AM by khyperia » Logged
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #11 on: May 31, 2012, 08:36:01 AM »

If the ray direction was, say, 45 degree angle to the fractal, then the distance along the ray direction until hitting the fractal is different then if you were at a 90 degree angle.

You're right - the DE is not directional :-) Hmmm, wonder what M3D's binary search actually does?

Btw, I remember reading a paper, where they changed from DE to a fixed step-size if the camera ray was nearly parallel to surface (since you will use a lot of ray steps here). I'll se if I can dig it up.

Quote
The banding is not caused by taking 'normal gradient difference points' inside the fractal. It is caused by different pixels being different distances away from the fractal at normal evaluation time. I don't even use difference points for normals, I use dual numbers, which do not include an arbitrary step distance and instead determine the gradient at a single point.

I'm not convinced. As I see it, the problem arise because we use the gradient of the distance estimate to approximate a surface normal (dual numbers also do this). Now consider the case of a hollow object (thin surfaces - isn't the Mandelbox hollow?). The DE will increase on both sides of the surface - meaning that the gradient will be exactly zero when exactly on the thin surface. This is fairly intuitive, since a thin surface will have two normals, pointing in opposite directions. So we cannot tell the correct one, without taking the direction we came from into consideration. So I think backstepping should also be used with dual numbers - I was not very clear about this when I wrote my blog post on dual numbers, I'm afraid.

Quote
Also, what is a 'signed DE'?

A signed distance field or distance estimator just means the DE will return a negatively signed distance when you are inside an object. This is of course only possible for solid objects, and good interior distance estimates are very difficult to find for fractals.

 I write a bit about signed distance fields and normals at the start of http://blog.hvidtfeldts.net/index.php/2011/08/distance-estimated-3d-fractals-iii-folding-space/.
Logged
khyperia
Guest
« Reply #12 on: May 31, 2012, 03:43:36 PM »

I'm not convinced. As I see it, the problem arise because we use the gradient of the distance estimate to approximate a surface normal (dual numbers also do this). Now consider the case of a hollow object (thin surfaces - isn't the Mandelbox hollow?). The DE will increase on both sides of the surface - meaning that the gradient will be exactly zero when exactly on the thin surface. This is fairly intuitive, since a thin surface will have two normals, pointing in opposite directions. So we cannot tell the correct one, without taking the direction we came from into consideration. So I think backstepping should also be used with dual numbers - I was not very clear about this when I wrote my blog post on dual numbers, I'm afraid.

The thing is, I'm not actually on the edge of the fractal- I'm a little bit away from it. This is the point of the original formula, to get every pixel exactly 'distance' away from the fractal. So even if accuracy is a little bit off, then the normal will only be off a tiny bit, not completely reversed as is the case if the point is inside the fractal.
Logged
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #13 on: May 31, 2012, 03:58:40 PM »

The thing is, I'm not actually on the edge of the fractal- I'm a little bit away from it. This is the point of the original formula, to get every pixel exactly 'distance' away from the fractal. So even if accuracy is a little bit off, then the normal will only be off a tiny bit, not completely reversed as is the case if the point is inside the fractal.

Yes, I know, but I'm talking about the artifacts in your original (the lower part) image - the one without the binary search thing. Here some camera rays may end up exactly at the surface, where the gradient is zero and probably becomes random when normalized (for hollow fractals). I think this causes the banding. Your method solves it, but you can also solve it by backstepping a little before evaluating the normal.
Logged
khyperia
Guest
« Reply #14 on: May 31, 2012, 04:57:39 PM »

Yes, I know, but I'm talking about the artifacts in your original (the lower part) image - the one without the binary search thing. Here some camera rays may end up exactly at the surface, where the gradient is zero and probably becomes random when normalized (for hollow fractals). I think this causes the banding. Your method solves it, but you can also solve it by backstepping a little before evaluating the normal.

The problem with backstepping is that the pixels will still be different distances away from the fractal- different distances mean different outputs from my coloring algorithm, and higher distances mean more averaged normals.
I really need a better coloring algorithm, I've been searching forever for a good one. The one right now is a modified version of the one in Boxplorer, which I think uses final position after a fixed number of iterations and orbit trap, both of which vary with proximity to the fractal.
Logged
Pages: [1] 2   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Searching formula / equation for z^4 and z^5 Help & Support maverdigitalarts 13 2381 Last post November 26, 2006, 03:20:59 PM
by cKleinhuis
Searching for fractals may help cancer cell testing Fractal News across the World trafassel 2 2131 Last post October 25, 2011, 10:41:16 PM
by jehovajah
Mandelbulb 3D - Searching for a Dark Entity Movies Showcase (Rate My Movie) crotafang 0 742 Last post May 02, 2012, 06:10:08 AM
by crotafang
Blender Multibool, Searching for Fractal Fractal Programs mclarekin 3 641 Last post September 25, 2013, 02:15:36 AM
by mclarekin
Searching for lifeforms Images Showcase (Rate My Fractal) AstroArs 0 774 Last post June 18, 2014, 08:27:30 PM
by AstroArs

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.219 seconds with 24 queries. (Pretty URLs adds 0.018s, 2q)