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>
52 template<
typename ManagerT>
55 using RangeT =
typename ManagerT::RangeType;
56 using LeafT =
typename ManagerT::LeafType;
57 using BufT =
typename ManagerT::BufferType;
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>
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(); }
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;
207 , mLeafCount(end-begin)
210 , mLeafPtrs(new
LeafType*[mLeafCount])
211 , mLeafs(mLeafPtrs.get())
213 size_t n = mLeafCount;
215 while (n--) *target++ = *source++;
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);
269 this->initAuxBuffers(serial);
278 this->initLeafArray(serial);
295 for (
const auto&
leaf: range) { sum +=
leaf.onVoxelCount(); }
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;
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)
486 transform.run(this->
leafRange(grainSize), threaded);
531 template<
typename LeafOp>
532 void reduce(LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
535 transform.run(this->
leafRange(grainSize), threaded);
538 template<
typename ArrayT>
543 using LeafT =
typename std::conditional<std::is_const<
548 array.resize(mLeafCount);
549 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
551 mTree->getNodes(array);
556 template<
typename ArrayT>
562 "argument to getNodes() must be an array of const node pointers");
566 array.resize(mLeafCount);
567 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
569 mTree->getNodes(array);
587 if (offsets ==
nullptr || size < mLeafCount) {
589 offsets =
new size_t[mLeafCount];
593 if ( grainSize > 0 ) {
594 PrefixSum tmp(this->
leafRange( grainSize ), offsets, prefix);
596 for (
size_t i=0; i<mLeafCount; ++i) {
598 prefix += mLeafs[i]->onVoxelCount();
610 if (mTask) mTask(const_cast<LeafManager*>(
this), r);
616 void initLeafArray(
bool serial =
false)
621 using NonConstLeafParentT =
typename NodeChainT::template Get<1>;
624 std::deque<LeafParentT*> leafParents;
625 mTree->getNodes(leafParents);
629 std::vector<Index32> leafCounts;
631 leafCounts.reserve(leafParents.size());
632 for (LeafParentT* leafParent : leafParents) {
633 leafCounts.push_back(leafParent->childCount());
636 leafCounts.resize(leafParents.size());
641 tbb::blocked_range<size_t>(0, leafParents.size(), 64),
642 [&](tbb::blocked_range<size_t>&
range)
644 for (
size_t i = range.begin(); i < range.end(); i++) {
645 leafCounts[i] = leafParents[i]->childCount();
653 for (
size_t i = 1; i < leafCounts.size(); i++) {
654 leafCounts[i] += leafCounts[i-1];
657 const size_t leafCount = leafCounts.empty() ? 0 : leafCounts.back();
661 if (leafCount != mLeafCount) {
663 mLeafPtrs.reset(
new LeafType*[leafCount]);
664 mLeafs = mLeafPtrs.get();
672 if (mLeafCount == 0)
return;
678 for (LeafParentT* leafParent : leafParents) {
679 for (
auto iter = leafParent->beginChildOn(); iter; ++iter) {
680 *leafPtr++ = &iter.getValue();
685 tbb::blocked_range<size_t>(0, leafParents.size()),
686 [&](tbb::blocked_range<size_t>& range)
688 size_t i = range.begin();
690 if (i > 0) leafPtr += leafCounts[i-1];
691 for ( ; i < range.end(); i++) {
692 for (
auto iter = leafParents[i]->beginChildOn(); iter; ++iter) {
693 *leafPtr++ = &iter.getValue();
701 void initAuxBuffers(
bool serial)
704 if (auxBufferCount != mAuxBufferCount) {
705 if (auxBufferCount > 0) {
707 mAuxBuffers = mAuxBufferPtrs.get();
709 mAuxBufferPtrs.reset();
710 mAuxBuffers =
nullptr;
717 void cook(
size_t grainsize)
726 void doSwapLeafBuffer(
const RangeType&
r,
size_t auxBufferIdx)
729 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
732 void doSwapAuxBuffer(
const RangeType&
r,
size_t auxBufferIdx1,
size_t auxBufferIdx2)
734 for (
size_t N = mAuxBuffersPerLeaf,
n =
N*r.
begin(),
m =
N*r.
end();
n !=
m;
n+=
N) {
735 mAuxBuffers[
n + auxBufferIdx1].swap(mAuxBuffers[
n + auxBufferIdx2]);
739 void doSyncAuxBuffer(
const RangeType& r,
size_t auxBufferIdx)
741 for (
size_t n = r.begin(),
m = r.end(),
N = mAuxBuffersPerLeaf;
n !=
m; ++
n) {
742 mAuxBuffers[
n*
N + auxBufferIdx] = mLeafs[
n]->buffer();
746 void doSyncAllBuffers1(
const RangeType& r)
748 for (
size_t n = r.begin(),
m = r.end();
n !=
m; ++
n) {
749 mAuxBuffers[
n] = mLeafs[
n]->buffer();
753 void doSyncAllBuffers2(
const RangeType& r)
755 for (
size_t n = r.begin(),
m = r.end();
n !=
m; ++
n) {
756 const BufferType& leafBuffer = mLeafs[
n]->buffer();
757 mAuxBuffers[2*
n ] = leafBuffer;
758 mAuxBuffers[2*
n+1] = leafBuffer;
762 void doSyncAllBuffersN(
const RangeType& r)
764 for (
size_t n = r.begin(),
m = r.end(),
N = mAuxBuffersPerLeaf;
n !=
m; ++
n) {
765 const BufferType& leafBuffer = mLeafs[
n]->buffer();
766 for (
size_t i=
n*
N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
772 template<
typename LeafOp>
773 struct LeafTransformer
775 LeafTransformer(
const LeafOp &leafOp) : mLeafOp(leafOp)
778 void run(
const LeafRange &range,
bool threaded)
const
784 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
786 const LeafOp mLeafOp;
791 template<
typename LeafOp>
794 LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp)
797 LeafReducer(
const LeafReducer &other,
tbb::split)
798 : mLeafOpPtr(std::make_unique<LeafOp>(*(other.mLeafOp), tbb::
split()))
799 , mLeafOp(mLeafOpPtr.get())
802 void run(
const LeafRange& range,
bool threaded)
804 threaded ? tbb::parallel_reduce(range, *
this) : (*
this)(range);
808 LeafOp &op = *mLeafOp;
809 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos());
811 void join(
const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
812 std::unique_ptr<LeafOp> mLeafOpPtr;
813 LeafOp *mLeafOp =
nullptr;
819 PrefixSum(
const LeafRange& r,
size_t*
offsets,
size_t& prefix)
823 for (
size_t i=0, leafCount = r.size(); i<
leafCount; ++i) {
824 size_t tmp = offsets[i];
829 inline void operator()(
const LeafRange& r)
const {
830 for (
typename LeafRange::Iterator i = r.begin(); i; ++i) {
831 mOffsets[i.pos()] = i->onVoxelCount();
837 using FuncType =
typename std::function<void (LeafManager*, const RangeType&)>;
840 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
841 std::unique_ptr<LeafType*[]> mLeafPtrs;
843 std::unique_ptr<NonConstBufferType[]> mAuxBufferPtrs;
845 FuncType mTask =
nullptr;
850 template<
typename TreeT>
869 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
void rebuild(TreeType &tree, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
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.
SYS_FORCE_INLINE const_iterator begin() const
typename TreeType::ValueType ValueType
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
typename ManagerT::LeafType LeafT
OPENVDB_DEPRECATED_MESSAGE("Use Tree::getNodes()") void getNodes(ArrayT &array) const
typename CopyConstness< TreeType, NonConstBufferType >::Type BufferType
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
const LeafManager & leafManager() const
Iterator & operator=(const Iterator &)=default
const TreeType & tree() const
Return a const reference to tree associated with this manager.
GLuint GLsizei const GLuint const GLintptr * offsets
TreeType & tree()
Return a reference to the tree associated with this manager.
bool operator!=(const Iterator &other) const
typename ManagerT::BufferType BufT
RootNodeType & root()
Return a reference to the root node associated with this manager.
#define OPENVDB_USE_VERSION_NAMESPACE
bool is_divisible() const
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
**But if you need a or simply need to know when the task has note that the like this
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
Change the number of auxiliary buffers.
tbb::blocked_range< size_t > RangeType
bool isValid() const
Return true if the position of this iterator is in a valid range.
GLuint GLenum GLenum transform
SYS_FORCE_INLINE const_iterator end() const
size_t leafCount() const
Return the number of leaf nodes.
typename TreeType::LeafNodeType NonConstLeafType
typename SubtreeT::template Append< HeadT > Type
void rebuildLeafArray(bool serial=false)
Remove the auxiliary buffers and rebuild the leaf array.
void OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
Iterator(const LeafRange &range, size_t pos)
typename LeafType::Buffer NonConstBufferType
typename ManagerT::LeafType LeafT
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
BufferType & buffer(size_t bufferIdx)
Return the nth buffer for the leaf node to which this iterator is pointing, where n = bufferIdx and n...
typename TreeType::RootNodeType RootNodeType
GLsizei GLsizei GLchar * source
typename std::remove_const< ToType >::type Type
LeafManager(TreeType &tree, LeafType **begin, LeafType **end, size_t auxBuffersPerLeaf=0, bool serial=false)
Construct directly from an existing array of leafnodes.
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
bool empty() const
Return true if this iterator is exhausted.
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).
typename TreeT::LeafIter LeafIterType
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
typename leafmgr::TreeTraits< TreeType >::LeafIterType LeafIterType
typename ManagerT::BufferType BufT
size_t pos() const
Return the index into the leaf array of the current leaf node.
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
LeafManager(const LeafManager &other)
bool swapLeafBuffer(size_t bufferIdx, bool serial=false)
Swap each leaf node's buffer with the nth corresponding auxiliary buffer, where n = bufferIdx...
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
The root node of an OpenVDB tree.
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
typename ManagerT::RangeType RangeT
static const bool IsConstTree
typename TreeT::LeafCIter LeafIterType
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
LeafRange(LeafRange &r, tbb::split)
GA_API const UT_StringHolder N
static const bool IsConstTree
GLsizei const GLfloat * value
void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
typename ManagerT::RangeType RangeT
OPENVDB_DEPRECATED_MESSAGE("Use Tree::getNodes()") void getNodes(ArrayT &array)
Useful traits for Tree types.
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Iterator & operator++()
Advance to the next leaf node.
void rebuild(bool serial=false)
(Re)initialize by resizing (if necessary) and repopulating the leaf array and by deleting existing au...
bool operator==(const Iterator &other) const
typename CopyConstness< TreeType, NonConstLeafType >::Type LeafType
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
const LeafRange & leafRange() const
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
#define OPENVDB_THROW(exception, message)
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...
bool test() const
Return true if this iterator is not yet exhausted.
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.