# Colliding vs an implicit distance field

## Recommended Posts

raigan    1110
By "implicit distance field", I mean you don't have a grid of sampled distance values, instead you evaluate distance functions, see e.g [url="http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm"]http://www.iquilezles.org/www/articles/distfunctions/distfunctions.htm[/url]

Those distance functions will tell you the closest distance to the surface at a given query point, but for e.g sphere-vs-distance-field you need a distance + direction. This could be approximated by finite differences (i.e query at (x,y), (x+1,y), (x,y+1) and use the difference in returned distance to infer the closest point) but I'm wondering if there's a simpler/cheaper/more direct way.

thanks,
Raigan

##### Share on other sites
Emergent    982
The sphere case is easy; just find the closest point to the center of the sphere, and compare its distance from the center to the radius.

Ellipses you can also do in the same way, after a (linear) change of coordinates (to make the ellipses spherical).

Finally, note that the collision normal is the gradient of the scalar field.

##### Share on other sites
raigan    1110
Thanks... maybe my question was a bit confusing.

I understand how to collide a sphere, but to do that you need a closest point. What I meant to ask was: how exactly might one "find the closest point to the center of the sphere" given a distance field defined implicitly as a set of distance functions? (see that link I posted)

##### Share on other sites
Emergent    982

Since your scalar fields are true distance functions, you get a collision whenever the center of your sphere, if it has radius [i]r[/i], reaches the r-sublevel set of the function.

(You would not have this luxury if your surfaces were the zero-level sets of some other functions besides distance fields.)

I also see part of the problem now. Although it is easy to determine collisions, determining normals is a little trickier. To be absolutely sure it's right, you'd need to evaluate the scalar field's gradient at the contact point. That contact point can probably be determined by a few iterations of Newton's method. [i]However[/i], I can't come up with an example where the gradient evaluated at the [i]center[/i] of the sphere isn't [i]identical[/i] to the gradient evaluated at the contact point (for the case of distance fields, and spheres), and I [i]think [/i]-- though I could be mistaken -- that you can show this to always be the case.

##### Share on other sites
raigan    1110
Thanks! I'm going to try implementing this today.

In order to calculate the gradient at a particular point, are there any options that aren't finite-difference-based?

Also, I have to admit that I don't really understand what you meant by "(You would not have this luxury if your surfaces were the zero-level sets of some other functions besides distance fields.)"... my mathematical intuituin regarding level sets is not great. I can visualize them as a plane intersecting a terrain (the energy function) but I realize there are deeper mathematical meanings which I'm ignorant of

##### Share on other sites
raigan    1110
Well, this didn't really work.

Specifically, just calculating the distance from a query point doesn't really work -- it seems to be a conservative estimate, so that if you use it as Quilez intended (e.g raymarching) it does converge correctly, when distance=0 you're on the surface. However if you use it to calculate the distance to a surface from an arbitrary point, it will fail in many cases -- basically any time the point is inside any of the volumes. This is especially problematic for e.g different and intersection, where much of the volume might be empty/non-solid... if the query point is inside one of these, the results aren't always correct.

I also tried stepping towards the surface from the query point, similar to Newton's method: calculate the gradient via forward difference at the current position, then step along the gradient by the current position's distance. This seems to work okay if the query point starts outside the volumes, but it fails in general.

Am I missing something, or is what I want to do just not possible?

##### Share on other sites
Emergent    982
[quote name='raigan' timestamp='1328912791' post='4911805']
However if you use it to calculate the distance to a surface from an arbitrary point, it will fail in many cases -- basically any time the point is inside any of the volumes.
[/quote]

I thought most of the formulas on the page you referenced were for [i]signed[/i] distance -- so, they're positive when you're outside, negative when you're inside, and the absolute value is the distance to the surface.

[quote name='raigan' timestamp='1328912791' post='4911805']
I don't really understand what you meant by "(You would not have this luxury if your surfaces were the zero-level sets of some other functions besides distance fields.)"[/quote]

My point was just that the sphere is colliding with the zero-level set if and only if the center is a distance 'r' from the level set. Since "How far away am I?" is exactly what a distance field returns, you just need to check whether it evaluates to a number less than r. But what if your function [i]isn't[/i] a distance field? You can imagine other functions that have the right zero-level sets, but that DON'T tell you the distance to the set when you're at other points; (when you're not on the zero level set, it can return any other number, so long as it's nonzero).

