| 1 | // Created on: 2014-09-11 |
| 2 | // Created by: Danila ULYANOV |
| 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_LinearBuilder_Header |
| 17 | #define _BVH_LinearBuilder_Header |
| 18 | |
| 19 | #include <BVH_RadixSorter.hxx> |
| 20 | #include <Standard_Assert.hxx> |
| 21 | |
| 22 | //! Performs fast BVH construction using LBVH building approach. |
| 23 | //! Algorithm uses spatial Morton codes to reduce the BVH construction |
| 24 | //! problem to a sorting problem (radix sort -- O(N) complexity). This |
| 25 | //! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees |
| 26 | //! of lower quality compared to SAH-based BVH builders but it is over |
| 27 | //! an order of magnitude faster (up to 3M triangles per second). |
| 28 | //! |
| 29 | //! For more details see: |
| 30 | //! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha. |
| 31 | //! Fast BVH construction on GPUs. Eurographics, 2009. |
| 32 | template<class T, int N> |
| 33 | class BVH_LinearBuilder : public BVH_Builder<T, N> |
| 34 | { |
| 35 | public: |
| 36 | |
| 37 | typedef typename BVH::VectorType<T, N>::Type BVH_VecNt; |
| 38 | |
| 39 | public: |
| 40 | |
| 41 | //! Creates binned LBVH builder. |
| 42 | BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = BVH_Constants_LeafNodeSizeDefault, |
| 43 | const Standard_Integer theMaxTreeDepth = BVH_Constants_MaxTreeDepth); |
| 44 | |
| 45 | //! Releases resources of LBVH builder. |
| 46 | virtual ~BVH_LinearBuilder(); |
| 47 | |
| 48 | //! Builds BVH. |
| 49 | virtual void Build (BVH_Set<T, N>* theSet, |
| 50 | BVH_Tree<T, N>* theBVH, |
| 51 | const BVH_Box<T, N>& theBox) const Standard_OVERRIDE; |
| 52 | |
| 53 | protected: |
| 54 | |
| 55 | typedef NCollection_Array1<BVH_EncodedLink>::iterator LinkIterator; |
| 56 | |
| 57 | protected: |
| 58 | |
| 59 | //! Emits hierarchy from sorted Morton codes. |
| 60 | Standard_Integer emitHierachy (BVH_Tree<T, N>* theBVH, |
| 61 | const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks, |
| 62 | const Standard_Integer theBit, |
| 63 | const Standard_Integer theShift, |
| 64 | const Standard_Integer theStart, |
| 65 | const Standard_Integer theFinal) const; |
| 66 | |
| 67 | //! Returns index of the first element which does not compare less than the given one. |
| 68 | Standard_Integer lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks, |
| 69 | Standard_Integer theStart, |
| 70 | Standard_Integer theFinal, |
| 71 | Standard_Integer theDigit) const; |
| 72 | |
| 73 | }; |
| 74 | |
| 75 | // ======================================================================= |
| 76 | // function : BVH_LinearBuilder |
| 77 | // purpose : |
| 78 | // ======================================================================= |
| 79 | template<class T, int N> |
| 80 | BVH_LinearBuilder<T, N>::BVH_LinearBuilder (const Standard_Integer theLeafNodeSize, |
| 81 | const Standard_Integer theMaxTreeDepth) |
| 82 | : BVH_Builder<T, N> (theLeafNodeSize, |
| 83 | theMaxTreeDepth) |
| 84 | { |
| 85 | // |
| 86 | } |
| 87 | |
| 88 | // ======================================================================= |
| 89 | // function : ~BVH_LinearBuilder |
| 90 | // purpose : |
| 91 | // ======================================================================= |
| 92 | template<class T, int N> |
| 93 | BVH_LinearBuilder<T, N>::~BVH_LinearBuilder() |
| 94 | { |
| 95 | // |
| 96 | } |
| 97 | |
| 98 | // ======================================================================= |
| 99 | // function : lowerBound |
| 100 | // purpose : Returns index of first element greater than the given one |
| 101 | // ======================================================================= |
| 102 | template<class T, int N> |
| 103 | Standard_Integer BVH_LinearBuilder<T, N>::lowerBound (const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks, |
| 104 | Standard_Integer theStart, |
| 105 | Standard_Integer theFinal, |
| 106 | Standard_Integer theDigit) const |
| 107 | { |
| 108 | Standard_Integer aNbPrims = theFinal - theStart; |
| 109 | while (aNbPrims > 0) |
| 110 | { |
| 111 | const Standard_Integer aStep = aNbPrims / 2; |
| 112 | if (theEncodedLinks.Value (theStart + aStep).first & (1 << theDigit)) |
| 113 | { |
| 114 | aNbPrims = aStep; |
| 115 | } |
| 116 | else |
| 117 | { |
| 118 | theStart += aStep + 1; |
| 119 | aNbPrims -= aStep + 1; |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | return theStart; |
| 124 | } |
| 125 | |
| 126 | // ======================================================================= |
| 127 | // function : emitHierachy |
| 128 | // purpose : Emits hierarchy from sorted Morton codes |
| 129 | // ======================================================================= |
| 130 | template<class T, int N> |
| 131 | Standard_Integer BVH_LinearBuilder<T, N>::emitHierachy (BVH_Tree<T, N>* theBVH, |
| 132 | const NCollection_Array1<BVH_EncodedLink>& theEncodedLinks, |
| 133 | const Standard_Integer theBit, |
| 134 | const Standard_Integer theShift, |
| 135 | const Standard_Integer theStart, |
| 136 | const Standard_Integer theFinal) const |
| 137 | { |
| 138 | if (theFinal - theStart > BVH_Builder<T, N>::myLeafNodeSize) |
| 139 | { |
| 140 | const Standard_Integer aPosition = theBit < 0 ? |
| 141 | (theStart + theFinal) / 2 : lowerBound (theEncodedLinks, theStart, theFinal, theBit); |
| 142 | if (aPosition == theStart || aPosition == theFinal) |
| 143 | { |
| 144 | return emitHierachy (theBVH, theEncodedLinks, theBit - 1, theShift, theStart, theFinal); |
| 145 | } |
| 146 | |
| 147 | // Build inner node |
| 148 | const Standard_Integer aNode = theBVH->AddInnerNode (0, 0); |
| 149 | const Standard_Integer aRghNode = theShift + aPosition - theStart; |
| 150 | |
| 151 | const Standard_Integer aLftChild = emitHierachy (theBVH, theEncodedLinks, theBit - 1, theShift, theStart, aPosition); |
| 152 | const Standard_Integer aRghChild = emitHierachy (theBVH, theEncodedLinks, theBit - 1, aRghNode, aPosition, theFinal); |
| 153 | |
| 154 | theBVH->NodeInfoBuffer()[aNode].y() = aLftChild; |
| 155 | theBVH->NodeInfoBuffer()[aNode].z() = aRghChild; |
| 156 | return aNode; |
| 157 | } |
| 158 | else |
| 159 | { |
| 160 | // Build leaf node |
| 161 | return theBVH->AddLeafNode (theShift, theShift + theFinal - theStart - 1); |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | namespace BVH |
| 166 | { |
| 167 | //! Calculates bounding boxes (AABBs) for the given BVH tree. |
| 168 | template<class T, int N> |
| 169 | Standard_Integer UpdateBounds (BVH_Set<T, N>* theSet, BVH_Tree<T, N>* theTree, const Standard_Integer theNode = 0) |
| 170 | { |
| 171 | const BVH_Vec4i aData = theTree->NodeInfoBuffer()[theNode]; |
| 172 | if (aData.x() == 0) |
| 173 | { |
| 174 | const Standard_Integer aLftChild = theTree->NodeInfoBuffer()[theNode].y(); |
| 175 | const Standard_Integer aRghChild = theTree->NodeInfoBuffer()[theNode].z(); |
| 176 | |
| 177 | const Standard_Integer aLftDepth = UpdateBounds (theSet, theTree, aLftChild); |
| 178 | const Standard_Integer aRghDepth = UpdateBounds (theSet, theTree, aRghChild); |
| 179 | |
| 180 | typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theTree->MinPointBuffer()[aLftChild]; |
| 181 | typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theTree->MaxPointBuffer()[aLftChild]; |
| 182 | typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theTree->MinPointBuffer()[aRghChild]; |
| 183 | typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theTree->MaxPointBuffer()[aRghChild]; |
| 184 | |
| 185 | BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint); |
| 186 | BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint); |
| 187 | |
| 188 | theTree->MinPointBuffer()[theNode] = aLftMinPoint; |
| 189 | theTree->MaxPointBuffer()[theNode] = aLftMaxPoint; |
| 190 | return Max (aLftDepth, aRghDepth) + 1; |
| 191 | } |
| 192 | else |
| 193 | { |
| 194 | typename BVH_Box<T, N>::BVH_VecNt& aMinPoint = theTree->MinPointBuffer()[theNode]; |
| 195 | typename BVH_Box<T, N>::BVH_VecNt& aMaxPoint = theTree->MaxPointBuffer()[theNode]; |
| 196 | for (Standard_Integer aPrimIdx = aData.y(); aPrimIdx <= aData.z(); ++aPrimIdx) |
| 197 | { |
| 198 | const BVH_Box<T, N> aBox = theSet->Box (aPrimIdx); |
| 199 | if (aPrimIdx == aData.y()) |
| 200 | { |
| 201 | aMinPoint = aBox.CornerMin(); |
| 202 | aMaxPoint = aBox.CornerMax(); |
| 203 | } |
| 204 | else |
| 205 | { |
| 206 | BVH::BoxMinMax<T, N>::CwiseMin (aMinPoint, aBox.CornerMin()); |
| 207 | BVH::BoxMinMax<T, N>::CwiseMax (aMaxPoint, aBox.CornerMax()); |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | return 0; |
| 212 | } |
| 213 | |
| 214 | template<class T, int N> |
| 215 | struct BoundData |
| 216 | { |
| 217 | BVH_Set <T, N>* mySet; //!< Set of geometric objects |
| 218 | BVH_Tree<T, N>* myBVH; //!< BVH tree built over the set |
| 219 | Standard_Integer myNode; //!< BVH node to update bounding box |
| 220 | Standard_Integer myLevel; //!< Level of the processed BVH node |
| 221 | Standard_Integer* myHeight; //!< Height of the processed BVH node |
| 222 | }; |
| 223 | |
| 224 | //! Task for parallel bounds updating. |
| 225 | template<class T, int N> |
| 226 | class UpdateBoundTask |
| 227 | { |
| 228 | public: |
| 229 | |
| 230 | UpdateBoundTask (const Standard_Boolean isParallel) |
| 231 | : myIsParallel (isParallel) |
| 232 | { |
| 233 | } |
| 234 | |
| 235 | //! Executes the task. |
| 236 | void operator()(const BoundData<T, N>& theData) const |
| 237 | { |
| 238 | if (theData.myBVH->IsOuter (theData.myNode) || theData.myLevel > 2) |
| 239 | { |
| 240 | *theData.myHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, theData.myNode); |
| 241 | } |
| 242 | else |
| 243 | { |
| 244 | Standard_Integer aLftHeight = 0; |
| 245 | Standard_Integer aRghHeight = 0; |
| 246 | |
| 247 | const Standard_Integer aLftChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].y(); |
| 248 | const Standard_Integer aRghChild = theData.myBVH->NodeInfoBuffer()[theData.myNode].z(); |
| 249 | |
| 250 | std::vector<BoundData<T, N> > aList; |
| 251 | aList.reserve (2); |
| 252 | if (!theData.myBVH->IsOuter (aLftChild)) |
| 253 | { |
| 254 | BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aLftChild, theData.myLevel + 1, &aLftHeight}; |
| 255 | aList.push_back (aBoundData); |
| 256 | } |
| 257 | else |
| 258 | { |
| 259 | aLftHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aLftChild); |
| 260 | } |
| 261 | |
| 262 | if (!theData.myBVH->IsOuter (aRghChild)) |
| 263 | { |
| 264 | BoundData<T, N> aBoundData = {theData.mySet, theData.myBVH, aRghChild, theData.myLevel + 1, &aRghHeight}; |
| 265 | aList.push_back (aBoundData); |
| 266 | } |
| 267 | else |
| 268 | { |
| 269 | aRghHeight = BVH::UpdateBounds (theData.mySet, theData.myBVH, aRghChild); |
| 270 | } |
| 271 | |
| 272 | if (!aList.empty()) |
| 273 | { |
| 274 | OSD_Parallel::ForEach (aList.begin (), aList.end (), UpdateBoundTask<T, N> (myIsParallel), !myIsParallel); |
| 275 | } |
| 276 | |
| 277 | typename BVH_Box<T, N>::BVH_VecNt aLftMinPoint = theData.myBVH->MinPointBuffer()[aLftChild]; |
| 278 | typename BVH_Box<T, N>::BVH_VecNt aLftMaxPoint = theData.myBVH->MaxPointBuffer()[aLftChild]; |
| 279 | typename BVH_Box<T, N>::BVH_VecNt aRghMinPoint = theData.myBVH->MinPointBuffer()[aRghChild]; |
| 280 | typename BVH_Box<T, N>::BVH_VecNt aRghMaxPoint = theData.myBVH->MaxPointBuffer()[aRghChild]; |
| 281 | |
| 282 | BVH::BoxMinMax<T, N>::CwiseMin (aLftMinPoint, aRghMinPoint); |
| 283 | BVH::BoxMinMax<T, N>::CwiseMax (aLftMaxPoint, aRghMaxPoint); |
| 284 | |
| 285 | theData.myBVH->MinPointBuffer()[theData.myNode] = aLftMinPoint; |
| 286 | theData.myBVH->MaxPointBuffer()[theData.myNode] = aLftMaxPoint; |
| 287 | |
| 288 | *theData.myHeight = Max (aLftHeight, aRghHeight) + 1; |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | private: |
| 293 | |
| 294 | Standard_Boolean myIsParallel; |
| 295 | }; |
| 296 | } |
| 297 | |
| 298 | // ======================================================================= |
| 299 | // function : Build |
| 300 | // purpose : |
| 301 | // ======================================================================= |
| 302 | template<class T, int N> |
| 303 | void BVH_LinearBuilder<T, N>::Build (BVH_Set<T, N>* theSet, |
| 304 | BVH_Tree<T, N>* theBVH, |
| 305 | const BVH_Box<T, N>& theBox) const |
| 306 | { |
| 307 | Standard_STATIC_ASSERT (N == 2 || N == 3 || N == 4); |
| 308 | const Standard_Integer aSetSize = theSet->Size(); |
| 309 | if (theBVH == NULL || aSetSize == 0) |
| 310 | { |
| 311 | return; |
| 312 | } |
| 313 | |
| 314 | theBVH->Clear(); |
| 315 | |
| 316 | // Step 0 -- Initialize parameter of virtual grid |
| 317 | BVH_RadixSorter<T, N> aRadixSorter (theBox); |
| 318 | aRadixSorter.SetParallel (this->IsParallel()); |
| 319 | |
| 320 | // Step 1 - Perform radix sorting of primitive set |
| 321 | aRadixSorter.Perform (theSet); |
| 322 | |
| 323 | // Step 2 -- Emitting BVH hierarchy from sorted Morton codes |
| 324 | emitHierachy (theBVH, aRadixSorter.EncodedLinks(), 29, 0, 0, theSet->Size()); |
| 325 | |
| 326 | // Step 3 -- Compute bounding boxes of BVH nodes |
| 327 | theBVH->MinPointBuffer().resize (theBVH->NodeInfoBuffer().size()); |
| 328 | theBVH->MaxPointBuffer().resize (theBVH->NodeInfoBuffer().size()); |
| 329 | |
| 330 | Standard_Integer aHeight = 0; |
| 331 | BVH::BoundData<T, N> aBoundData = { theSet, theBVH, 0, 0, &aHeight }; |
| 332 | BVH::UpdateBoundTask<T, N> aBoundTask (this->IsParallel()); |
| 333 | aBoundTask (aBoundData); |
| 334 | |
| 335 | BVH_Builder<T, N>::updateDepth (theBVH, aHeight); |
| 336 | } |
| 337 | |
| 338 | #endif // _BVH_LinearBuilder_Header |