问有效地计算查看光线和一组对象之间的第一个交点的最佳方法是什么？

EN

“计算效率”取决于集合的大小。

对于三个微不足道的集合，只需依次测试每一个，这真的不值得尝试优化。

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

或者，如果我误解了你的问题，而你实际上是在询问特定对象类型的光线-对象相交的算法，请参阅同一本书！

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

使用该预计算，您就可以知道将拍摄到场景中的几乎所有光线都可见的内容。因此，光线与环境相交的问题将大大简化:每条光线都会命中一个特定的对象。

当我在做这个many years ago的时候，我正在制作公认简单的场景的实时光线跟踪图像。我已经有很长一段时间没有重温这段代码了，但我怀疑，使用现代编译器和图形硬件，性能会比我当时看到的要好几个数量级。

PS:我第一次读到item buffer的想法是在90年代初做文献搜索的时候。我最初是在(我相信)70年代末的一篇ACM论文中发现的。遗憾的是，我没有可用的源代码参考，但简而言之，这是一个非常古老的想法，在扫描转换硬件上工作得很好。

我假设您有一个射线d= (dx，dy，dz)，从o= (ox，oy，oz)开始，并且您正在寻找参数t，使得交点p= o+d*t。(像this页面，它使用P2-P1表示d，P1表示o，u表示t)。

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

如果不是，那么你可以作弊一点，并按顺序检查光线碰撞。由于每帧有三个对象可能会移动，也可能不会移动，因此预先计算它们与相机的距离(例如，距离中心点)是值得的。按距离摄像机从小到大依次对每个对象进行测试。虽然空闲空间现在是渲染中最昂贵的部分，但这比仅对所有三个空间进行测试并取一个最小值更有效。如果你的图像是高分辨率的，那么这是特别有效的，因为你在像素数量上摊销了成本。

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

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