1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ What exactly should be the output? (orthogonal projection with respect to the normal vector?) what should happen outside the triangle? $\endgroup$
    – Thomas
    Jan 25 at 18:28
  • $\begingroup$ The output is a point on the triangle such that the distance from the original point to its projection is the shortest euclidean distance between the point and any point on the triangle. $\endgroup$
    – Makogan
    Jan 25 at 20:02
  • $\begingroup$ well you can matrix transform the triangle So its ocupting the space in a way where one point is at 0,0 and other vertexes are on x 1 and y axis one. then project. not sure its less convoluted but still. $\endgroup$
    – joojaa
    Jan 28 at 23:07

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.