Started by Feb 09 2012 04:30 PM

,
12 replies to this topic

Posted 09 February 2012 - 04:30 PM

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

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

Posted 09 February 2012 - 06:13 PM

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.

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.

Posted 09 February 2012 - 06:59 PM

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)

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)

Posted 09 February 2012 - 10:17 PM

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.

Since your scalar fields are true distance functions, you get a collision whenever the center of your sphere, if it has radius

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

Posted 10 February 2012 - 10:37 AM

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

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

Posted 10 February 2012 - 04:26 PM

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?

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?

Posted 10 February 2012 - 08:36 PM

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

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

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?

Posted 11 February 2012 - 08:37 AM

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.

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.

Posted 11 February 2012 - 10:40 PM

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

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

But for points

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.

Posted 12 February 2012 - 09:19 AM

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

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

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

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

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)

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

signeddistance function and you want to find the closest point on the surface, you need to gouphill, but when you'reoutsideyou need to godownhill. 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

definitionof 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 pointsinsideunion(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)

Posted 12 February 2012 - 03:20 PM

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?

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 http://persson.berke...mesh/index.html

Posted 12 February 2012 - 03:29 PM

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)

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

Posted 13 February 2012 - 07:52 AM

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