New binary searching algorithm

[knighty]

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

[khyperia]

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.   

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!

[cKleinhuis]

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 ...

[David Makin]

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
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;)

[David Makin]

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......

[Syntopia]

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).

[knighty]

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.

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.   

Yes it is integrated in the raymarching step.

[khyperia]

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