Duplicated leaf node in custom BVH8.

[MaxLykoS]

I'm following bvh_builder tutorial to use rtcNewBVH to build my own custom BVH8. However when I calculated leaf counts under each node I found that given the input of bounding box, the leaf nodes of BVH tree might get duplicated, for example if input bounding boxes are 13, final leaf counts is 25. Here is my BVH8 creation code. I can provide whole code if you want to reproduce it.

struct Node
{
public:
  unsigned int id;
  bool isLeaf;
  virtual float SAH() = 0;
};

struct InnerNode : public Node
{
  embree::BBox3fa bounds[8];
  Node* children[8];

  InnerNode()
  {
    isLeaf = false;
    for (size_t i = 0; i < 8; ++i)
    {
      bounds[i] = embree::empty;
      children[i] = nullptr;
    }
  }

  float SAH()
  {
    float sum_area = 0.0f;
    embree::BBox3fa merged_bounds(embree::empty);
    for (size_t i = 0; i < 8; i++)
    {
      if (children == nullptr) break;
      if (children[i] == nullptr) continue;
      sum_area += area(bounds[i]) * children[i]->SAH();
      merged_bounds.extend(bounds[i]);
    }
    return 1.0f + sum_area / area(merged_bounds);
    //return 1.0f + (area(bounds[0]) * children[0]->sah() + area(bounds[1]) * children[1]->sah()) / area(merge(bounds[0], bounds[1]));
  }

  static void* Create(RTCThreadLocalAllocator alloc, unsigned int numChildren, void* userPtr)
  {
    //assert(numChildren == 8);
    void* ptr = rtcThreadLocalAlloc(alloc, sizeof(InnerNode), 16);
    return (void*) new (ptr) InnerNode;
  }

  static void  SetChildren(void* nodePtr, void** childPtr, unsigned int numChildren, void* userPtr)
  {
    //assert(numChildren == 8);
    for (size_t i = 0; i < numChildren; i++)
      ((InnerNode*)nodePtr)->children[i] = (Node*)childPtr[i];
  }

  static void  SetBounds(void* nodePtr, const RTCBounds** bounds, unsigned int numChildren, void* userPtr)
  {
    //assert(numChildren == 8);
    for (size_t i = 0; i < numChildren; i++)
      ((InnerNode*)nodePtr)->bounds[i] = *(const embree::BBox3fa*)bounds[i];
  }
};

struct LeafNode : public Node
{
  embree::BBox3fa bounds;
  unsigned int indexToInstanceData;

  LeafNode(const embree::BBox3fa& bounds, unsigned int indexToInstanceData)
    :
    bounds(bounds),
    indexToInstanceData(indexToInstanceData)
  {
    isLeaf = true;
  }

  float SAH()
  {
    return 1.0f;
  }

  static void* Create(RTCThreadLocalAllocator alloc, const RTCBuildPrimitive* prims, size_t numPrims, void* userPtr)
  {
    assert(numPrims == 1);
    void* ptr = rtcThreadLocalAlloc(alloc, sizeof(LeafNode), 16);
    return (void*) new (ptr) LeafNode(*(embree::BBox3fa*)prims, prims->geomID);
  }
};

bool memoryMonitor(void* userPtr, ssize_t bytes, bool post)
{
  return true;
}

bool buildProgress(void* userPtr, double f)
{
  return true;
}

void splitPrimitive(const RTCBuildPrimitive* prim, unsigned int dim, float pos, RTCBounds* lprim, RTCBounds* rprim, void* userPtr)
{
  assert(dim < 3);
  assert(prim->geomID == 0);
  *(embree::BBox3fa*)lprim = *(embree::BBox3fa*)prim;
  *(embree::BBox3fa*)rprim = *(embree::BBox3fa*)prim;
  (&lprim->upper_x)[dim] = pos;
  (&rprim->lower_x)[dim] = pos;
}

void BVH8::Build(embree::avector<RTCBuildPrimitive>& prims_i, const size_t& extraSpace)
{
  rtcSetDeviceMemoryMonitorFunction(m_device, memoryMonitor, nullptr);

  m_bvh = rtcNewBVH(m_device);

  embree::avector<RTCBuildPrimitive> prims;
  prims.reserve(prims_i.size() + extraSpace);
  prims.resize(prims_i.size());

  /* settings for BVH build */
  RTCBuildArguments arguments = rtcDefaultBuildArguments();
  arguments.byteSize = sizeof(arguments);
  arguments.buildFlags = RTC_BUILD_FLAG_DYNAMIC;
  arguments.buildQuality = RTC_BUILD_QUALITY_HIGH;
  arguments.maxBranchingFactor = 8;
  arguments.maxDepth = 1024;
  arguments.sahBlockSize = 8;
  arguments.minLeafSize = 1;
  arguments.maxLeafSize = 1;
  arguments.traversalCost = 1.0f;
  arguments.intersectionCost = 1.0f;
  arguments.bvh = m_bvh;
  arguments.primitives = prims.data();
  arguments.primitiveCount = prims.size();
  arguments.primitiveArrayCapacity = prims.capacity();
  arguments.createNode = InnerNode::Create;
  arguments.setNodeChildren = InnerNode::SetChildren;
  arguments.setNodeBounds = InnerNode::SetBounds;
  arguments.createLeaf = LeafNode::Create;
  arguments.splitPrimitive = splitPrimitive;
  arguments.buildProgress = buildProgress;
  arguments.userPtr = nullptr;

  /* we recreate the prims array here, as the builders modify this array */
  for (size_t j = 0; j < prims.size(); j++)
    prims[j] = prims_i[j];

  std::cout << "Building BVH over " << prims.size() << " primitives, " << std::flush;
  double t0 = embree::getSeconds();
  m_root = (Node*)rtcBuildBVH(&arguments);
  double t1 = embree::getSeconds();
  const float sah = m_root ? m_root->SAH() : 0.0f;
  std::cout << 1000.0f * (t1 - t0) << "ms, " << 1E-6 * double(prims.size()) / (t1 - t0) << " Mprims/s, sah = " << sah << " [DONE]" << std::endl;
}

[svenwoop]

This is expected behaviour in RTC_BUILD_QUALITY_HIGH mode, which will perform spatial splits. Use RTC_BUILD_QUALITY_MEDIUM if you do not want the BVH builder to perform spatial splits.