<commit_before>// ======================================================================== //
// Copyright 2009-2015 Intel Corporation                                    //
//                                                                          //
// Licensed under the Apache License, Version 2.0 (the "License");          //
// you may not use this file except in compliance with the License.         //
// You may obtain a copy of the License at                                  //
//                                                                          //
//     http://www.apache.org/licenses/LICENSE-2.0                           //
//                                                                          //
// Unless required by applicable law or agreed to in writing, software      //
// distributed under the License is distributed on an "AS IS" BASIS,        //
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. //
// See the License for the specific language governing permissions and      //
// limitations under the License.                                           //
// ======================================================================== //

#pragma once

#include "builders/heuristic_object_partition_new.h"
#include "builders/workstack.h"

#include "algorithms/parallel_create_tree.h"

namespace embree
{
  namespace isa
  {
    template<typename NodeRef>
      class __aligned(64) BuildRecord : public PrimInfo
    {
    public:
      __forceinline BuildRecord() {}
      
      __forceinline BuildRecord(const PrimInfo& pinfo, const size_t depth, NodeRef* parent) 
        : PrimInfo(pinfo), depth(depth), parent(parent), area(embree::area(pinfo.geomBounds)) {}
      
#if defined(_MSC_VER)
      __forceinline BuildRecord& operator=(const BuildRecord &arg) { 
        memcpy(this, &arg, sizeof(BuildRecord));    
        return *this;
      }
#endif

      __forceinline void init(size_t depth)
      {
        parent = NULL;
        this->depth = depth;
        area = embree::area(geomBounds);
      }
      
      __forceinline bool operator<(const BuildRecord &br) const { return size() < br.size(); } 
      __forceinline bool operator>(const BuildRecord &br) const { return size() > br.size(); } 
      
      struct Greater {
        __forceinline bool operator()(const BuildRecord& a, const BuildRecord& b) {
          return a.size() > b.size();
        }
      };

    public:
      unsigned depth;         //!< depth from the root of the tree
      float    area;          //!< surface area of bounding box
      NodeRef* parent;        //!< reference pointing to us
    };
    
    template<typename NodeRef, typename Allocator, typename CreateAllocFunc, typename CreateNodeFunc, typename CreateLeafFunc>
      class BVHBuilderSAH
    {
      static const size_t MAX_BRANCHING_FACTOR = 16;  //!< maximal supported BVH branching factor
      static const size_t MIN_LARGE_LEAF_LEVELS = 8;  //!< create balanced tree of we are that many levels before the maximal tree depth

    public:

      BVHBuilderSAH (CreateAllocFunc& createAlloc, CreateNodeFunc& createNode, CreateLeafFunc& createLeaf,
                         PrimRef* prims, const PrimInfo& pinfo,
                         const size_t branchingFactor, const size_t maxDepth, 
                         const size_t logBlockSize, const size_t minLeafSize, const size_t maxLeafSize)
        : createAlloc(createAlloc), createNode(createNode), createLeaf(createLeaf), 
          prims(prims), pinfo(pinfo), 
          branchingFactor(branchingFactor), maxDepth(maxDepth),
          logBlockSize(logBlockSize), minLeafSize(minLeafSize), maxLeafSize(maxLeafSize)
      {
        if (branchingFactor > MAX_BRANCHING_FACTOR)
          THROW_RUNTIME_ERROR("bvh4_builder: branching factor too large");
      }

      void splitFallback(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild)
      {
        const size_t center = (current.begin + current.end)/2;
        
        CentGeomBBox3fa left; left.reset();
        for (size_t i=current.begin; i<center; i++)
          left.extend(prims[i].bounds());
        new (&leftChild) PrimInfo(current.begin,center,left.geomBounds,left.centBounds);
        
        CentGeomBBox3fa right; right.reset();
        for (size_t i=center; i<current.end; i++)
          right.extend(prims[i].bounds());	
        new (&rightChild) PrimInfo(center,current.end,right.geomBounds,right.centBounds);
      }

