OpenVDB 10.0.1
Loading...
Searching...
No Matches
LeafManager.h
Go to the documentation of this file.
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 "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
28namespace openvdb {
30namespace OPENVDB_VERSION_NAME {
31namespace tree {
32
33namespace leafmgr {
34
35//@{
36/// Useful traits for Tree types
37template<typename TreeT> struct TreeTraits {
38 static const bool IsConstTree = false;
39 using LeafIterType = typename TreeT::LeafIter;
40};
41template<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.
52template<typename ManagerT>
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.
83template<typename TreeT>
85{
86public:
87 using TreeType = TreeT;
88 using ValueType = typename TreeT::ValueType;
89 using RootNodeType = typename TreeT::RootNodeType;
90 using NonConstLeafType = typename TreeType::LeafNodeType;
94 using NonConstBufferType = typename LeafType::Buffer;
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
102 {
103 public:
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
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
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 /// @brief Generate a linear array of prefix sums of offsets into the
539 /// active voxels in the leafs. So @a offsets[n]+m is the offset to the
540 /// mth active voxel in the nth leaf node (useful for
541 /// user-managed value buffers, e.g. in tools/LevelSetAdvect.h).
542 /// @return The total number of active values in the leaf nodes
543 /// @param offsets array of prefix sums of offsets to active voxels
544 /// @param size on input, the size of @a offsets; on output, its new size
545 /// @param grainSize optional grain size for threading
546 /// @details If @a offsets is @c nullptr or @a size is smaller than the
547 /// total number of active voxels (the return value) then @a offsets
548 /// is reallocated and @a size equals the total number of active voxels.
549 size_t getPrefixSum(size_t*& offsets, size_t& size, size_t grainSize=1) const
550 {
551 if (offsets == nullptr || size < mLeafCount) {
552 delete [] offsets;
553 offsets = new size_t[mLeafCount];
554 size = mLeafCount;
555 }
556 size_t prefix = 0;
557 if ( grainSize > 0 ) {
558 PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix);
559 } else {// serial
560 for (size_t i=0; i<mLeafCount; ++i) {
561 offsets[i] = prefix;
562 prefix += mLeafs[i]->onVoxelCount();
563 }
564 }
565 return prefix;
566 }
567
568 ////////////////////////////////////////////////////////////////////////////////////
569 // All methods below are for internal use only and should never be called directly
570
571 /// Used internally by tbb::parallel_for() - never call it directly!
572 void operator()(const RangeType& r) const
573 {
574 if (mTask) mTask(const_cast<LeafManager*>(this), r);
575 else OPENVDB_THROW(ValueError, "task is undefined");
576 }
577
578private:
579
580 void initLeafArray(bool serial = false)
581 {
582 // Build an array of all nodes that have leaf nodes as their immediate children
583
584 using NodeChainT = typename NodeChain<RootNodeType, RootNodeType::LEVEL>::Type;
585 using NonConstLeafParentT = typename NodeChainT::template Get</*Level=*/1>;
586 using LeafParentT = typename CopyConstness<TreeType, NonConstLeafParentT>::Type;
587
588 std::deque<LeafParentT*> leafParents;
589 mTree->getNodes(leafParents);
590
591 // Compute the leaf counts for each node
592
593 std::vector<Index32> leafCounts;
594 if (serial) {
595 leafCounts.reserve(leafParents.size());
596 for (LeafParentT* leafParent : leafParents) {
597 leafCounts.push_back(leafParent->childCount());
598 }
599 } else {
600 leafCounts.resize(leafParents.size());
601 tbb::parallel_for(
602 // with typical node sizes and SSE enabled, there are only a handful
603 // of instructions executed per-operation with a default grainsize
604 // of 1, so increase to 64 to reduce parallel scheduling overhead
605 tbb::blocked_range<size_t>(0, leafParents.size(), /*grainsize=*/64),
606 [&](tbb::blocked_range<size_t>& range)
607 {
608 for (size_t i = range.begin(); i < range.end(); i++) {
609 leafCounts[i] = leafParents[i]->childCount();
610 }
611 }
612 );
613 }
614
615 // Turn leaf counts into a cumulative histogram and obtain total leaf count
616
617 for (size_t i = 1; i < leafCounts.size(); i++) {
618 leafCounts[i] += leafCounts[i-1];
619 }
620
621 const size_t leafCount = leafCounts.empty() ? 0 : leafCounts.back();
622
623 // Allocate (or deallocate) the leaf pointer array
624
625 if (leafCount != mLeafCount) {
626 if (leafCount > 0) {
627 mLeafPtrs.reset(new LeafType*[leafCount]);
628 mLeafs = mLeafPtrs.get();
629 } else {
630 mLeafPtrs.reset();
631 mLeafs = nullptr;
632 }
633 mLeafCount = leafCount;
634 }
635
636 if (mLeafCount == 0) return;
637
638 // Populate the leaf node pointers
639
640 if (serial) {
641 LeafType** leafPtr = mLeafs;
642 for (LeafParentT* leafParent : leafParents) {
643 for (auto iter = leafParent->beginChildOn(); iter; ++iter) {
644 *leafPtr++ = &iter.getValue();
645 }
646 }
647 } else {
648 tbb::parallel_for(
649 tbb::blocked_range<size_t>(0, leafParents.size()),
650 [&](tbb::blocked_range<size_t>& range)
651 {
652 size_t i = range.begin();
653 LeafType** leafPtr = mLeafs;
654 if (i > 0) leafPtr += leafCounts[i-1];
655 for ( ; i < range.end(); i++) {
656 for (auto iter = leafParents[i]->beginChildOn(); iter; ++iter) {
657 *leafPtr++ = &iter.getValue();
658 }
659 }
660 }
661 );
662 }
663 }
664
665 void initAuxBuffers(bool serial)
666 {
667 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
668 if (auxBufferCount != mAuxBufferCount) {
669 if (auxBufferCount > 0) {
670 mAuxBufferPtrs.reset(new NonConstBufferType[auxBufferCount]);
671 mAuxBuffers = mAuxBufferPtrs.get();
672 } else {
673 mAuxBufferPtrs.reset();
674 mAuxBuffers = nullptr;
675 }
676 mAuxBufferCount = auxBufferCount;
677 }
678 this->syncAllBuffers(serial);
679 }
680
681 void cook(size_t grainsize)
682 {
683 if (grainsize>0) {
684 tbb::parallel_for(this->getRange(grainsize), *this);
685 } else {
686 (*this)(this->getRange());
687 }
688 }
689
690 void doSwapLeafBuffer(const RangeType& r, size_t auxBufferIdx)
691 {
692 LeafManagerImpl<LeafManager>::doSwapLeafBuffer(
693 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
694 }
695
696 void doSwapAuxBuffer(const RangeType& r, size_t auxBufferIdx1, size_t auxBufferIdx2)
697 {
698 for (size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
699 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
700 }
701 }
702
703 void doSyncAuxBuffer(const RangeType& r, size_t auxBufferIdx)
704 {
705 for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
706 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
707 }
708 }
709
710 void doSyncAllBuffers1(const RangeType& r)
711 {
712 for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
713 mAuxBuffers[n] = mLeafs[n]->buffer();
714 }
715 }
716
717 void doSyncAllBuffers2(const RangeType& r)
718 {
719 for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
720 const BufferType& leafBuffer = mLeafs[n]->buffer();
721 mAuxBuffers[2*n ] = leafBuffer;
722 mAuxBuffers[2*n+1] = leafBuffer;
723 }
724 }
725
726 void doSyncAllBuffersN(const RangeType& r)
727 {
728 for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
729 const BufferType& leafBuffer = mLeafs[n]->buffer();
730 for (size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
731 }
732 }
733
734 /// @brief Private member class that applies a user-defined
735 /// functor to perform parallel_for on all the leaf nodes.
736 template<typename LeafOp>
737 struct LeafTransformer
738 {
739 LeafTransformer(const LeafOp &leafOp) : mLeafOp(leafOp)
740 {
741 }
742 void run(const LeafRange &range, bool threaded) const
743 {
744 threaded ? tbb::parallel_for(range, *this) : (*this)(range);
745 }
746 void operator()(const LeafRange &range) const
747 {
748 for (typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
749 }
750 const LeafOp mLeafOp;
751 };// LeafTransformer
752
753 /// @brief Private member class that applies a user-defined
754 /// functor to perform parallel_reduce on all the leaf nodes.
755 template<typename LeafOp>
756 struct LeafReducer
757 {
758 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp)
759 {
760 }
761 LeafReducer(const LeafReducer &other, tbb::split)
762 : mLeafOpPtr(std::make_unique<LeafOp>(*(other.mLeafOp), tbb::split()))
763 , mLeafOp(mLeafOpPtr.get())
764 {
765 }
766 void run(const LeafRange& range, bool threaded)
767 {
768 threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
769 }
770 void operator()(const LeafRange& range)
771 {
772 LeafOp &op = *mLeafOp;//local registry
773 for (typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos());
774 }
775 void join(const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
776 std::unique_ptr<LeafOp> mLeafOpPtr;
777 LeafOp *mLeafOp = nullptr;
778 };// LeafReducer
779
780 // Helper class to compute a prefix sum of offsets to active voxels
781 struct PrefixSum
782 {
783 PrefixSum(const LeafRange& r, size_t* offsets, size_t& prefix)
784 : mOffsets(offsets)
785 {
786 tbb::parallel_for( r, *this);
787 for (size_t i=0, leafCount = r.size(); i<leafCount; ++i) {
788 size_t tmp = offsets[i];
789 offsets[i] = prefix;
790 prefix += tmp;
791 }
792 }
793 inline void operator()(const LeafRange& r) const {
794 for (typename LeafRange::Iterator i = r.begin(); i; ++i) {
795 mOffsets[i.pos()] = i->onVoxelCount();
796 }
797 }
798 size_t* mOffsets;
799 };// PrefixSum
800
801 using FuncType = typename std::function<void (LeafManager*, const RangeType&)>;
802
803 TreeType* mTree;
804 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
805 std::unique_ptr<LeafType*[]> mLeafPtrs;
806 LeafType** mLeafs = nullptr;//array of LeafNode pointers
807 std::unique_ptr<NonConstBufferType[]> mAuxBufferPtrs;
808 NonConstBufferType* mAuxBuffers = nullptr;//array of auxiliary buffers
809 FuncType mTask = nullptr;
810};//end of LeafManager class
811
812
813// Partial specializations of LeafManager methods for const trees
814template<typename TreeT>
815struct LeafManagerImpl<LeafManager<const TreeT> >
816{
818 using RangeT = typename ManagerT::RangeType;
819 using LeafT = typename ManagerT::LeafType;
820 using BufT = typename ManagerT::BufferType;
821
822 static inline void doSwapLeafBuffer(const RangeT&, size_t /*auxBufferIdx*/,
823 LeafT**, BufT*, size_t /*bufsPerLeaf*/)
824 {
825 // Buffers can't be swapped into const trees.
826 }
827};
828
829} // namespace tree
830} // namespace OPENVDB_VERSION_NAME
831} // namespace openvdb
832
833#endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
The root node of an OpenVDB tree.
Definition: Exceptions.h:65
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:130
Iterator & operator=(const Iterator &)=default
bool isValid() const
Return true if the position of this iterator is in a valid range.
Definition: LeafManager.h:128
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:134
Iterator(const LeafRange &range, size_t pos)
Definition: LeafManager.h:107
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:118
bool operator!=(const Iterator &other) const
Definition: LeafManager.h:135
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:116
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:126
BufferType & buffer(size_t bufferIdx)
Return the nth buffer for the leaf node to which this iterator is pointing, where n = bufferIdx and n...
Definition: LeafManager.h:121
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:114
const LeafRange & leafRange() const
Definition: LeafManager.h:140
bool operator==(const Iterator &other) const
Definition: LeafManager.h:139
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:147
Iterator begin() const
Definition: LeafManager.h:155
size_t size() const
Definition: LeafManager.h:159
bool is_divisible() const
Definition: LeafManager.h:167
const LeafManager & leafManager() const
Definition: LeafManager.h:163
Iterator end() const
Definition: LeafManager.h:157
bool empty() const
Definition: LeafManager.h:165
LeafRange(LeafRange &r, tbb::split)
Definition: LeafManager.h:169
size_t grainsize() const
Definition: LeafManager.h:161
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:85
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:302
BufferType & getBuffer(size_t leafIdx, size_t bufferIdx) const
Return the leaf or auxiliary buffer for the leaf node at index leafIdx. If bufferIdx is zero,...
Definition: LeafManager.h:330
size_t getPrefixSum(size_t *&offsets, size_t &size, size_t grainSize=1) const
Generate a linear array of prefix sums of offsets into the active voxels in the leafs....
Definition: LeafManager.h:549
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:282
typename CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:95
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:311
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:305
typename TreeT::ValueType ValueType
Definition: LeafManager.h:88
typename leafmgr::TreeTraits< TreeT >::LeafIterType LeafIterType
Definition: LeafManager.h:93
bool swapLeafBuffer(size_t bufferIdx, bool serial=false)
Swap each leaf node's buffer with the nth corresponding auxiliary buffer, where n = bufferIdx.
Definition: LeafManager.h:359
void rebuild(TreeType &tree, bool serial=false)
Definition: LeafManager.h:250
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:572
void rebuild(bool serial=false)
(Re)initialize by resizing (if necessary) and repopulating the leaf array and by deleting existing au...
Definition: LeafManager.h:238
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:371
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:342
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:395
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:407
LeafManager(const LeafManager &other)
Definition: LeafManager.h:222
void reduce(LeafOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to each leaf node in the LeafManager....
Definition: LeafManager.h:532
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:314
typename TreeT::RootNodeType RootNodeType
Definition: LeafManager.h:89
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
Definition: LeafManager.h:192
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:284
typename TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:90
LeafManager(TreeType &tree, LeafType **begin, LeafType **end, size_t auxBuffersPerLeaf=0, bool serial=false)
Construct directly from an existing array of leafnodes.
Definition: LeafManager.h:204
void rebuildLeafArray(bool serial=false)
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:275
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:287
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Definition: LeafManager.h:255
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:96
void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
Change the number of auxiliary buffers.
Definition: LeafManager.h:266
void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:245
typename LeafType::Buffer NonConstBufferType
Definition: LeafManager.h:94
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:345
TreeT TreeType
Definition: LeafManager.h:87
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:308
typename CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:91
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
Definition: LeafManager.h:291
LeafType LeafNodeType
Definition: LeafManager.h:92
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:272
OPENVDB_AX_API void run(const char *ax, openvdb::GridBase &grid, const AttributeBindings &bindings={})
Run a full AX pipeline (parse, compile and execute) on a single OpenVDB Grid.
Index32 Index
Definition: Types.h:54
uint64_t Index64
Definition: Types.h:53
Definition: Exceptions.h:13
Definition: Coord.h:587
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
typename std::remove_const< ToType >::type Type
Definition: Types.h:400
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:819
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:818
typename ManagerT::BufferType BufT
Definition: LeafManager.h:820
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:822
Definition: LeafManager.h:54
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:59
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:56
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:55
typename ManagerT::BufferType BufT
Definition: LeafManager.h:57
typename SubtreeT::template Append< HeadT > Type
Definition: RootNode.h:1003
typename TreeT::LeafCIter LeafIterType
Definition: LeafManager.h:43
Useful traits for Tree types.
Definition: LeafManager.h:37
typename TreeT::LeafIter LeafIterType
Definition: LeafManager.h:39
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212