pouët.net

Go to bottom

Inaccuracies strolling along a ray in GLSL. -.-'

category: code [glöplog]
Hello!

Sadly I can't access my old username, but you wouldn't know or remember me anyway. ^_^
First of all ... Praised be the demoscene and its sceners, I never stopped loving you all! :)

I ask here, because you're the top of the mountain and there's no freaking point asking
anywhere else anyway and I always feel comfortable here. ^_^
So glad this site hasn't changed much! :D


OKAY, so, I wanted to get back into gfx coding and do my first steps in GLSL,
so I kind of hacked together a ... not really ray tracer, not really ray marcher I think.

It's a mess, but I'm slowly understanding how this stuff works! Woohoo! :D


Okay, so I'm throwing rays through a 3d simplex noise on my fragment shader and
for some reason I actually managed to get it to work! After losing lots of blood, sweat,
tears and sacrificing a lamb I now am stuck at a weird problem.

BB Image

I apologize for the colors (^_^), but I have no normals yet. This is the highest precision,
where my ray steps 0.01 forward. It works, it's fine, it's damn slow.

So I thought, just like I've read about ray marching,
I'll start doing bigger steps until I hit something.

So this here is with steps the size 0.1.

BB Image

Okay, now my issue comes in when I want to increase my step resolution.

I stroll along the ray through the simplex at 0.1 steps until I find a value above my threshhold.


Code:vec3 rs,ro,rd; float i = 0.1; float j = 0.01; float a; while (s < 0.1) { i+=0.1; rs = ro + rd * i; s = snoise(rs); }


Then I take a step back and do the same again, but at higher resolution.

Code: i-=0.2; s = 0.0; vec3 rt = ro + rd * i while (s < 0.1) { j+=0.01; rs = rt + rd * j; s = snoise(rs); }


This creates this and you can see the difference and inaccuracies.

BB Image

I've tried several variations of doing this, which I've all abandoned already.
The latest now is this ...

[code]
s = 0.0;
while (s < 0.1)
{
a++;
rs = ro + rd * (i*a);
s = snoise(rs);
}

s = 0.0;
a-=1;

float b = 0;
vec3 rt = ro + rd * (i*a);

while (s < 0.1)
{
b++;
rs = rt + rd * (j*b);
s = snoise(rs);
}
[code]

... because I thought maybe adding 0.1 every loop is too much for floats (wtf?),
but it produces a similar result.

I also tried cutting the direction vector and using that one instead
and it actually works really well, but I still get the same issues.


Okay, I hope I didn't accidentially mix up some code,
but I think I get the point across.


I'm strolling along a ray in steps of 0.1, trying to find (s > 0.1).
Whenever I find (s > 0.1) I take a step back and do smaller steps of 0.01 to find that s again.

My issue is that his doesn't create the same image as if I did steps of 0.01 right from the start.


Oh please dear mighty gods of the demoscene, help me out! D:
I've been wasting days on this and I can't figure out what's going on!


Thanks!
I guess I still can't edit posts?
So glad things haven't changed that much. xD

Sorry for the broken code-tag above. -.-
Yes that is ray marching, you're just marching small constant steps along the ray instead of an optimized strategy. It's generally not a very good algorithm for anything realtime. I don't consider myself an expert but I'd recommend trying a better method, possibly just good old sphere tracing (the thing that most people call "ray marching").

'm not sure what exactly causes the artifacts, but I think it's simply that your step size is so large that you simply march right through the geometry without even registering a hit. Your hack of course works when the surface is thick enough and you approach it parallel to the surface normal, but along the edges the accuracy just isn't enough. Not sure what causes the discontinuity in the middle though, but probably also a side-effect of your approach.
added on the 2015-08-21 11:14:37 by noby noby
Basically what noby said. Consider very small or thin features, your step might go straight past it, then continue like nothing happened. You get holes, glitches, generally bad things happen :)

So yes, look at SDFs (spherical distance functions, a.k.a. sphere tracing). They sound harder than they are :) Basically it gives you the distance to the closest surface, which is good because you know you can move along the ray by that distance without stepping past anything. Empty spaces = big steps, small features aren't skipped.
added on the 2015-08-21 11:33:57 by psonice psonice
SDF can also be translated with "signed distance function" which means that the distance inside the volume is negative)

I don't know what your snoise function looks like. If it is a valid distance function then you can add the return value directly to your vector for the next iteration.
Typical example:
Code:for(int i=0; i<35; i++) { dist += scene(startPos + dir*dist); }
added on the 2015-08-21 13:18:02 by movAX13h movAX13h
Thanks for your replies!

I'm not sure I follow. Assuming I overstep at some parts, it doesn't explain the differences when I step back and remarch at 0.01 ... does it? I mean, ofc I might overstep some parts but once I hit and step back (I tried various distances), then remarch at 0.01 I should get the same detail as in the highres image... but I don't.

