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: Did you know ? you can use LaTex inside Postings on fractalforums.com!
 
*
Welcome, Guest. Please login or register. March 29, 2024, 11:21:58 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 [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 794 times)
0 Members and 1 Guest are viewing this topic.
knighty
Fractal Iambus
***
Posts: 819


« Reply #15 on: May 31, 2012, 08:25:33 PM »

I did something similar. See the file attached with this post. I did so for the same reason: banding artifacts. AFAIK, these bandings are caused by the fake AO not the normals. One needs the determination of the surface to be more accurate in order to remove those artifacts. This can also be achieved by binary search or secant method as Lycium said. The secant method is in principle much faster.
I would use binary search or secant methods on CPU. On GPU, I thought it's better to keep it as simple as possible. There is also the delicate issue of numerical accuracy, critical on the GPU.

The "color shifting" problem is well known and it's still not solved. Maybe it's possible to compensate it by using the derivative of the coloring function w.r.t. the distance estimate...?

Edit: Maybe this thread should go into programming section.?
« Last Edit: May 31, 2012, 08:27:42 PM by knighty » Logged
khyperia
Guest
« Reply #16 on: May 31, 2012, 09:39:25 PM »

This can also be achieved by binary search or secant method as Lycium said. The secant method is in principle much faster.

Mind linking me to a explanation of the secant method? Many people are talking highly of it, yet I don't know what it is.

Knighty, I opened up the Pklenian/fragment.glsl, I'm assuming its this-
Code:
D = (side * d(p + totalD * dp) - totalD * min_dist) * MINDIST_MULT;
So you integrated this formula (or rather your formula, I give credit to you for figuring it out first) into the raymarching step, am I correct? I actually started to hammer out ideas for that, but I guess you're already doing it.   Azn

Slightly offtopic: Wow, even knighty is joining in. I've never talked to people I look up to like this before! Thanks for everything, everyone!
Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #17 on: May 31, 2012, 09:50:16 PM »

Edit: Maybe this thread should go into programming section.?

side question, and what existing board you would choose for that ?!

board is going to be re-organized throughout the year i think ...
Logged

---

divide and conquer - iterate and rule - chaos is No random!
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #18 on: May 31, 2012, 10:07:04 PM »

With respect to getting the normals more accurately than is possible using DE derivatives or other analytical methods there's also the old stand-by that takes a little extra computation i.e. ray cast the surrounding 4 half-pixel offset rays around the ray for the surface pixel along short line-segments around the distance found for the pixel concerned and use any surface points found to compute the normal - that way at least the normal is directly based on the actual surface found using the algorithm rather than hoping the analytical method matches closely enough wink
Using restricted line-segments on the adjacent rays means that the overhead is considerably less than you might think plus of course the method is more generic in that it works in cases where no analytical method exists or is accurate or optimum enough.

Actually that's the only method I've ever used anyway;)
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #19 on: May 31, 2012, 10:17:02 PM »

Also with respect to a colouring method I just had a thought that the next simplest to solid colour would be one based solely on the direction of the surface normals - requiring hardly any extra computation to get a colour, I guess someone's done that but I don't recall anyone......
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #20 on: May 31, 2012, 11:52:48 PM »

I did something similar. See the file attached with this post. I did so for the same reason: banding artifacts. AFAIK, these bandings are caused by the fake AO not the normals.

Are you sure? I get very heavy banding even without AO. Take a simple hollow sphere:
Code:
float  DE(vec3 z)  { return abs(length(z)-1.0); }



The first image is the sphere rendered without any backstepping. The second shows how close the hit point was to the surface (black is exactly on the surface, where the gradient is zero). The third a backstepped version. Notice how the gradient is wrong at the points where the ray hit closest to the surface.

Of course banding may arise many places, including AO, glow, etc...

Mind linking me to a explanation of the secant method? Many people are talking highly of it, yet I don't know what it is.

Try this: http://en.wikipedia.org/wiki/Secant_method

With respect to getting the normals more accurately than is possible using DE derivatives or other analytical methods there's also the old stand-by that takes a little extra computation i.e. ray cast the surrounding 4 half-pixel offset rays around the ray for the surface pixel...

Yes - in John Hart's original paper, he used the Z-buffer as one way to calculate normals (whole instead of half-pixel offset) but screen space methods often have other artifacts, e.g in your case a pixel in the background may have a half-pixel neighbor in the foreground, resulting in wrong normals along the rim of objects covering each other. I prefer the numerical gradient way, it is just necessary to stop before hitting the surface (one way or another).
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #21 on: June 01, 2012, 05:38:41 PM »

Are you sure? I get very heavy banding even without AO. Take a simple hollow sphere:
Code:
float  DE(vec3 z)  { return abs(length(z)-1.0); }
In your example the banding is due to discontinuousity in the gradient. If you remove the abs, the banding will disappear. There is another way to obtain a hollow sphere by using the sign of the DE at the initial point. Because I  used this method, I didn't get the banding problem with normals but with AO and fog.
Anyway, just wanted to say that khyperia is not wrong about the method -which does the job just like every method cited in this thread- even if naming it "binary search" is misleading if not wrong.

side question, and what existing board you would choose for that ?!
Well... programming board. wink

Knighty, I opened up the Pklenian/fragment.glsl, I'm assuming its this-
Code:
D = (side * d(p + totalD * dp) - totalD * min_dist) * MINDIST_MULT;
So you integrated this formula (or rather your formula, I give credit to you for figuring it out first) into the raymarching step, am I correct? I actually started to hammer out ideas for that, but I guess you're already doing it.   Azn
Yes it is integrated in the raymarching step.
Logged
khyperia
Guest
« Reply #22 on: June 02, 2012, 06:24:01 PM »

Anyway, just wanted to say that khyperia is not wrong about the method -which does the job just like every method cited in this thread- even if naming it "binary search" is misleading if not wrong.

Yeah, sorry about that. I didn't know what to call it, and I thought there was only one formula out there for doing this, so I said its a new way of doing things.
Once again a case of a arrogant dummy thinking he's the best in the world embarrass
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.153 seconds with 24 queries. (Pretty URLs adds 0.009s, 2q)