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

问题描述

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

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.

我做什么:

CurrentTriangle = A 点所在的三角形.

CurrentTriangle = triangle on which the point A lies.

虽然 CurrentTriangle != 有 B 点的三角形:

While CurrentTriangle != triangle with point B:

将 B 投影 (Bp) 投影到 CurrentTriangle:将 B 移动-CurrentTriangle.normal * 到平面的距离.

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

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

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

将结果位置移向位置 B 以找到新的 CurrentTriangle.

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

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

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

预期结果(红线):

推荐答案

在世界空间坐标中工作(或者甚至更好，以相机中心为原点的 3D 笛卡尔坐标，但无论您在何种 3D 坐标系中表示所有数据).假设您知道 A 和 B 在世界空间中的笛卡尔坐标(基本上将它们的齐次坐标除以它们各自的第四个分量并去掉第四个分量，现在为 1).假设您也知道相机中心的笛卡尔坐标，称该点为 O.

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.

想法是将点 A、B、O 确定的平面与每个三角形相交，从包含 A 的那个开始，到包含 B 的那个结束.

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. 首先求平面ABO的法向量N，它是载体 OA 和 OB.

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

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

Now, start with the triangle that contains A.

• 让三角形具有顶点 U、V 和 W，同样用笛卡尔世界坐标编写.
• 然后计算向量 UV 和 UW 的叉积向量 M.
• 然后计算 N 和 M 的叉积，得到向量 K.
• 检查与向量 AB 的 K 点积是否为正.如果不是，则将 K 乘以 -1.
• 从点 A 开始，跟随向量 K 直到与三角形 UVW 的边缘相交.用 P 表示该点.
• 作为这些步骤的结果，您选择了一个点 P 以及与三角形 UVW 共享 P 所在边的三角形.

重复以下过程:假设您在一个三角形 UVW 处，并且您已经在它的一条边上确定了点 P(例如参见前面的步骤 2).

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

• 取向量 UV 和 UW 的叉积向量 M.
• 取向量 N 和 M 的叉积向量 K.
• 从点 P 开始，跟随向量 K 直到与三角形 UVW 的边相交(或者，如果您在最后一个三角形处，则直到到达点 B).用 P 表示新的交点.
• 点 P 位于三角形 UVW 的三个边之一上.取下一个三角形，它是与 UVW 共享 P 所在边的三角形.称这个新三角形为 UVW.
• 继续迭代第 3 步，直到到达 B 点所在的三角形 UVW.

(算法中几何构造的解释)你有向量N = OA x OB垂直于平面OAB和垂直于平面UVW的矢量M = UV x UW.那么两个平面OAB和UVW的交线L在它们两个平面上一方面，L位于平面 OAB 上，因此从点 O 投影到屏幕上作为一条线.另一方面，L 位于三角形UVW 的平面上.因此，线L 垂直于向量N 和M.因此，向量 N 和 M 的叉积向量 K = N x M 与它们垂直，因此平行于线L(即向量K 与行L 对齐).因此线L(位于三角形UVW的平面上)由点P和矢量K定义.

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.

编辑 2: (可能是算法的简化)

同样，在世界空间坐标中工作(或者甚至更好，以相机中心为原点的 3D 笛卡尔坐标，但无论您在何种 3D 坐标系中表示所有数据).假设您知道 A 和 B 在世界空间中的笛卡尔坐标以及三角剖分顶点的所有世界坐标.假设您也知道相机中心的笛卡尔坐标，称该点为 O.

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.

想法是将点 A、B、O 确定的平面与每个三角形相交，从包含 A 的那个开始，到包含 B 的那个结束.

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.

这是几何对齐.从包含 A 的三角形开始.让三角形具有顶点 U、V 和 W，同样用笛卡尔世界坐标书写.这个想法是找到 UVW 的三个边中的哪一个在点 P 处与平面 OAB 相交，使得 AP 与 AB 的点积 AP.AB 是正数.它基本上是 3D 中的线与 3D 中的平面相交的公式.例如，这里的线由点 V 和 W 确定，平面是 OAB.那么平面的方程是 N.(X-A) = 0 对于平面 OAB 上的任何点 X.这里 '.'是点积.直线方程为 X = V + t*(W-V).因此，当我们将直线方程代入平面方程时，通过求解 t 来找到交点:N.(V + t*(W-V) - A) = 0很容易求解 t:t = ( N.(A-V) )/( N.(W-V) )
因此 OAB 和 UV 之间的交点 P 是P = V + ((N.(A-V))/(N.(W-V)))*(W-V)为了确保 P 在边缘上，即它在 U 和 V 之间，我们必须检查 N.(W-V)/= 0 和 0 <= t <= 1.否则我们移动到另一个边缘.

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. 首先找到平面ABO的法向量N，它是向量OA和OB的叉积N = OA x OB.

从包含 A 的三角形开始.让三角形具有顶点 U、V 和 W，同样用笛卡尔世界坐标表示.:

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

• 计算点积 N.(W-V) 并检查它是否不为零.如果是，则选择三角形的另一条边，从第2步开始重新开始；
• 计算 t = ( N.(A-V) )/( N.(W-V) ) .如果 t > 1 或 t <0 然后选择UVW的另一条边，从第2步开始重新开始；
• 计算P = V + t*(W-V) ;
• 执行以下检查:(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 所在边的三角形.

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

重复以下过程:假设您在一个三角形 UVW 处，并且您已经在它的一条边上确定了点 P，比如说 VW(例如参见前面的步骤 2).我们需要找到平面 OAB 与 UV 或 UW 两条边中的哪一条相交(它应该与其中之一相交).从边缘 UV 开始:

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:

• 计算N.(V-U) 并检查它是否不等于零.如果是，则选择另一条边UW，从第3步开始重新开始；
• 计算 t = ( N.(A-U) )/( N.(V-U) ) .如果 t > 1 或 t <0 然后选择另一条边 UW 从第 3 步开始重新开始；
• 计算P = U + t*(V-U) ;
• 绘制连接旧点和新点 P 的线段(在我们的示例中，第一个在 VW 边上，第二个在 UV 边上)；
• 取与三角形 UVW 共享 P 所在边的三角形.
• 点 P 位于三角形 UVW 的三个边之一上.取下一个三角形，它是与 UVW 共享 P 所在边的三角形.称这个新三角形为 UVW.
• 继续迭代第 3 步，直到到达 B 点所在的三角形 UVW.

• 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屋！