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

Question

我正在为 x86 消费类硬件编写一个 CPU-raytracer(在 C++11 中，目前使用 gcc 4.7.1)。

我正在使用一个 kD 树来保存我的三角形，并用我给定的光线将叶子中的所有三角形相交。根据我的探查器，此任务占用了大部分运行时间(取决于 kd 树和输入和选择的参数，大约占我运行时间的 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 大致相同的时间否定任何速度奖励。错过跳跃预测可能是大幅放缓的原因。

我该怎么做才正确(“它”在每个三角形中只调用一次相交)？

Answer 1

您可以继续计算光线并将与三角形相交的最后一条光线的索引直接存储在三角形中。如果你是多线程的，你可以有多个这样的值和线程索引索引。

emplace 由于重新散列可能会花费很多时间。您可以使用从最后一帧收集的统计数据(针对同一光线，或者只是所有光线的上限)为 unordered_set 构造函数指定更好的初始桶数。