OpenVDB  7.0.0
TreeIterator.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
5 
6 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
7 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
8 
9 #include <boost/mpl/front.hpp>
10 #include <boost/mpl/pop_front.hpp>
11 #include <boost/mpl/push_back.hpp>
12 #include <boost/mpl/size.hpp>
13 #include <boost/mpl/vector.hpp>
14 #include <tbb/blocked_range.h>
15 #include <tbb/parallel_for.h>
16 #include <openvdb/version.h>
17 #include <openvdb/Types.h>
18 #include <algorithm>
19 #include <sstream>
20 #include <string>
21 #include <type_traits>
22 
23 // Prior to 0.96.1, depth-bounded value iterators always descended to the leaf level
24 // and iterated past leaf nodes. Now, they never descend past the maximum depth.
25 // Comment out the following line to restore the older, less-efficient behavior:
26 #define ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
27 
28 
29 namespace openvdb {
31 namespace OPENVDB_VERSION_NAME {
32 namespace tree {
33 
34 namespace iter {
35 
36 template<typename HeadT, int HeadLevel>
37 struct InvertedTree {
38  using SubtreeT = typename InvertedTree<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
39  using Type = typename boost::mpl::push_back<SubtreeT, HeadT>::type;
40 };
41 template<typename HeadT>
42 struct InvertedTree<HeadT, /*HeadLevel=*/1> {
43  using Type = typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type;
44 };
45 
46 } // namespace iter
47 
48 
50 
51 
63 template<typename NodeT, typename IterT>
64 struct IterTraits
65 {
66  template<typename ChildT> static ChildT* getChild(const IterT&) { return nullptr; }
67 };
68 
69 template<typename NodeT>
70 struct IterTraits<NodeT, typename NodeT::ChildOnIter>
71 {
72  using IterT = typename NodeT::ChildOnIter;
73  static IterT begin(NodeT& node) { return node.beginChildOn(); }
74  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
75  return &iter.getValue();
76  }
77  template<typename OtherNodeT> struct NodeConverter {
78  using Type = typename OtherNodeT::ChildOnIter;
79  };
80 };
81 
82 template<typename NodeT>
83 struct IterTraits<NodeT, typename NodeT::ChildOnCIter>
84 {
85  using IterT = typename NodeT::ChildOnCIter;
86  static IterT begin(const NodeT& node) { return node.cbeginChildOn(); }
87  template<typename ChildT> static const ChildT* getChild(const IterT& iter) {
88  return &iter.getValue();
89  }
90  template<typename OtherNodeT> struct NodeConverter {
91  using Type = typename OtherNodeT::ChildOnCIter;
92  };
93 };
94 
95 template<typename NodeT>
96 struct IterTraits<NodeT, typename NodeT::ChildOffIter>
97 {
98  using IterT = typename NodeT::ChildOffIter;
99  static IterT begin(NodeT& node) { return node.beginChildOff(); }
100  template<typename OtherNodeT> struct NodeConverter {
101  using Type = typename OtherNodeT::ChildOffIter;
102  };
103 };
104 
105 template<typename NodeT>
106 struct IterTraits<NodeT, typename NodeT::ChildOffCIter>
107 {
108  using IterT = typename NodeT::ChildOffCIter;
109  static IterT begin(const NodeT& node) { return node.cbeginChildOff(); }
110  template<typename OtherNodeT> struct NodeConverter {
111  using Type = typename OtherNodeT::ChildOffCIter;
112  };
113 };
114 
115 template<typename NodeT>
116 struct IterTraits<NodeT, typename NodeT::ChildAllIter>
117 {
118  using IterT = typename NodeT::ChildAllIter;
119  static IterT begin(NodeT& node) { return node.beginChildAll(); }
120  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
121  typename IterT::NonConstValueType val;
122  return iter.probeChild(val);
123  }
124  template<typename OtherNodeT> struct NodeConverter {
125  using Type = typename OtherNodeT::ChildAllIter;
126  };
127 };
128 
129 template<typename NodeT>
130 struct IterTraits<NodeT, typename NodeT::ChildAllCIter>
131 {
132  using IterT = typename NodeT::ChildAllCIter;
133  static IterT begin(const NodeT& node) { return node.cbeginChildAll(); }
134  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
135  typename IterT::NonConstValueType val;
136  return iter.probeChild(val);
137  }
138  template<typename OtherNodeT> struct NodeConverter {
139  using Type = typename OtherNodeT::ChildAllCIter;
140  };
141 };
142 
143 template<typename NodeT>
144 struct IterTraits<NodeT, typename NodeT::ValueOnIter>
145 {
146  using IterT = typename NodeT::ValueOnIter;
147  static IterT begin(NodeT& node) { return node.beginValueOn(); }
148  template<typename OtherNodeT> struct NodeConverter {
149  using Type = typename OtherNodeT::ValueOnIter;
150  };
151 };
152 
153 template<typename NodeT>
154 struct IterTraits<NodeT, typename NodeT::ValueOnCIter>
155 {
156  using IterT = typename NodeT::ValueOnCIter;
157  static IterT begin(const NodeT& node) { return node.cbeginValueOn(); }
158  template<typename OtherNodeT> struct NodeConverter {
159  using Type = typename OtherNodeT::ValueOnCIter;
160  };
161 };
162 
163 template<typename NodeT>
164 struct IterTraits<NodeT, typename NodeT::ValueOffIter>
165 {
166  using IterT = typename NodeT::ValueOffIter;
167  static IterT begin(NodeT& node) { return node.beginValueOff(); }
168  template<typename OtherNodeT> struct NodeConverter {
169  using Type = typename OtherNodeT::ValueOffIter;
170  };
171 };
172 
173 template<typename NodeT>
174 struct IterTraits<NodeT, typename NodeT::ValueOffCIter>
175 {
176  using IterT = typename NodeT::ValueOffCIter;
177  static IterT begin(const NodeT& node) { return node.cbeginValueOff(); }
178  template<typename OtherNodeT> struct NodeConverter {
179  using Type = typename OtherNodeT::ValueOffCIter;
180  };
181 };
182 
183 template<typename NodeT>
184 struct IterTraits<NodeT, typename NodeT::ValueAllIter>
185 {
186  using IterT = typename NodeT::ValueAllIter;
187  static IterT begin(NodeT& node) { return node.beginValueAll(); }
188  template<typename OtherNodeT> struct NodeConverter {
189  using Type = typename OtherNodeT::ValueAllIter;
190  };
191 };
192 
193 template<typename NodeT>
194 struct IterTraits<NodeT, typename NodeT::ValueAllCIter>
195 {
196  using IterT = typename NodeT::ValueAllCIter;
197  static IterT begin(const NodeT& node) { return node.cbeginValueAll(); }
198  template<typename OtherNodeT> struct NodeConverter {
199  using Type = typename OtherNodeT::ValueAllCIter;
200  };
201 };
202 
203 
205 
206 
217 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level>
219 {
220 public:
222  using PrevIterT = typename PrevItemT::IterT;
224  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
227  NodeConverter<_NodeT>::Type;
228 
230  using NodeT = typename IterT::NodeType;
232  using NCNodeT = typename IterT::NonConstNodeType;
234  using NCValueT = typename IterT::NonConstValueType;
241  static const Index Level = _Level;
242 
243  IterListItem(PrevItemT* prev): mNext(this), mPrev(prev) {}
244 
245  IterListItem(const IterListItem& other):
246  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
248  {
249  if (&other != this) {
250  mIter = other.mIter;
251  mNext = other.mNext;
252  mPrev = nullptr;
253  }
254  return *this;
255  }
256 
257  void updateBackPointers(PrevItemT* prev) { mPrev = prev; mNext.updateBackPointers(this); }
258 
259  void setIter(const IterT& iter) { mIter = iter; }
260  template<typename OtherIterT>
261  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
262 
264  void getNode(Index lvl, NodeT*& node) const
265  {
266  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
267  }
269  template<typename OtherNodeT>
270  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
271 
277  template<typename OtherIterListItemT>
278  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
279  {
280  if (lvl == Level) {
281  const NodeT* node = nullptr;
282  otherListItem.getNode(lvl, node);
283  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
284  } else {
285  // Forward to one of the following list elements.
286  mNext.initLevel(lvl, otherListItem);
287  }
288  }
289 
291  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
292 
294  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
295 
297  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
298 
301  bool down(Index lvl)
302  {
303  if (lvl == Level && mPrev != nullptr && mIter) {
304  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
305  mPrev->setIter(PrevItemT::ITraits::begin(*child));
306  return true;
307  }
308  }
309  return (lvl > Level) ? mNext.down(lvl) : false;
310  }
311 
314  Coord getCoord(Index lvl) const
315  {
316  return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
317  }
319  {
320  return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
321  }
324  {
325  return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
326  }
327 
329  bool isValueOn(Index lvl) const
330  {
331  return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
332  }
333 
335  const NCValueT& getValue(Index lvl) const
336  {
337  if (lvl == Level) return mIter.getValue();
338  return mNext.getValue(lvl);
339  }
340 
344  void setValue(Index lvl, const NCValueT& val) const
345  {
346  if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val);
347  }
351  void setValueOn(Index lvl, bool on = true) const
352  {
353  if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
354  }
358  void setValueOff(Index lvl) const
359  {
360  if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl);
361  }
362 
365  template<typename ModifyOp>
366  void modifyValue(Index lvl, const ModifyOp& op) const
367  {
368  if (lvl == Level) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
369  }
370 
371 private:
372  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
373  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, Level + 1>;
374 
375  IterT mIter;
376  NextItem mNext;
377  PrevItemT* mPrev;
378 };
379 
380 
382 template<typename PrevItemT, typename NodeVecT, size_t VecSize>
383 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U>
384 {
385 public:
387  using PrevIterT = typename PrevItemT::IterT;
389  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
392  NodeConverter<_NodeT>::Type;
393 
395  using NodeT = typename IterT::NodeType;
397  using NCNodeT = typename IterT::NonConstNodeType;
399  using NCValueT = typename IterT::NonConstValueType;
402  static const Index Level = 0;
403 
404  IterListItem(PrevItemT*): mNext(this), mPrev(nullptr) {}
405 
406  IterListItem(const IterListItem& other):
407  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
409  {
410  if (&other != this) {
411  mIter = other.mIter;
412  mNext = other.mNext;
413  mPrev = nullptr;
414  }
415  return *this;
416  }
417 
418  void updateBackPointers(PrevItemT* = nullptr)
419  {
420  mPrev = nullptr; mNext.updateBackPointers(this);
421  }
422 
423  void setIter(const IterT& iter) { mIter = iter; }
424  template<typename OtherIterT>
425  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
426 
427  void getNode(Index lvl, NodeT*& node) const
428  {
429  node = (lvl == 0) ? mIter.getParentNode() : nullptr;
430  }
431  template<typename OtherNodeT>
432  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
433 
434  template<typename OtherIterListItemT>
435  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
436  {
437  if (lvl == 0) {
438  const NodeT* node = nullptr;
439  otherListItem.getNode(lvl, node);
440  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
441  } else {
442  mNext.initLevel(lvl, otherListItem);
443  }
444  }
445 
446  Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
447 
448  bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
449 
450  bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
451 
452  bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); }
453 
454  Coord getCoord(Index lvl) const
455  {
456  return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
457  }
459  {
460  return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
461  }
462 
464  {
465  return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
466  }
467 
468  bool isValueOn(Index lvl) const
469  {
470  return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
471  }
472 
473  const NCValueT& getValue(Index lvl) const
474  {
475  if (lvl == 0) return mIter.getValue();
476  return mNext.getValue(lvl);
477  }
478 
479  void setValue(Index lvl, const NCValueT& val) const
480  {
481  if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val);
482  }
483  void setValueOn(Index lvl, bool on = true) const
484  {
485  if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
486  }
487  void setValueOff(Index lvl) const
488  {
489  if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl);
490  }
491 
492  template<typename ModifyOp>
493  void modifyValue(Index lvl, const ModifyOp& op) const
494  {
495  if (lvl == 0) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
496  }
497 
498 private:
499  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
500  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1>;
501 
502  IterT mIter;
503  NextItem mNext;
504  PrevItemT* mPrev;
505 };
506 
507 
509 template<typename PrevItemT, typename NodeVecT, Index _Level>
510 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level>
511 {
512 public:
513  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
515  using PrevIterT = typename PrevItemT::IterT;
518  NodeConverter<_NodeT>::Type;
519 
521  using NodeT = typename IterT::NodeType;
523  using NCNodeT = typename IterT::NonConstNodeType;
525  using NCValueT = typename IterT::NonConstValueType;
532  static const Index Level = _Level;
533 
534  IterListItem(PrevItemT* prev): mPrev(prev) {}
535 
536  IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(nullptr) {}
538  {
539  if (&other != this) {
540  mIter = other.mIter;
541  mPrev = nullptr;
542  }
543  return *this;
544  }
545 
546  void updateBackPointers(PrevItemT* prev) { mPrev = prev; }
547 
548  // The following method specializations differ from the default template
549  // implementations mainly in that they don't forward.
550 
551  void setIter(const IterT& iter) { mIter = iter; }
552 
553  void getNode(Index lvl, NodeT*& node) const
554  {
555  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
556  }
557 
558  template<typename OtherIterListItemT>
559  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
560  {
561  if (lvl == Level) {
562  const NodeT* node = nullptr;
563  otherListItem.getNode(lvl, node);
564  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
565  }
566  }
567 
568  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); }
569 
570  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; }
571 
572  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; }
573 
574  bool down(Index lvl)
575  {
576  if (lvl == Level && mPrev != nullptr && mIter) {
577  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
578  mPrev->setIter(PrevItemT::ITraits::begin(*child));
579  return true;
580  }
581  }
582  return false;
583  }
584 
585  Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); }
586  Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; }
587  Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; }
588 
589  bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; }
590 
591  const NCValueT& getValue(Index lvl) const
592  {
593  assert(lvl == Level);
594  (void)lvl; // avoid unused variable warning in optimized builds
595  return mIter.getValue();
596  }
597 
598  void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); }
599  void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); }
600  void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); }
601 
602  template<typename ModifyOp>
603  void modifyValue(Index lvl, const ModifyOp& op) const
604  {
605  if (lvl == Level) mIter.modifyValue(op);
606  }
607 
608 private:
609  IterT mIter;
610  PrevItemT* mPrev;
611 };
612 
613 
615 
616 
617 //#define DEBUG_TREE_VALUE_ITERATOR
618 
620 template<typename _TreeT, typename _ValueIterT>
622 {
623 public:
624  using TreeT = _TreeT;
625  using ValueIterT = _ValueIterT;
626  using NodeT = typename ValueIterT::NodeType;
627  using ValueT = typename ValueIterT::NonConstValueType;
628  using ChildOnIterT = typename NodeT::ChildOnCIter;
629  static const Index ROOT_LEVEL = NodeT::LEVEL;
630  static_assert(ValueIterT::NodeType::LEVEL == ROOT_LEVEL, "invalid value iterator node type");
631  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
632 
634 
636  TreeValueIteratorBase& operator=(const TreeValueIteratorBase& other);
637 
639  void setMinDepth(Index minDepth);
641  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
643  void setMaxDepth(Index maxDepth);
645  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
646 
648  bool test() const { return mValueIterList.test(mLevel); }
650  operator bool() const { return this->test(); }
652 
655  bool next();
657  TreeValueIteratorBase& operator++() { this->next(); return *this; }
658 
661  Index getLevel() const { return mLevel; }
664  Index getDepth() const { return ROOT_LEVEL - mLevel; }
665  static Index getLeafDepth() { return LEAF_DEPTH; }
666 
671  template<typename NodeType>
672  void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); }
673 
676  Coord getCoord() const { return mValueIterList.getCoord(mLevel); }
680  bool getBoundingBox(CoordBBox&) const;
683  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
684 
686  Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);}
687 
689  bool isTileValue() const { return mLevel != 0 && this->test(); }
691  bool isVoxelValue() const { return mLevel == 0 && this->test(); }
693  bool isValueOn() const { return mValueIterList.isValueOn(mLevel); }
694 
696  const ValueT& getValue() const { return mValueIterList.getValue(mLevel); }
698  const ValueT& operator*() const { return this->getValue(); }
699  const ValueT* operator->() const { return &(this->operator*()); }
701 
704  void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); }
707  void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); }
709  void setValueOff() const { mValueIterList.setValueOff(mLevel); }
710 
716  template<typename ModifyOp>
717  void modifyValue(const ModifyOp& op) const { mValueIterList.modifyValue(mLevel, op); }
718 
720  TreeT* getTree() const { return mTree; }
721 
723  std::string summary() const;
724 
725 private:
726  bool advance(bool dontIncrement = false);
727 
728  using InvTreeT = typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type;
729  struct PrevChildItem { using IterT = ChildOnIterT; };
730  struct PrevValueItem { using IterT = ValueIterT; };
731 
732  IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList;
733  IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList;
734  Index mLevel;
735  int mMinLevel, mMaxLevel;
736  TreeT* mTree;
737 }; // class TreeValueIteratorBase
738 
739 
740 template<typename TreeT, typename ValueIterT>
741 inline
743  mChildIterList(nullptr),
744  mValueIterList(nullptr),
745  mLevel(ROOT_LEVEL),
746  mMinLevel(int(LEAF_LEVEL)),
747  mMaxLevel(int(ROOT_LEVEL)),
748  mTree(&tree)
749 {
750  mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.root()));
751  mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.root()));
752  this->advance(/*dontIncrement=*/true);
753 }
754 
755 
756 template<typename TreeT, typename ValueIterT>
757 inline
759  mChildIterList(other.mChildIterList),
760  mValueIterList(other.mValueIterList),
761  mLevel(other.mLevel),
762  mMinLevel(other.mMinLevel),
763  mMaxLevel(other.mMaxLevel),
764  mTree(other.mTree)
765 {
766  mChildIterList.updateBackPointers();
767  mValueIterList.updateBackPointers();
768 }
769 
770 
771 template<typename TreeT, typename ValueIterT>
774 {
775  if (&other != this) {
776  mChildIterList = other.mChildIterList;
777  mValueIterList = other.mValueIterList;
778  mLevel = other.mLevel;
779  mMinLevel = other.mMinLevel;
780  mMaxLevel = other.mMaxLevel;
781  mTree = other.mTree;
782  mChildIterList.updateBackPointers();
783  mValueIterList.updateBackPointers();
784  }
785  return *this;
786 }
787 
788 
789 template<typename TreeT, typename ValueIterT>
790 inline void
792 {
793  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
794  if (int(mLevel) > mMaxLevel) this->next();
795 }
796 
797 
798 template<typename TreeT, typename ValueIterT>
799 inline void
801 {
802  // level = ROOT_LEVEL - depth
803  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
804  if (int(mLevel) < mMinLevel) this->next();
805 }
806 
807 
808 template<typename TreeT, typename ValueIterT>
809 inline bool
811 {
812  do {
813  if (!this->advance()) return false;
814  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
815  return true;
816 }
817 
818 
819 template<typename TreeT, typename ValueIterT>
820 inline bool
822 {
823  bool recurse = false;
824  do {
825  recurse = false;
826  Index
827  vPos = mValueIterList.pos(mLevel),
828  cPos = mChildIterList.pos(mLevel);
829  if (vPos == cPos && mChildIterList.test(mLevel)) {
831  mValueIterList.next(mLevel);
832  vPos = mValueIterList.pos(mLevel);
833  }
834  if (vPos < cPos) {
835  if (dontIncrement) return true;
836  if (mValueIterList.next(mLevel)) {
837  if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
840  mValueIterList.next(mLevel);
841  }
842  // If there is a next value and it precedes the next child, return.
843  if (mValueIterList.pos(mLevel) < cPos) return true;
844  }
845  } else {
846  // Advance to the next child, which may or may not precede the next value.
847  if (!dontIncrement) mChildIterList.next(mLevel);
848  }
849 #ifdef DEBUG_TREE_VALUE_ITERATOR
850  std::cout << "\n" << this->summary() << std::flush;
851 #endif
852 
853  // Descend to the lowest level at which the next value precedes the next child.
854  while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
855 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
856  if (int(mLevel) == mMinLevel) {
857  // If the current node lies at the lowest allowed level, none of its
858  // children can be visited, so just advance its child iterator.
859  mChildIterList.next(mLevel);
860  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
861  && mChildIterList.test(mLevel))
862  {
865  mValueIterList.next(mLevel);
866  }
867  } else
868 #endif
869  if (mChildIterList.down(mLevel)) {
870  --mLevel; // descend one level
871  mValueIterList.initLevel(mLevel, mChildIterList);
872  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
873  && mChildIterList.test(mLevel))
874  {
877  mValueIterList.next(mLevel);
878  }
879  } else break;
880 #ifdef DEBUG_TREE_VALUE_ITERATOR
881  std::cout << "\n" << this->summary() << std::flush;
882 #endif
883  }
884  // Ascend to the nearest level at which one of the iterators is not yet exhausted.
885  while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
886  if (mLevel == ROOT_LEVEL) return false;
887  ++mLevel;
888  mChildIterList.next(mLevel);
889  dontIncrement = true;
890  recurse = true;
891  }
892  } while (recurse);
893  return true;
894 }
895 
896 
897 template<typename TreeT, typename ValueIterT>
898 inline bool
900 {
901  if (!this->test()) {
902  bbox = CoordBBox();
903  return false;
904  }
905  bbox.min() = mValueIterList.getCoord(mLevel);
906  bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1);
907  return true;
908 }
909 
910 
911 template<typename TreeT, typename ValueIterT>
912 inline std::string
914 {
915  std::ostringstream ostr;
916  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
917  if (lvl == 0) ostr << "leaf";
918  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
919  else ostr << "int" << (ROOT_LEVEL - lvl);
920  ostr << " v" << mValueIterList.pos(lvl)
921  << " c" << mChildIterList.pos(lvl);
922  if (lvl > int(mLevel)) ostr << " / ";
923  }
924  if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
925  if (mLevel == 0) {
926  ostr << " " << this->getCoord();
927  } else {
928  ostr << " " << this->getBoundingBox();
929  }
930  }
931  return ostr.str();
932 }
933 
934 
936 
937 
939 template<typename _TreeT, typename RootChildOnIterT>
941 {
942 public:
943  using TreeT = _TreeT;
944  using RootIterT = RootChildOnIterT;
945  using RootNodeT = typename RootIterT::NodeType;
946  using NCRootNodeT = typename RootIterT::NonConstNodeType;
947  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
949  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
950 
952 
955 
956  NodeIteratorBase(const NodeIteratorBase& other);
958 
960  void setMinDepth(Index minDepth);
962  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
964  void setMaxDepth(Index maxDepth);
966  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
967 
969  bool test() const { return !mDone; }
971  operator bool() const { return this->test(); }
973 
976  bool next();
978  void increment() { this->next(); }
979  NodeIteratorBase& operator++() { this->increment(); return *this; }
981  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
982 
985  Index getLevel() const { return mLevel; }
988  Index getDepth() const { return ROOT_LEVEL - mLevel; }
989  static Index getLeafDepth() { return LEAF_DEPTH; }
990 
993  Coord getCoord() const;
997  bool getBoundingBox(CoordBBox& bbox) const;
1000  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
1001 
1003  template<typename NodeT>
1007  void getNode(NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1008  template<typename NodeT>
1009  void getNode(const NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1011 
1012  TreeT* getTree() const { return mTree; }
1013 
1014  std::string summary() const;
1015 
1016 private:
1017  struct PrevItem { using IterT = RootIterT; };
1018 
1019  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1020  Index mLevel;
1021  int mMinLevel, mMaxLevel;
1022  bool mDone;
1023  TreeT* mTree;
1024 }; // class NodeIteratorBase
1025 
1026 
1027 template<typename TreeT, typename RootChildOnIterT>
1028 inline
1030  mIterList(nullptr),
1031  mLevel(ROOT_LEVEL),
1032  mMinLevel(int(LEAF_LEVEL)),
1033  mMaxLevel(int(ROOT_LEVEL)),
1034  mDone(true),
1035  mTree(nullptr)
1036 {
1037 }
1038 
1039 
1040 template<typename TreeT, typename RootChildOnIterT>
1041 inline
1043  mIterList(nullptr),
1044  mLevel(ROOT_LEVEL),
1045  mMinLevel(int(LEAF_LEVEL)),
1046  mMaxLevel(int(ROOT_LEVEL)),
1047  mDone(false),
1048  mTree(&tree)
1049 {
1050  mIterList.setIter(RootIterTraits::begin(tree.root()));
1051 }
1052 
1053 
1054 template<typename TreeT, typename RootChildOnIterT>
1055 inline
1057  mIterList(other.mIterList),
1058  mLevel(other.mLevel),
1059  mMinLevel(other.mMinLevel),
1060  mMaxLevel(other.mMaxLevel),
1061  mDone(other.mDone),
1062  mTree(other.mTree)
1063 {
1064  mIterList.updateBackPointers();
1065 }
1066 
1067 
1068 template<typename TreeT, typename RootChildOnIterT>
1071 {
1072  if (&other != this) {
1073  mLevel = other.mLevel;
1074  mMinLevel = other.mMinLevel;
1075  mMaxLevel = other.mMaxLevel;
1076  mDone = other.mDone;
1077  mTree = other.mTree;
1078  mIterList = other.mIterList;
1079  mIterList.updateBackPointers();
1080  }
1081  return *this;
1082 }
1083 
1084 
1085 template<typename TreeT, typename RootChildOnIterT>
1086 inline void
1088 {
1089  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
1090  if (int(mLevel) > mMaxLevel) this->next();
1091 }
1092 
1093 
1094 template<typename TreeT, typename RootChildOnIterT>
1095 inline void
1097 {
1098  // level = ROOT_LEVEL - depth
1099  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
1100  if (int(mLevel) < mMinLevel) this->next();
1101 }
1102 
1103 
1104 template<typename TreeT, typename RootChildOnIterT>
1105 inline bool
1107 {
1108  do {
1109  if (mDone) return false;
1110 
1111  // If the iterator over the current node points to a child,
1112  // descend to the child (depth-first traversal).
1113  if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1114  if (!mIterList.down(mLevel)) return false;
1115  --mLevel;
1116  } else {
1117  // Ascend to the nearest ancestor that has other children.
1118  while (!mIterList.test(mLevel)) {
1119  if (mLevel == ROOT_LEVEL) {
1120  // Can't ascend higher than the root.
1121  mDone = true;
1122  return false;
1123  }
1124  ++mLevel; // ascend one level
1125  mIterList.next(mLevel); // advance to the next child, if there is one
1126  }
1127  // Descend to the child.
1128  if (!mIterList.down(mLevel)) return false;
1129  --mLevel;
1130  }
1131  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1132  return true;
1133 }
1134 
1135 
1136 template<typename TreeT, typename RootChildOnIterT>
1137 inline Coord
1139 {
1140  if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1);
1141  RootNodeT* root = nullptr;
1142  this->getNode(root);
1143  return root ? root->getMinIndex() : Coord::min();
1144 }
1145 
1146 
1147 template<typename TreeT, typename RootChildOnIterT>
1148 inline bool
1150 {
1151  if (mLevel == ROOT_LEVEL) {
1152  RootNodeT* root = nullptr;
1153  this->getNode(root);
1154  if (root == nullptr) {
1155  bbox = CoordBBox();
1156  return false;
1157  }
1158  root->getIndexRange(bbox);
1159  return true;
1160  }
1161  bbox.min() = mIterList.getCoord(mLevel + 1);
1162  bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1163  return true;
1164 }
1165 
1166 
1167 template<typename TreeT, typename RootChildOnIterT>
1168 inline std::string
1170 {
1171  std::ostringstream ostr;
1172  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1173  if (lvl == 0) ostr << "leaf";
1174  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
1175  else ostr << "int" << (ROOT_LEVEL - lvl);
1176  ostr << " c" << mIterList.pos(lvl);
1177  if (lvl > int(mLevel)) ostr << " / ";
1178  }
1179  CoordBBox bbox;
1180  this->getBoundingBox(bbox);
1181  ostr << " " << bbox;
1182  return ostr.str();
1183 }
1184 
1185 
1187 
1188 
1190 template<typename TreeT, typename RootChildOnIterT>
1192 {
1193 public:
1194  using RootIterT = RootChildOnIterT;
1195  using RootNodeT = typename RootIterT::NodeType;
1196  using NCRootNodeT = typename RootIterT::NonConstNodeType;
1197  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
1199  using NCLeafNodeT = typename boost::mpl::front<InvTreeT>::type;
1201  static const Index LEAF_LEVEL = 0, LEAF_PARENT_LEVEL = LEAF_LEVEL + 1;
1202 
1204 
1205  LeafIteratorBase(): mIterList(nullptr), mTree(nullptr) {}
1206 
1207  LeafIteratorBase(TreeT& tree): mIterList(nullptr), mTree(&tree)
1208  {
1209  // Initialize the iterator list with a root node iterator.
1210  mIterList.setIter(RootIterTraits::begin(tree.root()));
1211  // Descend along the first branch, initializing the node iterator at each level.
1212  Index lvl = ROOT_LEVEL;
1213  for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {}
1214  // If the first branch terminated above the leaf level, backtrack to the next branch.
1215  if (lvl > 0) this->next();
1216  }
1217 
1218  LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree)
1219  {
1220  mIterList.updateBackPointers();
1221  }
1223  {
1224  if (&other != this) {
1225  mTree = other.mTree;
1226  mIterList = other.mIterList;
1227  mIterList.updateBackPointers();
1228  }
1229  return *this;
1230  }
1231 
1233  LeafNodeT* getLeaf() const
1235  {
1236  LeafNodeT* n = nullptr;
1237  mIterList.getNode(LEAF_LEVEL, n);
1238  return n;
1239  }
1240  LeafNodeT& operator*() const { return *this->getLeaf(); }
1241  LeafNodeT* operator->() const { return this->getLeaf(); }
1243 
1244  bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); }
1245  operator bool() const { return this->test(); }
1246 
1248  bool next();
1250  void increment() { this->next(); }
1251  LeafIteratorBase& operator++() { this->increment(); return *this; }
1253  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1255 
1256  TreeT* getTree() const { return mTree; }
1257 
1258 private:
1259  struct PrevItem { using IterT = RootIterT; };
1260 
1264  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1265  TreeT* mTree;
1266 }; // class LeafIteratorBase
1267 
1268 
1269 template<typename TreeT, typename RootChildOnIterT>
1270 inline bool
1272 {
1273  // If the iterator is valid for the current node one level above the leaf level,
1274  // advance the iterator to the node's next child.
1275  if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1276  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1277  return true;
1278  }
1279 
1280  Index lvl = LEAF_PARENT_LEVEL;
1281  while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1282  if (mIterList.test(lvl)) {
1283  mIterList.next(lvl);
1284  } else {
1285  do {
1286  // Ascend to the nearest level at which
1287  // one of the iterators is not yet exhausted.
1288  if (lvl == ROOT_LEVEL) return false;
1289  ++lvl;
1290  if (mIterList.test(lvl)) mIterList.next(lvl);
1291  } while (!mIterList.test(lvl));
1292  }
1293  // Descend to the lowest child, but not as far as the leaf iterator.
1294  while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1295  }
1296  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1297  return true;
1298 }
1299 
1300 
1302 
1303 
1306 template<typename IterT>
1308 {
1309 public:
1310  IteratorRange(const IterT& iter, size_t grainSize = 8):
1311  mIter(iter),
1312  mGrainSize(grainSize),
1313  mSize(0)
1314  {
1315  mSize = this->size();
1316  }
1317  IteratorRange(IteratorRange& other, tbb::split):
1318  mIter(other.mIter),
1319  mGrainSize(other.mGrainSize),
1320  mSize(other.mSize >> 1)
1321  {
1322  other.increment(mSize);
1323  }
1324 
1328  const IterT& iterator() const { return mIter; }
1329 
1330  bool empty() const { return mSize == 0 || !mIter.test(); }
1331  bool test() const { return !this->empty(); }
1332  operator bool() const { return !this->empty(); }
1333 
1336  bool is_divisible() const { return mSize > mGrainSize; }
1337 
1339  void increment(Index n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1341  IteratorRange& operator++() { this->increment(); return *this; }
1344  bool next() { this->increment(); return this->test(); }
1345 
1346 private:
1347  Index size() const { Index n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; }
1348 
1349  IterT mIter;
1350  size_t mGrainSize;
1355  Index mSize;
1356 };
1357 
1358 
1360 
1361 
1364 
1365 } // namespace tree
1366 } // namespace OPENVDB_VERSION_NAME
1367 } // namespace openvdb
1368 
1369 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:463
LeafNodeT & operator*() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1240
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:120
typename OtherNodeT::ChildOffCIter Type
Definition: TreeIterator.h:111
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:534
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:585
LeafIteratorBase(TreeT &tree)
Definition: TreeIterator.h:1207
static IterT begin(NodeT &node)
Definition: TreeIterator.h:73
An IterListItem is an element of a compile-time linked list of iterators to nodes of different types...
Definition: TreeIterator.h:218
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:197
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Initialize the iterator for level lvl of the tree with the node over which the corresponding iterator...
Definition: TreeIterator.h:278
typename OtherNodeT::ChildOnIter Type
Definition: TreeIterator.h:78
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:525
void setIter(const IterT &iter)
Definition: TreeIterator.h:259
typename NodeT::ValueAllCIter IterT
Definition: TreeIterator.h:196
typename NodeT::ChildAllIter IterT
Definition: TreeIterator.h:118
typename OtherNodeT::ChildAllIter Type
Definition: TreeIterator.h:125
void increment(Index n=1)
Advance the iterator n times.
Definition: TreeIterator.h:1339
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:621
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:483
typename CopyConstness< NodeT, typename NodeT::ChildNodeType >::Type ChildT
NodeT&#39;s child node type, with the same constness (e.g., const InternalNode<...>)
Definition: TreeIterator.h:236
TreeValueIteratorBase & operator=(const TreeValueIteratorBase &other)
Definition: TreeIterator.h:773
typename NodeT::ChildOnCIter ChildOnIterT
Definition: TreeIterator.h:628
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:587
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:86
Index pos(Index lvl) const
Definition: TreeIterator.h:568
bool isVoxelValue() const
Return true if this iterator is currently pointing to a (leaf) voxel value.
Definition: TreeIterator.h:691
TreeT * getTree() const
Definition: TreeIterator.h:1012
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:661
typename ValueIterT::NodeType NodeT
Definition: TreeIterator.h:626
TreeT * getTree() const
Return a pointer to the tree over which this iterator is iterating.
Definition: TreeIterator.h:720
_ValueIterT ValueIterT
Definition: TreeIterator.h:625
typename NodeT::ValueAllIter IterT
Definition: TreeIterator.h:186
void increment(Index n)
Increment the iterator n times.
Definition: TreeIterator.h:981
std::string summary() const
Return a string (for debugging, mainly) describing this iterator&#39;s current state. ...
Definition: TreeIterator.h:913
typename NodeT::ChildOffIter IterT
Definition: TreeIterator.h:98
static const Index LEAF_LEVEL
Definition: TreeIterator.h:631
TreeValueIteratorBase & operator++()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:657
static const Index ROOT_DEPTH
Definition: TreeIterator.h:631
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:1000
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:157
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:1196
void getNode(Index lvl, OtherNodeT *&node) const
Return the node over which one of the following list elements&#39; iterator iterates. ...
Definition: TreeIterator.h:270
static const Index ROOT_LEVEL
Definition: TreeIterator.h:629
const IterT & iterator() const
Return a reference to this range&#39;s iterator.
Definition: TreeIterator.h:1328
typename ValueIterT::NonConstValueType ValueT
Definition: TreeIterator.h:627
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:406
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:591
typename OtherNodeT::ValueOffIter Type
Definition: TreeIterator.h:169
bool test(Index lvl) const
Return true if the iterator at level lvl of the tree has not yet reached its end. ...
Definition: TreeIterator.h:294
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:454
typename CopyConstness< RootNodeT, NCLeafNodeT >::Type LeafNodeT
Definition: TreeIterator.h:1200
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:177
typename boost::mpl::front< InvTreeT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:224
typename boost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: TreeIterator.h:43
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:546
NodeIteratorBase()
Definition: TreeIterator.h:1029
_TreeT TreeT
Definition: TreeIterator.h:624
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:134
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:683
IteratorRange & operator++()
Advance the iterator to the next item.
Definition: TreeIterator.h:1341
bool next()
Advance to the next tile or voxel value. Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:810
typename NodeT::ValueOnCIter IterT
Definition: TreeIterator.h:156
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:523
static IterT begin(NodeT &node)
Definition: TreeIterator.h:99
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:245
IteratorRange(const IterT &iter, size_t grainSize=8)
Definition: TreeIterator.h:1310
typename OtherNodeT::ChildOnCIter Type
Definition: TreeIterator.h:91
void setValue(const ValueT &val) const
Change the tile or voxel value to which this iterator is currently pointing and mark it as active...
Definition: TreeIterator.h:704
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:408
IteratorRange(IteratorRange &other, tbb::split)
Definition: TreeIterator.h:1317
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:1138
typename NodeT::ChildOffCIter IterT
Definition: TreeIterator.h:108
void setValueOff(Index lvl) const
Definition: TreeIterator.h:600
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:791
static const Index LEAF_DEPTH
Definition: TreeIterator.h:631
bool next()
Advance the iterator to the next item.
Definition: TreeIterator.h:1344
static const Index LEAF_LEVEL
Definition: TreeIterator.h:949
bool down(Index lvl)
Definition: TreeIterator.h:574
bool next()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1271
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:945
Index64 getVoxelCount(Index lvl) const
Return the number of (virtual) voxels spanned by a tile value or child node.
Definition: TreeIterator.h:323
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:985
void setValueOff() const
Mark the tile or voxel value to which this iterator is currently pointing as inactive.
Definition: TreeIterator.h:709
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:515
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:948
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:553
typename boost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: TreeIterator.h:39
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:247
void setValueOn(Index lvl, bool on=true) const
Set the value (to val) to which the iterator at level lvl of the tree points and mark the value as ac...
Definition: TreeIterator.h:351
static IterT begin(NodeT &node)
Definition: TreeIterator.h:187
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:232
typename boost::mpl::front< InvTreeT >::type NCLeafNodeT
Definition: TreeIterator.h:1199
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:238
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:109
typename std::remove_const< ToType >::type Type
Definition: Types.h:298
typename NodeT::ValueOffCIter IterT
Definition: TreeIterator.h:176
void getNode(NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1007
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:427
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
static IterT begin(NodeT &node)
Definition: TreeIterator.h:119
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:397
bool empty() const
Definition: TreeIterator.h:1330
typename CopyConstness< NodeT, typename NodeT::ChildNodeType >::Type ChildT
NodeT&#39;s child node type, with the same constness (e.g., const InternalNode<...>)
Definition: TreeIterator.h:527
LeafIteratorBase(const LeafIteratorBase &other)
Definition: TreeIterator.h:1218
bool next(Index lvl)
Increment the iterator at level lvl of the tree.
Definition: TreeIterator.h:297
TreeT * getTree() const
Definition: TreeIterator.h:1256
Index pos(Index lvl) const
Return The table offset of the iterator at level lvl of the tree.
Definition: TreeIterator.h:291
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:230
bool test(Index lvl) const
Definition: TreeIterator.h:448
void setIter(const IterT &iter)
Definition: TreeIterator.h:551
typename boost::mpl::front< NodeVecT >::type _NodeT
Definition: TreeIterator.h:513
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:74
typename OtherNodeT::ChildOffIter Type
Definition: TreeIterator.h:101
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:257
static const Index ROOT_LEVEL
Definition: TreeIterator.h:947
void setValueOff(Index lvl) const
Definition: TreeIterator.h:487
bool next(Index lvl)
Definition: TreeIterator.h:450
bool next(Index lvl)
Definition: TreeIterator.h:572
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:1195
void setActiveState(bool on) const
Change the active/inactive state of the tile or voxel value to which this iterator is currently point...
Definition: TreeIterator.h:707
typename NodeT::ChildOnCIter IterT
Definition: TreeIterator.h:85
bool is_divisible() const
Return true if this range is splittable (i.e., if the iterator can be advanced more than mGrainSize t...
Definition: TreeIterator.h:1336
typename InvertedTree< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: TreeIterator.h:38
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:529
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:395
static Index getLeafDepth()
Definition: TreeIterator.h:665
std::string summary() const
Definition: TreeIterator.h:1169
Definition: Exceptions.h:13
void modifyValue(Index lvl, const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing.
Definition: TreeIterator.h:366
void getNode(const NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1009
Level
Message severity level.
Definition: logging.h:31
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:676
Coord getCoord(Index lvl) const
Return the global coordinates of the voxel or tile to which the iterator at level lvl of the tree is ...
Definition: TreeIterator.h:314
bool test(Index lvl) const
Definition: TreeIterator.h:570
Definition: TreeIterator.h:37
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:988
Definition: TreeIterator.h:64
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:586
static IterT begin(NodeT &node)
Definition: TreeIterator.h:147
typename OtherNodeT::ValueOnIter Type
Definition: TreeIterator.h:149
void getNode(Index lvl, NodeT *&node) const
Return the node over which this list element&#39;s iterator iterates.
Definition: TreeIterator.h:264
static IterT begin(NodeT &node)
Definition: TreeIterator.h:167
bool isValueOn() const
Return true if the value to which this iterator is currently pointing is active.
Definition: TreeIterator.h:693
NodeIteratorBase & operator++()
Definition: TreeIterator.h:979
NodeIteratorBase & operator=(const NodeIteratorBase &other)
Definition: TreeIterator.h:1070
bool down(Index lvl)
If the iterator at level lvl of the tree points to a child node, initialize the next iterator in this...
Definition: TreeIterator.h:301
Library and file format version numbers.
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1191
bool next()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:1106
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:473
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:800
Definition: TreeIterator.h:1307
static Index getLeafDepth()
Definition: TreeIterator.h:989
typename NodeT::ChildAllCIter IterT
Definition: TreeIterator.h:132
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:458
typename boost::mpl::front< NodeVecT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:389
typename PrevItem::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:222
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:435
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:1087
static const ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:87
Index32 Index
Definition: Types.h:31
LeafNodeT * operator->() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1241
RootChildOnIterT RootIterT
Definition: TreeIterator.h:944
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:966
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:425
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:133
void setValueOff(Index lvl) const
Mark the value to which the iterator at level lvl of the tree points as inactive. ...
Definition: TreeIterator.h:358
typename IterT::NodeType NodeT
The type of node over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:521
bool isValueOn(Index lvl) const
Return true if the iterator at level lvl of the tree points to an active value.
Definition: TreeIterator.h:329
bool down(Index lvl)
Definition: TreeIterator.h:452
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:603
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:536
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:387
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:559
TreeValueIteratorBase(TreeT &)
Definition: TreeIterator.h:742
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:243
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:261
Index pos(Index lvl) const
Definition: TreeIterator.h:446
typename NodeT::ValueOnIter IterT
Definition: TreeIterator.h:146
_TreeT TreeT
Definition: TreeIterator.h:943
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:102
const ValueT & operator*() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:698
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:618
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., RootNode::ValueOnCIter)
Definition: TreeIterator.h:518
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:468
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:589
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:641
typename NodeT::ValueOffIter IterT
Definition: TreeIterator.h:166
typename OtherNodeT::ChildAllCIter Type
Definition: TreeIterator.h:139
typename OtherNodeT::ValueAllCIter Type
Definition: TreeIterator.h:199
static ChildT * getChild(const IterT &)
Definition: TreeIterator.h:66
LeafIteratorBase()
Definition: TreeIterator.h:1205
uint64_t Index64
Definition: Types.h:30
LeafIteratorBase & operator=(const LeafIteratorBase &other)
Definition: TreeIterator.h:1222
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:493
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:1198
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:598
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:645
void updateBackPointers(PrevItemT *=nullptr)
Definition: TreeIterator.h:418
const NCValueT & getValue(Index lvl) const
Return the value to which the iterator at level lvl of the tree points.
Definition: TreeIterator.h:335
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:970
typename OtherNodeT::ValueOffCIter Type
Definition: TreeIterator.h:179
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
typename OtherNodeT::ValueOnCIter Type
Definition: TreeIterator.h:159
typename NodeT::ChildOnIter IterT
Definition: TreeIterator.h:72
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
Definition: TreeIterator.h:227
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:940
const ValueT * operator->() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:699
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:1096
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:649
void getNode(NodeType *&node) const
Return in node a pointer to the node over which this iterator is currently iterating or one of that n...
Definition: TreeIterator.h:672
LeafIteratorBase & operator++()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1251
bool test() const
Definition: TreeIterator.h:1331
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:234
void modifyValue(const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing. (Not valid for const iterators...
Definition: TreeIterator.h:717
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:599
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:318
bool test() const
Definition: TreeIterator.h:1244
void setValue(Index lvl, const NCValueT &val) const
Set the value (to val) to which the iterator at level lvl of the tree points and mark the value as ac...
Definition: TreeIterator.h:344
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:978
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:479
void setIter(const IterT &iter)
Definition: TreeIterator.h:423
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:962
bool isTileValue() const
Return true if this iterator is currently pointing to a (non-leaf) tile value.
Definition: TreeIterator.h:689
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:537
typename IterTraits< typename PrevIterT::NonConstNodeType, PrevIterT >::template NodeConverter< _NodeT >::Type IterT
The type of iterator stored in this list item (e.g., InternalNode::ValueOnCIter)
Definition: TreeIterator.h:392
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:399
Index64 getVoxelCount() const
Return the number of (virtual) voxels corresponding to the value.
Definition: TreeIterator.h:686
typename OtherNodeT::ValueAllIter Type
Definition: TreeIterator.h:189
void getNode(Index lvl, OtherNodeT *&node) const
Definition: TreeIterator.h:432
RootChildOnIterT RootIterT
Definition: TreeIterator.h:1194
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:946
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:664
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1250