bvh_builder_hair.h

// Copyright 2009-2021 Intel Corporation
// SPDX-License-Identifier: Apache-2.0

#pragma once

#include "../bvh/bvh.h"
#include "../geometry/primitive.h"
#include "../builders/bvh_builder_sah.h"
#include "../builders/heuristic_binning_array_aligned.h"
#include "../builders/heuristic_binning_array_unaligned.h"
#include "../builders/heuristic_strand_array.h"

#define NUM_HAIR_OBJECT_BINS 32

namespace embree
{
  namespace isa
  {
    struct BVHBuilderHair
    {
      /*! settings for builder */
      struct Settings
      {
        /*! default settings */
        Settings ()
        : branchingFactor(2), maxDepth(32), logBlockSize(0), minLeafSize(1), maxLeafSize(7), finished_range_threshold(inf) {}

      public:
        size_t branchingFactor;  //!< branching factor of BVH to build
        size_t maxDepth;         //!< maximum depth of BVH to build
        size_t logBlockSize;     //!< log2 of blocksize for SAH heuristic
        size_t minLeafSize;      //!< minimum size of a leaf
        size_t maxLeafSize;      //!< maximum size of a leaf
        size_t finished_range_threshold;  //!< finished range threshold
      };

      template<typename NodeRef,
        typename CreateAllocFunc,
        typename CreateAABBNodeFunc,
        typename SetAABBNodeFunc,
        typename CreateOBBNodeFunc,
        typename SetOBBNodeFunc,
        typename CreateLeafFunc,
        typename ProgressMonitor,
        typename ReportFinishedRangeFunc>

        class BuilderT
        {
          ALIGNED_CLASS_(16);
          friend struct BVHBuilderHair;

          typedef FastAllocator::CachedAllocator Allocator;
          typedef HeuristicArrayBinningSAH<PrimRef,NUM_HAIR_OBJECT_BINS> HeuristicBinningSAH;
          typedef UnalignedHeuristicArrayBinningSAH<PrimRef,NUM_HAIR_OBJECT_BINS> UnalignedHeuristicBinningSAH;
          typedef HeuristicStrandSplit HeuristicStrandSplitSAH;

          static const size_t MAX_BRANCHING_FACTOR =  8;         //!< maximum supported BVH branching factor
          static const size_t MIN_LARGE_LEAF_LEVELS = 8;         //!< create balanced tree if we are that many levels before the maximum tree depth
          static const size_t SINGLE_THREADED_THRESHOLD = 4096;  //!< threshold to switch to single threaded build

          static const size_t travCostAligned = 1;
          static const size_t travCostUnaligned = 5;
          static const size_t intCost = 6;

          BuilderT (Scene* scene,
                    PrimRef* prims,
                    const CreateAllocFunc& createAlloc,
                    const CreateAABBNodeFunc& createAABBNode,
                    const SetAABBNodeFunc& setAABBNode,
                    const CreateOBBNodeFunc& createOBBNode,
                    const SetOBBNodeFunc& setOBBNode,
                    const CreateLeafFunc& createLeaf,
                    const ProgressMonitor& progressMonitor,
                    const ReportFinishedRangeFunc& reportFinishedRange,
                    const Settings settings)

            : cfg(settings),
            prims(prims),
            createAlloc(createAlloc),
            createAABBNode(createAABBNode),
            setAABBNode(setAABBNode),
            createOBBNode(createOBBNode),
            setOBBNode(setOBBNode),
            createLeaf(createLeaf),
            progressMonitor(progressMonitor),
            reportFinishedRange(reportFinishedRange),
            alignedHeuristic(prims), unalignedHeuristic(scene,prims), strandHeuristic(scene,prims) {}

          /*! checks if all primitives are from the same geometry */
          __forceinline bool sameGeometry(const PrimInfoRange& range)
          {
            if (range.size() == 0) return true;
            unsigned int firstGeomID = prims[range.begin()].geomID();
            for (size_t i=range.begin()+1; i<range.end(); i++) {
              if (prims[i].geomID() != firstGeomID){
                return false;
              }
            }
            return true;
          }

