View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Closest point on triangle

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1agby  Members

Posted 10 November 2009 - 02:39 AM

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]

### #20BZEN  Members

Posted 10 November 2009 - 04:20 AM

Yup, that's the one I use. I like the fact that it can also return the (s, t) parametric coordinates, very useful.

Everything is better with Metal.

### #3Dirk Gregorius  Members

Posted 10 November 2009 - 04:58 AM

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.

### #4Dave Eberly  Members

Posted 10 November 2009 - 06:43 AM

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)."

### #5agby  Members

Posted 10 November 2009 - 07:32 AM

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... :)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.