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