Shortest Directed Distance between two 3D Triangles?

E16f3fa370e8c89f12369e007fc2b33c
0
Kuroyume 101 Sep 30, 2009 at 01:40

As much as I appreciate David Eberly’s math and code for many 2D/3D CG problems, most of the time it requires quite a bit of extracting his highly-dependent levels of code to get everything you need. In other words, it is too much work to convert his overly generalized library to direct code with an existing code base (id est: unchangeable).

Anyway, with that said, my situation is a bit more specific than his generalized triangle-triangle distance code. I need to find the minimum global Y distance between two 3D triangles. The problem is that the triangle-triangle code devolves into a 3D segment-segment code which then gives you the absolute minimum distance in whatever direction. This will not work for my needs - needs to be an axially aligned minimal distance.

It is disconcerting that there is not a single reference to math, algorithm, or code for this situation (which would probably be a frequent need for any gravity-based collision, stacking, and so on). Any takers on how to approach this mess in an efficient manner?

Thanks!
Robert

6 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Sep 30, 2009 at 03:46

If I understand your problem correctly, can’t you simply compute each triangle’s extent on the y-axis (the min and max y of the vertices) then compare the extents in 1D?

E16f3fa370e8c89f12369e007fc2b33c
0
Kuroyume 101 Sep 30, 2009 at 04:32

No, that’s incorrect. Not the absolute closest no matter what. The closest points directly along the Y-axis so that if you subtracted that distance the triangles would touch.

That’s the problem. Most triangle-triangle tests (Moller, Eberly) are simply seeking intersection (there is no intersection!). I want the distance that brings them into primary ‘intersection’. In a non-time dependent scenario, one could just check a very fine resolution grid of points over the two triangles to find the shortest distance (a scan-line approach). When you want to find this before the end of time (because there are literally tens of thousands of triangles to test) you must consider optimal situations. The situation is that the edge segments of each side of each triangle checked against the edge segments of the other is the current popular method - but even as complex as this is, it yields the absolutely shortest distance indifferent to the direction of this distance vector. In reality, say one triangle completely enveloped by the other from an X-Z plane projection, one must do both segment-segment and segment-triangle tests. And I only want to consider the shortest distance in one direction.

For example, you have two complex polygon objects, one above the other, and you want the one above to move so as to be just touching the other. Not polyhedrons, not planes, any polygon objects. One must get down to considering polygon-polygon - in my case triangle-triangle - distances to do this. Think placing a set of polygon-object trees (hovering above) onto a polygon-object landscape accurately. Currently, I do ray-triangle intersection testing where the source triangle’s vertices are the start of the ray directed -Y towards the target triangle. This is good in many situations but doesn’t cover all cases (where none of the source/target triangle vertices are actually over the target/source triangle even though the two triangles obviously intersect).

E16f3fa370e8c89f12369e007fc2b33c
0
Kuroyume 101 Sep 30, 2009 at 04:58

For illustrative purposes, here are two situations where, looking along the -Y axis, the vertex-triangle and segment-triangle tests would fail. Note that these two polygons need not be coplanar or in any way like-oriented in 3D space.

Case1.jpg

Case2.jpg

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Sep 30, 2009 at 15:33

Ok, I think I understand.

Basically, you’ve got two polygons, and you want to find the minimum y-axis translation such that they intersect.

If so, there is no simple clear cut solution to this. Your best bet is to ray cast from each vertex in each polygon and check for an edge intersection in the second.

A more general approach would use the simplex algorithm.

E16f3fa370e8c89f12369e007fc2b33c
0
Kuroyume 101 Sep 30, 2009 at 17:01

Yes, that’s it.

I’m currently using a ray-triangle intersection test to get the distance using each vertex as the origin of the ray. (Added: ) Also doing a similar test using the triangle’s centroid. But it can fail in the cases illustrated (among others) and therefore isn’t always accurate or efficacious. I was only doing a one-way test though (source to target polygon). Seems that most algorithms for this are testing both directions so that might eat up some more cases.

The segment-triangle distance test is a bit more costly and haven’t found a really good source to do this - except Eberly’s WildMagic which is, as mentioned, very terse (lots of fluff and descending into classes - four levels at last count).

Do you have more information on the simplex algorithm? (I’ll Google about but Google has been more useless than usual lately.) ;)

Thanks,
Robert

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Oct 01, 2009 at 04:32

Yeah, you need to test both directions: from A to B and B to A.

For Simplex, the Wiki page is ok, and it has some good links by the looks of it.

Basically you’re just formulating the problem as a system of linear equations, and the simplex algorithm is an algorithm that solves a system of linear equations. I haven’t actually used it myself, but I’m pretty sure that’s what they use for proper physics engines where the normal hacky methods aren’t good enough.