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