# pouët.net

## So, what do distance field equations look like? And how do we solve them?

category: code [glöplog]
As in raymarching how do we figure out the distance to the closest object? It's not immediately clear to me. The only thing I can think of is to grow a sphere and test every object until we get an intersection- I'm sure that would take too long. How do you find this distance quickly?
added on the 2009-08-08 19:33:38 by sigflup
you basically construct a function that returns the distance to the nearest point on your surface, and step along a ray by the distance returned by that function until you hit the surface. in some cases you can use a conservative approximate function instead.
added on the 2009-08-08 19:42:54 by kusma
Why would you step along the ray if that function has already returned the exact distance?

Just asking, my math skills suck and I never completely understand how to ray trace depth fields / implicit surfaces.
added on the 2009-08-08 19:47:50 by Rob
*understood
added on the 2009-08-08 19:48:21 by Rob
You jsut trace into the ray direction. Let's say the depth field at the eye position is 5. so you know that you can go 5 units into whatever direction without hitting anything. so you go ahead 5 units into the ray direction and then GOTO 10 until you actually hit something or decide that it's slowly taking too long :)
added on the 2009-08-08 19:52:35 by kb_
actually every geometry has its own unique distance function. you can of course construct new geometry by modifying this distance function (adding a little bit of noise for a rocky surface for example). if you rotate the distance function in function of an angle with a constant derivative for example (linear angle values), you will end up with a twisted geometry.

the thing is, the distance to the closest object is just:
Code:`min(distance1, distance2)`

in other words, you just calculate the distance from your current position to the object's surface for each object and you just use the minimum of these values. and that also means, there will not be any object closer to you than the object with the minimum distance from your position, thus you can advance on your ray that much and it will not create any geometrical artifacts (actually iq has a wonderful presentation / paper about this, Rendering Worlds in Realtime or something like that). therefore, we are indeed growing a sphere :D but our sphere just doesn't linearly grow. its radius grows to the next closest distance from our current position on the current ray.

I am very tired and have a little hangover, I also experience some euphoria and happiness hormone overdose due to assembly :), but hopefully I could help a bit.
added on the 2009-08-08 19:53:36 by decipher
actually every geometry has its own unique distance function. you can of course construct new geometry by modifying this distance function (adding a little bit of noise for a rocky surface for example). if you rotate the distance function in function of an angle with a constant derivative for example (linear angle values), you will end up with a twisted geometry.

the thing is, the distance to the closest object is just:
Code:`min(distance1, distance2)`

in other words, you just calculate the distance from your current position to the object's surface for each object and you just use the minimum of these values. and that also means, there will not be any object closer to you than the object with the minimum distance from your position, thus you can advance on your ray that much and it will not create any geometrical artifacts (actually iq has a wonderful presentation / paper about this, Rendering Worlds in Realtime or something like that). therefore, we are indeed growing a sphere :D but our sphere just doesn't linearly grow. its radius grows to the next closest distance from our current position on the current ray.

I am very tired and have a little hangover, I also experience some euphoria and happiness hormone overdose due to assembly :), but hopefully I could help a bit.
added on the 2009-08-08 19:54:04 by decipher
Quote:
you basically construct a function that returns the distance to the nearest point on your surface
.

ok, my question is what does this function look like? I can't think of a fast way to do it
added on the 2009-08-08 19:54:45 by sigflup
Helps, a little decipher. Thanks.
added on the 2009-08-08 19:56:45 by sigflup
I understand the raymarching of a landscape/2d map. Is it something like that?

I have read all IQ's articles but there just hasn't been this 'AH!' moment :(
added on the 2009-08-08 19:59:34 by Rob
sigflup I just told it :), but here's an example:
Code:``` float sphere(float x, float y, float z, float r) { return sqrt(x * x + y * y + z * z) - r; } float distance(float x, float y, float z) { float s1[3] = { 3.f, 4.f, 10.f }; float s2[3] = { 1.f, 4.f, 8.f }; float d1 = sphere(s1[0] - x, s1[1] - y, s1[2] - z, 3.f); float d2 = sphere(s2[0] - x, s2[1] - y, s2[2] - z, 3.f); return min(d1, d2); } ```

there you go :)
added on the 2009-08-08 20:01:48 by decipher
or simpler for origin-aligned objects...

Code:``` float sphere(float radius) { return length(radius); } ```
added on the 2009-08-08 20:03:31 by ferris
sigflup: Depends on your geometry. Read Iq's article, it has some examples (I won't reveal mine yet, hehe).
added on the 2009-08-08 20:03:42 by kusma
Ok, how about a cube? or some wicked polynomial? I've seen this done with fractal objects as well
added on the 2009-08-08 20:03:53 by sigflup
Also, for the comment about why you'd need to step, some of these objects get deformed and some are more complex than simple geometric distances can represent, such as a twisting cube.
added on the 2009-08-08 20:05:05 by ferris
cube:

Code:``` float cube(float x,float y,float z,float size){ return max(max(abs(x)-size,abs(y)-size),abs(z)-size); } ```

This is a simple intersection of 6 planes.
added on the 2009-08-08 20:06:41 by ferris
BTW most of this info can also be found in this paper, where most of us learned the methods we use for raymarching implicit surfaces ;)
added on the 2009-08-08 20:08:46 by ferris
Thanks a lot. Going to experiment a bit with this hoping to understand it all :)
added on the 2009-08-08 20:11:29 by Rob
So what you're saying is we have to calculate all the space-deformations (twisting.. and so fourth) and then test every object keeping a record of the smallest distance.
added on the 2009-08-08 20:11:53 by sigflup
ahh... reading zeno.pdf it looks like they forget objects that are outside their bounding volume before finding the distance of the real thing
added on the 2009-08-08 20:17:23 by sigflup
erm...sort of :/

Let me outline the basic algorithm:
Code:``` vec3 p = camera position; vec3 v = ray direction; while(length(p)<20.) { // Limit rays somehow to avoid endless loops d=min(test1,test2); if(d<0.) { calc intersection stuff and break } p+=v*d; } ```

Now i just used test1 and test2..but either test should look something like:
Code:``` float cube(vec3 p,float size){ float angle=p.y*.2; p=vec3(p.x*cos(angle)+p.z*sin(angle),p.y,p.z*cos(angle)-p.x*sin(angle)); // Rotate p along the y axis to twist the cube. return max(max(abs(p.x)-size,abs(p.y)-size),abs(p.z)-size); } ```

..Make sense?
added on the 2009-08-08 20:18:15 by ferris
...IQ's article explains deformations better than any I think.
added on the 2009-08-08 20:18:42 by ferris
An important point is that deformations are object-specific and should only be applied to a temporary vec3 p just before distances are calculated.
added on the 2009-08-08 20:20:19 by ferris
ok, thanks ferris.
Anyone have a link to iq's article? I've found some slides but so far that's all.
added on the 2009-08-08 20:20:42 by sigflup
For demos, you should go after geometric shapes that yields simple functions. start with a sphere, do booleans with other simple objects.. that's a smart thing that some people already did.

generally, creating, say, a 3d-matrix of distances to a given surface can be generated for later, possibly realtime, use. Danielsson's algortihm from 1980 is supposed to do this and i'm sure the algorithms have gotten better since then :)

added on the 2009-08-08 20:21:35 by Hyde