# pouët.net

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

category: code [glöplog]
iq: so you've been looking into using spherical harmonics as an improvement to the algorithm too? :)
added on the 2010-05-11 09:30:24 by kusma
I have not done any experiments, just thought about it cause it seems like the obvious improvement to me. Did you get any interesting results? Share with us, pls!
added on the 2010-05-11 10:31:20 by iq
umm iq, the link to Johns paper actually link sot falty...can you redo the link?
added on the 2010-05-11 13:06:01 by auld
Sorry I mean to the 1989 paper...
added on the 2010-05-11 13:06:48 by auld
iq: No, I haven't implemented anything (and I doubt I will, I'm lazy on the coding front these days), just trying to map out the possibilities and issues. I'm thinking that the closest distance should be the constant part of the spherical harmonic (obviously), and the directional part needs to be conservative. How to ensure that is still a little bit of mystery to me still, and I don't have much math background. I'm expecting that the spherical harmonics can be build simply by looking at the gradients of the distance field, but I have no experience in building spherical harmonics.

I'm also suspecting that there could be some issues with interpolating the spherical harmonics without risking to end up with a non-conservative distance. Intuitively it sounds like it should be OK, but I'm not strong enough on maths to tell for sure without spending a lot more time than I have ;)

If interpolation is a problem, then it should be a simple matter of disabling texture-filtering; the constant part of the spherical harmonic makes sure one always ends up stepping at least one voxel - unless on the surface of course.

Perhaps the best result performance-wise would be to do the first iterations considering many coefficients, and gradually lowering the amount of coefficient you consider? I'm thinking that as you get closer to the surface, the low-frequency coefficients become more important (well, they always are, but more than normally :P). The more iterations you've considered, the more likely it is that you are close to the surface. ESPECIALLY if you're using a lot of coefficients early on.

