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