OpenVDB  6.2.1
TreeIterator.h
Go to the documentation of this file.
1 //
3 // Copyright (c) DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
32 
33 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
34 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
35 
36 #include <boost/mpl/front.hpp>
37 #include <boost/mpl/pop_front.hpp>
38 #include <boost/mpl/push_back.hpp>
39 #include <boost/mpl/size.hpp>
40 #include <boost/mpl/vector.hpp>
41 #include <tbb/blocked_range.h>
42 #include <tbb/parallel_for.h>
43 #include <openvdb/version.h>
44 #include <openvdb/Types.h>
45 #include <algorithm>
46 #include <sstream>
47 #include <string>
48 #include <type_traits>
49 
50 // Prior to 0.96.1, depth-bounded value iterators always descended to the leaf level
51 // and iterated past leaf nodes. Now, they never descend past the maximum depth.
52 // Comment out the following line to restore the older, less-efficient behavior:
53 #define ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
54 
55 
56 namespace openvdb {
58 namespace OPENVDB_VERSION_NAME {
59 namespace tree {
60 
61 namespace iter {
62 
63 template<typename HeadT, int HeadLevel>
64 struct InvertedTree {
65  using SubtreeT = typename InvertedTree<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
66  using Type = typename boost::mpl::push_back<SubtreeT, HeadT>::type;
67 };
68 template<typename HeadT>
69 struct InvertedTree<HeadT, /*HeadLevel=*/1> {
70  using Type = typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type;
71 };
72 
73 } // namespace iter
74 
75 
77 
78 
90 template<typename NodeT, typename IterT>
91 struct IterTraits
92 {
93  template<typename ChildT> static ChildT* getChild(const IterT&) { return nullptr; }
94 };
95 
96 template<typename NodeT>
97 struct IterTraits<NodeT, typename NodeT::ChildOnIter>
98 {
99  using IterT = typename NodeT::ChildOnIter;
100  static IterT begin(NodeT& node) { return node.beginChildOn(); }
101  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
102  return &iter.getValue();
103  }
104  template<typename OtherNodeT> struct NodeConverter {
105  using Type = typename OtherNodeT::ChildOnIter;
106  };
107 };
108 
109 template<typename NodeT>
110 struct IterTraits<NodeT, typename NodeT::ChildOnCIter>
111 {
112  using IterT = typename NodeT::ChildOnCIter;
113  static IterT begin(const NodeT& node) { return node.cbeginChildOn(); }
114  template<typename ChildT> static const ChildT* getChild(const IterT& iter) {
115  return &iter.getValue();
116  }
117  template<typename OtherNodeT> struct NodeConverter {
118  using Type = typename OtherNodeT::ChildOnCIter;
119  };
120 };
121 
122 template<typename NodeT>
123 struct IterTraits<NodeT, typename NodeT::ChildOffIter>
124 {
125  using IterT = typename NodeT::ChildOffIter;
126  static IterT begin(NodeT& node) { return node.beginChildOff(); }
127  template<typename OtherNodeT> struct NodeConverter {
128  using Type = typename OtherNodeT::ChildOffIter;
129  };
130 };
131 
132 template<typename NodeT>
133 struct IterTraits<NodeT, typename NodeT::ChildOffCIter>
134 {
135  using IterT = typename NodeT::ChildOffCIter;
136  static IterT begin(const NodeT& node) { return node.cbeginChildOff(); }
137  template<typename OtherNodeT> struct NodeConverter {
138  using Type = typename OtherNodeT::ChildOffCIter;
139  };
140 };
141 
142 template<typename NodeT>
143 struct IterTraits<NodeT, typename NodeT::ChildAllIter>
144 {
145  using IterT = typename NodeT::ChildAllIter;
146  static IterT begin(NodeT& node) { return node.beginChildAll(); }
147  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
148  typename IterT::NonConstValueType val;
149  return iter.probeChild(val);
150  }
151  template<typename OtherNodeT> struct NodeConverter {
152  using Type = typename OtherNodeT::ChildAllIter;
153  };
154 };
155 
156 template<typename NodeT>
157 struct IterTraits<NodeT, typename NodeT::ChildAllCIter>
158 {
159  using IterT = typename NodeT::ChildAllCIter;
160  static IterT begin(const NodeT& node) { return node.cbeginChildAll(); }
161  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
162  typename IterT::NonConstValueType val;
163  return iter.probeChild(val);
164  }
165  template<typename OtherNodeT> struct NodeConverter {
166  using Type = typename OtherNodeT::ChildAllCIter;
167  };
168 };
169 
170 template<typename NodeT>
171 struct IterTraits<NodeT, typename NodeT::ValueOnIter>
172 {
173  using IterT = typename NodeT::ValueOnIter;
174  static IterT begin(NodeT& node) { return node.beginValueOn(); }
175  template<typename OtherNodeT> struct NodeConverter {
176  using Type = typename OtherNodeT::ValueOnIter;
177  };
178 };
179 
180 template<typename NodeT>
181 struct IterTraits<NodeT, typename NodeT::ValueOnCIter>
182 {
183  using IterT = typename NodeT::ValueOnCIter;
184  static IterT begin(const NodeT& node) { return node.cbeginValueOn(); }
185  template<typename OtherNodeT> struct NodeConverter {
186  using Type = typename OtherNodeT::ValueOnCIter;
187  };
188 };
189 
190 template<typename NodeT>
191 struct IterTraits<NodeT, typename NodeT::ValueOffIter>
192 {
193  using IterT = typename NodeT::ValueOffIter;
194  static IterT begin(NodeT& node) { return node.beginValueOff(); }
195  template<typename OtherNodeT> struct NodeConverter {
196  using Type = typename OtherNodeT::ValueOffIter;
197  };
198 };
199 
200 template<typename NodeT>
201 struct IterTraits<NodeT, typename NodeT::ValueOffCIter>
202 {
203  using IterT = typename NodeT::ValueOffCIter;
204  static IterT begin(const NodeT& node) { return node.cbeginValueOff(); }
205  template<typename OtherNodeT> struct NodeConverter {
206  using Type = typename OtherNodeT::ValueOffCIter;
207  };
208 };
209 
210 template<typename NodeT>
211 struct IterTraits<NodeT, typename NodeT::ValueAllIter>
212 {
213  using IterT = typename NodeT::ValueAllIter;
214  static IterT begin(NodeT& node) { return node.beginValueAll(); }
215  template<typename OtherNodeT> struct NodeConverter {
216  using Type = typename OtherNodeT::ValueAllIter;
217  };
218 };
219 
220 template<typename NodeT>
221 struct IterTraits<NodeT, typename NodeT::ValueAllCIter>
222 {
223  using IterT = typename NodeT::ValueAllCIter;
224  static IterT begin(const NodeT& node) { return node.cbeginValueAll(); }
225  template<typename OtherNodeT> struct NodeConverter {
226  using Type = typename OtherNodeT::ValueAllCIter;
227  };
228 };
229 
230 
232 
233 
244 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level>
246 {
247 public:
249  using PrevIterT = typename PrevItemT::IterT;
251  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
254  NodeConverter<_NodeT>::Type;
255 
257  using NodeT = typename IterT::NodeType;
259  using NCNodeT = typename IterT::NonConstNodeType;
261  using NCValueT = typename IterT::NonConstValueType;
268  static const Index Level = _Level;
269 
270  IterListItem(PrevItemT* prev): mNext(this), mPrev(prev) {}
271 
272  IterListItem(const IterListItem& other):
273  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
275  {
276  if (&other != this) {
277  mIter = other.mIter;
278  mNext = other.mNext;
279  mPrev = nullptr;
280  }
281  return *this;
282  }
283 
284  void updateBackPointers(PrevItemT* prev) { mPrev = prev; mNext.updateBackPointers(this); }
285 
286  void setIter(const IterT& iter) { mIter = iter; }
287  template<typename OtherIterT>
288  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
289 
291  void getNode(Index lvl, NodeT*& node) const
292  {
293  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
294  }
296  template<typename OtherNodeT>
297  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
298 
304  template<typename OtherIterListItemT>
305  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
306  {
307  if (lvl == Level) {
308  const NodeT* node = nullptr;
309  otherListItem.getNode(lvl, node);
310  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
311  } else {
312  // Forward to one of the following list elements.
313  mNext.initLevel(lvl, otherListItem);
314  }
315  }
316 
318  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
319 
321  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
322 
324  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
325 
328  bool down(Index lvl)
329  {
330  if (lvl == Level && mPrev != nullptr && mIter) {
331  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
332  mPrev->setIter(PrevItemT::ITraits::begin(*child));
333  return true;
334  }
335  }
336  return (lvl > Level) ? mNext.down(lvl) : false;
337  }
338 
341  Coord getCoord(Index lvl) const
342  {
343  return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
344  }
346  {
347  return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
348  }
351  {
352  return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
353  }
354 
356  bool isValueOn(Index lvl) const
357  {
358  return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
359  }
360 
362  const NCValueT& getValue(Index lvl) const
363  {
364  if (lvl == Level) return mIter.getValue();
365  return mNext.getValue(lvl);
366  }
367 
371  void setValue(Index lvl, const NCValueT& val) const
372  {
373  if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val);
374  }
378  void setValueOn(Index lvl, bool on = true) const
379  {
380  if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
381  }
385  void setValueOff(Index lvl) const
386  {
387  if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl);
388  }
389 
392  template<typename ModifyOp>
393  void modifyValue(Index lvl, const ModifyOp& op) const
394  {
395  if (lvl == Level) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
396  }
397 
398 private:
399  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
400  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, Level + 1>;
401 
402  IterT mIter;
403  NextItem mNext;
404  PrevItemT* mPrev;
405 };
406 
407 
409 template<typename PrevItemT, typename NodeVecT, size_t VecSize>
410 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U>
411 {
412 public:
414  using PrevIterT = typename PrevItemT::IterT;
416  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
419  NodeConverter<_NodeT>::Type;
420 
422  using NodeT = typename IterT::NodeType;
424  using NCNodeT = typename IterT::NonConstNodeType;
426  using NCValueT = typename IterT::NonConstValueType;
429  static const Index Level = 0;
430 
431  IterListItem(PrevItemT*): mNext(this), mPrev(nullptr) {}
432 
433  IterListItem(const IterListItem& other):
434  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
436  {
437  if (&other != this) {
438  mIter = other.mIter;
439  mNext = other.mNext;
440  mPrev = nullptr;
441  }
442  return *this;
443  }
444 
445  void updateBackPointers(PrevItemT* = nullptr)
446  {
447  mPrev = nullptr; mNext.updateBackPointers(this);
448  }
449 
450  void setIter(const IterT& iter) { mIter = iter; }
451  template<typename OtherIterT>
452  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
453 
454  void getNode(Index lvl, NodeT*& node) const
455  {
456  node = (lvl == 0) ? mIter.getParentNode() : nullptr;
457  }
458  template<typename OtherNodeT>
459  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
460 
461  template<typename OtherIterListItemT>
462  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
463  {
464  if (lvl == 0) {
465  const NodeT* node = nullptr;
466  otherListItem.getNode(lvl, node);
467  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
468  } else {
469  mNext.initLevel(lvl, otherListItem);
470  }
471  }
472 
473  Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
474 
475  bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
476 
477  bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
478 
479  bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); }
480 
481  Coord getCoord(Index lvl) const
482  {
483  return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
484  }
486  {
487  return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
488  }
489 
491  {
492  return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
493  }
494 
495  bool isValueOn(Index lvl) const
496  {
497  return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
498  }
499 
500  const NCValueT& getValue(Index lvl) const
501  {
502  if (lvl == 0) return mIter.getValue();
503  return mNext.getValue(lvl);
504  }
505 
506  void setValue(Index lvl, const NCValueT& val) const
507  {
508  if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val);
509  }
510  void setValueOn(Index lvl, bool on = true) const
511  {
512  if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
513  }
514  void setValueOff(Index lvl) const
515  {
516  if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl);
517  }
518 
519  template<typename ModifyOp>
520  void modifyValue(Index lvl, const ModifyOp& op) const
521  {
522  if (lvl == 0) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
523  }
524 
525 private:
526  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
527  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1>;
528 
529  IterT mIter;
530  NextItem mNext;
531  PrevItemT* mPrev;
532 };
533 
534 
536 template<typename PrevItemT, typename NodeVecT, Index _Level>
537 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level>
538 {
539 public:
540  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
542  using PrevIterT = typename PrevItemT::IterT;
545  NodeConverter<_NodeT>::Type;
546 
548  using NodeT = typename IterT::NodeType;
550  using NCNodeT = typename IterT::NonConstNodeType;
552  using NCValueT = typename IterT::NonConstValueType;
559  static const Index Level = _Level;
560 
561  IterListItem(PrevItemT* prev): mPrev(prev) {}
562 
563  IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(nullptr) {}
565  {
566  if (&other != this) {
567  mIter = other.mIter;
568  mPrev = nullptr;
569  }
570  return *this;
571  }
572 
573  void updateBackPointers(PrevItemT* prev) { mPrev = prev; }
574 
575  // The following method specializations differ from the default template
576  // implementations mainly in that they don't forward.
577 
578  void setIter(const IterT& iter) { mIter = iter; }
579 
580  void getNode(Index lvl, NodeT*& node) const
581  {
582  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
583  }
584 
585  template<typename OtherIterListItemT>
586  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
587  {
588  if (lvl == Level) {
589  const NodeT* node = nullptr;
590  otherListItem.getNode(lvl, node);
591  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
592  }
593  }
594 
595  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); }
596 
597  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; }
598 
599  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; }
600 
601  bool down(Index lvl)
602  {
603  if (lvl == Level && mPrev != nullptr && mIter) {
604  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
605  mPrev->setIter(PrevItemT::ITraits::begin(*child));
606  return true;
607  }
608  }
609  return false;
610  }
611 
612  Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); }
613  Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; }
614  Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; }
615 
616  bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; }
617 
618  const NCValueT& getValue(Index lvl) const
619  {
620  assert(lvl == Level);
621  (void)lvl; // avoid unused variable warning in optimized builds
622  return mIter.getValue();
623  }
624 
625  void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); }
626  void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); }
627  void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); }
628 
629  template<typename ModifyOp>
630  void modifyValue(Index lvl, const ModifyOp& op) const
631  {
632  if (lvl == Level) mIter.modifyValue(op);
633  }
634 
635 private:
636  IterT mIter;
637  PrevItemT* mPrev;
638 };
639 
640 
642 
643 
644 //#define DEBUG_TREE_VALUE_ITERATOR
645 
647 template<typename _TreeT, typename _ValueIterT>
649 {
650 public:
651  using TreeT = _TreeT;
652  using ValueIterT = _ValueIterT;
653  using NodeT = typename ValueIterT::NodeType;
654  using ValueT = typename ValueIterT::NonConstValueType;
655  using ChildOnIterT = typename NodeT::ChildOnCIter;
656  static const Index ROOT_LEVEL = NodeT::LEVEL;
657  static_assert(ValueIterT::NodeType::LEVEL == ROOT_LEVEL, "invalid value iterator node type");
658  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
659 
661 
663  TreeValueIteratorBase& operator=(const TreeValueIteratorBase& other);
664 
666  void setMinDepth(Index minDepth);
668  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
670  void setMaxDepth(Index maxDepth);
672  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
673 
675  bool test() const { return mValueIterList.test(mLevel); }
677  operator bool() const { return this->test(); }
679 
682  bool next();
684  TreeValueIteratorBase& operator++() { this->next(); return *this; }
685 
688  Index getLevel() const { return mLevel; }
691  Index getDepth() const { return ROOT_LEVEL - mLevel; }
692  static Index getLeafDepth() { return LEAF_DEPTH; }
693 
698  template<typename NodeType>
699  void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); }
700 
703  Coord getCoord() const { return mValueIterList.getCoord(mLevel); }
707  bool getBoundingBox(CoordBBox&) const;
710  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
711 
713  Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);}
714 
716  bool isTileValue() const { return mLevel != 0 && this->test(); }
718  bool isVoxelValue() const { return mLevel == 0 && this->test(); }
720  bool isValueOn() const { return mValueIterList.isValueOn(mLevel); }
721 
723  const ValueT& getValue() const { return mValueIterList.getValue(mLevel); }
725  const ValueT& operator*() const { return this->getValue(); }
726  const ValueT* operator->() const { return &(this->operator*()); }
728 
731  void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); }
734  void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); }
736  void setValueOff() const { mValueIterList.setValueOff(mLevel); }
737 
743  template<typename ModifyOp>
744  void modifyValue(const ModifyOp& op) const { mValueIterList.modifyValue(mLevel, op); }
745 
747  TreeT* getTree() const { return mTree; }
748 
750  std::string summary() const;
751 
752 private:
753  bool advance(bool dontIncrement = false);
754 
755  using InvTreeT = typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type;
756  struct PrevChildItem { using IterT = ChildOnIterT; };
757  struct PrevValueItem { using IterT = ValueIterT; };
758 
759  IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList;
760  IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList;
761  Index mLevel;
762  int mMinLevel, mMaxLevel;
763  TreeT* mTree;
764 }; // class TreeValueIteratorBase
765 
766 
767 template<typename TreeT, typename ValueIterT>
768 inline
770  mChildIterList(nullptr),
771  mValueIterList(nullptr),
772  mLevel(ROOT_LEVEL),
773  mMinLevel(int(LEAF_LEVEL)),
774  mMaxLevel(int(ROOT_LEVEL)),
775  mTree(&tree)
776 {
777  mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.root()));
778  mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.root()));
779  this->advance(/*dontIncrement=*/true);
780 }
781 
782 
783 template<typename TreeT, typename ValueIterT>
784 inline
786  mChildIterList(other.mChildIterList),
787  mValueIterList(other.mValueIterList),
788  mLevel(other.mLevel),
789  mMinLevel(other.mMinLevel),
790  mMaxLevel(other.mMaxLevel),
791  mTree(other.mTree)
792 {
793  mChildIterList.updateBackPointers();
794  mValueIterList.updateBackPointers();
795 }
796 
797 
798 template<typename TreeT, typename ValueIterT>
801 {
802  if (&other != this) {
803  mChildIterList = other.mChildIterList;
804  mValueIterList = other.mValueIterList;
805  mLevel = other.mLevel;
806  mMinLevel = other.mMinLevel;
807  mMaxLevel = other.mMaxLevel;
808  mTree = other.mTree;
809  mChildIterList.updateBackPointers();
810  mValueIterList.updateBackPointers();
811  }
812  return *this;
813 }
814 
815 
816 template<typename TreeT, typename ValueIterT>
817 inline void
819 {
820  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
821  if (int(mLevel) > mMaxLevel) this->next();
822 }
823 
824 
825 template<typename TreeT, typename ValueIterT>
826 inline void
828 {
829  // level = ROOT_LEVEL - depth
830  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
831  if (int(mLevel) < mMinLevel) this->next();
832 }
833 
834 
835 template<typename TreeT, typename ValueIterT>
836 inline bool
838 {
839  do {
840  if (!this->advance()) return false;
841  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
842  return true;
843 }
844 
845 
846 template<typename TreeT, typename ValueIterT>
847 inline bool
849 {
850  bool recurse = false;
851  do {
852  recurse = false;
853  Index
854  vPos = mValueIterList.pos(mLevel),
855  cPos = mChildIterList.pos(mLevel);
856  if (vPos == cPos && mChildIterList.test(mLevel)) {
858  mValueIterList.next(mLevel);
859  vPos = mValueIterList.pos(mLevel);
860  }
861  if (vPos < cPos) {
862  if (dontIncrement) return true;
863  if (mValueIterList.next(mLevel)) {
864  if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
867  mValueIterList.next(mLevel);
868  }
869  // If there is a next value and it precedes the next child, return.
870  if (mValueIterList.pos(mLevel) < cPos) return true;
871  }
872  } else {
873  // Advance to the next child, which may or may not precede the next value.
874  if (!dontIncrement) mChildIterList.next(mLevel);
875  }
876 #ifdef DEBUG_TREE_VALUE_ITERATOR
877  std::cout << "\n" << this->summary() << std::flush;
878 #endif
879 
880  // Descend to the lowest level at which the next value precedes the next child.
881  while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
882 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
883  if (int(mLevel) == mMinLevel) {
884  // If the current node lies at the lowest allowed level, none of its
885  // children can be visited, so just advance its child iterator.
886  mChildIterList.next(mLevel);
887  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
888  && mChildIterList.test(mLevel))
889  {
892  mValueIterList.next(mLevel);
893  }
894  } else
895 #endif
896  if (mChildIterList.down(mLevel)) {
897  --mLevel; // descend one level
898  mValueIterList.initLevel(mLevel, mChildIterList);
899  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
900  && mChildIterList.test(mLevel))
901  {
904  mValueIterList.next(mLevel);
905  }
906  } else break;
907 #ifdef DEBUG_TREE_VALUE_ITERATOR
908  std::cout << "\n" << this->summary() << std::flush;
909 #endif
910  }
911  // Ascend to the nearest level at which one of the iterators is not yet exhausted.
912  while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
913  if (mLevel == ROOT_LEVEL) return false;
914  ++mLevel;
915  mChildIterList.next(mLevel);
916  dontIncrement = true;
917  recurse = true;
918  }
919  } while (recurse);
920  return true;
921 }
922 
923 
924 template<typename TreeT, typename ValueIterT>
925 inline bool
927 {
928  if (!this->test()) {
929  bbox = CoordBBox();
930  return false;
931  }
932  bbox.min() = mValueIterList.getCoord(mLevel);
933  bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1);
934  return true;
935 }
936 
937 
938 template<typename TreeT, typename ValueIterT>
939 inline std::string
941 {
942  std::ostringstream ostr;
943  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
944  if (lvl == 0) ostr << "leaf";
945  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
946  else ostr << "int" << (ROOT_LEVEL - lvl);
947  ostr << " v" << mValueIterList.pos(lvl)
948  << " c" << mChildIterList.pos(lvl);
949  if (lvl > int(mLevel)) ostr << " / ";
950  }
951  if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
952  if (mLevel == 0) {
953  ostr << " " << this->getCoord();
954  } else {
955  ostr << " " << this->getBoundingBox();
956  }
957  }
958  return ostr.str();
959 }
960 
961 
963 
964 
966 template<typename _TreeT, typename RootChildOnIterT>
968 {
969 public:
970  using TreeT = _TreeT;
971  using RootIterT = RootChildOnIterT;
972  using RootNodeT = typename RootIterT::NodeType;
973  using NCRootNodeT = typename RootIterT::NonConstNodeType;
974  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
976  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
977 
979 
982 
983  NodeIteratorBase(const NodeIteratorBase& other);
985 
987  void setMinDepth(Index minDepth);
989  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
991  void setMaxDepth(Index maxDepth);
993  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
994 
996  bool test() const { return !mDone; }
998  operator bool() const { return this->test(); }
1000 
1003  bool next();
1005  void increment() { this->next(); }
1006  NodeIteratorBase& operator++() { this->increment(); return *this; }
1008  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1009 
1012  Index getLevel() const { return mLevel; }
1015  Index getDepth() const { return ROOT_LEVEL - mLevel; }
1016  static Index getLeafDepth() { return LEAF_DEPTH; }
1017 
1020  Coord getCoord() const;
1024  bool getBoundingBox(CoordBBox& bbox) const;
1027  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
1028 
1030  template<typename NodeT>
1034  void getNode(NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1035  template<typename NodeT>
1036  void getNode(const NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1038 
1039  TreeT* getTree() const { return mTree; }
1040 
1041  std::string summary() const;
1042 
1043 private:
1044  struct PrevItem { using IterT = RootIterT; };
1045 
1046  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1047  Index mLevel;
1048  int mMinLevel, mMaxLevel;
1049  bool mDone;
1050  TreeT* mTree;
1051 }; // class NodeIteratorBase
1052 
1053 
1054 template<typename TreeT, typename RootChildOnIterT>
1055 inline
1057  mIterList(nullptr),
1058  mLevel(ROOT_LEVEL),
1059  mMinLevel(int(LEAF_LEVEL)),
1060  mMaxLevel(int(ROOT_LEVEL)),
1061  mDone(true),
1062  mTree(nullptr)
1063 {
1064 }
1065 
1066 
1067 template<typename TreeT, typename RootChildOnIterT>
1068 inline
1070  mIterList(nullptr),
1071  mLevel(ROOT_LEVEL),
1072  mMinLevel(int(LEAF_LEVEL)),
1073  mMaxLevel(int(ROOT_LEVEL)),
1074  mDone(false),
1075  mTree(&tree)
1076 {
1077  mIterList.setIter(RootIterTraits::begin(tree.root()));
1078 }
1079 
1080 
1081 template<typename TreeT, typename RootChildOnIterT>
1082 inline
1084  mIterList(other.mIterList),
1085  mLevel(other.mLevel),
1086  mMinLevel(other.mMinLevel),
1087  mMaxLevel(other.mMaxLevel),
1088  mDone(other.mDone),
1089  mTree(other.mTree)
1090 {
1091  mIterList.updateBackPointers();
1092 }
1093 
1094 
1095 template<typename TreeT, typename RootChildOnIterT>
1098 {
1099  if (&other != this) {
1100  mLevel = other.mLevel;
1101  mMinLevel = other.mMinLevel;
1102  mMaxLevel = other.mMaxLevel;
1103  mDone = other.mDone;
1104  mTree = other.mTree;
1105  mIterList = other.mIterList;
1106  mIterList.updateBackPointers();
1107  }
1108  return *this;
1109 }
1110 
1111 
1112 template<typename TreeT, typename RootChildOnIterT>
1113 inline void
1115 {
1116  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
1117  if (int(mLevel) > mMaxLevel) this->next();
1118 }
1119 
1120 
1121 template<typename TreeT, typename RootChildOnIterT>
1122 inline void
1124 {
1125  // level = ROOT_LEVEL - depth
1126  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
1127  if (int(mLevel) < mMinLevel) this->next();
1128 }
1129 
1130 
1131 template<typename TreeT, typename RootChildOnIterT>
1132 inline bool
1134 {
1135  do {
1136  if (mDone) return false;
1137 
1138  // If the iterator over the current node points to a child,
1139  // descend to the child (depth-first traversal).
1140  if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1141  if (!mIterList.down(mLevel)) return false;
1142  --mLevel;
1143  } else {
1144  // Ascend to the nearest ancestor that has other children.
1145  while (!mIterList.test(mLevel)) {
1146  if (mLevel == ROOT_LEVEL) {
1147  // Can't ascend higher than the root.
1148  mDone = true;
1149  return false;
1150  }
1151  ++mLevel; // ascend one level
1152  mIterList.next(mLevel); // advance to the next child, if there is one
1153  }
1154  // Descend to the child.
1155  if (!mIterList.down(mLevel)) return false;
1156  --mLevel;
1157  }
1158  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1159  return true;
1160 }
1161 
1162 
1163 template<typename TreeT, typename RootChildOnIterT>
1164 inline Coord
1166 {
1167  if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1);
1168  RootNodeT* root = nullptr;
1169  this->getNode(root);
1170  return root ? root->getMinIndex() : Coord::min();
1171 }
1172 
1173 
1174 template<typename TreeT, typename RootChildOnIterT>
1175 inline bool
1177 {
1178  if (mLevel == ROOT_LEVEL) {
1179  RootNodeT* root = nullptr;
1180  this->getNode(root);
1181  if (root == nullptr) {
1182  bbox = CoordBBox();
1183  return false;
1184  }
1185  root->getIndexRange(bbox);
1186  return true;
1187  }
1188  bbox.min() = mIterList.getCoord(mLevel + 1);
1189  bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1190  return true;
1191 }
1192 
1193 
1194 template<typename TreeT, typename RootChildOnIterT>
1195 inline std::string
1197 {
1198  std::ostringstream ostr;
1199  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1200  if (lvl == 0) ostr << "leaf";
1201  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
1202  else ostr << "int" << (ROOT_LEVEL - lvl);
1203  ostr << " c" << mIterList.pos(lvl);
1204  if (lvl > int(mLevel)) ostr << " / ";
1205  }
1206  CoordBBox bbox;
1207  this->getBoundingBox(bbox);
1208  ostr << " " << bbox;
1209  return ostr.str();
1210 }
1211 
1212 
1214 
1215 
1217 template<typename TreeT, typename RootChildOnIterT>
1219 {
1220 public:
1221  using RootIterT = RootChildOnIterT;
1222  using RootNodeT = typename RootIterT::NodeType;
1223  using NCRootNodeT = typename RootIterT::NonConstNodeType;
1224  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
1226  using NCLeafNodeT = typename boost::mpl::front<InvTreeT>::type;
1228  static const Index LEAF_LEVEL = 0, LEAF_PARENT_LEVEL = LEAF_LEVEL + 1;
1229 
1231 
1232  LeafIteratorBase(): mIterList(nullptr), mTree(nullptr) {}
1233 
1234  LeafIteratorBase(TreeT& tree): mIterList(nullptr), mTree(&tree)
1235  {
1236  // Initialize the iterator list with a root node iterator.
1237  mIterList.setIter(RootIterTraits::begin(tree.root()));
1238  // Descend along the first branch, initializing the node iterator at each level.
1239  Index lvl = ROOT_LEVEL;
1240  for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {}
1241  // If the first branch terminated above the leaf level, backtrack to the next branch.
1242  if (lvl > 0) this->next();
1243  }
1244 
1245  LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree)
1246  {
1247  mIterList.updateBackPointers();
1248  }
1250  {
1251  if (&other != this) {
1252  mTree = other.mTree;
1253  mIterList = other.mIterList;
1254  mIterList.updateBackPointers();
1255  }
1256  return *this;
1257  }
1258 
1260  LeafNodeT* getLeaf() const
1262  {
1263  LeafNodeT* n = nullptr;
1264  mIterList.getNode(LEAF_LEVEL, n);
1265  return n;
1266  }
1267  LeafNodeT& operator*() const { return *this->getLeaf(); }
1268  LeafNodeT* operator->() const { return this->getLeaf(); }
1270 
1271  bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); }
1272  operator bool() const { return this->test(); }
1273 
1275  bool next();
1277  void increment() { this->next(); }
1278  LeafIteratorBase& operator++() { this->increment(); return *this; }
1280  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1282 
1283  TreeT* getTree() const { return mTree; }
1284 
1285 private:
1286  struct PrevItem { using IterT = RootIterT; };
1287 
1291  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1292  TreeT* mTree;
1293 }; // class LeafIteratorBase
1294 
1295 
1296 template<typename TreeT, typename RootChildOnIterT>
1297 inline bool
1299 {
1300  // If the iterator is valid for the current node one level above the leaf level,
1301  // advance the iterator to the node's next child.
1302  if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1303  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1304  return true;
1305  }
1306 
1307  Index lvl = LEAF_PARENT_LEVEL;
1308  while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1309  if (mIterList.test(lvl)) {
1310  mIterList.next(lvl);
1311  } else {
1312  do {
1313  // Ascend to the nearest level at which
1314  // one of the iterators is not yet exhausted.
1315  if (lvl == ROOT_LEVEL) return false;
1316  ++lvl;
1317  if (mIterList.test(lvl)) mIterList.next(lvl);
1318  } while (!mIterList.test(lvl));
1319  }
1320  // Descend to the lowest child, but not as far as the leaf iterator.
1321  while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1322  }
1323  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1324  return true;
1325 }
1326 
1327 
1329 
1330 
1333 template<typename IterT>
1335 {
1336 public:
1337  IteratorRange(const IterT& iter, size_t grainSize = 8):
1338  mIter(iter),
1339  mGrainSize(grainSize),
1340  mSize(0)
1341  {
1342  mSize = this->size();
1343  }
1344  IteratorRange(IteratorRange& other, tbb::split):
1345  mIter(other.mIter),
1346  mGrainSize(other.mGrainSize),
1347  mSize(other.mSize >> 1)
1348  {
1349  other.increment(mSize);
1350  }
1351 
1355  const IterT& iterator() const { return mIter; }
1356 
1357  bool empty() const { return mSize == 0 || !mIter.test(); }
1358  bool test() const { return !this->empty(); }
1359  operator bool() const { return !this->empty(); }
1360 
1363  bool is_divisible() const { return mSize > mGrainSize; }
1364 
1366  void increment(Index n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1368  IteratorRange& operator++() { this->increment(); return *this; }
1371  bool next() { this->increment(); return this->test(); }
1372 
1373 private:
1374  Index size() const { Index n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; }
1375 
1376  IterT mIter;
1377  size_t mGrainSize;
1382  Index mSize;
1383 };
1384 
1385 
1387 
1388 
1391 
1392 } // namespace tree
1393 } // namespace OPENVDB_VERSION_NAME
1394 } // namespace openvdb
1395 
1396 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
1397 
1398 // Copyright (c) DreamWorks Animation LLC
1399 // All rights reserved. This software is distributed under the
1400 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool next()
Advance the iterator to the next item.
Definition: TreeIterator.h:1371
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:973
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:580
static IterT begin(NodeT &node)
Definition: TreeIterator.h:214
typename NodeT::ChildOffIter IterT
Definition: TreeIterator.h:125
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:672
TreeT * getTree() const
Definition: TreeIterator.h:1283
typename NodeT::ValueOffIter IterT
Definition: TreeIterator.h:193
void increment(Index n)
Increment the iterator n times.
Definition: TreeIterator.h:1008
typename boost::mpl::front< NodeVecT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:416
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:305
typename ValueIterT::NonConstValueType ValueT
Definition: TreeIterator.h:654
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:989
void updateBackPointers(PrevItemT *=nullptr)
Definition: TreeIterator.h:445
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:204
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:1027
static const ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:114
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:485
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:1225
typename NodeT::ChildOffCIter IterT
Definition: TreeIterator.h:135
bool isVoxelValue() const
Return true if this iterator is currently pointing to a (leaf) voxel value.
Definition: TreeIterator.h:718
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:556
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:703
typename boost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: TreeIterator.h:66
typename NodeT::ValueAllIter IterT
Definition: TreeIterator.h:213
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:490
Index pos(Index lvl) const
Definition: TreeIterator.h:473
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:676
const NCValueT & getValue(Index lvl) const
Return the value to which the iterator at level lvl of the tree points.
Definition: TreeIterator.h:362
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:341
TreeT * getTree() const
Return a pointer to the tree over which this iterator is iterating.
Definition: TreeIterator.h:747
static IterT begin(NodeT &node)
Definition: TreeIterator.h:146
Index pos(Index lvl) const
Definition: TreeIterator.h:595
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:616
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:520
void setValueOff(Index lvl) const
Definition: TreeIterator.h:627
typename boost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: TreeIterator.h:70
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:668
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:261
typename OtherNodeT::ValueAllIter Type
Definition: TreeIterator.h:216
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:506
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:433
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:648
Index pos(Index lvl) const
Return The table offset of the iterator at level lvl of the tree.
Definition: TreeIterator.h:318
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:419
static const Index LEAF_LEVEL
Definition: TreeIterator.h:976
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:481
typename OtherNodeT::ChildOnCIter Type
Definition: TreeIterator.h:118
bool isValueOn() const
Return true if the value to which this iterator is currently pointing is active.
Definition: TreeIterator.h:720
RootChildOnIterT RootIterT
Definition: TreeIterator.h:1221
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:321
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:613
NodeIteratorBase()
Definition: TreeIterator.h:1056
LeafIteratorBase & operator++()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1278
Index32 Index
Definition: Types.h:61
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:614
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:422
bool test() const
Definition: TreeIterator.h:1271
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:731
Index64 getVoxelCount(Index lvl) const
Return the number of (virtual) voxels spanned by a tile value or child node.
Definition: TreeIterator.h:350
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:734
typename NodeT::ChildOnCIter IterT
Definition: TreeIterator.h:112
typename OtherNodeT::ValueOnIter Type
Definition: TreeIterator.h:176
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:563
void setValueOff() const
Mark the tile or voxel value to which this iterator is currently pointing as inactive.
Definition: TreeIterator.h:736
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:688
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:1165
typename IterT::NodeType NodeT
The type of node over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:548
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:452
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:552
void setIter(const IterT &iter)
Definition: TreeIterator.h:286
typename OtherNodeT::ValueOffIter Type
Definition: TreeIterator.h:196
IteratorRange & operator++()
Advance the iterator to the next item.
Definition: TreeIterator.h:1368
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1277
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:818
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:184
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:371
LeafIteratorBase()
Definition: TreeIterator.h:1232
bool isValueOn(Index lvl) const
Return true if the iterator at level lvl of the tree points to an active value.
Definition: TreeIterator.h:356
static const Index ROOT_LEVEL
Definition: TreeIterator.h:974
void increment(Index n=1)
Advance the iterator n times.
Definition: TreeIterator.h:1366
void modifyValue(Index lvl, const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing.
Definition: TreeIterator.h:393
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:586
static const Index LEAF_LEVEL
Definition: TreeIterator.h:658
LeafIteratorBase & operator=(const LeafIteratorBase &other)
Definition: TreeIterator.h:1249
bool next(Index lvl)
Increment the iterator at level lvl of the tree.
Definition: TreeIterator.h:324
void getNode(Index lvl, OtherNodeT *&node) const
Return the node over which one of the following list elements&#39; iterator iterates. ...
Definition: TreeIterator.h:297
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:573
TreeValueIteratorBase & operator++()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:684
bool test() const
Definition: TreeIterator.h:1358
typename OtherNodeT::ChildOffIter Type
Definition: TreeIterator.h:128
void getNode(Index lvl, NodeT *&node) const
Return the node over which this list element&#39;s iterator iterates.
Definition: TreeIterator.h:291
IteratorRange(IteratorRange &other, tbb::split)
Definition: TreeIterator.h:1344
TreeValueIteratorBase & operator=(const TreeValueIteratorBase &other)
Definition: TreeIterator.h:800
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:259
std::string summary() const
Definition: TreeIterator.h:1196
typename std::remove_const< ToType >::type Type
Definition: Types.h:348
_TreeT TreeT
Definition: TreeIterator.h:651
Definition: TreeIterator.h:91
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:101
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:426
typename boost::mpl::front< NodeVecT >::type _NodeT
Definition: TreeIterator.h:540
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
void getNode(NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1034
void setValueOff(Index lvl) const
Mark the value to which the iterator at level lvl of the tree points as inactive. ...
Definition: TreeIterator.h:385
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:328
LeafNodeT * operator->() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1268
typename OtherNodeT::ValueOnCIter Type
Definition: TreeIterator.h:186
typename NodeT::ValueOffCIter IterT
Definition: TreeIterator.h:203
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:645
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:618
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:435
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:972
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:500
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:975
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:1012
typename OtherNodeT::ValueOffCIter Type
Definition: TreeIterator.h:206
typename OtherNodeT::ChildOffCIter Type
Definition: TreeIterator.h:138
Definition: TreeIterator.h:64
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:113
typename ValueIterT::NodeType NodeT
Definition: TreeIterator.h:653
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:545
bool next()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:1133
Definition: Exceptions.h:40
An IterListItem is an element of a compile-time linked list of iterators to nodes of different types...
Definition: TreeIterator.h:245
Definition: TreeIterator.h:1334
bool next(Index lvl)
Definition: TreeIterator.h:477
bool test(Index lvl) const
Definition: TreeIterator.h:597
typename CopyConstness< RootNodeT, NCLeafNodeT >::Type LeafNodeT
Definition: TreeIterator.h:1227
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:1363
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:424
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:1114
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:1015
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:630
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:414
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:993
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:625
typename NodeT::ChildAllCIter IterT
Definition: TreeIterator.h:159
NodeIteratorBase & operator=(const NodeIteratorBase &other)
Definition: TreeIterator.h:1097
uint64_t Index64
Definition: Types.h:60
static const Index LEAF_DEPTH
Definition: TreeIterator.h:658
LeafNodeT & operator*() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1267
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:691
static IterT begin(NodeT &node)
Definition: TreeIterator.h:194
Library and file format version numbers.
NodeIteratorBase & operator++()
Definition: TreeIterator.h:1006
typename boost::mpl::front< InvTreeT >::type NCLeafNodeT
Definition: TreeIterator.h:1226
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:378
void getNode(const NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1036
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:542
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:147
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:160
RootChildOnIterT RootIterT
Definition: TreeIterator.h:971
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:265
bool next()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1298
const ValueT * operator->() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:726
Level
Message severity level.
Definition: logging.h:58
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:257
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:272
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:345
typename NodeT::ChildOnIter IterT
Definition: TreeIterator.h:99
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:1223
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:510
void getNode(Index lvl, OtherNodeT *&node) const
Definition: TreeIterator.h:459
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:274
_ValueIterT ValueIterT
Definition: TreeIterator.h:652
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:136
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:288
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:284
bool empty() const
Definition: TreeIterator.h:1357
bool next(Index lvl)
Definition: TreeIterator.h:599
static const Index ROOT_DEPTH
Definition: TreeIterator.h:658
typename boost::mpl::front< InvTreeT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:251
typename OtherNodeT::ChildAllCIter Type
Definition: TreeIterator.h:166
typename PrevItem::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:249
static Index getLeafDepth()
Definition: TreeIterator.h:692
void setIter(const IterT &iter)
Definition: TreeIterator.h:450
typename OtherNodeT::ChildAllIter Type
Definition: TreeIterator.h:152
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:454
typename InvertedTree< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: TreeIterator.h:65
IteratorRange(const IterT &iter, size_t grainSize=8)
Definition: TreeIterator.h:1337
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:270
std::string summary() const
Return a string (for debugging, mainly) describing this iterator&#39;s current state. ...
Definition: TreeIterator.h:940
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:626
static const Index ROOT_LEVEL
Definition: TreeIterator.h:656
_TreeT TreeT
Definition: TreeIterator.h:970
typename NodeT::ChildOnCIter ChildOnIterT
Definition: TreeIterator.h:655
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:263
static Index getLeafDepth()
Definition: TreeIterator.h:1016
typename NodeT::ChildAllIter IterT
Definition: TreeIterator.h:145
typename NodeT::ValueOnIter IterT
Definition: TreeIterator.h:173
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:967
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1005
void setValueOff(Index lvl) const
Definition: TreeIterator.h:514
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:550
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:564
LeafIteratorBase(TreeT &tree)
Definition: TreeIterator.h:1234
void setIter(const IterT &iter)
Definition: TreeIterator.h:578
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:462
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:997
const IterT & iterator() const
Return a reference to this range&#39;s iterator.
Definition: TreeIterator.h:1355
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:710
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:224
typename NodeT::ValueOnCIter IterT
Definition: TreeIterator.h:183
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:1123
typename OtherNodeT::ChildOnIter Type
Definition: TreeIterator.h:105
bool down(Index lvl)
Definition: TreeIterator.h:601
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:827
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:744
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:495
bool test(Index lvl) const
Definition: TreeIterator.h:475
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:554
LeafIteratorBase(const LeafIteratorBase &other)
Definition: TreeIterator.h:1245
typename NodeT::ValueAllCIter IterT
Definition: TreeIterator.h:223
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:699
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1218
TreeValueIteratorBase(TreeT &)
Definition: TreeIterator.h:769
static IterT begin(NodeT &node)
Definition: TreeIterator.h:100
Index64 getVoxelCount() const
Return the number of (virtual) voxels corresponding to the value.
Definition: TreeIterator.h:713
const ValueT & operator*() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:725
typename OtherNodeT::ValueAllCIter Type
Definition: TreeIterator.h:226
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:561
static ChildT * getChild(const IterT &)
Definition: TreeIterator.h:93
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:254
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:612
bool isTileValue() const
Return true if this iterator is currently pointing to a (non-leaf) tile value.
Definition: TreeIterator.h:716
bool next()
Advance to the next tile or voxel value. Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:837
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:1222
static IterT begin(NodeT &node)
Definition: TreeIterator.h:174
static IterT begin(NodeT &node)
Definition: TreeIterator.h:126
TreeT * getTree() const
Definition: TreeIterator.h:1039
bool down(Index lvl)
Definition: TreeIterator.h:479
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:161