I also think it would be interesting to look at building a voronoi diagram of the scene (based on Zheng Qin's work on vector glyphs, extended to 3D). Perhaps one could build a 6-dimensional voronoi-diagram, taking the direction into account? Of course, 6-dimensions would be too much for texture mapping based approaches, so something like spatial hashing would have to be used I guess.
added on the 2010-05-11 13:51:54 by kusma
ok, just found that indeed Jhon was indeed one of the authors of the paper on raymarching fractals too in 1989.

1989 raymarching 3D Julia Sets : http://graphics.cs.uiuc.edu/~jch/papers/rtqjs.pdf
1996 raymarching distance fields ("sphere tracing"): http://graphics.cs.uiuc.edu/~jch/papers/zeno.pdf

The rest of the papers: http://graphics.cs.uiuc.edu/~jch/papers/
added on the 2010-05-11 18:30:14 by iq
iq, I see your point but there is still a slight difference in clarifying "spheretracing" and you have explained why. The original problem is "how to efficiently render an implicit surface?"... a class of methods to solve this problem is somewhat called "raymarching in distance fields", but inside this class (finding roots and selecting, or the first root), there are lots of different methods/algo : constant step, bisection... and "spheretracing".

So, when we are talking about raymarching using spheretracing algo... this way, I know which algo you are talking about... but when It's only "raymarching in distance fields", I don't know which method is used. That's probably the only point that disturb me when I read your article.

I agree also that strictly speaking, we are following the trace of a ray, but the ray is traced in a "minimum bounding sphere" way (Hart's algo). All the images referring to this algo are drawing the same thing here :

as you said it's a "schematic picture", a "ray" and "spheres" are actually drawn to explain the algo, and when I see this picture, I know that It's the "SphereTracing" algo from Hart and nothing else.

But ok, in the end, I agree with you, speaking about "raymarching in a distance field" is preferable, as it is a more general term and can be derived into several methods.

To come back to the real subject here :), so far, I haven't been able to significantly improve raymarching methods that is enough small and much more efficient to make the difference in a 4k. I tried the sphere packing stuff, the coarse grain volume pre-rendering, level of detail... but nothing arise from that as a general improvement method... just specific to some scene configuration, and sometimes, requires more shader's code (like the duplication of code involved in level of detail) for just a slight improvement.

added on the 2010-05-11 18:58:17 by xoofx
trying to understand this...

given an implicit surface equation of the form f(x,y,z) = 0 is the distance function simply f(x,y,z) ? Is this the "best" distance function for this surface (ie the one that gets you to the surface in least steps)?
added on the 2010-05-13 16:45:37 by auld
no, many functions f(x,y,z)=0 can parametrice the same surface, but not all represent a distance. For example, a sphere can be represented by

[1] x^2 + y^2 + z^2 - R^2 = 0

[2] (x^2 + y^2 + z^2)^7 - R^14= 0

[3] sqrt( x^2 + y^2 + z^2 ) - R = 0

but only the last is a distance in the euclidean sense.
added on the 2010-05-13 18:25:49 by iq
Quote:

distance to a rounded cube:

Code:

Code:``` float distToCBox( in vec3 p, in vec3 box, float rad ) { return length( max( abs(p) - box + vec3(rad), 0.0 ) ) - rad; } ```

box is, as usual, half the length of the box's side
rad is the radious of the curvature

What's the reason behind the max(..., 0)? Having negative distances is helpful for determining if I am inside the box.
added on the 2010-05-14 10:51:17 by xTr1m
the max is so the proper coordinates get masked out in the Pythagoras computation so distances to the faces, edges and vertices of the box are computed with one single formula (will have to the math yourself to check how that works). If you are inside the cube you will have to apply another formula, which is simpler probably (distance to the closest face, no need for edges and vertices).
added on the 2010-05-14 11:03:29 by iq
length() is a nice op afterall :D
( only used it in my first raymarcher ( constant stepsize ) and tried to avoid it afterwards...for some reasons ( that only apply to my affinity to keep it smaller than small ) )
and i have to say: i tried more than once to come up with some easy solution to get the rounded_cubes, but having length() completely clamped out of my possibilities i never came up with that solution ofcoz, haha !
sometimes the shadow is something to jump over ! mostly if its your own ! ( so not only if your min_stepsize is too big :p )
How do you calculate the normal vectors for a distance field? Just define the normals for each part separately?
added on the 2010-05-16 13:59:10 by msqrt
the answer is just one click away...
added on the 2010-05-16 19:21:43 by iq
The gradient of a scalar field (like a distance function) is the direction in which the scalar function grows most rapidly. For distance fields that means the direction pointing most away from nearby surface points (i.e. the normal).

You can find the gradient most easily by numerical differentiation, as discussed in this thread.
added on the 2010-05-16 19:36:37 by doomdoom
iq, I don't know which click of the all possible ones :)

Thanks doom, that clears stuff out. Seems like the solution was very easy after all.
added on the 2010-05-17 00:22:55 by msqrt
guys, add this to your toolboxes: signed distance to a box:

Code:```float signedDistToBox( const vec3 & p, const vec3 & b ) { const vec3 di = abs(p) - b; const float mc = maxcomp(di); return mc<0.0f ? mc : length(max(di,0.0f)); }```

you can use this one too, if you think square roots are faster than conditional movs:

Code:```float signedDistToBox( in vec3 p, in vec3 b ) { const vec3 di = abs(p) - b; return min( maxcomp(di), length(max(di,0.0)) ); }```

maxcomp(vec) returns the greater component of the vector.

(note - this doesn't mean I'm doing raymarching lately, it only means I'm playing with formulas)
added on the 2010-06-03 02:22:56 by iq
(why the ugly double spaces? I'm 100% sure I didn't have them nor I had double \n\r in the submit box... Anyway
added on the 2010-06-03 02:23:36 by iq
msqrt: the only problem with the said method (and unfortunately so far the only generic method for distance fields) is that you have to sample the field many times with a virtual epsilon offset from the current point of sampling.

in other words, this is shit slow :/
added on the 2010-06-03 11:12:03 by decipher
When you deform objects by rotating your rays (something like rotateray(p.y)), you are distorting the distance field and some values are getting closer together. Is there a way to acount for that? Or do you just use a simple estimation like dist(p)* 0.8?
added on the 2010-07-07 08:33:41 by TGGC
I suppose the answer is just a a few clicks away.
added on the 2010-07-07 10:27:40 by raer
you rotate the actual point of the ray and dont bend the ray itself or sth !
for the next step you give your distance_estimator-function the unrotated point of the ray ( plus the last minimal distance ofcoz ) as input again.
oh wait, i think i see what you meant...but theres no workaround i´d say ! just dont rotate too heavy !
simple estimation could fix some of the more visible stuff ofcoz, hehe...
If you’re twisting around z (the transformation is [x, y, z][x cos a·z − y sin a·z, x sin a·z + y cos a·z, z]), the distance should be divided by √(4r² + π²/a²) (a is in radians and r = √(x²+y²) is the distance from the twisting axis).

See page 18 of the paper for a nice picture.
added on the 2010-07-07 11:34:14 by rrrola
hehe, lots of extra-gpu (/cpu) -load...but ofcoz theres math to fix it if you dont need it in realtime or just have a monster-PC :)
on the other hand refraction and even some (soft-)shadows arent that much of extraload, while AO is nearly for free...i really need a better grafix-card to see what these new ones are capable of ! as what i´m coding these days isnt running any better than 30fps on that 8800GTS :/ smash-syndrome ?
Thanks for the pointer. Now lets see, if something comes out from it ;-)
added on the 2010-07-08 08:54:43 by TGGC