Jump to content

Image of the Day

What's the best way to move your heavy stuff? Using a power loader! #spacr #screenshotsaturday 💪🤖💪 https://t.co/sOjz2XNVeq
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content.


Sign up now

Closest point on triangle

4: Adsense

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.


  • You cannot reply to this topic
4 replies to this topic

#1 agby   Members   

132
Like
0Likes
Like

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]

#2 0BZEN   Members   

2194
Like
0Likes
Like

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.


#3 Dirk Gregorius   Members   

2623
Like
0Likes
Like

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.

#4 Dave Eberly   Members   

1169
Like
0Likes
Like

Posted 10 November 2009 - 06:43 AM

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


#5 agby   Members   

132
Like
0Likes
Like

Posted 10 November 2009 - 07:32 AM

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





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.