Continuous distance function

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Numsgil
Posts: 38
Joined: Wed May 14, 2008 5:58 am

Continuous distance function

Post by Numsgil »

I'm working on a collision detection algorithm, and I'm looking for alternatives to GJK for calculating the "distance" between two convex polyhedra. At this point performance isn't a concern, as it's very speculative research. Instead, I want these basic properties:

1. The distance function returns a constant value (call it D) if the two polyhedra are *just* touching. It doesn't matter if this constant is 0 or not.
2. If the two bodies are overlapping the distance function returns a value < D that is proportional to the overlap.
3. If the two bodies are separated, the distance function returns a value > D that is proportional to their separation distance.
4. The distance function is ideally C^infinity. That is, it has a well defined derivative. And its derivative has a well defined derivative. And so on and so on. cos(t) is C^infinity, for instance. If I can't get C^infinity I'll settle for as many derivatives as possible.

If #4 still doesn't make sense, I basically want the value of the distance function to smoothly change as you move either polyhedra, assuming you move it in a way that is itself smooth. For instance, if you were translate one of the bodies on the curve <t, cos(t)> and track the "distance" of the two polyhedra over time, I'd like it to appear smooth.

Vanilla GJK falls over on 2 and 4. The usual refinements to GJK handle 2 but definitely not 4. As different features of the two polyhedra become the closest pair the distance function gets a kink in it as the first and higher derivatives vanish. This is going to be true for any algorithm that returns the actual distance between the bodies. So I want something that works a bit like distance but isn't.

For instance, in 2D if I were to calculate the signed area of the two polygons connected with a zero area channel (a common technique in CSG algorithms), its value will be less than the actual area of the two polygons iff they're overlapping. The amount the computed area falls below the actual area, the more they're penetrating. The signed area performs a lot like penetration distance. It does really well with #2, but doesn't help at all with #1 and #3, and I suspect #4 fails as well. Gluing signed area together with GJK would give me everything except #4.

A more sophisticated idea is to use the gradient of generalized barycentric coordinates. See this presentation, page 76. This satisfies all the criteria above, and even relaxes the convex requirement, but it's only defined for a single point. So if I were interested in finding the distance between a point and a polygon (polyhedra are possible too with some modifications) this would be perfect! But it doesn't seem to really generalize to polyhedra vs. polyhedra. It might be possible to modify this idea to give distance between polyhedra by forming some composite function of all the vertices in one of the polyhedra against the other, but forming a smooth composite function is tricky, and there are collisions that can happen between polyhedra that don't involve any vertices (edge-vs-edge for instance).

I may just be looking at this problem from a weird direction, so I'm curious if anyone has any other directions to explore?
DannyChapman
Posts: 84
Joined: Sun Jan 07, 2007 4:29 pm
Location: Oxford, England
Contact:

Re: Continuous distance function

Post by DannyChapman »

If performance isn't a concern, you could calculate the Minkowski difference between the polyhedra and then use your generalized barycentric coordinates to get a distance measure between that and the origin which, as you say, will have a well defined derivative, and will handle overlap/separation.

But this seems too obvious, so perhaps I misunderstood something?!
Numsgil
Posts: 38
Joined: Wed May 14, 2008 5:58 am

Re: Continuous distance function

Post by Numsgil »

Yeah, that's actually the approach I'm exploring right now. I'm sort of off on my own in left field at the moment, though, so I'm looking for some perspective.
Post Reply