Go to the documentation of this file.
15 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
16 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
19 #include <tbb/blocked_range.h>
20 #include <tbb/parallel_for.h>
21 #include <tbb/parallel_reduce.h>
23 #include <type_traits>
36 static const bool IsConstTree =
false;
39 template<
typename TreeT>
struct TreeTraits<const TreeT> {
40 static const bool IsConstTree =
true;
50 template<
typename ManagerT>
53 using RangeT =
typename ManagerT::RangeType;
54 using LeafT =
typename ManagerT::LeafType;
55 using BufT =
typename ManagerT::BufferType;
58 LeafT** leafs,
BufT* bufs,
size_t bufsPerLeaf)
60 for (
size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
61 leafs[n]->swap(bufs[n * N + auxBufferIdx]);
81 template<
typename TreeT>
107 assert(this->isValid());
121 return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
124 size_t pos()
const {
return mPos; }
126 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
128 bool test()
const {
return mPos < mRange.mEnd; }
130 operator bool()
const {
return this->test(); }
132 bool empty()
const {
return !this->test(); }
135 return (mPos != other.mPos) || (&mRange != &other.mRange);
148 , mGrainSize(grainSize)
149 , mLeafManager(leafManager)
157 size_t size()
const {
return mEnd - mBegin; }
163 bool empty()
const {
return !(mBegin < mEnd);}
170 , mGrainSize(r.mGrainSize)
171 , mLeafManager(r.mLeafManager)
176 size_t mEnd, mBegin, mGrainSize;
182 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
194 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
196 , mAuxBuffers(nullptr)
200 this->rebuild(serial);
207 size_t auxBuffersPerLeaf=0,
bool serial=
false)
209 , mLeafCount(end-begin)
211 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
213 , mAuxBuffers(nullptr)
217 size_t n = mLeafCount;
218 LeafType **target = mLeafs, **source = begin;
219 while (n--) *target++ = *source++;
220 if (auxBuffersPerLeaf) this->initAuxBuffers(serial);
228 , mLeafCount(other.mLeafCount)
229 , mAuxBufferCount(other.mAuxBufferCount)
230 , mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf)
231 , mLeafs(other.mLeafs)
232 , mAuxBuffers(other.mAuxBuffers)
242 delete [] mAuxBuffers;
253 this->initLeafArray();
254 this->initAuxBuffers(serial);
257 void rebuild(
size_t auxBuffersPerLeaf,
bool serial=
false)
260 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
261 this->rebuild(serial);
266 this->rebuild(serial);
271 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
272 this->rebuild(serial);
275 void rebuildAuxBuffers(
size_t auxBuffersPerLeaf,
bool serial=
false)
281 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
282 this->initAuxBuffers(serial);
290 this->removeAuxBuffers();
291 this->initLeafArray();
306 return tbb::parallel_reduce(this->leafRange(),
Index64(0),
308 for (
const auto& leaf: range) { sum += leaf.onVoxelCount(); }
331 LeafType&
leaf(
size_t leafIdx)
const { assert(leafIdx<mLeafCount);
return *mLeafs[leafIdx]; }
345 assert(leafIdx < mLeafCount);
346 assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
347 return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
348 : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
360 return LeafRange(0, mLeafCount, *
this, grainsize);
374 namespace ph = std::placeholders;
375 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree())
return false;
376 mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, bufferIdx - 1);
377 this->cook(serial ? 0 : 512);
384 bool swapBuffer(
size_t bufferIdx1,
size_t bufferIdx2,
bool serial =
false)
386 namespace ph = std::placeholders;
387 const size_t b1 =
std::min(bufferIdx1, bufferIdx2);
388 const size_t b2 =
std::max(bufferIdx1, bufferIdx2);
389 if (b1 == b2 || b2 > mAuxBuffersPerLeaf)
return false;
391 if (this->isConstTree())
return false;
392 mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, b2-1);
394 mTask = std::bind(&LeafManager::doSwapAuxBuffer, ph::_1, ph::_2, b1-1, b2-1);
396 this->cook(serial ? 0 : 512);
410 namespace ph = std::placeholders;
411 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf)
return false;
412 mTask = std::bind(&LeafManager::doSyncAuxBuffer, ph::_1, ph::_2, bufferIdx - 1);
413 this->cook(serial ? 0 : 64);
422 namespace ph = std::placeholders;
423 switch (mAuxBuffersPerLeaf) {
424 case 0:
return false;
425 case 1: mTask = std::bind(&LeafManager::doSyncAllBuffers1, ph::_1, ph::_2);
break;
426 case 2: mTask = std::bind(&LeafManager::doSyncAllBuffers2, ph::_1, ph::_2);
break;
427 default: mTask = std::bind(&LeafManager::doSyncAllBuffersN, ph::_1, ph::_2);
break;
429 this->cook(serial ? 0 : 64);
495 template<
typename LeafOp>
496 void foreach(
const LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
498 LeafTransformer<LeafOp> transform(op);
499 transform.run(this->leafRange(grainSize), threaded);
544 template<
typename LeafOp>
545 void reduce(LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
547 LeafReducer<LeafOp> transform(op);
548 transform.run(this->leafRange(grainSize), threaded);
556 template<
typename ArrayT>
559 using T =
typename ArrayT::value_type;
560 static_assert(std::is_pointer<T>::value,
"argument to getNodes() must be a pointer array");
561 using LeafT =
typename std::conditional<std::is_const<
562 typename std::remove_pointer<T>::type>::value,
const LeafType,
LeafType>::type;
565 if (std::is_same<T, LeafT*>::value) {
566 array.resize(mLeafCount);
567 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
569 mTree->getNodes(array);
578 template<
typename ArrayT>
581 using T =
typename ArrayT::value_type;
582 static_assert(std::is_pointer<T>::value,
"argument to getNodes() must be a pointer array");
583 static_assert(std::is_const<
typename std::remove_pointer<T>::type>::value,
584 "argument to getNodes() must be an array of const node pointers");
587 if (std::is_same<T, const LeafType*>::value) {
588 array.resize(mLeafCount);
589 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
591 mTree->getNodes(array);
607 size_t getPrefixSum(
size_t*& offsets,
size_t& size,
size_t grainSize=1)
const
609 if (offsets ==
nullptr || size < mLeafCount) {
611 offsets =
new size_t[mLeafCount];
615 if ( grainSize > 0 ) {
616 PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix);
618 for (
size_t i=0; i<mLeafCount; ++i) {
620 prefix += mLeafs[i]->onVoxelCount();
632 if (mTask) mTask(const_cast<LeafManager*>(
this), r);
642 using value_type = LeafType*;
644 MyArray(value_type* array) : ptr(array) {}
645 void push_back(value_type leaf) { *ptr++ = leaf; }
650 const size_t leafCount = mTree->leafCount();
651 if (leafCount != mLeafCount) {
653 mLeafs = (leafCount == 0) ?
nullptr :
new LeafType*[leafCount];
654 mLeafCount = leafCount;
660 void initAuxBuffers(
bool serial)
662 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
663 if (auxBufferCount != mAuxBufferCount) {
664 delete [] mAuxBuffers;
665 mAuxBuffers = (auxBufferCount == 0) ?
nullptr :
new NonConstBufferType[auxBufferCount];
666 mAuxBufferCount = auxBufferCount;
668 this->syncAllBuffers(serial);
671 void cook(
size_t grainsize)
674 tbb::parallel_for(this->getRange(grainsize), *
this);
676 (*this)(this->getRange());
680 void doSwapLeafBuffer(
const RangeType& r,
size_t auxBufferIdx)
682 LeafManagerImpl<LeafManager>::doSwapLeafBuffer(
683 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
686 void doSwapAuxBuffer(
const RangeType& r,
size_t auxBufferIdx1,
size_t auxBufferIdx2)
688 for (
size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
689 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
693 void doSyncAuxBuffer(
const RangeType& r,
size_t auxBufferIdx)
695 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
696 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
700 void doSyncAllBuffers1(
const RangeType& r)
702 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
703 mAuxBuffers[n] = mLeafs[n]->buffer();
707 void doSyncAllBuffers2(
const RangeType& r)
709 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
710 const BufferType& leafBuffer = mLeafs[n]->buffer();
711 mAuxBuffers[2*n ] = leafBuffer;
712 mAuxBuffers[2*n+1] = leafBuffer;
716 void doSyncAllBuffersN(
const RangeType& r)
718 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
719 const BufferType& leafBuffer = mLeafs[n]->buffer();
720 for (
size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
726 template<
typename LeafOp>
727 struct LeafTransformer
729 LeafTransformer(
const LeafOp &leafOp) : mLeafOp(leafOp)
732 void run(
const LeafRange &range,
bool threaded)
const
734 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
736 void operator()(
const LeafRange &range)
const
738 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
740 const LeafOp mLeafOp;
745 template<
typename LeafOp>
748 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp), mOwnsOp(false)
751 LeafReducer(
const LeafReducer &other, tbb::split)
752 : mLeafOp(new LeafOp(*(other.mLeafOp),
tbb::split())), mOwnsOp(true)
755 ~LeafReducer() {
if (mOwnsOp)
delete mLeafOp; }
756 void run(
const LeafRange& range,
bool threaded)
758 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
760 void operator()(
const LeafRange& range)
762 LeafOp &op = *mLeafOp;
763 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos());
765 void join(
const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
773 PrefixSum(
const LeafRange& r,
size_t* offsets,
size_t& prefix)
776 tbb::parallel_for( r, *
this);
777 for (
size_t i=0, leafCount = r.size(); i<leafCount; ++i) {
778 size_t tmp = offsets[i];
783 inline void operator()(
const LeafRange& r)
const {
784 for (
typename LeafRange::Iterator i = r.begin(); i; ++i) {
785 mOffsets[i.pos()] = i->onVoxelCount();
791 using FuncType =
typename std::function<void (LeafManager*,
const RangeType&)>;
794 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
796 NonConstBufferType* mAuxBuffers;
798 const bool mIsMaster;
803 template<
typename TreeT>
822 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:384
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:206
Iterator begin() const
Definition: LeafManager.h:153
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:321
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:545
void getNodes(ArrayT &array)
Insert pointers to nodes of the specified type into the array.
Definition: LeafManager.h:557
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:132
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:618
LeafRange(LeafRange &r, tbb::split)
Definition: LeafManager.h:167
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:54
bool isValid() const
Return true if the position of this iterator is in a valid range.
Definition: LeafManager.h:126
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:114
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
Definition: LeafManager.h:304
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:372
TreeT TreeType
Definition: LeafManager.h:85
typename TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:88
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:119
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:358
typename CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:93
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:318
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:288
const LeafManager & leafManager() const
Definition: LeafManager.h:161
typename LeafType::Buffer NonConstBufferType
Definition: LeafManager.h:92
size_t grainsize() const
Definition: LeafManager.h:159
bool operator!=(const Iterator &other) const
Definition: LeafManager.h:133
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Definition: LeafManager.h:268
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:145
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:420
Definition: LeafManager.h:51
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
Definition: LeafManager.h:190
typename leafmgr::TreeTraits< TreeT >::LeafIterType LeafIterType
Definition: LeafManager.h:91
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:112
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:295
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:53
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:57
size_t size() const
Definition: LeafManager.h:157
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:331
Definition: LeafManager.h:99
typename ManagerT::BufferType BufT
Definition: LeafManager.h:809
typename ManagerT::BufferType BufT
Definition: LeafManager.h:55
void rebuild(TreeType &tree, bool serial=false)
Definition: LeafManager.h:263
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:94
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:408
void rebuild(bool serial=false)
(Re)initialize by resizing (if necessary) and repopulating the leaf array and by deleting existing au...
Definition: LeafManager.h:251
typename TreeT::RootNodeType RootNodeType
Definition: LeafManager.h:87
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:315
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:343
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:82
typename ManagerT::LeafType LeafT
Definition: LeafManager.h:808
typename TreeT::ValueType ValueType
Definition: LeafManager.h:86
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
Definition: LeafManager.h:102
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:128
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:124
bool operator==(const Iterator &other) const
Definition: LeafManager.h:137
virtual ~LeafManager()
Definition: LeafManager.h:238
LeafType LeafNodeType
Definition: LeafManager.h:90
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:630
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:327
Index32 Index
Definition: Types.h:31
Useful traits for Tree types.
Definition: LeafManager.h:35
bool is_divisible() const
Definition: LeafManager.h:165
typename std::remove_const< ToType >::type Type
Definition: Types.h:298
typename ManagerT::RangeType RangeT
Definition: LeafManager.h:807
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
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:607
LeafManager(const LeafManager &other)
Definition: LeafManager.h:226
Definition: Exceptions.h:65
typename CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:89
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:324
const LeafRange & leafRange() const
Definition: LeafManager.h:138
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:300
Definition: Exceptions.h:13
uint64_t Index64
Definition: Types.h:30
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:297
typename TreeT::LeafCIter LeafIterType
Definition: LeafManager.h:41
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:355
Iterator end() const
Definition: LeafManager.h:155
bool empty() const
Definition: LeafManager.h:163
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:285
Iterator(const LeafRange &range, size_t pos)
Definition: LeafManager.h:105
void getNodes(ArrayT &array) const
Insert node pointers of the specified type into the array.
Definition: LeafManager.h:579
typename TreeT::LeafIter LeafIterType
Definition: LeafManager.h:37
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:811