c++ - 优化光线追踪器中的 BVH 遍历

Question

在我的 CPU 光线追踪器(好吧，路径追踪器)中，大部分 CPU 时间都花在了 BVH 遍历函数上。根据我的分析器，75% 的光线追踪时间花在这个函数和它调用的函数上，而 35% 的时间花在函数本身上。其他 40% 在它调用的不同交集测试中。

基本上，该代码对所有与其相交的边界框和三角形进行 DFS 遍历。它在堆栈上使用静态分配的数组来保存要探索的节点(BVHSTACKSIZE 设置为 32，它永远不需要大部分空间)，因此不会动态分配内存。然而，35% 的时间都花在这里，这对我来说似乎很疯狂。我花了一段时间优化代码，它目前是我能做到的最快速度，但它仍然是我程序中最大的单一瓶颈。

有没有人有进一步优化它的提示？我已经有了一个不错的 BVH 构造算法，所以我认为我不会通过使用不同的 BVH 来获得任何加速。有没有人知道如何在 Mac 上最好地进行逐行分析？

作为引用，示例场景中的这段代码耗时从 <1 微秒到 40 微秒不等，具体取决于交叉点的数量，而 while 循环运行 1 到 ~400 次迭代(也取决于交叉点的数量)。

谢谢!

bool BVHAccel::intersect(Ray& ray) const {
  bool hit = false;

  BVHNode* to_intersect[BVHSTACKSIZE];
  int head = 0;
  to_intersect[head++] = root;

  while (head != 0) {
    assert(head < BVHSTACKSIZE);
    BVHNode* cur = to_intersect[--head];

    if (cur->bb.intersect(ray)) { // Does not modify the ray
      if (cur->isLeaf()) {
        for (const auto& primitive : cur->primitives) {
          hit |= primitive->intersect(ray); // Modifies the ray!
        }
      } else {
        to_intersect[head++] = cur->r;
        to_intersect[head++] = cur->l;
      }
    }
  }

  return hit;
}

bool BBox::intersect(const Ray& r) const {
  double txmin = (min.x - r.o.x) * r.inv_d.x;
  double txmax = (max.x - r.o.x) * r.inv_d.x;
  double tymin = (min.y - r.o.y) * r.inv_d.y;
  double tymax = (max.y - r.o.y) * r.inv_d.y;
  double tzmin = (min.z - r.o.z) * r.inv_d.z;
  double tzmax = (max.z - r.o.z) * r.inv_d.z;

  ascending(txmin, txmax);
  ascending(tymin, tymax);
  ascending(tzmin, tzmax);

  double t0 = std::max(txmin, std::max(tymin, tzmin));
  double t1 = std::min(txmax, std::min(tymax, tzmax));

  if (t1 < t0 || t0 > r.max_t || t1 < r.min_t) {
    return false;
  }

  return true;
}

void ascending(double& a, double& b) {
  if (a > b) {
    std::swap(a, b);
  }
}

Answer 1

您的代码似乎至少有一个问题。 复制 primitive 可能是一项昂贵的操作。

bool BVHAccel::intersect(Ray ray) const {
  bool hit = false;

  BVHNode* to_intersect[BVHSTACKSIZE];
  int head = 0;
  to_intersect[head++] = root;

  while (head != 0) {
    assert(head < BVHSTACKSIZE);
    BVHNode* cur = to_intersect[--head];

    if (cur->bb.intersect(ray)) { // Does not modify the ray
      if (cur->isLeaf()) {
        for (const auto& primitive : cur->primitives) { // this code made a copy of primitives on every call!
          hit |= primitive->intersect(ray); // Modifies the ray!
        }
      } else {
        to_intersect[head++] = cur->r;
        to_intersect[head++] = cur->l;
      }
    }
  }

  return hit;
}

为什么需要修改射线拷贝？

编辑 1:我们可以假设 BVHNode 看起来像这样吗？

constexpr auto BVHSTACKSIZE = 32;

struct Primitive;

struct BVHNode {
    std::vector<Primitive> primitives;
    AABB        bb;   
    BVHNode*    r = nullptr;
    BVHNode*    l = nullptr;

    bool isLeaf() const { return r == nullptr && l == nullptr; }
};