用于高效光线追踪的数据结构/方法

Question

我正在编写一个3D光线跟踪器作为个人学习项目(Enlight),并遇到了一个有趣的问题,涉及在光线和物体场景之间进行交叉测试.

情况是:

• 我有许多光线可以与(球体,盒子,平面等)及其组相交的基元.总的来说,我正在调用这些场景对象.
• 我希望能够通过将它们包装在一个Transform对象中来对具有任意仿射变换的场景对象进行渲染(重要的是,这将使得相同图元的多个实例能够在场景中的不同位置使用,因为图元是不可变的)
• 场景对象可以存储在边界卷层次结构中(即我正在进行空间分区)
• 我的交叉测试Ray用于表示部分光线段的对象(起始矢量,标准化方向矢量,起始距离,结束距离)

问题是当光线撞击Transform对象的边界框时,看起来与包含在其中的变换图元进行交叉测试的唯一方法是将变换Ray为坐标变换的坐标空间.这很容易,但是如果光线没有碰到任何变形的物体,我需要回到原始状态Ray继续跟踪.由于Transforms可以嵌套,这意味着我必须Ray为每个完成的交集跟踪维护一整堆s.

这当然是整个应用程序的内部循环和主要性能瓶颈.它将被称为每秒数百万次,所以我渴望最小化复杂性/避免不必要的内存分配.

有一种聪明的方法可以避免分配新Ray的/保持Ray堆栈吗？

或者有一种更聪明的方式完全这样做？

Answer 1

大多数时候，在光线追踪中，您有几个（数百个、数千个）对象和相当多的光线。可能有数百万条光线。在这种情况下，了解可以在对象上花费什么样的计算以使光线与它们交互更快/更容易是有意义的。

正如 boyfarrell 所建议的，缓存将非常有帮助。不仅在对象上创建将它们移入或移出全局框架的正向和反向变换，而且在全局框架中保留对象的副本可能是有意义的。它使得创建对象或移动它们变得更加昂贵（因为变换发生了变化，缓存的全局帧副本也会发生变化），但这可能没问题。

如果你投射 N 条光线并有 M 个物体，并且 N >> M，那么按理说每个物体都会有多条光线击中它。如果我们假设每条光线都击中一个物体，那么每个物体都有 N/M 条光线击中它。这意味着将 N/M 条光线转换到每个物体，进行命中测试，并可能将其反转。或者每个对象至少进行 N/M 次变换。但是，如果我们缓存变换后的对象，我们可以对每个对象执行一次变换以到达全局框架，然后不需要任何额外的操作。至少对于命中测试来说是这样。