42 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 43 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED 45 #include <boost/shared_ptr.hpp> 46 #include <boost/bind.hpp> 47 #include <boost/function.hpp> 48 #include <boost/mpl/if.hpp> 49 #include <boost/type_traits/is_const.hpp> 50 #include <boost/type_traits/is_pointer.hpp> 51 #include <boost/type_traits/is_same.hpp> 52 #include <boost/type_traits/remove_pointer.hpp> 53 #include <tbb/blocked_range.h> 54 #include <tbb/parallel_for.h> 55 #include <tbb/parallel_reduce.h> 69 static const bool IsConstTree =
false;
72 template<
typename TreeT>
struct TreeTraits<const TreeT> {
73 static const bool IsConstTree =
true;
83 template<
typename ManagerT>
86 typedef typename ManagerT::RangeType
RangeT;
87 typedef typename ManagerT::LeafType
LeafT;
88 typedef typename ManagerT::BufferType
BufT;
91 LeafT** leafs, BufT* bufs,
size_t bufsPerLeaf)
93 for (
size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
94 leafs[n]->swap(bufs[n * N + auxBufferIdx]);
114 template<
typename TreeT>
140 assert(this->isValid());
147 LeafType&
operator*()
const {
return mRange.mLeafManager.leaf(mPos); }
154 return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
157 size_t pos()
const {
return mPos; }
159 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
161 bool test()
const {
return mPos < mRange.mEnd; }
163 operator bool()
const {
return this->test(); }
165 bool empty()
const {
return !this->test(); }
168 return (mPos != other.mPos) || (&mRange != &other.mRange);
181 , mGrainSize(grainSize)
182 , mLeafManager(leafManager)
190 size_t size()
const {
return mEnd - mBegin; }
196 bool empty()
const {
return !(mBegin < mEnd);}
203 , mGrainSize(r.mGrainSize)
204 , mLeafManager(r.mLeafManager)
209 size_t mEnd, mBegin, mGrainSize;
215 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
223 LeafManager(TreeType& tree,
size_t auxBuffersPerLeaf=0,
bool serial=
false)
227 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
229 , mAuxBuffers(nullptr)
233 this->rebuild(serial);
240 size_t auxBuffersPerLeaf=0,
bool serial=
false)
242 , mLeafCount(end-begin)
244 , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
245 , mLeafs(new LeafType*[mLeafCount])
246 , mAuxBuffers(nullptr)
250 size_t n = mLeafCount;
251 LeafType **target = mLeafs, **source = begin;
252 while (n--) *target++ = *source++;
253 if (auxBuffersPerLeaf) this->initAuxBuffers(serial);
261 , mLeafCount(other.mLeafCount)
262 , mAuxBufferCount(other.mAuxBufferCount)
263 , mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf)
264 , mLeafs(other.mLeafs)
265 , mAuxBuffers(other.mAuxBuffers)
275 delete [] mAuxBuffers;
286 this->initLeafArray();
287 this->initAuxBuffers(serial);
290 void rebuild(
size_t auxBuffersPerLeaf,
bool serial=
false)
293 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
294 this->rebuild(serial);
296 void rebuild(TreeType& tree,
bool serial=
false)
299 this->rebuild(serial);
301 void rebuild(TreeType& tree,
size_t auxBuffersPerLeaf,
bool serial=
false)
304 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
305 this->rebuild(serial);
308 void rebuildAuxBuffers(
size_t auxBuffersPerLeaf,
bool serial=
false)
314 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
315 this->initAuxBuffers(serial);
323 this->removeAuxBuffers();
324 this->initLeafArray();
339 return tbb::parallel_reduce(this->leafRange(),
Index64(0),
341 for (
const auto& leaf: range) { sum += leaf.onVoxelCount(); }
348 const TreeType&
tree()
const {
return *mTree; }
351 TreeType&
tree() {
return *mTree; }
354 const RootNodeType&
root()
const {
return mTree->root(); }
357 RootNodeType&
root() {
return mTree->root(); }
364 LeafType&
leaf(
size_t leafIdx)
const { assert(leafIdx<mLeafCount);
return *mLeafs[leafIdx]; }
376 BufferType&
getBuffer(
size_t leafIdx,
size_t bufferIdx)
const 378 assert(leafIdx < mLeafCount);
379 assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
380 return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
381 : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
388 RangeType
getRange(
size_t grainsize = 1)
const {
return RangeType(0, mLeafCount, grainsize); }
393 return LeafRange(0, mLeafCount, *
this, grainsize);
407 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree())
return false;
408 mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, bufferIdx - 1);
409 this->cook(serial ? 0 : 512);
416 bool swapBuffer(
size_t bufferIdx1,
size_t bufferIdx2,
bool serial =
false)
418 const size_t b1 =
std::min(bufferIdx1, bufferIdx2);
419 const size_t b2 =
std::max(bufferIdx1, bufferIdx2);
420 if (b1 == b2 || b2 > mAuxBuffersPerLeaf)
return false;
422 if (this->isConstTree())
return false;
423 mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, b2-1);
425 mTask = boost::bind(&LeafManager::doSwapAuxBuffer, _1, _2, b1-1, b2-1);
427 this->cook(serial ? 0 : 512);
441 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf)
return false;
442 mTask = boost::bind(&LeafManager::doSyncAuxBuffer, _1, _2, bufferIdx - 1);
443 this->cook(serial ? 0 : 64);
452 switch (mAuxBuffersPerLeaf) {
453 case 0:
return false;
454 case 1: mTask = boost::bind(&LeafManager::doSyncAllBuffers1, _1, _2);
break;
455 case 2: mTask = boost::bind(&LeafManager::doSyncAllBuffers2, _1, _2);
break;
456 default: mTask = boost::bind(&LeafManager::doSyncAllBuffersN, _1, _2);
break;
458 this->cook(serial ? 0 : 64);
524 template<
typename LeafOp>
525 void foreach(
const LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
527 LeafTransformer<LeafOp> transform(op);
528 transform.run(this->leafRange(grainSize), threaded);
573 template<
typename LeafOp>
574 void reduce(LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
576 LeafReducer<LeafOp> transform(op);
577 transform.run(this->leafRange(grainSize), threaded);
585 template<
typename ArrayT>
588 typedef typename ArrayT::value_type T;
589 BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
590 typedef typename boost::mpl::if_<boost::is_const<typename boost::remove_pointer<T>::type>,
591 const LeafType, LeafType>::type LeafT;
594 if (boost::is_same<T, LeafT*>::value) {
595 array.resize(mLeafCount);
596 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
598 mTree->getNodes(array);
607 template<
typename ArrayT>
610 typedef typename ArrayT::value_type T;
611 BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
612 BOOST_STATIC_ASSERT(boost::is_const<
typename boost::remove_pointer<T>::type>::value);
615 if (boost::is_same<T, const LeafType*>::value) {
616 array.resize(mLeafCount);
617 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
619 mTree->getNodes(array);
635 size_t getPrefixSum(
size_t*& offsets,
size_t& size,
size_t grainSize=1)
const 637 if (offsets ==
nullptr || size < mLeafCount) {
639 offsets =
new size_t[mLeafCount];
643 if ( grainSize > 0 ) {
644 PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix);
646 for (
size_t i=0; i<mLeafCount; ++i) {
648 prefix += mLeafs[i]->onVoxelCount();
660 if (mTask) mTask(const_cast<LeafManager*>(
this), r);
670 typedef LeafType* value_type;
672 MyArray(value_type* array) : ptr(array) {}
673 void push_back(value_type leaf) { *ptr++ = leaf; }
678 const size_t leafCount = mTree->leafCount();
679 if (leafCount != mLeafCount) {
681 mLeafs = (leafCount == 0) ?
nullptr :
new LeafType*[leafCount];
682 mLeafCount = leafCount;
688 void initAuxBuffers(
bool serial)
690 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
691 if (auxBufferCount != mAuxBufferCount) {
692 delete [] mAuxBuffers;
693 mAuxBuffers = (auxBufferCount == 0) ?
nullptr :
new NonConstBufferType[auxBufferCount];
694 mAuxBufferCount = auxBufferCount;
696 this->syncAllBuffers(serial);
699 void cook(
size_t grainsize)
702 tbb::parallel_for(this->getRange(grainsize), *
this);
704 (*this)(this->getRange());
708 void doSwapLeafBuffer(
const RangeType& r,
size_t auxBufferIdx)
711 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
714 void doSwapAuxBuffer(
const RangeType& r,
size_t auxBufferIdx1,
size_t auxBufferIdx2)
716 for (
size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
717 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
721 void doSyncAuxBuffer(
const RangeType& r,
size_t auxBufferIdx)
723 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
724 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
728 void doSyncAllBuffers1(
const RangeType& r)
730 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
731 mAuxBuffers[n] = mLeafs[n]->buffer();
735 void doSyncAllBuffers2(
const RangeType& r)
737 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
738 const BufferType& leafBuffer = mLeafs[n]->buffer();
739 mAuxBuffers[2*n ] = leafBuffer;
740 mAuxBuffers[2*n+1] = leafBuffer;
744 void doSyncAllBuffersN(
const RangeType& r)
746 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
747 const BufferType& leafBuffer = mLeafs[n]->buffer();
748 for (
size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
754 template<
typename LeafOp>
755 struct LeafTransformer
757 LeafTransformer(
const LeafOp &leafOp) : mLeafOp(leafOp)
760 void run(
const LeafRange &range,
bool threaded)
const 762 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
764 void operator()(
const LeafRange &range)
const 768 const LeafOp mLeafOp;
773 template<
typename LeafOp>
776 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp), mOwnsOp(
false)
779 LeafReducer(
const LeafReducer &other, tbb::split)
780 : mLeafOp(
new LeafOp(*(other.mLeafOp), tbb::split())), mOwnsOp(
true)
783 ~LeafReducer() {
if (mOwnsOp)
delete mLeafOp; }
784 void run(
const LeafRange& range,
bool threaded)
786 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
790 LeafOp &op = *mLeafOp;
793 void join(
const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
801 PrefixSum(
const LeafRange& r,
size_t* offsets,
size_t& prefix)
804 tbb::parallel_for( r, *
this);
805 for (
size_t i=0, leafCount = r.
size(); i<leafCount; ++i) {
806 size_t tmp = offsets[i];
811 inline void operator()(
const LeafRange& r)
const {
813 mOffsets[i.pos()] = i->onVoxelCount();
819 typedef typename boost::function<void (LeafManager*, const RangeType&)> FuncType;
822 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
824 NonConstBufferType* mAuxBuffers;
826 const bool mIsMaster;
831 template<
typename TreeT>
840 LeafT**, BufT*,
size_t )
850 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED Definition: LeafManager.h:132
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:333
Useful traits for Tree types.
Definition: LeafManager.h:68
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:376
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:360
CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:122
LeafType LeafNodeType
Definition: LeafManager.h:123
size_t grainsize() const
Definition: LeafManager.h:192
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:239
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:157
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:127
LeafRange(LeafRange &r, tbb::split)
Definition: LeafManager.h:200
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:147
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:635
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Matrix multiplication.
Definition: Mat3.h:654
Iterator(const LeafRange &range, size_t pos)
Definition: LeafManager.h:138
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:364
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:115
TreeT::LeafCIter LeafIterType
Definition: LeafManager.h:74
boost::remove_const< ToType >::type Type
Definition: TreeIterator.h:66
TreeT TreeType
Definition: LeafManager.h:118
TreeT::RootNodeType RootNodeType
Definition: LeafManager.h:120
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:658
void getNodes(ArrayT &array)
Insert pointers to nodes of the specified type into the array.
Definition: LeafManager.h:586
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:450
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:90
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
Definition: LeafManager.h:223
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:351
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
Definition: LeafManager.h:337
#define OPENVDB_VERSION_NAME
Definition: version.h:43
ManagerT::LeafType LeafT
Definition: LeafManager.h:87
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:357
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:354
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:348
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:152
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:145
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:391
bool is_divisible() const
Definition: LeafManager.h:198
TreeT::ValueType ValueType
Definition: LeafManager.h:119
Definition: Exceptions.h:39
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:388
LeafManager< const TreeT > ManagerT
Definition: LeafManager.h:834
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:416
const LeafManager & leafManager() const
Definition: LeafManager.h:194
bool empty() const
Definition: LeafManager.h:196
void getNodes(ArrayT &array) const
Insert node pointers of the specified type into the array.
Definition: LeafManager.h:608
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:161
bool isValid() const
Return true if the position of this iterator is in a valid range.
Definition: LeafManager.h:159
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:328
Definition: LeafManager.h:84
ManagerT::RangeType RangeT
Definition: LeafManager.h:86
void rebuild(TreeType &tree, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:296
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:178
virtual ~LeafManager()
Definition: LeafManager.h:271
TreeT::LeafIter LeafIterType
Definition: LeafManager.h:70
Definition: Exceptions.h:92
uint64_t Index64
Definition: Types.h:56
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:318
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:321
ManagerT::BufferType BufT
Definition: LeafManager.h:88
Iterator end() const
Definition: LeafManager.h:188
void rebuild(bool serial=false)
(Re)initialize by resizing (if necessary) and repopulating the leaf array and by deleting existing au...
Definition: LeafManager.h:284
LeafType::Buffer NonConstBufferType
Definition: LeafManager.h:125
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:839
Iterator begin() const
Definition: LeafManager.h:186
ManagerT::RangeType RangeT
Definition: LeafManager.h:835
ManagerT::LeafType LeafT
Definition: LeafManager.h:836
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:439
size_t size() const
Definition: LeafManager.h:190
bool operator!=(const Iterator &other) const
Definition: LeafManager.h:166
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:301
ManagerT::BufferType BufT
Definition: LeafManager.h:837
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:405
Definition: LeafManager.h:135
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
leafmgr::TreeTraits< TreeT >::LeafIterType LeafIterType
Definition: LeafManager.h:124
Index32 Index
Definition: Types.h:57
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:574
CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:126
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:165
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:330
const LeafRange & leafRange() const
Definition: LeafManager.h:171
LeafManager(const LeafManager &other)
Definition: LeafManager.h:259
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:149
TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:121
bool operator==(const Iterator &other) const
Definition: LeafManager.h:170