Let's consider a simple 1d example. Say our set is the interval [-1,1]. The signed distance to this set is just

d(x) = abs(x)-1 .

Another function that also evaluates to zero at the same points is,

f(x) = x^2 - 1

but the number it returns isn't the distance to the set. E.g., the point 2 is d(2)=1 away from the set, not f(2)=3 away from the set.

Does this clear things up, or am I not answering your question?

##### Share on other sites
raigan    1110
Thanks for your reply! Now I see what you were saying about the distance field, thanks for explaining.

I do understand about signed distance, however that shouldn't make a difference though, should it? i.e marching along the gradient should always bring me to the surface (the point where the distance function is 0) regardless of whether I'm "pulled" down or "pushed" up by positive/negative distance.

What I meant was that the union/subtraction/intersection functions listed on that page don't seem to actually be correct as distance functions. Take for example the union operator: min(d1,d2)

This implies that the shortest distance from a query point to a union of 2 shapes will always be the distance from the query point to a closest point on one of the shapes in the union.

AFAICT this is incorrect in general -- imagine for example if the query point is in the area where two circles overlap: each circle will report the distance to its surface, but the correct global distance isn't either of those, instead it's one of the two points where the circles' boundaries intersect. I hope this example is clear... basically the correct global distance value is often not a closest-point for any of the individual shapes.

Possibly this is correct and I'm simply not marching along the gradient correctly? Is it possible that signed distances don't work with the union/subtraction/intersection operators?

I feel like I'm missing something pretty fundamental here -- the functions definitely work for ray-marching (i.e they are 0 only at the surface of the correct union/subtraction/intersection volumes) but seem to fail as distance functions in general for some reason.

##### Share on other sites
Emergent    982
[quote name='raigan' timestamp='1328971064' post='4911960']
I do understand about signed distance, however that shouldn't make a difference though, should it? i.e marching along the gradient should always bring me to the surface (the point where the distance function is 0) regardless of whether I'm "pulled" down or "pushed" up by positive/negative distance.[/quote]

First: Why do you need the closest point? You should be able to test for collisions without knowing it (you just need to be able to evaluate the distance function at the center of the sphere). Is it because you want to evaluate the gradient there? Have you tried just using the gradient at the sphere's center?

Second: When you're inside, if you have a [i]signed[/i] distance function and you want to find the closest point on the surface, you need to go [i]uphill[/i], but when you're [i]outside[/i] you need to go [i]downhill[/i]. Consider the one-dimensional "d(x)=abs(x)-1" example.

[quote name='raigan' timestamp='1328971064' post='4911960']
What I meant was that the union/subtraction/intersection functions listed on that page don't seem to actually be correct as distance functions. Take for example the union operator: min(d1,d2)[/quote]

For points outside union(S1,S2), it's correct. The [i]definition[/i] of the distance from the point to a set, is that it's the minimum over all the distances to all the points in that set.

But for points [i]inside[/i] union(S1, S2), it is only an upper bound on the signed distance (lower bound on the distance to complement). It does always have the correct sign and the correct zero-level set.

1d example:

In 1d, all signed distance functions take the form

d(x) = abs(x-a)+b

for some constants a and b.

Now say your sets are the intervals,

S1 = [-5, 1]
S2 = [-1, 5] .

Then you have the signed distance functions

d1(x) = abs(x+2)-3
d2(x) = abs(x-2)-3 .

Now define the function

f(x) = min(d1(x), d2(x)).

Question: Is f(x) a distance function? If you plot it, you'll see that the answer is "no." It doesn't have the shape of a shifted/translated absolute value function.

##### Share on other sites
raigan    1110
Thanks again for the taking the time to try and enlighten me!

[quote name='Emergent' timestamp='1329021608' post='4912178']
First: Why do you need the closest point? You should be able to test for collisions without knowing it (you just need to be able to evaluate the distance function at the center of the sphere). Is it because you want to evaluate the gradient there? Have you tried just using the gradient at the sphere's center?
[/quote]

In order to respond to the collision I need a surface normal (which, with the distance, implies a closest point). Evaluating at the center of the sphere failed in the case of compound operations (union/intersection/subtraction); since things seemed to converge on the correct normal when distance=0, I figured marching downward towards the closest point (distance=0) might be useful. But it's not [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img]

[quote name='Emergent' timestamp='1329021608' post='4912178']
Second: When you're inside, if you have a [i]signed[/i] distance function and you want to find the closest point on the surface, you need to go [i]uphill[/i], but when you're [i]outside[/i] you need to go [i]downhill[/i]. Consider the one-dimensional "d(x)=abs(x)-1" example.
[/quote]

