algorithm - 射线-三角形相交

Question

我看到了Fast Minimum Storage Ray/Triangle Intersection经常推荐 Moller 和 Trumbore 的作品。

问题是，我不介意预先计算和存储任何数量的数据，只要它能加快交叉路口的速度。

所以我的问题是，不关心内存，进行射线-三角形相交的最快方法是什么？

编辑:我不会移动三角形，即它是一个静态场景。

Answer 1

正如其他人所提到的，加快速度的最有效方法是使用加速结构来减少所需的射线-三角形相交的数量。也就是说，您仍然希望光线-三角形相交速度快。如果您乐于预先计算内容，可以尝试以下操作:

将您的射线和三角形边转换为 Plücker coordinates .这使您可以确定您的射线是否以每条边 6 次乘法/加法穿过三角形。您仍然需要将您的光线起点和终点与三角形平面进行比较(每点 4 次乘法/加法)以确保它确实击中了三角形。

最坏情况下的运行时间开销是 26 次乘法/加法的总和。另外请注意，您只需为每个光线/边缘组合计算一次光线/边缘符号，因此如果您正在评估网格，您可能能够使用每个边缘评估两次。

此外，这些数字假设一切都是在齐次坐标系中完成的。您可以通过提前归一化来减少乘法的次数。