c++ - 仅对集合中的每个元素进行一次测试

我正在为x86消费类硬件(以及到目前为止使用gcc 4.7.1的C++ 11)编写CPU-raytracer。

我正在使用一个kD树来保存我的三角形，并用给定的射线将叶子中的所有三角形相交。根据我的探查器，此任务占用了大部分运行时(取决于kd-tree以及大约50％或更多的运行时中的输入和所选参数)。

for (auto p : leaf.triangles) {
    p->intersect(ray, t, intersection); //void intersect(const Ray& ray, float t, Intersection& output)
}

(p是指向 vector 中其他地方的三角形的指针)。

我的kd树可能会更深地展开，但这迫使我有更多的叶子共享相同的三角形。因为我经常被迫测试相邻的叶子，我最终将一遍又一遍地相交相同的三角形。到目前为止，这可能是我最大的瓶颈。

一个简单的解决方案似乎是某种列表，该列表将保留所有我已经交叉的指针。由于unordered_set<Triangle*>和find的平均平均费用不变，因此我决定使用emplace。

unordered_set<Triangle*> alreadyTested; //used for all leafs a ray visits
for (auto p : leaf.triangles) {
     if (alreadyTested.find(p) == alreadyTested.end()) {
          p->intersect(ray, t, intersection);
          alreadyTested.emplace(p);
     }
}

用GCC -O3编译

我的运行时总体增加了4到8倍。我的分析器告诉我，find和emplace花费的时间与单个intersect消除速度提成的时间大致相同。错过的跳跃预测可能是大规模减速的原因。

我该如何正确处理(“it”在每个三角形中仅相交一次)？

最佳答案

您可以继续对光线进行计数，并存储直接与三角形相交的最后一条光线的索引。如果您是多线程的，则可以有多个这样的值并按线程索引进行索引。

由于重新哈希，emplace可能会花费很多时间。您可以使用从最后一帧收集的统计信息(对于同一条射线，或仅对所有射线的上限)来为unordered_set构造函数指定更好的初始存储桶数。

关于c++ - 仅对集合中的每个元素进行一次测试，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25352263/