What is the easiest (not most efficient or fastest) algorithm to find the closest points between two triangular meshes? What are the easiest early out algorithms in the broad phase? What kind of broad phase algorithm would you recommend if I only have 2 (large and complex) objects? Lastly, what is the again easiest way to compute the closest point between two triangles?
In the absence of further clarification on what the restrictions are, I'm going to assume two meshes that are basically polygon soup (a set of triangles, possibly unconnected).
You're basically doing n*m triangle to triangle collisions (where n is the number of triangles in object A, m the number in object B). The easiest way is to simply do a brute force closest-point-between-two-triangles for every pairing of triangles. So check triangle 0 in object A against triangle 0 in B, then 1 in B, 2, etc.
Triangle to triangle checks are pretty straightforward, if you have the RTC book mentioned you probably have a better algorithm already. But basically you only have three cases
- the two triangles are parallel (in which case any point on the triangle is equally close to the other triangle)
- an edge on one triangle is parallel to a line which crosses the triangle. So you can find two lines of equal length, one contained in the first triangle, one in the second. As those lines are parallel to each other, every point along those lines is equally close to the equivalent point on the other triangle.
- a single vertex of one triangle is closest to some point on the plane inside the other triangle.
The 3rd case is just a closest-point-on-triangle-to-point, for which you project the point onto the plane of the triangle (i.e. find the closest point to your target on the plane which contains the triangle), and then constrain it to be within the triangle. If the projected point is within the triangle, then you have your closest point, otherwise you now have 3 closest-point-on-line-to-point problems, which you can solve with dot products (and pick the smallest of the three solutions).
Again you can brute force the triangle-triangle check, by iterating every vertex in triangle X and doing a closest-point-to-triangle check against triangle Y; then iterating every vertex in Y and doing a closest-point-to-triangle check against X. Now for each vertex you have a distance to the other triangle. If you have one vertex which is strictly closer than all the others, you're in case 3, and you're done. If you have two vertices on the same triangle equally close to the other triangle, you're in case two. If all three verts of one triangle are equally close to the other, you're in case 1.
In terms of optimisations / early outs, you need to find a cheaper way of testing two triangles for rough closeness, so that you can discard all but the few potential options. I think you could probably get a lot from AABB checking. E.g.:
- for each triangle calculate the AABB
- for each triangle pairing (n * m), calculate the distance between the two closest parts of the AABB, and the two furthest parts (separating axis makes this fairly cheap).
- Now you know that for those two triangles, the closest point is somewhere in between those two distances.
- Find the pairing with the smallest maximum distance ([min], [max]). From that pairing you know that you have a closest point which is at most [max] distance away, and so you can eliminate all other pairings which have a minimum distance further away than [max], because even at its best, the pairing is worse than the one you already have.
This is a really broad topic, and I suppose the answer would be 'it depends'. I can recommend the book 'real time collision detection'. There are a lot of options, and they all have tradeoffs.
My guess for easiest early out would be using a grid, then again, it's not very effective if you only have two large objects, in which case bounding volumes are a good choice.
Only having two objects is kind of weird though, could you give us a scenario? (as it is, it smells a bit like a homework question)
The following answer assume a fairly good grasp of geometry.
The shortest distance between two triangles fall into one of four cases:
It is between two corners, calculate all the corner to corner distances.
It is between a corner and an edge, calculate all the corner to line distances, remember to assert that the point on the line you find is actually part of the edge, if not then the number must be discarded.
It is between two edges, calculate line to line to distances, again assert that the points on the lines are on the edges.
It is between a corner and a centre area, calculate the corner to plane distances, assert that the point on the plane found is within the area of the triangle.