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
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?
Please log in or register to post a reply.
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?
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).
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.
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.
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.) ;)
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.