`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