What I need to do is find the smallest possible distance that exists between two convex polyhedra. I am using this to determine leaf visibility in a BSP tree as a function of distance. The method I'm using works well and I'm pleased with the results, but I'm not sure if it's finding the real distance or works always, because I really had no formal knowledge of how to tackle this problem. I basically wrote up some basic code, and added fixes for every test situation I discovered that didn't work. This is how I arrived at my current process. I'll just explain the core algoritm, and we can assume it loops through each leaf and checks it against each other leaf, et cetera. In addition, I already have all the data I need, such as the vertices and face normals, which face outwards from the center of each polyhedra respectively: Please note that I interchange plane and face. I am quite aware of the difference, but I usually refer to plane when I'm doing plane operations such as dot products, and use face if I'm refering the the actually shape/vertices of the polygon. ---------------------- First, loop through each face of Polygon 1 , searching for one which contains all vertices of Polygon 2 on its front side. We will call this face/plane split_plane . If none exist, we resort to a somewhat exhaustive method (ewww, but right now it's all I can think of). We create "bounary planes" (planes which enclose a face and are parallel to the normal) for each face of Polygon 1 , clip all the faces of Polygon 2 to these these boudaries and then find the minimum of the distances between all the points of the final clipped faces and the face on Polygon 1 . We then do the same thing with Polygon 2 and Polygon 1 . The minimum of all calculations is taken. If we do find our split_plane , create a list of all faces of Polygon 2 which contain all vertices of Polygon 1 on their front sides. IF we have more than one of these such faces/planes, we calculate their intersection points and take the minimum of their distances to split_plane (my logic is that if you have two or more planes which meet the criteria that also intersect, their intersection point have to be closer to split_plane than any other point on the faces themselves. Could be completely wrong ). IF we have only one of these such faces/planes (face/plane Q ), (this is where it gets hunky-dorey difficult), we first create "boundary planes" for split_plane. If any of the points on face Q lie completely within the "boundary planes", we take the minimum distance between all the points that lie inside and split_plane . Otherwise, we take the minimum distance between all the points on split_plane and plane Q . However, if none of these such planes exist, we take the minimum of the distances between all the vertices of Polygon 2 and split_plane . ---------------------- In addition to that (because I'm still unsure that it works in all cases), I added a basic vertex-to-vertex check for each of the vertices of both polyhedra. This tends to generate larger distances than the previous method, but only the minimum of everything is taken into consideration As you can see, that's the low-down dirty way I'm calculating my distances . No idea if they're 100% exact, but they generate good results I guess my question is: What's the proper, formal way to do this? It really bugs me that I don't know, being the big math advocate I am. [edited by - Zipster on May 2, 2002 2:53:28 AM]

I use V-clip. V-clip doesn''t itself give you a distance. It reports the pair of features (face-vertex, edge-edge, vertex-edge or vertex-vertex) that contain the closest ponts on the polyhedra. But as these are the closest points calculating the distance is then just a point-plane, line-line etc. distance calculation away.

V-clip is very efficient and robust, but it''s quite an effort to implement. A comparable algorithm that uses a different approach but produces similar results is GJK. Both have been implemented in collision detection libraries.

Sounds good. Now that I''m reading up on it, I like the sound of the V-Clip method. Although non of my polyhedra will collide, and I hear that Lin-Canny is "faster", I also hear it''s a "code complexity", with plenty of degenerate cases. Nasty

Actually, now that I think about it, I don''t know if I want to implement any of those algorithms. I was thinking about the situation today, when an idea hit me:

What I would do is take every face on Polyhedra 1 and create those special "boundary planes". I would then clip all the faces on Polyhedra 2 to these boundaries and face. If everything wasn''t clipped away, I take the shortest distance of all the points in the remaining clipped polygons to the original face. Rinse and repeat for every polygon on Polyhedra 1. Then, I switch the check, so that we are comparing Polyhedra 2 with Polyhedra 1.
As a final check, which will handle any cases the previous method can''t do (such as two cubes disjoint in two or more axis), I plan to do a simple vertex-to-vertex check for all the vertices on both polyhedra.

Thoughts? It sounds slow, but it''s really easy for me to implement, and it sounds like it would work really well! I know I said I wanted speed, but I can always make some odd optimisations here and there.

Ok, just wanted to say that I finished coding the algorithm, and it works great! (in addition to the vertex-to-vertex check for those special cases )

I guess if no one else has anything to say, then.... it''s OK to close this thread, I''ve reached my Nirvana

It seems clear to me that the minimum difference would be between points on an edge of each. Why not compute the orthocenter of polyhedron A, then find the closest edge on polyhedron B, then find the closest edge to that on polyhedron A, then use standard algorithms to find the minimum distance between them?

Sneftel said:
>It seems clear to me that the minimum difference would be
>between points on an edge of each. Why not compute the
>orthocenter of polyhedron A, then find the closest edge on
>polyhedron B, then find the closest edge to that on polyhedron
>A, then use standard algorithms to find the minimum distance
>between them?

Because it''s incorrect. Picture a small cube sitting on
top of a large cube, in the middle of the top face.
The closest feature on the large cube to the small cube
is then the top face itself, not one of its edges (nor
vertices).

An efficient method for testing convex polyhedra against
each other is the GJK algorithm. If you don''t want to
implement it yourself, there are publicly available
implementation from e.g. Cameron and van den Bergen.


Christer Ericson
Sony Computer Entertainment, Santa Monica

I actually like the method I use now. It''s suprisingly robust and simple to implement; I only have to add a vertex-to-vertex check afterwards to finish the processing. However, even though I was able to get the number of checks from O(n²) to O(^n!/_{2(n - 2)!}), the entire process takes longer I think it''s the result of the math used to clip a face to a plane. But the slowdown is minimal with a few extra optimizations, and since the processing is done at compiletime, there aren''t any realtime speed requirements anyway. I also managed to get rid of processor data crunching sounds: turns out that an if(x) delete x; type statement makes crunching noises, as opposed to just a delete x; situation. Kinky