1

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

在该方法中，我正在检查光线和对象的交集，我返回一个结构，其中包含光线到命中的距离、命中的位置向量和法线向量，如果距离为 -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，或者是一个具有最预期交叉点数量的数组，然后在其中包含负距离的交叉点。

4

1 回答 1

1

这是我成功用于大量对象的方法。（特别是对于球棒原子模型；请参阅我的Wikipedia 用户页面了解我用于这些的方程式。）

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

例如，如果您有一条单位射线n（因此n · n = 1）和一个以c为中心的半径为r的球体，当且仅当h ≥ 0 时，射线与球体相交，

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

如果是这样，在距离d，

d = n · c ± sqrt( h )

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

对于每条射线，根据已知的最小 z 坐标（例如，c z - r表示球体）对要测试的对象进行排序/选择。这样，当您在距离d处找到交点时，您可以忽略最小 z 坐标大于d的所有对象，因为交点必然在已知交点后面更远。

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

于 2019-01-21T17:00:41.480 回答