How to find correct way to project point on triangle for drawing line on mesh?

Question

I have mesh and 2 points on it - A and B. Each point lies on some triangle of mesh. The main goal is - draw correct line on mesh using 2 points. When points lies on triangles with different planes - I have problems with line drawing.

What I do:

CurrentTriangle = triangle on which the point A lies.

While CurrentTriangle != triangle with point B:

Get B projected(Bp) to CurrentTriangle: moving B by -CurrentTriangle.normal * distance to plane.

Find the exit point from the triangle - the intersection of ABp with the side of the triangle(converting 3d coords to 2d and find intersection point, then using barycentric coordinates gets 3d intersection point).

Move the resulting position towards position B to find a new CurrentTriangle.

The problem is to project position B correctly onto the plane of the CurrentTriangle. Actual result:

Expected result (red line):

Answer 1

Work in world-space coordinates (or even better, 3D Cartesian coordinates with origin the camera center, but whatever 3D coordinate system you have all the data represented in). Assume that you know the Cartesian coordinates of A and B in world-space (basically divide their homogeneous coordinates by their respective forth components and get rid of the forth component, which is now 1). Assume you know the Cartesian coordinates of the camera's center as well, call that point O.

The idea is to intersect the plane determined by the points A, B, O with each triangle, starting from the one that contains A and ending with the one that contains B.

1. At first, find the normal vector N to the plane ABO, which is the cross product of vectors OA and OB.

2. Now, start with the triangle that contains A.

   • Let the triangle have vertices U, V and W, again written in Cartesian world-coordinates.
   • Then calculate the cross-product vector M of the vectors UV and UW.
   • After that calculate the cross product of N and M, which gives you the vector K.
   • The check if K dot product with vector AB is positive. If not, multiply K by -1.
   • Starting from point A follow vector K until you intersect the edge of the triangle UVW. Denote that point by P.
   • As a result of these steps you have picked a point P together with the triangle that shares with the triangle UVW the edge on which P is located.

3. Iterate the following procedure: assume you are at a triangle UVW and you have determined point P on one of its edges (see for example the previous step 2).

   • Take the cross-product vector M of vectors UV and UW.
   • Take the cross-product vector K of vectors N and M.
   • Starting from point P follow vector K until you intersect the edge of the triangle UVW (or, if you are at the last triangle, until you reach point B). Denote that new intersection point by P.
   • Point P lies on one of the three edges of triangle UVW. Take the next triangle, which is the triangle that shares with UVW the edge on which P is located. Call that new triangle UVW.
   • Keep iterating step 3 until you reach triangle UVW in which point B lies.

Edit 1: (Explanation of the geomtric construction in the algorithm) You have vector N = OA x OB perpendicular to the plane OAB and vector M = UV x UW perpendicular to the plane UVW. Then the intersection line L of the two planes OAB and UVW lies on both of them On one hand, L lies on the plane OAB and therefore projects from point O onto the screen as a line. On the other hand, L lies on the plane of the triangle UVW. Consequently, the line L is perpendicular to both vectors N and M. Hence, the cross product vector K = N x M of vectors N and M is perpendicular to both of them and is therefore parallel to the line L (i.e. vector K is aligned with line L). Therefore line L (which lies on the plane of triangle UVW) is defined by point P and vector K.

Edit 2: (Possibly a simplification of the algorithm)

Again, work in world-space coordinates (or even better, 3D Cartesian coordinates with origin the camera center, but whatever 3D coordinate system you have all the data represented in). Assume that you know the Cartesian coordinates of A and B in world-space as well as all the world-coordinates of the vertices of the triangulation. Assume you know the Cartesian coordinates of the camera's center as well, call that point O.

The idea is to intersect the plane determined by the points A, B, O with each triangle, starting from the one that contains A and ending with the one that contains B.

Here is the geometric justification. Start with the triangle that contains A. Let the triangle have vertices U, V and W, again written in Cartesian world-coordinates. The idea is to find which of the three edges of UVW intersects the plane OAB at the point P such that the dot product AP.AB of AP with AB is a positive number. It is basically the formula for the intersection of a line in 3D and a plane in 3D. The line here is, say, determined by the points V and W and the plane is OAB. Then the equation of the plane is N.(X-A) = 0 for any point X on the plane OAB. Here '.' is the dot product. The line equation is X = V + t*(W-V). Thus the intersection point is found by solving for t when we plug the equation of the line into the equation of the plane: N.(V + t*(W-V) - A) = 0 It is very easy to solve for t: t = ( N.(A-V) )/( N.(W-V) )
And hence the intersection point P between OAB and UV is P = V + ((N.(A-V))/( N.(W-V)))*(W-V) To be sure that P is on the edge, i.e. it is between U and V we have to check that N.(W-V) /= 0 and 0 <= t <= 1. Otherwise we move to another edge.

1. At first, find the normal vector N to the plane ABO, which is the cross product N = OA x OB of vectors OA and OB.

2. Start with the triangle that contains A. Let the triangle have vertices U, V and W, again written in Cartesian world-coordinates.:

   • Calculate the dot product N.(W-V) and check that it is not equal to zero. If it is, choose another edge of the triangle and start again from the beginning of step 2;
   • Calculate t = ( N.(A-V) )/( N.(W-V) ) . If t > 1 or t < 0 then choose another edge of UVW and start again from the beginning of step 2;
   • Calculate P = V + t*(W-V) ;
   • Perform the following checks: (i)calculate the cross-product vectors OA x OP and OP x OB; (ii) Calculate their dot product (OA x OP).(OP x OB); (iii) check that (OA x OP).(OP x OB) > 0. If not, choose another edge and start again from the beginning of step 2;
   • Draw the line segment connecting point A to the point P;
   • Take the triangle that shares with triangle UVW the edge on which P is located.
   • As a result of these steps, you have picked a point P together with the triangle that shares with the triangle UVW the edge on which P is located.

3. Iterate the following procedure: assume you are at a triangle UVW and you have determined point P on one of its edges, say VW (see for example the previous step 2). We need to find which of the two edges UV or UW the plane OAB intersects (it should intersect at one of them). Start with, say, edge UV:

   • Calculate N.(V-U) and check that it is not equal to zero. If it is, choose the other edge UW and start again from the beginning of step 3;
   • Calculate t = ( N.(A-U) )/( N.(V-U) ) . If t > 1 or t < 0 then choose the other edge UW and start again from the beginning of step 3;
   • Calculate P = U + t*(V-U) ;
   • Draw the line segment connecting the old to the new point P (the first on edge VW and the second on edge UV in our example);
   • Take the triangle that shares with triangle UVW the edge on which P is located.
   • Point P lies on one of the three edges of triangle UVW. Take the next triangle, which is the triangle that shares with UVW the edge on which P is located. Call that new triangle UVW.
   • Keep iterating step 3 until you reach triangle UVW in which point B lies.