如何找到在三角形上投影点以在网格上画线的正确方法？

Question

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

我的工作：

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.

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

预期结果（红线）：

Answer 1

在世界坐标系中工作-space 坐标（或者更好的是，3D 笛卡尔坐标系，原点为相机中心，但无论使用何种 3D 坐标系，您都可以在其中表示所有数据）。假设您知道 A 和 B 在 world-space 中的笛卡尔坐标（基本上将它们的齐次坐标除以它们各自的第四分量并去掉第四分量，现在是 1）。假设您也知道相机中心的笛卡尔坐标，将该点称为 O。

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

1. 首先求平面ABO的法向量N，它是 矢量 OA 和 OB。

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

   • 让三角形有顶点 U、V 和 W，同样用笛卡尔世界坐标表示。
   • 然后计算向量UV和UW的叉积向量M。
   • 之后计算 N 和 M 的叉积，得到向量 K。
   • 检查 K 与向量 AB 的点积是否为正。如果不是，则将 K 乘以 -1。
   • 从点 A 开始沿着矢量 K 直到与三角形 UVW 的边相交。用 P.
   表示该点
   • 作为这些步骤的结果，您已经选择了点 P 以及与三角形 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 上，因此投影从点 O 到屏幕上作为一条线。另一方面，L 位于三角形 UVW 的平面上。因此，直线 L 垂直于向量 N 和 M。因此，向量 N 和 M 的叉积向量 K = N x M 垂直于它们，因此平行于线 L（即向量 K与 L 行对齐）。因此，线 L（位于三角形 UVW 的平面上）由点 P 和向量 K 定义。

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

同样，在 world-space 坐标中工作（或者甚至更好，3D 笛卡尔坐标，原点为相机中心，但无论 3D 坐标系如何表示所有数据）。假设您知道 A 和 B 在 world-space 中的笛卡尔坐标以及三角剖分顶点的所有世界坐标。假设您也知道相机中心的笛卡尔坐标，将该点称为 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 找到交点： 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。否则我们移动到另一个边缘。

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

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

   • 计算点积 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 所在边的三角形。

3. 重复以下过程：假设您位于一个三角形 UVW 处，并且您已在其一条边上确定点 P，例如 VW（例如，请参见前面的步骤 2）。我们需要找到平面 OAB 与两条边 UV 或 UW 中的哪一条相交（它应该在其中一条相交）。从边缘 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。