I think I was doing this right -- I was marching against the gradient, pos -= distance*gradient (which marches downhill when distance is positive and uphill when negative).

[quote name='Emergent' timestamp='1329021608' post='4912178']
For points outside union(S1,S2), it's correct. The [i]definition[/i] of the distance from the point to a set, is that it's the minimum over all the distances to all the points in that set.

But for points [i]inside[/i] union(S1, S2), it is only an upper bound on the signed distance (lower bound on the distance to complement). It does always have the correct sign and the correct zero-level set.
[/quote]

Yeah, this is what I was afraid of.

It's not the union so much as the subtraction/intersection operations -- with union you expect your objects to stay on the outside (of course, in practice they might not, but that can be addressed later) so things will be well-behaved. But in the case of subtraction/intersection, all of one/some of both volumes (respectively) will be empty space, which means it's likely that the query point will be inside the volume and ruin the correct result (which only happens when the query point is outside of both volumes).

[quote name='Emergent' timestamp='1329021608' post='4912178']
1d example:

In 1d, all signed distance functions take the form

d(x) = abs(x-a)+b

for some constants a and b.

Now say your sets are the intervals,

S1 = [-5, 1]
S2 = [-1, 5] .

Then you have the signed distance functions

d1(x) = abs(x+2)-3
d2(x) = abs(x-2)-3 .

Now define the function

f(x) = min(d1(x), d2(x)).

Question: Is f(x) a distance function? If you plot it, you'll see that the answer is "no." It doesn't have the shape of a shifted/translated absolute value function.
[/quote]

Thanks, this makes it clear to me.

I guess there's just no way to do what I want? (e.g compose simple primitive distance functions -- sphere, box, etc. -- into compound functions which represent CSG operations on sets of primitives)

##### Share on other sites
raigan    1110
[quote name='Emergent' timestamp='1329021608' post='4912178']
First: Why do you need the closest point? You should be able to test for collisions without knowing it (you just need to be able to evaluate the distance function at the center of the sphere). Is it because you want to evaluate the gradient there? Have you tried just using the gradient at the sphere's center?
[/quote]

The gradient at the sphere's center (and the distance at the sphere's center) is often incorrect -- for example when the sphere is inside one or both of the shapes that form a union, intersection, or difference. As you pointed out these operations don't seem to be preserving the true-distance-field-ness of the distance function, just providing upper/lower bounds.

I tried adding some damping to my gradient descent, and now it does converge (barring certain degenerate configurations) on the correct closest point. A more sophisticated approach to approximating the gradient might help improve convergence (currently I'm just doing a forward difference by sampling at p, p+(1,0), p+(0,1)).

It seems like fundamentally what I want is impossible: I drew the isosurface contours of a circle+AABB intersection distance function, and it's just not correct... it's like the voronoi regions of the edges of the shape are smeared outward. AFAICT this isn't due to error in my code, rather it's fundamental to approximating e.g the intersection of A and B as max(dist_A, dist_B) -- the correct answer (i.e the true distance) is often neither the distance to the closest point on A or the distance to the closest point on B, because where the boundaries of the two shapes intersect new vertices are formed which are ignored in this approach.

What's weird is that many people seem to be using these sort of signed distance functions (and their composition via union/subtraction/intersection operators) with no problems, e.g [url="http://persson.berkeley.edu/distmesh/index.html"]http://persson.berke...mesh/index.html[/url]

##### Share on other sites
Emergent    982
[quote name='raigan' timestamp='1329059983' post='4912272']
I guess there's just no way to do what I want? (e.g compose simple primitive distance functions -- sphere, box, etc. -- into compound functions which represent CSG operations on sets of primitives)
[/quote]

I don't think there's a nice way if you need to make sure that all your functions truly are distance functions. It doesn't feel like it should even be possible using just the two functions' values at the one point.

I guess you're ok if you don't use the assumption that your scalar field is a distance field, though. That means you're back to numerical minimization, but maybe that's ok. Unfortunately, there [i]will[/i] be local minima, so Newton's method by itself won't give you any guarantees; you'll really need to sample your functions over the surfaces of your objects.

##### Share on other sites
raigan    1110
Yeah, that's too bad -- I was hoping this would be a cheap alternative to explicit/sampled/grid-based distance fields. Oh well