c - 关于光线追踪算法相交测试性能的问题

Question

我目前正在构建一个基本的光线追踪算法，并且需要弄清楚哪种处理交点的系统在性能方面是最佳的。

在我检查光线和对象的交点的方法中，我返回一个结构，其中包含光线行进到命中的距离、命中的位置 vector 和法线 vector 或 -1没有交叉点时的距离。

对于下一步，我必须找到所有交叉点的最短距离并排除距离为负的那些。

我什至考虑过使用 2 个结构，一个只有负距离，一个完整的结构来减少所需的空间量，但我认为这不会真正产生影响。

到目前为止我的选择:首先遍历交叉点的数组并排除距离为负的那些，然后通过排序算法(由于实现速度快，可能是插入排序)找到与剩余部分的最短距离。

或者将它们放在一个算法中，如果距离为负，则在每个排序步骤中进行测试。

typedef Point3f float[3];
typedef struct {
    float distance;
    Point3f point;
    Point3f normal;
} Intersection;

Intersection intersectObject (Ray-params, object) {
    Intersection intersection;
    //...
    if (hit) {
        intersection.distance = distance;
        intersection.point = point;
        intersection.normal = normal;
    } else {
        intersection.distance = -1.0f;
    }
    return intersection;
}

//loop over screen pixel
    Intersection* intersections;
    int amountIntersections;
    //loop over all objects
    //here I would handle the intersections
    if (amountIntersections) {
        //cast additional rays
    }

我真的想不出什么是处理这个问题的最佳方法，因为它会被调用很多次。交点数组可能是一个动态数组，其中 amountIntersections 作为长度变量，或者是一个具有最大预期交点数量的数组，然后其中有负距离的交点。

Answer 1

这是我已成功用于大量对象的方法。 (特别是对于球棒原子模型；请参阅我的 Wikipedia user page 了解我用于这些的方程式。)

首先，将物体变换到以眼睛为原点的坐标系，投影平面平行于xy平面，中心在正z轴上。正如您从上面的链接页面中看到的那样，这大大简化了所需的方程式。

举个例子，如果你有一个单位射线n(所以n· b>n = 1) 和一个以 c 为中心的半径 r 的球体，光线与球体相交当且仅当 h ≥ 0,

h = (n·c)² + r² - (c·c)

如果是，在距离 d,

d = n·c ± sqrt(h)

如果您编写出必要的代码并使用合理的临时变量，您会发现您可以使用八次乘法和六次加法或减法拒绝非交叉球体，并且这可以使用 SSE2/AVX 内在函数轻松跨对象矢量化(#include <x86intrin.h>)。 (也就是说，不要尝试对 n 或 c 使用 XMM/YMM vector 寄存器，而是将每个寄存器组件用于不同的对象，一次计算 2/4/8 个对象的 h。)

对于每条射线，根据已知的最小 z 坐标(例如，c_z - < i>r 表示球体)。这样，当你在距离d处找到一个交点时，你可以忽略所有最小z坐标大于d的对象，因为交点必然更远，后面已知的十字路口。

同样，您应该忽略所有距离小于到投影平面的距离(即 z_d/< i>n_z，如果飞机在z = z_d，并且每条射线只需要计算一次)，因为这些交点位于眼睛和投影平面之间。 (从技术上讲，如果您将投影平面视为相机，那么您已经“撞上”了某物。)