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 d2>=0 and d6 <= 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.