Shortest Directed Distance between two 3D Triangles?
Posted 30 September 2009 - 01:40 AM
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?
Posted 30 September 2009 - 04:32 AM
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).
Posted 30 September 2009 - 04:58 AM
Posted 30 September 2009 - 03:33 PM
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.
Posted 30 September 2009 - 05:01 PM
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.) ;)
Posted 01 October 2009 - 04:32 AM
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.
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users