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