35 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
36 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
41 #include <boost/type_traits/remove_const.hpp>
42 #include <openvdb/Exceptions.h>
43 #include <openvdb/Types.h>
44 #include <openvdb/io/Compression.h>
45 #include <openvdb/math/Math.h>
46 #include <openvdb/math/BBox.h>
47 #include <openvdb/util/NodeMasks.h>
48 #include <openvdb/version.h>
57 template<
typename ChildType>
65 static const Index LEVEL = 1 + ChildType::LEVEL;
69 template<
typename OtherValueType>
94 template<
typename OtherChildType>
96 const ValueType& background,
const ValueType& foreground,
114 template<
typename OtherChildType>
124 Tile(): value(
zeroVal<ValueType>()), active(false) {}
125 Tile(
const ValueType& v,
bool b): value(v), active(b) {}
135 NodeStruct(): child(NULL) {}
136 NodeStruct(ChildType& c): child(&c) {}
137 NodeStruct(
const Tile& t): child(NULL), tile(t) {}
140 bool isChild()
const {
return child != NULL; }
141 bool isTile()
const {
return child == NULL; }
142 bool isTileOff()
const {
return isTile() && !tile.active; }
143 bool isTileOn()
const {
return isTile() && tile.active; }
145 void set(ChildType& c) {
delete child; child = &c; }
146 void set(
const Tile& t) {
delete child; child = NULL; tile = t; }
147 ChildType& steal(
const Tile& t) { ChildType* c = child; child = NULL; tile = t;
return *c; }
150 typedef std::map<Coord, NodeStruct> MapType;
151 typedef typename MapType::iterator MapIter;
152 typedef typename MapType::const_iterator MapCIter;
154 typedef std::set<Coord> CoordSet;
155 typedef typename CoordSet::iterator CoordSetIter;
156 typedef typename CoordSet::const_iterator CoordSetCIter;
158 static void setTile(
const MapIter& i,
const Tile& t) { i->second.set(t); }
159 static void setChild(
const MapIter& i, ChildType& c) { i->second.set(c); }
160 static Tile& getTile(
const MapIter& i) {
return i->second.tile; }
161 static const Tile& getTile(
const MapCIter& i) {
return i->second.tile; }
162 static ChildType& getChild(
const MapIter& i) {
return *(i->second.child); }
163 static const ChildType& getChild(
const MapCIter& i) {
return *(i->second.child); }
164 static ChildType& stealChild(
const MapIter& i,
const Tile& t) {
return i->second.steal(t);}
165 static const ChildType& stealChild(
const MapCIter& i,
const Tile& t) {
return i->second.steal(t);}
167 static bool isChild(
const MapCIter& i) {
return i->second.isChild(); }
168 static bool isChild(
const MapIter& i) {
return i->second.isChild(); }
169 static bool isTile(
const MapCIter& i) {
return i->second.isTile(); }
170 static bool isTile(
const MapIter& i) {
return i->second.isTile(); }
171 static bool isTileOff(
const MapCIter& i) {
return i->second.isTileOff(); }
172 static bool isTileOff(
const MapIter& i) {
return i->second.isTileOff(); }
173 static bool isTileOn(
const MapCIter& i) {
return i->second.isTileOn(); }
174 static bool isTileOn(
const MapIter& i) {
return i->second.isTileOn(); }
177 static inline bool test(
const MapIter&) {
return true; }
178 static inline bool test(
const MapCIter&) {
return true; }
181 static inline bool test(
const MapIter& i) {
return isTileOn(i); }
182 static inline bool test(
const MapCIter& i) {
return isTileOn(i); }
184 struct ValueOffPred {
185 static inline bool test(
const MapIter& i) {
return isTileOff(i); }
186 static inline bool test(
const MapCIter& i) {
return isTileOff(i); }
188 struct ValueAllPred {
189 static inline bool test(
const MapIter& i) {
return isTile(i); }
190 static inline bool test(
const MapCIter& i) {
return isTile(i); }
193 static inline bool test(
const MapIter& i) {
return isChild(i); }
194 static inline bool test(
const MapCIter& i) {
return isChild(i); }
196 struct ChildOffPred {
197 static inline bool test(
const MapIter& i) {
return isTile(i); }
198 static inline bool test(
const MapCIter& i) {
return isTile(i); }
201 template<
typename _RootNodeT,
typename _MapIterT,
typename FilterPredT>
205 typedef _RootNodeT RootNodeT;
206 typedef _MapIterT MapIterT;
210 return (mParentNode == other.mParentNode) && (mIter == other.mIter);
212 bool operator!=(
const BaseIter& other)
const {
return !(*
this == other); }
214 RootNodeT* getParentNode()
const {
return mParentNode; }
216 RootNodeT& parent()
const
218 if (!mParentNode)
OPENVDB_THROW(ValueError,
"iterator references a null parent node");
222 bool test()
const { assert(mParentNode);
return mIter != mParentNode->mTable.end(); }
223 operator bool()
const {
return this->test(); }
225 void increment() { ++mIter; this->skip(); }
226 bool next() { this->increment();
return this->test(); }
227 void increment(
Index n) {
for (
int i = 0; i < n && this->next(); ++i) {} }
233 return !mParentNode ? 0U :
Index(std::distance(mParentNode->mTable.begin(), mIter));
236 bool isValueOn()
const {
return RootNodeT::isTileOn(mIter); }
237 bool isValueOff()
const {
return RootNodeT::isTileOff(mIter); }
238 void setValueOn(
bool on =
true)
const { mIter->second.tile.active = on; }
239 void setValueOff()
const { mIter->second.tile.active =
false; }
242 Coord getCoord()
const {
return mIter->first; }
244 void getCoord(
Coord& xyz)
const { xyz = this->getCoord(); }
247 BaseIter(): mParentNode(NULL) {}
248 BaseIter(RootNodeT& parent,
const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
250 void skip() {
while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
252 RootNodeT* mParentNode;
256 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ChildNodeT>
257 class ChildIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
260 typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
261 typedef RootNodeT NodeType;
262 typedef NodeType ValueType;
263 typedef ChildNodeT ChildNodeType;
264 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
265 typedef typename boost::remove_const<ValueType>::type NonConstValueType;
266 typedef typename boost::remove_const<ChildNodeType>::type NonConstChildNodeType;
270 ChildIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
272 ChildIter& operator++() { BaseT::increment();
return *
this; }
274 ChildNodeT& getValue()
const {
return getChild(mIter); }
275 ChildNodeT&
operator*()
const {
return this->getValue(); }
276 ChildNodeT* operator->()
const {
return &this->getValue(); }
279 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ValueT>
280 class ValueIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
283 typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
284 typedef RootNodeT NodeType;
285 typedef ValueT ValueType;
286 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
287 typedef typename boost::remove_const<ValueT>::type NonConstValueType;
291 ValueIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
293 ValueIter& operator++() { BaseT::increment();
return *
this; }
295 ValueT& getValue()
const {
return getTile(mIter).value; }
296 ValueT&
operator*()
const {
return this->getValue(); }
297 ValueT* operator->()
const {
return &(this->getValue()); }
299 void setValue(
const ValueT& v)
const { assert(isTile(mIter)); getTile(mIter).value = v; }
302 template<
typename RootNodeT,
typename MapIterT,
typename ChildNodeT,
typename ValueT>
303 class DenseIter:
public BaseIter<RootNodeT, MapIterT, NullPred>
306 typedef BaseIter<RootNodeT, MapIterT, NullPred> BaseT;
307 typedef RootNodeT NodeType;
308 typedef ValueT ValueType;
309 typedef ChildNodeT ChildNodeType;
310 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
311 typedef typename boost::remove_const<ValueT>::type NonConstValueType;
312 typedef typename boost::remove_const<ChildNodeT>::type NonConstChildNodeType;
316 DenseIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) {}
318 DenseIter& operator++() { BaseT::increment();
return *
this; }
320 bool isChildNode()
const {
return isChild(mIter); }
322 ChildNodeT* probeChild(NonConstValueType& value)
const
324 if (isChild(mIter))
return &getChild(mIter);
325 value = getTile(mIter).value;
328 bool probeChild(ChildNodeT*& child, NonConstValueType& value)
const
330 child = this->probeChild(value);
331 return child != NULL;
333 bool probeValue(NonConstValueType& value)
const {
return !this->probeChild(value); }
335 void setChild(ChildNodeT& c)
const { RootNodeT::setChild(mIter, c); }
336 void setChild(ChildNodeT* c)
const { assert(c != NULL); RootNodeT::setChild(mIter, *c); }
337 void setValue(
const ValueT& v)
const
339 if (isTile(mIter)) getTile(mIter).value = v;
343 else stealChild(mIter, Tile(v,
true));
348 typedef ChildIter<RootNode, MapIter, ChildOnPred, ChildType>
ChildOnIter;
349 typedef ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>
ChildOnCIter;
350 typedef ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>
ChildOffIter;
351 typedef ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>
ChildOffCIter;
352 typedef DenseIter<RootNode, MapIter, ChildType, ValueType>
ChildAllIter;
353 typedef DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>
ChildAllCIter;
355 typedef ValueIter<RootNode, MapIter, ValueOnPred, ValueType>
ValueOnIter;
356 typedef ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>
ValueOnCIter;
357 typedef ValueIter<RootNode, MapIter, ValueOffPred, ValueType>
ValueOffIter;
358 typedef ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>
ValueOffCIter;
359 typedef ValueIter<RootNode, MapIter, ValueAllPred, ValueType>
ValueAllIter;
360 typedef ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>
ValueAllCIter;
388 void evalActiveVoxelBoundingBox(
CoordBBox& bbox)
const;
396 void setBackground(
const ValueType& value);
403 bool isBackgroundTile(
const Tile&)
const;
405 bool isBackgroundTile(
const MapIter&)
const;
407 bool isBackgroundTile(
const MapCIter&)
const;
411 size_t numBackgroundTiles()
const;
414 size_t eraseBackgroundTiles();
415 void clear() { this->clearTable(); }
418 bool empty()
const {
return mTable.size() == numBackgroundTiles(); }
423 bool expand(
const Coord& xyz);
426 static void getNodeLog2Dims(std::vector<Index>& dims);
432 Index getWidth()
const {
return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
433 Index getHeight()
const {
return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
434 Index getDepth()
const {
return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
437 Coord getMinIndex()
const;
439 Coord getMaxIndex()
const;
441 void getIndexRange(
CoordBBox& bbox)
const;
445 template<
typename OtherChildType>
449 template<
typename OtherChildType>
456 Index64 onLeafVoxelCount()
const;
457 Index64 offLeafVoxelCount()
const;
459 bool isValueOn(
const Coord& xyz)
const;
461 bool hasActiveTiles()
const;
463 const ValueType& getValue(
const Coord& xyz)
const;
464 bool probeValue(
const Coord& xyz, ValueType& value)
const;
469 int getValueDepth(
const Coord& xyz)
const;
472 void setActiveState(
const Coord& xyz,
bool on);
475 void setValueOff(
const Coord& xyz);
477 void setValueOff(
const Coord& xyz,
const ValueType& value);
479 void setValueOn(
const Coord& xyz,
const ValueType& value);
480 void setValueOnly(
const Coord& xyz,
const ValueType& value);
481 void setValueOnMin(
const Coord& xyz,
const ValueType& value);
482 void setValueOnMax(
const Coord& xyz,
const ValueType& value);
483 void setValueOnSum(
const Coord& xyz,
const ValueType& value);
491 void fill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
499 template<
typename DenseT>
505 bool writeTopology(std::ostream&,
bool toHalf =
false)
const;
506 bool readTopology(std::istream&,
bool fromHalf =
false);
508 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
509 void readBuffers(std::istream&,
bool fromHalf =
false);
515 template<
typename AccessorT>
516 const ValueType& getValueAndCache(
const Coord& xyz, AccessorT&)
const;
521 template<
typename AccessorT>
522 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
528 template<
typename AccessorT>
529 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
535 template<
typename AccessorT>
536 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
543 template<
typename AccessorT>
544 void setValueOnSumAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
550 template<
typename AccessorT>
551 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
557 template<
typename AccessorT>
558 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
564 template<
typename AccessorT>
565 bool probeValueAndCache(
const Coord& xyz, ValueType& value, AccessorT&)
const;
572 template<
typename AccessorT>
573 int getValueDepthAndCache(
const Coord& xyz, AccessorT&)
const;
581 template<
typename PruneOp>
void pruneOp(PruneOp&);
586 void prune(
const ValueType&
tolerance = zeroVal<ValueType>());
590 void pruneInactive(
const ValueType&);
594 void pruneInactive();
596 void pruneTiles(
const ValueType&);
600 void addLeaf(LeafNodeType* leaf);
604 template<
typename AccessorT>
605 void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
615 template<
typename NodeT>
616 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool state);
620 void addTile(
Index level,
const Coord& xyz,
const ValueType& value,
bool state);
624 template<
typename AccessorT>
625 void addTileAndCache(
Index level,
const Coord& xyz,
const ValueType& value,
626 bool state, AccessorT&);
634 LeafNodeType* touchLeaf(
const Coord& xyz);
638 template<
typename AccessorT>
639 LeafNodeType* touchLeafAndCache(
const Coord& xyz, AccessorT& acc);
643 template <
typename NodeT>
644 NodeT* probeNode(
const Coord& xyz);
645 template <
typename NodeT>
646 const NodeT* probeConstNode(
const Coord& xyz)
const;
651 template<
typename NodeT,
typename AccessorT>
652 NodeT* probeNodeAndCache(
const Coord& xyz, AccessorT& acc);
656 template<
typename NodeT,
typename AccessorT>
657 const NodeT* probeConstNodeAndCache(
const Coord& xyz, AccessorT& acc)
const;
667 return this->
template probeConstNode<LeafNodeType>(xyz);
674 template<
typename AccessorT>
677 return this->
template probeNodeAndCache<LeafNodeType>(xyz, acc);
682 template<
typename AccessorT>
685 return this->
template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
688 template<
typename AccessorT>
691 return this->probeConstLeafAndCache(xyz, acc);
695 template<
typename NodeT>
696 static bool hasNodeType();
703 void signedFloodFill();
711 void signedFloodFill(
const ValueType& outside,
const ValueType& inside);
721 void voxelizeActiveTiles();
736 template<
typename OtherChildType>
739 template<
typename CombineOp>
742 template<
typename CombineOp>
744 CombineOp& op,
bool prune =
false);
751 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
753 template<
typename VisitorOp>
void visit(VisitorOp&);
754 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
756 template<
typename OtherRootNodeType,
typename VisitorOp>
757 void visit2(OtherRootNodeType& other, VisitorOp&);
758 template<
typename OtherRootNodeType,
typename VisitorOp>
759 void visit2(OtherRootNodeType& other, VisitorOp&)
const;
768 inline void clearTable();
770 void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
772 void resetTable(
const MapType&)
const {}
775 Index getChildCount()
const;
776 Index getTileCount()
const;
777 Index getActiveTileCount()
const;
778 Index getInactiveTileCount()
const;
781 static Coord coordToKey(
const Coord& xyz) {
return xyz & ~(ChildType::DIM - 1); }
784 void insertKeys(CoordSet&)
const;
787 bool hasKey(
const Coord& key)
const {
return mTable.find(key) != mTable.end(); }
789 MapIter findKey(
const Coord& key) {
return mTable.find(key); }
792 MapCIter findKey(
const Coord& key)
const {
return mTable.find(key); }
795 MapIter findCoord(
const Coord& xyz) {
return mTable.find(coordToKey(xyz)); }
798 MapCIter findCoord(
const Coord& xyz)
const {
return mTable.find(coordToKey(xyz)); }
800 MapIter findOrAddCoord(
const Coord& xyz);
806 template<
typename OtherChildType>
807 static void enforceSameConfiguration(
const RootNode<OtherChildType>& other);
809 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
810 static inline void doVisit(RootNodeT&, VisitorOp&);
812 template<
typename RootNodeT,
typename OtherRootNodeT,
typename VisitorOp,
813 typename ChildAllIterT,
typename OtherChildAllIterT>
814 static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
818 ValueType mBackground;
825 template<
typename ChildT>
833 template<
typename ChildT>
841 template<
typename ChildT>
842 template<
typename OtherChildType>
851 enforceSameConfiguration(other);
853 const Tile bgTile(backgd,
false), fgTile(foregd,
true);
856 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
857 mTable[i->first] = OtherRootT::isTile(i)
858 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
859 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd, foregd,
TopologyCopy())));
864 template<
typename ChildT>
865 template<
typename OtherChildType>
874 enforceSameConfiguration(other);
876 const Tile bgTile(backgd,
false), fgTile(backgd,
true);
878 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
879 mTable[i->first] = OtherRootT::isTile(i)
880 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
881 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd,
TopologyCopy())));
886 template<
typename ChildT>
890 mBackground = other.mBackground;
895 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
897 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(
new ChildT(getChild(i))));
906 template<
typename ChildT>
914 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
915 ChildT *child = iter->second.child;
917 child->resetBackground(mBackground, background);
919 Tile& tile = getTile(iter);
920 if (tile.active)
continue;
922 tile.value = background;
928 mBackground = background;
932 template<
typename ChildT>
939 template<
typename ChildT>
946 template<
typename ChildT>
954 template<
typename ChildT>
959 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
960 if (this->isBackgroundTile(i)) ++count;
966 template<
typename ChildT>
970 std::set<Coord> keysToErase;
971 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
972 if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
974 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
977 return keysToErase.size();
984 template<
typename ChildT>
988 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
989 keys.insert(i->first);
994 template<
typename ChildT>
995 inline typename RootNode<ChildT>::MapIter
996 RootNode<ChildT>::findOrAddCoord(
const Coord& xyz)
998 const Coord key = coordToKey(xyz);
999 std::pair<MapIter, bool> result = mTable.insert(
1000 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1001 return result.first;
1005 template<
typename ChildT>
1009 const Coord key = coordToKey(xyz);
1010 std::pair<MapIter, bool> result = mTable.insert(
1011 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1012 return result.second;
1019 template<
typename ChildT>
1024 ChildT::getNodeLog2Dims(dims);
1028 template<
typename ChildT>
1032 return mTable.empty() ?
Coord(0) : mTable.begin()->first;
1035 template<
typename ChildT>
1039 return mTable.empty() ?
Coord(0) : mTable.rbegin()->first +
Coord(ChildT::DIM - 1);
1043 template<
typename ChildT>
1047 bbox.
min() = this->getMinIndex();
1048 bbox.
max() = this->getMaxIndex();
1055 template<
typename ChildT>
1056 template<
typename OtherChildType>
1061 typedef typename OtherRootT::MapType OtherMapT;
1062 typedef typename OtherRootT::MapIter OtherIterT;
1063 typedef typename OtherRootT::MapCIter OtherCIterT;
1065 if (!hasSameConfiguration(other))
return false;
1068 OtherMapT copyOfOtherTable = other.mTable;
1071 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1072 if (this->isBackgroundTile(thisIter))
continue;
1075 OtherCIterT otherIter = other.findKey(thisIter->first);
1076 if (otherIter == other.mTable.end())
return false;
1079 if (isChild(thisIter)) {
1080 if (OtherRootT::isTile(otherIter))
return false;
1082 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter)))
return false;
1084 if (OtherRootT::isChild(otherIter))
return false;
1085 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active)
return false;
1092 copyOfOtherTable.erase(otherIter->first);
1095 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1102 template<
typename ChildT>
1103 template<
typename OtherChildType>
1107 std::vector<Index> thisDims, otherDims;
1110 return (thisDims == otherDims);
1114 template<
typename ChildT>
1115 template<
typename OtherChildType>
1119 std::vector<Index> thisDims, otherDims;
1122 if (thisDims != otherDims) {
1123 std::ostringstream ostr;
1124 ostr <<
"grids have incompatible configurations (" << thisDims[0];
1125 for (
size_t i = 1, N = thisDims.size(); i < N; ++i) ostr <<
" x " << thisDims[i];
1126 ostr <<
" vs. " << otherDims[0];
1127 for (
size_t i = 1, N = otherDims.size(); i < N; ++i) ostr <<
" x " << otherDims[i];
1137 template<
typename ChildT>
1142 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1143 if (
const ChildT *child = iter->second.child) {
1144 sum += child->memUsage();
1150 template<
typename ChildT>
1154 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1155 if (
const ChildT *child = iter->second.child) {
1156 child->evalActiveVoxelBoundingBox(bbox);
1157 }
else if (isTileOn(iter)) {
1158 bbox.
expand(iter->first, ChildT::DIM);
1164 template<
typename ChildT>
1168 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1169 delete i->second.child;
1175 template<
typename ChildT>
1177 RootNode<ChildT>::getChildCount()
const {
1179 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1180 if (isChild(i)) ++sum;
1186 template<
typename ChildT>
1188 RootNode<ChildT>::getTileCount()
const
1191 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1192 if (isTile(i)) ++sum;
1198 template<
typename ChildT>
1200 RootNode<ChildT>::getActiveTileCount()
const
1203 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1204 if (isTileOn(i)) ++sum;
1210 template<
typename ChildT>
1212 RootNode<ChildT>::getInactiveTileCount()
const
1215 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1216 if (isTileOff(i)) ++sum;
1222 template<
typename ChildT>
1227 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1228 if (isChild(i)) sum += getChild(i).leafCount();
1234 template<
typename ChildT>
1239 if (ChildT::LEVEL != 0) {
1240 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1241 if (isChild(i)) sum += getChild(i).nonLeafCount();
1248 template<
typename ChildT>
1253 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1255 sum += getChild(i).onVoxelCount();
1256 }
else if (isTileOn(i)) {
1257 sum += ChildT::NUM_VOXELS;
1264 template<
typename ChildT>
1269 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1271 sum += getChild(i).offVoxelCount();
1272 }
else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1273 sum += ChildT::NUM_VOXELS;
1280 template<
typename ChildT>
1285 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1286 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1292 template<
typename ChildT>
1297 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1298 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1307 template<
typename ChildT>
1311 MapCIter iter = this->findCoord(xyz);
1312 if (iter == mTable.end() || isTileOff(iter))
return false;
1313 return isTileOn(iter) ?
true : getChild(iter).isValueOn(xyz);
1316 template<
typename ChildT>
1320 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1321 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active)
return true;
1326 template<
typename ChildT>
1327 template<
typename AccessorT>
1331 MapCIter iter = this->findCoord(xyz);
1332 if (iter == mTable.end() || isTileOff(iter))
return false;
1333 if (isTileOn(iter))
return true;
1334 acc.insert(xyz, &getChild(iter));
1335 return getChild(iter).isValueOnAndCache(xyz, acc);
1339 template<
typename ChildT>
1340 inline const typename ChildT::ValueType&
1343 MapCIter iter = this->findCoord(xyz);
1344 return iter == mTable.end() ? mBackground
1345 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1348 template<
typename ChildT>
1349 template<
typename AccessorT>
1350 inline const typename ChildT::ValueType&
1353 MapCIter iter = this->findCoord(xyz);
1354 if (iter == mTable.end())
return mBackground;
1355 if (isChild(iter)) {
1356 acc.insert(xyz, &getChild(iter));
1357 return getChild(iter).getValueAndCache(xyz, acc);
1359 return getTile(iter).value;
1363 template<
typename ChildT>
1367 MapCIter iter = this->findCoord(xyz);
1368 return iter == mTable.end() ? -1
1369 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1372 template<
typename ChildT>
1373 template<
typename AccessorT>
1377 MapCIter iter = this->findCoord(xyz);
1378 if (iter == mTable.end())
return -1;
1379 if (isTile(iter))
return 0;
1380 acc.insert(xyz, &getChild(iter));
1381 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1385 template<
typename ChildT>
1389 MapIter iter = this->findCoord(xyz);
1390 if (iter != mTable.end() && !isTileOff(iter)) {
1391 if (isTileOn(iter)) {
1392 setChild(iter, *
new ChildT(xyz, getTile(iter).value,
true));
1394 getChild(iter).setValueOff(xyz);
1399 template<
typename ChildT>
1403 ChildT* child = NULL;
1404 MapIter iter = this->findCoord(xyz);
1405 if (iter == mTable.end()) {
1407 child =
new ChildT(xyz, mBackground);
1408 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1412 }
else if (isChild(iter)) {
1413 child = &getChild(iter);
1414 }
else if (on != getTile(iter).active) {
1415 child =
new ChildT(xyz, getTile(iter).value, !on);
1416 setChild(iter, *child);
1418 if (child) child->setActiveState(xyz, on);
1421 template<
typename ChildT>
1422 template<
typename AccessorT>
1426 ChildT* child = NULL;
1427 MapIter iter = this->findCoord(xyz);
1428 if (iter == mTable.end()) {
1430 child =
new ChildT(xyz, mBackground);
1431 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1435 }
else if (isChild(iter)) {
1436 child = &getChild(iter);
1437 }
else if (on != getTile(iter).active) {
1438 child =
new ChildT(xyz, getTile(iter).value, !on);
1439 setChild(iter, *child);
1442 acc.insert(xyz, child);
1443 child->setActiveStateAndCache(xyz, on, acc);
1448 template<
typename ChildT>
1452 ChildT* child = NULL;
1453 MapIter iter = this->findCoord(xyz);
1454 if (iter == mTable.end()) {
1456 child =
new ChildT(xyz, mBackground);
1457 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1459 }
else if (isChild(iter)) {
1460 child = &getChild(iter);
1462 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1463 setChild(iter, *child);
1465 if (child) child->setValueOff(xyz, value);
1468 template<
typename ChildT>
1469 template<
typename AccessorT>
1473 ChildT* child = NULL;
1474 MapIter iter = this->findCoord(xyz);
1475 if (iter == mTable.end()) {
1477 child =
new ChildT(xyz, mBackground);
1478 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1480 }
else if (isChild(iter)) {
1481 child = &getChild(iter);
1483 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1484 setChild(iter, *child);
1487 acc.insert(xyz, child);
1488 child->setValueOffAndCache(xyz, value, acc);
1493 template<
typename ChildT>
1497 ChildT* child = NULL;
1498 MapIter iter = this->findCoord(xyz);
1499 if (iter == mTable.end()) {
1500 child =
new ChildT(xyz, mBackground);
1501 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1502 }
else if (isChild(iter)) {
1503 child = &getChild(iter);
1505 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1506 setChild(iter, *child);
1508 if (child) child->setValueOn(xyz, value);
1511 template<
typename ChildT>
1512 template<
typename AccessorT>
1516 ChildT* child = NULL;
1517 MapIter iter = this->findCoord(xyz);
1518 if (iter == mTable.end()) {
1519 child =
new ChildT(xyz, mBackground);
1520 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1521 }
else if (isChild(iter)) {
1522 child = &getChild(iter);
1524 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1525 setChild(iter, *child);
1528 acc.insert(xyz, child);
1529 child->setValueAndCache(xyz, value, acc);
1534 template<
typename ChildT>
1538 ChildT* child = NULL;
1539 MapIter iter = this->findCoord(xyz);
1540 if (iter == mTable.end()) {
1541 child =
new ChildT(xyz, mBackground);
1542 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1543 }
else if (isChild(iter)) {
1544 child = &getChild(iter);
1546 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1547 setChild(iter, *child);
1549 if (child) child->setValueOnly(xyz, value);
1552 template<
typename ChildT>
1553 template<
typename AccessorT>
1557 ChildT* child = NULL;
1558 MapIter iter = this->findCoord(xyz);
1559 if (iter == mTable.end()) {
1560 child =
new ChildT(xyz, mBackground);
1561 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1562 }
else if (isChild(iter)) {
1563 child = &getChild(iter);
1565 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1566 setChild(iter, *child);
1569 acc.insert(xyz, child);
1570 child->setValueOnlyAndCache(xyz, value, acc);
1575 template<
typename ChildT>
1579 ChildT* child = NULL;
1580 MapIter iter = this->findCoord(xyz);
1581 if (iter == mTable.end()) {
1582 child =
new ChildT(xyz, mBackground);
1583 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1584 }
else if (isChild(iter)) {
1585 child = &getChild(iter);
1586 }
else if (isTileOff(iter) || getTile(iter).value > value) {
1587 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1588 setChild(iter, *child);
1590 if (child) child->setValueOnMin(xyz, value);
1594 template<
typename ChildT>
1598 ChildT* child = NULL;
1599 MapIter iter = this->findCoord(xyz);
1600 if (iter == mTable.end()) {
1601 child =
new ChildT(xyz, mBackground);
1602 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1603 }
else if (isChild(iter)) {
1604 child = &getChild(iter);
1605 }
else if (isTileOff(iter) || getTile(iter).value < value) {
1606 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1607 setChild(iter, *child);
1609 if (child) child->setValueOnMax(xyz, value);
1613 template<
typename ChildT>
1617 ChildT* child = NULL;
1618 MapIter iter = this->findCoord(xyz);
1619 if (iter == mTable.end()) {
1620 child =
new ChildT(xyz, mBackground);
1621 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1622 }
else if (isChild(iter)) {
1623 child = &getChild(iter);
1625 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1626 setChild(iter, *child);
1628 if (child) child->setValueOnSum(xyz, addend);
1631 template<
typename ChildT>
1632 template<
typename AccessorT>
1635 const ValueType& addend, AccessorT& acc)
1637 ChildT* child = NULL;
1638 MapIter iter = this->findCoord(xyz);
1639 if (iter == mTable.end()) {
1640 child =
new ChildT(xyz, mBackground);
1641 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1642 }
else if (isChild(iter)) {
1643 child = &getChild(iter);
1645 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1646 setChild(iter, *child);
1649 acc.insert(xyz, child);
1650 child->setValueOnSumAndCache(xyz, addend, acc);
1655 template<
typename ChildT>
1659 MapCIter iter = this->findCoord(xyz);
1660 if (iter == mTable.end()) {
1661 value = mBackground;
1663 }
else if (isChild(iter)) {
1664 return getChild(iter).probeValue(xyz, value);
1666 value = getTile(iter).value;
1667 return isTileOn(iter);
1670 template<
typename ChildT>
1671 template<
typename AccessorT>
1675 MapCIter iter = this->findCoord(xyz);
1676 if (iter == mTable.end()) {
1677 value = mBackground;
1679 }
else if (isChild(iter)) {
1680 acc.insert(xyz, &getChild(iter));
1681 return getChild(iter).probeValueAndCache(xyz, value, acc);
1683 value = getTile(iter).value;
1684 return isTileOn(iter);
1691 template<
typename ChildT>
1695 if (bbox.
empty())
return;
1698 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
1700 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
1702 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
1706 Coord tileMin = coordToKey(xyz);
1707 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
1713 ChildT* child = NULL;
1714 MapIter iter = this->findKey(tileMin);
1715 if (iter == mTable.end()) {
1718 child =
new ChildT(xyz, mBackground);
1719 mTable[tileMin] = NodeStruct(*child);
1720 }
else if (isTile(iter)) {
1723 const Tile& tile = getTile(iter);
1724 child =
new ChildT(xyz, tile.value, tile.active);
1725 mTable[tileMin] = NodeStruct(*child);
1726 }
else if (isChild(iter)) {
1727 child = &getChild(iter);
1738 MapIter iter = this->findOrAddCoord(tileMin);
1739 setTile(iter, Tile(value, active));
1746 template<
typename ChildT>
1747 template<
typename DenseT>
1751 const size_t xStride = dense.xStride(), yStride = dense.yStride();
1752 const Coord&
min = dense.bbox().min();
1754 for (
Coord xyz = bbox.
min(); xyz[0] <= bbox.
max()[0]; xyz[0] = nodeBBox.
max()[0] + 1) {
1755 for (xyz[1] = bbox.
min()[1]; xyz[1] <= bbox.
max()[1]; xyz[1] = nodeBBox.
max()[1] + 1) {
1756 for (xyz[2] = bbox.
min()[2]; xyz[2] <= bbox.
max()[2]; xyz[2] = nodeBBox.
max()[2] + 1) {
1764 MapCIter iter = this->findKey(nodeBBox.
min());
1765 if (iter != mTable.end() && isChild(iter)) {
1766 getChild(iter).copyToDense(sub, dense);
1768 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
1771 for (
Int32 x=sub.
min()[0], ex=sub.
max()[0]+1; x<ex; ++x) {
1773 for (
Int32 y=sub.
min()[1], ey=sub.
max()[1]+1; y<ey; ++y) {
1775 for (
Int32 z=sub.
min()[2], ez=sub.
max()[2]+1; z<ez; ++z) *a2++ = value;
1787 template<
typename ChildT>
1792 os.write(reinterpret_cast<const char*>(&mBackground),
sizeof(
ValueType));
1795 os.write(reinterpret_cast<const char*>(&truncatedVal),
sizeof(
ValueType));
1799 const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
1800 os.write(reinterpret_cast<const char*>(&numTiles),
sizeof(
Index));
1801 os.write(reinterpret_cast<const char*>(&numChildren),
sizeof(
Index));
1803 if (numTiles == 0 && numChildren == 0)
return false;
1806 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1807 if (isChild(i))
continue;
1808 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
1809 os.write(reinterpret_cast<const char*>(&getTile(i).value),
sizeof(
ValueType));
1810 os.write(reinterpret_cast<const char*>(&getTile(i).active),
sizeof(
bool));
1813 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1814 if (isTile(i))
continue;
1815 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
1816 getChild(i).writeTopology(os, toHalf);
1823 template<
typename ChildT>
1835 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
1837 is.read(reinterpret_cast<char*>(&inside),
sizeof(
ValueType));
1842 Coord rangeMin, rangeMax;
1844 is.read(reinterpret_cast<char*>(rangeMax.
asPointer()), 3 *
sizeof(
Int32));
1847 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
1849 for (
int i = 0; i < 3; ++i) {
1850 offset[i] = rangeMin[i] >> ChildT::TOTAL;
1851 rangeMin[i] = offset[i] << ChildT::TOTAL;
1853 tableSize += log2Dim[i];
1854 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
1856 log2Dim[3] = log2Dim[1] + log2Dim[2];
1857 tableSize = 1U << tableSize;
1865 for (
Index i = 0; i < tableSize; ++i) {
1869 origin[0] = (n >> log2Dim[3]) + offset[0];
1870 n &= (1U << log2Dim[3]) - 1;
1871 origin[1] = (n >> log2Dim[2]) + offset[1];
1872 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
1873 origin <<= ChildT::TOTAL;
1875 if (childMask.isOn(i)) {
1877 ChildT* child =
new ChildT(origin, mBackground);
1878 child->readTopology(is);
1879 mTable[origin] = NodeStruct(*child);
1884 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
1886 mTable[origin] = NodeStruct(Tile(value, valueMask.
isOn(i)));
1895 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
1898 Index numTiles = 0, numChildren = 0;
1899 is.read(reinterpret_cast<char*>(&numTiles),
sizeof(
Index));
1900 is.read(reinterpret_cast<char*>(&numChildren),
sizeof(
Index));
1902 if (numTiles == 0 && numChildren == 0)
return false;
1909 for (
Index n = 0; n < numTiles; ++n) {
1910 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
1911 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
1912 is.read(reinterpret_cast<char*>(&active),
sizeof(
bool));
1913 mTable[
Coord(vec)] = NodeStruct(Tile(value, active));
1917 for (
Index n = 0; n < numChildren; ++n) {
1918 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
1920 ChildT* child =
new ChildT(origin, mBackground);
1921 child->readTopology(is, fromHalf);
1922 mTable[
Coord(vec)] = NodeStruct(*child);
1929 template<
typename ChildT>
1933 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1934 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
1939 template<
typename ChildT>
1943 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1944 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
1952 template<
typename ChildT>
1953 template<
typename PruneOp>
1957 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1958 if (this->isTile(i)|| !op(this->getChild(i)))
continue;
1959 this->setTile(i, Tile(op.value, op.state));
1961 this->eraseBackgroundTiles();
1965 template<
typename ChildT>
1974 template<
typename ChildT>
1983 template<
typename ChildT>
1987 this->pruneInactive(mBackground);
1991 template<
typename ChildT>
2002 template<
typename ChildT>
2003 template<
typename NodeT>
2007 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2008 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2010 MapIter iter = this->findCoord(xyz);
2011 if (iter == mTable.end() || isTile(iter))
return NULL;
2012 return (boost::is_same<NodeT, ChildT>::value)
2013 ?
reinterpret_cast<NodeT*
>(&stealChild(iter, Tile(value, state)))
2014 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2022 template<
typename ChildT>
2026 if (leaf == NULL)
return;
2027 ChildT* child = NULL;
2028 const Coord& xyz = leaf->origin();
2029 MapIter iter = this->findCoord(xyz);
2030 if (iter == mTable.end()) {
2031 if (ChildT::LEVEL>0) {
2032 child =
new ChildT(xyz, mBackground,
false);
2034 child =
reinterpret_cast<ChildT*
>(leaf);
2036 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2037 }
else if (isChild(iter)) {
2038 if (ChildT::LEVEL>0) {
2039 child = &getChild(iter);
2041 child =
reinterpret_cast<ChildT*
>(leaf);
2042 setChild(iter, *child);
2045 if (ChildT::LEVEL>0) {
2046 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2048 child =
reinterpret_cast<ChildT*
>(leaf);
2050 setChild(iter, *child);
2052 child->addLeaf(leaf);
2056 template<
typename ChildT>
2057 template<
typename AccessorT>
2061 if (leaf == NULL)
return;
2062 ChildT* child = NULL;
2063 const Coord& xyz = leaf->origin();
2064 MapIter iter = this->findCoord(xyz);
2065 if (iter == mTable.end()) {
2066 if (ChildT::LEVEL>0) {
2067 child =
new ChildT(xyz, mBackground,
false);
2069 child =
reinterpret_cast<ChildT*
>(leaf);
2071 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2072 }
else if (isChild(iter)) {
2073 if (ChildT::LEVEL>0) {
2074 child = &getChild(iter);
2076 child =
reinterpret_cast<ChildT*
>(leaf);
2077 setChild(iter, *child);
2080 if (ChildT::LEVEL>0) {
2081 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2083 child =
reinterpret_cast<ChildT*
>(leaf);
2085 setChild(iter, *child);
2087 acc.insert(xyz, child);
2088 child->addLeafAndCache(leaf, acc);
2092 template<
typename ChildT>
2097 if (LEVEL >= level && level > 0) {
2098 MapIter iter = this->findCoord(xyz);
2099 if (iter == mTable.end()) {
2100 if (LEVEL > level) {
2101 ChildT* child =
new ChildT(xyz, mBackground,
false);
2102 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2103 child->addTile(level, xyz, value, state);
2105 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2107 }
else if (isChild(iter)) {
2108 if (LEVEL > level) {
2109 getChild(iter).addTile(level, xyz, value, state);
2111 setTile(iter, Tile(value, state));
2114 if (LEVEL > level) {
2115 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2116 setChild(iter, *child);
2117 child->addTile(level, xyz, value, state);
2119 setTile(iter, Tile(value, state));
2126 template<
typename ChildT>
2127 template<
typename AccessorT>
2130 bool state, AccessorT& acc)
2132 if (LEVEL >= level && level > 0) {
2133 MapIter iter = this->findCoord(xyz);
2134 if (iter == mTable.end()) {
2135 if (LEVEL > level) {
2136 ChildT* child =
new ChildT(xyz, mBackground,
false);
2137 acc.insert(xyz, child);
2138 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2139 child->addTileAndCache(level, xyz, value, state, acc);
2141 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2143 }
else if (isChild(iter)) {
2144 if (LEVEL > level) {
2145 ChildT* child = &getChild(iter);
2146 acc.insert(xyz, child);
2147 child->addTileAndCache(level, xyz, value, state, acc);
2149 setTile(iter, Tile(value, state));
2152 if (LEVEL > level) {
2153 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2154 acc.insert(xyz, child);
2155 setChild(iter, *child);
2156 child->addTileAndCache(level, xyz, value, state, acc);
2158 setTile(iter, Tile(value, state));
2168 template<
typename ChildT>
2169 inline typename ChildT::LeafNodeType*
2172 ChildT* child = NULL;
2173 MapIter iter = this->findCoord(xyz);
2174 if (iter == mTable.end()) {
2175 child =
new ChildT(xyz, mBackground,
false);
2176 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2177 }
else if (isChild(iter)) {
2178 child = &getChild(iter);
2180 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2181 setChild(iter, *child);
2183 return child->touchLeaf(xyz);
2187 template<
typename ChildT>
2188 template<
typename AccessorT>
2189 inline typename ChildT::LeafNodeType*
2192 ChildT* child = NULL;
2193 MapIter iter = this->findCoord(xyz);
2194 if (iter == mTable.end()) {
2195 child =
new ChildT(xyz, mBackground,
false);
2196 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2197 }
else if (isChild(iter)) {
2198 child = &getChild(iter);
2200 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2201 setChild(iter, *child);
2203 acc.insert(xyz, child);
2204 return child->touchLeafAndCache(xyz, acc);
2210 template<
typename ChildT>
2211 template<
typename NodeT>
2215 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2216 NodeT::LEVEL > ChildT::LEVEL)
return false;
2218 return ChildT::template hasNodeType<NodeT>();
2224 template<
typename ChildT>
2225 template<
typename NodeT>
2229 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2230 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2232 MapIter iter = this->findCoord(xyz);
2233 if (iter == mTable.end() || isTile(iter))
return NULL;
2234 ChildT* child = &getChild(iter);
2235 return (boost::is_same<NodeT, ChildT>::value)
2236 ?
reinterpret_cast<NodeT*
>(child)
2237 : child->template probeNode<NodeT>(xyz);
2240 template<
typename ChildT>
2241 template<
typename NodeT>
2245 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2246 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2248 MapCIter iter = this->findCoord(xyz);
2249 if (iter == mTable.end() || isTile(iter))
return NULL;
2250 const ChildT* child = &getChild(iter);
2251 return (boost::is_same<NodeT, ChildT>::value)
2252 ?
reinterpret_cast<const NodeT*
>(child)
2253 : child->template probeConstNode<NodeT>(xyz);
2256 template<
typename ChildT>
2257 template<
typename NodeT,
typename AccessorT>
2261 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2262 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2264 MapIter iter = this->findCoord(xyz);
2265 if (iter == mTable.end() || isTile(iter))
return NULL;
2266 ChildT* child = &getChild(iter);
2267 acc.insert(xyz, child);
2268 return (boost::is_same<NodeT, ChildT>::value)
2269 ?
reinterpret_cast<NodeT*
>(child)
2270 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2274 template<
typename ChildT>
2275 template<
typename NodeT,
typename AccessorT>
2279 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2280 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2282 MapCIter iter = this->findCoord(xyz);
2283 if (iter == mTable.end() || isTile(iter))
return NULL;
2284 const ChildT* child = &getChild(iter);
2285 acc.insert(xyz, child);
2286 return (boost::is_same<NodeT, ChildT>::value)
2287 ?
reinterpret_cast<const NodeT*
>(child)
2288 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2295 template<
typename ChildT>
2299 this->signedFloodFill(mBackground,
negative(mBackground));
2303 template<
typename ChildT>
2307 const ValueType zero = zeroVal<ValueType>();
2309 mBackground = outside;
2313 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2314 if (this->isTile(i))
continue;
2315 getChild(i).signedFloodFill(outside, inside);
2316 nodeKeys.insert(i->first);
2322 const Tile insideTile(inside,
false);
2323 CoordSetCIter b = nodeKeys.begin(), e = nodeKeys.end();
2324 if ( b == e )
return;
2325 for (CoordSetCIter a = b++; b != e; ++a, ++b) {
2327 if (d[0]!=0 || d[1]!=0 || d[2]==
Int32(ChildT::DIM))
continue;
2328 MapIter i = mTable.find(*a), j = mTable.find(*b);
2329 const ValueType fill[] = { getChild(i).getLastValue(), getChild(j).getFirstValue() };
2330 if (!(fill[0] < zero) || !(fill[1] < zero))
continue;
2331 for (
Coord c = *a +
Coord(0u,0u,ChildT::DIM); c[2] != (*b)[2]; c[2] += ChildT::DIM) {
2332 mTable[c] = insideTile;
2341 template<
typename ChildT>
2345 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2346 if (this->isTileOff(i))
continue;
2347 ChildT* child = i->second.child;
2349 child =
new ChildT(i->first, this->getTile(i).value,
true);
2350 i->second.child = child;
2352 child->voxelizeActiveTiles();
2360 template<
typename ChildT>
2364 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2365 MapIter j = mTable.find(i->first);
2366 if (other.isChild(i)) {
2367 if (j == mTable.end()) {
2368 mTable[i->first]=NodeStruct(stealChild(i, Tile(other.mBackground,
false)));
2369 }
else if (isTile(j)) {
2370 setChild(j, stealChild(i, Tile(other.mBackground,
false)));
2372 getChild(j).merge(getChild(i),other.mBackground, mBackground);
2375 if (j == mTable.end()) {
2376 mTable[i->first] = i->second;
2388 template<
typename ChildT>
2389 template<
typename OtherChildType>
2394 typedef typename OtherRootT::MapCIter OtherCIterT;
2396 enforceSameConfiguration(other);
2398 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2399 MapIter j = mTable.find(i->first);
2400 if (other.isChild(i)) {
2401 if (j == mTable.end()) {
2402 mTable[i->first] = NodeStruct(
2403 *(
new ChildT(other.getChild(i), mBackground,
TopologyCopy())));
2404 }
else if (this->isChild(j)) {
2405 this->getChild(j).topologyUnion(other.getChild(i));
2407 ChildT* child =
new ChildT(
2408 other.getChild(i), this->getTile(j).value,
TopologyCopy());
2409 if (this->isTileOn(j)) child->setValuesOn();
2410 this->setChild(j, *child);
2412 }
else if (other.isTileOn(i)) {
2413 if (j == mTable.end()) {
2414 mTable[i->first] = NodeStruct(Tile(mBackground,
true));
2415 }
else if (this->isChild(j)) {
2416 this->getChild(j).setValuesOn();
2417 }
else if (this->isTileOff(j)) {
2418 this->setTile(j, Tile(this->getTile(j).value,
true));
2428 template<
typename ChildT>
2429 template<
typename CombineOp>
2436 this->insertKeys(keys);
2437 other.insertKeys(keys);
2439 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2440 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
2441 if (isTile(iter) && isTile(otherIter)) {
2444 op(args.
setARef(getTile(iter).value)
2445 .setAIsActive(isTileOn(iter))
2446 .setBRef(getTile(otherIter).value)
2447 .setBIsActive(isTileOn(otherIter)));
2450 }
else if (isChild(iter) && isTile(otherIter)) {
2452 ChildT& child = getChild(iter);
2453 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
2455 }
else if (isTile(iter) && isChild(otherIter)) {
2460 ChildT& child = getChild(otherIter);
2461 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
2464 setChild(iter, stealChild(otherIter, Tile()));
2468 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
2469 child.combine(otherChild, op);
2471 if (prune && isChild(iter)) getChild(iter).prune();
2475 op(args.
setARef(mBackground).setBRef(other.mBackground));
2476 mBackground = args.
result();
2486 template<
typename ChildT>
2487 template<
typename CombineOp>
2490 CombineOp& op,
bool prune)
2495 other0.insertKeys(keys);
2496 other1.insertKeys(keys);
2499 bg0(Tile(other0.mBackground,
false)),
2500 bg1(Tile(other1.mBackground,
false));
2502 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2503 MapIter thisIter = this->findOrAddCoord(*i);
2504 MapCIter iter0 = other0.findKey(*i), iter1 = other1.findKey(*i);
2506 &ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0,
2507 &ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
2508 if (ns0.isTile() && ns1.isTile()) {
2511 op(args.
setARef(ns0.tile.value)
2512 .setAIsActive(ns0.isTileOn())
2513 .setBRef(ns1.tile.value)
2514 .setBIsActive(ns1.isTileOn()));
2517 ChildT& otherChild = ns0.isChild() ? *ns0.child : *ns1.child;
2518 if (!isChild(thisIter)) {
2521 *(
new ChildT(otherChild.getOrigin(), getTile(thisIter).value)));
2523 ChildT& child = getChild(thisIter);
2528 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
2529 }
else if (ns1.isTile()) {
2532 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
2536 child.combine2(*ns0.child, *ns1.child, op);
2539 if (prune && isChild(thisIter)) getChild(thisIter).prune();
2543 op(args.
setARef(other0.mBackground).setBRef(other1.mBackground));
2544 mBackground = args.
result();
2551 template<
typename ChildT>
2552 template<
typename BBoxOp>
2556 const bool descent = op.template descent<LEVEL>();
2557 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2558 if (this->isTileOff(i))
continue;
2559 if (this->isChild(i) && descent) {
2560 this->getChild(i).visitActiveBBox(op);
2572 template<
typename ChildT>
2573 template<
typename VisitorOp>
2577 doVisit<RootNode, VisitorOp, ChildAllIter>(*
this, op);
2581 template<
typename ChildT>
2582 template<
typename VisitorOp>
2586 doVisit<const RootNode, VisitorOp, ChildAllCIter>(*
this, op);
2590 template<
typename ChildT>
2591 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
2595 typename RootNodeT::ValueType val;
2596 for (ChildAllIterT iter =
self.beginChildAll(); iter; ++iter) {
2597 if (op(iter))
continue;
2598 if (
typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2608 template<
typename ChildT>
2609 template<
typename OtherRootNodeType,
typename VisitorOp>
2614 typename OtherRootNodeType::ChildAllIter>(*
this, other, op);
2618 template<
typename ChildT>
2619 template<
typename OtherRootNodeType,
typename VisitorOp>
2624 typename OtherRootNodeType::ChildAllCIter>(*
this, other, op);
2628 template<
typename ChildT>
2631 typename OtherRootNodeT,
2633 typename ChildAllIterT,
2634 typename OtherChildAllIterT>
2640 enforceSameConfiguration(other);
2642 typename RootNodeT::ValueType val;
2643 typename OtherRootNodeT::ValueType otherVal;
2648 RootNodeT copyOfSelf(
self.mBackground);
2649 copyOfSelf.mTable =
self.mTable;
2650 OtherRootNodeT copyOfOther(other.mBackground);
2651 copyOfOther.mTable = other.mTable;
2655 self.insertKeys(keys);
2656 other.insertKeys(keys);
2657 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2658 copyOfSelf.findOrAddCoord(*i);
2659 copyOfOther.findOrAddCoord(*i);
2662 ChildAllIterT iter = copyOfSelf.beginChildAll();
2663 OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
2665 for ( ; iter && otherIter; ++iter, ++otherIter)
2667 const size_t skipBranch =
static_cast<size_t>(op(iter, otherIter));
2669 typename ChildAllIterT::ChildNodeType* child =
2670 (skipBranch & 1U) ? NULL : iter.probeChild(val);
2671 typename OtherChildAllIterT::ChildNodeType* otherChild =
2672 (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
2674 if (child != NULL && otherChild != NULL) {
2675 child->visit2Node(*otherChild, op);
2676 }
else if (child != NULL) {
2677 child->visit2(otherIter, op);
2678 }
else if (otherChild != NULL) {
2679 otherChild->visit2(iter, op,
true);
2684 copyOfSelf.eraseBackgroundTiles();
2685 copyOfOther.eraseBackgroundTiles();
2689 self.resetTable(copyOfSelf.mTable);
2690 other.resetTable(copyOfOther.mTable);
2697 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED