BVH depth and recommended stack depth

[robinchrist]

In most examples, a SmallStack with stack depth 64 is used.

If I understand the code correctly, you can run into undefined behaviour (in Release mode) or generally issues if your SmallStack is too small.

Is 64 so large that there will never be a case that it's not enough?

Or would it make sense to use GrowingStack and call reserve on the elems vector beforehand to make sure it's fast enough?

Is there any out of the box way to find the BVH depth? I couldn't find one and it doesn't seem like it's tracked during construction.

[madmann91]

That is a fair question. There currently isn't a way to compute the depth of a BVH in the code, though doing it shouldn't be very hard:

size_t depth(const Bvh& bvh, size_t node_id = 0) {
  const auto& node = bvh.nodes[node_id];
  if (node.is_leaf())
    return 1;
  else
    return 1 + std::max(depth(bvh, node.index.first_id()), depth(bvh, node.index.first_id() + 1));
}

That said, a depth of 64 should be enough most of the time. The overhead of using a dynamic stack is high enough to justify using a fixed one in my experience.

[robinchrist]

The overhead of using a dynamic stack is high enough to justify using a fixed one in my experience.

I wonder why though? If you pre-allocate it (and re-use it), it shouldn’t be slower than the static stack

[madmann91]

Stack memory will typically be in the cache, and on most ABIs you have a dedicated register to hold the address of the stack pointer. This means that, using a fixed stack, you: 1. Don't have cache misses as often, 2. Don't need additional registers to hold the pointers to the stack.

[madmann91]

I just realized that in my previous comment, I am referring to the traversal stack and the ABI stack with the same word "stack", which could be confusing. What I mean is that using the ABI stack for the traversal stack is more efficient than using the heap (for the two reasons pointed out above). A local variable of type bvh::SmallStack will have its elements on the ABI stack, unlike a bvh::GrowingStack.