Sign in to follow this  

Closest point on triangle

This topic is 2959 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Quote:
Original post by agby
However 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)."

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave Eberly

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


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

Share this post


Link to post
Share on other sites

This topic is 2959 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this