33 #ifndef OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
34 #define OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED
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>
51 #define ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
66 typedef typename boost::remove_const<ToType>::type
Type;
68 template<
typename FromType,
typename ToType>
struct CopyConstness<const FromType, ToType> {
78 template<
typename HeadT,
int HeadLevel>
81 typedef typename boost::mpl::push_back<SubtreeT, HeadT>::type
Type;
83 template<
typename HeadT>
85 typedef typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type
Type;
105 template<
typename NodeT,
typename IterT>
108 template<
typename ChildT>
static ChildT*
getChild(
const IterT&) {
return NULL; }
111 template<
typename NodeT>
114 typedef typename NodeT::ChildOnIter
IterT;
115 static IterT begin(NodeT& node) {
return node.beginChildOn(); }
117 return &iter.getValue();
119 template<
typename OtherNodeT>
struct NodeConverter {
120 typedef typename OtherNodeT::ChildOnIter
Type;
124 template<
typename NodeT>
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();
132 template<
typename OtherNodeT>
struct NodeConverter {
133 typedef typename OtherNodeT::ChildOnCIter
Type;
137 template<
typename NodeT>
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;
147 template<
typename NodeT>
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;
157 template<
typename NodeT>
160 typedef typename NodeT::ChildAllIter
IterT;
161 static IterT begin(NodeT& node) {
return node.beginChildAll(); }
163 typename IterT::NonConstValueType val;
164 return iter.probeChild(val);
166 template<
typename OtherNodeT>
struct NodeConverter {
167 typedef typename OtherNodeT::ChildAllIter
Type;
171 template<
typename NodeT>
174 typedef typename NodeT::ChildAllCIter
IterT;
175 static IterT begin(
const NodeT& node) {
return node.cbeginChildAll(); }
177 typename IterT::NonConstValueType val;
178 return iter.probeChild(val);
180 template<
typename OtherNodeT>
struct NodeConverter {
181 typedef typename OtherNodeT::ChildAllCIter
Type;
185 template<
typename NodeT>
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;
195 template<
typename NodeT>
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;
205 template<
typename NodeT>
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;
215 template<
typename NodeT>
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;
225 template<
typename NodeT>
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;
235 template<
typename NodeT>
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;
259 template<
typename PrevItemT,
typename NodeVecT,
size_t VecSize, Index _Level>
266 typedef typename boost::mpl::front<NodeVecT>::type
_NodeT;
272 typedef typename IterT::NodeType
NodeT;
274 typedef typename IterT::NonConstNodeType
NCNodeT;
276 typedef typename IterT::NonConstValueType
NCValueT;
290 if (&other !=
this) {
301 template<
typename OtherIterT>
302 void setIter(
const OtherIterT& iter) { mNext.setIter(iter); }
307 node = (lvl <= Level) ? mIter.getParentNode() : NULL;
310 template<
typename OtherNodeT>
311 void getNode(
Index lvl, OtherNodeT*& node)
const { mNext.getNode(lvl, node); }
318 template<
typename OtherIterListItemT>
322 const NodeT* node = NULL;
323 otherListItem.getNode(lvl, node);
324 mIter = (node == NULL) ?
IterT() : ITraits::begin(*const_cast<NodeT*>(node));
327 mNext.initLevel(lvl, otherListItem);
332 Index pos(
Index lvl)
const {
return (lvl == Level) ? mIter.pos() : mNext.pos(lvl); }
335 bool test(
Index lvl)
const {
return (lvl == Level) ? mIter.test() : mNext.test(lvl); }
338 bool next(
Index lvl) {
return (lvl == Level) ? mIter.next() : mNext.next(lvl); }
344 if (lvl == Level && mPrev != NULL && mIter) {
345 if (
ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
346 mPrev->setIter(PrevItemT::ITraits::begin(*child));
350 return (lvl > Level) ? mNext.down(lvl) :
false;
357 return (lvl == Level) ? mIter.getCoord() : mNext.getCoord(lvl);
361 return (lvl == Level) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
366 return (lvl == Level) ? ChildT::NUM_VOXELS : mNext.getVoxelCount(lvl);
372 return (lvl == Level) ? mIter.isValueOn() : mNext.isValueOn(lvl);
378 if (lvl == Level)
return mIter.getValue();
379 return mNext.getValue(lvl);
387 if (lvl == Level) mIter.setValue(val);
else mNext.setValue(lvl, val);
394 if (lvl == Level) mIter.setValueOn(on);
else mNext.setValueOn(lvl, on);
401 if (lvl == Level) mIter.setValueOff();
else mNext.setValueOff(lvl);
405 typedef typename boost::mpl::pop_front<NodeVecT>::type RestT;
415 template<
typename PrevItemT,
typename NodeVecT,
size_t VecSize>
422 typedef typename boost::mpl::front<NodeVecT>::type
_NodeT;
428 typedef typename IterT::NodeType
NodeT;
430 typedef typename IterT::NonConstNodeType
NCNodeT;
432 typedef typename IterT::NonConstValueType
NCValueT;
442 if (&other !=
this) {
453 template<
typename OtherIterT>
454 void setIter(
const OtherIterT& iter) { mNext.setIter(iter); }
458 node = (lvl == 0) ? mIter.getParentNode() : NULL;
460 template<
typename OtherNodeT>
461 void getNode(
Index lvl, OtherNodeT*& node)
const { mNext.getNode(lvl, node); }
463 template<
typename OtherIterListItemT>
467 const NodeT* node = NULL;
468 otherListItem.getNode(lvl, node);
469 mIter = (node == NULL) ?
IterT() : ITraits::begin(*const_cast<NodeT*>(node));
471 mNext.initLevel(lvl, otherListItem);
475 Index pos(
Index lvl)
const {
return (lvl == 0) ? mIter.pos() : mNext.pos(lvl); }
477 bool test(
Index lvl)
const {
return (lvl == 0) ? mIter.test() : mNext.test(lvl); }
479 bool next(
Index lvl) {
return (lvl == 0) ? mIter.next() : mNext.next(lvl); }
481 bool down(
Index lvl) {
return (lvl == 0) ?
false : mNext.down(lvl); }
485 return (lvl == 0) ? mIter.getCoord() : mNext.getCoord(lvl);
489 return (lvl == 0) ? NodeT::getChildDim() : mNext.getChildDim(lvl);
494 return (lvl == 0) ? 1 : mNext.getVoxelCount(lvl);
499 return (lvl == 0) ? mIter.isValueOn() : mNext.isValueOn(lvl);
504 if (lvl == 0)
return mIter.getValue();
505 return mNext.getValue(lvl);
510 if (lvl == 0) mIter.setValue(val);
else mNext.setValue(lvl, val);
514 if (lvl == 0) mIter.setValueOn(on);
else mNext.setValueOn(lvl, on);
518 if (lvl == 0) mIter.setValueOff();
else mNext.setValueOff(lvl);
522 typedef typename boost::mpl::pop_front<NodeVecT>::type RestT;
532 template<
typename PrevItemT,
typename NodeVecT, Index _Level>
536 typedef typename boost::mpl::front<NodeVecT>::type
_NodeT;
544 typedef typename IterT::NodeType
NodeT;
546 typedef typename IterT::NonConstNodeType
NCNodeT;
548 typedef typename IterT::NonConstValueType
NCValueT;
562 if (&other !=
this) {
578 node = (lvl <= Level) ? mIter.getParentNode() : NULL;
581 template<
typename OtherIterListItemT>
585 const NodeT* node = NULL;
586 otherListItem.getNode(lvl, node);
587 mIter = (node == NULL) ?
IterT() : ITraits::begin(*const_cast<NodeT*>(node));
593 bool test(
Index lvl)
const {
return (lvl == Level) ? mIter.test() :
false; }
595 bool next(
Index lvl) {
return (lvl == Level) ? mIter.next() :
false; }
599 if (lvl == Level && mPrev != NULL && mIter) {
600 if (
ChildT* child = ITraits::template getChild<ChildT>(mIter)) {
601 mPrev->setIter(PrevItemT::ITraits::begin(*child));
612 bool isValueOn(
Index lvl)
const {
return (lvl == Level) ? mIter.isValueOn() :
false; }
616 assert(lvl == Level);
618 return mIter.getValue();
622 void setValueOn(
Index lvl,
bool on =
true)
const {
if (lvl == Level) mIter.setValueOn(on); }
637 template<
typename _TreeT,
typename ValueIterT>
642 typedef typename ValueIterT::NodeType
NodeT;
643 typedef typename ValueIterT::NonConstValueType
ValueT;
645 static const Index ROOT_LEVEL = NodeT::LEVEL;
646 BOOST_STATIC_ASSERT(ValueIterT::NodeType::LEVEL == ROOT_LEVEL);
647 static const Index LEAF_LEVEL = 0, ROOT_DEPTH = 0, LEAF_DEPTH = ROOT_LEVEL;
655 void setMinDepth(
Index minDepth);
659 void setMaxDepth(
Index maxDepth);
664 bool test()
const {
return mValueIterList.test(mLevel); }
666 operator bool()
const {
return this->test(); }
687 template<
typename NodeType>
688 void getNode(NodeType*& node)
const { mValueIterList.getNode(mLevel, node); }
709 bool isValueOn()
const {
return mValueIterList.isValueOn(mLevel); }
712 const ValueT& getValue()
const {
return mValueIterList.getValue(mLevel); }
731 std::string summary()
const;
734 bool advance(
bool dontIncrement =
false);
737 struct PrevChildItem {
typedef ChildOnIterT IterT; };
738 struct PrevValueItem {
typedef ValueIterT IterT; };
740 IterListItem<PrevChildItem, InvTreeT, ROOT_LEVEL+1, 0> mChildIterList;
741 IterListItem<PrevValueItem, InvTreeT, ROOT_LEVEL+1, 0> mValueIterList;
743 int mMinLevel, mMaxLevel;
748 template<
typename TreeT,
typename ValueIterT>
751 mChildIterList(NULL),
752 mValueIterList(NULL),
754 mMinLevel(int(LEAF_LEVEL)),
755 mMaxLevel(int(ROOT_LEVEL)),
764 template<
typename TreeT,
typename ValueIterT>
767 mChildIterList(other.mChildIterList),
768 mValueIterList(other.mValueIterList),
769 mLevel(other.mLevel),
770 mMinLevel(other.mMinLevel),
771 mMaxLevel(other.mMaxLevel),
779 template<
typename TreeT,
typename ValueIterT>
783 if (&other !=
this) {
784 mChildIterList = other.mChildIterList;
785 mValueIterList = other.mValueIterList;
786 mLevel = other.mLevel;
787 mMinLevel = other.mMinLevel;
788 mMaxLevel = other.mMaxLevel;
790 mChildIterList.updateBackPointers();
791 mValueIterList.updateBackPointers();
797 template<
typename TreeT,
typename ValueIterT>
801 mMaxLevel = int(ROOT_LEVEL - minDepth);
802 if (
int(mLevel) > mMaxLevel) this->next();
806 template<
typename TreeT,
typename ValueIterT>
811 mMinLevel = int(ROOT_LEVEL -
std::min(maxDepth, this->getLeafDepth()));
812 if (
int(mLevel) < mMinLevel) this->next();
816 template<
typename TreeT,
typename ValueIterT>
821 if (!this->advance())
return false;
822 }
while (
int(mLevel) < mMinLevel ||
int(mLevel) > mMaxLevel);
827 template<
typename TreeT,
typename ValueIterT>
832 vPos = mValueIterList.pos(mLevel),
833 cPos = mChildIterList.pos(mLevel);
834 if (vPos == cPos && mChildIterList.test(mLevel)) {
836 mValueIterList.
next(mLevel);
837 vPos = mValueIterList.pos(mLevel);
840 if (dontIncrement)
return true;
841 if (mValueIterList.next(mLevel)) {
842 if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
844 mValueIterList.next(mLevel);
847 if (mValueIterList.pos(mLevel) < cPos)
return true;
851 if (!dontIncrement) mChildIterList.next(mLevel);
853 #ifdef DEBUG_TREE_VALUE_ITERATOR
854 std::cout <<
"\n" << this->summary() << std::flush;
858 while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
859 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
860 if (
int(mLevel) == mMinLevel) {
865 while (mChildIterList.test(mLevel)) mChildIterList.next(mLevel);
868 if (mChildIterList.down(mLevel)) {
870 mValueIterList.initLevel(mLevel, mChildIterList);
871 if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
872 && mChildIterList.test(mLevel))
875 mValueIterList.next(mLevel);
878 #ifdef DEBUG_TREE_VALUE_ITERATOR
879 std::cout <<
"\n" << this->summary() << std::flush;
883 while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
884 if (mLevel == ROOT_LEVEL)
return false;
886 mChildIterList.next(mLevel);
893 template<
typename TreeT,
typename ValueIterT>
901 bbox.
min() = mValueIterList.getCoord(mLevel);
902 bbox.
max() = bbox.
min().
offsetBy(mValueIterList.getChildDim(mLevel) - 1);
907 template<
typename TreeT,
typename ValueIterT>
911 std::ostringstream ostr;
912 for (
int lvl =
int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
913 if (lvl == 0) ostr <<
"leaf";
914 else if (lvl ==
int(ROOT_LEVEL)) ostr <<
"root";
915 else ostr <<
"int" << (ROOT_LEVEL - lvl);
916 ostr <<
" v" << mValueIterList.pos(lvl)
917 <<
" c" << mChildIterList.pos(lvl);
918 if (lvl >
int(mLevel)) ostr <<
" / ";
920 if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
922 ostr <<
" " << this->getCoord();
924 ostr <<
" " << this->getBoundingBox();
935 template<
typename _TreeT,
typename RootChildOnIterT>
965 bool test()
const {
return !mDone; }
967 operator bool()
const {
return this->
test(); }
1001 template<
typename NodeT>
1009 struct PrevItem {
typedef RootIterT IterT; };
1013 int mMinLevel, mMaxLevel;
1019 template<
typename TreeT,
typename RootChildOnIterT>
1024 mMinLevel(int(LEAF_LEVEL)),
1025 mMaxLevel(int(ROOT_LEVEL)),
1032 template<
typename TreeT,
typename RootChildOnIterT>
1037 mMinLevel(int(LEAF_LEVEL)),
1038 mMaxLevel(int(ROOT_LEVEL)),
1042 mIterList.
setIter(RootIterTraits::begin(tree.getRootNode()));
1046 template<
typename TreeT,
typename RootChildOnIterT>
1049 mIterList(other.mIterList),
1050 mLevel(other.mLevel),
1051 mMinLevel(other.mMinLevel),
1052 mMaxLevel(other.mMaxLevel),
1060 template<
typename TreeT,
typename RootChildOnIterT>
1064 if (&other !=
this) {
1065 mLevel = other.mLevel;
1066 mMinLevel = other.mMinLevel;
1067 mMaxLevel = other.mMaxLevel;
1068 mDone = other.mDone;
1069 mTree = other.mTree;
1070 mIterList = other.mIterList;
1077 template<
typename TreeT,
typename RootChildOnIterT>
1081 mMaxLevel = int(ROOT_LEVEL - minDepth);
1082 if (
int(mLevel) > mMaxLevel) this->next();
1086 template<
typename TreeT,
typename RootChildOnIterT>
1091 mMinLevel = int(ROOT_LEVEL -
std::min(maxDepth, this->getLeafDepth()));
1092 if (
int(mLevel) < mMinLevel) this->next();
1096 template<
typename TreeT,
typename RootChildOnIterT>
1101 if (mDone)
return false;
1105 if (
int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1106 if (!mIterList.down(mLevel))
return false;
1110 while (!mIterList.test(mLevel)) {
1111 if (mLevel == ROOT_LEVEL) {
1117 mIterList.next(mLevel);
1120 if (!mIterList.down(mLevel))
return false;
1123 }
while (
int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1128 template<
typename TreeT,
typename RootChildOnIterT>
1132 if (mLevel != ROOT_LEVEL)
return mIterList.getCoord(mLevel + 1);
1134 this->getNode(root);
1135 return root ? root->getMinIndex() :
Coord::min();
1139 template<
typename TreeT,
typename RootChildOnIterT>
1143 if (mLevel == ROOT_LEVEL) {
1145 this->getNode(root);
1150 root->getIndexRange(bbox);
1153 bbox.
min() = mIterList.getCoord(mLevel + 1);
1154 bbox.
max() = bbox.
min().
offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1159 template<
typename TreeT,
typename RootChildOnIterT>
1163 std::ostringstream ostr;
1164 for (
int lvl =
int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1165 if (lvl == 0) ostr <<
"leaf";
1166 else if (lvl ==
int(ROOT_LEVEL)) ostr <<
"root";
1167 else ostr <<
"int" << (ROOT_LEVEL - lvl);
1168 ostr <<
" c" << mIterList.pos(lvl);
1169 if (lvl >
int(mLevel)) ostr <<
" / ";
1172 this->getBoundingBox(bbox);
1173 ostr <<
" " << bbox;
1182 template<
typename TreeT,
typename RootChildOnIterT>
1202 mIterList.
setIter(RootIterTraits::begin(tree.getRootNode()));
1205 for ( ; lvl > 0 && mIterList.
down(lvl); --lvl) {}
1207 if (lvl > 0) this->
next();
1216 if (&other !=
this) {
1217 mTree = other.mTree;
1218 mIterList = other.mIterList;
1232 operator bool()
const {
return this->
test(); }
1246 struct PrevItem {
typedef RootIterT IterT; };
1256 template<
typename TreeT,
typename RootChildOnIterT>
1262 if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1263 mIterList.down(LEAF_PARENT_LEVEL);
1267 Index lvl = LEAF_PARENT_LEVEL;
1268 while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1269 if (mIterList.test(lvl)) {
1270 mIterList.next(lvl);
1275 if (lvl == ROOT_LEVEL)
return false;
1277 if (mIterList.test(lvl)) mIterList.next(lvl);
1278 }
while (!mIterList.test(lvl));
1281 while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1283 mIterList.down(LEAF_PARENT_LEVEL);
1293 template<
typename IterT>
1299 mGrainSize(grainSize),
1302 mSize = this->size();
1306 mGrainSize(other.mGrainSize),
1307 mSize(other.mSize >> 1)
1317 bool empty()
const {
return mSize == 0 || !mIter.test(); }
1319 operator bool()
const {
return !this->
empty(); }
1326 void increment(
Index n = 1) {
for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1334 Index size()
const {
Index n = 0;
for (IterT it(mIter); it.test(); ++n, ++it) {}
return n; }
1356 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED