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