计算大量三角形的 3D 射线/三角形边交点的快速算法
Fast algorithm to calculate 3D ray / triangle edge intersections for a large number of triangles
我有一个 3D 三角形 ABC space 和一条三角形平面内的射线，由起点 E（总是在三角形的边缘内或边缘上）和方向向量 d 给出。
顶点 A、B 和 C 以及 E 和 d 在 3D 坐标 {x,y,z} 中给出。
我正在寻找一种算法来计算光线与三角形边 P 的交点。
我可以对三角形的 3 条边进行 3 次射线/线段相交测试，但由于我必须对大量三角形进行此操作，因此我正在寻找一种更高效、更快速的算法。
- 最好的方法是什么？
- 重心坐标有帮助吗？
- 时间复杂度为 O(1)
- 它可能会有所帮助。
如果我们谈论的是 3D 并且您的所有点都在一个平面上。在笛卡尔坐标系中需要求解三个线性系统
，找到三条线的交点，然后判断交点是否在边上。
或者您需要在线上找到两点的重心坐标。点 A(a1,a2,a3) = E 和 B(b1,b2,b3) = E+d。线方程是
现在您仍然需要解决三个线性系统（其中一个 mu = 0，其他的总和 = 1）。但是 2x2 系统更容易解决。然后检查找到的根的符号来确定找到的点是否在边上。
Could Barycentric Coordinates help?
可能吧。这在一定程度上取决于您的 non-barycentric 代码的优化程度，但我会说使用重心坐标至少更容易编写既可维护又高性能的代码。
据我所知，您的整个设置基本上是二维的，点 E 和方向 d 都包含在 A,B,C 所跨越的平面内。所以你有
E = aE*A + bE*B + cE*C with aE+bE+cE=1
d = ad*A + bd*B + cd*C with ad+bd+cd=0
现在你有两个子问题：
- 如何高效获取重心坐标
- 如何找到交点
让我们从后者开始。您只需将 E 添加到 d 的倍数，直到 c 坐标变为零。
P = E - (cE/cd)*d
根据您的设置，您可能也可以使用齐次坐标，在这种情况下，您可以将其写为 P = cd*E - cE*d。
如何将 d 和 E 的 x,y,z 坐标转换为重心 a,b,c？好吧，那只是一个线性方程组。您可以使用由向量 A,B,C 形成的矩阵的逆矩阵。同样，如果你正在处理齐次坐标，你可以使用附加而不是逆。
这里是拼写的同构方法：
aE = (By*Cz-Bz*Cy)*Ex + (Bz*Cx-Bx*Cz)*Ey + (Bx*Cy-By*Cx)*Ez
bE = (Cy*Az-Cz*Ay)*Ex + (Cz*Ax-Cx*Az)*Ey + (Cx*Ay-Cy*Ax)*Ez
cE = (Ay*Bz-Az*By)*Ex + (Az*Bx-Ax*Bz)*Ey + (Ax*By-Ay*Bx)*Ez
ad = (By*Cz-Bz*Cy)*dx + (Bz*Cx-Bx*Cz)*dy + (Bx*Cy-By*Cx)*dz
bd = (Cy*Az-Cz*Ay)*dx + (Cz*Ax-Cx*Az)*dy + (Cx*Ay-Cy*Ax)*dz
cd = (Ay*Bz-Az*By)*dx + (Az*Bx-Ax*Bz)*dy + (Ax*By-Ay*Bx)*dz
aP = cd*aE - cE*ad
bP = cd*bE - cE*bd
Px = aP/(aP+bP)*Ax + bP/(aP+bP)*Bx
Py = aP/(aP+bP)*Ay + bP/(aP+bP)*By
Pz = aP/(aP+bP)*Az + bP/(aP+bP)*Bz
前三行将 E 转换为重心坐标，接下来的三行 d。然后我们计算 P 的重心坐标，并将其转换回笛卡尔坐标。在那一步中，我们还将它们去均匀化，即除以重心坐标的总和。
总的来说，这里的代码量还是比较大的。您可以通过将通用表达式移至专用变量来减少操作次数，尤其是当您的编译器不为您执行此操作时。一个好处是除了最终的去均质化，即除以 (a+b) 之外，您不需要任何除法。如果计算 1/(a+b) 一次，只需要一次除法即可凑合，这对性能有好处。
然而，上述代码的真正好处可能是您可以使用重心坐标做很多其他坐标系无法轻易完成的好事。例如，如果要检查射线是否击中线段上或三角形外某处的线AB，只需检查是否aP*bP > 0。
暂时忽略 d 具有最小分量的轴，并处理由此产生的二维问题，就像我们在您的插图上看到的那样。
您可以预先计算射线支撑线的方程，形式为 ax + by + c = 0（假设忽略 z）。在这个表达式中插入三个顶点的坐标，符号会告诉你顶点在直线的哪一侧。
与直线的两个交点出现在端点处符号不同的边上。
然后，要确定哪条是右边缘，射线与第三条角之间的夹角的符号就可以了（如果我是对的）；
当你知道哪条边时，你可以计算边的参数方程的参数，你可以从前面计算的符号中推导出来。例如，沿边 AB，t = Sb / (Sb - Sa)。同时计算 1 - t;
最后，使用 t 值在端点之间进行插值，这次是在 3D 中。
计算成本为
Sa,Sb,Sc三个符号的求值，取6+和6x；
选择两个边缘候选，进行两次或三次比较；
选择单个候选，取一个2D叉积，3+和2x和一个比较；
计算插值参数,2+,1/;
最终3D插值，3+，6x.
很难做到更短。
查看论文
Fast, minimum storage ray-triangle intersection,
by Tomas Möller and Ben Trombone,
in
Journal of Graphics Tools, 2(1):21–28, 1997.
另见 this page。
作者说：
One advantage of this method is that the plane equation need not be computed on the fly nor be stored, which can amount to significant memory savings for triangle meshes. As we found our method to be comparable in speed to previous methods, we believe it is the fastest ray-triangle intersection routine for triangles that do not have precomputed plane equations.
我有一个 3D 三角形 ABC space 和一条三角形平面内的射线，由起点 E（总是在三角形的边缘内或边缘上）和方向向量 d 给出。
顶点 A、B 和 C 以及 E 和 d 在 3D 坐标 {x,y,z} 中给出。
我正在寻找一种算法来计算光线与三角形边 P 的交点。
我可以对三角形的 3 条边进行 3 次射线/线段相交测试，但由于我必须对大量三角形进行此操作，因此我正在寻找一种更高效、更快速的算法。
- 最好的方法是什么？
- 重心坐标有帮助吗？
- 时间复杂度为 O(1)
- 它可能会有所帮助。
如果我们谈论的是 3D 并且您的所有点都在一个平面上。在笛卡尔坐标系中需要求解三个线性系统
Could Barycentric Coordinates help?
可能吧。这在一定程度上取决于您的 non-barycentric 代码的优化程度，但我会说使用重心坐标至少更容易编写既可维护又高性能的代码。
据我所知，您的整个设置基本上是二维的，点 E 和方向 d 都包含在 A,B,C 所跨越的平面内。所以你有
E = aE*A + bE*B + cE*C with aE+bE+cE=1
d = ad*A + bd*B + cd*C with ad+bd+cd=0
现在你有两个子问题：
- 如何高效获取重心坐标
- 如何找到交点
让我们从后者开始。您只需将 E 添加到 d 的倍数，直到 c 坐标变为零。
P = E - (cE/cd)*d
根据您的设置，您可能也可以使用齐次坐标，在这种情况下，您可以将其写为 P = cd*E - cE*d。
如何将 d 和 E 的 x,y,z 坐标转换为重心 a,b,c？好吧，那只是一个线性方程组。您可以使用由向量 A,B,C 形成的矩阵的逆矩阵。同样，如果你正在处理齐次坐标，你可以使用附加而不是逆。
这里是拼写的同构方法：
aE = (By*Cz-Bz*Cy)*Ex + (Bz*Cx-Bx*Cz)*Ey + (Bx*Cy-By*Cx)*Ez
bE = (Cy*Az-Cz*Ay)*Ex + (Cz*Ax-Cx*Az)*Ey + (Cx*Ay-Cy*Ax)*Ez
cE = (Ay*Bz-Az*By)*Ex + (Az*Bx-Ax*Bz)*Ey + (Ax*By-Ay*Bx)*Ez
ad = (By*Cz-Bz*Cy)*dx + (Bz*Cx-Bx*Cz)*dy + (Bx*Cy-By*Cx)*dz
bd = (Cy*Az-Cz*Ay)*dx + (Cz*Ax-Cx*Az)*dy + (Cx*Ay-Cy*Ax)*dz
cd = (Ay*Bz-Az*By)*dx + (Az*Bx-Ax*Bz)*dy + (Ax*By-Ay*Bx)*dz
aP = cd*aE - cE*ad
bP = cd*bE - cE*bd
Px = aP/(aP+bP)*Ax + bP/(aP+bP)*Bx
Py = aP/(aP+bP)*Ay + bP/(aP+bP)*By
Pz = aP/(aP+bP)*Az + bP/(aP+bP)*Bz
前三行将 E 转换为重心坐标，接下来的三行 d。然后我们计算 P 的重心坐标，并将其转换回笛卡尔坐标。在那一步中，我们还将它们去均匀化，即除以重心坐标的总和。
总的来说，这里的代码量还是比较大的。您可以通过将通用表达式移至专用变量来减少操作次数，尤其是当您的编译器不为您执行此操作时。一个好处是除了最终的去均质化，即除以 (a+b) 之外，您不需要任何除法。如果计算 1/(a+b) 一次，只需要一次除法即可凑合，这对性能有好处。
然而，上述代码的真正好处可能是您可以使用重心坐标做很多其他坐标系无法轻易完成的好事。例如，如果要检查射线是否击中线段上或三角形外某处的线AB，只需检查是否aP*bP > 0。
暂时忽略 d 具有最小分量的轴，并处理由此产生的二维问题，就像我们在您的插图上看到的那样。
您可以预先计算射线支撑线的方程，形式为 ax + by + c = 0（假设忽略 z）。在这个表达式中插入三个顶点的坐标，符号会告诉你顶点在直线的哪一侧。
与直线的两个交点出现在端点处符号不同的边上。
然后，要确定哪条是右边缘，射线与第三条角之间的夹角的符号就可以了（如果我是对的）；
当你知道哪条边时，你可以计算边的参数方程的参数，你可以从前面计算的符号中推导出来。例如，沿边 AB，t = Sb / (Sb - Sa)。同时计算 1 - t;
最后，使用 t 值在端点之间进行插值，这次是在 3D 中。
计算成本为
Sa,Sb,Sc三个符号的求值，取6+和6x；
选择两个边缘候选，进行两次或三次比较；
选择单个候选，取一个2D叉积，3+和2x和一个比较；
计算插值参数,2+,1/;
最终3D插值，3+，6x.
很难做到更短。
查看论文
Fast, minimum storage ray-triangle intersection, by Tomas Möller and Ben Trombone, in Journal of Graphics Tools, 2(1):21–28, 1997.
另见 this page。
作者说：
One advantage of this method is that the plane equation need not be computed on the fly nor be stored, which can amount to significant memory savings for triangle meshes. As we found our method to be comparable in speed to previous methods, we believe it is the fastest ray-triangle intersection routine for triangles that do not have precomputed plane equations.