Does this make sense? Hm...

Eye ................... ray ..................... Blob.

At 0.1 I might it at Bl.ob.

So I step back to x ...

Eye ................... ray ..................x... Blob.

... and then remarch at high resolution.

Am I blinded somehow? Does it actually work as expected, except for some parts and I make too much of an issue about the small inaccuracies? I will look into that...


Re: Raymarching/sphere tracing.

I have read pretty much everything besides pdfs that re too math heavy.
I'm not much of a mathemagician. :/

At some point I wanted to believe that it's a massive conspiracy and doesn't actually work and everyone just pretends it works. ^_^

And... I have no idea how to spheretrace a 3d simplex noise algorithm.
I understand the idea of spheretracing halfways,
however it doesn't make any sense in my head...

I've been reading through the raymarching threads here as well. ^_^

Oh and yeah my approach isn't probably the best, but it was what I came up with first and I have some ideas to speed it up. Not dismissing other techniques, it's just so I learn how to use GLSL. ^_^

Open for anything... don't want to waste yet another day without progress.
MovAX ... I'm using this noise function.
https://github.com/ashima/webgl-noise/blob/master/src/noise3D.glsl

And I don't think I understand.

Sorry for crappy layout or slightly weird sentences, I'm at work and on mobile right now.
The problem isn't exactly overstepping, it's MIS-stepping. Consider the following picture.

BB Image

The line is your ray, the dots are your iterations. With very low sampling frequency, you're going to get in a way a form of aliasing. Even though the ray in reality intersects the geometry, due to the marching step the algorithm isn't even aware of some of the geometry because the primary rays don't sample it initially at high enough frequency. Of course it's completely possible that with a different offset an iteration could land inside the blob (and some do), and that's when your algorithm works, but it's extremely unlikely these missteps wouldn't happen along the geometry edges. With 10 times higher step frequency you're going to have little to no such cases with your current geometry. The non-edge parts of the surface are mostly the same in both versions. The slight differences could come from slightly different sampling offsets.

As said, look into sphere tracing instead, you'll reduce your iteration count by an order of magnitude or two, and with better quality typically :). Distance fields impose some more restrictions and have their own problems, but in the long run it'll get you a lot further. I recommend to stay away from the academic papers for start at least. They're "intentionally" complex and mathematical, and aren't intended for people trying to understand the concept without a proper knowledge (certainly took a while for me). Rather try googling up some web articles intended more for a layman.

Hopefully that helps, and I myself didn't misunderstand anything.
added on the 2015-08-21 14:02:18 by noby noby
Ok, I don't post to much on pouet.net but I was wondering, Does anybody know a way to estimate distance to "3D noise" ?
added on the 2015-08-21 14:08:52 by kloumpt kloumpt
Thanks noby! I will try to make deeper sense of it after work.
Damn, you people are all geniuses!

And what kloumpt said. I tried googling for it, to no avail.
Doesn't help me not grasping it fully.
@Noby: Aaahhhhhhh...... hhhmmmm........
What you actually do is raymarching a density field... why not just do it the hacky way and adjust your stepsize to the density? Fiddle with magic constants and some clamping until your scene looks right.

If in doubt, add lot's of noise 2D layers with boom boom soundtrack over it to hide any artifacts... hehehe.
added on the 2015-08-21 15:19:38 by EvilOne EvilOne
Quote:
And... I have no idea how to spheretrace a 3d simplex noise algorithm.

Quote:
Does anybody know a way to estimate distance to "3D noise" ?


This was probably discussed over and over in different threads, but anyway...

Most people don't trace their SDF in a correct way, obviously.
Overestimated/underestimated distance, discontinuities, etc.. are very common, often just ignored.

If you don't know it already, IQ did a nice compendium about basic SDFs:
http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

But, as you can see, he did not find general solution to domain deformations or distance deformations (i.e. by adding 3d noise). All he proposes is to decrease step size "somehow". And some people do it totally by trial&error until they find a sweet spot that looks good and is not slowing it down too much, i.e.

approxSDF(p)*factor, where factor < 1

But in fact, if your function has bounded slope (which is true for gradient-noise function by definition, such as Perlin noise), this factor depends on inverse of maximum slope, as the function just cannot "go" faster towards zero. So your distance function will be bounded simply to noise value divided by |max slope|, or more formally:

|exactSDF(p)| >= |approxSDF(p)*factor|, where factor = 1/|max slope|
added on the 2015-08-21 15:31:34 by tomkh tomkh
and be true... version with 0.1 stepsize actually looks damn cool :-D Looks like isoline tracing there... some clever postprocessing and you can make it look like the second effect from asd/monolith. Profit!
added on the 2015-08-21 15:31:49 by EvilOne EvilOne
@EvilOne: what? :/ I'm doing what and ... what? What density?
How would I even know that? Sheesh, I'm dumb, but I'll think about it.
And please don't think I'm looking for done solutions! I am trying to learn!

