graphics - 有效计算观察光线和一组对象之间的第一个交点的最佳方法是什么？

Question

例如：

一种有效计算视线与一组三个对象之间的第一个交点的方法：一个球体、一个圆锥体和一个圆柱体（其他 3D 图元）。

Answer 1

您正在寻找的是空间分区方案。有很多选择可以解决这个问题，并且在这个领域也进行了大量的研究。值得一读的是 Christer Ericsson 的Real-Time Collision Detection。

那本书中介绍的一种简单方法是定义一个网格，将所有对象分配给它相交的所有单元格，然后沿着与线相交的网格单元从前到后，与与该网格单元关联的每个对象相交。请记住，一个对象可能与更多网格单元相关联，因此计算出的交点实际上可能不在当前单元中，但实际上在稍后。

下一个问题是如何定义该网格。不幸的是，没有一个好的答案，您需要考虑哪种方法最适合您的场景。

其他感兴趣的分区方案是不同的树结构，例如kd-、Oct-和BSP-trees。您甚至可以考虑将树与网格结合使用。

编辑
正如所指出的，如果您的集合实际上是这三个对象，那么您肯定最好只与每个对象相交，然后选择最早的对象。如果您正在寻找射线球、射线圆柱等相交测试，这些并不难，快速的谷歌应该提供您可能需要的所有数学。:)

Answer 2

“计算效率”取决于集合有多大。

对于琐碎的三个，只需依次测试它们中的每一个，它真的不值得尝试优化。

对于较大的集合，请查看划分空间的数据结构（例如 KD-Trees）。整章（甚至整本书）都致力于解决这个问题。我最喜欢的参考书是An Introduction to Ray Tracing (ed. Andrew. S. Glassner)

或者，如果我误读了您的问题，而您实际上是在要求针对特定类型对象的光线-对象交叉算法，请参阅同一本书！

Answer 3

嗯，这取决于你真正想要做什么。如果您想为简单场景中的几乎每个像素生成一个正确的解决方案，一种非常快速的方法是通过预渲染具有唯一标识的所有对象来预先计算每个像素的“前面是什么”使用扫描转换（也称为 z 缓冲区）将颜色转换为背景项缓冲区。这有时被称为项目缓冲区。

使用该预计算，您就可以知道您将要拍摄到场景中的几乎所有光线都可以看到什么。结果，您的光线-环境相交问题得到了极大的简化：每条光线都击中一个特定的对象。

当我多年前这样做时，我正在制作公认的简单场景的实时光线追踪图像。我已经有一段时间没有重新访问该代码了，但我怀疑使用现代编译器和图形硬件，性能会比我当时看到的要好几个数量级。

PS：我在 90 年代初进行文献检索时第一次读到有关 item buffer 的想法。我最初发现它在（我相信）70 年代后期的 ACM 论文中提到过。遗憾的是，我没有可用的源参考，但简而言之，这是一个非常古老的想法，并且在扫描转换硬件上运行良好。

Answer 4

我假设您有一条射线 d = (dx,dy,dz)，从 o = (ox,oy,oz) 开始，并且您正在找到参数 t，使得交点 p = o+d*t。（就像这个页面，它描述了使用 P2-P1 表示 d、P1 表示 o 和 u 表示 t 的射线平面相交）

我要问的第一个问题是“这些物体是否相交”？

如果没有，那么您可以稍微作弊并按顺序检查光线碰撞。由于您有三个可能每帧移动也可能不移动的对象，因此需要预先计算它们与相机的距离（例如从它们的中心点）。按与相机的距离，从最小到最大依次测试每个对象。尽管空白空间现在是渲染中最昂贵的部分，但这比仅针对所有三个进行测试并取最小值更有效。如果您的图像是高分辨率的，那么这将特别有效，因为您可以在像素数上摊销成本。

否则，对所有三个进行测试并取最小值......

在其他情况下，您可能希望混合使用这两种方法。如果您可以按顺序测试其中两个对象（例如，一个球体和一个立方体沿圆柱形隧道向下移动），但测试第三个对象并取最小值以找到最终对象。