1 // Copyright Contributors to the OpenVDB Project 2 // SPDX-License-Identifier: MPL-2.0 3 4 /// @file LeafManager.h 5 /// 6 /// @brief A LeafManager manages a linear array of pointers to a given tree's 7 /// leaf nodes, as well as optional auxiliary buffers (one or more per leaf) 8 /// that can be swapped with the leaf nodes' voxel data buffers. 9 /// @details The leaf array is useful for multithreaded computations over 10 /// leaf voxels in a tree with static topology but varying voxel values. 11 /// The auxiliary buffers are convenient for temporal integration. 12 /// Efficient methods are provided for multithreaded swapping and synching 13 /// (i.e., copying the contents) of these buffers. 14 15 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 16 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 17 18 #include <openvdb/Types.h> 19 #include <openvdb/tree/RootNode.h> // for NodeChain 20 #include <tbb/blocked_range.h> 21 #include <tbb/parallel_for.h> 22 #include <tbb/parallel_reduce.h> 23 #include <deque> 24 #include <functional> 25 #include <type_traits> 26 27 28 namespace openvdb { 29 OPENVDB_USE_VERSION_NAMESPACE 30 namespace OPENVDB_VERSION_NAME { 31 namespace tree { 32 33 namespace leafmgr { 34 35 //@{ 36 /// Useful traits for Tree types 37 template<typename TreeT> struct TreeTraits { 38 static const bool IsConstTree = false; 39 using LeafIterType = typename TreeT::LeafIter; 40 }; 41 template<typename TreeT> struct TreeTraits<const TreeT> { 42 static const bool IsConstTree = true; 43 using LeafIterType = typename TreeT::LeafCIter; 44 }; 45 //@} 46 47 } // namespace leafmgr 48 49 50 /// This helper class implements LeafManager methods that need to be 51 /// specialized for const vs. non-const trees. 52 template<typename ManagerT> 53 struct LeafManagerImpl 54 { 55 using RangeT = typename ManagerT::RangeType; 56 using LeafT = typename ManagerT::LeafType; 57 using BufT = typename ManagerT::BufferType; 58 59 static inline void doSwapLeafBuffer(const RangeT& r, size_t auxBufferIdx, 60 LeafT** leafs, BufT* bufs, size_t bufsPerLeaf) 61 { 62 for (size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) { 63 leafs[n]->swap(bufs[n * N + auxBufferIdx]); 64 } 65 } 66 }; 67 68 69 //////////////////////////////////////// 70 71 72 /// @brief This class manages a linear array of pointers to a given tree's 73 /// leaf nodes, as well as optional auxiliary buffers (one or more per leaf) 74 /// that can be swapped with the leaf nodes' voxel data buffers. 75 /// @details The leaf array is useful for multithreaded computations over 76 /// leaf voxels in a tree with static topology but varying voxel values. 77 /// The auxiliary buffers are convenient for temporal integration. 78 /// Efficient methods are provided for multithreaded swapping and sync'ing 79 /// (i.e., copying the contents) of these buffers. 80 /// 81 /// @note Buffer index 0 denotes a leaf node's internal voxel data buffer. 82 /// Any auxiliary buffers are indexed starting from one. 83 template<typename TreeT> 84 class LeafManager 85 { 86 public: 87 using TreeType = TreeT; 88 using ValueType = typename TreeT::ValueType; 89 using RootNodeType = typename TreeT::RootNodeType; 90 using NonConstLeafType = typename TreeType::LeafNodeType; 91 using LeafType = typename CopyConstness<TreeType, NonConstLeafType>::Type; 92 using LeafNodeType = LeafType; 93 using LeafIterType = typename leafmgr::TreeTraits<TreeT>::LeafIterType; 94 using NonConstBufferType = typename LeafType::Buffer; 95 using BufferType = typename CopyConstness<TreeType, NonConstBufferType>::Type; 96 using RangeType = tbb::blocked_range<size_t>; // leaf index range 97 static const Index DEPTH = 2; // root + leaf nodes 98 99 static const bool IsConstTree = leafmgr::TreeTraits<TreeT>::IsConstTree; 100 101 class LeafRange 102 { 103 public: 104 class Iterator 105 { 106 public: 107 Iterator(const LeafRange& range, size_t pos): mRange(range), mPos(pos) 108 { 109 assert(this->isValid()); 110 } 111 Iterator(const Iterator&) = default; 112 Iterator& operator=(const Iterator&) = default; 113 /// Advance to the next leaf node. 114 Iterator& operator++() { ++mPos; return *this; } 115 /// Return a reference to the leaf node to which this iterator is pointing. 116 LeafType& operator*() const { return mRange.mLeafManager.leaf(mPos); } 117 /// Return a pointer to the leaf node to which this iterator is pointing. 118 LeafType* operator->() const { return &(this->operator*()); } 119 /// @brief Return the nth buffer for the leaf node to which this iterator is pointing, 120 /// where n = @a bufferIdx and n = 0 corresponds to the leaf node's own buffer. 121 BufferType& buffer(size_t bufferIdx) 122 { 123 return mRange.mLeafManager.getBuffer(mPos, bufferIdx); 124 } 125 /// Return the index into the leaf array of the current leaf node. 126 size_t pos() const { return mPos; } 127 /// Return @c true if the position of this iterator is in a valid range. 128 bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; } 129 /// Return @c true if this iterator is not yet exhausted. 130 bool test() const { return mPos < mRange.mEnd; } 131 /// Return @c true if this iterator is not yet exhausted. 132 operator bool() const { return this->test(); } 133 /// Return @c true if this iterator is exhausted. 134 bool empty() const { return !this->test(); } 135 bool operator!=(const Iterator& other) const 136 { 137 return (mPos != other.mPos) || (&mRange != &other.mRange); 138 } 139 bool operator==(const Iterator& other) const { return !(*this != other); } 140 const LeafRange& leafRange() const { return mRange; } 141 142 private: 143 const LeafRange& mRange; 144 size_t mPos; 145 };// end Iterator 146 147 LeafRange(size_t begin, size_t end, const LeafManager& leafManager, size_t grainSize=1) 148 : mEnd(end) 149 , mBegin(begin) 150 , mGrainSize(grainSize) 151 , mLeafManager(leafManager) 152 { 153 } 154 155 Iterator begin() const {return Iterator(*this, mBegin);} 156 157 Iterator end() const {return Iterator(*this, mEnd);} 158 159 size_t size() const { return mEnd - mBegin; } 160 161 size_t grainsize() const { return mGrainSize; } 162 163 const LeafManager& leafManager() const { return mLeafManager; } 164 165 bool empty() const {return !(mBegin < mEnd);} 166 167 bool is_divisible() const {return mGrainSize < this->size();} 168 169 LeafRange(LeafRange& r, tbb::split) 170 : mEnd(r.mEnd) 171 , mBegin(doSplit(r)) 172 , mGrainSize(r.mGrainSize) 173 , mLeafManager(r.mLeafManager) 174 { 175 } 176 177 private: 178 size_t mEnd, mBegin, mGrainSize; 179 const LeafManager& mLeafManager; 180 181 static size_t doSplit(LeafRange& r) 182 { 183 assert(r.is_divisible()); 184 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u; 185 r.mEnd = middle; 186 return middle; 187 } 188 };// end of LeafRange 189 190 /// @brief Constructor from a tree reference and an auxiliary buffer count 191 /// @note The default is no auxiliary buffers 192 LeafManager(TreeType& tree, size_t auxBuffersPerLeaf=0, bool serial=false) 193 : mTree(&tree) 194 , mLeafCount(0) 195 , mAuxBufferCount(0) 196 , mAuxBuffersPerLeaf(auxBuffersPerLeaf) 197 { 198 this->rebuild(serial); 199 } 200 201 /// @brief Construct directly from an existing array of leafnodes. 202 /// @warning The leafnodes are implicitly assumed to exist in the 203 /// input @a tree. 204 LeafManager(TreeType& tree, LeafType** begin, LeafType** end, 205 size_t auxBuffersPerLeaf=0, bool serial=false) 206 : mTree(&tree) 207 , mLeafCount(end-begin) 208 , mAuxBufferCount(0) 209 , mAuxBuffersPerLeaf(auxBuffersPerLeaf) 210 , mLeafPtrs(new LeafType*[mLeafCount]) 211 , mLeafs(mLeafPtrs.get()) 212 { 213 size_t n = mLeafCount; 214 LeafType **target = mLeafs, **source = begin; 215 while (n--) *target++ = *source++; 216 if (auxBuffersPerLeaf) this->initAuxBuffers(serial); 217 } 218 219 /// Shallow copy constructor called by tbb::parallel_for() threads 220 /// 221 /// @note This should never get called directly 222 LeafManager(const LeafManager& other) 223 : mTree(other.mTree) 224 , mLeafCount(other.mLeafCount) 225 , mAuxBufferCount(other.mAuxBufferCount) 226 , mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf) 227 , mLeafs(other.mLeafs) 228 , mAuxBuffers(other.mAuxBuffers) 229 , mTask(other.mTask) 230 { 231 } 232 233 /// @brief (Re)initialize by resizing (if necessary) and repopulating the leaf array 234 /// and by deleting existing auxiliary buffers and allocating new ones. 235 /// @details Call this method if the tree's topology, and therefore the number 236 /// of leaf nodes, changes. New auxiliary buffers are initialized with copies 237 /// of corresponding leaf node buffers. 238 void rebuild(bool serial=false) 239 { 240 this->initLeafArray(serial); 241 this->initAuxBuffers(serial); 242 } 243 //@{ 244 /// Repopulate the leaf array and delete and reallocate auxiliary buffers. 245 void rebuild(size_t auxBuffersPerLeaf, bool serial=false) 246 { 247 mAuxBuffersPerLeaf = auxBuffersPerLeaf; 248 this->rebuild(serial); 249 } 250 void rebuild(TreeType& tree, bool serial=false) 251 { 252 mTree = &tree; 253 this->rebuild(serial); 254 } 255 void rebuild(TreeType& tree, size_t auxBuffersPerLeaf, bool serial=false) 256 { 257 mTree = &tree; 258 mAuxBuffersPerLeaf = auxBuffersPerLeaf; 259 this->rebuild(serial); 260 } 261 //@} 262 /// @brief Change the number of auxiliary buffers. 263 /// @details If auxBuffersPerLeaf is 0, all existing auxiliary buffers are deleted. 264 /// New auxiliary buffers are initialized with copies of corresponding leaf node buffers. 265 /// This method does not rebuild the leaf array. 266 void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false) 267 { 268 mAuxBuffersPerLeaf = auxBuffersPerLeaf; 269 this->initAuxBuffers(serial); 270 } 271 /// @brief Remove the auxiliary buffers, but don't rebuild the leaf array. 272 void removeAuxBuffers() { this->rebuildAuxBuffers(0); } 273 274 /// @brief Remove the auxiliary buffers and rebuild the leaf array. 275 void rebuildLeafArray(bool serial = false) 276 { 277 this->removeAuxBuffers(); 278 this->initLeafArray(serial); 279 } 280 281 /// @brief Return the total number of allocated auxiliary buffers. 282 size_t auxBufferCount() const { return mAuxBufferCount; } 283 /// @brief Return the number of auxiliary buffers per leaf node. 284 size_t auxBuffersPerLeaf() const { return mAuxBuffersPerLeaf; } 285 286 /// @brief Return the number of leaf nodes. 287 size_t leafCount() const { return mLeafCount; } 288 289 /// @brief Return the number of active voxels in the leaf nodes. 290 /// @note Multi-threaded for better performance than Tree::activeLeafVoxelCount 291 Index64 activeLeafVoxelCount() const 292 { 293 return tbb::parallel_reduce(this->leafRange(), Index64(0), 294 [] (const LeafRange& range, Index64 sum) -> Index64 { 295 for (const auto& leaf: range) { sum += leaf.onVoxelCount(); } 296 return sum; 297 }, 298 [] (Index64 n, Index64 m) -> Index64 { return n + m; }); 299 } 300 301 /// Return a const reference to tree associated with this manager. 302 const TreeType& tree() const { return *mTree; } 303 304 /// Return a reference to the tree associated with this manager. 305 TreeType& tree() { return *mTree; } 306 307 /// Return a const reference to root node associated with this manager. 308 const RootNodeType& root() const { return mTree->root(); } 309 310 /// Return a reference to the root node associated with this manager. 311 RootNodeType& root() { return mTree->root(); } 312 313 /// Return @c true if the tree associated with this manager is immutable. 314 bool isConstTree() const { return this->IsConstTree; } 315 316 /// @brief Return a pointer to the leaf node at index @a leafIdx in the array. 317 /// @note For performance reasons no range check is performed (other than an assertion)! 318 LeafType& leaf(size_t leafIdx) const { assert(leafIdx<mLeafCount); return *mLeafs[leafIdx]; } 319 320 /// @brief Return the leaf or auxiliary buffer for the leaf node at index @a leafIdx. 321 /// If @a bufferIdx is zero, return the leaf buffer, otherwise return the nth 322 /// auxiliary buffer, where n = @a bufferIdx - 1. 323 /// 324 /// @note For performance reasons no range checks are performed on the inputs 325 /// (other than assertions)! Since auxiliary buffers, unlike leaf buffers, 326 /// might not exist, be especially careful when specifying the @a bufferIdx. 327 /// @note For const trees, this method always returns a reference to a const buffer. 328 /// It is safe to @c const_cast and modify any auxiliary buffer (@a bufferIdx > 0), 329 /// but it is not safe to modify the leaf buffer (@a bufferIdx = 0). 330 BufferType& getBuffer(size_t leafIdx, size_t bufferIdx) const 331 { 332 assert(leafIdx < mLeafCount); 333 assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf); 334 return bufferIdx == 0 ? mLeafs[leafIdx]->buffer() 335 : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1]; 336 } 337 338 /// @brief Return a @c tbb::blocked_range of leaf array indices. 339 /// 340 /// @note Consider using leafRange() instead, which provides access methods 341 /// to leaf nodes and buffers. 342 RangeType getRange(size_t grainsize = 1) const { return RangeType(0, mLeafCount, grainsize); } 343 344 /// Return a TBB-compatible LeafRange. 345 LeafRange leafRange(size_t grainsize = 1) const 346 { 347 return LeafRange(0, mLeafCount, *this, grainsize); 348 } 349 350 /// @brief Swap each leaf node's buffer with the nth corresponding auxiliary buffer, 351 /// where n = @a bufferIdx. 352 /// @return @c true if the swap was successful 353 /// @param bufferIdx index of the buffer that will be swapped with 354 /// the corresponding leaf node buffer 355 /// @param serial if false, swap buffers in parallel using multiple threads. 356 /// @note Recall that the indexing of auxiliary buffers is 1-based, since 357 /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes 358 /// the first auxiliary buffer. 359 bool swapLeafBuffer(size_t bufferIdx, bool serial = false) 360 { 361 namespace ph = std::placeholders; 362 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree()) return false; 363 mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, bufferIdx - 1); 364 this->cook(serial ? 0 : 512); 365 return true;//success 366 } 367 /// @brief Swap any two buffers for each leaf node. 368 /// @note Recall that the indexing of auxiliary buffers is 1-based, since 369 /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes 370 /// the first auxiliary buffer. 371 bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial = false) 372 { 373 namespace ph = std::placeholders; 374 const size_t b1 = std::min(bufferIdx1, bufferIdx2); 375 const size_t b2 = std::max(bufferIdx1, bufferIdx2); 376 if (b1 == b2 || b2 > mAuxBuffersPerLeaf) return false; 377 if (b1 == 0) { 378 if (this->isConstTree()) return false; 379 mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, b2-1); 380 } else { 381 mTask = std::bind(&LeafManager::doSwapAuxBuffer, ph::_1, ph::_2, b1-1, b2-1); 382 } 383 this->cook(serial ? 0 : 512); 384 return true;//success 385 } 386 387 /// @brief Sync up the specified auxiliary buffer with the corresponding leaf node buffer. 388 /// @return @c true if the sync was successful 389 /// @param bufferIdx index of the buffer that will contain a 390 /// copy of the corresponding leaf node buffer 391 /// @param serial if false, sync buffers in parallel using multiple threads. 392 /// @note Recall that the indexing of auxiliary buffers is 1-based, since 393 /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes 394 /// the first auxiliary buffer. 395 bool syncAuxBuffer(size_t bufferIdx, bool serial = false) 396 { 397 namespace ph = std::placeholders; 398 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf) return false; 399 mTask = std::bind(&LeafManager::doSyncAuxBuffer, ph::_1, ph::_2, bufferIdx - 1); 400 this->cook(serial ? 0 : 64); 401 return true;//success 402 } 403 404 /// @brief Sync up all auxiliary buffers with their corresponding leaf node buffers. 405 /// @return true if the sync was successful 406 /// @param serial if false, sync buffers in parallel using multiple threads. 407 bool syncAllBuffers(bool serial = false) 408 { 409 namespace ph = std::placeholders; 410 switch (mAuxBuffersPerLeaf) { 411 case 0: return false;//nothing to do 412 case 1: mTask = std::bind(&LeafManager::doSyncAllBuffers1, ph::_1, ph::_2); break; 413 case 2: mTask = std::bind(&LeafManager::doSyncAllBuffers2, ph::_1, ph::_2); break; 414 default: mTask = std::bind(&LeafManager::doSyncAllBuffersN, ph::_1, ph::_2); break; 415 } 416 this->cook(serial ? 0 : 64); 417 return true;//success 418 } 419 420 /// @brief Threaded method that applies a user-supplied functor 421 /// to each leaf node in the LeafManager. 422 /// 423 /// @details The user-supplied functor needs to define the methods 424 /// required for tbb::parallel_for. 425 /// 426 /// @param op user-supplied functor, see examples for interface details. 427 /// @param threaded optional toggle to disable threading, on by default. 428 /// @param grainSize optional parameter to specify the grainsize 429 /// for threading, one by default. 430 /// 431 /// @warning The functor object is deep-copied to create TBB tasks. 432 /// This allows the function to use non-thread-safe members 433 /// like a ValueAccessor. 434 /// 435 /// @par Example: 436 /// @code 437 /// // Functor to offset a tree's voxel values with values from another tree. 438 /// template<typename TreeType> 439 /// struct OffsetOp 440 /// { 441 /// using Accessor = tree::ValueAccessor<const TreeType>; 442 /// 443 /// OffsetOp(const TreeType& tree): mRhsTreeAcc(tree) {} 444 /// 445 /// template <typename LeafNodeType> 446 /// void operator()(LeafNodeType &lhsLeaf, size_t) const 447 /// { 448 /// const LeafNodeType *rhsLeaf = mRhsTreeAcc.probeConstLeaf(lhsLeaf.origin()); 449 /// if (rhsLeaf) { 450 /// typename LeafNodeType::ValueOnIter iter = lhsLeaf.beginValueOn(); 451 /// for (; iter; ++iter) { 452 /// iter.setValue(iter.getValue() + rhsLeaf->getValue(iter.pos())); 453 /// } 454 /// } 455 /// } 456 /// Accessor mRhsTreeAcc; 457 /// }; 458 /// 459 /// // usage: 460 /// tree::LeafManager<FloatTree> leafNodes(lhsTree); 461 /// leafNodes.foreach(OffsetOp<FloatTree>(rhsTree)); 462 /// 463 /// // A functor that performs a min operation between different auxiliary buffers. 464 /// template<typename LeafManagerType> 465 /// struct MinOp 466 /// { 467 /// using BufferType = typename LeafManagerType::BufferType; 468 /// 469 /// MinOp(LeafManagerType& leafNodes): mLeafs(leafNodes) {} 470 /// 471 /// template <typename LeafNodeType> 472 /// void operator()(LeafNodeType &leaf, size_t leafIndex) const 473 /// { 474 /// // get the first buffer 475 /// BufferType& buffer = mLeafs.getBuffer(leafIndex, 1); 476 /// 477 /// // min ... 478 /// } 479 /// LeafManagerType& mLeafs; 480 /// }; 481 /// @endcode 482 template<typename LeafOp> 483 void foreach(const LeafOp& op, bool threaded = true, size_t grainSize=1) 484 { 485 LeafTransformer<LeafOp> transform(op); 486 transform.run(this->leafRange(grainSize), threaded); 487 } 488 489 /// @brief Threaded method that applies a user-supplied functor 490 /// to each leaf node in the LeafManager. Unlike foreach 491 /// (defined above) this method performs a reduction on 492 /// all the leaf nodes. 493 /// 494 /// @details The user-supplied functor needs to define the methods 495 /// required for tbb::parallel_reduce. 496 /// 497 /// @param op user-supplied functor, see examples for interface details. 498 /// @param threaded optional toggle to disable threading, on by default. 499 /// @param grainSize optional parameter to specify the grainsize 500 /// for threading, one by default. 501 /// 502 /// @warning The functor object is deep-copied to create TBB tasks. 503 /// This allows the function to use non-thread-safe members 504 /// like a ValueAccessor. 505 /// 506 /// @par Example: 507 /// @code 508 /// // Functor to count the number of negative (active) leaf values 509 /// struct CountOp 510 /// { 511 /// CountOp() : mCounter(0) {} 512 /// CountOp(const CountOp &other) : mCounter(other.mCounter) {} 513 /// CountOp(const CountOp &other, tbb::split) : mCounter(0) {} 514 /// template <typename LeafNodeType> 515 /// void operator()(LeafNodeType &leaf, size_t) 516 /// { 517 /// typename LeafNodeType::ValueOnIter iter = leaf.beginValueOn(); 518 /// for (; iter; ++iter) if (*iter < 0.0f) ++mCounter; 519 /// } 520 /// void join(const CountOp &other) {mCounter += other.mCounter;} 521 /// size_t mCounter; 522 /// }; 523 /// 524 /// // usage: 525 /// tree::LeafManager<FloatTree> leafNodes(tree); 526 /// MinValueOp min; 527 /// leafNodes.reduce(min); 528 /// std::cerr << "Number of negative active voxels = " << min.mCounter << std::endl; 529 /// 530 /// @endcode 531 template<typename LeafOp> 532 void reduce(LeafOp& op, bool threaded = true, size_t grainSize=1) 533 { 534 LeafReducer<LeafOp> transform(op); 535 transform.run(this->leafRange(grainSize), threaded); 536 } 537 538 template<typename ArrayT> 539 OPENVDB_DEPRECATED_MESSAGE("Use Tree::getNodes()") void getNodes(ArrayT& array) 540 { 541 using T = typename ArrayT::value_type; 542 static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array"); 543 using LeafT = typename std::conditional<std::is_const< 544 typename std::remove_pointer<T>::type>::value, const LeafType, LeafType>::type; 545 546 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 547 if (std::is_same<T, LeafT*>::value) { 548 array.resize(mLeafCount); 549 for (size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]); 550 } else { 551 mTree->getNodes(array); 552 } 553 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 554 } 555 556 template<typename ArrayT> 557 OPENVDB_DEPRECATED_MESSAGE("Use Tree::getNodes()") void getNodes(ArrayT& array) const 558 { 559 using T = typename ArrayT::value_type; 560 static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array"); 561 static_assert(std::is_const<typename std::remove_pointer<T>::type>::value, 562 "argument to getNodes() must be an array of const node pointers"); 563 564 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 565 if (std::is_same<T, const LeafType*>::value) { 566 array.resize(mLeafCount); 567 for (size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]); 568 } else { 569 mTree->getNodes(array); 570 } 571 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 572 } 573 574 /// @brief Generate a linear array of prefix sums of offsets into the 575 /// active voxels in the leafs. So @a offsets[n]+m is the offset to the 576 /// mth active voxel in the nth leaf node (useful for 577 /// user-managed value buffers, e.g. in tools/LevelSetAdvect.h). 578 /// @return The total number of active values in the leaf nodes 579 /// @param offsets array of prefix sums of offsets to active voxels 580 /// @param size on input, the size of @a offsets; on output, its new size 581 /// @param grainSize optional grain size for threading 582 /// @details If @a offsets is @c nullptr or @a size is smaller than the 583 /// total number of active voxels (the return value) then @a offsets 584 /// is reallocated and @a size equals the total number of active voxels. 585 size_t getPrefixSum(size_t*& offsets, size_t& size, size_t grainSize=1) const 586 { 587 if (offsets == nullptr || size < mLeafCount) { 588 delete [] offsets; 589 offsets = new size_t[mLeafCount]; 590 size = mLeafCount; 591 } 592 size_t prefix = 0; 593 if ( grainSize > 0 ) { 594 PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix); 595 } else {// serial 596 for (size_t i=0; i<mLeafCount; ++i) { 597 offsets[i] = prefix; 598 prefix += mLeafs[i]->onVoxelCount(); 599 } 600 } 601 return prefix; 602 } 603 604 //////////////////////////////////////////////////////////////////////////////////// 605 // All methods below are for internal use only and should never be called directly 606 607 /// Used internally by tbb::parallel_for() - never call it directly! 608 void operator()(const RangeType& r) const 609 { 610 if (mTask) mTask(const_cast<LeafManager*>(this), r); 611 else OPENVDB_THROW(ValueError, "task is undefined"); 612 } 613 614 private: 615 616 void initLeafArray(bool serial = false) 617 { 618 // Build an array of all nodes that have leaf nodes as their immediate children 619 620 using NodeChainT = typename NodeChain<RootNodeType, RootNodeType::LEVEL>::Type; 621 using NonConstLeafParentT = typename NodeChainT::template Get</*Level=*/1>; 622 using LeafParentT = typename CopyConstness<TreeType, NonConstLeafParentT>::Type; 623 624 std::deque<LeafParentT*> leafParents; 625 mTree->getNodes(leafParents); 626 627 // Compute the leaf counts for each node 628 629 std::vector<Index32> leafCounts; 630 if (serial) { 631 leafCounts.reserve(leafParents.size()); 632 for (LeafParentT* leafParent : leafParents) { 633 leafCounts.push_back(leafParent->childCount()); 634 } 635 } else { 636 leafCounts.resize(leafParents.size()); 637 tbb::parallel_for( 638 // with typical node sizes and SSE enabled, there are only a handful 639 // of instructions executed per-operation with a default grainsize 640 // of 1, so increase to 64 to reduce parallel scheduling overhead 641 tbb::blocked_range<size_t>(0, leafParents.size(), /*grainsize=*/64), 642 [&](tbb::blocked_range<size_t>& range) 643 { 644 for (size_t i = range.begin(); i < range.end(); i++) { 645 leafCounts[i] = leafParents[i]->childCount(); 646 } 647 } 648 ); 649 } 650 651 // Turn leaf counts into a cumulative histogram and obtain total leaf count 652 653 for (size_t i = 1; i < leafCounts.size(); i++) { 654 leafCounts[i] += leafCounts[i-1]; 655 } 656 657 const size_t leafCount = leafCounts.empty() ? 0 : leafCounts.back(); 658 659 // Allocate (or deallocate) the leaf pointer array 660 661 if (leafCount != mLeafCount) { 662 if (leafCount > 0) { 663 mLeafPtrs.reset(new LeafType*[leafCount]); 664 mLeafs = mLeafPtrs.get(); 665 } else { 666 mLeafPtrs.reset(); 667 mLeafs = nullptr; 668 } 669 mLeafCount = leafCount; 670 } 671 672 if (mLeafCount == 0) return; 673 674 // Populate the leaf node pointers 675 676 if (serial) { 677 LeafType** leafPtr = mLeafs; 678 for (LeafParentT* leafParent : leafParents) { 679 for (auto iter = leafParent->beginChildOn(); iter; ++iter) { 680 *leafPtr++ = &iter.getValue(); 681 } 682 } 683 } else { 684 tbb::parallel_for( 685 tbb::blocked_range<size_t>(0, leafParents.size()), 686 [&](tbb::blocked_range<size_t>& range) 687 { 688 size_t i = range.begin(); 689 LeafType** leafPtr = mLeafs; 690 if (i > 0) leafPtr += leafCounts[i-1]; 691 for ( ; i < range.end(); i++) { 692 for (auto iter = leafParents[i]->beginChildOn(); iter; ++iter) { 693 *leafPtr++ = &iter.getValue(); 694 } 695 } 696 } 697 ); 698 } 699 } 700 701 void initAuxBuffers(bool serial) 702 { 703 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf; 704 if (auxBufferCount != mAuxBufferCount) { 705 if (auxBufferCount > 0) { 706 mAuxBufferPtrs.reset(new NonConstBufferType[auxBufferCount]); 707 mAuxBuffers = mAuxBufferPtrs.get(); 708 } else { 709 mAuxBufferPtrs.reset(); 710 mAuxBuffers = nullptr; 711 } 712 mAuxBufferCount = auxBufferCount; 713 } 714 this->syncAllBuffers(serial); 715 } 716 717 void cook(size_t grainsize) 718 { 719 if (grainsize>0) { 720 tbb::parallel_for(this->getRange(grainsize), *this); 721 } else { 722 (*this)(this->getRange()); 723 } 724 } 725 726 void doSwapLeafBuffer(const RangeType& r, size_t auxBufferIdx) 727 { 728 LeafManagerImpl<LeafManager>::doSwapLeafBuffer( 729 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf); 730 } 731 732 void doSwapAuxBuffer(const RangeType& r, size_t auxBufferIdx1, size_t auxBufferIdx2) 733 { 734 for (size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) { 735 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]); 736 } 737 } 738 739 void doSyncAuxBuffer(const RangeType& r, size_t auxBufferIdx) 740 { 741 for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) { 742 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer(); 743 } 744 } 745 746 void doSyncAllBuffers1(const RangeType& r) 747 { 748 for (size_t n = r.begin(), m = r.end(); n != m; ++n) { 749 mAuxBuffers[n] = mLeafs[n]->buffer(); 750 } 751 } 752 753 void doSyncAllBuffers2(const RangeType& r) 754 { 755 for (size_t n = r.begin(), m = r.end(); n != m; ++n) { 756 const BufferType& leafBuffer = mLeafs[n]->buffer(); 757 mAuxBuffers[2*n ] = leafBuffer; 758 mAuxBuffers[2*n+1] = leafBuffer; 759 } 760 } 761 762 void doSyncAllBuffersN(const RangeType& r) 763 { 764 for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) { 765 const BufferType& leafBuffer = mLeafs[n]->buffer(); 766 for (size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer; 767 } 768 } 769 770 /// @brief Private member class that applies a user-defined 771 /// functor to perform parallel_for on all the leaf nodes. 772 template<typename LeafOp> 773 struct LeafTransformer 774 { 775 LeafTransformer(const LeafOp &leafOp) : mLeafOp(leafOp) 776 { 777 } 778 void run(const LeafRange &range, bool threaded) const 779 { 780 threaded ? tbb::parallel_for(range, *this) : (*this)(range); 781 } 782 void operator()(const LeafRange &range) const 783 { 784 for (typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos()); 785 } 786 const LeafOp mLeafOp; 787 };// LeafTransformer 788 789 /// @brief Private member class that applies a user-defined 790 /// functor to perform parallel_reduce on all the leaf nodes. 791 template<typename LeafOp> 792 struct LeafReducer 793 { 794 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp) 795 { 796 } 797 LeafReducer(const LeafReducer &other, tbb::split) 798 : mLeafOpPtr(std::make_unique<LeafOp>(*(other.mLeafOp), tbb::split())) 799 , mLeafOp(mLeafOpPtr.get()) 800 { 801 } 802 void run(const LeafRange& range, bool threaded) 803 { 804 threaded ? tbb::parallel_reduce(range, *this) : (*this)(range); 805 } 806 void operator()(const LeafRange& range) 807 { 808 LeafOp &op = *mLeafOp;//local registry 809 for (typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos()); 810 } 811 void join(const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); } 812 std::unique_ptr<LeafOp> mLeafOpPtr; 813 LeafOp *mLeafOp = nullptr; 814 };// LeafReducer 815 816 // Helper class to compute a prefix sum of offsets to active voxels 817 struct PrefixSum 818 { 819 PrefixSum(const LeafRange& r, size_t* offsets, size_t& prefix) 820 : mOffsets(offsets) 821 { 822 tbb::parallel_for( r, *this); 823 for (size_t i=0, leafCount = r.size(); i<leafCount; ++i) { 824 size_t tmp = offsets[i]; 825 offsets[i] = prefix; 826 prefix += tmp; 827 } 828 } 829 inline void operator()(const LeafRange& r) const { 830 for (typename LeafRange::Iterator i = r.begin(); i; ++i) { 831 mOffsets[i.pos()] = i->onVoxelCount(); 832 } 833 } 834 size_t* mOffsets; 835 };// PrefixSum 836 837 using FuncType = typename std::function<void (LeafManager*, const RangeType&)>; 838 839 TreeType* mTree; 840 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf; 841 std::unique_ptr<LeafType*[]> mLeafPtrs; 842 LeafType** mLeafs = nullptr;//array of LeafNode pointers 843 std::unique_ptr<NonConstBufferType[]> mAuxBufferPtrs; 844 NonConstBufferType* mAuxBuffers = nullptr;//array of auxiliary buffers 845 FuncType mTask = nullptr; 846 };//end of LeafManager class 847 848 849 // Partial specializations of LeafManager methods for const trees 850 template<typename TreeT> 851 struct LeafManagerImpl<LeafManager<const TreeT> > 852 { 853 using ManagerT = LeafManager<const TreeT>; 854 using RangeT = typename ManagerT::RangeType; 855 using LeafT = typename ManagerT::LeafType; 856 using BufT = typename ManagerT::BufferType; 857 858 static inline void doSwapLeafBuffer(const RangeT&, size_t /*auxBufferIdx*/, 859 LeafT**, BufT*, size_t /*bufsPerLeaf*/) 860 { 861 // Buffers can't be swapped into const trees. 862 } 863 }; 864 865 } // namespace tree 866 } // namespace OPENVDB_VERSION_NAME 867 } // namespace openvdb 868 869 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 870