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

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

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.

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)

Ah, my bad.

Since your scalar fields are true distance functions, you get a collision whenever the center of your sphere, if it has radius r, 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. However, I can't come up with an example where the gradient evaluated at the center of the sphere isn't identical to the gradient evaluated at the contact point (for the case of distance fields, and spheres), and I think -- though I could be mistaken -- that you can show this to always be the case.

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

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?

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.

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

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 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 isn't 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?

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.

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.

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 signed distance function and you want to find the closest point on the surface, you need to go uphill, but when you're outside you need to go downhill. Consider the one-dimensional "d(x)=abs(x)-1" example.

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)

For points outside union(S1,S2), it's correct. The definition 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 inside 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.

Thanks again for the taking the time to try and enlighten me!

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?

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

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

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

For points outside union(S1,S2), it's correct. The definition 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 inside 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.

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

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.

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)