performance - 数据结构/有效光线追踪的方法

我正在将3D raytracer编写为个人学习项目(Enlight)，并且遇到了一个有趣的问题，该问题与在射线和物体场景之间进行相交测试有关。

情况是:

我有许多可以与光线相交的图元(球体，盒子，平面等)及其组。我统称为这些场景对象。

我希望能够通过将对象原语包装在Transform对象中来对对象原语进行任意仿射变换(重要的是，这将使同一原语的多个实例可以在场景中的不同位置使用，因为原语是不可变的)

场景对象可以存储在边界体积层次结构中(即，我正在执行空间分区)

我的交集测试适用于代表局部射线段(起始向量，归一化方向向量，起始距离，结束距离)的Ray对象

问题是，当射线撞击Transform对象的边界框时，似乎对包含在其中的已转换图元进行相交测试的唯一方法是将Ray转换为已转换的坐标空间。这很容易，但是如果射线没有击中任何变形的对象，我就需要退回到原始的Ray继续跟踪。由于Transforms可能是嵌套的，因此这意味着我必须为完成的每个相交轨迹维护一整堆Ray。

这当然是在整个应用程序的内部循环和主要的性能瓶颈之内。每秒将调用数百万次，因此我渴望将复杂性降到最低/避免不必要的内存分配。

有没有一种聪明的方法来避免必须分配新的Ray/保留Ray堆栈？

还是有一种更巧妙的方法来做到这一点？

最佳答案

大多数时候，在光线追踪中，您有几个(十万个)对象以及更多的光线。可能有数百万条射线。在这种情况下，有意义的是查看可以在对象上进行哪种计算，以便更快/更轻松地使光线与对象进行交互。

如boyfarrell建议的那样，缓存将非常有帮助。不仅要在将对象移入或移出全局框架的对象上创建正向和反向变换，而且还要在全局框架中保留对象的副本，这可能是有道理的。创建对象或移动它们(由于转换更改，以及缓存的全局框架副本也是如此)会变得更加昂贵，但这可能是可以的。

如果转换N条光线并具有M个对象，并且N >> M，则可以说每个对象都会有多条光线射中它。如果我们假设每条射线都击中一个对象，那么每个对象都有N/M条射线会照到它。这意味着将N/M射线转换为每个对象，进行测试，并可能将其反转回来。或每个对象最少N/M转换。但是，如果我们缓存转换后的对象，则可以对每个对象执行一次转换以到达全局框架，然后不需要任何其他操作。至少用于 HitTest 。

关于performance - 数据结构/有效光线追踪的方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13924296/