🔒 Locked

Distance Between Triangles

Started by leoptimus Oct 11, 2005 at 8:33 PM 1 replies 4.4k views

Original Post

Oct 11, 2005 at 8:33 PM

Is there a fast technique for find closest points between two triangles? Separating Axis is the unique method for this? Separating Axis takes 11 direction tests for find the minimun distance, 2 for each plane direction, and 9 (3x3) of the cross product between triangle1 edges Vs triangle2 edges. Each test takes 6 dot products for find nearest projections of the triangles vertices. All this stuff spends a lot of cpu time!

Zakwayda

Oct 11, 2005 at 9:28 PM

Like many other distance or closest point problems, this can be set up in terms of quadratic minimization over a domain. The function to minimize is f(s,t,u,v) = |P(s,t)-Q(u,v)|^2, where P() and Q() are the two triangles in parametric form. The code is somewhat complex, as it involves addressing all the boundary cases individually. However, if it's performance you're concerned about I'd think this would be as fast as any other method (I don't know that for sure though).

leoptimus

Oct 12, 2005 at 1:28 AM

Hey!, I've founded some distance algorithm in WildMagic Library..
check out:
http://www.geometrictools.com/SourceCode.html

However, I don't know if it runs efficiently.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.