Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
1  
Question: do you actually need complex collision detection? If the answer is no, then you're going about solving your problem in a fairly complex way. – Tim Holt Dec 22 '10 at 20:49
Your comment below says you're building an engineering simulation, but you need to be clearer about what sort of objects you're simulating. Are they convex/concave? Are they allowed to intersect? Do you want penetration depth out of the answer? – MrCranky Dec 24 '10 at 10:17
An observation: @ebusiness and @mrcranky triangle to triangle checks, should come up with the same answer (just remember, As @ebusiness hinted at, you are not guaranteed a unique set of two points in the case that whole edge is the closest). – Jonathan Fischoff Dec 24 '10 at 20:49

3 Answers

up vote 5 down vote

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

  1. the two triangles are parallel (in which case any point on the triangle is equally close to the other triangle)
  2. 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.
  3. 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.
share|improve this answer
The assumption that two meshes are a polygon soup fits to my problem and the answer more than helpful. While four early out heuristics seems pretty adequate, further heuristic proposals will also count. – udurak Dec 25 '10 at 6:08
After the early outs, the closest distance between meshes in the final AABB paring could be an edge of one triangle of meshA and an edge of a triangle of meshB. So measuring against points or vertices only is not always an accurate answer... In game dev, that's probably an acceptable compromise though. In an engineering sim, maybe, maybe not. – Steve H Dec 25 '10 at 14:58
Just to be clear - the four points I make there are just one early-out heuristic - you need to do all four steps to be able to discard the pairings. @Steve H: Not sure what you mean - the AABB checking doesn't tell you anything about closest points, you still need to do the triangle-triangle check (which may come up with various answers like: entire triangle is equ-distant to other triangle, closest edge is equ-distant to line on other triangle, or point is closest to point on other triangle). – MrCranky Dec 27 '10 at 10:06
Edited to note the edge-line case in triangle-triangle checking – MrCranky Dec 27 '10 at 10:20
up vote 1 down vote

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)

share|improve this answer
I second "real time collision detection". It is one of the most useful books I own. You can have a look at few chapters from it here: books.google.ca/books?id=WGpL6Sk9qNAC&printsec=frontcover – arriu Dec 22 '10 at 21:00
Not a homework actually, that's for a quick and dirty solution for an engineering simulation of two dynamic (mechanical) systems. I have the book and make use of it a lot, but I am after collecting the recommendations from the practioners. – udurak Dec 22 '10 at 21:32
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.