0

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:

Problem example

Expected result (red line): enter image description here

Konstantin Saietskyi
  • 53
  • 1
  • 9
  • I am going to ask the same thing again that I asked under your previous question: What is the correct line? Is it a geodesic? Why is the red line better than the black one? – Nico Schertler May 02 '19 at 15:30
  • @Nico Schertlera correct line is a line that is straight on the screen without distortion. Red line better because user sets 2 points and should see a line, not a curve – Konstantin Saietskyi May 02 '19 at 15:41
  • 1
    @KonstantinSaietskyi You can use the plane of the triangle formed by the camera center, A, and B, and do a segment-plane intersection for each edge and select the intersection closest to B. – Gilles-Philippe Paillé May 02 '19 at 16:21
  • So, can this path be discontinuous? Imagine we had a view point farther to the left. The small rim would not be visible to us. Should the path then skip these triangles altogether? Would it be more appropriate to draw the line directly in screen space? – Nico Schertler May 02 '19 at 19:09
  • @NicoSchertler Hmm, I think converting triangles/lines positions to screen-space its a good idea, but then after finding intersection in 2d how can I map intersection point to 3d? – Konstantin Saietskyi May 02 '19 at 21:50
  • @NicoSchertler if triangles doesn't visible to us, they should be skipped. – Konstantin Saietskyi May 02 '19 at 22:12
  • 1
    Then do the intersection in 2D. Once you have the 2D points, simply do a back-projection. The simplest way to do this is to remember the edges and the position on the edge. Keep in mind that perspective projections do not preserve length ratios, i.e. linear interpolation between two vertices has to take depth into account. You probably also need to stop paths in the middle of faces if they are partially occluded by other faces in front of them. – Nico Schertler May 02 '19 at 22:25
  • @NicoSchertler can you explain more detailed? If I do back-projection from 2d to 3d it seems that has some inaccuracy and intersected point lies near to line, but not on it. Also I don't understand what do you mean about "You probably also need to stop paths in the middle of faces if they are partially occluded by other faces in front of them.". – Konstantin Saietskyi May 03 '19 at 08:49
  • 1) I did not mean to do an actual back-projection. Just remember the edge and position on the edge (which you get from the 2D intersection) and calculate the corresponding point in 3D. 2) Assume two triangles where one partially occludes the other and a 2D line that passes through both of them. At the time the line leaves the front triangle, it will be in the middle of the back triangle, not on an edge. – Nico Schertler May 03 '19 at 15:29

1 Answers1

3

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.
Futurologist
  • 1,874
  • 2
  • 7
  • 9
  • Can you explain more about "Starting from point A follow vector K until you intersect the edge of the triangle UVW. Denote that point by P."? We have vector K which is perpendicular from ABO normal to triangle normal(UVW) and if I follow from A by vector K it's won't move to triangle edge. https://imgur.com/a/PxV1Jrm – Konstantin Saietskyi May 07 '19 at 19:03
  • @KonstantinSaietskyi You have vector N = OA x OB perpendicular to OAB and vector M = UV x UW perpendicular to UVW. Then the intersection line L of the two planes OAB and UVW lies on both of them (and in particular on the plane of the triangle UVW), so L is perpendicular to both N and M. Hence, the cross product vector K 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. – Futurologist May 07 '19 at 19:12
  • @KonstantinSaietskyi On your picture you are probably not taking vector OB as part of the definition of normal vector N. When placed at point A, the projection of vector K onto the screen should be aligned with the projection of line AB onto the screen, because K lies on the plane OAB in three space and the plane OAB projects onto the screen as a line. And point O is the point of view (point of projection), not the center of the screen. That also matters. – Futurologist May 07 '19 at 19:17
  • @KonstantinSaietskyi I added an edit to the answer, explaining the geometry. Observe cross-product is taken three times. Also vector N is always the same everywhere. Only vector M changes with each 3D triangle. – Futurologist May 07 '19 at 19:32
  • Sorry for misunderstanding about picture, uploaded new image https://imgur.com/a/J2BPZwP. So we have vector K, that perpendicular to both planes OAB and UVW. The part that I don't understand - is how to find point on triangle(UVW) edge using K vector? – Konstantin Saietskyi May 07 '19 at 19:52
  • @KonstantinSaietskyi Now your picture looks better! If you look at your picture, you have to write the equation of the line from point ```A``` along the vector ```K```, which has equation ```X = A + s*K``` and intersect it with the line determined by the vertices ```V``` and ```W```, whose equation is ```X = (1-t)*V + t*W``` . The intersection point ```P``` of these two lines is the solution of the system of linear equations ```A + s*K = (1-t)*V + t*W``` , which can be solved for ```(s,t)```. But you just have to find say ```s```. As soon as you find it, it is ```P=A + s*K```. – Futurologist May 07 '19 at 20:06
  • I see, in that way I should convert these coordinates(A, K, UVW) from world to screen positions, find intersection and back-project intersection from screen to world coords? – Konstantin Saietskyi May 07 '19 at 20:21
  • @KonstantinSaietskyi No, this is intersection of two lines directly in 3D space. No need to convert back and forth. However, I think I might improve the method a bit, to make the calculations a bit less. The philosophy is however the same. I will write a second edited version of the algorithm. – Futurologist May 07 '19 at 20:44
  • Then I don't understand how can I find intersection by moving from point A along the vector K, because K vector don't lie in plane UVW: https://imgur.com/a/M6cW2gn. Did a few pictures with different camera angles for better understanding – Konstantin Saietskyi May 07 '19 at 21:07
  • @KonstantinSaietskyi It does. It is specially constructed that way. It is guaranteed by the three cross products. Nevertheless, I added another version of the algorithm. It does not use the vector K and directly calculates point P. Just check the formulas, make sure they are correct. Otherwise the method is geometrically correct. – Futurologist May 07 '19 at 21:20
  • Simplificated algorithm works! But in some cases it didn't find correct intersection point: For example: A = (-0.2274438, -0.02901424, 1.962507) B = (-0.1217735, 0.1864354, 1.772951) O = (-0.1700001, 1.78, 1.150001) N = (0.65457, 0.2923512, 0.6971864) U = (-0.1756014, -0.1275818, 1.962362) V = (-0.2970552, -0.000002846504, 1.962948) W = (-0.2170552, 0.0000000001494274, 1.962362) https://imgur.com/a/Fhb6In2 Second image: Intersection point should be on edge UW, but it found 2 intersection points instead: on the UV and VW edges. – Konstantin Saietskyi May 08 '19 at 18:35
  • @KonstantinSaietskyi I got a different vector for N. You have to use the proper formula for ```N = (A - O) x (B - O)``` . My vector is ```N = [0.1678553780796; 0.0749689547746; 0.178782852959804]``` . When starting from point A, you will always have intersection with two out of the three edges. However, you choose the one for which the point P satisfies the condition (P-A).(B-A)>0. The other point P will satisfy (P-A).(B-A)<0 so you rule it out. In the example you provide P is on VW. – Futurologist May 08 '19 at 21:39
  • @KonstantinSaietskyi Check the correct cross-product formula: https://en.wikipedia.org/wiki/Cross_product – Futurologist May 08 '19 at 21:41
  • You are right, I just normalized cross vector (N) and this was a mistake – Konstantin Saietskyi May 08 '19 at 21:57
  • @KonstantinSaietskyi Yeah, I realized you did that. I think there is no need to normalize it, so you can avoid square roots and division, which adds numerical error. – Futurologist May 08 '19 at 22:03
  • Found one interesting case: `A = (-0.233863, 0.05659757, 1.96262)` `B = (-0.1778871, 0.1345785, 1.879314)` `O = (-0.1700001, 1.78, 1.150001)` `N = (0.08019959, 0.040167, 0.09148897)` `U = (-0.240321, 0.174607, 1.962948)` `V = (-0.2170552, 0.0000000001494274, 1.962362)` `W = (-0.2970552, -0.000002846504, 1.962948)` https://imgur.com/a/G1zyyX3 In this case I got UW intersection (only UW has AP.AB > 0), but UW intersection is not suitable for this case (correct edge is UV, but it has AP.AB < 0). The question is - how to find correct way to find one of two intersections? – Konstantin Saietskyi May 09 '19 at 22:34
  • can you help? I find a solution: project P, A, B to screen space and check if P between AB, but I'm sure there is better solution. – Konstantin Saietskyi May 10 '19 at 13:17
  • @KonstantinSaietskyi The dot product is much simpler than the projection onto the screen space and leads to the same result (the dot product projects AP onto AB and checks if the projected P is between A and B). The time when it fails (and the projection will fail) is when the 3D geometry of your triangulation is strongly concave so that at first the sequence of triangles connecting A to B on the surface diverges away from the 3D segment AB but then it "circles" around and ends at point B. But honestly, I am not seeing this kind of geometry on the picture you sent me. – Futurologist May 10 '19 at 16:05
  • @KonstantinSaietskyi I guess, something ugly that you can do to patch up this, you can simply track simultaneously both paths that emerge from point A. I mean, at step 2 of the algorithm you have two intersection points P. Simply apply the iterated step 3 to both of them, keep the results for both, and as soon as one of them arrives at B, erase the other. – Futurologist May 10 '19 at 16:11
  • @KonstantinSaietskyi The algorithm is geometrically correct, however, it is based on the local geometry of the surface (two neighboring triangles) and cannot account for the global nature of the sequence of triangles. However, there are only two alternatives for the path from point A and B. The choice happens only at point A, after that everything is uniquely determined. That is why I propose to keep track of both paths and let them compete. One of them will reach point B and will win the competition. – Futurologist May 10 '19 at 16:21
  • @KonstantinSaietskyi Ah, ok! I think, if I understand correctly the geometry of the picture you sent, the sequence of triangles is in fact concave away from AB. I think Maybe you should project points A, B and P onto the screen space and check if P is between A and B. Use that instead of the dot product in step 2. That should work better, even for these concave cases. – Futurologist May 10 '19 at 16:33
  • @KonstantinSaietskyi I added a correction to the second algorithm in my answer. You can try that one too, it should be equvalent to the screen projection, just done in 3D directly. Check which approach is faster or easier for implementation. – Futurologist May 10 '19 at 16:59