An Issue About FMath::ClosestPointOnTriangleToPoint Function In UE4

Introduction

UE4 has already provide a function FMath::ClosestPointOnTriangleToPoint for us to calculate the closest point on a triangle to a specific point:

FVector FMath::ClosestPointOnTriangleToPoint(const FVector& Point, const FVector& A, const FVector& B, const FVector& C)
{
        //Figure out what region the point is in and compare against that "point" or "edge"
        const FVector BA = A - B;
        const FVector AC = C - A;
        const FVector CB = B - C;
        const FVector TriNormal = BA ^ CB;

        // Get the planes that define this triangle
        // edges BA, AC, BC with normals perpendicular to the edges facing outward
        const FPlane Planes[3] = { FPlane(B, TriNormal ^ BA), FPlane(A, TriNormal ^ AC), FPlane(C, TriNormal ^ CB) };
        int32 PlaneHalfspaceBitmask = 0;

        //Determine which side of each plane the test point exists
        for (int32 i=0; i<3; i++)
        {
                if (Planes[i].PlaneDot(Point) > 0.0f)
                {
                        PlaneHalfspaceBitmask |= (1 << i);
                }
        }

        FVector Result(Point.X, Point.Y, Point.Z);
        switch (PlaneHalfspaceBitmask)
        {
        case 0: //000 Inside
                return FVector::PointPlaneProject(Point, A, B, C);
        case 1:        //001 Segment BA
                Result = FMath::ClosestPointOnSegment(Point, B, A);
                break;
        case 2:        //010 Segment AC
                Result = FMath::ClosestPointOnSegment(Point, A, C);
                break;
        case 3:        //011 point A
                return A;
        case 4: //100 Segment BC
                Result = FMath::ClosestPointOnSegment(Point, B, C);
                break;
        case 5: //101 point B
                return B;
        case 6: //110 point C
                return C;
        default:
                UE_LOG(LogUnrealMath, Log, TEXT("Impossible result in FMath::ClosestPointOnTriangleToPoint"));
                break;
        }

        return Result;
}

This function works fine for a right triangle or an acute triangle. But this function can return a wrong result for an obtuse triangle:

The Core Algorithm

How Does This Function Work?

This function simply split the 3-d space into 8 regions. And the closest point is calculated considering which region it is located in:

It’s easy to tell that this can perfectly do the trick for an acute triangle through a little calculation. But this does not work for an obtuse triangle.

What About An Obtuse Triangle?

Imagine a triangle and a point like this:

The function can return point A as the result of the input point P. But actually it is point D that is the true closest point on the triangle like this:

And that is the issue, or rather, the bug of this implementation.

PhysX’s Implementation

PhysX‘s implementation is like this:

Two additional dot production comparisons are performed to fix this issue. So the space partition is like this:

A precise solution is necessary for physx since GJK algorithm needs to find the support point.

Chaos’ Implementation

Chaos has its own implementation as well:

This implementation method is quite simple:

1. Firstly, calculate the target point onto the plane P';
2. Second, calculate the barycentric coordinate of P'. If P' is located in this triangle, then P' is the closest point.
3. Or else, the result point must locate in the edge of this triangle. Thus, calculate the closest point to these 3 line segment, and find the closest one.

The performance implementation is not that good. The implementation of PhysX is preferred considering performance.