1 // Created on: 2014-01-09 2 // Created by: Denis BOGOLEPOV 3 // Copyright (c) 2013-2014 OPEN CASCADE SAS 4 // 5 // This file is part of Open CASCADE Technology software library. 6 // 7 // This library is free software; you can redistribute it and/or modify it under 8 // the terms of the GNU Lesser General Public License version 2.1 as published 9 // by the Free Software Foundation, with special exception defined in the file 10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT 11 // distribution for complete text of the license and disclaimer of any warranty. 12 // 13 // Alternatively, this file may be used under the terms of Open CASCADE 14 // commercial license or contractual agreement. 15 16 #ifndef _BVH_SweepPlaneBuilder_Header 17 #define _BVH_SweepPlaneBuilder_Header 18 19 #include <BVH_QueueBuilder.hxx> 20 #include <BVH_QuickSorter.hxx> 21 #include <NCollection_Array1.hxx> 22 23 //! Performs building of BVH tree using sweep plane SAH algorithm. 24 template<class T, int N> 25 class BVH_SweepPlaneBuilder : public BVH_QueueBuilder<T, N> 26 { 27 public: 28 29 //! Creates sweep plane SAH BVH builder. BVH_SweepPlaneBuilder(const Standard_Integer theLeafNodeSize=BVH_Constants_LeafNodeSizeDefault,const Standard_Integer theMaxTreeDepth=BVH_Constants_MaxTreeDepth,const Standard_Integer theNumOfThreads=1)30 BVH_SweepPlaneBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault, 31 const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth, 32 const Standard_Integer theNumOfThreads = 1) 33 : BVH_QueueBuilder<T, N> (theLeafNodeSize, 34 theMaxTreeDepth, 35 theNumOfThreads) {} 36 37 //! Releases resources of sweep plane SAH BVH builder. ~BVH_SweepPlaneBuilder()38 virtual ~BVH_SweepPlaneBuilder() {} 39 40 protected: 41 42 //! Performs splitting of the given BVH node. buildNode(BVH_Set<T,N> * theSet,BVH_Tree<T,N> * theBVH,const Standard_Integer theNode) const43 typename BVH_QueueBuilder<T, N>::BVH_ChildNodes buildNode (BVH_Set<T, N>* theSet, 44 BVH_Tree<T, N>* theBVH, 45 const Standard_Integer theNode) const Standard_OVERRIDE 46 { 47 const Standard_Integer aNodeBegPrimitive = theBVH->BegPrimitive (theNode); 48 const Standard_Integer aNodeEndPrimitive = theBVH->EndPrimitive (theNode); 49 const Standard_Integer aNodeNbPrimitives = theBVH->NbPrimitives (theNode); 50 if (aNodeEndPrimitive - aNodeBegPrimitive < BVH_Builder<T, N>::myLeafNodeSize) 51 { 52 return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // node does not require partitioning 53 } 54 55 // Parameters for storing best split 56 Standard_Integer aMinSplitAxis = -1; 57 Standard_Integer aMinSplitIndex = 0; 58 59 NCollection_Array1<Standard_Real> aLftSet (0, aNodeNbPrimitives - 1); 60 NCollection_Array1<Standard_Real> aRghSet (0, aNodeNbPrimitives - 1); 61 Standard_Real aMinSplitCost = std::numeric_limits<Standard_Real>::max(); 62 63 // Find best split 64 for (Standard_Integer anAxis = 0; anAxis < (N < 4 ? N : 3); ++anAxis) 65 { 66 const T aNodeSize = BVH::VecComp<T, N>::Get (theBVH->MaxPoint (theNode), anAxis) - 67 BVH::VecComp<T, N>::Get (theBVH->MinPoint (theNode), anAxis); 68 if (aNodeSize <= BVH::THE_NODE_MIN_SIZE) 69 { 70 continue; 71 } 72 73 BVH_QuickSorter<T, N> (anAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive); 74 BVH_Box<T, N> aLftBox; 75 BVH_Box<T, N> aRghBox; 76 aLftSet.ChangeFirst() = std::numeric_limits<T>::max(); 77 aRghSet.ChangeFirst() = std::numeric_limits<T>::max(); 78 79 // Sweep from left 80 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) 81 { 82 aLftBox.Combine (theSet->Box (anIndex + aNodeBegPrimitive - 1)); 83 aLftSet (anIndex) = static_cast<Standard_Real> (aLftBox.Area()); 84 } 85 86 // Sweep from right 87 for (Standard_Integer anIndex = 1; anIndex < aNodeNbPrimitives; ++anIndex) 88 { 89 aRghBox.Combine (theSet->Box (aNodeEndPrimitive - anIndex + 1)); 90 aRghSet (anIndex) = static_cast<Standard_Real> (aRghBox.Area()); 91 } 92 93 // Find best split using simplified SAH 94 for (Standard_Integer aNbLft = 1, aNbRgh = aNodeNbPrimitives - 1; aNbLft < aNodeNbPrimitives; ++aNbLft, --aNbRgh) 95 { 96 Standard_Real aCost = (aLftSet (aNbLft) /* / aNodeArea */) * aNbLft + 97 (aRghSet (aNbRgh) /* / aNodeArea */) * aNbRgh; 98 if (aCost < aMinSplitCost) 99 { 100 aMinSplitCost = aCost; 101 aMinSplitAxis = anAxis; 102 aMinSplitIndex = aNbLft; 103 } 104 } 105 } 106 107 if (aMinSplitAxis == -1) 108 { 109 return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes(); // failed to find split axis 110 } 111 112 theBVH->SetInner (theNode); 113 if (aMinSplitAxis != (N < 4 ? N - 1 : 2)) 114 { 115 BVH_QuickSorter<T, N> (aMinSplitAxis).Perform (theSet, aNodeBegPrimitive, aNodeEndPrimitive); 116 } 117 118 BVH_Box<T, N> aMinSplitBoxLft; 119 BVH_Box<T, N> aMinSplitBoxRgh; 120 121 // Compute bounding boxes for selected split plane 122 for (Standard_Integer anIndex = aNodeBegPrimitive; anIndex < aMinSplitIndex + aNodeBegPrimitive; ++anIndex) 123 { 124 aMinSplitBoxLft.Combine (theSet->Box (anIndex)); 125 } 126 127 for (Standard_Integer anIndex = aNodeEndPrimitive; anIndex >= aMinSplitIndex + aNodeBegPrimitive; --anIndex) 128 { 129 aMinSplitBoxRgh.Combine (theSet->Box (anIndex)); 130 } 131 132 const Standard_Integer aMiddle = aNodeBegPrimitive + aMinSplitIndex; 133 typedef typename BVH_QueueBuilder<T, N>::BVH_PrimitiveRange Range; 134 return typename BVH_QueueBuilder<T, N>::BVH_ChildNodes (aMinSplitBoxLft, 135 aMinSplitBoxRgh, 136 Range (aNodeBegPrimitive, aMiddle - 1), 137 Range (aMiddle, aNodeEndPrimitive)); 138 } 139 140 }; 141 142 #endif // _BVH_SweepPlaneBuilder_Header 143