15 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 16 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 20 #include <tbb/blocked_range.h> 21 #include <tbb/parallel_for.h> 22 #include <tbb/parallel_reduce.h> 25 #include <type_traits> 38 static const bool IsConstTree =
false;
41 template<
typename TreeT>
struct TreeTraits<const TreeT> {
42 static const bool IsConstTree =
true;
52 template<
typename ManagerT>
55 using RangeT =
typename ManagerT::RangeType;
56 using LeafT =
typename ManagerT::LeafType;
57 using BufT =
typename ManagerT::BufferType;
60 LeafT** leafs,
BufT* bufs,
size_t bufsPerLeaf)
62 for (
size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
63 leafs[n]->swap(bufs[n * N + auxBufferIdx]);
83 template<
typename TreeT>
87 using TreeType = TreeT;
94 using NonConstBufferType =
typename LeafType::Buffer;
123 return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
126 size_t pos()
const {
return mPos; }
128 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
130 bool test()
const {
return mPos < mRange.mEnd; }
132 operator bool()
const {
return this->test(); }
134 bool empty()
const {
return !this->test(); }
137 return (mPos != other.mPos) || (&mRange != &other.mRange);
150 , mGrainSize(grainSize)
151 , mLeafManager(leafManager)
159 size_t size()
const {
return mEnd - mBegin; }
165 bool empty()
const {
return !(mBegin < mEnd);}
172 , mGrainSize(r.mGrainSize)
173 , mLeafManager(r.mLeafManager)
178 size_t mEnd, mBegin, mGrainSize;
184 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
192 LeafManager(TreeType& tree,
size_t auxBuffersPerLeaf=0,
bool serial=
false)
196 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
198 this->rebuild(serial);
205 size_t auxBuffersPerLeaf=0,
bool serial=
false)
207 , mLeafCount(end-begin)
209 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
210 , mLeafPtrs(new
LeafType*[mLeafCount])
211 , mLeafs(mLeafPtrs.get())
213 size_t n = mLeafCount;
214 LeafType **target = mLeafs, **source = begin;
215 while (n--) *target++ = *source++;
216 if (auxBuffersPerLeaf) this->initAuxBuffers(serial);
224 , mLeafCount(other.mLeafCount)
225 , mAuxBufferCount(other.mAuxBufferCount)
226 , mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf)
227 , mLeafs(other.mLeafs)
228 , mAuxBuffers(other.mAuxBuffers)
240 this->initLeafArray(serial);
241 this->initAuxBuffers(serial);
245 void rebuild(
size_t auxBuffersPerLeaf,
bool serial=
false)
247 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
248 this->rebuild(serial);
250 void rebuild(TreeType& tree,
bool serial=
false)
253 this->rebuild(serial);
255 void rebuild(TreeType& tree,
size_t auxBuffersPerLeaf,
bool serial=
false)
258 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
259 this->rebuild(serial);
268 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
269 this->initAuxBuffers(serial);
277 this->removeAuxBuffers();
278 this->initLeafArray(serial);
293 return tbb::parallel_reduce(this->leafRange(),
Index64(0),
295 for (
const auto& leaf: range) { sum += leaf.onVoxelCount(); }
302 const TreeType&
tree()
const {
return *mTree; }
305 TreeType&
tree() {
return *mTree; }
318 LeafType&
leaf(
size_t leafIdx)
const { assert(leafIdx<mLeafCount);
return *mLeafs[leafIdx]; }
332 assert(leafIdx < mLeafCount);
333 assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
334 return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
335 : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
347 return LeafRange(0, mLeafCount, *
this, grainsize);
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);
371 bool swapBuffer(
size_t bufferIdx1,
size_t bufferIdx2,
bool serial =
false)
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;
378 if (this->isConstTree())
return false;
379 mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, b2-1);
381 mTask = std::bind(&LeafManager::doSwapAuxBuffer, ph::_1, ph::_2, b1-1, b2-1);
383 this->cook(serial ? 0 : 512);
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);
409 namespace ph = std::placeholders;
410 switch (mAuxBuffersPerLeaf) {
411 case 0:
return false;
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;
416 this->cook(serial ? 0 : 64);
482 template<
typename LeafOp>
483 void foreach(
const LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
485 LeafTransformer<LeafOp> transform(op);
486 transform.run(this->leafRange(grainSize), threaded);
531 template<
typename LeafOp>
532 void reduce(LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
534 LeafReducer<LeafOp> transform(op);
535 transform.run(this->leafRange(grainSize), threaded);
549 size_t getPrefixSum(
size_t*& offsets,
size_t& size,
size_t grainSize=1)
const 551 if (offsets ==
nullptr || size < mLeafCount) {
553 offsets =
new size_t[mLeafCount];
557 if ( grainSize > 0 ) {
558 PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix);
560 for (
size_t i=0; i<mLeafCount; ++i) {
562 prefix += mLeafs[i]->onVoxelCount();
574 if (mTask) mTask(const_cast<LeafManager*>(
this), r);
580 void initLeafArray(
bool serial =
false)
585 using NonConstLeafParentT =
typename NodeChainT::template Get<1>;
588 std::deque<LeafParentT*> leafParents;
589 if constexpr(std::is_same<NonConstLeafParentT, RootNodeType>::value) {
590 leafParents.emplace_back(&mTree->root());
593 mTree->getNodes(leafParents);
598 std::vector<Index32> leafCounts;
600 leafCounts.reserve(leafParents.size());
601 for (LeafParentT* leafParent : leafParents) {
602 leafCounts.push_back(leafParent->childCount());
605 leafCounts.resize(leafParents.size());
610 tbb::blocked_range<size_t>(0, leafParents.size(), 64),
611 [&](tbb::blocked_range<size_t>& range)
613 for (
size_t i = range.begin(); i < range.end(); i++) {
614 leafCounts[i] = leafParents[i]->childCount();
622 for (
size_t i = 1; i < leafCounts.size(); i++) {
623 leafCounts[i] += leafCounts[i-1];
626 const size_t leafCount = leafCounts.empty() ? 0 : leafCounts.back();
630 if (leafCount != mLeafCount) {
632 mLeafPtrs.reset(
new LeafType*[leafCount]);
633 mLeafs = mLeafPtrs.get();
638 mLeafCount = leafCount;
641 if (mLeafCount == 0)
return;
647 for (LeafParentT* leafParent : leafParents) {
648 for (
auto iter = leafParent->beginChildOn(); iter; ++iter) {
649 *leafPtr++ = &iter.getValue();
654 tbb::blocked_range<size_t>(0, leafParents.size()),
655 [&](tbb::blocked_range<size_t>& range)
657 size_t i = range.begin();
659 if (i > 0) leafPtr += leafCounts[i-1];
660 for ( ; i < range.end(); i++) {
661 for (
auto iter = leafParents[i]->beginChildOn(); iter; ++iter) {
662 *leafPtr++ = &iter.getValue();
670 void initAuxBuffers(
bool serial)
672 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
673 if (auxBufferCount != mAuxBufferCount) {
674 if (auxBufferCount > 0) {
675 mAuxBufferPtrs.reset(
new NonConstBufferType[auxBufferCount]);
676 mAuxBuffers = mAuxBufferPtrs.get();
678 mAuxBufferPtrs.reset();
679 mAuxBuffers =
nullptr;
681 mAuxBufferCount = auxBufferCount;
683 this->syncAllBuffers(serial);
686 void cook(
size_t grainsize)
689 tbb::parallel_for(this->getRange(grainsize), *
this);
691 (*this)(this->getRange());
695 void doSwapLeafBuffer(
const RangeType& r,
size_t auxBufferIdx)
698 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
701 void doSwapAuxBuffer(
const RangeType& r,
size_t auxBufferIdx1,
size_t auxBufferIdx2)
703 for (
size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
704 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
708 void doSyncAuxBuffer(
const RangeType& r,
size_t auxBufferIdx)
710 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
711 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
715 void doSyncAllBuffers1(
const RangeType& r)
717 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
718 mAuxBuffers[n] = mLeafs[n]->buffer();
722 void doSyncAllBuffers2(
const RangeType& r)
724 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
725 const BufferType& leafBuffer = mLeafs[n]->buffer();
726 mAuxBuffers[2*n ] = leafBuffer;
727 mAuxBuffers[2*n+1] = leafBuffer;
731 void doSyncAllBuffersN(
const RangeType& r)
733 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
734 const BufferType& leafBuffer = mLeafs[n]->buffer();
735 for (
size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
741 template<
typename LeafOp>
742 struct LeafTransformer
744 LeafTransformer(
const LeafOp &leafOp) : mLeafOp(leafOp)
747 void run(
const LeafRange &range,
bool threaded)
const 749 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
751 void operator()(
const LeafRange &range)
const 753 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
755 const LeafOp mLeafOp;
760 template<
typename LeafOp>
763 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp)
766 LeafReducer(
const LeafReducer &other,
tbb::split)
767 : mLeafOpPtr(std::make_unique<LeafOp>(*(other.mLeafOp),
tbb::split()))
768 , mLeafOp(mLeafOpPtr.get())
771 void run(
const LeafRange& range,
bool threaded)
773 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
775 void operator()(
const LeafRange& range)
777 LeafOp &op = *mLeafOp;
778 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos());
780 void join(
const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
781 std::unique_ptr<LeafOp> mLeafOpPtr;
782 LeafOp *mLeafOp =
nullptr;
788 PrefixSum(
const LeafRange& r,
size_t* offsets,
size_t& prefix)
791 tbb::parallel_for( r, *
this);
792 for (
size_t i=0, leafCount = r.size(); i<leafCount; ++i) {
793 size_t tmp = offsets[i];
798 inline void operator()(
const LeafRange& r)
const {
799 for (
typename LeafRange::Iterator i = r.begin(); i; ++i) {
800 mOffsets[i.pos()] = i->onVoxelCount();
806 using FuncType =
typename std::function<void (LeafManager*, const RangeType&)>;
809 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
810 std::unique_ptr<LeafType*[]> mLeafPtrs;
812 std::unique_ptr<NonConstBufferType[]> mAuxBufferPtrs;
813 NonConstBufferType* mAuxBuffers =
nullptr;
814 FuncType mTask =
nullptr;
819 template<
typename TreeT>
838 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED typename ManagerT::BufferType BufT
Definition: LeafManager.h:825
size_t grainsize() const
Definition: LeafManager.h:161
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:407
Definition: Exceptions.h:65
typename CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:95
size_t size() const
Definition: LeafManager.h:159
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:59
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:147
Iterator end() const
Definition: LeafManager.h:157
bool operator==(const Iterator &other) const
Definition: LeafManager.h:139
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:345
typename TreeType::RootNodeType RootNodeType
Definition: LeafManager.h:89
typename TreeType::ValueType ValueType
Definition: LeafManager.h:88
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:55
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:96
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:572
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:118
Iterator(const LeafRange &range, size_t pos)
Definition: LeafManager.h:107
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
Definition: LeafManager.h:192
typename CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:91
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:126
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:371
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:824
bool operator!=(const Iterator &other) const
Definition: LeafManager.h:135
void rebuild(TreeType &tree, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:250
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:597
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:314
Definition: LeafManager.h:101
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:255
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. So offsets[n]+m is the offset to the mth active voxel in the nth leaf node (useful for user-managed value buffers, e.g. in tools/LevelSetAdvect.h).
Definition: LeafManager.h:549
void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:245
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
typename ManagerT::BufferType BufT
Definition: LeafManager.h:57
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:827
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
uint64_t Index64
Definition: Types.h:53
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:395
typename std::remove_const< ToType >::type Type
Definition: Types.h:439
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:305
bool empty() const
Definition: LeafManager.h:165
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:272
typename TreeT::LeafIter LeafIterType
Definition: LeafManager.h:39
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. Unlike foreach (defined above) this method performs a reduction on all the leaf nodes.
Definition: LeafManager.h:532
void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
Change the number of auxiliary buffers.
Definition: LeafManager.h:266
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
Definition: Exceptions.h:13
typename leafmgr::TreeTraits< TreeType >::LeafIterType LeafIterType
Definition: LeafManager.h:93
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:302
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:284
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:134
typename TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:90
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
Definition: LeafManager.h:291
LeafRange(LeafRange &r, tbb::split)
Definition: LeafManager.h:169
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:287
Definition: LeafManager.h:53
Useful traits for Tree types.
Definition: LeafManager.h:37
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:116
const LeafManager & leafManager() const
Definition: LeafManager.h:163
Index32 Index
Definition: Types.h:54
Definition: LeafManager.h:104
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:311
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:318
bool isValid() const
Return true if the position of this iterator is in a valid range.
Definition: LeafManager.h:128
LeafManager(const LeafManager &other)
Definition: LeafManager.h:222
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:282
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:342
The root node of an OpenVDB tree.
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:308
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.
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
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:114
LeafType LeafNodeType
Definition: LeafManager.h:92
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:84
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:823
static bool isValid(const void *p)
return true if the specified pointer is aligned and not NULL
Definition: NanoVDB.h:743
const LeafRange & leafRange() const
Definition: LeafManager.h:140
void rebuildLeafArray(bool serial=false)
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:275
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
void split(ContainerT &out, const std::string &in, const char delim)
Definition: Name.h:43
bool is_divisible() const
Definition: LeafManager.h:167
Iterator begin() const
Definition: LeafManager.h:155
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:56
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:130
typename TreeT::LeafCIter LeafIterType
Definition: LeafManager.h:43
typename SubtreeT::template Append< HeadT > Type
Definition: RootNode.h:999
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
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