Clever projection of point onto triangle?

Question

I know of at leas tone way to project a point onto a triangle.

Project onto the plane, check barycentric coordinates, if outisde triangle, project onto the 3 segments, check distance, retain closest projection.

Is there a less convoluted approach?

Answer 1

The approach you are taking works but isn't very efficient.

Projection of a point onto a triangle can be boiled down to classifying the point into the various regions defined by the support planes of the edges. (there are 7 regions total)

The seven regions are the triangle face, the 3 edge regions and the 3 vertex regions. (draw lines perpendicular to each of the 3 edges at the vertex's a,b,c to get a diagram of the regions)

These are the Voronoi regions of the triangle. The vertex region at A has normals of (B-A) and (C-A) for the intersecting half spaces. (by using The dot product with the vector (P-A) where P is the original point will tell us if P lies inside the region. IE the barycentric coordinates will be (1,0,0).

A similar test can be done for vertex B and C getting barycentric coordinates of (0,1,0) and (0,0,1) for each.

Here are the functions:

// Determine if point lies in vertex regions
AB = b-a;
AC = c-a;

AP = p-a;
dA1 = dot(AB,AP);
dA2 = dot(AC,AP);
if( dA1<=0 and dA2 <=0) return a; // vertex region a (bary coords 1,0,0)

BP = p - b;
dB1 = dot(AB, BP);
dB2 = dot(AC, BP);
if( dB1 >= 0 && dB2=<0 ) return b; // vertex region b (bary coords 0,1,0)

CP = p - c;
dC1 = Dot(AB,CP);
dC2 = Dot(AC,CP);
if( dC2 >= 0 && dC1 <= dC2 ) return c; // vertex region c (bary coords 0,0,1)

To determine if the point lies in the edge regions you can continue with the barycentric coordinate computations. ie summed area method. This computation boils down to using dot products used to compute the vertex regions to check if the point lies in the edge regions.

EdgeAB = dA1*dB2 - dB1*dA2;
if( EdgeAB <= 0 and dA1 >= 0 and dB1 <=0) { 
   // lies in edge region bary coords (1-u, u,0); 
   // project point onto edge AB and return result;
}

EdgeBC = dB1*dC2 - dC1*dB2; 
if( EdgeBC <= 0 and (dB2-dB1)>=0 and (dC1-dC2)>=0) {
   // lies in edge region BC bary coords (0, 1-u, u)
   // project point onto edge BC and return;
}

EdgeAC = dC1*dA2 - dA1*dC2;
if( EdgeAC <= 0 and dA2>=0 and dC2<=0 ) {
   // lies in edge region AC bary coords (1-u, 0 ,u )
   // project point onto edge AC and return result
}

Finally if it isn't in any of these regions it must be inside the triangle face. Luckily we have computed everything needed to find the barycentric coords at this point...

 summed_area = EdgeAB + EdgeBC +EdgeAC;
 v = EdgeAC / summed_area;
 w = EdgeAB / summed_area;
 return a + ab * v + ac * w;

According to my notes the original source of this method is the book Real Time Collision Detection by Christer Ericson.

Answer 2

Your problem is essentially planar, as on can be convinced by looking in the direction perpendicular to the plane of the triangle. (This is achieved by using a change of coordinate system such that the normal to the plane becomes $z$.)

The point of interest can belong to one of seven regions, delimited by normal lines at the triangle vertices (in blue). To tell the region, you need to compare against all three triangle edges (left-of test). If the point falls inside, you are done; otherwise, if it lies on the right of two sides, you project on the common vertex; if it lies on the right of a single side, you need to test against two normals, and the projection will be on a side or a vertex.

Caution: the discussion is slightly different when the triangle is obtuse.