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, 2023 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, 2023 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, 2023 at 23:07

2 Answers 2

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

$\endgroup$
3
  • $\begingroup$ I just relaized what are d2 and d6 in this answer? They are never defined. $\endgroup$
    – Makogan
    Apr 25, 2023 at 0:15
  • $\begingroup$ Have you been able to find it? $\endgroup$
    – Makogan
    Apr 26, 2023 at 0:33
  • $\begingroup$ The answer is updated. $\endgroup$
    – pmw1234
    Apr 26, 2023 at 10:06
1
$\begingroup$

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.

enter image description here

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

$\endgroup$
2
  • $\begingroup$ This is the diagram alluded to in the other answer. $\endgroup$
    – pmw1234
    Apr 26, 2023 at 13:05
  • $\begingroup$ @pmw1234: you are right. This diagram proves that you need $3$ tests to make a decision in the best case, and $5$ in the worst case. I believe that with an initial change of coordinates, the total number of operations is lowered. $\endgroup$
    – user1703
    Apr 26, 2023 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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