agby 132 Report post Posted November 10, 2009 I was poking around looking for an algorithm for finding closest point on a triangle. Found this one on these forums: http://www.gamedev.net/community/forums/topic.asp?topic_id=516608 I kind of recognized it so I tried it out and it doesn't work. :( This paper describes the correct way to solve what the algorithm above tries to do: http://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf However it's heavy on math and does not give the complete source code. Here is the complete source code: vector3 closesPointOnTriangle( const vector3 *triangle, const vector3 &sourcePosition ) { vector3 edge0 = triangle[1] - triangle[0]; vector3 edge1 = triangle[2] - triangle[0]; vector3 v0 = triangle[0] - sourcePosition; float a = edge0.dot( edge0 ); float b = edge0.dot( edge1 ); float c = edge1.dot( edge1 ); float d = edge0.dot( v0 ); float e = edge1.dot( v0 ); float det = a*c - b*b; float s = b*e - c*d; float t = b*d - a*e; if ( s + t < det ) { if ( s < 0.f ) { if ( t < 0.f ) { if ( d < 0.f ) { s = clamp( -d/a, 0.f, 1.f ); t = 0.f; } else { s = 0.f; t = clamp( -e/c, 0.f, 1.f ); } } else { s = 0.f; t = clamp( -e/c, 0.f, 1.f ); } } else if ( t < 0.f ) { s = clamp( -d/a, 0.f, 1.f ); t = 0.f; } else { float invDet = 1.f / det; s *= invDet; t *= invDet; } } else { if ( s < 0.f ) { float tmp0 = b+d; float tmp1 = c+e; if ( tmp1 > tmp0 ) { float numer = tmp1 - tmp0; float denom = a-2*b+c; s = clamp( numer/denom, 0.f, 1.f ); t = 1-s; } else { t = clamp( -e/c, 0.f, 1.f ); s = 0.f; } } else if ( t < 0.f ) { if ( a+d > b+e ) { float numer = c+e-b-d; float denom = a-2*b+c; s = clamp( numer/denom, 0.f, 1.f ); t = 1-s; } else { s = clamp( -e/c, 0.f, 1.f ); t = 0.f; } } else { float numer = c+e-b-d; float denom = a-2*b+c; s = clamp( numer/denom, 0.f, 1.f ); t = 1.f - s; } } return triangle[0] + s * edge0 + t * edge1; } [Edited by - agby on November 10, 2009 9:49:36 AM] 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted November 10, 2009 Yup, that's the one I use. I like the fact that it can also return the (s, t) parametric coordinates, very useful. 0 Share this post Link to post Share on other sites
Dirk Gregorius 2764 Report post Posted November 10, 2009 Christer Ericson's book "Real-Time Collision Detection" has a decent coverage of this problem. I recommend getting the book if you don't have it already and look at it. 0 Share this post Link to post Share on other sites
Dave Eberly 1173 Report post Posted November 10, 2009 Quote:Original post by agbyHowever it's heavy on math and does not give the complete source code.Here is the complete source code:*** Source Snippet Removed ***As with most of my PDFs, the implementations are in the freely downloadable source code from my web site. The point-triangle distance is on this page, in the section with comment "Distance from a point to a triangle (3D)." 0 Share this post Link to post Share on other sites
agby 132 Report post Posted November 10, 2009 Quote:Original post by Dave EberlyAs with most of my PDFs, the implementations are in the freely downloadable source code from my web site. The point-triangle distance is on this page, in the section with comment "Distance from a point to a triangle (3D)."Ah! Thanks for the link. You really should make sure that Google can reach those pages so they show up on searches. Lots of goodies there... :) 0 Share this post Link to post Share on other sites