HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 <tbb/blocked_range.h>
20 #include <tbb/parallel_for.h>
21 #include <tbb/parallel_reduce.h>
22 #include <functional>
23 #include <type_traits>
24 
25 
26 namespace openvdb {
28 namespace OPENVDB_VERSION_NAME {
29 namespace tree {
30 
31 namespace leafmgr {
32 
33 //@{
34 /// Useful traits for Tree types
35 template<typename TreeT> struct TreeTraits {
36  static const bool IsConstTree = false;
37  using LeafIterType = typename TreeT::LeafIter;
38 };
39 template<typename TreeT> struct TreeTraits<const TreeT> {
40  static const bool IsConstTree = true;
41  using LeafIterType = typename TreeT::LeafCIter;
42 };
43 //@}
44 
45 } // namespace leafmgr
46 
47 
48 /// This helper class implements LeafManager methods that need to be
49 /// specialized for const vs. non-const trees.
50 template<typename ManagerT>
52 {
53  using RangeT = typename ManagerT::RangeType;
54  using LeafT = typename ManagerT::LeafType;
55  using BufT = typename ManagerT::BufferType;
56 
57  static inline void doSwapLeafBuffer(const RangeT& r, size_t auxBufferIdx,
58  LeafT** leafs, BufT* bufs, size_t bufsPerLeaf)
59  {
60  for (size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
61  leafs[n]->swap(bufs[n * N + auxBufferIdx]);
62  }
63  }
64 };
65 
66 
67 ////////////////////////////////////////
68 
69 
70 /// @brief This class manages a linear array of pointers to a given tree's
71 /// leaf nodes, as well as optional auxiliary buffers (one or more per leaf)
72 /// that can be swapped with the leaf nodes' voxel data buffers.
73 /// @details The leaf array is useful for multithreaded computations over
74 /// leaf voxels in a tree with static topology but varying voxel values.
75 /// The auxiliary buffers are convenient for temporal integration.
76 /// Efficient methods are provided for multithreaded swapping and sync'ing
77 /// (i.e., copying the contents) of these buffers.
78 ///
79 /// @note Buffer index 0 denotes a leaf node's internal voxel data buffer.
80 /// Any auxiliary buffers are indexed starting from one.
81 template<typename TreeT>
83 {
84 public:
85  using TreeType = TreeT;
86  using ValueType = typename TreeT::ValueType;
87  using RootNodeType = typename TreeT::RootNodeType;
88  using NonConstLeafType = typename TreeType::LeafNodeType;
92  using NonConstBufferType = typename LeafType::Buffer;
94  using RangeType = tbb::blocked_range<size_t>; // leaf index range
95  static const Index DEPTH = 2; // root + leaf nodes
96 
98 
99  class LeafRange
100  {
101  public:
102  class Iterator
103  {
104  public:
105  Iterator(const LeafRange& range, size_t pos): mRange(range), mPos(pos)
106  {
107  assert(this->isValid());
108  }
109  Iterator(const Iterator&) = default;
110  Iterator& operator=(const Iterator&) = default;
111  /// Advance to the next leaf node.
112  Iterator& operator++() { ++mPos; return *this; }
113  /// Return a reference to the leaf node to which this iterator is pointing.
114  LeafType& operator*() const { return mRange.mLeafManager.leaf(mPos); }
115  /// Return a pointer to the leaf node to which this iterator is pointing.
116  LeafType* operator->() const { return &(this->operator*()); }
117  /// @brief Return the nth buffer for the leaf node to which this iterator is pointing,
118  /// where n = @a bufferIdx and n = 0 corresponds to the leaf node's own buffer.
119  BufferType& buffer(size_t bufferIdx)
120  {
121  return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
122  }
123  /// Return the index into the leaf array of the current leaf node.
124  size_t pos() const { return mPos; }
125  /// Return @c true if the position of this iterator is in a valid range.
126  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
127  /// Return @c true if this iterator is not yet exhausted.
128  bool test() const { return mPos < mRange.mEnd; }
129  /// Return @c true if this iterator is not yet exhausted.
130  operator bool() const { return this->test(); }
131  /// Return @c true if this iterator is exhausted.
132  bool empty() const { return !this->test(); }
133  bool operator!=(const Iterator& other) const
134  {
135  return (mPos != other.mPos) || (&mRange != &other.mRange);
136  }
137  bool operator==(const Iterator& other) const { return !(*this != other); }
138  const LeafRange& leafRange() const { return mRange; }
139 
140  private:
141  const LeafRange& mRange;
142  size_t mPos;
143  };// end Iterator
144 
145  LeafRange(size_t begin, size_t end, const LeafManager& leafManager, size_t grainSize=1)
146  : mEnd(end)
147  , mBegin(begin)
148  , mGrainSize(grainSize)
149  , mLeafManager(leafManager)
150  {
151  }
152 
153  Iterator begin() const {return Iterator(*this, mBegin);}
154 
155  Iterator end() const {return Iterator(*this, mEnd);}
156 
157  size_t size() const { return mEnd - mBegin; }
158 
159  size_t grainsize() const { return mGrainSize; }
160 
161  const LeafManager& leafManager() const { return mLeafManager; }
162 
163  bool empty() const {return !(mBegin < mEnd);}
164 
165  bool is_divisible() const {return mGrainSize < this->size();}
166 
168  : mEnd(r.mEnd)
169  , mBegin(doSplit(r))
170  , mGrainSize(r.mGrainSize)
171  , mLeafManager(r.mLeafManager)
172  {
173  }
174 
175  private:
176  size_t mEnd, mBegin, mGrainSize;
177  const LeafManager& mLeafManager;
178 
179  static size_t doSplit(LeafRange& r)
180  {
181  assert(r.is_divisible());
182  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
183  r.mEnd = middle;
184  return middle;
185  }
186  };// end of LeafRange
187 
188  /// @brief Constructor from a tree reference and an auxiliary buffer count
189  /// @note The default is no auxiliary buffers
190  LeafManager(TreeType& tree, size_t auxBuffersPerLeaf=0, bool serial=false)
191  : mTree(&tree)
192  , mLeafCount(0)
193  , mAuxBufferCount(0)
194  , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
195  , mLeafs(nullptr)
196  , mAuxBuffers(nullptr)
197  , mTask(nullptr)
198  , mIsMaster(true)
199  {
200  this->rebuild(serial);
201  }
202 
203  /// @brief Construct directly from an existing array of leafnodes.
204  /// @warning The leafnodes are implicitly assumed to exist in the
205  /// input @a tree.
207  size_t auxBuffersPerLeaf=0, bool serial=false)
208  : mTree(&tree)
209  , mLeafCount(end-begin)
210  , mAuxBufferCount(0)
211  , mAuxBuffersPerLeaf(auxBuffersPerLeaf)
212  , mLeafs(new LeafType*[mLeafCount])
213  , mAuxBuffers(nullptr)
214  , mTask(nullptr)
215  , mIsMaster(true)
216  {
217  size_t n = mLeafCount;
218  LeafType **target = mLeafs, **source = begin;
219  while (n--) *target++ = *source++;
220  if (auxBuffersPerLeaf) this->initAuxBuffers(serial);
221  }
222 
223  /// Shallow copy constructor called by tbb::parallel_for() threads
224  ///
225  /// @note This should never get called directly
226  LeafManager(const LeafManager& other)
227  : mTree(other.mTree)
228  , mLeafCount(other.mLeafCount)
229  , mAuxBufferCount(other.mAuxBufferCount)
230  , mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf)
231  , mLeafs(other.mLeafs)
232  , mAuxBuffers(other.mAuxBuffers)
233  , mTask(other.mTask)
234  , mIsMaster(false)
235  {
236  }
237 
238  virtual ~LeafManager()
239  {
240  if (mIsMaster) {
241  delete [] mLeafs;
242  delete [] mAuxBuffers;
243  }
244  }
245 
246  /// @brief (Re)initialize by resizing (if necessary) and repopulating the leaf array
247  /// and by deleting existing auxiliary buffers and allocating new ones.
248  /// @details Call this method if the tree's topology, and therefore the number
249  /// of leaf nodes, changes. New auxiliary buffers are initialized with copies
250  /// of corresponding leaf node buffers.
251  void rebuild(bool serial=false)
252  {
253  this->initLeafArray();
254  this->initAuxBuffers(serial);
255  }
256  //@{
257  /// Repopulate the leaf array and delete and reallocate auxiliary buffers.
258  void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
259  {
260  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
261  this->rebuild(serial);
262  }
263  void rebuild(TreeType& tree, bool serial=false)
264  {
265  mTree = &tree;
266  this->rebuild(serial);
267  }
268  void rebuild(TreeType& tree, size_t auxBuffersPerLeaf, bool serial=false)
269  {
270  mTree = &tree;
271  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
272  this->rebuild(serial);
273  }
274  //@}
275  /// @brief Change the number of auxiliary buffers.
276  /// @details If auxBuffersPerLeaf is 0, all existing auxiliary buffers are deleted.
277  /// New auxiliary buffers are initialized with copies of corresponding leaf node buffers.
278  /// This method does not rebuild the leaf array.
279  void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
280  {
281  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
282  this->initAuxBuffers(serial);
283  }
284  /// @brief Remove the auxiliary buffers, but don't rebuild the leaf array.
285  void removeAuxBuffers() { this->rebuildAuxBuffers(0); }
286 
287  /// @brief Remove the auxiliary buffers and rebuild the leaf array.
289  {
290  this->removeAuxBuffers();
291  this->initLeafArray();
292  }
293 
294  /// @brief Return the total number of allocated auxiliary buffers.
295  size_t auxBufferCount() const { return mAuxBufferCount; }
296  /// @brief Return the number of auxiliary buffers per leaf node.
297  size_t auxBuffersPerLeaf() const { return mAuxBuffersPerLeaf; }
298 
299  /// @brief Return the number of leaf nodes.
300  size_t leafCount() const { return mLeafCount; }
301 
302  /// @brief Return the number of active voxels in the leaf nodes.
303  /// @note Multi-threaded for better performance than Tree::activeLeafVoxelCount
305  {
306  return tbb::parallel_reduce(this->leafRange(), Index64(0),
307  [] (const LeafRange& range, Index64 sum) -> Index64 {
308  for (const auto& leaf: range) { sum += leaf.onVoxelCount(); }
309  return sum;
310  },
311  [] (Index64 n, Index64 m) -> Index64 { return n + m; });
312  }
313 
314  /// Return a const reference to tree associated with this manager.
315  const TreeType& tree() const { return *mTree; }
316 
317  /// Return a reference to the tree associated with this manager.
318  TreeType& tree() { return *mTree; }
319 
320  /// Return a const reference to root node associated with this manager.
321  const RootNodeType& root() const { return mTree->root(); }
322 
323  /// Return a reference to the root node associated with this manager.
324  RootNodeType& root() { return mTree->root(); }
325 
326  /// Return @c true if the tree associated with this manager is immutable.
327  bool isConstTree() const { return this->IsConstTree; }
328 
329  /// @brief Return a pointer to the leaf node at index @a leafIdx in the array.
330  /// @note For performance reasons no range check is performed (other than an assertion)!
331  LeafType& leaf(size_t leafIdx) const { assert(leafIdx<mLeafCount); return *mLeafs[leafIdx]; }
332 
333  /// @brief Return the leaf or auxiliary buffer for the leaf node at index @a leafIdx.
334  /// If @a bufferIdx is zero, return the leaf buffer, otherwise return the nth
335  /// auxiliary buffer, where n = @a bufferIdx - 1.
336  ///
337  /// @note For performance reasons no range checks are performed on the inputs
338  /// (other than assertions)! Since auxiliary buffers, unlike leaf buffers,
339  /// might not exist, be especially careful when specifying the @a bufferIdx.
340  /// @note For const trees, this method always returns a reference to a const buffer.
341  /// It is safe to @c const_cast and modify any auxiliary buffer (@a bufferIdx > 0),
342  /// but it is not safe to modify the leaf buffer (@a bufferIdx = 0).
343  BufferType& getBuffer(size_t leafIdx, size_t bufferIdx) const
344  {
345  assert(leafIdx < mLeafCount);
346  assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
347  return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
348  : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
349  }
350 
351  /// @brief Return a @c tbb::blocked_range of leaf array indices.
352  ///
353  /// @note Consider using leafRange() instead, which provides access methods
354  /// to leaf nodes and buffers.
355  RangeType getRange(size_t grainsize = 1) const { return RangeType(0, mLeafCount, grainsize); }
356 
357  /// Return a TBB-compatible LeafRange.
358  LeafRange leafRange(size_t grainsize = 1) const
359  {
360  return LeafRange(0, mLeafCount, *this, grainsize);
361  }
362 
363  /// @brief Swap each leaf node's buffer with the nth corresponding auxiliary buffer,
364  /// where n = @a bufferIdx.
365  /// @return @c true if the swap was successful
366  /// @param bufferIdx index of the buffer that will be swapped with
367  /// the corresponding leaf node buffer
368  /// @param serial if false, swap buffers in parallel using multiple threads.
369  /// @note Recall that the indexing of auxiliary buffers is 1-based, since
370  /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes
371  /// the first auxiliary buffer.
372  bool swapLeafBuffer(size_t bufferIdx, bool serial = false)
373  {
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);
378  return true;//success
379  }
380  /// @brief Swap any two buffers for each leaf node.
381  /// @note Recall that the indexing of auxiliary buffers is 1-based, since
382  /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes
383  /// the first auxiliary buffer.
384  bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial = false)
385  {
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;
390  if (b1 == 0) {
391  if (this->isConstTree()) return false;
392  mTask = std::bind(&LeafManager::doSwapLeafBuffer, ph::_1, ph::_2, b2-1);
393  } else {
394  mTask = std::bind(&LeafManager::doSwapAuxBuffer, ph::_1, ph::_2, b1-1, b2-1);
395  }
396  this->cook(serial ? 0 : 512);
397  return true;//success
398  }
399 
400  /// @brief Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
401  /// @return @c true if the sync was successful
402  /// @param bufferIdx index of the buffer that will contain a
403  /// copy of the corresponding leaf node buffer
404  /// @param serial if false, sync buffers in parallel using multiple threads.
405  /// @note Recall that the indexing of auxiliary buffers is 1-based, since
406  /// buffer index 0 denotes the leaf node buffer. So buffer index 1 denotes
407  /// the first auxiliary buffer.
408  bool syncAuxBuffer(size_t bufferIdx, bool serial = false)
409  {
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);
414  return true;//success
415  }
416 
417  /// @brief Sync up all auxiliary buffers with their corresponding leaf node buffers.
418  /// @return true if the sync was successful
419  /// @param serial if false, sync buffers in parallel using multiple threads.
420  bool syncAllBuffers(bool serial = false)
421  {
422  namespace ph = std::placeholders;
423  switch (mAuxBuffersPerLeaf) {
424  case 0: return false;//nothing to do
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;
428  }
429  this->cook(serial ? 0 : 64);
430  return true;//success
431  }
432 
433  /// @brief Threaded method that applies a user-supplied functor
434  /// to each leaf node in the LeafManager.
435  ///
436  /// @details The user-supplied functor needs to define the methods
437  /// required for tbb::parallel_for.
438  ///
439  /// @param op user-supplied functor, see examples for interface details.
440  /// @param threaded optional toggle to disable threading, on by default.
441  /// @param grainSize optional parameter to specify the grainsize
442  /// for threading, one by default.
443  ///
444  /// @warning The functor object is deep-copied to create TBB tasks.
445  /// This allows the function to use non-thread-safe members
446  /// like a ValueAccessor.
447  ///
448  /// @par Example:
449  /// @code
450  /// // Functor to offset a tree's voxel values with values from another tree.
451  /// template<typename TreeType>
452  /// struct OffsetOp
453  /// {
454  /// using Accessor = tree::ValueAccessor<const TreeType>;
455  ///
456  /// OffsetOp(const TreeType& tree): mRhsTreeAcc(tree) {}
457  ///
458  /// template <typename LeafNodeType>
459  /// void operator()(LeafNodeType &lhsLeaf, size_t) const
460  /// {
461  /// const LeafNodeType *rhsLeaf = mRhsTreeAcc.probeConstLeaf(lhsLeaf.origin());
462  /// if (rhsLeaf) {
463  /// typename LeafNodeType::ValueOnIter iter = lhsLeaf.beginValueOn();
464  /// for (; iter; ++iter) {
465  /// iter.setValue(iter.getValue() + rhsLeaf->getValue(iter.pos()));
466  /// }
467  /// }
468  /// }
469  /// Accessor mRhsTreeAcc;
470  /// };
471  ///
472  /// // usage:
473  /// tree::LeafManager<FloatTree> leafNodes(lhsTree);
474  /// leafNodes.foreach(OffsetOp<FloatTree>(rhsTree));
475  ///
476  /// // A functor that performs a min operation between different auxiliary buffers.
477  /// template<typename LeafManagerType>
478  /// struct MinOp
479  /// {
480  /// using BufferType = typename LeafManagerType::BufferType;
481  ///
482  /// MinOp(LeafManagerType& leafNodes): mLeafs(leafNodes) {}
483  ///
484  /// template <typename LeafNodeType>
485  /// void operator()(LeafNodeType &leaf, size_t leafIndex) const
486  /// {
487  /// // get the first buffer
488  /// BufferType& buffer = mLeafs.getBuffer(leafIndex, 1);
489  ///
490  /// // min ...
491  /// }
492  /// LeafManagerType& mLeafs;
493  /// };
494  /// @endcode
495  template<typename LeafOp>
496  void foreach(const LeafOp& op, bool threaded = true, size_t grainSize=1)
497  {
498  LeafTransformer<LeafOp> transform(op);
499  transform.run(this->leafRange(grainSize), threaded);
500  }
501 
502  /// @brief Threaded method that applies a user-supplied functor
503  /// to each leaf node in the LeafManager. Unlike foreach
504  /// (defined above) this method performs a reduction on
505  /// all the leaf nodes.
506  ///
507  /// @details The user-supplied functor needs to define the methods
508  /// required for tbb::parallel_reduce.
509  ///
510  /// @param op user-supplied functor, see examples for interface details.
511  /// @param threaded optional toggle to disable threading, on by default.
512  /// @param grainSize optional parameter to specify the grainsize
513  /// for threading, one by default.
514  ///
515  /// @warning The functor object is deep-copied to create TBB tasks.
516  /// This allows the function to use non-thread-safe members
517  /// like a ValueAccessor.
518  ///
519  /// @par Example:
520  /// @code
521  /// // Functor to count the number of negative (active) leaf values
522  /// struct CountOp
523  /// {
524  /// CountOp() : mCounter(0) {}
525  /// CountOp(const CountOp &other) : mCounter(other.mCounter) {}
526  /// CountOp(const CountOp &other, tbb::split) : mCounter(0) {}
527  /// template <typename LeafNodeType>
528  /// void operator()(LeafNodeType &leaf, size_t)
529  /// {
530  /// typename LeafNodeType::ValueOnIter iter = leaf.beginValueOn();
531  /// for (; iter; ++iter) if (*iter < 0.0f) ++mCounter;
532  /// }
533  /// void join(const CountOp &other) {mCounter += other.mCounter;}
534  /// size_t mCounter;
535  /// };
536  ///
537  /// // usage:
538  /// tree::LeafManager<FloatTree> leafNodes(tree);
539  /// MinValueOp min;
540  /// leafNodes.reduce(min);
541  /// std::cerr << "Number of negative active voxels = " << min.mCounter << std::endl;
542  ///
543  /// @endcode
544  template<typename LeafOp>
545  void reduce(LeafOp& op, bool threaded = true, size_t grainSize=1)
546  {
547  LeafReducer<LeafOp> transform(op);
548  transform.run(this->leafRange(grainSize), threaded);
549  }
550 
551 
552  /// @brief Insert pointers to nodes of the specified type into the array.
553  /// @details The type of node pointer is defined by the type
554  /// ArrayT::value_type. If the node type is a LeafNode the nodes
555  /// are inserted from this LeafManager, else of the corresponding tree.
556  template<typename ArrayT>
557  void getNodes(ArrayT& array)
558  {
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;
563 
566  array.resize(mLeafCount);
567  for (size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
568  } else {
569  mTree->getNodes(array);
570  }
572  }
573 
574  /// @brief Insert node pointers of the specified type into the array.
575  /// @details The type of node pointer is defined by the type
576  /// ArrayT::value_type. If the node type is a LeafNode the nodes
577  /// are inserted from this LeafManager, else of the corresponding tree.
578  template<typename ArrayT>
579  void getNodes(ArrayT& array) const
580  {
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");
585 
588  array.resize(mLeafCount);
589  for (size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
590  } else {
591  mTree->getNodes(array);
592  }
594  }
595 
596  /// @brief Generate a linear array of prefix sums of offsets into the
597  /// active voxels in the leafs. So @a offsets[n]+m is the offset to the
598  /// mth active voxel in the nth leaf node (useful for
599  /// user-managed value buffers, e.g. in tools/LevelSetAdvect.h).
600  /// @return The total number of active values in the leaf nodes
601  /// @param offsets array of prefix sums of offsets to active voxels
602  /// @param size on input, the size of @a offsets; on output, its new size
603  /// @param grainSize optional grain size for threading
604  /// @details If @a offsets is @c nullptr or @a size is smaller than the
605  /// total number of active voxels (the return value) then @a offsets
606  /// is reallocated and @a size equals the total number of active voxels.
607  size_t getPrefixSum(size_t*& offsets, size_t& size, size_t grainSize=1) const
608  {
609  if (offsets == nullptr || size < mLeafCount) {
610  delete [] offsets;
611  offsets = new size_t[mLeafCount];
612  size = mLeafCount;
613  }
614  size_t prefix = 0;
615  if ( grainSize > 0 ) {
616  PrefixSum tmp(this->leafRange( grainSize ), offsets, prefix);
617  } else {// serial
618  for (size_t i=0; i<mLeafCount; ++i) {
619  offsets[i] = prefix;
620  prefix += mLeafs[i]->onVoxelCount();
621  }
622  }
623  return prefix;
624  }
625 
626  ////////////////////////////////////////////////////////////////////////////////////
627  // All methods below are for internal use only and should never be called directly
628 
629  /// Used internally by tbb::parallel_for() - never call it directly!
630  void operator()(const RangeType& r) const
631  {
632  if (mTask) mTask(const_cast<LeafManager*>(this), r);
633  else OPENVDB_THROW(ValueError, "task is undefined");
634  }
635 
636 private:
637 
638  // This a simple wrapper for a c-style array so it mimics the api
639  // of a std container, e.g. std::vector or std::deque, and can be
640  // passed to Tree::getNodes().
641  struct MyArray {
642  using value_type = LeafType*;//required by Tree::getNodes
643  value_type* ptr;
644  MyArray(value_type* array) : ptr(array) {}
645  void push_back(value_type leaf) { *ptr++ = leaf; }//required by Tree::getNodes
646  };
647 
648  void initLeafArray()
649  {
650  const size_t leafCount = mTree->leafCount();
651  if (leafCount != mLeafCount) {
652  delete [] mLeafs;
653  mLeafs = (leafCount == 0) ? nullptr : new LeafType*[leafCount];
654  mLeafCount = leafCount;
655  }
656  MyArray a(mLeafs);
657  mTree->getNodes(a);
658  }
659 
660  void initAuxBuffers(bool serial)
661  {
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;
667  }
668  this->syncAllBuffers(serial);
669  }
670 
671  void cook(size_t grainsize)
672  {
673  if (grainsize>0) {
674  tbb::parallel_for(this->getRange(grainsize), *this);
675  } else {
676  (*this)(this->getRange());
677  }
678  }
679 
680  void doSwapLeafBuffer(const RangeType& r, size_t auxBufferIdx)
681  {
683  r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
684  }
685 
686  void doSwapAuxBuffer(const RangeType& r, size_t auxBufferIdx1, size_t auxBufferIdx2)
687  {
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]);
690  }
691  }
692 
693  void doSyncAuxBuffer(const RangeType& r, size_t auxBufferIdx)
694  {
695  for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
696  mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
697  }
698  }
699 
700  void doSyncAllBuffers1(const RangeType& r)
701  {
702  for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
703  mAuxBuffers[n] = mLeafs[n]->buffer();
704  }
705  }
706 
707  void doSyncAllBuffers2(const RangeType& r)
708  {
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;
713  }
714  }
715 
716  void doSyncAllBuffersN(const RangeType& r)
717  {
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;
721  }
722  }
723 
724  /// @brief Private member class that applies a user-defined
725  /// functor to perform parallel_for on all the leaf nodes.
726  template<typename LeafOp>
727  struct LeafTransformer
728  {
729  LeafTransformer(const LeafOp &leafOp) : mLeafOp(leafOp)
730  {
731  }
732  void run(const LeafRange &range, bool threaded) const
733  {
734  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
735  }
736  void operator()(const LeafRange &range) const
737  {
738  for (typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
739  }
740  const LeafOp mLeafOp;
741  };// LeafTransformer
742 
743  /// @brief Private member class that applies a user-defined
744  /// functor to perform parallel_reduce on all the leaf nodes.
745  template<typename LeafOp>
746  struct LeafReducer
747  {
748  LeafReducer(LeafOp &leafOp) : mLeafOp(&leafOp), mOwnsOp(false)
749  {
750  }
751  LeafReducer(const LeafReducer &other, tbb::split)
752  : mLeafOp(new LeafOp(*(other.mLeafOp), tbb::split())), mOwnsOp(true)
753  {
754  }
755  ~LeafReducer() { if (mOwnsOp) delete mLeafOp; }
756  void run(const LeafRange& range, bool threaded)
757  {
758  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
759  }
760  void operator()(const LeafRange& range)
761  {
762  LeafOp &op = *mLeafOp;//local registry
763  for (typename LeafRange::Iterator it = range.begin(); it; ++it) op(*it, it.pos());
764  }
765  void join(const LeafReducer& other) { mLeafOp->join(*(other.mLeafOp)); }
766  LeafOp *mLeafOp;
767  const bool mOwnsOp;
768  };// LeafReducer
769 
770  // Helper class to compute a prefix sum of offsets to active voxels
771  struct PrefixSum
772  {
773  PrefixSum(const LeafRange& r, size_t* offsets, size_t& prefix)
774  : mOffsets(offsets)
775  {
776  tbb::parallel_for( r, *this);
777  for (size_t i=0, leafCount = r.size(); i<leafCount; ++i) {
778  size_t tmp = offsets[i];
779  offsets[i] = prefix;
780  prefix += tmp;
781  }
782  }
783  inline void operator()(const LeafRange& r) const {
784  for (typename LeafRange::Iterator i = r.begin(); i; ++i) {
785  mOffsets[i.pos()] = i->onVoxelCount();
786  }
787  }
788  size_t* mOffsets;
789  };// PrefixSum
790 
791  using FuncType = typename std::function<void (LeafManager*, const RangeType&)>;
792 
793  TreeType* mTree;
794  size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
795  LeafType** mLeafs;//array of LeafNode pointers
796  NonConstBufferType* mAuxBuffers;//array of auxiliary buffers
797  FuncType mTask;
798  const bool mIsMaster;
799 };//end of LeafManager class
800 
801 
802 // Partial specializations of LeafManager methods for const trees
803 template<typename TreeT>
805 {
807  using RangeT = typename ManagerT::RangeType;
808  using LeafT = typename ManagerT::LeafType;
809  using BufT = typename ManagerT::BufferType;
810 
811  static inline void doSwapLeafBuffer(const RangeT&, size_t /*auxBufferIdx*/,
812  LeafT**, BufT*, size_t /*bufsPerLeaf*/)
813  {
814  // Buffers can't be swapped into const trees.
815  }
816 };
817 
818 } // namespace tree
819 } // namespace OPENVDB_VERSION_NAME
820 } // namespace openvdb
821 
822 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
void rebuild(TreeType &tree, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:263
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:268
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count.
Definition: LeafManager.h:190
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))
Definition: parallel.h:153
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:545
GLenum GLint * range
Definition: glew.h:3500
SYS_FORCE_INLINE const_iterator begin() const
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:145
GLsizeiptr size
Definition: glew.h:1681
typename CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:93
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:358
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:57
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:116
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
GLuint GLenum GLenum transform
Definition: glew.h:14742
GLenum target
Definition: glew.h:2865
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:315
GLuint GLsizei const GLuint const GLintptr * offsets
Definition: glew.h:4117
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:318
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:324
GLsizei GLsizei GLchar * source
Definition: glew.h:1832
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:166
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:630
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:321
const GLdouble * m
Definition: glew.h:9124
uint64 value_type
Definition: GA_PrimCompat.h:29
void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
Change the number of auxiliary buffers.
Definition: LeafManager.h:279
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:94
bool isValid() const
Return true if the position of this iterator is in a valid range.
Definition: LeafManager.h:126
SYS_FORCE_INLINE const_iterator end() const
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:300
typename TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:88
void OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
typename LeafType::Buffer NonConstBufferType
Definition: LeafManager.h:92
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:114
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
*But if you need a or simply need to know when the task has note that the like this
Definition: thread.h:639
typename TreeT::RootNodeType RootNodeType
Definition: LeafManager.h:87
typename std::remove_const< ToType >::type Type
Definition: Types.h:298
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
GLuint GLuint end
Definition: glew.h:1253
GLsizei n
Definition: glew.h:4040
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:132
void getNodes(ArrayT &array)
Insert pointers to nodes of the specified type into the array.
Definition: LeafManager.h:557
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:607
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 leafmgr::TreeTraits< TreeT >::LeafIterType LeafIterType
Definition: LeafManager.h:91
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:124
const GLenum * bufs
Definition: glew.h:1823
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:355
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
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:327
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:408
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
SIMD Intrinsic Headers.
Definition: Platform.h:114
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:295
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:297
const void * ptr(const T *p)
Definition: format.h:3292
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
GA_API const UT_StringHolder N
void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:258
arg_join< It, char > join(It begin, It end, string_view sep)
Definition: format.h:3326
GLenum array
Definition: glew.h:9066
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:115
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:331
#define const
Definition: zconf.h:214
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:112
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
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
void getNodes(ArrayT &array) const
Insert node pointers of the specified type into the array.
Definition: LeafManager.h:579
typename CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:89
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:811
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:112
GLsizei const GLfloat * value
Definition: glew.h:1849
Index64 activeLeafVoxelCount() const
Return the number of active voxels in the leaf nodes.
Definition: LeafManager.h:304
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:285
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:384
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
type
Definition: core.h:528
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
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:128
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:288
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:420