OpenVDB  10.0.0
NodeManager.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 tree/NodeManager.h
5 ///
6 /// @authors Ken Museth, Dan Bailey
7 ///
8 /// @brief NodeManager produces linear arrays of all tree nodes
9 /// allowing for efficient threading and bottom-up processing.
10 ///
11 /// @note A NodeManager can be constructed from a Tree or LeafManager.
12 
13 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
14 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
15 
16 #include <openvdb/Types.h>
17 #include <tbb/parallel_for.h>
18 #include <tbb/parallel_reduce.h>
19 #include <deque>
20 
21 
22 namespace openvdb {
24 namespace OPENVDB_VERSION_NAME {
25 namespace tree {
26 
27 // Produce linear arrays of all tree nodes, to facilitate efficient threading
28 // and bottom-up processing.
29 template<typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
31 
32 
33 // Produce linear arrays of all tree nodes lazily, to facilitate efficient threading
34 // of topology-changing top-down workflows.
35 template<typename TreeOrLeafManagerT, Index _LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
37 
38 
39 ////////////////////////////////////////
40 
41 
42 // This is a dummy node filtering class used by the NodeManager class to match
43 // the internal filtering interface used by the DynamicNodeManager.
44 struct NodeFilter
45 {
46  static bool valid(size_t) { return true; }
47 }; // struct NodeFilter
48 
49 
50 /// @brief This class caches tree nodes of a specific type in a linear array.
51 ///
52 /// @note It is for internal use and should rarely be used directly.
53 template<typename NodeT>
54 class NodeList
55 {
56 public:
57  NodeList() = default;
58 
59  NodeT& operator()(size_t n) const { assert(n<mNodeCount); return *(mNodes[n]); }
60 
61  NodeT*& operator[](size_t n) { assert(n<mNodeCount); return mNodes[n]; }
62 
63  Index64 nodeCount() const { return mNodeCount; }
64 
65  void clear()
66  {
67  mNodePtrs.reset();
68  mNodes = nullptr;
69  mNodeCount = 0;
70  }
71 
72  // initialize this node list from the provided root node
73  template <typename RootT>
74  bool initRootChildren(RootT& root)
75  {
76  // Allocate (or deallocate) the node pointer array
77 
78  size_t nodeCount = root.childCount();
79 
80  if (nodeCount != mNodeCount) {
81  if (nodeCount > 0) {
82  mNodePtrs.reset(new NodeT*[nodeCount]);
83  mNodes = mNodePtrs.get();
84  } else {
85  mNodePtrs.reset();
86  mNodes = nullptr;
87  }
88  mNodeCount = nodeCount;
89  }
90 
91  if (mNodeCount == 0) return false;
92 
93  // Populate the node pointers
94 
95  NodeT** nodePtr = mNodes;
96  for (auto iter = root.beginChildOn(); iter; ++iter) {
97  *nodePtr++ = &iter.getValue();
98  }
99 
100  return true;
101  }
102 
103  // initialize this node list from another node list containing the parent nodes
104  template <typename ParentsT, typename NodeFilterT>
105  bool initNodeChildren(ParentsT& parents, const NodeFilterT& nodeFilter = NodeFilterT(), bool serial = false)
106  {
107  // Compute the node counts for each node
108 
109  std::vector<Index32> nodeCounts;
110  if (serial) {
111  nodeCounts.reserve(parents.nodeCount());
112  for (size_t i = 0; i < parents.nodeCount(); i++) {
113  if (!nodeFilter.valid(i)) nodeCounts.push_back(0);
114  else nodeCounts.push_back(parents(i).childCount());
115  }
116  } else {
117  nodeCounts.resize(parents.nodeCount());
118  tbb::parallel_for(
119  // with typical node sizes and SSE enabled, there are only a handful
120  // of instructions executed per-operation with a default grainsize
121  // of 1, so increase to 64 to reduce parallel scheduling overhead
122  tbb::blocked_range<Index64>(0, parents.nodeCount(), /*grainsize=*/64),
123  [&](tbb::blocked_range<Index64>& range)
124  {
125  for (Index64 i = range.begin(); i < range.end(); i++) {
126  if (!nodeFilter.valid(i)) nodeCounts[i] = 0;
127  else nodeCounts[i] = parents(i).childCount();
128  }
129  }
130  );
131  }
132 
133  // Turn node counts into a cumulative histogram and obtain total node count
134 
135  for (size_t i = 1; i < nodeCounts.size(); i++) {
136  nodeCounts[i] += nodeCounts[i-1];
137  }
138 
139  const size_t nodeCount = nodeCounts.empty() ? 0 : nodeCounts.back();
140 
141  // Allocate (or deallocate) the node pointer array
142 
143  if (nodeCount != mNodeCount) {
144  if (nodeCount > 0) {
145  mNodePtrs.reset(new NodeT*[nodeCount]);
146  mNodes = mNodePtrs.get();
147  } else {
148  mNodePtrs.reset();
149  mNodes = nullptr;
150  }
151  mNodeCount = nodeCount;
152  }
153 
154  if (mNodeCount == 0) return false;
155 
156  // Populate the node pointers
157 
158  if (serial) {
159  NodeT** nodePtr = mNodes;
160  for (size_t i = 0; i < parents.nodeCount(); i++) {
161  if (!nodeFilter.valid(i)) continue;
162  for (auto iter = parents(i).beginChildOn(); iter; ++iter) {
163  *nodePtr++ = &iter.getValue();
164  }
165  }
166  } else {
167  tbb::parallel_for(
168  tbb::blocked_range<Index64>(0, parents.nodeCount()),
169  [&](tbb::blocked_range<Index64>& range)
170  {
171  Index64 i = range.begin();
172  NodeT** nodePtr = mNodes;
173  if (i > 0) nodePtr += nodeCounts[i-1];
174  for ( ; i < range.end(); i++) {
175  if (!nodeFilter.valid(i)) continue;
176  for (auto iter = parents(i).beginChildOn(); iter; ++iter) {
177  *nodePtr++ = &iter.getValue();
178  }
179  }
180  }
181  );
182  }
183 
184  return true;
185  }
186 
187  class NodeRange
188  {
189  public:
190 
191  NodeRange(size_t begin, size_t end, const NodeList& nodeList, size_t grainSize=1):
192  mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
193 
194  NodeRange(NodeRange& r, tbb::split):
195  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
196  mNodeList(r.mNodeList) {}
197 
198  size_t size() const { return mEnd - mBegin; }
199 
200  size_t grainsize() const { return mGrainSize; }
201 
202  const NodeList& nodeList() const { return mNodeList; }
203 
204  bool empty() const {return !(mBegin < mEnd);}
205 
206  bool is_divisible() const {return mGrainSize < this->size();}
207 
208  class Iterator
209  {
210  public:
211  Iterator(const NodeRange& range, size_t pos): mRange(range), mPos(pos)
212  {
213  assert(this->isValid());
214  }
215  Iterator(const Iterator&) = default;
216  Iterator& operator=(const Iterator&) = default;
217  /// Advance to the next node.
218  Iterator& operator++() { ++mPos; return *this; }
219  /// Return a reference to the node to which this iterator is pointing.
220  NodeT& operator*() const { return mRange.mNodeList(mPos); }
221  /// Return a pointer to the node to which this iterator is pointing.
222  NodeT* operator->() const { return &(this->operator*()); }
223  /// Return the index into the list of the current node.
224  size_t pos() const { return mPos; }
225  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
226  /// Return @c true if this iterator is not yet exhausted.
227  bool test() const { return mPos < mRange.mEnd; }
228  /// Return @c true if this iterator is not yet exhausted.
229  operator bool() const { return this->test(); }
230  /// Return @c true if this iterator is exhausted.
231  bool empty() const { return !this->test(); }
232  bool operator!=(const Iterator& other) const
233  {
234  return (mPos != other.mPos) || (&mRange != &other.mRange);
235  }
236  bool operator==(const Iterator& other) const { return !(*this != other); }
237  const NodeRange& nodeRange() const { return mRange; }
238 
239  private:
240  const NodeRange& mRange;
241  size_t mPos;
242  };// NodeList::NodeRange::Iterator
243 
244  Iterator begin() const {return Iterator(*this, mBegin);}
245 
246  Iterator end() const {return Iterator(*this, mEnd);}
247 
248  private:
249  size_t mEnd, mBegin, mGrainSize;
250  const NodeList& mNodeList;
251 
252  static size_t doSplit(NodeRange& r)
253  {
254  assert(r.is_divisible());
255  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
256  r.mEnd = middle;
257  return middle;
258  }
259  };// NodeList::NodeRange
260 
261  /// Return a TBB-compatible NodeRange.
262  NodeRange nodeRange(size_t grainsize = 1) const
263  {
264  return NodeRange(0, this->nodeCount(), *this, grainsize);
265  }
266 
267  template<typename NodeOp>
268  void foreach(const NodeOp& op, bool threaded = true, size_t grainSize=1)
269  {
270  NodeTransformerCopy<NodeOp> transform(op); // always deep-copies the op
271  transform.run(this->nodeRange(grainSize), threaded);
272  }
273 
274  template<typename NodeOp>
275  void reduce(NodeOp& op, bool threaded = true, size_t grainSize=1)
276  {
277  NodeReducer<NodeOp> transform(op);
278  transform.run(this->nodeRange(grainSize), threaded);
279  }
280 
281  // identical to foreach except the operator() method has a node index and
282  // the operator is referenced instead of copied in NodeTransformer
283  template<typename NodeOp>
284  void foreachWithIndex(const NodeOp& op, bool threaded = true, size_t grainSize=1)
285  {
286  NodeTransformer<NodeOp, OpWithIndex> transform(op);
287  transform.run(this->nodeRange(grainSize), threaded);
288  }
289 
290  // identical to reduce except the operator() method has a node index
291  template<typename NodeOp>
292  void reduceWithIndex(NodeOp& op, bool threaded = true, size_t grainSize=1)
293  {
294  NodeReducer<NodeOp, OpWithIndex> transform(op);
295  transform.run(this->nodeRange(grainSize), threaded);
296  }
297 
298 private:
299 
300  // default execution in the NodeManager ignores the node index
301  // given by the iterator position
302  struct OpWithoutIndex
303  {
304  template <typename T>
305  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter); }
306  };
307 
308  // execution in the DynamicNodeManager matches that of the LeafManager in
309  // passing through the node index given by the iterator position
310  struct OpWithIndex
311  {
312  template <typename T>
313  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter, iter.pos()); }
314  };
315 
316  // Private struct of NodeList that performs parallel_for
317  template<typename NodeOp, typename OpT = OpWithoutIndex>
318  struct NodeTransformerCopy
319  {
320  NodeTransformerCopy(const NodeOp& nodeOp) : mNodeOp(nodeOp)
321  {
322  }
323  void run(const NodeRange& range, bool threaded = true)
324  {
325  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
326  }
327  void operator()(const NodeRange& range) const
328  {
329  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
330  OpT::template eval(mNodeOp, it);
331  }
332  }
333  const NodeOp mNodeOp;
334  };// NodeList::NodeTransformerCopy
335 
336  // Private struct of NodeList that performs parallel_for
337  template<typename NodeOp, typename OpT = OpWithoutIndex>
338  struct NodeTransformer
339  {
340  NodeTransformer(const NodeOp& nodeOp) : mNodeOp(nodeOp)
341  {
342  }
343  void run(const NodeRange& range, bool threaded = true)
344  {
345  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
346  }
347  void operator()(const NodeRange& range) const
348  {
349  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
350  OpT::template eval(mNodeOp, it);
351  }
352  }
353  const NodeOp& mNodeOp;
354  };// NodeList::NodeTransformer
355 
356  // Private struct of NodeList that performs parallel_reduce
357  template<typename NodeOp, typename OpT = OpWithoutIndex>
358  struct NodeReducer
359  {
360  NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp)
361  {
362  }
363  NodeReducer(const NodeReducer& other, tbb::split)
364  : mNodeOpPtr(std::make_unique<NodeOp>(*(other.mNodeOp), tbb::split()))
365  , mNodeOp(mNodeOpPtr.get())
366  {
367  }
368  void run(const NodeRange& range, bool threaded = true)
369  {
370  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
371  }
372  void operator()(const NodeRange& range)
373  {
374  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
375  OpT::template eval(*mNodeOp, it);
376  }
377  }
378  void join(const NodeReducer& other)
379  {
380  mNodeOp->join(*(other.mNodeOp));
381  }
382  std::unique_ptr<NodeOp> mNodeOpPtr;
383  NodeOp *mNodeOp = nullptr;
384  };// NodeList::NodeReducer
385 
386 
387 protected:
388  size_t mNodeCount = 0;
389  std::unique_ptr<NodeT*[]> mNodePtrs;
390  NodeT** mNodes = nullptr;
391 };// NodeList
392 
393 
394 /////////////////////////////////////////////
395 
396 
397 /// @brief This class is a link in a chain that each caches tree nodes
398 /// of a specific type in a linear array.
399 ///
400 /// @note It is for internal use and should rarely be used directly.
401 template<typename NodeT, Index LEVEL>
403 {
404 public:
405  using NonConstChildNodeType = typename NodeT::ChildNodeType;
407 
408  NodeManagerLink() = default;
409 
410  void clear() { mList.clear(); mNext.clear(); }
411 
412  template <typename RootT>
413  void initRootChildren(RootT& root, bool serial = false)
414  {
415  mList.initRootChildren(root);
416  mNext.initNodeChildren(mList, serial);
417  }
418 
419  template<typename ParentsT>
420  void initNodeChildren(ParentsT& parents, bool serial = false)
421  {
422  mList.initNodeChildren(parents, NodeFilter(), serial);
423  mNext.initNodeChildren(mList, serial);
424  }
425 
426  Index64 nodeCount() const { return mList.nodeCount() + mNext.nodeCount(); }
427 
429  {
430  return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
431  }
432 
433  template<typename NodeOp>
434  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
435  {
436  mNext.foreachBottomUp(op, threaded, grainSize);
437  mList.foreach(op, threaded, grainSize);
438  }
439 
440  template<typename NodeOp>
441  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
442  {
443  mList.foreach(op, threaded, grainSize);
444  mNext.foreachTopDown(op, threaded, grainSize);
445  }
446 
447  template<typename NodeOp>
448  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
449  {
450  mNext.reduceBottomUp(op, threaded, grainSize);
451  mList.reduce(op, threaded, grainSize);
452  }
453 
454  template<typename NodeOp>
455  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
456  {
457  mList.reduce(op, threaded, grainSize);
458  mNext.reduceTopDown(op, threaded, grainSize);
459  }
460 
461 protected:
464 };// NodeManagerLink class
465 
466 
467 ////////////////////////////////////////
468 
469 
470 /// @private
471 /// @brief Specialization that terminates the chain of cached tree nodes
472 /// @note It is for internal use and should rarely be used directly.
473 template<typename NodeT>
474 class NodeManagerLink<NodeT, 0>
475 {
476 public:
477  NodeManagerLink() = default;
478 
479  /// @brief Clear all the cached tree nodes
480  void clear() { mList.clear(); }
481 
482  template <typename RootT>
483  void initRootChildren(RootT& root, bool /*serial*/ = false) { mList.initRootChildren(root); }
484 
485  template<typename ParentsT>
486  void initNodeChildren(ParentsT& parents, bool serial = false) { mList.initNodeChildren(parents, NodeFilter(), serial); }
487 
488  Index64 nodeCount() const { return mList.nodeCount(); }
489 
490  Index64 nodeCount(Index) const { return mList.nodeCount(); }
491 
492  template<typename NodeOp>
493  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
494  {
495  mList.foreach(op, threaded, grainSize);
496  }
497 
498  template<typename NodeOp>
499  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
500  {
501  mList.foreach(op, threaded, grainSize);
502  }
503 
504  template<typename NodeOp>
505  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
506  {
507  mList.reduce(op, threaded, grainSize);
508  }
509 
510  template<typename NodeOp>
511  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
512  {
513  mList.reduce(op, threaded, grainSize);
514  }
515 
516 protected:
517  NodeList<NodeT> mList;
518 };// NodeManagerLink class
519 
520 
521 ////////////////////////////////////////
522 
523 
524 /// @brief To facilitate threading over the nodes of a tree, cache
525 /// node pointers in linear arrays, one for each level of the tree.
526 ///
527 /// @details This implementation works with trees of any depth, but
528 /// optimized specializations are provided for the most typical tree depths.
529 template<typename TreeOrLeafManagerT, Index _LEVELS>
530 class NodeManager
531 {
532 public:
533  static const Index LEVELS = _LEVELS;
534  static_assert(LEVELS > 0,
535  "expected instantiation of template specialization"); // see specialization below
536  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
538  using NonConstChildNodeType = typename RootNodeType::ChildNodeType;
540  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
541 
542  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
543  : mRoot(tree.root())
544  {
545  this->rebuild(serial);
546  }
547 
548  NodeManager(const NodeManager&) = delete;
549 
550  /// @brief Clear all the cached tree nodes
551  void clear() { mChain.clear(); }
552 
553  /// @brief Clear and recache all the tree nodes from the
554  /// tree. This is required if tree nodes have been added or removed.
555  void rebuild(bool serial = false) { mChain.initRootChildren(mRoot, serial); }
556 
557  /// @brief Return a reference to the root node.
558  const RootNodeType& root() const { return mRoot; }
559 
560  /// @brief Return the total number of cached nodes (excluding the root node)
561  Index64 nodeCount() const { return mChain.nodeCount(); }
562 
563  /// @brief Return the number of cached nodes at level @a i, where
564  /// 0 corresponds to the lowest level.
565  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
566 
567  //@{
568  /// @brief Threaded method that applies a user-supplied functor
569  /// to all the nodes in the tree.
570  ///
571  /// @param op user-supplied functor, see examples for interface details.
572  /// @param threaded optional toggle to disable threading, on by default.
573  /// @param grainSize optional parameter to specify the grainsize
574  /// for threading, one by default.
575  ///
576  /// @warning The functor object is deep-copied to create TBB tasks.
577  ///
578  /// @par Example:
579  /// @code
580  /// // Functor to offset all the inactive values of a tree. Note
581  /// // this implementation also illustrates how different
582  /// // computation can be applied to the different node types.
583  /// template<typename TreeType>
584  /// struct OffsetOp
585  /// {
586  /// using ValueT = typename TreeT::ValueType;
587  /// using RootT = typename TreeT::RootNodeType;
588  /// using LeafT = typename TreeT::LeafNodeType;
589  /// OffsetOp(const ValueT& v) : mOffset(v) {}
590  ///
591  /// // Processes the root node. Required by the NodeManager
592  /// void operator()(RootT& root) const
593  /// {
594  /// for (typename RootT::ValueOffIter i = root.beginValueOff(); i; ++i) *i += mOffset;
595  /// }
596  /// // Processes the leaf nodes. Required by the NodeManager
597  /// void operator()(LeafT& leaf) const
598  /// {
599  /// for (typename LeafT::ValueOffIter i = leaf.beginValueOff(); i; ++i) *i += mOffset;
600  /// }
601  /// // Processes the internal nodes. Required by the NodeManager
602  /// template<typename NodeT>
603  /// void operator()(NodeT& node) const
604  /// {
605  /// for (typename NodeT::ValueOffIter i = node.beginValueOff(); i; ++i) *i += mOffset;
606  /// }
607  /// private:
608  /// const ValueT mOffset;
609  /// };
610  ///
611  /// // usage:
612  /// OffsetOp<FloatTree> op(3.0f);
613  /// tree::NodeManager<FloatTree> nodes(tree);
614  /// nodes.foreachBottomUp(op);
615  ///
616  /// // or if a LeafManager already exists
617  /// using T = tree::LeafManager<FloatTree>;
618  /// OffsetOp<T> op(3.0f);
619  /// tree::NodeManager<T> nodes(leafManager);
620  /// nodes.foreachBottomUp(op);
621  ///
622  /// @endcode
623  template<typename NodeOp>
624  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
625  {
626  mChain.foreachBottomUp(op, threaded, grainSize);
627  op(mRoot);
628  }
629 
630  template<typename NodeOp>
631  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
632  {
633  op(mRoot);
634  mChain.foreachTopDown(op, threaded, grainSize);
635  }
636 
637  //@}
638 
639  //@{
640  /// @brief Threaded method that processes nodes with a user supplied functor
641  ///
642  /// @param op user-supplied functor, see examples for interface details.
643  /// @param threaded optional toggle to disable threading, on by default.
644  /// @param grainSize optional parameter to specify the grainsize
645  /// for threading, one by default.
646  ///
647  /// @warning The functor object is deep-copied to create TBB tasks.
648  ///
649  /// @par Example:
650  /// @code
651  /// // Functor to count nodes in a tree
652  /// template<typename TreeType>
653  /// struct NodeCountOp
654  /// {
655  /// NodeCountOp() : nodeCount(TreeType::DEPTH, 0), totalCount(0)
656  /// {
657  /// }
658  /// NodeCountOp(const NodeCountOp& other, tbb::split) :
659  /// nodeCount(TreeType::DEPTH, 0), totalCount(0)
660  /// {
661  /// }
662  /// void join(const NodeCountOp& other)
663  /// {
664  /// for (size_t i = 0; i < nodeCount.size(); ++i) {
665  /// nodeCount[i] += other.nodeCount[i];
666  /// }
667  /// totalCount += other.totalCount;
668  /// }
669  /// // do nothing for the root node
670  /// void operator()(const typename TreeT::RootNodeType& node)
671  /// {
672  /// }
673  /// // count the internal and leaf nodes
674  /// template<typename NodeT>
675  /// void operator()(const NodeT& node)
676  /// {
677  /// ++(nodeCount[NodeT::LEVEL]);
678  /// ++totalCount;
679  /// }
680  /// std::vector<openvdb::Index64> nodeCount;
681  /// openvdb::Index64 totalCount;
682  /// };
683  ///
684  /// // usage:
685  /// NodeCountOp<FloatTree> op;
686  /// tree::NodeManager<FloatTree> nodes(tree);
687  /// nodes.reduceBottomUp(op);
688  ///
689  /// // or if a LeafManager already exists
690  /// NodeCountOp<FloatTree> op;
691  /// using T = tree::LeafManager<FloatTree>;
692  /// T leafManager(tree);
693  /// tree::NodeManager<T> nodes(leafManager);
694  /// nodes.reduceBottomUp(op);
695  ///
696  /// @endcode
697  template<typename NodeOp>
698  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
699  {
700  mChain.reduceBottomUp(op, threaded, grainSize);
701  op(mRoot);
702  }
703 
704  template<typename NodeOp>
705  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
706  {
707  op(mRoot);
708  mChain.reduceTopDown(op, threaded, grainSize);
709  }
710  //@}
711 
712 protected:
715 };// NodeManager class
716 
717 
718 ////////////////////////////////////////////
719 
720 
721 // Wraps a user-supplied DynamicNodeManager operator and stores the return
722 // value of the operator() method to the index of the node in a bool array
723 template <typename OpT>
725 {
726  explicit ForeachFilterOp(const OpT& op, openvdb::Index64 size)
727  : mOp(op)
728  , mValidPtr(std::make_unique<bool[]>(size))
729  , mValid(mValidPtr.get()) { }
730 
732  : mOp(other.mOp)
733  , mValid(other.mValid) { }
734 
735  template<typename NodeT>
736  void operator()(NodeT& node, size_t idx) const
737  {
738  mValid[idx] = mOp(node, idx);
739  }
740 
741  bool valid(size_t idx) const { return mValid[idx]; }
742 
743  const OpT& op() const { return mOp; }
744 
745 private:
746  const OpT& mOp;
747  std::unique_ptr<bool[]> mValidPtr;
748  bool* mValid = nullptr;
749 }; // struct ForeachFilterOp
750 
751 
752 // Wraps a user-supplied DynamicNodeManager operator and stores the return
753 // value of the operator() method to the index of the node in a bool array
754 template <typename OpT>
756 {
758  : mOp(&op)
759  , mValidPtr(std::make_unique<bool[]>(size))
760  , mValid(mValidPtr.get()) { }
761 
763  : mOp(other.mOp)
764  , mValid(other.mValid) { }
765 
766  ReduceFilterOp(const ReduceFilterOp& other, tbb::split)
767  : mOpPtr(std::make_unique<OpT>(*(other.mOp), tbb::split()))
768  , mOp(mOpPtr.get())
769  , mValid(other.mValid) { }
770 
771  template<typename NodeT>
772  void operator()(NodeT& node, size_t idx) const
773  {
774  mValid[idx] = (*mOp)(node, idx);
775  }
776 
777  void join(const ReduceFilterOp& other)
778  {
779  mOp->join(*(other.mOp));
780  }
781 
782  bool valid(size_t idx) const
783  {
784  return mValid[idx];
785  }
786 
787  OpT& op() { return *mOp; }
788 
789 private:
790  std::unique_ptr<OpT> mOpPtr;
791  OpT* mOp = nullptr;
792  std::unique_ptr<bool[]> mValidPtr;
793  bool* mValid = nullptr;
794 }; // struct ReduceFilterOp
795 
796 
797 /// @brief This class is a link in a chain that each caches tree nodes
798 /// of a specific type in a linear array.
799 ///
800 /// @note It is for internal use and should rarely be used directly.
801 template<typename NodeT, Index LEVEL>
803 {
804 public:
805  using NonConstChildNodeType = typename NodeT::ChildNodeType;
807 
808  DynamicNodeManagerLink() = default;
809 
810  template<typename NodeOpT, typename RootT>
811  void foreachTopDown(const NodeOpT& op, RootT& root, bool threaded,
812  size_t leafGrainSize, size_t nonLeafGrainSize)
813  {
814  if (!op(root, /*index=*/0)) return;
815  if (!mList.initRootChildren(root)) return;
816  ForeachFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
817  mList.foreachWithIndex(filterOp, threaded, LEVEL == 0 ? leafGrainSize : nonLeafGrainSize);
818  mNext.foreachTopDownRecurse(filterOp, mList, threaded, leafGrainSize, nonLeafGrainSize);
819  }
820 
821  template<typename FilterOpT, typename ParentT>
822  void foreachTopDownRecurse(const FilterOpT& filterOp, ParentT& parent, bool threaded,
823  size_t leafGrainSize, size_t nonLeafGrainSize)
824  {
825  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
826  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
827  mList.foreachWithIndex(childFilterOp, threaded, LEVEL == 0 ? leafGrainSize : nonLeafGrainSize);
828  mNext.foreachTopDownRecurse(childFilterOp, mList, threaded, leafGrainSize, nonLeafGrainSize);
829  }
830 
831  template<typename NodeOpT, typename RootT>
832  void reduceTopDown(NodeOpT& op, RootT& root, bool threaded,
833  size_t leafGrainSize, size_t nonLeafGrainSize)
834  {
835  if (!op(root, /*index=*/0)) return;
836  if (!mList.initRootChildren(root)) return;
837  ReduceFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
838  mList.reduceWithIndex(filterOp, threaded, LEVEL == 0 ? leafGrainSize : nonLeafGrainSize);
839  mNext.reduceTopDownRecurse(filterOp, mList, threaded, leafGrainSize, nonLeafGrainSize);
840  }
841 
842  template<typename FilterOpT, typename ParentT>
843  void reduceTopDownRecurse(FilterOpT& filterOp, ParentT& parent, bool threaded,
844  size_t leafGrainSize, size_t nonLeafGrainSize)
845  {
846  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
847  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
848  mList.reduceWithIndex(childFilterOp, threaded, LEVEL == 0 ? leafGrainSize : nonLeafGrainSize);
849  mNext.reduceTopDownRecurse(childFilterOp, mList, threaded, leafGrainSize, nonLeafGrainSize);
850  }
851 
852 protected:
855 };// DynamicNodeManagerLink class
856 
857 
858 /// @private
859 /// @brief Specialization that terminates the chain of cached tree nodes
860 /// @note It is for internal use and should rarely be used directly.
861 template<typename NodeT>
862 class DynamicNodeManagerLink<NodeT, 0>
863 {
864 public:
865  DynamicNodeManagerLink() = default;
866 
867  template<typename NodeFilterOp, typename ParentT>
868  void foreachTopDownRecurse(const NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded,
869  size_t leafGrainSize, size_t /*nonLeafGrainSize*/)
870  {
871  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
872  mList.foreachWithIndex(nodeFilterOp.op(), threaded, leafGrainSize);
873  }
874 
875  template<typename NodeFilterOp, typename ParentT>
876  void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded,
877  size_t leafGrainSize, size_t /*nonLeafGrainSize*/)
878  {
879  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
880  mList.reduceWithIndex(nodeFilterOp.op(), threaded, leafGrainSize);
881  }
882 
883 protected:
884  NodeList<NodeT> mList;
885 };// DynamicNodeManagerLink class
886 
887 
888 template<typename TreeOrLeafManagerT, Index _LEVELS>
889 class DynamicNodeManager
890 {
891 public:
892  static const Index LEVELS = _LEVELS;
893  static_assert(LEVELS > 0,
894  "expected instantiation of template specialization"); // see specialization below
895  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
897  using NonConstChildNodeType = typename RootNodeType::ChildNodeType;
899  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
900 
901  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
902 
903  DynamicNodeManager(const DynamicNodeManager&) = delete;
904 
905  /// @brief Return a reference to the root node.
906  const NonConstRootNodeType& root() const { return mRoot; }
907 
908  /// @brief Threaded method that applies a user-supplied functor
909  /// to all the nodes in the tree.
910  ///
911  /// @param op user-supplied functor, see examples for interface details.
912  /// @param threaded optional toggle to disable threading, on by default.
913  /// @param leafGrainSize optional parameter to specify the grainsize
914  /// for threading over leaf nodes, one by default.
915  /// @param nonLeafGrainSize optional parameter to specify the grainsize
916  /// for threading over non-leaf nodes, one by default.
917  ///
918  /// @note There are two key differences to the interface of the
919  /// user-supplied functor to the NodeManager class - (1) the operator()
920  /// method aligns with the LeafManager class in expecting the index of the
921  /// node in a linear array of identical node types, (2) the operator()
922  /// method returns a boolean termination value with true indicating that
923  /// children of this node should be processed, false indicating the
924  /// early-exit termination should occur.
925  ///
926  /// @note Unlike the NodeManager, the foreach() method of the
927  /// DynamicNodeManager uses copy-by-reference for the user-supplied functor.
928  /// This can be an issue when using a shared Accessor or shared Sampler in
929  /// the operator as they are not inherently thread-safe. For these use
930  /// cases, it is recommended to create the Accessor or Sampler in the
931  /// operator execution itself.
932  ///
933  /// @par Example:
934  /// @code
935  /// // Functor to densify the first child node in a linear array. Note
936  /// // this implementation also illustrates how different
937  /// // computation can be applied to the different node types.
938  ///
939  /// template<typename TreeT>
940  /// struct DensifyOp
941  /// {
942  /// using RootT = typename TreeT::RootNodeType;
943  /// using LeafT = typename TreeT::LeafNodeType;
944  ///
945  /// DensifyOp() = default;
946  ///
947  /// // Processes the root node. Required by the DynamicNodeManager
948  /// bool operator()(RootT&, size_t) const { return true; }
949  ///
950  /// // Processes the internal nodes. Required by the DynamicNodeManager
951  /// template<typename NodeT>
952  /// bool operator()(NodeT& node, size_t idx) const
953  /// {
954  /// // densify child
955  /// for (auto iter = node.cbeginValueAll(); iter; ++iter) {
956  /// const openvdb::Coord ijk = iter.getCoord();
957  /// node.addChild(new typename NodeT::ChildNodeType(iter.getCoord(), NodeT::LEVEL, true));
958  /// }
959  /// // early-exit termination for all non-zero index children
960  /// return idx == 0;
961  /// }
962  /// // Processes the leaf nodes. Required by the DynamicNodeManager
963  /// bool operator()(LeafT&, size_t) const
964  /// {
965  /// return true;
966  /// }
967  /// };// DensifyOp
968  ///
969  /// // usage:
970  /// DensifyOp<FloatTree> op;
971  /// tree::DynamicNodeManager<FloatTree> nodes(tree);
972  /// nodes.foreachTopDown(op);
973  ///
974  /// @endcode
975  template<typename NodeOp>
976  void foreachTopDown(const NodeOp& op, bool threaded = true,
977  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
978  {
979  mChain.foreachTopDown(op, mRoot, threaded, leafGrainSize, nonLeafGrainSize);
980  }
981 
982  /// @brief Threaded method that processes nodes with a user supplied functor
983  ///
984  /// @param op user-supplied functor, see examples for interface details.
985  /// @param threaded optional toggle to disable threading, on by default.
986  /// @param leafGrainSize optional parameter to specify the grainsize
987  /// for threading over leaf nodes, one by default.
988  /// @param nonLeafGrainSize optional parameter to specify the grainsize
989  /// for threading over non-leaf nodes, one by default.
990  ///
991  /// @note There are two key differences to the interface of the
992  /// user-supplied functor to the NodeManager class - (1) the operator()
993  /// method aligns with the LeafManager class in expecting the index of the
994  /// node in a linear array of identical node types, (2) the operator()
995  /// method returns a boolean termination value with true indicating that
996  /// children of this node should be processed, false indicating the
997  /// early-exit termination should occur.
998  ///
999  /// @par Example:
1000  /// @code
1001  /// // Functor to count nodes in a tree
1002  /// template<typename TreeType>
1003  /// struct NodeCountOp
1004  /// {
1005  /// NodeCountOp() : nodeCount(TreeType::DEPTH, 0), totalCount(0)
1006  /// {
1007  /// }
1008  /// NodeCountOp(const NodeCountOp& other, tbb::split) :
1009  /// nodeCount(TreeType::DEPTH, 0), totalCount(0)
1010  /// {
1011  /// }
1012  /// void join(const NodeCountOp& other)
1013  /// {
1014  /// for (size_t i = 0; i < nodeCount.size(); ++i) {
1015  /// nodeCount[i] += other.nodeCount[i];
1016  /// }
1017  /// totalCount += other.totalCount;
1018  /// }
1019  /// // do nothing for the root node
1020  /// bool operator()(const typename TreeT::RootNodeType& node, size_t)
1021  /// {
1022  /// return true;
1023  /// }
1024  /// // count the internal and leaf nodes
1025  /// template<typename NodeT>
1026  /// bool operator()(const NodeT& node, size_t)
1027  /// {
1028  /// ++(nodeCount[NodeT::LEVEL]);
1029  /// ++totalCount;
1030  /// return true;
1031  /// }
1032  /// std::vector<openvdb::Index64> nodeCount;
1033  /// openvdb::Index64 totalCount;
1034  /// };
1035  ///
1036  /// // usage:
1037  /// NodeCountOp<FloatTree> op;
1038  /// tree::DynamicNodeManager<FloatTree> nodes(tree);
1039  /// nodes.reduceTopDown(op);
1040  ///
1041  /// @endcode
1042  template<typename NodeOp>
1043  void reduceTopDown(NodeOp& op, bool threaded = true,
1044  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1045  {
1046  mChain.reduceTopDown(op, mRoot, threaded, leafGrainSize, nonLeafGrainSize);
1047  }
1048 
1049 protected:
1052 };// DynamicNodeManager class
1053 
1054 
1055 
1056 ////////////////////////////////////////////
1057 
1058 
1059 /// @private
1060 /// Template specialization of the NodeManager with no caching of nodes
1061 template<typename TreeOrLeafManagerT>
1062 class NodeManager<TreeOrLeafManagerT, 0>
1063 {
1064 public:
1065  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1067  static const Index LEVELS = 0;
1068 
1069  NodeManager(TreeOrLeafManagerT& tree, bool /*serial*/ = false) : mRoot(tree.root()) { }
1070 
1071  NodeManager(const NodeManager&) = delete;
1072 
1073  /// @brief Clear all the cached tree nodes
1074  void clear() {}
1075 
1076  /// @brief Clear and recache all the tree nodes from the
1077  /// tree. This is required if tree nodes have been added or removed.
1078  void rebuild(bool /*serial*/ = false) { }
1079 
1080  /// @brief Return a reference to the root node.
1081  const RootNodeType& root() const { return mRoot; }
1082 
1083  /// @brief Return the total number of cached nodes (excluding the root node)
1084  Index64 nodeCount() const { return 0; }
1085 
1086  Index64 nodeCount(Index) const { return 0; }
1087 
1088  template<typename NodeOp>
1089  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
1090 
1091  template<typename NodeOp>
1092  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
1093 
1094  template<typename NodeOp>
1095  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
1096 
1097  template<typename NodeOp>
1098  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
1099 
1100 protected:
1101  RootNodeType& mRoot;
1102 }; // NodeManager<0>
1103 
1104 
1105 ////////////////////////////////////////////
1106 
1107 
1108 /// @private
1109 /// Template specialization of the NodeManager with one level of nodes
1110 template<typename TreeOrLeafManagerT>
1111 class NodeManager<TreeOrLeafManagerT, 1>
1112 {
1113 public:
1114  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1116  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1117  static const Index LEVELS = 1;
1118 
1119  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
1120  : mRoot(tree.root())
1121  {
1122  this->rebuild(serial);
1123  }
1124 
1125  NodeManager(const NodeManager&) = delete;
1126 
1127  /// @brief Clear all the cached tree nodes
1128  void clear() { mList0.clear(); }
1129 
1130  /// @brief Clear and recache all the tree nodes from the
1131  /// tree. This is required if tree nodes have been added or removed.
1132  void rebuild(bool /*serial*/ = false) { mList0.initRootChildren(mRoot); }
1133 
1134  /// @brief Return a reference to the root node.
1135  const RootNodeType& root() const { return mRoot; }
1136 
1137  /// @brief Return the total number of cached nodes (excluding the root node)
1138  Index64 nodeCount() const { return mList0.nodeCount(); }
1139 
1140  /// @brief Return the number of cached nodes at level @a i, where
1141  /// 0 corresponds to the lowest level.
1142  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
1143 
1144  template<typename NodeOp>
1145  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1146  {
1147  mList0.foreach(op, threaded, grainSize);
1148  op(mRoot);
1149  }
1150 
1151  template<typename NodeOp>
1152  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1153  {
1154  op(mRoot);
1155  mList0.foreach(op, threaded, grainSize);
1156  }
1157 
1158  template<typename NodeOp>
1159  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1160  {
1161  mList0.reduce(op, threaded, grainSize);
1162  op(mRoot);
1163  }
1164 
1165  template<typename NodeOp>
1166  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1167  {
1168  op(mRoot);
1169  mList0.reduce(op, threaded, grainSize);
1170  }
1171 
1172 protected:
1173  using NodeT1 = RootNodeType;
1174  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1175  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1176  using ListT0 = NodeList<NodeT0>;
1177 
1178  NodeT1& mRoot;
1179  ListT0 mList0;
1180 }; // NodeManager<1>
1181 
1182 
1183 ////////////////////////////////////////////
1184 
1185 
1186 /// @private
1187 /// Template specialization of the NodeManager with two levels of nodes
1188 template<typename TreeOrLeafManagerT>
1189 class NodeManager<TreeOrLeafManagerT, 2>
1190 {
1191 public:
1192  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1194  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1195  static const Index LEVELS = 2;
1196 
1197  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1198  {
1199  this->rebuild(serial);
1200  }
1201 
1202  NodeManager(const NodeManager&) = delete;
1203 
1204  /// @brief Clear all the cached tree nodes
1205  void clear() { mList0.clear(); mList1.clear(); }
1206 
1207  /// @brief Clear and recache all the tree nodes from the
1208  /// tree. This is required if tree nodes have been added or removed.
1209  void rebuild(bool serial = false)
1210  {
1211  mList1.initRootChildren(mRoot);
1212  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1213  }
1214 
1215  /// @brief Return a reference to the root node.
1216  const RootNodeType& root() const { return mRoot; }
1217 
1218  /// @brief Return the total number of cached nodes (excluding the root node)
1219  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
1220 
1221  /// @brief Return the number of cached nodes at level @a i, where
1222  /// 0 corresponds to the lowest level.
1223  Index64 nodeCount(Index i) const
1224  {
1225  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1226  }
1227 
1228  template<typename NodeOp>
1229  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1230  {
1231  mList0.foreach(op, threaded, grainSize);
1232  mList1.foreach(op, threaded, grainSize);
1233  op(mRoot);
1234  }
1235 
1236  template<typename NodeOp>
1237  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1238  {
1239  op(mRoot);
1240  mList1.foreach(op, threaded, grainSize);
1241  mList0.foreach(op, threaded, grainSize);
1242  }
1243 
1244  template<typename NodeOp>
1245  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1246  {
1247  mList0.reduce(op, threaded, grainSize);
1248  mList1.reduce(op, threaded, grainSize);
1249  op(mRoot);
1250  }
1251 
1252  template<typename NodeOp>
1253  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1254  {
1255  op(mRoot);
1256  mList1.reduce(op, threaded, grainSize);
1257  mList0.reduce(op, threaded, grainSize);
1258  }
1259 
1260 protected:
1261  using NodeT2 = RootNodeType;
1262  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1263  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1264  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1265  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1266 
1267  using ListT1 = NodeList<NodeT1>; // upper level
1268  using ListT0 = NodeList<NodeT0>; // lower level
1269 
1270  NodeT2& mRoot;
1271  ListT1 mList1;
1272  ListT0 mList0;
1273 }; // NodeManager<2>
1274 
1275 
1276 ////////////////////////////////////////////
1277 
1278 
1279 /// @private
1280 /// Template specialization of the NodeManager with three levels of nodes
1281 template<typename TreeOrLeafManagerT>
1282 class NodeManager<TreeOrLeafManagerT, 3>
1283 {
1284 public:
1285  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1287  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1288  static const Index LEVELS = 3;
1289 
1290  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1291  {
1292  this->rebuild(serial);
1293  }
1294 
1295  NodeManager(const NodeManager&) = delete;
1296 
1297  /// @brief Clear all the cached tree nodes
1298  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1299 
1300  /// @brief Clear and recache all the tree nodes from the
1301  /// tree. This is required if tree nodes have been added or removed.
1302  void rebuild(bool serial = false)
1303  {
1304  mList2.initRootChildren(mRoot);
1305  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1306  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1307  }
1308 
1309  /// @brief Return a reference to the root node.
1310  const RootNodeType& root() const { return mRoot; }
1311 
1312  /// @brief Return the total number of cached nodes (excluding the root node)
1313  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1314 
1315  /// @brief Return the number of cached nodes at level @a i, where
1316  /// 0 corresponds to the lowest level.
1317  Index64 nodeCount(Index i) const
1318  {
1319  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1320  : i==2 ? mList2.nodeCount() : 0;
1321  }
1322 
1323  template<typename NodeOp>
1324  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1325  {
1326  mList0.foreach(op, threaded, grainSize);
1327  mList1.foreach(op, threaded, grainSize);
1328  mList2.foreach(op, threaded, grainSize);
1329  op(mRoot);
1330  }
1331 
1332  template<typename NodeOp>
1333  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1334  {
1335  op(mRoot);
1336  mList2.foreach(op, threaded, grainSize);
1337  mList1.foreach(op, threaded, grainSize);
1338  mList0.foreach(op, threaded, grainSize);
1339  }
1340 
1341  template<typename NodeOp>
1342  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1343  {
1344  mList0.reduce(op, threaded, grainSize);
1345  mList1.reduce(op, threaded, grainSize);
1346  mList2.reduce(op, threaded, grainSize);
1347  op(mRoot);
1348  }
1349 
1350  template<typename NodeOp>
1351  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1352  {
1353  op(mRoot);
1354  mList2.reduce(op, threaded, grainSize);
1355  mList1.reduce(op, threaded, grainSize);
1356  mList0.reduce(op, threaded, grainSize);
1357  }
1358 
1359 protected:
1360  using NodeT3 = RootNodeType;
1361  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1362  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1363  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1364  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1365  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1366  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1367 
1368  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1369  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1370  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1371 
1372  NodeT3& mRoot;
1373  ListT2 mList2;
1374  ListT1 mList1;
1375  ListT0 mList0;
1376 }; // NodeManager<3>
1377 
1378 
1379 ////////////////////////////////////////////
1380 
1381 
1382 /// @private
1383 /// Template specialization of the NodeManager with four levels of nodes
1384 template<typename TreeOrLeafManagerT>
1385 class NodeManager<TreeOrLeafManagerT, 4>
1386 {
1387 public:
1388  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1390  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1391  static const Index LEVELS = 4;
1392 
1393  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1394  {
1395  this->rebuild(serial);
1396  }
1397 
1398  NodeManager(const NodeManager&) = delete; // disallow copy-construction
1399 
1400  /// @brief Clear all the cached tree nodes
1401  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1402 
1403  /// @brief Clear and recache all the tree nodes from the
1404  /// tree. This is required if tree nodes have been added or removed.
1405  void rebuild(bool serial = false)
1406  {
1407  mList3.initRootChildren(mRoot);
1408  mList2.initNodeChildren(mList3, NodeFilter(), serial);
1409  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1410  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1411  }
1412 
1413  /// @brief Return a reference to the root node.
1414  const RootNodeType& root() const { return mRoot; }
1415 
1416  /// @brief Return the total number of cached nodes (excluding the root node)
1417  Index64 nodeCount() const
1418  {
1419  return mList0.nodeCount() + mList1.nodeCount()
1420  + mList2.nodeCount() + mList3.nodeCount();
1421  }
1422 
1423  /// @brief Return the number of cached nodes at level @a i, where
1424  /// 0 corresponds to the lowest level.
1425  Index64 nodeCount(Index i) const
1426  {
1427  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1428  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1429  }
1430 
1431  template<typename NodeOp>
1432  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1433  {
1434  mList0.foreach(op, threaded, grainSize);
1435  mList1.foreach(op, threaded, grainSize);
1436  mList2.foreach(op, threaded, grainSize);
1437  mList3.foreach(op, threaded, grainSize);
1438  op(mRoot);
1439  }
1440 
1441  template<typename NodeOp>
1442  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1443  {
1444  op(mRoot);
1445  mList3.foreach(op, threaded, grainSize);
1446  mList2.foreach(op, threaded, grainSize);
1447  mList1.foreach(op, threaded, grainSize);
1448  mList0.foreach(op, threaded, grainSize);
1449  }
1450 
1451  template<typename NodeOp>
1452  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1453  {
1454  mList0.reduce(op, threaded, grainSize);
1455  mList1.reduce(op, threaded, grainSize);
1456  mList2.reduce(op, threaded, grainSize);
1457  mList3.reduce(op, threaded, grainSize);
1458  op(mRoot);
1459  }
1460 
1461  template<typename NodeOp>
1462  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1463  {
1464  op(mRoot);
1465  mList3.reduce(op, threaded, grainSize);
1466  mList2.reduce(op, threaded, grainSize);
1467  mList1.reduce(op, threaded, grainSize);
1468  mList0.reduce(op, threaded, grainSize);
1469  }
1470 
1471 protected:
1472  using NodeT4 = RootNodeType;
1473  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1474  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1475  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1476  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1477  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1478  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1479  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1480  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1481 
1482  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1483  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1484  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1485  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1486 
1487  NodeT4& mRoot;
1488  ListT3 mList3;
1489  ListT2 mList2;
1490  ListT1 mList1;
1491  ListT0 mList0;
1492 }; // NodeManager<4>
1493 
1494 
1495 ////////////////////////////////////////////
1496 
1497 
1498 /// @private
1499 /// Template specialization of the DynamicNodeManager with no caching of nodes
1500 template<typename TreeOrLeafManagerT>
1501 class DynamicNodeManager<TreeOrLeafManagerT, 0>
1502 {
1503 public:
1504  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1506  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1507  static const Index LEVELS = 0;
1508 
1509  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1510 
1511  DynamicNodeManager(const DynamicNodeManager&) = delete;
1512 
1513  /// @brief Return a reference to the root node.
1514  const RootNodeType& root() const { return mRoot; }
1515 
1516  template<typename NodeOp>
1517  void foreachTopDown(const NodeOp& op, bool /*threaded*/=true, size_t /*grainSize*/=1)
1518  {
1519  // root
1520  if (!op(mRoot, /*index=*/0)) return;
1521  }
1522 
1523  template<typename NodeOp>
1524  void reduceTopDown(NodeOp& op, bool /*threaded*/=true, size_t /*grainSize*/=1)
1525  {
1526  // root
1527  if (!op(mRoot, /*index=*/0)) return;
1528  }
1529 
1530 protected:
1531  using NodeT1 = RootNodeType;
1532 
1533  NodeT1& mRoot;
1534 };// DynamicNodeManager<0> class
1535 
1536 
1537 ////////////////////////////////////////////
1538 
1539 
1540 /// @private
1541 /// Template specialization of the DynamicNodeManager with one level of nodes
1542 template<typename TreeOrLeafManagerT>
1543 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1544 {
1545 public:
1546  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1548  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1549  static const Index LEVELS = 1;
1550 
1551  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1552 
1553  DynamicNodeManager(const DynamicNodeManager&) = delete;
1554 
1555  /// @brief Return a reference to the root node.
1556  const RootNodeType& root() const { return mRoot; }
1557 
1558  template<typename NodeOp>
1559  void foreachTopDown(const NodeOp& op, bool threaded = true,
1560  size_t leafGrainSize=1, size_t /*nonLeafGrainSize*/ =1)
1561  {
1562  // root
1563  if (!op(mRoot, /*index=*/0)) return;
1564  // list0
1565  if (!mList0.initRootChildren(mRoot)) return;
1566  ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1567  mList0.foreachWithIndex(nodeOp, threaded, leafGrainSize);
1568  }
1569 
1570  template<typename NodeOp>
1571  void reduceTopDown(NodeOp& op, bool threaded = true,
1572  size_t leafGrainSize=1, size_t /*nonLeafGrainSize*/ =1)
1573  {
1574  // root
1575  if (!op(mRoot, /*index=*/0)) return;
1576  // list0
1577  if (!mList0.initRootChildren(mRoot)) return;
1578  ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1579  mList0.reduceWithIndex(nodeOp, threaded, leafGrainSize);
1580  }
1581 
1582 protected:
1583  using NodeT1 = RootNodeType;
1584  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1585  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1586  using ListT0 = NodeList<NodeT0>;
1587 
1588  NodeT1& mRoot;
1589  ListT0 mList0;
1590 };// DynamicNodeManager<1> class
1591 
1592 
1593 ////////////////////////////////////////////
1594 
1595 
1596 /// @private
1597 /// Template specialization of the DynamicNodeManager with two levels of nodes
1598 template<typename TreeOrLeafManagerT>
1599 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1600 {
1601 public:
1602  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1604  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1605  static const Index LEVELS = 2;
1606 
1607  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1608 
1609  DynamicNodeManager(const DynamicNodeManager&) = delete;
1610 
1611  /// @brief Return a reference to the root node.
1612  const RootNodeType& root() const { return mRoot; }
1613 
1614  template<typename NodeOp>
1615  void foreachTopDown(const NodeOp& op, bool threaded = true,
1616  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1617  {
1618  // root
1619  if (!op(mRoot, /*index=*/0)) return;
1620  // list1
1621  if (!mList1.initRootChildren(mRoot)) return;
1622  ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1623  mList1.foreachWithIndex(nodeOp, threaded, nonLeafGrainSize);
1624  // list0
1625  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1626  mList0.foreachWithIndex(op, threaded, leafGrainSize);
1627  }
1628 
1629  template<typename NodeOp>
1630  void reduceTopDown(NodeOp& op, bool threaded = true,
1631  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1632  {
1633  // root
1634  if (!op(mRoot, /*index=*/0)) return;
1635  // list1
1636  if (!mList1.initRootChildren(mRoot)) return;
1637  ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1638  mList1.reduceWithIndex(nodeOp, threaded, nonLeafGrainSize);
1639  // list0
1640  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1641  mList0.reduceWithIndex(op, threaded, leafGrainSize);
1642  }
1643 
1644 protected:
1645  using NodeT2 = RootNodeType;
1646  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1647  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1648  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1649  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1650 
1651  using ListT1 = NodeList<NodeT1>; // upper level
1652  using ListT0 = NodeList<NodeT0>; // lower level
1653 
1654  NodeT2& mRoot;
1655  ListT1 mList1;
1656  ListT0 mList0;
1657 };// DynamicNodeManager<2> class
1658 
1659 
1660 ////////////////////////////////////////////
1661 
1662 
1663 /// @private
1664 /// Template specialization of the DynamicNodeManager with three levels of nodes
1665 template<typename TreeOrLeafManagerT>
1666 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1667 {
1668 public:
1669  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1671  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1672  static const Index LEVELS = 3;
1673 
1674  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1675 
1676  DynamicNodeManager(const DynamicNodeManager&) = delete;
1677 
1678  /// @brief Return a reference to the root node.
1679  const RootNodeType& root() const { return mRoot; }
1680 
1681  template<typename NodeOp>
1682  void foreachTopDown(const NodeOp& op, bool threaded = true,
1683  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1684  {
1685  // root
1686  if (!op(mRoot, /*index=*/0)) return;
1687  // list2
1688  if (!mList2.initRootChildren(mRoot)) return;
1689  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1690  mList2.foreachWithIndex(nodeOp2, threaded, nonLeafGrainSize);
1691  // list1
1692  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1693  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1694  mList1.foreachWithIndex(nodeOp1, threaded, nonLeafGrainSize);
1695  // list0
1696  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1697  mList0.foreachWithIndex(op, threaded, leafGrainSize);
1698  }
1699 
1700  template<typename NodeOp>
1701  void reduceTopDown(NodeOp& op, bool threaded = true,
1702  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1703  {
1704  // root
1705  if (!op(mRoot, /*index=*/0)) return;
1706  // list2
1707  if (!mList2.initRootChildren(mRoot)) return;
1708  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1709  mList2.reduceWithIndex(nodeOp2, threaded, nonLeafGrainSize);
1710  // list1
1711  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1712  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1713  mList1.reduceWithIndex(nodeOp1, threaded, nonLeafGrainSize);
1714  // list0
1715  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1716  mList0.reduceWithIndex(op, threaded, leafGrainSize);
1717  }
1718 
1719 protected:
1720  using NodeT3 = RootNodeType;
1721  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1722  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1723  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1724  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1725  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1726  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1727 
1728  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1729  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1730  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1731 
1732  NodeT3& mRoot;
1733  ListT2 mList2;
1734  ListT1 mList1;
1735  ListT0 mList0;
1736 };// DynamicNodeManager<3> class
1737 
1738 
1739 ////////////////////////////////////////////
1740 
1741 
1742 /// @private
1743 /// Template specialization of the DynamicNodeManager with four levels of nodes
1744 template<typename TreeOrLeafManagerT>
1745 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1746 {
1747 public:
1748  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1750  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1751  static const Index LEVELS = 4;
1752 
1753  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1754 
1755  DynamicNodeManager(const DynamicNodeManager&) = delete;
1756 
1757  /// @brief Return a reference to the root node.
1758  const RootNodeType& root() const { return mRoot; }
1759 
1760  template<typename NodeOp>
1761  void foreachTopDown(const NodeOp& op, bool threaded = true,
1762  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1763  {
1764  // root
1765  if (!op(mRoot, /*index=*/0)) return;
1766  // list3
1767  if (!mList3.initRootChildren(mRoot)) return;
1768  ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1769  mList3.foreachWithIndex(nodeOp3, threaded, nonLeafGrainSize);
1770  // list2
1771  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1772  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1773  mList2.foreachWithIndex(nodeOp2, threaded, nonLeafGrainSize);
1774  // list1
1775  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1776  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1777  mList1.foreachWithIndex(nodeOp1, threaded, nonLeafGrainSize);
1778  // list0
1779  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1780  mList0.foreachWithIndex(op, threaded, leafGrainSize);
1781  }
1782 
1783  template<typename NodeOp>
1784  void reduceTopDown(NodeOp& op, bool threaded = true,
1785  size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
1786  {
1787  // root
1788  if (!op(mRoot, /*index=*/0)) return;
1789  // list3
1790  if (!mList3.initRootChildren(mRoot)) return;
1791  ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1792  mList3.reduceWithIndex(nodeOp3, threaded, nonLeafGrainSize);
1793  // list2
1794  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1795  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1796  mList2.reduceWithIndex(nodeOp2, threaded, nonLeafGrainSize);
1797  // list1
1798  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1799  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1800  mList1.reduceWithIndex(nodeOp1, threaded, nonLeafGrainSize);
1801  // list0
1802  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1803  mList0.reduceWithIndex(op, threaded, leafGrainSize);
1804  }
1805 
1806 protected:
1807  using NodeT4 = RootNodeType;
1808  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1809  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1810  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1811  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1812  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1813  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1814  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1815  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1816 
1817  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1818  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1819  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1820  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1821 
1822  NodeT4& mRoot;
1823  ListT3 mList3;
1824  ListT2 mList2;
1825  ListT1 mList1;
1826  ListT0 mList0;
1827 };// DynamicNodeManager<4> class
1828 
1829 
1830 } // namespace tree
1831 } // namespace OPENVDB_VERSION_NAME
1832 } // namespace openvdb
1833 
1834 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
typename std::remove_const< ToType >::type Type
Definition: Types.h:400
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays, one for each level of the tree.
Definition: NodeManager.h:30
void foreachWithIndex(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:284
Index32 Index
Definition: Types.h:54
NodeT *& operator[](size_t n)
Definition: NodeManager.h:61
uint64_t Index64
Definition: Types.h:53
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:631
bool valid(size_t idx) const
Definition: NodeManager.h:782
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:896
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:597
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:565
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:897
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:232
Definition: NodeManager.h:187
NodeManager(TreeOrLeafManagerT &tree, bool serial=false)
Definition: NodeManager.h:542
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:705
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:551
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:976
size_t grainsize() const
Definition: NodeManager.h:200
void clear()
Definition: NodeManager.h:65
bool empty() const
Definition: NodeManager.h:204
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:736
Iterator begin() const
Definition: NodeManager.h:244
Definition: Coord.h:587
std::unique_ptr< NodeT *[]> mNodePtrs
Definition: NodeManager.h:389
const NodeList & nodeList() const
Definition: NodeManager.h:202
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:537
Definition: NodeManager.h:44
OpT & op()
Definition: NodeManager.h:787
Definition: NodeManager.h:755
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:220
RootNodeType & mRoot
Definition: NodeManager.h:1050
ReduceFilterOp(OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:757
ForeachFilterOp(const ForeachFilterOp &other)
Definition: NodeManager.h:731
bool valid(size_t idx) const
Definition: NodeManager.h:741
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:231
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:539
bool isValid() const
Definition: NodeManager.h:225
RootNodeType & mRoot
Definition: NodeManager.h:713
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:191
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:898
Iterator end() const
Definition: NodeManager.h:246
OPENVDB_AX_API void run(const char *ax, openvdb::GridBase &grid, const AttributeBindings &bindings={})
Run a full AX pipeline (parse, compile and execute) on a single OpenVDB Grid.
void reduceTopDown(NodeOp &op, bool threaded=true, size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:1043
size_t size() const
Definition: NodeManager.h:198
DynamicNodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:901
bool initRootChildren(RootT &root)
Definition: NodeManager.h:74
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:194
bool operator==(const Iterator &other) const
Definition: NodeManager.h:236
Definition: Exceptions.h:13
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:538
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:895
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:275
Definition: NodeManager.h:724
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:218
DynamicNodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:1051
void rebuild(bool serial=false)
Clear and recache all the tree nodes from the tree. This is required if tree nodes have been added or...
Definition: NodeManager.h:555
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:222
ForeachFilterOp(const OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:726
const NodeRange & nodeRange() const
Definition: NodeManager.h:237
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:536
void join(const ReduceFilterOp &other)
Definition: NodeManager.h:777
static bool valid(size_t)
Definition: NodeManager.h:46
void foreachBottomUp(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:624
void reduceWithIndex(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:292
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:772
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:54
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:561
ReduceFilterOp(const ReduceFilterOp &other)
Definition: NodeManager.h:762
bool initNodeChildren(ParentsT &parents, const NodeFilterT &nodeFilter=NodeFilterT(), bool serial=false)
Definition: NodeManager.h:105
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:227
const NonConstRootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:906
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:698
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:558
NodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:714
NodeT & operator()(size_t n) const
Definition: NodeManager.h:59
static bool isValid(const void *p)
return true if the specified pointer is aligned and not NULL
Definition: NanoVDB.h:504
ReduceFilterOp(const ReduceFilterOp &other, tbb::split)
Definition: NodeManager.h:766
Index64 nodeCount() const
Definition: NodeManager.h:63
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:262
bool is_divisible() const
Definition: NodeManager.h:206
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:211
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:224
const OpT & op() const
Definition: NodeManager.h:743
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
Definition: NodeManager.h:36