          /*! creates a large leaf that could be larger than supported by the BVH */
          NodeRef createLargeLeaf(size_t depth, const PrimInfoRange& pinfo, Allocator alloc)
          {
            /* this should never occur but is a fatal error */
            if (depth > cfg.maxDepth)
              throw_RTCError(RTC_ERROR_UNKNOWN,"depth limit reached");

            /* create leaf for few primitives */
            if (pinfo.size() <= cfg.maxLeafSize && sameGeometry(pinfo))
              return createLeaf(prims,pinfo,alloc);

            /* fill all children by always splitting the largest one */
            PrimInfoRange children[MAX_BRANCHING_FACTOR];
            unsigned numChildren = 1;
            children[0] = pinfo;

            do {

              /* find best child with largest bounding box area */
              int bestChild = -1;
              size_t bestSize = 0;
              for (unsigned i=0; i<numChildren; i++)
              {
                /* ignore leaves as they cannot get split */
                if (children[i].size() <= cfg.maxLeafSize && sameGeometry(children[i]))
                  continue;

                /* remember child with largest size */
                if (children[i].size() > bestSize) {
                  bestSize = children[i].size();
                  bestChild = i;
                }
              }
              if (bestChild == -1) break;

              /*! split best child into left and right child */
              __aligned(64) PrimInfoRange left, right;
              if (!sameGeometry(children[bestChild])) {
                alignedHeuristic.splitByGeometry(children[bestChild],left,right);
              } else {
                alignedHeuristic.splitFallback(children[bestChild],left,right);
              }

              /* add new children left and right */
              children[bestChild] = children[numChildren-1];
              children[numChildren-1] = left;
              children[numChildren+0] = right;
              numChildren++;

            } while (numChildren < cfg.branchingFactor);

            /* create node */
            auto node = createAABBNode(alloc);

            for (size_t i=0; i<numChildren; i++) {
              const NodeRef child = createLargeLeaf(depth+1,children[i],alloc);
              setAABBNode(node,i,child,children[i].geomBounds);
            }

            return node;
          }

          /*! performs split */
          __noinline void split(const PrimInfoRange& pinfo, PrimInfoRange& linfo, PrimInfoRange& rinfo, bool& aligned) // FIXME: not inlined as ICC otherwise uses much stack
          {
            /* variable to track the SAH of the best splitting approach */
            float bestSAH = inf;
            const size_t blocks = (pinfo.size()+(1ull<<cfg.logBlockSize)-1ull) >> cfg.logBlockSize;
            const float leafSAH = intCost*float(blocks)*halfArea(pinfo.geomBounds);

            /* try standard binning in aligned space */
            float alignedObjectSAH = inf;
            HeuristicBinningSAH::Split alignedObjectSplit;
            if (aligned) {
              alignedObjectSplit = alignedHeuristic.find(pinfo,cfg.logBlockSize);
              alignedObjectSAH = travCostAligned*halfArea(pinfo.geomBounds) + intCost*alignedObjectSplit.splitSAH();
              bestSAH = min(alignedObjectSAH,bestSAH);
            }

            /* try standard binning in unaligned space */
            UnalignedHeuristicBinningSAH::Split unalignedObjectSplit;
            LinearSpace3fa uspace;
            float unalignedObjectSAH = inf;
            if (bestSAH > 0.7f*leafSAH) {
              uspace = unalignedHeuristic.computeAlignedSpace(pinfo);
              const PrimInfoRange sinfo = unalignedHeuristic.computePrimInfo(pinfo,uspace);
              unalignedObjectSplit = unalignedHeuristic.find(sinfo,cfg.logBlockSize,uspace);
              unalignedObjectSAH = travCostUnaligned*halfArea(pinfo.geomBounds) + intCost*unalignedObjectSplit.splitSAH();
              bestSAH = min(unalignedObjectSAH,bestSAH);
            }

            /* try splitting into two strands */
            HeuristicStrandSplitSAH::Split strandSplit;
            float strandSAH = inf;
            if (bestSAH > 0.7f*leafSAH && pinfo.size() <= 256) {
              strandSplit = strandHeuristic.find(pinfo,cfg.logBlockSize);
              strandSAH = travCostUnaligned*halfArea(pinfo.geomBounds) + intCost*strandSplit.splitSAH();
              bestSAH = min(strandSAH,bestSAH);
            }

            /* fallback if SAH heuristics failed */
            if (unlikely(!std::isfinite(bestSAH)))
            {
              alignedHeuristic.deterministic_order(pinfo);
              alignedHeuristic.splitFallback(pinfo,linfo,rinfo);
            }

            /* perform aligned split if this is best */
            else if (bestSAH == alignedObjectSAH) {
              alignedHeuristic.split(alignedObjectSplit,pinfo,linfo,rinfo);
            }

            /* perform unaligned split if this is best */
            else if (bestSAH == unalignedObjectSAH) {
              unalignedHeuristic.split(unalignedObjectSplit,uspace,pinfo,linfo,rinfo);
              aligned = false;
            }

            /* perform strand split if this is best */
            else if (bestSAH == strandSAH) {
              strandHeuristic.split(strandSplit,pinfo,linfo,rinfo);
              aligned = false;
            }

            /* can never happen */
            else
              assert(false);
          }