      __forceinline void splitSequential(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild)
      {
        /* calculate binning function */
        PrimInfo pinfo(current.size(),current.geomBounds,current.centBounds);
        ObjectPartitionNew::Split split = ObjectPartitionNew::find(prims,current.begin,current.end,pinfo,logBlockSize);

        /* if we cannot find a valid split, enforce an arbitrary split */
        if (unlikely(!split.valid())) splitFallback(current,leftChild,rightChild);
        
        /* partitioning of items */
        else {
          //split.partition_parallel(prims, current.begin, current.end, leftChild, rightChild);
          //size_t left0 = leftChild.size();
          split.partition(prims, current.begin, current.end, leftChild, rightChild);
          //size_t left1 = leftChild.size();
          //if (left0 != left1) PRINT2(left0,left1);
        }
      }

      void splitParallel(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild, Allocator& alloc)
      {
        /* calculate binning function */
        PrimInfo pinfo(current.size(),current.geomBounds,current.centBounds);
        ObjectPartitionNew::Split split = ObjectPartitionNew::find_parallel(prims,current.begin,current.end,pinfo,logBlockSize);
        
        /* if we cannot find a valid split, enforce an arbitrary split */
        if (unlikely(!split.valid())) splitFallback(current,leftChild,rightChild);
        
        /* partitioning of items */
        else {
          split.partition_parallel(prims, current.begin, current.end, leftChild, rightChild);
          //size_t left0 = leftChild.size();
          //split.partition(prims, current.begin, current.end, leftChild, rightChild);
          //size_t left1 = leftChild.size();
          //if (left0 != left1) PRINT2(left0,left1);
        }
      }

