Closest point on triangle

Started by
6 comments, last by Dave Eberly 4 years, 2 months ago
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]
Advertisement
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.

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

OP's code seems to have a bug. Eberly's link died… now can be found by searching Google for “GteDistPointTriangleExact.h”

I guess you'll find it in one of the source code here: https://www.geometrictools.com/Downloads/Downloads.html

There is also this code from iq: https://iquilezles.org/www/articles/distfunctions/distfunctions.htm

GTEngine 3 had file names starting with Gte. The current code posted is GTEngine 4, but the Gte prefix on files is no longer used. That said, I kept the version 3 files at my site in order to avoid breaking external links. The GTE3 link is still what it used to be

https://www.geometrictools.com/GTEngine/Include/Mathematics/GteDistPointTriangleExact.h

The GTE4 link is

https://www.geometrictools.com/GTE/Mathematics/DistPointTriangleExact.h

The simplest way to access the code, as mentioned by JoeJ, is to download the entire distribution as a zip file.

This topic is closed to new replies.

Advertisement