          /*! recursive build */
          NodeRef recurse(size_t depth, const PrimInfoRange& pinfo, Allocator alloc, bool toplevel, bool alloc_barrier)
          {
            /* get thread local allocator */
            if (!alloc)
              alloc = createAlloc();

            /* call memory monitor function to signal progress */
            if (toplevel && pinfo.size() <= SINGLE_THREADED_THRESHOLD)
              progressMonitor(pinfo.size());

            PrimInfoRange children[MAX_BRANCHING_FACTOR];

            /* create leaf node */
            if (depth+MIN_LARGE_LEAF_LEVELS >= cfg.maxDepth || pinfo.size() <= cfg.minLeafSize) {
              alignedHeuristic.deterministic_order(pinfo);
              return createLargeLeaf(depth,pinfo,alloc);
            }

            /* fill all children by always splitting the one with the largest surface area */
            size_t numChildren = 1;
            children[0] = pinfo;
            bool aligned = true;

            do {

              /* find best child with largest bounding box area */
              ssize_t bestChild = -1;
              float bestArea = neg_inf;
              for (size_t i=0; i<numChildren; i++)
              {
                /* ignore leaves as they cannot get split */
                if (children[i].size() <= cfg.minLeafSize)
                  continue;

                /* remember child with largest area */
                if (area(children[i].geomBounds) > bestArea) {
                  bestArea = area(children[i].geomBounds);
                  bestChild = i;
                }
              }
              if (bestChild == -1) break;

              /*! split best child into left and right child */
              PrimInfoRange left, right;
              split(children[bestChild],left,right,aligned);

              /* add new children left and right */
              children[bestChild] = children[numChildren-1];
              children[numChildren-1] = left;
              children[numChildren+0] = right;
              numChildren++;

            } while (numChildren < cfg.branchingFactor);

            NodeRef node;

            /* create aligned node */
            if (aligned)
            {
              node = createAABBNode(alloc);

              /* spawn tasks or ... */
              if (pinfo.size() > SINGLE_THREADED_THRESHOLD)
              {
                parallel_for(size_t(0), numChildren, [&] (const range<size_t>& r) {
                    for (size_t i=r.begin(); i<r.end(); i++) {
                      const bool child_alloc_barrier = pinfo.size() > cfg.finished_range_threshold && children[i].size() <= cfg.finished_range_threshold;
                      setAABBNode(node,i,recurse(depth+1,children[i],nullptr,true,child_alloc_barrier),children[i].geomBounds);
                      _mm_mfence(); // to allow non-temporal stores during build
                    }
                  });
              }
              /* ... continue sequentially */
              else {
                for (size_t i=0; i<numChildren; i++) {
                  const bool child_alloc_barrier = pinfo.size() > cfg.finished_range_threshold && children[i].size() <= cfg.finished_range_threshold;
                  setAABBNode(node,i,recurse(depth+1,children[i],alloc,false,child_alloc_barrier),children[i].geomBounds);
                }
              }
            }

            /* create unaligned node */
            else
            {
              node = createOBBNode(alloc);

              /* spawn tasks or ... */
              if (pinfo.size() > SINGLE_THREADED_THRESHOLD)
              {
                parallel_for(size_t(0), numChildren, [&] (const range<size_t>& r) {
                    for (size_t i=r.begin(); i<r.end(); i++) {
                      const LinearSpace3fa space = unalignedHeuristic.computeAlignedSpace(children[i]);
                      const PrimInfoRange sinfo = unalignedHeuristic.computePrimInfo(children[i],space);
                      const OBBox3fa obounds(space,sinfo.geomBounds);
                      const bool child_alloc_barrier = pinfo.size() > cfg.finished_range_threshold && children[i].size() <= cfg.finished_range_threshold;
                      setOBBNode(node,i,recurse(depth+1,children[i],nullptr,true,child_alloc_barrier),obounds);
                      _mm_mfence(); // to allow non-temporal stores during build
                    }
                  });
              }
              /* ... continue sequentially */
              else
              {
                for (size_t i=0; i<numChildren; i++) {
                  const LinearSpace3fa space = unalignedHeuristic.computeAlignedSpace(children[i]);
                  const PrimInfoRange sinfo = unalignedHeuristic.computePrimInfo(children[i],space);
                  const OBBox3fa obounds(space,sinfo.geomBounds);
                  const bool child_alloc_barrier = pinfo.size() > cfg.finished_range_threshold && children[i].size() <= cfg.finished_range_threshold;
                  setOBBNode(node,i,recurse(depth+1,children[i],alloc,false,child_alloc_barrier),obounds);
                }
              }
            }

            /* reports a finished range of primrefs */
            if (unlikely(alloc_barrier))
              reportFinishedRange(pinfo);

            return node;
          }

