时间戳

首页 > 解决方案 > 如何找到正确的方法在三角形上投影点以在网格上绘制线？

3d - 如何找到正确的方法在三角形上投影点以在网格上绘制线？

问题描述

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

我做什么：

CurrentTriangle = A 点所在的三角形。

而 CurrentTriangle != 带 B 点的三角形：

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

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

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

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

问题示例

预期结果（红线）： 在此处输入图像描述

标签： 3dgeometryprojectionraycastingmap-projections

解决方案

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

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

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

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

    • 让三角形有顶点 U、V 和 W，同样用笛卡尔世界坐标书写。
    • 然后计算向量UV和UW的叉积向量M。
    • 之后计算 N 和 M 的叉积，得到向量 K。
    • 检查向量 AB 的 K 点积是否为正。如果不是，则将 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。L然后是两个平面的交线，OAB并且UVW位于它们两者上 一方面，L位于平面上OAB，因此从点O投影到屏幕上作为一条线。另一方面，L位于三角形的平面上UVW。因此，该线 L垂直于两个向量 N和M。因此，向量的叉积K = N x M向量N和M都垂直于它们，因此平行于线L（即 vectorK与 line 对齐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。则平面方程为 N.(XA) = 0，对于平面 OAB 上的任意点 X。这里 '。' 是点积。线性方程为 X = V + t*(WV)。因此，当我们将直线方程代入平面方程时，通过求解 t 可以找到交点： 求解 t N.(V + t*(W-V) - A) = 0 非常容易： t = ( N.(A-V) )/( N.(W-V) )
因此 OAB 和 UV 之间的交点 P 是 P = V + ((N.(A-V))/( N.(W-V)))*(W-V) 为了确保 P 在边缘上，即它在 U 和 V 之间，我们必须检查 N.(WV) /= 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 与平面 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。

推荐阅读