Andreas Brinck skrev:
> does anyone know where I can find code that computes the distance between a
> box and a triangle. I was first thinking about extending David Eberly's
> rectangle to triangle distance code, but I think the original code is too
> long as it is (every case written out explicitely). I'm also thinking about
> formulating the problem as a quadtratic programming problem with constraints
> but haven't been able to find a small free solver that is easy to integrate
> into my code. Any pointers would be much appreciated.


I'm not aware of any small freely-available QP solvers, but if you
are willing to implement them from scratch, the most promising ones
for small problems seem to be the randomized algorithms of Gärtner
and of Botkin.

As others have mentioned, the GJK algorithm will give you the result
you need, and there's code available for it.

You can also implement it in terms of simpler primitives by recognizing
that (for non-intersecting primitives) the closest points must be a
vertex, on an edge or on a face of each primitive. You then write
tests for all feature pairs, picking the pair of points giving the
globally smallest distance. Trivially you can reduce this to triangle-
triangle distance computations, but those are sort of expensive in
themselves. However, if you look at all feature-feature tests, there
are certain tests that are not needed, such as face-face tests (which
are subsumed by others).

In your case I would probably go for GJK, because its pretty fast and
code already exists.


Christer Ericson
Sony Computer Entertainment, Santa Monica