        private:
          Settings cfg;
          PrimRef* prims;
          const CreateAllocFunc& createAlloc;
          const CreateAABBNodeFunc& createAABBNode;
          const SetAABBNodeFunc& setAABBNode;
          const CreateOBBNodeFunc& createOBBNode;
          const SetOBBNodeFunc& setOBBNode;
          const CreateLeafFunc& createLeaf;
          const ProgressMonitor& progressMonitor;
          const ReportFinishedRangeFunc& reportFinishedRange;

        private:
          HeuristicBinningSAH alignedHeuristic;
          UnalignedHeuristicBinningSAH unalignedHeuristic;
          HeuristicStrandSplitSAH strandHeuristic;
        };

      template<typename NodeRef,
        typename CreateAllocFunc,
        typename CreateAABBNodeFunc,
        typename SetAABBNodeFunc,
        typename CreateOBBNodeFunc,
        typename SetOBBNodeFunc,
        typename CreateLeafFunc,
        typename ProgressMonitor,
        typename ReportFinishedRangeFunc>

        static NodeRef build (const CreateAllocFunc& createAlloc,
                              const CreateAABBNodeFunc& createAABBNode,
                              const SetAABBNodeFunc& setAABBNode,
                              const CreateOBBNodeFunc& createOBBNode,
                              const SetOBBNodeFunc& setOBBNode,
                              const CreateLeafFunc& createLeaf,
                              const ProgressMonitor& progressMonitor,
                              const ReportFinishedRangeFunc& reportFinishedRange,
                              Scene* scene,
                              PrimRef* prims,
                              const PrimInfo& pinfo,
                              const Settings settings)
        {
          typedef BuilderT<NodeRef,
            CreateAllocFunc,
            CreateAABBNodeFunc,SetAABBNodeFunc,
            CreateOBBNodeFunc,SetOBBNodeFunc,
            CreateLeafFunc,ProgressMonitor,
            ReportFinishedRangeFunc> Builder;

          Builder builder(scene,prims,createAlloc,
                          createAABBNode,setAABBNode,
                          createOBBNode,setOBBNode,
                          createLeaf,progressMonitor,reportFinishedRange,settings);

          NodeRef root = builder.recurse(1,pinfo,nullptr,true,false);
          _mm_mfence(); // to allow non-temporal stores during build
          return root;
        }
    };
  }
}