OpenVDB  5.2.0
TreeIterator.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2018 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 
67 template<typename FromType, typename ToType> struct CopyConstness {
68  using Type = typename std::remove_const<ToType>::type;
69 };
70 template<typename FromType, typename ToType> struct CopyConstness<const FromType, ToType> {
71  using Type = const ToType;
72 };
73 
74 
76 
77 
78 namespace iter {
79 
80 template<typename HeadT, int HeadLevel>
81 struct InvertedTree {
82  using SubtreeT = typename InvertedTree<typename HeadT::ChildNodeType, HeadLevel-1>::Type;
83  using Type = typename boost::mpl::push_back<SubtreeT, HeadT>::type;
84 };
85 template<typename HeadT>
86 struct InvertedTree<HeadT, /*HeadLevel=*/1> {
87  using Type = typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type;
88 };
89 
90 } // namespace iter
91 
92 
94 
95 
107 template<typename NodeT, typename IterT>
109 {
110  template<typename ChildT> static ChildT* getChild(const IterT&) { return nullptr; }
111 };
112 
113 template<typename NodeT>
114 struct IterTraits<NodeT, typename NodeT::ChildOnIter>
115 {
116  using IterT = typename NodeT::ChildOnIter;
117  static IterT begin(NodeT& node) { return node.beginChildOn(); }
118  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
119  return &iter.getValue();
120  }
121  template<typename OtherNodeT> struct NodeConverter {
122  using Type = typename OtherNodeT::ChildOnIter;
123  };
124 };
125 
126 template<typename NodeT>
127 struct IterTraits<NodeT, typename NodeT::ChildOnCIter>
128 {
129  using IterT = typename NodeT::ChildOnCIter;
130  static IterT begin(const NodeT& node) { return node.cbeginChildOn(); }
131  template<typename ChildT> static const ChildT* getChild(const IterT& iter) {
132  return &iter.getValue();
133  }
134  template<typename OtherNodeT> struct NodeConverter {
135  using Type = typename OtherNodeT::ChildOnCIter;
136  };
137 };
138 
139 template<typename NodeT>
140 struct IterTraits<NodeT, typename NodeT::ChildOffIter>
141 {
142  using IterT = typename NodeT::ChildOffIter;
143  static IterT begin(NodeT& node) { return node.beginChildOff(); }
144  template<typename OtherNodeT> struct NodeConverter {
145  using Type = typename OtherNodeT::ChildOffIter;
146  };
147 };
148 
149 template<typename NodeT>
150 struct IterTraits<NodeT, typename NodeT::ChildOffCIter>
151 {
152  using IterT = typename NodeT::ChildOffCIter;
153  static IterT begin(const NodeT& node) { return node.cbeginChildOff(); }
154  template<typename OtherNodeT> struct NodeConverter {
155  using Type = typename OtherNodeT::ChildOffCIter;
156  };
157 };
158 
159 template<typename NodeT>
160 struct IterTraits<NodeT, typename NodeT::ChildAllIter>
161 {
162  using IterT = typename NodeT::ChildAllIter;
163  static IterT begin(NodeT& node) { return node.beginChildAll(); }
164  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
165  typename IterT::NonConstValueType val;
166  return iter.probeChild(val);
167  }
168  template<typename OtherNodeT> struct NodeConverter {
169  using Type = typename OtherNodeT::ChildAllIter;
170  };
171 };
172 
173 template<typename NodeT>
174 struct IterTraits<NodeT, typename NodeT::ChildAllCIter>
175 {
176  using IterT = typename NodeT::ChildAllCIter;
177  static IterT begin(const NodeT& node) { return node.cbeginChildAll(); }
178  template<typename ChildT> static ChildT* getChild(const IterT& iter) {
179  typename IterT::NonConstValueType val;
180  return iter.probeChild(val);
181  }
182  template<typename OtherNodeT> struct NodeConverter {
183  using Type = typename OtherNodeT::ChildAllCIter;
184  };
185 };
186 
187 template<typename NodeT>
188 struct IterTraits<NodeT, typename NodeT::ValueOnIter>
189 {
190  using IterT = typename NodeT::ValueOnIter;
191  static IterT begin(NodeT& node) { return node.beginValueOn(); }
192  template<typename OtherNodeT> struct NodeConverter {
193  using Type = typename OtherNodeT::ValueOnIter;
194  };
195 };
196 
197 template<typename NodeT>
198 struct IterTraits<NodeT, typename NodeT::ValueOnCIter>
199 {
200  using IterT = typename NodeT::ValueOnCIter;
201  static IterT begin(const NodeT& node) { return node.cbeginValueOn(); }
202  template<typename OtherNodeT> struct NodeConverter {
203  using Type = typename OtherNodeT::ValueOnCIter;
204  };
205 };
206 
207 template<typename NodeT>
208 struct IterTraits<NodeT, typename NodeT::ValueOffIter>
209 {
210  using IterT = typename NodeT::ValueOffIter;
211  static IterT begin(NodeT& node) { return node.beginValueOff(); }
212  template<typename OtherNodeT> struct NodeConverter {
213  using Type = typename OtherNodeT::ValueOffIter;
214  };
215 };
216 
217 template<typename NodeT>
218 struct IterTraits<NodeT, typename NodeT::ValueOffCIter>
219 {
220  using IterT = typename NodeT::ValueOffCIter;
221  static IterT begin(const NodeT& node) { return node.cbeginValueOff(); }
222  template<typename OtherNodeT> struct NodeConverter {
223  using Type = typename OtherNodeT::ValueOffCIter;
224  };
225 };
226 
227 template<typename NodeT>
228 struct IterTraits<NodeT, typename NodeT::ValueAllIter>
229 {
230  using IterT = typename NodeT::ValueAllIter;
231  static IterT begin(NodeT& node) { return node.beginValueAll(); }
232  template<typename OtherNodeT> struct NodeConverter {
233  using Type = typename OtherNodeT::ValueAllIter;
234  };
235 };
236 
237 template<typename NodeT>
238 struct IterTraits<NodeT, typename NodeT::ValueAllCIter>
239 {
240  using IterT = typename NodeT::ValueAllCIter;
241  static IterT begin(const NodeT& node) { return node.cbeginValueAll(); }
242  template<typename OtherNodeT> struct NodeConverter {
243  using Type = typename OtherNodeT::ValueAllCIter;
244  };
245 };
246 
247 
249 
250 
261 template<typename PrevItemT, typename NodeVecT, size_t VecSize, Index _Level>
263 {
264 public:
266  using PrevIterT = typename PrevItemT::IterT;
268  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
271  NodeConverter<_NodeT>::Type;
272 
274  using NodeT = typename IterT::NodeType;
276  using NCNodeT = typename IterT::NonConstNodeType;
278  using NCValueT = typename IterT::NonConstValueType;
285  static const Index Level = _Level;
286 
287  IterListItem(PrevItemT* prev): mNext(this), mPrev(prev) {}
288 
289  IterListItem(const IterListItem& other):
290  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
292  {
293  if (&other != this) {
294  mIter = other.mIter;
295  mNext = other.mNext;
296  mPrev = nullptr;
297  }
298  return *this;
299  }
300 
301  void updateBackPointers(PrevItemT* prev) { mPrev = prev; mNext.updateBackPointers(this); }
302 
303  void setIter(const IterT& iter) { mIter = iter; }
304  template<typename OtherIterT>
305  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
306 
308  void getNode(Index lvl, NodeT*& node) const
309  {
310  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
311  }
313  template<typename OtherNodeT>
314  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
315 
321  template<typename OtherIterListItemT>
322  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
323  {
324  if (lvl == Level) {
325  const NodeT* node = nullptr;
326  otherListItem.getNode(lvl, node);
327  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
328  } else {
329  // Forward to one of the following list elements.
330  mNext.initLevel(lvl, otherListItem);
331  }
332  }
333 
335  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
336 
338  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
339 
341  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
342 
345  bool down(Index lvl)
346  {
347  if (lvl == Level && mPrev != nullptr && mIter) {
348  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
349  mPrev->setIter(PrevItemT::ITraits::begin(*child));
350  return true;
351  }
352  }
353  return (lvl > Level) ? mNext.down(lvl) : false;
354  }
355 
358  Coord getCoord(Index lvl) const
359  {
360  return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
361  }
363  {
364  return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
365  }
368  {
369  return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
370  }
371 
373  bool isValueOn(Index lvl) const
374  {
375  return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
376  }
377 
379  const NCValueT& getValue(Index lvl) const
380  {
381  if (lvl == Level) return mIter.getValue();
382  return mNext.getValue(lvl);
383  }
384 
388  void setValue(Index lvl, const NCValueT& val) const
389  {
390  if (lvl == Level) mIter.setValue(val); else mNext.setValue(lvl, val);
391  }
395  void setValueOn(Index lvl, bool on = true) const
396  {
397  if (lvl == Level) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
398  }
402  void setValueOff(Index lvl) const
403  {
404  if (lvl == Level) mIter.setValueOff(); else mNext.setValueOff(lvl);
405  }
406 
409  template<typename ModifyOp>
410  void modifyValue(Index lvl, const ModifyOp& op) const
411  {
412  if (lvl == Level) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
413  }
414 
415 private:
416  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
417  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, Level + 1>;
418 
419  IterT mIter;
420  NextItem mNext;
421  PrevItemT* mPrev;
422 };
423 
424 
426 template<typename PrevItemT, typename NodeVecT, size_t VecSize>
427 class IterListItem<PrevItemT, NodeVecT, VecSize, /*Level=*/0U>
428 {
429 public:
431  using PrevIterT = typename PrevItemT::IterT;
433  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
436  NodeConverter<_NodeT>::Type;
437 
439  using NodeT = typename IterT::NodeType;
441  using NCNodeT = typename IterT::NonConstNodeType;
443  using NCValueT = typename IterT::NonConstValueType;
446  static const Index Level = 0;
447 
448  IterListItem(PrevItemT*): mNext(this), mPrev(nullptr) {}
449 
450  IterListItem(const IterListItem& other):
451  mIter(other.mIter), mNext(other.mNext), mPrev(nullptr) {}
453  {
454  if (&other != this) {
455  mIter = other.mIter;
456  mNext = other.mNext;
457  mPrev = nullptr;
458  }
459  return *this;
460  }
461 
462  void updateBackPointers(PrevItemT* = nullptr)
463  {
464  mPrev = nullptr; mNext.updateBackPointers(this);
465  }
466 
467  void setIter(const IterT& iter) { mIter = iter; }
468  template<typename OtherIterT>
469  void setIter(const OtherIterT& iter) { mNext.setIter(iter); }
470 
471  void getNode(Index lvl, NodeT*& node) const
472  {
473  node = (lvl == 0) ? mIter.getParentNode() : nullptr;
474  }
475  template<typename OtherNodeT>
476  void getNode(Index lvl, OtherNodeT*& node) const { mNext.getNode(lvl, node); }
477 
478  template<typename OtherIterListItemT>
479  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
480  {
481  if (lvl == 0) {
482  const NodeT* node = nullptr;
483  otherListItem.getNode(lvl, node);
484  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
485  } else {
486  mNext.initLevel(lvl, otherListItem);
487  }
488  }
489 
490  Index pos(Index lvl) const { return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
491 
492  bool test(Index lvl) const { return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
493 
494  bool next(Index lvl) { return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
495 
496  bool down(Index lvl) { return (lvl == 0) ? false : mNext.down(lvl); }
497 
498  Coord getCoord(Index lvl) const
499  {
500  return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
501  }
503  {
504  return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
505  }
506 
508  {
509  return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
510  }
511 
512  bool isValueOn(Index lvl) const
513  {
514  return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
515  }
516 
517  const NCValueT& getValue(Index lvl) const
518  {
519  if (lvl == 0) return mIter.getValue();
520  return mNext.getValue(lvl);
521  }
522 
523  void setValue(Index lvl, const NCValueT& val) const
524  {
525  if (lvl == 0) mIter.setValue(val); else mNext.setValue(lvl, val);
526  }
527  void setValueOn(Index lvl, bool on = true) const
528  {
529  if (lvl == 0) mIter.setValueOn(on); else mNext.setValueOn(lvl, on);
530  }
531  void setValueOff(Index lvl) const
532  {
533  if (lvl == 0) mIter.setValueOff(); else mNext.setValueOff(lvl);
534  }
535 
536  template<typename ModifyOp>
537  void modifyValue(Index lvl, const ModifyOp& op) const
538  {
539  if (lvl == 0) mIter.modifyValue(op); else mNext.modifyValue(lvl, op);
540  }
541 
542 private:
543  using RestT = typename boost::mpl::pop_front<NodeVecT>::type; // NodeVecT minus its first item
544  using NextItem = IterListItem<IterListItem, RestT, VecSize - 1, /*Level=*/1>;
545 
546  IterT mIter;
547  NextItem mNext;
548  PrevItemT* mPrev;
549 };
550 
551 
553 template<typename PrevItemT, typename NodeVecT, Index _Level>
554 class IterListItem<PrevItemT, NodeVecT, /*VecSize=*/1, _Level>
555 {
556 public:
557  using _NodeT = typename boost::mpl::front<NodeVecT>::type;
559  using PrevIterT = typename PrevItemT::IterT;
562  NodeConverter<_NodeT>::Type;
563 
565  using NodeT = typename IterT::NodeType;
567  using NCNodeT = typename IterT::NonConstNodeType;
569  using NCValueT = typename IterT::NonConstValueType;
576  static const Index Level = _Level;
577 
578  IterListItem(PrevItemT* prev): mPrev(prev) {}
579 
580  IterListItem(const IterListItem& other): mIter(other.mIter), mPrev(nullptr) {}
582  {
583  if (&other != this) {
584  mIter = other.mIter;
585  mPrev = nullptr;
586  }
587  return *this;
588  }
589 
590  void updateBackPointers(PrevItemT* prev) { mPrev = prev; }
591 
592  // The following method specializations differ from the default template
593  // implementations mainly in that they don't forward.
594 
595  void setIter(const IterT& iter) { mIter = iter; }
596 
597  void getNode(Index lvl, NodeT*& node) const
598  {
599  node = (lvl <= Level) ? mIter.getParentNode() : nullptr;
600  }
601 
602  template<typename OtherIterListItemT>
603  void initLevel(Index lvl, OtherIterListItemT& otherListItem)
604  {
605  if (lvl == Level) {
606  const NodeT* node = nullptr;
607  otherListItem.getNode(lvl, node);
608  mIter = (node == nullptr) ? IterT() : ITraits::begin(*const_cast<NodeT*>(node));
609  }
610  }
611 
612  Index pos(Index lvl) const { return (lvl == Level) ? mIter.pos() : Index(-1); }
613 
614  bool test(Index lvl) const { return (lvl == Level) ? mIter.test() : false; }
615 
616  bool next(Index lvl) { return (lvl == Level) ? mIter.next() : false; }
617 
618  bool down(Index lvl)
619  {
620  if (lvl == Level && mPrev != nullptr && mIter) {
621  if (ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
622  mPrev->setIter(PrevItemT::ITraits::begin(*child));
623  return true;
624  }
625  }
626  return false;
627  }
628 
629  Coord getCoord(Index lvl) const { return (lvl == Level) ? mIter.getCoord() : Coord(); }
630  Index getChildDim(Index lvl) const { return (lvl == Level) ? NodeT::getChildDim() : 0; }
631  Index64 getVoxelCount(Index lvl) const { return (lvl == Level) ? ChildT::NUM_VOXELS : 0; }
632 
633  bool isValueOn(Index lvl) const { return (lvl == Level) ? mIter.isValueOn() : false; }
634 
635  const NCValueT& getValue(Index lvl) const
636  {
637  assert(lvl == Level);
638  (void)lvl; // avoid unused variable warning in optimized builds
639  return mIter.getValue();
640  }
641 
642  void setValue(Index lvl, const NCValueT& val) const { if (lvl == Level) mIter.setValue(val); }
643  void setValueOn(Index lvl, bool on = true) const { if (lvl == Level) mIter.setValueOn(on); }
644  void setValueOff(Index lvl) const { if (lvl == Level) mIter.setValueOff(); }
645 
646  template<typename ModifyOp>
647  void modifyValue(Index lvl, const ModifyOp& op) const
648  {
649  if (lvl == Level) mIter.modifyValue(op);
650  }
651 
652 private:
653  IterT mIter;
654  PrevItemT* mPrev;
655 };
656 
657 
659 
660 
661 //#define DEBUG_TREE_VALUE_ITERATOR
662 
664 template<typename _TreeT, typename _ValueIterT>
666 {
667 public:
668  using TreeT = _TreeT;
669  using ValueIterT = _ValueIterT;
670  using NodeT = typename ValueIterT::NodeType;
671  using ValueT = typename ValueIterT::NonConstValueType;
672  using ChildOnIterT = typename NodeT::ChildOnCIter;
673  static const Index ROOT_LEVEL = NodeT::LEVEL;
674  static_assert(ValueIterT::NodeType::LEVEL == ROOT_LEVEL, "invalid value iterator node type");
675  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
676 
678 
680  TreeValueIteratorBase& operator=(const TreeValueIteratorBase& other);
681 
683  void setMinDepth(Index minDepth);
685  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
687  void setMaxDepth(Index maxDepth);
689  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
690 
692  bool test() const { return mValueIterList.test(mLevel); }
694  operator bool() const { return this->test(); }
696 
699  bool next();
701  TreeValueIteratorBase& operator++() { this->next(); return *this; }
702 
705  Index getLevel() const { return mLevel; }
708  Index getDepth() const { return ROOT_LEVEL - mLevel; }
709  static Index getLeafDepth() { return LEAF_DEPTH; }
710 
715  template<typename NodeType>
716  void getNode(NodeType*& node) const { mValueIterList.getNode(mLevel, node); }
717 
720  Coord getCoord() const { return mValueIterList.getCoord(mLevel); }
724  bool getBoundingBox(CoordBBox&) const;
727  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
728 
730  Index64 getVoxelCount() const { return mValueIterList.getVoxelCount(mLevel);}
731 
733  bool isTileValue() const { return mLevel != 0 && this->test(); }
735  bool isVoxelValue() const { return mLevel == 0 && this->test(); }
737  bool isValueOn() const { return mValueIterList.isValueOn(mLevel); }
738 
740  const ValueT& getValue() const { return mValueIterList.getValue(mLevel); }
742  const ValueT& operator*() const { return this->getValue(); }
743  const ValueT* operator->() const { return &(this->operator*()); }
745 
748  void setValue(const ValueT& val) const { mValueIterList.setValue(mLevel, val); }
751  void setActiveState(bool on) const { mValueIterList.setValueOn(mLevel, on); }
753  void setValueOff() const { mValueIterList.setValueOff(mLevel); }
754 
760  template<typename ModifyOp>
761  void modifyValue(const ModifyOp& op) const { mValueIterList.modifyValue(mLevel, op); }
762 
764  TreeT* getTree() const { return mTree; }
765 
767  std::string summary() const;
768 
769 private:
770  bool advance(bool dontIncrement = false);
771 
772  using InvTreeT = typename iter::InvertedTree<NodeT, NodeT::LEVEL>::Type;
773  struct PrevChildItem { using IterT = ChildOnIterT; };
774  struct PrevValueItem { using IterT = ValueIterT; };
775 
776  IterListItem<PrevChildItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mChildIterList;
777  IterListItem<PrevValueItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, /*Level=*/0> mValueIterList;
778  Index mLevel;
779  int mMinLevel, mMaxLevel;
780  TreeT* mTree;
781 }; // class TreeValueIteratorBase
782 
783 
784 template<typename TreeT, typename ValueIterT>
785 inline
787  mChildIterList(nullptr),
788  mValueIterList(nullptr),
789  mLevel(ROOT_LEVEL),
790  mMinLevel(int(LEAF_LEVEL)),
791  mMaxLevel(int(ROOT_LEVEL)),
792  mTree(&tree)
793 {
794  mChildIterList.setIter(IterTraits<NodeT, ChildOnIterT>::begin(tree.root()));
795  mValueIterList.setIter(IterTraits<NodeT, ValueIterT>::begin(tree.root()));
796  this->advance(/*dontIncrement=*/true);
797 }
798 
799 
800 template<typename TreeT, typename ValueIterT>
801 inline
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 {
810  mChildIterList.updateBackPointers();
811  mValueIterList.updateBackPointers();
812 }
813 
814 
815 template<typename TreeT, typename ValueIterT>
818 {
819  if (&other != this) {
820  mChildIterList = other.mChildIterList;
821  mValueIterList = other.mValueIterList;
822  mLevel = other.mLevel;
823  mMinLevel = other.mMinLevel;
824  mMaxLevel = other.mMaxLevel;
825  mTree = other.mTree;
826  mChildIterList.updateBackPointers();
827  mValueIterList.updateBackPointers();
828  }
829  return *this;
830 }
831 
832 
833 template<typename TreeT, typename ValueIterT>
834 inline void
836 {
837  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
838  if (int(mLevel) > mMaxLevel) this->next();
839 }
840 
841 
842 template<typename TreeT, typename ValueIterT>
843 inline void
845 {
846  // level = ROOT_LEVEL - depth
847  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
848  if (int(mLevel) < mMinLevel) this->next();
849 }
850 
851 
852 template<typename TreeT, typename ValueIterT>
853 inline bool
855 {
856  do {
857  if (!this->advance()) return false;
858  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
859  return true;
860 }
861 
862 
863 template<typename TreeT, typename ValueIterT>
864 inline bool
866 {
867  bool recurse = false;
868  do {
869  recurse = false;
870  Index
871  vPos = mValueIterList.pos(mLevel),
872  cPos = mChildIterList.pos(mLevel);
873  if (vPos == cPos && mChildIterList.test(mLevel)) {
875  mValueIterList.next(mLevel);
876  vPos = mValueIterList.pos(mLevel);
877  }
878  if (vPos < cPos) {
879  if (dontIncrement) return true;
880  if (mValueIterList.next(mLevel)) {
881  if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
884  mValueIterList.next(mLevel);
885  }
886  // If there is a next value and it precedes the next child, return.
887  if (mValueIterList.pos(mLevel) < cPos) return true;
888  }
889  } else {
890  // Advance to the next child, which may or may not precede the next value.
891  if (!dontIncrement) mChildIterList.next(mLevel);
892  }
893 #ifdef DEBUG_TREE_VALUE_ITERATOR
894  std::cout << "\n" << this->summary() << std::flush;
895 #endif
896 
897  // Descend to the lowest level at which the next value precedes the next child.
898  while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
899 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
900  if (int(mLevel) == mMinLevel) {
901  // If the current node lies at the lowest allowed level, none of its
902  // children can be visited, so just advance its child iterator.
903  mChildIterList.next(mLevel);
904  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
905  && mChildIterList.test(mLevel))
906  {
909  mValueIterList.next(mLevel);
910  }
911  } else
912 #endif
913  if (mChildIterList.down(mLevel)) {
914  --mLevel; // descend one level
915  mValueIterList.initLevel(mLevel, mChildIterList);
916  if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
917  && mChildIterList.test(mLevel))
918  {
921  mValueIterList.next(mLevel);
922  }
923  } else break;
924 #ifdef DEBUG_TREE_VALUE_ITERATOR
925  std::cout << "\n" << this->summary() << std::flush;
926 #endif
927  }
928  // Ascend to the nearest level at which one of the iterators is not yet exhausted.
929  while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
930  if (mLevel == ROOT_LEVEL) return false;
931  ++mLevel;
932  mChildIterList.next(mLevel);
933  dontIncrement = true;
934  recurse = true;
935  }
936  } while (recurse);
937  return true;
938 }
939 
940 
941 template<typename TreeT, typename ValueIterT>
942 inline bool
944 {
945  if (!this->test()) {
946  bbox = CoordBBox();
947  return false;
948  }
949  bbox.min() = mValueIterList.getCoord(mLevel);
950  bbox.max() = bbox.min().offsetBy(mValueIterList.getChildDim(mLevel) - 1);
951  return true;
952 }
953 
954 
955 template<typename TreeT, typename ValueIterT>
956 inline std::string
958 {
959  std::ostringstream ostr;
960  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
961  if (lvl == 0) ostr << "leaf";
962  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
963  else ostr << "int" << (ROOT_LEVEL - lvl);
964  ostr << " v" << mValueIterList.pos(lvl)
965  << " c" << mChildIterList.pos(lvl);
966  if (lvl > int(mLevel)) ostr << " / ";
967  }
968  if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
969  if (mLevel == 0) {
970  ostr << " " << this->getCoord();
971  } else {
972  ostr << " " << this->getBoundingBox();
973  }
974  }
975  return ostr.str();
976 }
977 
978 
980 
981 
983 template<typename _TreeT, typename RootChildOnIterT>
985 {
986 public:
987  using TreeT = _TreeT;
988  using RootIterT = RootChildOnIterT;
989  using RootNodeT = typename RootIterT::NodeType;
990  using NCRootNodeT = typename RootIterT::NonConstNodeType;
991  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
993  static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
994 
996 
999 
1000  NodeIteratorBase(const NodeIteratorBase& other);
1002 
1004  void setMinDepth(Index minDepth);
1006  Index getMinDepth() const { return ROOT_LEVEL - Index(mMaxLevel); }
1008  void setMaxDepth(Index maxDepth);
1010  Index getMaxDepth() const { return ROOT_LEVEL - Index(mMinLevel); }
1011 
1013  bool test() const { return !mDone; }
1015  operator bool() const { return this->test(); }
1017 
1020  bool next();
1022  void increment() { this->next(); }
1023  NodeIteratorBase& operator++() { this->increment(); return *this; }
1025  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1026 
1029  Index getLevel() const { return mLevel; }
1032  Index getDepth() const { return ROOT_LEVEL - mLevel; }
1033  static Index getLeafDepth() { return LEAF_DEPTH; }
1034 
1037  Coord getCoord() const;
1041  bool getBoundingBox(CoordBBox& bbox) const;
1044  CoordBBox getBoundingBox() const { CoordBBox b; this->getBoundingBox(b); return b; }
1045 
1047  template<typename NodeT>
1051  void getNode(NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1052  template<typename NodeT>
1053  void getNode(const NodeT*& node) const { node = nullptr; mIterList.getNode(mLevel, node); }
1055 
1056  TreeT* getTree() const { return mTree; }
1057 
1058  std::string summary() const;
1059 
1060 private:
1061  struct PrevItem { using IterT = RootIterT; };
1062 
1063  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1064  Index mLevel;
1065  int mMinLevel, mMaxLevel;
1066  bool mDone;
1067  TreeT* mTree;
1068 }; // class NodeIteratorBase
1069 
1070 
1071 template<typename TreeT, typename RootChildOnIterT>
1072 inline
1074  mIterList(nullptr),
1075  mLevel(ROOT_LEVEL),
1076  mMinLevel(int(LEAF_LEVEL)),
1077  mMaxLevel(int(ROOT_LEVEL)),
1078  mDone(true),
1079  mTree(nullptr)
1080 {
1081 }
1082 
1083 
1084 template<typename TreeT, typename RootChildOnIterT>
1085 inline
1087  mIterList(nullptr),
1088  mLevel(ROOT_LEVEL),
1089  mMinLevel(int(LEAF_LEVEL)),
1090  mMaxLevel(int(ROOT_LEVEL)),
1091  mDone(false),
1092  mTree(&tree)
1093 {
1094  mIterList.setIter(RootIterTraits::begin(tree.root()));
1095 }
1096 
1097 
1098 template<typename TreeT, typename RootChildOnIterT>
1099 inline
1101  mIterList(other.mIterList),
1102  mLevel(other.mLevel),
1103  mMinLevel(other.mMinLevel),
1104  mMaxLevel(other.mMaxLevel),
1105  mDone(other.mDone),
1106  mTree(other.mTree)
1107 {
1108  mIterList.updateBackPointers();
1109 }
1110 
1111 
1112 template<typename TreeT, typename RootChildOnIterT>
1115 {
1116  if (&other != this) {
1117  mLevel = other.mLevel;
1118  mMinLevel = other.mMinLevel;
1119  mMaxLevel = other.mMaxLevel;
1120  mDone = other.mDone;
1121  mTree = other.mTree;
1122  mIterList = other.mIterList;
1123  mIterList.updateBackPointers();
1124  }
1125  return *this;
1126 }
1127 
1128 
1129 template<typename TreeT, typename RootChildOnIterT>
1130 inline void
1132 {
1133  mMaxLevel = int(ROOT_LEVEL - minDepth); // level = ROOT_LEVEL - depth
1134  if (int(mLevel) > mMaxLevel) this->next();
1135 }
1136 
1137 
1138 template<typename TreeT, typename RootChildOnIterT>
1139 inline void
1141 {
1142  // level = ROOT_LEVEL - depth
1143  mMinLevel = int(ROOT_LEVEL - std::min(maxDepth, this->getLeafDepth()));
1144  if (int(mLevel) < mMinLevel) this->next();
1145 }
1146 
1147 
1148 template<typename TreeT, typename RootChildOnIterT>
1149 inline bool
1151 {
1152  do {
1153  if (mDone) return false;
1154 
1155  // If the iterator over the current node points to a child,
1156  // descend to the child (depth-first traversal).
1157  if (int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1158  if (!mIterList.down(mLevel)) return false;
1159  --mLevel;
1160  } else {
1161  // Ascend to the nearest ancestor that has other children.
1162  while (!mIterList.test(mLevel)) {
1163  if (mLevel == ROOT_LEVEL) {
1164  // Can't ascend higher than the root.
1165  mDone = true;
1166  return false;
1167  }
1168  ++mLevel; // ascend one level
1169  mIterList.next(mLevel); // advance to the next child, if there is one
1170  }
1171  // Descend to the child.
1172  if (!mIterList.down(mLevel)) return false;
1173  --mLevel;
1174  }
1175  } while (int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1176  return true;
1177 }
1178 
1179 
1180 template<typename TreeT, typename RootChildOnIterT>
1181 inline Coord
1183 {
1184  if (mLevel != ROOT_LEVEL) return mIterList.getCoord(mLevel + 1);
1185  RootNodeT* root = nullptr;
1186  this->getNode(root);
1187  return root ? root->getMinIndex() : Coord::min();
1188 }
1189 
1190 
1191 template<typename TreeT, typename RootChildOnIterT>
1192 inline bool
1194 {
1195  if (mLevel == ROOT_LEVEL) {
1196  RootNodeT* root = nullptr;
1197  this->getNode(root);
1198  if (root == nullptr) {
1199  bbox = CoordBBox();
1200  return false;
1201  }
1202  root->getIndexRange(bbox);
1203  return true;
1204  }
1205  bbox.min() = mIterList.getCoord(mLevel + 1);
1206  bbox.max() = bbox.min().offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1207  return true;
1208 }
1209 
1210 
1211 template<typename TreeT, typename RootChildOnIterT>
1212 inline std::string
1214 {
1215  std::ostringstream ostr;
1216  for (int lvl = int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1217  if (lvl == 0) ostr << "leaf";
1218  else if (lvl == int(ROOT_LEVEL)) ostr << "root";
1219  else ostr << "int" << (ROOT_LEVEL - lvl);
1220  ostr << " c" << mIterList.pos(lvl);
1221  if (lvl > int(mLevel)) ostr << " / ";
1222  }
1223  CoordBBox bbox;
1224  this->getBoundingBox(bbox);
1225  ostr << " " << bbox;
1226  return ostr.str();
1227 }
1228 
1229 
1231 
1232 
1234 template<typename TreeT, typename RootChildOnIterT>
1236 {
1237 public:
1238  using RootIterT = RootChildOnIterT;
1239  using RootNodeT = typename RootIterT::NodeType;
1240  using NCRootNodeT = typename RootIterT::NonConstNodeType;
1241  static const Index ROOT_LEVEL = RootNodeT::LEVEL;
1243  using NCLeafNodeT = typename boost::mpl::front<InvTreeT>::type;
1245  static const Index LEAF_LEVEL = 0, LEAF_PARENT_LEVEL = LEAF_LEVEL + 1;
1246 
1248 
1249  LeafIteratorBase(): mIterList(nullptr), mTree(nullptr) {}
1250 
1251  LeafIteratorBase(TreeT& tree): mIterList(nullptr), mTree(&tree)
1252  {
1253  // Initialize the iterator list with a root node iterator.
1254  mIterList.setIter(RootIterTraits::begin(tree.root()));
1255  // Descend along the first branch, initializing the node iterator at each level.
1256  Index lvl = ROOT_LEVEL;
1257  for ( ; lvl > 0 && mIterList.down(lvl); --lvl) {}
1258  // If the first branch terminated above the leaf level, backtrack to the next branch.
1259  if (lvl > 0) this->next();
1260  }
1261 
1262  LeafIteratorBase(const LeafIteratorBase& other): mIterList(other.mIterList), mTree(other.mTree)
1263  {
1264  mIterList.updateBackPointers();
1265  }
1267  {
1268  if (&other != this) {
1269  mTree = other.mTree;
1270  mIterList = other.mIterList;
1271  mIterList.updateBackPointers();
1272  }
1273  return *this;
1274  }
1275 
1277  LeafNodeT* getLeaf() const
1279  {
1280  LeafNodeT* n = nullptr;
1281  mIterList.getNode(LEAF_LEVEL, n);
1282  return n;
1283  }
1284  LeafNodeT& operator*() const { return *this->getLeaf(); }
1285  LeafNodeT* operator->() const { return this->getLeaf(); }
1287 
1288  bool test() const { return mIterList.test(LEAF_PARENT_LEVEL); }
1289  operator bool() const { return this->test(); }
1290 
1292  bool next();
1294  void increment() { this->next(); }
1295  LeafIteratorBase& operator++() { this->increment(); return *this; }
1297  void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} }
1299 
1300  TreeT* getTree() const { return mTree; }
1301 
1302 private:
1303  struct PrevItem { using IterT = RootIterT; };
1304 
1308  IterListItem<PrevItem, InvTreeT, /*VecSize=*/ROOT_LEVEL+1, LEAF_LEVEL> mIterList;
1309  TreeT* mTree;
1310 }; // class LeafIteratorBase
1311 
1312 
1313 template<typename TreeT, typename RootChildOnIterT>
1314 inline bool
1316 {
1317  // If the iterator is valid for the current node one level above the leaf level,
1318  // advance the iterator to the node's next child.
1319  if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1320  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1321  return true;
1322  }
1323 
1324  Index lvl = LEAF_PARENT_LEVEL;
1325  while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1326  if (mIterList.test(lvl)) {
1327  mIterList.next(lvl);
1328  } else {
1329  do {
1330  // Ascend to the nearest level at which
1331  // one of the iterators is not yet exhausted.
1332  if (lvl == ROOT_LEVEL) return false;
1333  ++lvl;
1334  if (mIterList.test(lvl)) mIterList.next(lvl);
1335  } while (!mIterList.test(lvl));
1336  }
1337  // Descend to the lowest child, but not as far as the leaf iterator.
1338  while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1339  }
1340  mIterList.down(LEAF_PARENT_LEVEL); // initialize the leaf iterator
1341  return true;
1342 }
1343 
1344 
1346 
1347 
1350 template<typename IterT>
1352 {
1353 public:
1354  IteratorRange(const IterT& iter, size_t grainSize = 8):
1355  mIter(iter),
1356  mGrainSize(grainSize),
1357  mSize(0)
1358  {
1359  mSize = this->size();
1360  }
1361  IteratorRange(IteratorRange& other, tbb::split):
1362  mIter(other.mIter),
1363  mGrainSize(other.mGrainSize),
1364  mSize(other.mSize >> 1)
1365  {
1366  other.increment(mSize);
1367  }
1368 
1372  const IterT& iterator() const { return mIter; }
1373 
1374  bool empty() const { return mSize == 0 || !mIter.test(); }
1375  bool test() const { return !this->empty(); }
1376  operator bool() const { return !this->empty(); }
1377 
1380  bool is_divisible() const { return mSize > mGrainSize; }
1381 
1383  void increment(Index n = 1) { for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1385  IteratorRange& operator++() { this->increment(); return *this; }
1388  bool next() { this->increment(); return this->test(); }
1389 
1390 private:
1391  Index size() const { Index n = 0; for (IterT it(mIter); it.test(); ++n, ++it) {} return n; }
1392 
1393  IterT mIter;
1394  size_t mGrainSize;
1399  Index mSize;
1400 };
1401 
1402 
1404 
1405 
1408 
1409 } // namespace tree
1410 } // namespace OPENVDB_VERSION_NAME
1411 } // namespace openvdb
1412 
1413 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
1414 
1415 // Copyright (c) 2012-2018 DreamWorks Animation LLC
1416 // All rights reserved. This software is distributed under the
1417 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool next()
Advance the iterator to the next item.
Definition: TreeIterator.h:1388
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:502
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:153
void getNode(NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1051
static IterT begin(NodeT &node)
Definition: TreeIterator.h:163
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:264
typename InvertedTree< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: TreeIterator.h:82
static Coord min()
Return the smallest possible coordinate.
Definition: Coord.h:70
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:452
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:990
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:395
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:441
Index pos(Index lvl) const
Definition: TreeIterator.h:612
void setValueOff(Index lvl) const
Definition: TreeIterator.h:531
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:287
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:573
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:431
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:603
RootChildOnIterT RootIterT
Definition: TreeIterator.h:988
bool test(Index lvl) const
Definition: TreeIterator.h:614
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:569
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:727
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:291
const NCValueT & getValue(Index lvl) const
Return the value to which the iterator at level lvl of the tree points.
Definition: TreeIterator.h:379
typename NodeT::ValueOnIter IterT
Definition: TreeIterator.h:190
typename boost::mpl::front< InvTreeT >::type NCLeafNodeT
Definition: TreeIterator.h:1243
bool next(Index lvl)
Definition: TreeIterator.h:494
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:1029
bool isValueOn() const
Return true if the value to which this iterator is currently pointing is active.
Definition: TreeIterator.h:737
typename CopyConstness< RootNodeT, NCLeafNodeT >::Type LeafNodeT
Definition: TreeIterator.h:1244
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:716
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:751
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:201
void setValueOff(Index lvl) const
Definition: TreeIterator.h:644
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:280
_ValueIterT ValueIterT
Definition: TreeIterator.h:669
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:642
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:984
bool isValueOn(Index lvl) const
Return true if the iterator at level lvl of the tree points to an active value.
Definition: TreeIterator.h:373
static const Index ROOT_DEPTH
Definition: TreeIterator.h:675
static Index getLeafDepth()
Definition: TreeIterator.h:1033
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:178
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:1380
const Coord & min() const
Definition: Coord.h:337
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:51
typename OtherNodeT::ChildOffIter Type
Definition: TreeIterator.h:145
static const Index ROOT_LEVEL
Definition: TreeIterator.h:991
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:345
const ValueT & operator*() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:742
static const Index ROOT_LEVEL
Definition: TreeIterator.h:673
bool isVoxelValue() const
Return true if this iterator is currently pointing to a (leaf) voxel value.
Definition: TreeIterator.h:735
void getNode(Index lvl, OtherNodeT *&node) const
Return the node over which one of the following list elements&#39; iterator iterates. ...
Definition: TreeIterator.h:314
typename NodeT::ChildOnCIter ChildOnIterT
Definition: TreeIterator.h:672
Definition: TreeIterator.h:108
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:1006
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:118
static IterT begin(NodeT &node)
Definition: TreeIterator.h:211
static const Index LEAF_DEPTH
Definition: TreeIterator.h:675
void setValueOff(Index lvl) const
Mark the value to which the iterator at level lvl of the tree points as inactive. ...
Definition: TreeIterator.h:402
bool isTileValue() const
Return true if this iterator is currently pointing to a (non-leaf) tile value.
Definition: TreeIterator.h:733
TreeT * getTree() const
Definition: TreeIterator.h:1300
bool next()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1315
static const Index LEAF_LEVEL
Definition: TreeIterator.h:993
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:507
Level
Message severity level.
Definition: logging.h:58
void increment(Index n)
Increment the iterator n times.
Definition: TreeIterator.h:1025
typename RootIterT::NonConstNodeType NCRootNodeT
Definition: TreeIterator.h:1240
typename NodeT::ValueAllCIter IterT
Definition: TreeIterator.h:240
typename OtherNodeT::ValueOffIter Type
Definition: TreeIterator.h:213
bool test(Index lvl) const
Definition: TreeIterator.h:492
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:322
static ChildT * getChild(const IterT &)
Definition: TreeIterator.h:110
LeafIteratorBase(TreeT &tree)
Definition: TreeIterator.h:1251
void initLevel(Index lvl, OtherIterListItemT &otherListItem)
Definition: TreeIterator.h:479
bool empty() const
Definition: TreeIterator.h:1374
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:1010
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:177
void setIter(const IterT &iter)
Definition: TreeIterator.h:467
static IterT begin(NodeT &node)
Definition: TreeIterator.h:143
IteratorRange & operator++()
Advance the iterator to the next item.
Definition: TreeIterator.h:1385
typename OtherNodeT::ValueAllIter Type
Definition: TreeIterator.h:233
typename OtherNodeT::ChildAllCIter Type
Definition: TreeIterator.h:183
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:567
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:1014
typename std::remove_const< ToType >::type Type
Definition: TreeIterator.h:68
typename OtherNodeT::ChildAllIter Type
Definition: TreeIterator.h:169
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:471
LeafIteratorBase(const LeafIteratorBase &other)
Definition: TreeIterator.h:1262
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:1140
static Index getLeafDepth()
Definition: TreeIterator.h:709
bool next(Index lvl)
Definition: TreeIterator.h:616
bool test() const
Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:693
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:635
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:748
bool next()
Advance to the next tile or voxel value. Return true if this iterator is not yet exhausted.
Definition: TreeIterator.h:854
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:498
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:289
typename boost::mpl::front< NodeVecT >::type _NodeT
Definition: TreeIterator.h:557
void increment(Index n=1)
Advance the iterator n times.
Definition: TreeIterator.h:1383
bool down(Index lvl)
Definition: TreeIterator.h:618
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:571
Coord getCoord(Index lvl) const
Definition: TreeIterator.h:629
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:305
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:301
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:665
typename boost::mpl::front< InvTreeT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:268
IteratorRange(IteratorRange &other, tbb::split)
Definition: TreeIterator.h:1361
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:1131
typename PrevItem ::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:266
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:1239
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:992
Index64 getVoxelCount(Index lvl) const
Return the number of (virtual) voxels spanned by a tile value or child node.
Definition: TreeIterator.h:367
typename NodeT::ChildOnCIter IterT
Definition: TreeIterator.h:129
Index getLevel() const
Return the level in the tree (0 = leaf) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:705
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
void getNode(Index lvl, NodeT *&node) const
Definition: TreeIterator.h:597
IterListItem(PrevItemT *prev)
Definition: TreeIterator.h:578
Index pos(Index lvl) const
Return The table offset of the iterator at level lvl of the tree.
Definition: TreeIterator.h:335
typename OtherNodeT::ChildOnCIter Type
Definition: TreeIterator.h:135
TreeT * getTree() const
Return a pointer to the tree over which this iterator is iterating.
Definition: TreeIterator.h:764
Definition: TreeIterator.h:81
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:274
Index getMinDepth() const
Return the depth of the highest level of the tree to which this iterator ascends. ...
Definition: TreeIterator.h:685
LeafNodeT & operator*() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1284
void getNode(Index lvl, NodeT *&node) const
Return the node over which this list element&#39;s iterator iterates.
Definition: TreeIterator.h:308
IterListItem & operator=(const IterListItem &other)
Definition: TreeIterator.h:581
void setIter(const IterT &iter)
Definition: TreeIterator.h:595
NodeIteratorBase & operator++()
Definition: TreeIterator.h:1023
void setMaxDepth(Index maxDepth)
Specify the depth of the lowest level of the tree to which to descend (depth 0 = root).
Definition: TreeIterator.h:844
void updateBackPointers(PrevItemT *prev)
Definition: TreeIterator.h:590
typename boost::mpl::front< NodeVecT >::type _NodeT
The type of node (non-const) whose iterator is stored in this list item.
Definition: TreeIterator.h:433
TreeValueIteratorBase(TreeT &)
Definition: TreeIterator.h:786
typename NodeT::ValueOnCIter IterT
Definition: TreeIterator.h:200
Index64 getVoxelCount(Index lvl) const
Definition: TreeIterator.h:631
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:241
const ToType Type
Definition: TreeIterator.h:71
void setValue(Index lvl, const NCValueT &val) const
Definition: TreeIterator.h:523
bool down(Index lvl)
Definition: TreeIterator.h:496
typename iter::InvertedTree< NCRootNodeT, ROOT_LEVEL >::Type InvTreeT
Definition: TreeIterator.h:1242
typename boost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: TreeIterator.h:87
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:630
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:278
Definition: Exceptions.h:40
static ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:164
bool test() const
Definition: TreeIterator.h:1375
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1235
Coord offsetBy(Int32 dx, Int32 dy, Int32 dz) const
Definition: Coord.h:118
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:358
static IterT begin(NodeT &node)
Definition: TreeIterator.h:231
bool test() const
Definition: TreeIterator.h:1288
void updateBackPointers(PrevItemT *=nullptr)
Definition: TreeIterator.h:462
bool next()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:1150
typename NodeT::ChildOffCIter IterT
Definition: TreeIterator.h:152
NodeIteratorBase()
Definition: TreeIterator.h:1073
Index32 Index
Definition: Types.h:61
typename NodeT::ChildOnIter IterT
Definition: TreeIterator.h:116
typename ValueIterT::NonConstValueType ValueT
Definition: TreeIterator.h:671
typename OtherNodeT::ValueAllCIter Type
Definition: TreeIterator.h:243
_TreeT TreeT
Definition: TreeIterator.h:987
An IterListItem is an element of a compile-time linked list of iterators to nodes of different types...
Definition: TreeIterator.h:262
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:450
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:338
typename RootIterT::NodeType RootNodeT
Definition: TreeIterator.h:989
uint64_t Index64
Definition: Types.h:60
Index64 getVoxelCount() const
Return the number of (virtual) voxels corresponding to the value.
Definition: TreeIterator.h:730
typename NodeT::ChildAllCIter IterT
Definition: TreeIterator.h:176
TreeT * getTree() const
Definition: TreeIterator.h:1056
void modifyValue(Index lvl, const ModifyOp &op) const
Apply a functor to the item to which this iterator is pointing.
Definition: TreeIterator.h:410
typename IterT::NonConstNodeType NCNodeT
The type of the node with const qualifiers removed ("Non-Const")
Definition: TreeIterator.h:276
RootChildOnIterT RootIterT
Definition: TreeIterator.h:1238
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:512
void setIter(const IterT &iter)
Definition: TreeIterator.h:303
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:720
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:271
typename OtherNodeT::ValueOnCIter Type
Definition: TreeIterator.h:203
Definition: TreeIterator.h:1351
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:130
static IterT begin(const NodeT &node)
Definition: TreeIterator.h:221
static IterT begin(NodeT &node)
Definition: TreeIterator.h:191
const NCValueT & getValue(Index lvl) const
Definition: TreeIterator.h:517
Index getChildDim(Index lvl) const
Definition: TreeIterator.h:362
bool next(Index lvl)
Increment the iterator at level lvl of the tree.
Definition: TreeIterator.h:341
void setMinDepth(Index minDepth)
Specify the depth of the highest level of the tree to which to ascend (depth 0 = root).
Definition: TreeIterator.h:835
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:436
void setIter(const OtherIterT &iter)
Definition: TreeIterator.h:469
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:537
void getNode(Index lvl, OtherNodeT *&node) const
Definition: TreeIterator.h:476
NodeIteratorBase & operator=(const NodeIteratorBase &other)
Definition: TreeIterator.h:1114
CoordBBox getBoundingBox() const
Return the axis-aligned bounding box of the voxel or tile to which this iterator is currently pointin...
Definition: TreeIterator.h:1044
IteratorRange(const IterT &iter, size_t grainSize=8)
Definition: TreeIterator.h:1354
LeafIteratorBase & operator++()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1295
const Coord & max() const
Definition: Coord.h:338
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:761
TreeValueIteratorBase & operator++()
Advance to the next tile or voxel value.
Definition: TreeIterator.h:701
typename IterT::NodeType NodeT
The type of node (const or non-const) over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:439
TreeValueIteratorBase & operator=(const TreeValueIteratorBase &other)
Definition: TreeIterator.h:817
bool isValueOn(Index lvl) const
Definition: TreeIterator.h:633
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
_TreeT TreeT
Definition: TreeIterator.h:668
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
typename boost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: TreeIterator.h:83
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:388
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1022
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:708
static const ChildT * getChild(const IterT &iter)
Definition: TreeIterator.h:131
std::string summary() const
Definition: TreeIterator.h:1213
std::string summary() const
Return a string (for debugging, mainly) describing this iterator&#39;s current state. ...
Definition: TreeIterator.h:957
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:562
void increment()
Advance the iterator to the next leaf node.
Definition: TreeIterator.h:1294
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:643
typename OtherNodeT::ValueOffCIter Type
Definition: TreeIterator.h:223
Coord getCoord() const
Return the global coordinates of the voxel or tile to which this iterator is currently pointing...
Definition: TreeIterator.h:1182
LeafIteratorBase()
Definition: TreeIterator.h:1249
const ValueT * operator->() const
Return the tile or voxel value to which this iterator is currently pointing.
Definition: TreeIterator.h:743
LeafNodeT * operator->() const
Return the leaf node to which the iterator is pointing.
Definition: TreeIterator.h:1285
Index getDepth() const
Return the depth in the tree (0 = root) of the node to which this iterator is currently pointing...
Definition: TreeIterator.h:1032
typename OtherNodeT::ChildOffCIter Type
Definition: TreeIterator.h:155
Index pos(Index lvl) const
Definition: TreeIterator.h:490
typename PrevItemT::IterT PrevIterT
The type of iterator stored in the previous list item.
Definition: TreeIterator.h:559
LeafIteratorBase & operator=(const LeafIteratorBase &other)
Definition: TreeIterator.h:1266
Definition: TreeIterator.h:67
Index getMaxDepth() const
Return the depth of the lowest level of the tree to which this iterator ascends.
Definition: TreeIterator.h:689
typename NodeT::ValueOffIter IterT
Definition: TreeIterator.h:210
typename NodeT::ValueOffCIter IterT
Definition: TreeIterator.h:220
typename OtherNodeT::ChildOnIter Type
Definition: TreeIterator.h:122
typename ValueIterT::NodeType NodeT
Definition: TreeIterator.h:670
typename IterT::NodeType NodeT
The type of node over which IterT iterates (e.g., const RootNode<...>)
Definition: TreeIterator.h:565
typename NodeT::ChildAllIter IterT
Definition: TreeIterator.h:162
void getNode(const NodeT *&node) const
Return the node to which the iterator is pointing.
Definition: TreeIterator.h:1053
void modifyValue(Index lvl, const ModifyOp &op) const
Definition: TreeIterator.h:647
IterListItem(const IterListItem &other)
Definition: TreeIterator.h:580
static IterT begin(NodeT &node)
Definition: TreeIterator.h:117
void setValueOn(Index lvl, bool on=true) const
Definition: TreeIterator.h:527
typename OtherNodeT::ValueOnIter Type
Definition: TreeIterator.h:193
typename CopyConstness< NCNodeT, typename NCNodeT::ChildNodeType >::Type NCChildT
NodeT&#39;s child node type with const qualifiers removed.
Definition: TreeIterator.h:282
static const Index LEAF_LEVEL
Definition: TreeIterator.h:675
void setValueOff() const
Mark the tile or voxel value to which this iterator is currently pointing as inactive.
Definition: TreeIterator.h:753
typename NodeT::ValueAllIter IterT
Definition: TreeIterator.h:230
typename NodeT::ChildOffIter IterT
Definition: TreeIterator.h:142
const IterT & iterator() const
Return a reference to this range&#39;s iterator.
Definition: TreeIterator.h:1372
typename IterT::NonConstValueType NCValueT
The type of value (with const qualifiers removed) to which the iterator points.
Definition: TreeIterator.h:443