Andreas Brinck skrev:
> does anyone know where I can find code that computes the distance=20
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=20
too
> long as it is (every case written out explicitely). I'm also thinking=20
about
> formulating the problem as a quadtratic programming problem with=20
constraints
> but haven't been able to find a small free solver that is easy to=20
integrate
> into my code. Any pointers would be much appreciated.
I'm not aware of any small freelyavailable 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=E4rtner
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 nonintersecting 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 featurefeature tests, there
are certain tests that are not needed, such as faceface 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