      void createLargeLeaf(const BuildRecord<NodeRef>& current, Allocator& nodeAlloc, Allocator& leafAlloc)
      {
        if (current.depth > maxDepth) 
          THROW_RUNTIME_ERROR("depth limit reached");
        
        /* create leaf for few primitives */
        if (current.size() <= maxLeafSize) {
          createLeaf(current,prims,leafAlloc);
          return;
        }

        /* fill all children by always splitting the largest one */
        BuildRecord<NodeRef> children[MAX_BRANCHING_FACTOR];
        size_t numChildren = 1;
        children[0] = current;
        
        do {
          
          /* find best child with largest bounding box area */
          int bestChild = -1;
          int bestSize = 0;
          for (size_t i=0; i<numChildren; i++)<commit_msg>enabling parallel_partition in subtree creation works<commit_after>// ======================================================================== //
// Copyright 2009-2015 Intel Corporation                                    //
//                                                                          //
// Licensed under the Apache License, Version 2.0 (the "License");          //
// you may not use this file except in compliance with the License.         //
// You may obtain a copy of the License at                                  //
//                                                                          //
//     http://www.apache.org/licenses/LICENSE-2.0                           //
//                                                                          //
// Unless required by applicable law or agreed to in writing, software      //
// distributed under the License is distributed on an "AS IS" BASIS,        //
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. //
// See the License for the specific language governing permissions and      //
// limitations under the License.                                           //
// ======================================================================== //

#pragma once

#include "builders/heuristic_object_partition_new.h"
#include "builders/workstack.h"

#include "algorithms/parallel_create_tree.h"

namespace embree
{
  namespace isa
  {
    template<typename NodeRef>
      class __aligned(64) BuildRecord : public PrimInfo
    {
    public:
      __forceinline BuildRecord() {}
      
      __forceinline BuildRecord(const PrimInfo& pinfo, const size_t depth, NodeRef* parent) 
        : PrimInfo(pinfo), depth(depth), parent(parent), area(embree::area(pinfo.geomBounds)) {}
      
#if defined(_MSC_VER)
      __forceinline BuildRecord& operator=(const BuildRecord &arg) { 
        memcpy(this, &arg, sizeof(BuildRecord));    
        return *this;
      }
#endif

      __forceinline void init(size_t depth)
      {
        parent = NULL;
        this->depth = depth;
        area = embree::area(geomBounds);
      }
      
      __forceinline bool operator<(const BuildRecord &br) const { return size() < br.size(); } 
      __forceinline bool operator>(const BuildRecord &br) const { return size() > br.size(); } 
      
      struct Greater {
        __forceinline bool operator()(const BuildRecord& a, const BuildRecord& b) {
          return a.size() > b.size();
        }
      };

    public:
      unsigned depth;         //!< depth from the root of the tree
      float    area;          //!< surface area of bounding box
      NodeRef* parent;        //!< reference pointing to us
    };
    
    template<typename NodeRef, typename Allocator, typename CreateAllocFunc, typename CreateNodeFunc, typename CreateLeafFunc>
      class BVHBuilderSAH
    {
      static const size_t MAX_BRANCHING_FACTOR = 16;  //!< maximal supported BVH branching factor
      static const size_t MIN_LARGE_LEAF_LEVELS = 8;  //!< create balanced tree of we are that many levels before the maximal tree depth

    public:

      BVHBuilderSAH (CreateAllocFunc& createAlloc, CreateNodeFunc& createNode, CreateLeafFunc& createLeaf,
                         PrimRef* prims, const PrimInfo& pinfo,
                         const size_t branchingFactor, const size_t maxDepth, 
                         const size_t logBlockSize, const size_t minLeafSize, const size_t maxLeafSize)
        : createAlloc(createAlloc), createNode(createNode), createLeaf(createLeaf), 
          prims(prims), pinfo(pinfo), 
          branchingFactor(branchingFactor), maxDepth(maxDepth),
          logBlockSize(logBlockSize), minLeafSize(minLeafSize), maxLeafSize(maxLeafSize)
      {
        if (branchingFactor > MAX_BRANCHING_FACTOR)
          THROW_RUNTIME_ERROR("bvh4_builder: branching factor too large");
      }

      void splitFallback(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild)
      {
        const size_t center = (current.begin + current.end)/2;
        
        CentGeomBBox3fa left; left.reset();
        for (size_t i=current.begin; i<center; i++)
          left.extend(prims[i].bounds());
        new (&leftChild) PrimInfo(current.begin,center,left.geomBounds,left.centBounds);
        
        CentGeomBBox3fa right; right.reset();
        for (size_t i=center; i<current.end; i++)
          right.extend(prims[i].bounds());	
        new (&rightChild) PrimInfo(center,current.end,right.geomBounds,right.centBounds);
      }

      __forceinline void splitSequential(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild)
      {
        /* calculate binning function */
        PrimInfo pinfo(current.size(),current.geomBounds,current.centBounds);
        ObjectPartitionNew::Split split = ObjectPartitionNew::find(prims,current.begin,current.end,pinfo,logBlockSize);

        /* if we cannot find a valid split, enforce an arbitrary split */
        if (unlikely(!split.valid())) splitFallback(current,leftChild,rightChild);
        
        /* partitioning of items */
        else split.partition(prims, current.begin, current.end, leftChild, rightChild);
      }

      void splitParallel(const BuildRecord<NodeRef>& current, BuildRecord<NodeRef>& leftChild, BuildRecord<NodeRef>& rightChild, Allocator& alloc)
      {
        /* calculate binning function */
        PrimInfo pinfo(current.size(),current.geomBounds,current.centBounds);
        ObjectPartitionNew::Split split = ObjectPartitionNew::find_parallel(prims,current.begin,current.end,pinfo,logBlockSize);
        
        /* if we cannot find a valid split, enforce an arbitrary split */
        if (unlikely(!split.valid())) splitFallback(current,leftChild,rightChild);
        
        /* partitioning of items */
        else split.partition_parallel(prims, current.begin, current.end, leftChild, rightChild);
      }

      void createLargeLeaf(const BuildRecord<NodeRef>& current, Allocator& nodeAlloc, Allocator& leafAlloc)
      {
        if (current.depth > maxDepth) 
          THROW_RUNTIME_ERROR("depth limit reached");
        
        /* create leaf for few primitives */
        if (current.size() <= maxLeafSize) {
          createLeaf(current,prims,leafAlloc);
          return;
        }

        /* fill all children by always splitting the largest one */
        BuildRecord<NodeRef> children[MAX_BRANCHING_FACTOR];
        size_t numChildren = 1;
        children[0] = current;
        
        do {
          
          /* find best child with largest bounding box area */
          int bestChild = -1;
          int bestSize = 0;
          for (size_t i=0; i<numChildren; i++)
{'fraction_non_alphanumeric': 0.11704180064308682, 'fraction_numerical': 0.004715969989281886, 'mean_word_length': 2.2854460093896716, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3512341', 'n_tokens_mistral': 3730, 'n_tokens_neox': 3603, 'n_words': 958}