Btw, I know I could "voxelize" the whole thing beforehand, but I wanted to avoid using any buffers...
@tomkh: Thanks! I like cats!

(=I read so much about raymardhing, distance fields and I've seen the distance functions on IQs site... it makes no sense to me, like your post. Sorry...)
Hell, what's a bounded slope. English? I have to google half your post... no I'm not complaining about you being smarter than me, I'm just clueless as fuck when it comes to math, especially combined with english, though I doubt language changes much.
Here is someone sharing his source for ray marching through noise

https://0xef.wordpress.com/tag/ray-marching/

What you basically can do is create a look-up texture containing the distances from every point in the texture.

To do so you can find any point outside the noise function, then find the nearest point inside the noise function from there through brute force (for each pixel sample all other pixels and get distance for each other pixel that is 'inside' the noise; store minimum distance found for that pixel).

Code: foreach pixel: if pixel inside noise function: return 0 bestDistance = diagonal of 3D texture; sqrt(width * height * depth) foreach other_pixel: if other_pixel inside noise function: bestDistance = min(distance, bestDistance) return bestDistance


You can make this faster by beginning to sample around the current pixel, expanding the search radius until something is found. Just create a map of how to sample from an arbitrary point in space, where the map tells you the 3D positions to sample in an optimal order; closer points first.
Thanks Trevor, but I wanted to avoid buffers.
I am able to figure out how to do it with precomputed buffers, but I want to avoid them.
I mentioned it too late, just a few posts above.

Sorry...
Now I feel bad for bothering you guys.

I'll spend the night trying to decipher tomkh's post.
Solecist:
In this case I use "slope" colloquially. What it really stands for is a direction/magnitude of a gradient.

From wikipedia:
"The slope or gradient of a line is a number that describes both the direction and the steepness of the line"

However, we have a little more complicated case here, since it is a 3d dimensional function distance = f(x,y,z), but you can still measure at a given point its "steepness". To make it simpler, let's imagine a 2d surface function: z = f(x,y). Now we can find at every (x,y) a tangent plane and measure its "steepness" as a tan( angle between this plane and z = 0 plane ).

Now, by bounded slope, I simply mean a "slope" that has well-known finite maximum (and minimum, if we add direction to it). In this case, it would be equal to maximum "steepness".

If we go back to your 2d surface example, and we pick any (x,y) with positive value z = f(x, y), we can be sure that the closest "zero" (f(x,y) = 0) is at a distance >= z / |max "steepness"|

Hopefully it explains a little better what I mean, not worse ;-)
added on the 2015-08-21 16:13:19 by tomkh tomkh
Still have to dig, but I understand it better!

Thankd! :D
How do we measure steepness of a single point in space?
Or it's tangent?

You imply sampling surrounding points, like for normals?
I'm trying to imagine how it works,
but all my brain comes up with is a single point.

Hm.

Okay, the point has a value that might (?) gives clues about surrounding points.
My code filters out every point below 0.1, which show as black only anyway.

So based on the value of the point I can tell if there are any surrounding points?
I could then sample these, but again I would have to find these first...

I don't get it ...
Solecist:
The function you are dealing with is:

w = f(x,y,z)

It is a density function (you assign density to a point in 3d space). You can also imagine this function as a "terrain" (3d surface) in 4d, but I don't think it really helps.

Nevertheless, 2d, 3d or 4d, calculations are the same. You can approximate gradient by central difference (for some small real number h > 0):

grad(f) = (f(x+h,y,z) - f(x-h,y,z), f(x,y+h,z) - f(x,y-h,z), f(x,y,z+h) - f(x,y,z-h)) / h

And then absolute "steepness" = length(grad(f))

It's just like you calculate slope for a line:

grad(f) = ( f(x+h) - f(x-h) ) / h

just add extra dimensions.

Now, you would want to estimate max. length(grad(f)) for all points in space. Sometimes, if you know enough about your function, you can totally do it.
For example Perlin noise, since it is a gradient-noise, by definition has bounded max. length(grad(f)), and it should be in fact equal to 1.0 (lol) or your noise scale (amplitude) if you multiple it by something. If it's 1.0 you can totally use a abs(noise value) as a good distance estimation.

But in reality, people use shitty noise functions that tend to be faster than a proper gradient-noise, so it might be smaller than 1.0.

Also if you combine multiple noise functions (fBM) or use it to deform some other SDF representing a shape (cube, sphere or whatever), you will get different function and it will be harder and harder to find out accurate max. "steepness" value. That's why you will end up with trial&error anyway :P
added on the 2015-08-21 18:45:20 by tomkh tomkh

login

Go to top