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>
319 void initLevel(
Index lvl, OtherIterListItemT& otherListItem)
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);
392 void setValueOn(
Index lvl,
bool on =
true)
const
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>
464 void initLevel(
Index lvl, OtherIterListItemT& otherListItem)
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);
512 void setValueOn(
Index lvl,
bool on =
true)
const
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>
582 void initLevel(
Index lvl, OtherIterListItemT& otherListItem)
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);
665 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); }
735 std::string summary()
const;
738 bool advance(
bool dontIncrement =
false);
741 struct PrevChildItem {
typedef ChildOnIterT IterT; };
742 struct PrevValueItem {
typedef ValueIterT IterT; };
744 IterListItem<PrevChildItem, InvTreeT, ROOT_LEVEL+1, 0> mChildIterList;
745 IterListItem<PrevValueItem, InvTreeT, ROOT_LEVEL+1, 0> mValueIterList;
747 int mMinLevel, mMaxLevel;
752 template<
typename TreeT,
typename ValueIterT>
755 mChildIterList(NULL),
756 mValueIterList(NULL),
758 mMinLevel(int(LEAF_LEVEL)),
759 mMaxLevel(int(ROOT_LEVEL)),
768 template<
typename TreeT,
typename ValueIterT>
771 mChildIterList(other.mChildIterList),
772 mValueIterList(other.mValueIterList),
773 mLevel(other.mLevel),
774 mMinLevel(other.mMinLevel),
775 mMaxLevel(other.mMaxLevel),
783 template<
typename TreeT,
typename ValueIterT>
787 if (&other !=
this) {
788 mChildIterList = other.mChildIterList;
789 mValueIterList = other.mValueIterList;
790 mLevel = other.mLevel;
791 mMinLevel = other.mMinLevel;
792 mMaxLevel = other.mMaxLevel;
794 mChildIterList.updateBackPointers();
795 mValueIterList.updateBackPointers();
801 template<
typename TreeT,
typename ValueIterT>
805 mMaxLevel = int(ROOT_LEVEL - minDepth);
806 if (
int(mLevel) > mMaxLevel) this->next();
810 template<
typename TreeT,
typename ValueIterT>
815 mMinLevel = int(ROOT_LEVEL -
std::min(maxDepth, this->getLeafDepth()));
816 if (
int(mLevel) < mMinLevel) this->next();
820 template<
typename TreeT,
typename ValueIterT>
825 if (!this->advance())
return false;
826 }
while (
int(mLevel) < mMinLevel ||
int(mLevel) > mMaxLevel);
831 template<
typename TreeT,
typename ValueIterT>
836 vPos = mValueIterList.pos(mLevel),
837 cPos = mChildIterList.pos(mLevel);
838 if (vPos == cPos && mChildIterList.test(mLevel)) {
840 mValueIterList.
next(mLevel);
841 vPos = mValueIterList.pos(mLevel);
844 if (dontIncrement)
return true;
845 if (mValueIterList.next(mLevel)) {
846 if (mValueIterList.pos(mLevel) == cPos && mChildIterList.test(mLevel)) {
848 mValueIterList.next(mLevel);
851 if (mValueIterList.pos(mLevel) < cPos)
return true;
855 if (!dontIncrement) mChildIterList.next(mLevel);
857 #ifdef DEBUG_TREE_VALUE_ITERATOR
858 std::cout <<
"\n" << this->summary() << std::flush;
862 while (mChildIterList.pos(mLevel) < mValueIterList.pos(mLevel)) {
863 #ifdef ENABLE_TREE_VALUE_DEPTH_BOUND_OPTIMIZATION
864 if (
int(mLevel) == mMinLevel) {
869 while (mChildIterList.test(mLevel)) mChildIterList.next(mLevel);
872 if (mChildIterList.down(mLevel)) {
874 mValueIterList.initLevel(mLevel, mChildIterList);
875 if (mValueIterList.pos(mLevel) == mChildIterList.pos(mLevel)
876 && mChildIterList.test(mLevel))
879 mValueIterList.next(mLevel);
882 #ifdef DEBUG_TREE_VALUE_ITERATOR
883 std::cout <<
"\n" << this->summary() << std::flush;
887 while (!mChildIterList.test(mLevel) && !mValueIterList.test(mLevel)) {
888 if (mLevel == ROOT_LEVEL)
return false;
890 mChildIterList.next(mLevel);
897 template<
typename TreeT,
typename ValueIterT>
905 bbox.
min() = mValueIterList.getCoord(mLevel);
906 bbox.
max() = bbox.
min().
offsetBy(mValueIterList.getChildDim(mLevel) - 1);
911 template<
typename TreeT,
typename ValueIterT>
915 std::ostringstream ostr;
916 for (
int lvl =
int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
917 if (lvl == 0) ostr <<
"leaf";
918 else if (lvl ==
int(ROOT_LEVEL)) ostr <<
"root";
919 else ostr <<
"int" << (ROOT_LEVEL - lvl);
920 ostr <<
" v" << mValueIterList.pos(lvl)
921 <<
" c" << mChildIterList.pos(lvl);
922 if (lvl >
int(mLevel)) ostr <<
" / ";
924 if (this->test() && mValueIterList.pos(mLevel) < mChildIterList.pos(mLevel)) {
926 ostr <<
" " << this->getCoord();
928 ostr <<
" " << this->getBoundingBox();
939 template<
typename _TreeT,
typename RootChildOnIterT>
970 bool test()
const {
return !mDone; }
971 operator bool()
const {
return this->
test(); }
1005 template<
typename NodeT>
1013 struct PrevItem {
typedef RootIterT IterT; };
1017 int mMinLevel, mMaxLevel;
1023 template<
typename TreeT,
typename RootChildOnIterT>
1028 mMinLevel(int(LEAF_LEVEL)),
1029 mMaxLevel(int(ROOT_LEVEL)),
1036 template<
typename TreeT,
typename RootChildOnIterT>
1041 mMinLevel(int(LEAF_LEVEL)),
1042 mMaxLevel(int(ROOT_LEVEL)),
1046 mIterList.
setIter(RootIterTraits::begin(tree.getRootNode()));
1050 template<
typename TreeT,
typename RootChildOnIterT>
1053 mIterList(other.mIterList),
1054 mLevel(other.mLevel),
1055 mMinLevel(other.mMinLevel),
1056 mMaxLevel(other.mMaxLevel),
1064 template<
typename TreeT,
typename RootChildOnIterT>
1068 if (&other !=
this) {
1069 mLevel = other.mLevel;
1070 mMinLevel = other.mMinLevel;
1071 mMaxLevel = other.mMaxLevel;
1072 mDone = other.mDone;
1073 mTree = other.mTree;
1074 mIterList = other.mIterList;
1081 template<
typename TreeT,
typename RootChildOnIterT>
1085 mMaxLevel = int(ROOT_LEVEL - minDepth);
1086 if (
int(mLevel) > mMaxLevel) this->next();
1090 template<
typename TreeT,
typename RootChildOnIterT>
1095 mMinLevel = int(ROOT_LEVEL -
std::min(maxDepth, this->getLeafDepth()));
1096 if (
int(mLevel) < mMinLevel) this->next();
1100 template<
typename TreeT,
typename RootChildOnIterT>
1105 if (mDone)
return false;
1109 if (
int(mLevel) > mMinLevel && mIterList.test(mLevel)) {
1110 if (!mIterList.down(mLevel))
return false;
1114 while (!mIterList.test(mLevel)) {
1115 if (mLevel == ROOT_LEVEL) {
1121 mIterList.next(mLevel);
1124 if (!mIterList.down(mLevel))
return false;
1127 }
while (
int(mLevel) < mMinLevel || int(mLevel) > mMaxLevel);
1132 template<
typename TreeT,
typename RootChildOnIterT>
1136 if (mLevel != ROOT_LEVEL)
return mIterList.getCoord(mLevel + 1);
1138 this->getNode(root);
1139 return root ? root->getMinIndex() :
Coord::min();
1143 template<
typename TreeT,
typename RootChildOnIterT>
1147 if (mLevel == ROOT_LEVEL) {
1149 this->getNode(root);
1154 root->getIndexRange(bbox);
1157 bbox.
min() = mIterList.getCoord(mLevel + 1);
1158 bbox.
max() = bbox.
min().
offsetBy(mIterList.getChildDim(mLevel + 1) - 1);
1163 template<
typename TreeT,
typename RootChildOnIterT>
1167 std::ostringstream ostr;
1168 for (
int lvl =
int(ROOT_LEVEL); lvl >= 0 && lvl >= int(mLevel); --lvl) {
1169 if (lvl == 0) ostr <<
"leaf";
1170 else if (lvl ==
int(ROOT_LEVEL)) ostr <<
"root";
1171 else ostr <<
"int" << (ROOT_LEVEL - lvl);
1172 ostr <<
" c" << mIterList.pos(lvl);
1173 if (lvl >
int(mLevel)) ostr <<
" / ";
1176 this->getBoundingBox(bbox);
1177 ostr <<
" " << bbox;
1186 template<
typename TreeT,
typename RootChildOnIterT>
1206 mIterList.
setIter(RootIterTraits::begin(tree.getRootNode()));
1209 for ( ; lvl > 0 && mIterList.
down(lvl); --lvl) {}
1211 if (lvl > 0) this->
next();
1220 if (&other !=
this) {
1221 mTree = other.mTree;
1222 mIterList = other.mIterList;
1236 operator bool()
const {
return this->
test(); }
1250 struct PrevItem {
typedef RootIterT IterT; };
1260 template<
typename TreeT,
typename RootChildOnIterT>
1266 if (mIterList.test(LEAF_PARENT_LEVEL) && mIterList.next(LEAF_PARENT_LEVEL)) {
1267 mIterList.down(LEAF_PARENT_LEVEL);
1271 Index lvl = LEAF_PARENT_LEVEL;
1272 while (!mIterList.test(LEAF_PARENT_LEVEL)) {
1273 if (mIterList.test(lvl)) {
1274 mIterList.next(lvl);
1279 if (lvl == ROOT_LEVEL)
return false;
1281 if (mIterList.test(lvl)) mIterList.next(lvl);
1282 }
while (!mIterList.test(lvl));
1285 while (lvl > LEAF_PARENT_LEVEL && mIterList.down(lvl)) --lvl;
1287 mIterList.down(LEAF_PARENT_LEVEL);
1297 template<
typename IterT>
1303 mGrainSize(grainSize),
1306 mSize = this->size();
1310 mGrainSize(other.mGrainSize),
1311 mSize(other.mSize >> 1)
1321 bool empty()
const {
return mSize == 0 || !mIter.test(); }
1323 operator bool()
const {
return !this->
empty(); }
1330 void increment(
Index n = 1) {
for ( ; n > 0 && mSize > 0; --n, --mSize, ++mIter) {} }
1338 Index size()
const {
Index n = 0;
for (IterT it(mIter); it.test(); ++n, ++it) {}
return n; }
1360 #endif // OPENVDB_TREE_TREEITERATOR_HAS_BEEN_INCLUDED