如何找到在三角形上投影点的正确方法以在网格上画线？ [英] How to find correct way to project point on triangle for drawing line on mesh?

问题描述

我有网格和2个点- A 和 B 。每个点都位于网格的某个三角形上。主要目标是-使用2个点在网格上绘制 correct 线。当点位于具有不同平面的三角形上时-画线时会遇到问题。

我要做什么：

CurrentTriangle =点A所在的三角形。

CurrentTriangle！=带有B点的三角形：

获得B投影（ Bp ）到CurrentTriangle：将 B 移动
-CurrentTriangle.normal *到平面的距离。

找到三角形的出口点- ABp 与三角形边的交点（将3d坐标转换为2d并找到交点，然后使用重心坐标获得3d相交点。）

将结果位置移到位置 B ，以找到新的CurrentTriangle。

问题是将位置 B 正确投影到CurrentTriangle的平面上。实际结果：

预期结果（红线）：

解决方案

在世界空间坐标中工作（甚至更好的是，3D笛卡尔坐标的原点是相机中心，但是无论3D坐标系是什么，所有数据都以表示。假设您知道世界空间中A和B的笛卡尔坐标（基本上将它们的齐次坐标除以它们各自的第四分量，并摆脱第四分量，现在为1）。假设您也知道相机中心的笛卡尔坐标，则将该点称为O。

这个想法是将由点A，B，O确定的平面与

1. 首先，找到法线，然后从每个包含A的三角形开始。向量N到平面ABO，这是
   向量OA和OB的叉积。




2. 现在，从包含A的三角形开始。

   
   
   
   
   
   • 令三角形的顶点U，V和W再次用笛卡尔世界坐标表示。
   
   
   • 然后计算向量UV和UW的叉积向量M。
   
   
   • 此后，计算N和M的叉积，得出向量K。
   
   
   • 检查是否有向量AB的K点积为正。如果不是，则将K乘以-1。
   
   
   • 从点A开始遵循向量K，直到与三角形UVW的边相交。通过P表示该点。
   
   
   • 这些步骤的结果是，您选择了一个点P以及一个与三角形UVW共享的三角形，其中UVW共享P所在的边。
   
   



3. 重复以下过程：假设您位于三角形UVW上，并且已确定点P的边缘之一（参见例如上一步2）。

   
   
   
   
   
   • 取向量UV和UW的叉积向量M。
   
   
   • 取向量N和M的叉积向量K。
   
   
   • 从点P开始跟随向量K，直到与三角形的边缘相交UVW（或者，如果您位于最后一个三角形，直到到达B点）。用P表示新的交点。
   
   
   • 点P位于三角形UVW的三个边缘之一上。取下一个三角形，该三角形与UVW共享P所在的边。将该新三角形称为UVW。
   
   
   • 继续执行第3步，直到到达B点所在的三角形UVW。
   
   

编辑1： （说明算法中的几何构造）您有向量 N = OA x OB 垂直于平面 OAB 和向量 M = UV x UW 垂直于平面 UVW 。然后是两个平面 OAB 和 UVW L >都位于这两者上一方面， L 躺在飞机 OAB 上，因此从<$ c点投影$ c> O 在屏幕上显示为一行。另一方面， L 位于三角形 UVW 的平面上。因此，线 L 垂直于两个向量 N 和 M 。因此，向量 N 和 M的叉积向量 K = N x M code>垂直于两者，因此平行于 L 线（即向量 K 为与 L 行对齐）。因此，线 L （位于三角形 UVW 的平面上）由点 P定义和向量 K 。

编辑2： （可能是算法的简化）

同样，使用世界空间坐标（甚至更好的是，3D笛卡尔坐标以摄像机中心为原点，但是无论3D坐标系是代表什么数据，）。假设您知道世界空间中A和B的笛卡尔坐标以及三角剖分顶点的所有世界坐标。假设您也知道相机中心的笛卡尔坐标，则将该点称为O。

这个想法是将由点A，B，O确定的平面与每个三角形，从包含A的三角形开始，到包含B的三角形结束。

这里是几何对齐方式。从包含A的三角形开始。让三角形的顶点U，V和W再次用笛卡尔世界坐标表示。想法是找到UVW的三个边缘中的哪一个在点P与平面OAB相交，从而AP与AB的点积AP.AB为正数。它基本上是3D线和3D平面的交点的公式。例如，此处的线由点V和W确定，平面为OAB。那么，对于平面OAB上的任意点X，平面的等式为N.（X-A）= 0。这是点产品。线方程为X = V + t *（W-V）。因此，当将直线方程式插入平面方程式时，通过求解t可以找到交点：$ b​​ $ b N.（V + t *（WV）-A）= 0
求解t很容易：
t =（N.（AV））/（N.（WV））

因此，OAB和UV之间的交点P为
P = V +（（N.（AV））/（N.（WV ）））*（WV）
要确保P在边缘上，即它在U和V之间，我们必须检查N.（WV）/ = 0和0 < = t< = 1.否则，我们移到另一个边缘。

1. 首先，找到平面ABO的法线向量N，即叉积 N =向量OA和OB的OA x OB 。




2. 从包含A的三角形开始。让该三角形具有分别由笛卡儿世界坐标写成的U，V和W顶点。
   
   

   
   
   • 计算点积 N.（WV）并检查其不等于零。如果是，请选择三角形的另一条边，然后从步骤2的开头重新开始；否则，请重新开始。
   
   
   • 计算 t =（N.（A-V））/（N.（W-V））。如果t＞ 1或t ＜1，则t＞ 1。 0，然后选择UVW的另一条边，然后从步骤2的开头重新开始；
   
   
   • 计算 P = V + t *（WV）;
   
   
   • 执行以下检查：（i）计算叉积矢量OA x OP和OP x OB； （ii）计算其点积（OA x OP）。（OP x OB）; （iii）检查（OA x OP）。（OP x OB）> 0 。如果不是，请选择另一条边，然后从步骤2的开头重新开始；
   
   
   • 绘制将点A连接到点P的线段；
   
   
   • 用与三角形UVW共享的三角形作为P所在的边。
   
   
   • 这些步骤的结果是，您选择了一个点P以及与三角形UVW共享的三角形。 P所在的边缘。
   
   



3. 重复以下过程：假设您在三角形UVW上，并且已确定点P的边缘之一，例如说大众汽车（例如，请参阅前面的步骤2）。我们需要找到平面OAB相交的两条边UV或UW中的哪一条（应在其中一条相交）。从边缘UV开始，

   
   
   
   
   
   • 计算 N.（VU）并检查它不等于零。如果是，请选择另一个边沿UW，然后从步骤3的开头重新开始；否则，请重新开始。
   
   
   • 计算 t =（N.（A-U））/（N.（V-U））。如果t＞ 1或t ＜1，则t＞ 1。 0，然后选择另一个边UW，然后从步骤3的开头重新开始；
   
   
   • 计算 P = U + t *（VU）;
   
   
   • 绘制将旧点连接到新点P的线段（在我们的示例中，第一个在边VW上，第二个在边UV上）；
   
   
   • 将与三角形UVW共享的三角形作为P所在的边。
   
   
   • 点P位于三角形UVW的三个边缘之一上。取下一个三角形，该三角形与UVW共享P所在的边。将该新三角形称为UVW。
   
   
   • 继续执行第3步，直到到达B点位于其中的三角形UVW。
   
   

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):

解决方案

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.

这篇关于如何找到在三角形上投影点的正确方法以在网格上画线？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！