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 <boost/mpl/vector.hpp>
43 #include <boost/mpl/at.hpp>
44 #include <boost/mpl/push_back.hpp>
45 #include <boost/mpl/size.hpp>
46 #include <openvdb/Exceptions.h>
47 #include <openvdb/Types.h>
48 #include <openvdb/io/Compression.h>
49 #include <openvdb/math/Math.h>
50 #include <openvdb/math/BBox.h>
51 #include <openvdb/util/NodeMasks.h>
52 #include <openvdb/version.h>
62 template<
typename HeadType,
int HeadLevel>
struct NodeChain;
68 template<
typename ChildType>
76 static const Index LEVEL = 1 + ChildType::LEVEL;
80 BOOST_STATIC_ASSERT(boost::mpl::size<NodeChainType>::value == LEVEL + 1);
84 template<
typename OtherValueType>
92 template<
typename OtherNodeType>
112 template<
typename OtherChildType>
123 template<
typename OtherChildType>
125 const ValueType& background,
const ValueType& foreground,
TopologyCopy);
137 template<
typename OtherChildType>
149 template<
typename OtherChildType>
156 Tile(): value(
zeroVal<ValueType>()), active(false) {}
157 Tile(
const ValueType& v,
bool b): value(v), active(b) {}
167 NodeStruct(): child(NULL) {}
168 NodeStruct(ChildType& c): child(&c) {}
169 NodeStruct(
const Tile& t): child(NULL), tile(t) {}
172 bool isChild()
const {
return child != NULL; }
173 bool isTile()
const {
return child == NULL; }
174 bool isTileOff()
const {
return isTile() && !tile.active; }
175 bool isTileOn()
const {
return isTile() && tile.active; }
177 void set(ChildType& c) {
delete child; child = &c; }
178 void set(
const Tile& t) {
delete child; child = NULL; tile = t; }
179 ChildType& steal(
const Tile& t) { ChildType* c = child; child = NULL; tile = t;
return *c; }
182 typedef std::map<Coord, NodeStruct> MapType;
183 typedef typename MapType::iterator MapIter;
184 typedef typename MapType::const_iterator MapCIter;
186 typedef std::set<Coord> CoordSet;
187 typedef typename CoordSet::iterator CoordSetIter;
188 typedef typename CoordSet::const_iterator CoordSetCIter;
190 static void setTile(
const MapIter& i,
const Tile& t) { i->second.set(t); }
191 static void setChild(
const MapIter& i, ChildType& c) { i->second.set(c); }
192 static Tile& getTile(
const MapIter& i) {
return i->second.tile; }
193 static const Tile& getTile(
const MapCIter& i) {
return i->second.tile; }
194 static ChildType& getChild(
const MapIter& i) {
return *(i->second.child); }
195 static const ChildType& getChild(
const MapCIter& i) {
return *(i->second.child); }
196 static ChildType& stealChild(
const MapIter& i,
const Tile& t) {
return i->second.steal(t);}
197 static const ChildType& stealChild(
const MapCIter& i,
const Tile& t) {
return i->second.steal(t);}
199 static bool isChild(
const MapCIter& i) {
return i->second.isChild(); }
200 static bool isChild(
const MapIter& i) {
return i->second.isChild(); }
201 static bool isTile(
const MapCIter& i) {
return i->second.isTile(); }
202 static bool isTile(
const MapIter& i) {
return i->second.isTile(); }
203 static bool isTileOff(
const MapCIter& i) {
return i->second.isTileOff(); }
204 static bool isTileOff(
const MapIter& i) {
return i->second.isTileOff(); }
205 static bool isTileOn(
const MapCIter& i) {
return i->second.isTileOn(); }
206 static bool isTileOn(
const MapIter& i) {
return i->second.isTileOn(); }
209 static inline bool test(
const MapIter&) {
return true; }
210 static inline bool test(
const MapCIter&) {
return true; }
213 static inline bool test(
const MapIter& i) {
return isTileOn(i); }
214 static inline bool test(
const MapCIter& i) {
return isTileOn(i); }
216 struct ValueOffPred {
217 static inline bool test(
const MapIter& i) {
return isTileOff(i); }
218 static inline bool test(
const MapCIter& i) {
return isTileOff(i); }
220 struct ValueAllPred {
221 static inline bool test(
const MapIter& i) {
return isTile(i); }
222 static inline bool test(
const MapCIter& i) {
return isTile(i); }
225 static inline bool test(
const MapIter& i) {
return isChild(i); }
226 static inline bool test(
const MapCIter& i) {
return isChild(i); }
228 struct ChildOffPred {
229 static inline bool test(
const MapIter& i) {
return isTile(i); }
230 static inline bool test(
const MapCIter& i) {
return isTile(i); }
233 template<
typename _RootNodeT,
typename _MapIterT,
typename FilterPredT>
237 typedef _RootNodeT RootNodeT;
238 typedef _MapIterT MapIterT;
242 return (mParentNode == other.mParentNode) && (mIter == other.mIter);
244 bool operator!=(
const BaseIter& other)
const {
return !(*
this == other); }
246 RootNodeT* getParentNode()
const {
return mParentNode; }
248 RootNodeT& parent()
const
250 if (!mParentNode)
OPENVDB_THROW(ValueError,
"iterator references a null parent node");
254 bool test()
const { assert(mParentNode);
return mIter != mParentNode->mTable.end(); }
255 operator bool()
const {
return this->test(); }
257 void increment() { ++mIter; this->skip(); }
258 bool next() { this->increment();
return this->test(); }
259 void increment(
Index n) {
for (
int i = 0; i < n && this->next(); ++i) {} }
265 return !mParentNode ? 0U :
Index(std::distance(mParentNode->mTable.begin(), mIter));
268 bool isValueOn()
const {
return RootNodeT::isTileOn(mIter); }
269 bool isValueOff()
const {
return RootNodeT::isTileOff(mIter); }
270 void setValueOn(
bool on =
true)
const { mIter->second.tile.active = on; }
271 void setValueOff()
const { mIter->second.tile.active =
false; }
274 Coord getCoord()
const {
return mIter->first; }
276 void getCoord(Coord& xyz)
const { xyz = this->getCoord(); }
279 BaseIter(): mParentNode(NULL) {}
280 BaseIter(RootNodeT& parent,
const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
282 void skip() {
while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
284 RootNodeT* mParentNode;
288 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ChildNodeT>
289 class ChildIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
292 typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
293 typedef RootNodeT NodeType;
294 typedef NodeType ValueType;
295 typedef ChildNodeT ChildNodeType;
296 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
297 typedef typename boost::remove_const<ValueType>::type NonConstValueType;
298 typedef typename boost::remove_const<ChildNodeType>::type NonConstChildNodeType;
302 ChildIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
304 ChildIter& operator++() { BaseT::increment();
return *
this; }
306 ChildNodeT& getValue()
const {
return getChild(mIter); }
307 ChildNodeT&
operator*()
const {
return this->getValue(); }
308 ChildNodeT* operator->()
const {
return &this->getValue(); }
311 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ValueT>
312 class ValueIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
315 typedef BaseIter<RootNodeT, MapIterT, FilterPredT> BaseT;
316 typedef RootNodeT NodeType;
317 typedef ValueT ValueType;
318 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
319 typedef typename boost::remove_const<ValueT>::type NonConstValueType;
323 ValueIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
325 ValueIter& operator++() { BaseT::increment();
return *
this; }
327 ValueT& getValue()
const {
return getTile(mIter).value; }
328 ValueT&
operator*()
const {
return this->getValue(); }
329 ValueT* operator->()
const {
return &(this->getValue()); }
331 void setValue(
const ValueT& v)
const { assert(isTile(mIter)); getTile(mIter).value = v; }
333 template<
typename ModifyOp>
334 void modifyValue(
const ModifyOp& op)
const
336 assert(isTile(mIter));
337 op(getTile(mIter).value);
341 template<
typename RootNodeT,
typename MapIterT,
typename ChildNodeT,
typename ValueT>
342 class DenseIter:
public BaseIter<RootNodeT, MapIterT, NullPred>
345 typedef BaseIter<RootNodeT, MapIterT, NullPred> BaseT;
346 typedef RootNodeT NodeType;
347 typedef ValueT ValueType;
348 typedef ChildNodeT ChildNodeType;
349 typedef typename boost::remove_const<NodeType>::type NonConstNodeType;
350 typedef typename boost::remove_const<ValueT>::type NonConstValueType;
351 typedef typename boost::remove_const<ChildNodeT>::type NonConstChildNodeType;
355 DenseIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) {}
357 DenseIter& operator++() { BaseT::increment();
return *
this; }
359 bool isChildNode()
const {
return isChild(mIter); }
361 ChildNodeT* probeChild(NonConstValueType& value)
const
363 if (isChild(mIter))
return &getChild(mIter);
364 value = getTile(mIter).value;
367 bool probeChild(ChildNodeT*& child, NonConstValueType& value)
const
369 child = this->probeChild(value);
370 return child != NULL;
372 bool probeValue(NonConstValueType& value)
const {
return !this->probeChild(value); }
374 void setChild(ChildNodeT& c)
const { RootNodeT::setChild(mIter, c); }
375 void setChild(ChildNodeT* c)
const { assert(c != NULL); RootNodeT::setChild(mIter, *c); }
376 void setValue(
const ValueT& v)
const
378 if (isTile(mIter)) getTile(mIter).value = v;
382 else stealChild(mIter, Tile(v,
true));
387 typedef ChildIter<RootNode, MapIter, ChildOnPred, ChildType>
ChildOnIter;
388 typedef ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>
ChildOnCIter;
389 typedef ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>
ChildOffIter;
390 typedef ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>
ChildOffCIter;
391 typedef DenseIter<RootNode, MapIter, ChildType, ValueType>
ChildAllIter;
392 typedef DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>
ChildAllCIter;
394 typedef ValueIter<RootNode, MapIter, ValueOnPred, ValueType>
ValueOnIter;
395 typedef ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>
ValueOnCIter;
396 typedef ValueIter<RootNode, MapIter, ValueOffPred, ValueType>
ValueOffIter;
397 typedef ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>
ValueOffCIter;
398 typedef ValueIter<RootNode, MapIter, ValueAllPred, ValueType>
ValueAllIter;
399 typedef ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>
ValueAllCIter;
430 void evalActiveBoundingBox(CoordBBox& bbox,
bool visitVoxels =
true)
const;
442 void setBackground(
const ValueType& value,
bool updateChildNodes =
true);
448 bool isBackgroundTile(
const Tile&)
const;
450 bool isBackgroundTile(
const MapIter&)
const;
452 bool isBackgroundTile(
const MapCIter&)
const;
456 size_t numBackgroundTiles()
const;
459 size_t eraseBackgroundTiles();
460 void clear() { this->clearTable(); }
463 bool empty()
const {
return mTable.size() == numBackgroundTiles(); }
468 bool expand(
const Coord& xyz);
471 static void getNodeLog2Dims(std::vector<Index>& dims);
477 Index getWidth()
const {
return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
478 Index getHeight()
const {
return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
479 Index getDepth()
const {
return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
482 Coord getMinIndex()
const;
484 Coord getMaxIndex()
const;
486 void getIndexRange(CoordBBox& bbox)
const;
490 template<
typename OtherChildType>
494 template<
typename OtherChildType>
499 template<
typename OtherChildType>
506 Index64 onLeafVoxelCount()
const;
507 Index64 offLeafVoxelCount()
const;
510 bool isValueOn(
const Coord& xyz)
const;
512 bool hasActiveTiles()
const;
514 const ValueType& getValue(
const Coord& xyz)
const;
515 bool probeValue(
const Coord& xyz, ValueType& value)
const;
520 int getValueDepth(
const Coord& xyz)
const;
523 void setActiveState(
const Coord& xyz,
bool on);
525 void setValueOnly(
const Coord& xyz,
const ValueType& value);
527 void setValueOn(
const Coord& xyz,
const ValueType& value);
529 void setValueOff(
const Coord& xyz);
531 void setValueOff(
const Coord& xyz,
const ValueType& value);
535 template<
typename ModifyOp>
536 void modifyValue(
const Coord& xyz,
const ModifyOp& op);
538 template<
typename ModifyOp>
539 void modifyValueAndActiveState(
const Coord& xyz,
const ModifyOp& op);
547 void fill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
554 template<
typename DenseT>
555 void copyToDense(
const CoordBBox& bbox, DenseT& dense)
const;
561 bool writeTopology(std::ostream&,
bool toHalf =
false)
const;
562 bool readTopology(std::istream&,
bool fromHalf =
false);
564 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
565 void readBuffers(std::istream&,
bool fromHalf =
false);
575 template<
typename AccessorT>
576 const ValueType& getValueAndCache(
const Coord& xyz, AccessorT&)
const;
581 template<
typename AccessorT>
582 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
588 template<
typename AccessorT>
589 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
595 template<
typename AccessorT>
596 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
603 template<
typename ModifyOp,
typename AccessorT>
604 void modifyValueAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
610 template<
typename ModifyOp,
typename AccessorT>
611 void modifyValueAndActiveStateAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
617 template<
typename AccessorT>
618 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
624 template<
typename AccessorT>
625 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
632 template<
typename AccessorT>
633 bool probeValueAndCache(
const Coord& xyz, ValueType& value, AccessorT&)
const;
640 template<
typename AccessorT>
641 int getValueDepthAndCache(
const Coord& xyz, AccessorT&)
const;
649 template<
typename PruneOp>
void pruneOp(PruneOp&);
654 void prune(
const ValueType& tolerance = zeroVal<ValueType>());
658 void pruneInactive(
const ValueType&);
662 void pruneInactive();
667 void pruneTiles(
const ValueType& tolerance);
671 void addLeaf(LeafNodeType* leaf);
675 template<
typename AccessorT>
676 void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
686 template<
typename NodeT>
687 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool state);
692 void addTile(
Index level,
const Coord& xyz,
const ValueType& value,
bool state);
696 template<
typename AccessorT>
697 void addTileAndCache(
Index level,
const Coord& xyz,
const ValueType&,
bool state, AccessorT&);
704 LeafNodeType* touchLeaf(
const Coord& xyz);
708 template<
typename AccessorT>
709 LeafNodeType* touchLeafAndCache(
const Coord& xyz, AccessorT& acc);
712 template <
typename NodeT>
715 NodeT* probeNode(
const Coord& xyz);
716 template <
typename NodeT>
717 const NodeT* probeConstNode(
const Coord& xyz)
const;
721 template<
typename NodeT,
typename AccessorT>
724 NodeT* probeNodeAndCache(
const Coord& xyz, AccessorT& acc);
725 template<
typename NodeT,
typename AccessorT>
726 const NodeT* probeConstNodeAndCache(
const Coord& xyz, AccessorT& acc)
const;
730 LeafNodeType* probeLeaf(
const Coord& xyz);
733 const LeafNodeType* probeConstLeaf(
const Coord& xyz)
const;
734 const LeafNodeType* probeLeaf(
const Coord& xyz)
const;
738 template<
typename AccessorT>
741 LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT& acc);
742 template<
typename AccessorT>
743 const LeafNodeType* probeConstLeafAndCache(
const Coord& xyz, AccessorT& acc)
const;
744 template<
typename AccessorT>
745 const LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT& acc)
const;
756 void signedFloodFill();
763 void signedFloodFill(
const ValueType& outside,
const ValueType& inside);
766 void voxelizeActiveTiles();
775 template<MergePolicy Policy>
void merge(
RootNode& other);
790 template<
typename OtherChildType>
806 template<
typename OtherChildType>
819 template<
typename OtherChildType>
822 template<
typename CombineOp>
825 template<
typename CombineOp,
typename OtherRootNode >
826 void combine2(
const RootNode& other0,
const OtherRootNode& other1,
827 CombineOp& op,
bool prune =
false);
834 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
836 template<
typename VisitorOp>
void visit(VisitorOp&);
837 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
839 template<
typename OtherRootNodeType,
typename VisitorOp>
840 void visit2(OtherRootNodeType& other, VisitorOp&);
841 template<
typename OtherRootNodeType,
typename VisitorOp>
842 void visit2(OtherRootNodeType& other, VisitorOp&)
const;
854 inline void clearTable();
856 void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
858 void resetTable(
const MapType&)
const {}
861 Index getChildCount()
const;
862 Index getTileCount()
const;
863 Index getActiveTileCount()
const;
864 Index getInactiveTileCount()
const;
867 static Coord coordToKey(
const Coord& xyz) {
return xyz & ~(ChildType::DIM - 1); }
870 void insertKeys(CoordSet&)
const;
873 bool hasKey(
const Coord& key)
const {
return mTable.find(key) != mTable.end(); }
875 MapIter findKey(
const Coord& key) {
return mTable.find(key); }
878 MapCIter findKey(
const Coord& key)
const {
return mTable.find(key); }
881 MapIter findCoord(
const Coord& xyz) {
return mTable.find(coordToKey(xyz)); }
884 MapCIter findCoord(
const Coord& xyz)
const {
return mTable.find(coordToKey(xyz)); }
886 MapIter findOrAddCoord(
const Coord& xyz);
895 template<
typename OtherChildType>
896 static void enforceSameConfiguration(
const RootNode<OtherChildType>& other);
903 template<
typename OtherChildType>
904 static void enforceCompatibleValueTypes(
const RootNode<OtherChildType>& other);
906 template<
typename CombineOp,
typename OtherRootNode >
907 void doCombine2(
const RootNode&,
const OtherRootNode&, CombineOp&,
bool prune);
909 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
910 static inline void doVisit(RootNodeT&, VisitorOp&);
912 template<
typename RootNodeT,
typename OtherRootNodeT,
typename VisitorOp,
913 typename ChildAllIterT,
typename OtherChildAllIterT>
914 static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
918 ValueType mBackground;
945 template<
typename HeadT,
int HeadLevel>
948 typedef typename boost::mpl::push_back<SubtreeT, HeadT>::type
Type;
952 template<
typename HeadT>
954 typedef typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type
Type;
962 template<
typename ChildT1,
typename NodeT2>
966 static const bool value =
false;
969 template<
typename ChildT1,
typename ChildT2>
971 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
979 template<
typename ChildT>
987 template<
typename ChildT>
995 template<
typename ChildT>
996 template<
typename OtherChildType>
1004 enforceSameConfiguration(other);
1006 const Tile bgTile(backgd,
false), fgTile(foregd,
true);
1009 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1010 mTable[i->first] = OtherRootT::isTile(i)
1011 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1012 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd, foregd,
TopologyCopy())));
1017 template<
typename ChildT>
1018 template<
typename OtherChildType>
1026 enforceSameConfiguration(other);
1028 const Tile bgTile(backgd,
false), fgTile(backgd,
true);
1030 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1031 mTable[i->first] = OtherRootT::isTile(i)
1032 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1033 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd,
TopologyCopy())));
1044 template<
typename RootT,
typename OtherRootT,
bool Compatible = false>
1051 self.enforceSameConfiguration(other);
1052 self.enforceCompatibleValueTypes(other);
1054 std::ostringstream ostr;
1055 ostr <<
"cannot convert a " <<
typeid(OtherRootT).name()
1056 <<
" to a " <<
typeid(RootT).name();
1062 template<
typename RootT,
typename OtherRootT>
1067 typedef typename RootT::ValueType ValueT;
1068 typedef typename RootT::ChildNodeType ChildT;
1069 typedef typename RootT::NodeStruct NodeStruct;
1070 typedef typename RootT::Tile Tile;
1071 typedef typename OtherRootT::ValueType OtherValueT;
1072 typedef typename OtherRootT::ChildNodeType OtherChildT;
1073 typedef typename OtherRootT::MapCIter OtherMapCIter;
1074 typedef typename OtherRootT::Tile OtherTile;
1078 static inline ValueT convertValue(
const OtherValueT& val) {
return ValueT(val); }
1081 self.mBackground = Local::convertValue(other.mBackground);
1086 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1087 if (other.isTile(i)) {
1089 const OtherTile& otherTile = other.getTile(i);
1090 self.mTable[i->first] = NodeStruct(
1091 Tile(Local::convertValue(otherTile.value), otherTile.active));
1094 self.mTable[i->first] = NodeStruct(*(
new ChildT(other.getChild(i))));
1102 template<
typename ChildT>
1103 inline RootNode<ChildT>&
1106 if (&other !=
this) {
1107 mBackground = other.mBackground;
1112 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1114 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(
new ChildT(getChild(i))));
1121 template<
typename ChildT>
1122 template<
typename OtherChildType>
1127 typedef typename OtherRootT::ValueType OtherValueT;
1138 template<
typename ChildT>
1144 if (updateChildNodes) {
1147 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1148 ChildT *child = iter->second.child;
1150 child->resetBackground(mBackground, background);
1152 Tile& tile = getTile(iter);
1153 if (tile.active)
continue;
1155 tile.value = background;
1162 mBackground = background;
1166 template<
typename ChildT>
1173 template<
typename ChildT>
1180 template<
typename ChildT>
1188 template<
typename ChildT>
1193 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1194 if (this->isBackgroundTile(i)) ++count;
1200 template<
typename ChildT>
1204 std::set<Coord> keysToErase;
1205 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1206 if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1208 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1211 return keysToErase.size();
1218 template<
typename ChildT>
1222 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1223 keys.insert(i->first);
1228 template<
typename ChildT>
1229 inline typename RootNode<ChildT>::MapIter
1230 RootNode<ChildT>::findOrAddCoord(
const Coord& xyz)
1232 const Coord key = coordToKey(xyz);
1233 std::pair<MapIter, bool> result = mTable.insert(
1234 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1235 return result.first;
1239 template<
typename ChildT>
1243 const Coord key = coordToKey(xyz);
1244 std::pair<MapIter, bool> result = mTable.insert(
1245 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1246 return result.second;
1253 template<
typename ChildT>
1258 ChildT::getNodeLog2Dims(dims);
1262 template<
typename ChildT>
1266 return mTable.empty() ? Coord(0) : mTable.begin()->first;
1269 template<
typename ChildT>
1273 return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1277 template<
typename ChildT>
1281 bbox.min() = this->getMinIndex();
1282 bbox.max() = this->getMaxIndex();
1289 template<
typename ChildT>
1290 template<
typename OtherChildType>
1295 typedef typename OtherRootT::MapType OtherMapT;
1296 typedef typename OtherRootT::MapIter OtherIterT;
1297 typedef typename OtherRootT::MapCIter OtherCIterT;
1299 if (!hasSameConfiguration(other))
return false;
1302 OtherMapT copyOfOtherTable = other.mTable;
1305 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1306 if (this->isBackgroundTile(thisIter))
continue;
1309 OtherCIterT otherIter = other.findKey(thisIter->first);
1310 if (otherIter == other.mTable.end())
return false;
1313 if (isChild(thisIter)) {
1314 if (OtherRootT::isTile(otherIter))
return false;
1316 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter)))
return false;
1318 if (OtherRootT::isChild(otherIter))
return false;
1319 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active)
return false;
1326 copyOfOtherTable.erase(otherIter->first);
1329 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1336 template<
typename ChildT>
1337 template<
typename OtherChildType>
1341 std::vector<Index> thisDims, otherDims;
1344 return (thisDims == otherDims);
1348 template<
typename ChildT>
1349 template<
typename OtherChildType>
1353 std::vector<Index> thisDims, otherDims;
1356 if (thisDims != otherDims) {
1357 std::ostringstream ostr;
1358 ostr <<
"grids have incompatible configurations (" << thisDims[0];
1359 for (
size_t i = 1, N = thisDims.size(); i < N; ++i) ostr <<
" x " << thisDims[i];
1360 ostr <<
" vs. " << otherDims[0];
1361 for (
size_t i = 1, N = otherDims.size(); i < N; ++i) ostr <<
" x " << otherDims[i];
1368 template<
typename ChildT>
1369 template<
typename OtherChildType>
1373 typedef typename OtherChildType::ValueType OtherValueType;
1378 template<
typename ChildT>
1379 template<
typename OtherChildType>
1383 typedef typename OtherChildType::ValueType OtherValueType;
1385 std::ostringstream ostr;
1386 ostr <<
"values of type " << typeNameAsString<OtherValueType>()
1387 <<
" cannot be converted to type " << typeNameAsString<ValueType>();
1396 template<
typename ChildT>
1401 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1402 if (
const ChildT *child = iter->second.child) {
1403 sum += child->memUsage();
1410 template<
typename ChildT>
1414 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1415 delete i->second.child;
1421 template<
typename ChildT>
1425 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1426 if (
const ChildT *child = iter->second.child) {
1427 child->evalActiveBoundingBox(bbox, visitVoxels);
1428 }
else if (isTileOn(iter)) {
1429 bbox.expand(iter->first, ChildT::DIM);
1435 template<
typename ChildT>
1439 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1440 if (isChild(i)) ++sum;
1446 template<
typename ChildT>
1448 RootNode<ChildT>::getTileCount()
const
1451 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1452 if (isTile(i)) ++sum;
1458 template<
typename ChildT>
1460 RootNode<ChildT>::getActiveTileCount()
const
1463 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1464 if (isTileOn(i)) ++sum;
1470 template<
typename ChildT>
1472 RootNode<ChildT>::getInactiveTileCount()
const
1475 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1476 if (isTileOff(i)) ++sum;
1482 template<
typename ChildT>
1487 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1488 if (isChild(i)) sum += getChild(i).leafCount();
1494 template<
typename ChildT>
1499 if (ChildT::LEVEL != 0) {
1500 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1501 if (isChild(i)) sum += getChild(i).nonLeafCount();
1508 template<
typename ChildT>
1513 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1515 sum += getChild(i).onVoxelCount();
1516 }
else if (isTileOn(i)) {
1517 sum += ChildT::NUM_VOXELS;
1524 template<
typename ChildT>
1529 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1531 sum += getChild(i).offVoxelCount();
1532 }
else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1533 sum += ChildT::NUM_VOXELS;
1540 template<
typename ChildT>
1545 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1546 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1552 template<
typename ChildT>
1557 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1558 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1563 template<
typename ChildT>
1568 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1570 sum += getChild(i).onTileCount();
1571 }
else if (isTileOn(i)) {
1581 template<
typename ChildT>
1585 MapCIter iter = this->findCoord(xyz);
1586 if (iter == mTable.end() || isTileOff(iter))
return false;
1587 return isTileOn(iter) ?
true : getChild(iter).isValueOn(xyz);
1590 template<
typename ChildT>
1594 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1595 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active)
return true;
1600 template<
typename ChildT>
1601 template<
typename AccessorT>
1605 MapCIter iter = this->findCoord(xyz);
1606 if (iter == mTable.end() || isTileOff(iter))
return false;
1607 if (isTileOn(iter))
return true;
1608 acc.insert(xyz, &getChild(iter));
1609 return getChild(iter).isValueOnAndCache(xyz, acc);
1613 template<
typename ChildT>
1614 inline const typename ChildT::ValueType&
1617 MapCIter iter = this->findCoord(xyz);
1618 return iter == mTable.end() ? mBackground
1619 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1622 template<
typename ChildT>
1623 template<
typename AccessorT>
1624 inline const typename ChildT::ValueType&
1627 MapCIter iter = this->findCoord(xyz);
1628 if (iter == mTable.end())
return mBackground;
1629 if (isChild(iter)) {
1630 acc.insert(xyz, &getChild(iter));
1631 return getChild(iter).getValueAndCache(xyz, acc);
1633 return getTile(iter).value;
1637 template<
typename ChildT>
1641 MapCIter iter = this->findCoord(xyz);
1642 return iter == mTable.end() ? -1
1643 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1646 template<
typename ChildT>
1647 template<
typename AccessorT>
1651 MapCIter iter = this->findCoord(xyz);
1652 if (iter == mTable.end())
return -1;
1653 if (isTile(iter))
return 0;
1654 acc.insert(xyz, &getChild(iter));
1655 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1659 template<
typename ChildT>
1663 MapIter iter = this->findCoord(xyz);
1664 if (iter != mTable.end() && !isTileOff(iter)) {
1665 if (isTileOn(iter)) {
1666 setChild(iter, *
new ChildT(xyz, getTile(iter).value,
true));
1668 getChild(iter).setValueOff(xyz);
1673 template<
typename ChildT>
1677 ChildT* child = NULL;
1678 MapIter iter = this->findCoord(xyz);
1679 if (iter == mTable.end()) {
1681 child =
new ChildT(xyz, mBackground);
1682 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1686 }
else if (isChild(iter)) {
1687 child = &getChild(iter);
1688 }
else if (on != getTile(iter).active) {
1689 child =
new ChildT(xyz, getTile(iter).value, !on);
1690 setChild(iter, *child);
1692 if (child) child->setActiveState(xyz, on);
1695 template<
typename ChildT>
1696 template<
typename AccessorT>
1700 ChildT* child = NULL;
1701 MapIter iter = this->findCoord(xyz);
1702 if (iter == mTable.end()) {
1704 child =
new ChildT(xyz, mBackground);
1705 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1709 }
else if (isChild(iter)) {
1710 child = &getChild(iter);
1711 }
else if (on != getTile(iter).active) {
1712 child =
new ChildT(xyz, getTile(iter).value, !on);
1713 setChild(iter, *child);
1716 acc.insert(xyz, child);
1717 child->setActiveStateAndCache(xyz, on, acc);
1722 template<
typename ChildT>
1726 ChildT* child = NULL;
1727 MapIter iter = this->findCoord(xyz);
1728 if (iter == mTable.end()) {
1730 child =
new ChildT(xyz, mBackground);
1731 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1733 }
else if (isChild(iter)) {
1734 child = &getChild(iter);
1736 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1737 setChild(iter, *child);
1739 if (child) child->setValueOff(xyz, value);
1742 template<
typename ChildT>
1743 template<
typename AccessorT>
1747 ChildT* child = NULL;
1748 MapIter iter = this->findCoord(xyz);
1749 if (iter == mTable.end()) {
1751 child =
new ChildT(xyz, mBackground);
1752 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1754 }
else if (isChild(iter)) {
1755 child = &getChild(iter);
1757 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1758 setChild(iter, *child);
1761 acc.insert(xyz, child);
1762 child->setValueOffAndCache(xyz, value, acc);
1767 template<
typename ChildT>
1771 ChildT* child = NULL;
1772 MapIter iter = this->findCoord(xyz);
1773 if (iter == mTable.end()) {
1774 child =
new ChildT(xyz, mBackground);
1775 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1776 }
else if (isChild(iter)) {
1777 child = &getChild(iter);
1779 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1780 setChild(iter, *child);
1782 if (child) child->setValueOn(xyz, value);
1785 template<
typename ChildT>
1786 template<
typename AccessorT>
1790 ChildT* child = NULL;
1791 MapIter iter = this->findCoord(xyz);
1792 if (iter == mTable.end()) {
1793 child =
new ChildT(xyz, mBackground);
1794 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1795 }
else if (isChild(iter)) {
1796 child = &getChild(iter);
1798 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1799 setChild(iter, *child);
1802 acc.insert(xyz, child);
1803 child->setValueAndCache(xyz, value, acc);
1808 template<
typename ChildT>
1812 ChildT* child = NULL;
1813 MapIter iter = this->findCoord(xyz);
1814 if (iter == mTable.end()) {
1815 child =
new ChildT(xyz, mBackground);
1816 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1817 }
else if (isChild(iter)) {
1818 child = &getChild(iter);
1820 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1821 setChild(iter, *child);
1823 if (child) child->setValueOnly(xyz, value);
1826 template<
typename ChildT>
1827 template<
typename AccessorT>
1831 ChildT* child = NULL;
1832 MapIter iter = this->findCoord(xyz);
1833 if (iter == mTable.end()) {
1834 child =
new ChildT(xyz, mBackground);
1835 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1836 }
else if (isChild(iter)) {
1837 child = &getChild(iter);
1839 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1840 setChild(iter, *child);
1843 acc.insert(xyz, child);
1844 child->setValueOnlyAndCache(xyz, value, acc);
1849 template<
typename ChildT>
1850 template<
typename ModifyOp>
1854 ChildT* child = NULL;
1855 MapIter iter = this->findCoord(xyz);
1856 if (iter == mTable.end()) {
1857 child =
new ChildT(xyz, mBackground);
1858 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1859 }
else if (isChild(iter)) {
1860 child = &getChild(iter);
1864 bool createChild = isTileOff(iter);
1868 const ValueType& tileVal = getTile(iter).value;
1874 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1875 setChild(iter, *child);
1878 if (child) child->modifyValue(xyz, op);
1881 template<
typename ChildT>
1882 template<
typename ModifyOp,
typename AccessorT>
1886 ChildT* child = NULL;
1887 MapIter iter = this->findCoord(xyz);
1888 if (iter == mTable.end()) {
1889 child =
new ChildT(xyz, mBackground);
1890 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1891 }
else if (isChild(iter)) {
1892 child = &getChild(iter);
1896 bool createChild = isTileOff(iter);
1900 const ValueType& tileVal = getTile(iter).value;
1906 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1907 setChild(iter, *child);
1911 acc.insert(xyz, child);
1912 child->modifyValueAndCache(xyz, op, acc);
1917 template<
typename ChildT>
1918 template<
typename ModifyOp>
1922 ChildT* child = NULL;
1923 MapIter iter = this->findCoord(xyz);
1924 if (iter == mTable.end()) {
1925 child =
new ChildT(xyz, mBackground);
1926 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1927 }
else if (isChild(iter)) {
1928 child = &getChild(iter);
1930 const Tile& tile = getTile(iter);
1931 bool modifiedState = tile.active;
1933 op(modifiedVal, modifiedState);
1937 child =
new ChildT(xyz, tile.value, tile.active);
1938 setChild(iter, *child);
1941 if (child) child->modifyValueAndActiveState(xyz, op);
1944 template<
typename ChildT>
1945 template<
typename ModifyOp,
typename AccessorT>
1948 const Coord& xyz,
const ModifyOp& op, AccessorT& acc)
1950 ChildT* child = NULL;
1951 MapIter iter = this->findCoord(xyz);
1952 if (iter == mTable.end()) {
1953 child =
new ChildT(xyz, mBackground);
1954 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1955 }
else if (isChild(iter)) {
1956 child = &getChild(iter);
1958 const Tile& tile = getTile(iter);
1959 bool modifiedState = tile.active;
1961 op(modifiedVal, modifiedState);
1965 child =
new ChildT(xyz, tile.value, tile.active);
1966 setChild(iter, *child);
1970 acc.insert(xyz, child);
1971 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
1976 template<
typename ChildT>
1980 MapCIter iter = this->findCoord(xyz);
1981 if (iter == mTable.end()) {
1982 value = mBackground;
1984 }
else if (isChild(iter)) {
1985 return getChild(iter).probeValue(xyz, value);
1987 value = getTile(iter).value;
1988 return isTileOn(iter);
1991 template<
typename ChildT>
1992 template<
typename AccessorT>
1996 MapCIter iter = this->findCoord(xyz);
1997 if (iter == mTable.end()) {
1998 value = mBackground;
2000 }
else if (isChild(iter)) {
2001 acc.insert(xyz, &getChild(iter));
2002 return getChild(iter).probeValueAndCache(xyz, value, acc);
2004 value = getTile(iter).value;
2005 return isTileOn(iter);
2012 template<
typename ChildT>
2016 if (bbox.empty())
return;
2019 for (
int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2021 for (
int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2023 for (
int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2027 Coord tileMin = coordToKey(xyz);
2028 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2030 if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2034 ChildT* child = NULL;
2035 MapIter iter = this->findKey(tileMin);
2036 if (iter == mTable.end()) {
2039 child =
new ChildT(xyz, mBackground);
2040 mTable[tileMin] = NodeStruct(*child);
2041 }
else if (isTile(iter)) {
2044 const Tile& tile = getTile(iter);
2045 child =
new ChildT(xyz, tile.value, tile.active);
2046 mTable[tileMin] = NodeStruct(*child);
2047 }
else if (isChild(iter)) {
2048 child = &getChild(iter);
2059 MapIter iter = this->findOrAddCoord(tileMin);
2060 setTile(iter, Tile(value, active));
2067 template<
typename ChildT>
2068 template<
typename DenseT>
2072 typedef typename DenseT::ValueType DenseValueType;
2074 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2075 const Coord&
min = dense.bbox().min();
2077 for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2078 for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2079 for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2082 nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2087 MapCIter iter = this->findKey(nodeBBox.min());
2088 if (iter != mTable.end() && isChild(iter)) {
2089 getChild(iter).copyToDense(sub, dense);
2091 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2092 sub.translate(-min);
2093 DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2094 for (
Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2095 DenseValueType* a1 = a0 + x*xStride;
2096 for (
Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2097 DenseValueType* a2 = a1 + y*yStride;
2098 for (
Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2099 *a2 = DenseValueType(value);
2112 template<
typename ChildT>
2117 os.write(reinterpret_cast<const char*>(&mBackground),
sizeof(
ValueType));
2120 os.write(reinterpret_cast<const char*>(&truncatedVal),
sizeof(
ValueType));
2124 const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
2125 os.write(reinterpret_cast<const char*>(&numTiles),
sizeof(
Index));
2126 os.write(reinterpret_cast<const char*>(&numChildren),
sizeof(
Index));
2128 if (numTiles == 0 && numChildren == 0)
return false;
2131 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2132 if (isChild(i))
continue;
2133 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
2134 os.write(reinterpret_cast<const char*>(&getTile(i).value),
sizeof(
ValueType));
2135 os.write(reinterpret_cast<const char*>(&getTile(i).active),
sizeof(
bool));
2138 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2139 if (isTile(i))
continue;
2140 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
2141 getChild(i).writeTopology(os, toHalf);
2148 template<
typename ChildT>
2160 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
2162 is.read(reinterpret_cast<char*>(&inside),
sizeof(
ValueType));
2167 Coord rangeMin, rangeMax;
2168 is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 *
sizeof(
Int32));
2169 is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 *
sizeof(
Int32));
2172 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2174 for (
int i = 0; i < 3; ++i) {
2175 offset[i] = rangeMin[i] >> ChildT::TOTAL;
2176 rangeMin[i] = offset[i] << ChildT::TOTAL;
2178 tableSize += log2Dim[i];
2179 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2181 log2Dim[3] = log2Dim[1] + log2Dim[2];
2182 tableSize = 1U << tableSize;
2190 for (
Index i = 0; i < tableSize; ++i) {
2194 origin[0] = (n >> log2Dim[3]) + offset[0];
2195 n &= (1U << log2Dim[3]) - 1;
2196 origin[1] = (n >> log2Dim[2]) + offset[1];
2197 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2198 origin <<= ChildT::TOTAL;
2200 if (childMask.isOn(i)) {
2202 ChildT* child =
new ChildT(origin, mBackground);
2203 child->readTopology(is);
2204 mTable[origin] = NodeStruct(*child);
2209 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
2211 mTable[origin] = NodeStruct(Tile(value, valueMask.
isOn(i)));
2220 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
2223 Index numTiles = 0, numChildren = 0;
2224 is.read(reinterpret_cast<char*>(&numTiles),
sizeof(
Index));
2225 is.read(reinterpret_cast<char*>(&numChildren),
sizeof(
Index));
2227 if (numTiles == 0 && numChildren == 0)
return false;
2234 for (
Index n = 0; n < numTiles; ++n) {
2235 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
2236 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
2237 is.read(reinterpret_cast<char*>(&active),
sizeof(
bool));
2238 mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2242 for (
Index n = 0; n < numChildren; ++n) {
2243 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
2245 ChildT* child =
new ChildT(origin, mBackground);
2246 child->readTopology(is, fromHalf);
2247 mTable[Coord(vec)] = NodeStruct(*child);
2254 template<
typename ChildT>
2258 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2259 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2264 template<
typename ChildT>
2268 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2269 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2277 template<
typename ChildT>
2278 template<
typename PruneOp>
2282 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2283 if (this->isTile(i)|| !op(this->getChild(i)))
continue;
2284 this->setTile(i, Tile(op.value, op.state));
2286 this->eraseBackgroundTiles();
2290 template<
typename ChildT>
2299 template<
typename ChildT>
2308 template<
typename ChildT>
2312 this->pruneInactive(mBackground);
2316 template<
typename ChildT>
2328 template<
typename ChildT>
2329 template<
typename NodeT>
2333 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2334 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2336 MapIter iter = this->findCoord(xyz);
2337 if (iter == mTable.end() || isTile(iter))
return NULL;
2338 return (boost::is_same<NodeT, ChildT>::value)
2339 ?
reinterpret_cast<NodeT*
>(&stealChild(iter, Tile(value, state)))
2340 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2348 template<
typename ChildT>
2352 if (leaf == NULL)
return;
2353 ChildT* child = NULL;
2354 const Coord& xyz = leaf->origin();
2355 MapIter iter = this->findCoord(xyz);
2356 if (iter == mTable.end()) {
2357 if (ChildT::LEVEL>0) {
2358 child =
new ChildT(xyz, mBackground,
false);
2360 child =
reinterpret_cast<ChildT*
>(leaf);
2362 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2363 }
else if (isChild(iter)) {
2364 if (ChildT::LEVEL>0) {
2365 child = &getChild(iter);
2367 child =
reinterpret_cast<ChildT*
>(leaf);
2368 setChild(iter, *child);
2371 if (ChildT::LEVEL>0) {
2372 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2374 child =
reinterpret_cast<ChildT*
>(leaf);
2376 setChild(iter, *child);
2378 child->addLeaf(leaf);
2382 template<
typename ChildT>
2383 template<
typename AccessorT>
2387 if (leaf == NULL)
return;
2388 ChildT* child = NULL;
2389 const Coord& xyz = leaf->origin();
2390 MapIter iter = this->findCoord(xyz);
2391 if (iter == mTable.end()) {
2392 if (ChildT::LEVEL>0) {
2393 child =
new ChildT(xyz, mBackground,
false);
2395 child =
reinterpret_cast<ChildT*
>(leaf);
2397 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2398 }
else if (isChild(iter)) {
2399 if (ChildT::LEVEL>0) {
2400 child = &getChild(iter);
2402 child =
reinterpret_cast<ChildT*
>(leaf);
2403 setChild(iter, *child);
2406 if (ChildT::LEVEL>0) {
2407 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2409 child =
reinterpret_cast<ChildT*
>(leaf);
2411 setChild(iter, *child);
2413 acc.insert(xyz, child);
2414 child->addLeafAndCache(leaf, acc);
2418 template<
typename ChildT>
2423 if (LEVEL >= level) {
2424 MapIter iter = this->findCoord(xyz);
2425 if (iter == mTable.end()) {
2426 if (LEVEL > level) {
2427 ChildT* child =
new ChildT(xyz, mBackground,
false);
2428 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2429 child->addTile(level, xyz, value, state);
2431 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2433 }
else if (isChild(iter)) {
2434 if (LEVEL > level) {
2435 getChild(iter).addTile(level, xyz, value, state);
2437 setTile(iter, Tile(value, state));
2440 if (LEVEL > level) {
2441 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2442 setChild(iter, *child);
2443 child->addTile(level, xyz, value, state);
2445 setTile(iter, Tile(value, state));
2452 template<
typename ChildT>
2453 template<
typename AccessorT>
2456 bool state, AccessorT& acc)
2458 if (LEVEL >= level) {
2459 MapIter iter = this->findCoord(xyz);
2460 if (iter == mTable.end()) {
2461 if (LEVEL > level) {
2462 ChildT* child =
new ChildT(xyz, mBackground,
false);
2463 acc.insert(xyz, child);
2464 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2465 child->addTileAndCache(level, xyz, value, state, acc);
2467 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2469 }
else if (isChild(iter)) {
2470 if (LEVEL > level) {
2471 ChildT* child = &getChild(iter);
2472 acc.insert(xyz, child);
2473 child->addTileAndCache(level, xyz, value, state, acc);
2475 setTile(iter, Tile(value, state));
2478 if (LEVEL > level) {
2479 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2480 acc.insert(xyz, child);
2481 setChild(iter, *child);
2482 child->addTileAndCache(level, xyz, value, state, acc);
2484 setTile(iter, Tile(value, state));
2494 template<
typename ChildT>
2495 inline typename ChildT::LeafNodeType*
2498 ChildT* child = NULL;
2499 MapIter iter = this->findCoord(xyz);
2500 if (iter == mTable.end()) {
2501 child =
new ChildT(xyz, mBackground,
false);
2502 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2503 }
else if (isChild(iter)) {
2504 child = &getChild(iter);
2506 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2507 setChild(iter, *child);
2509 return child->touchLeaf(xyz);
2513 template<
typename ChildT>
2514 template<
typename AccessorT>
2515 inline typename ChildT::LeafNodeType*
2518 ChildT* child = NULL;
2519 MapIter iter = this->findCoord(xyz);
2520 if (iter == mTable.end()) {
2521 child =
new ChildT(xyz, mBackground,
false);
2522 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2523 }
else if (isChild(iter)) {
2524 child = &getChild(iter);
2526 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2527 setChild(iter, *child);
2529 acc.insert(xyz, child);
2530 return child->touchLeafAndCache(xyz, acc);
2537 template<
typename ChildT>
2538 template<
typename NodeT>
2542 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2543 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2545 MapIter iter = this->findCoord(xyz);
2546 if (iter == mTable.end() || isTile(iter))
return NULL;
2547 ChildT* child = &getChild(iter);
2548 return (boost::is_same<NodeT, ChildT>::value)
2549 ?
reinterpret_cast<NodeT*
>(child)
2550 : child->template probeNode<NodeT>(xyz);
2555 template<
typename ChildT>
2556 template<
typename NodeT>
2560 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2561 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2563 MapCIter iter = this->findCoord(xyz);
2564 if (iter == mTable.end() || isTile(iter))
return NULL;
2565 const ChildT* child = &getChild(iter);
2566 return (boost::is_same<NodeT, ChildT>::value)
2567 ?
reinterpret_cast<const NodeT*
>(child)
2568 : child->template probeConstNode<NodeT>(xyz);
2573 template<
typename ChildT>
2574 inline typename ChildT::LeafNodeType*
2577 return this->
template probeNode<LeafNodeType>(xyz);
2581 template<
typename ChildT>
2582 inline const typename ChildT::LeafNodeType*
2585 return this->
template probeConstNode<LeafNodeType>(xyz);
2589 template<
typename ChildT>
2590 template<
typename AccessorT>
2591 inline typename ChildT::LeafNodeType*
2594 return this->
template probeNodeAndCache<LeafNodeType>(xyz, acc);
2598 template<
typename ChildT>
2599 template<
typename AccessorT>
2600 inline const typename ChildT::LeafNodeType*
2603 return this->
template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2607 template<
typename ChildT>
2608 template<
typename AccessorT>
2609 inline const typename ChildT::LeafNodeType*
2612 return this->probeConstLeafAndCache(xyz, acc);
2616 template<
typename ChildT>
2617 template<
typename NodeT,
typename AccessorT>
2621 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2622 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2624 MapIter iter = this->findCoord(xyz);
2625 if (iter == mTable.end() || isTile(iter))
return NULL;
2626 ChildT* child = &getChild(iter);
2627 acc.insert(xyz, child);
2628 return (boost::is_same<NodeT, ChildT>::value)
2629 ?
reinterpret_cast<NodeT*
>(child)
2630 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2635 template<
typename ChildT>
2636 template<
typename NodeT,
typename AccessorT>
2640 if ((NodeT::LEVEL == ChildT::LEVEL && !(boost::is_same<NodeT, ChildT>::value)) ||
2641 NodeT::LEVEL > ChildT::LEVEL)
return NULL;
2643 MapCIter iter = this->findCoord(xyz);
2644 if (iter == mTable.end() || isTile(iter))
return NULL;
2645 const ChildT* child = &getChild(iter);
2646 acc.insert(xyz, child);
2647 return (boost::is_same<NodeT, ChildT>::value)
2648 ?
reinterpret_cast<const NodeT*
>(child)
2649 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2657 template<
typename ChildT>
2665 template<
typename ChildT>
2669 const ValueType zero = zeroVal<ValueType>();
2671 mBackground = outside;
2675 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2676 if (this->isTile(i))
continue;
2677 getChild(i).signedFloodFill(outside, inside);
2678 nodeKeys.insert(i->first);
2684 const Tile insideTile(inside,
false);
2685 CoordSetCIter b = nodeKeys.begin(), e = nodeKeys.end();
2686 if ( b == e )
return;
2687 for (CoordSetCIter a = b++; b != e; ++a, ++b) {
2689 if (d[0]!=0 || d[1]!=0 || d[2]==
Int32(ChildT::DIM))
continue;
2690 MapIter i = mTable.find(*a), j = mTable.find(*b);
2691 const ValueType fill[] = { getChild(i).getLastValue(), getChild(j).getFirstValue() };
2692 if (!(fill[0] < zero) || !(fill[1] < zero))
continue;
2693 for (Coord c = *a + Coord(0u,0u,ChildT::DIM); c[2] != (*b)[2]; c[2] += ChildT::DIM) {
2694 mTable[c] = insideTile;
2703 template<
typename ChildT>
2707 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2708 if (this->isTileOff(i))
continue;
2709 ChildT* child = i->second.child;
2711 child =
new ChildT(i->first, this->getTile(i).value,
true);
2712 i->second.child = child;
2714 child->voxelizeActiveTiles();
2722 template<
typename ChildT>
2723 template<MergePolicy Policy>
2733 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2734 MapIter j = mTable.find(i->first);
2735 if (other.isChild(i)) {
2736 if (j == mTable.end()) {
2737 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2738 child.resetBackground(other.mBackground, mBackground);
2739 mTable[i->first] = NodeStruct(child);
2740 }
else if (isTile(j)) {
2742 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2743 child.resetBackground(other.mBackground, mBackground);
2747 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
2748 other.mBackground, mBackground);
2750 }
else if (other.isTileOn(i)) {
2751 if (j == mTable.end()) {
2752 mTable[i->first] = i->second;
2753 }
else if (!isTileOn(j)) {
2755 setTile(j, Tile(other.getTile(i).value,
true));
2762 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2763 MapIter j = mTable.find(i->first);
2764 if (other.isChild(i)) {
2765 if (j == mTable.end()) {
2766 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2767 child.resetBackground(other.mBackground, mBackground);
2768 mTable[i->first] = NodeStruct(child);
2769 }
else if (isTile(j)) {
2770 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2771 child.resetBackground(other.mBackground, mBackground);
2774 getChild(j).template merge<MERGE_NODES>(
2775 getChild(i), other.mBackground, mBackground);
2782 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2783 MapIter j = mTable.find(i->first);
2784 if (other.isChild(i)) {
2785 if (j == mTable.end()) {
2787 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2788 child.resetBackground(other.mBackground, mBackground);
2789 mTable[i->first] = NodeStruct(child);
2790 }
else if (isTile(j)) {
2792 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2793 child.resetBackground(other.mBackground, mBackground);
2794 const Tile tile = getTile(j);
2798 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2799 tile.value, tile.active);
2803 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
2804 other.mBackground, mBackground);
2806 }
else if (other.isTileOn(i)) {
2807 if (j == mTable.end()) {
2809 mTable[i->first] = i->second;
2810 }
else if (isTileOff(j)) {
2812 setTile(j, Tile(other.getTile(i).value,
true));
2813 }
else if (isChild(j)) {
2815 const Tile& tile = getTile(i);
2816 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
2817 tile.value, tile.active);
2834 template<
typename ChildT>
2835 template<
typename OtherChildType>
2840 typedef typename OtherRootT::MapCIter OtherCIterT;
2842 enforceSameConfiguration(other);
2844 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2845 MapIter j = mTable.find(i->first);
2846 if (other.isChild(i)) {
2847 if (j == mTable.end()) {
2848 mTable[i->first] = NodeStruct(
2849 *(
new ChildT(other.getChild(i), mBackground,
TopologyCopy())));
2850 }
else if (this->isChild(j)) {
2851 this->getChild(j).topologyUnion(other.getChild(i));
2853 ChildT* child =
new ChildT(
2854 other.getChild(i), this->getTile(j).value,
TopologyCopy());
2855 if (this->isTileOn(j)) child->setValuesOn();
2856 this->setChild(j, *child);
2858 }
else if (other.isTileOn(i)) {
2859 if (j == mTable.end()) {
2860 mTable[i->first] = NodeStruct(Tile(mBackground,
true));
2861 }
else if (this->isChild(j)) {
2862 this->getChild(j).setValuesOn();
2863 }
else if (this->isTileOff(j)) {
2864 this->setTile(j, Tile(this->getTile(j).value,
true));
2870 template<
typename ChildT>
2871 template<
typename OtherChildType>
2876 typedef typename OtherRootT::MapCIter OtherCIterT;
2878 enforceSameConfiguration(other);
2880 std::set<Coord> tmp;
2881 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2882 OtherCIterT j = other.mTable.find(i->first);
2883 if (this->isChild(i)) {
2884 if (j == other.mTable.end() || other.isTileOff(j)) {
2885 tmp.insert(i->first);
2886 }
else if (other.isChild(j)) {
2887 this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
2889 }
else if (this->isTileOn(i)) {
2890 if (j == other.mTable.end() || other.isTileOff(j)) {
2891 this->setTile(i, Tile(this->getTile(i).value,
false));
2892 }
else if (other.isChild(j)) {
2894 new ChildT(other.getChild(j), this->getTile(i).value,
TopologyCopy());
2895 this->setChild(i, *child);
2899 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) mTable.erase(*i);
2902 template<
typename ChildT>
2903 template<
typename OtherChildType>
2908 typedef typename OtherRootT::MapCIter OtherCIterT;
2910 enforceSameConfiguration(other);
2912 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2913 MapIter j = mTable.find(i->first);
2914 if (other.isChild(i)) {
2915 if (j == mTable.end() || this->isTileOff(j)) {
2917 }
else if (this->isChild(j)) {
2918 this->getChild(j).topologyDifference(other.getChild(i), mBackground);
2919 }
else if (this->isTileOn(j)) {
2921 ChildT* child =
new ChildT(j->first, this->getTile(j).value,
true);
2922 child->topologyDifference(other.getChild(i), mBackground);
2923 this->setChild(j, *child);
2925 }
else if (other.isTileOn(i)) {
2926 if (j == mTable.end() || this->isTileOff(j)) {
2928 }
else if (this->isChild(j)) {
2929 mTable.erase(j->first);
2930 }
else if (this->isTileOn(j)) {
2931 this->setTile(j, Tile(this->getTile(j).value,
false));
2940 template<
typename ChildT>
2941 template<
typename CombineOp>
2948 this->insertKeys(keys);
2949 other.insertKeys(keys);
2951 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
2952 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
2953 if (isTile(iter) && isTile(otherIter)) {
2956 op(args.
setARef(getTile(iter).value)
2957 .setAIsActive(isTileOn(iter))
2958 .setBRef(getTile(otherIter).value)
2959 .setBIsActive(isTileOn(otherIter)));
2962 }
else if (isChild(iter) && isTile(otherIter)) {
2964 ChildT& child = getChild(iter);
2965 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
2967 }
else if (isTile(iter) && isChild(otherIter)) {
2972 ChildT& child = getChild(otherIter);
2973 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
2976 setChild(iter, stealChild(otherIter, Tile()));
2980 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
2981 child.combine(otherChild, op);
2983 if (prune && isChild(iter)) getChild(iter).prune();
2987 op(args.
setARef(mBackground).setBRef(other.mBackground));
2988 mBackground = args.
result();
3000 template<
typename CombineOp,
typename RootT,
typename OtherRootT,
bool Compatible = false>
3003 static inline void combine2(RootT&
self,
const RootT&,
const OtherRootT& other1,
3008 self.enforceSameConfiguration(other1);
3009 self.enforceCompatibleValueTypes(other1);
3011 std::ostringstream ostr;
3012 ostr <<
"cannot combine a " <<
typeid(OtherRootT).name()
3013 <<
" into a " <<
typeid(RootT).name();
3019 template<
typename CombineOp,
typename RootT,
typename OtherRootT>
3022 static inline void combine2(RootT&
self,
const RootT& other0,
const OtherRootT& other1,
3023 CombineOp& op,
bool prune)
3025 self.doCombine2(other0, other1, op, prune);
3030 template<
typename ChildT>
3031 template<
typename CombineOp,
typename OtherRootNode>
3034 CombineOp& op,
bool prune)
3036 typedef typename OtherRootNode::ValueType OtherValueType;
3040 *
this, other0, other1, op, prune);
3044 template<
typename ChildT>
3045 template<
typename CombineOp,
typename OtherRootNode>
3048 CombineOp& op,
bool prune)
3050 enforceSameConfiguration(other1);
3052 typedef typename OtherRootNode::ValueType OtherValueT;
3053 typedef typename OtherRootNode::Tile OtherTileT;
3054 typedef typename OtherRootNode::NodeStruct OtherNodeStructT;
3055 typedef typename OtherRootNode::MapCIter OtherMapCIterT;
3060 other0.insertKeys(keys);
3061 other1.insertKeys(keys);
3063 const NodeStruct bg0(Tile(other0.mBackground,
false));
3064 const OtherNodeStructT bg1(OtherTileT(other1.mBackground,
false));
3066 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3067 MapIter thisIter = this->findOrAddCoord(*i);
3068 MapCIter iter0 = other0.findKey(*i);
3069 OtherMapCIterT iter1 = other1.findKey(*i);
3070 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3071 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3072 if (ns0.isTile() && ns1.isTile()) {
3075 op(args.
setARef(ns0.tile.value)
3076 .setAIsActive(ns0.isTileOn())
3077 .setBRef(ns1.tile.value)
3078 .setBIsActive(ns1.isTileOn()));
3081 if (!isChild(thisIter)) {
3083 const Coord& childOrigin =
3084 ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3085 setChild(thisIter, *(
new ChildT(childOrigin, getTile(thisIter).value)));
3087 ChildT& child = getChild(thisIter);
3092 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3093 }
else if (ns1.isTile()) {
3096 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3100 child.combine2(*ns0.child, *ns1.child, op);
3103 if (prune && isChild(thisIter)) getChild(thisIter).prune();
3107 op(args.
setARef(other0.mBackground).setBRef(other1.mBackground));
3108 mBackground = args.
result();
3115 template<
typename ChildT>
3116 template<
typename BBoxOp>
3120 const bool descent = op.template descent<LEVEL>();
3121 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3122 if (this->isTileOff(i))
continue;
3123 if (this->isChild(i) && descent) {
3124 this->getChild(i).visitActiveBBox(op);
3127 op.operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3129 op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM));
3136 template<
typename ChildT>
3137 template<
typename VisitorOp>
3141 doVisit<RootNode, VisitorOp, ChildAllIter>(*
this, op);
3145 template<
typename ChildT>
3146 template<
typename VisitorOp>
3150 doVisit<const RootNode, VisitorOp, ChildAllCIter>(*
this, op);
3154 template<
typename ChildT>
3155 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
3159 typename RootNodeT::ValueType val;
3160 for (ChildAllIterT iter =
self.beginChildAll(); iter; ++iter) {
3161 if (op(iter))
continue;
3162 if (
typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
3172 template<
typename ChildT>
3173 template<
typename OtherRootNodeType,
typename VisitorOp>
3178 typename OtherRootNodeType::ChildAllIter>(*
this, other, op);
3182 template<
typename ChildT>
3183 template<
typename OtherRootNodeType,
typename VisitorOp>
3188 typename OtherRootNodeType::ChildAllCIter>(*
this, other, op);
3192 template<
typename ChildT>
3195 typename OtherRootNodeT,
3197 typename ChildAllIterT,
3198 typename OtherChildAllIterT>
3202 enforceSameConfiguration(other);
3204 typename RootNodeT::ValueType val;
3205 typename OtherRootNodeT::ValueType otherVal;
3210 RootNodeT copyOfSelf(
self.mBackground);
3211 copyOfSelf.mTable =
self.mTable;
3212 OtherRootNodeT copyOfOther(other.mBackground);
3213 copyOfOther.mTable = other.mTable;
3217 self.insertKeys(keys);
3218 other.insertKeys(keys);
3219 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3220 copyOfSelf.findOrAddCoord(*i);
3221 copyOfOther.findOrAddCoord(*i);
3224 ChildAllIterT iter = copyOfSelf.beginChildAll();
3225 OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
3227 for ( ; iter && otherIter; ++iter, ++otherIter)
3229 const size_t skipBranch =
static_cast<size_t>(op(iter, otherIter));
3231 typename ChildAllIterT::ChildNodeType* child =
3232 (skipBranch & 1U) ? NULL : iter.probeChild(val);
3233 typename OtherChildAllIterT::ChildNodeType* otherChild =
3234 (skipBranch & 2U) ? NULL : otherIter.probeChild(otherVal);
3236 if (child != NULL && otherChild != NULL) {
3237 child->visit2Node(*otherChild, op);
3238 }
else if (child != NULL) {
3239 child->visit2(otherIter, op);
3240 }
else if (otherChild != NULL) {
3241 otherChild->visit2(iter, op,
true);
3246 copyOfSelf.eraseBackgroundTiles();
3247 copyOfOther.eraseBackgroundTiles();
3251 self.resetTable(copyOfSelf.mTable);
3252 other.resetTable(copyOfOther.mTable);
3259 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
bool resultIsActive() const
Definition: Types.h:314
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
void pruneInactive()
Reduce the memory footprint of this tree by replacing with background tiles any nodes whose values ar...
Definition: RootNode.h:2310
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition: RootNode.h:390
Definition: RootNode.h:63
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1603
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition: RootNode.h:399
bool hasActiveTiles() const
Definition: RootNode.h:1592
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2583
ChildOffIter beginChildOff()
Definition: RootNode.h:409
T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:85
NodeT * probeNodeAndCache(const Coord &xyz, AccessorT &acc)
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2619
ValueOffIter beginValueOff()
Definition: RootNode.h:419
CanConvertType::value is true if a value of type ToType can be constructed from a v...
Definition: Types.h:145
Index32 leafCount() const
Definition: RootNode.h:1484
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition: RootNode.h:392
const NodeT * probeConstNodeAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2638
ChildOnIter beginChildOn()
Definition: RootNode.h:408
ChildType::ValueType ValueType
Definition: RootNode.h:74
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition: RootNode.h:2292
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition: RootNode.h:3003
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: RootNode.h:1639
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of all voxels, both active and inactive, that intersect a given bou...
Definition: RootNode.h:2070
Index64 offVoxelCount() const
Definition: RootNode.h:1526
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition: RootNode.h:2943
bool isValueOn(const Coord &xyz) const
Definition: RootNode.h:1583
void signedFloodFill()
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: RootNode.h:2659
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:303
ChildOnCIter beginChildOn() const
Definition: RootNode.h:405
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition: RootNode.h:396
Index64 onVoxelCount() const
Definition: RootNode.h:1510
~RootNode()
Definition: RootNode.h:152
Index32 Index
Definition: Types.h:57
void pruneOp(PruneOp &)
Definition: RootNode.h:2280
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1947
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
ValueOnIter beginValueOn()
Definition: RootNode.h:418
ChildAllCIter beginChildAll() const
Definition: RootNode.h:407
Index getWidth() const
Definition: RootNode.h:477
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1829
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2385
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition: RootNode.h:1168
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:446
ValueOnCIter beginValueOn() const
Definition: RootNode.h:415
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition: RootNode.h:398
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition: RootNode.h:1279
Index64 offLeafVoxelCount() const
Definition: RootNode.h:1554
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool state)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition: RootNode.h:2331
Helper class for use with Tree::pruneOp() to replace constant branches (to within the provided tolera...
Definition: tree/Util.h:47
ValueConverter::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition: RootNode.h:85
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition: RootNode.h:1371
static Index getChildDim()
Definition: RootNode.h:472
void topologyUnion(const RootNode< OtherChildType > &other)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition: RootNode.h:2837
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2455
ValueOnCIter cbeginValueOn() const
Definition: RootNode.h:412
SameConfiguration::value is true if and only if OtherNodeType is the type of a RootNod...
Definition: RootNode.h:93
const AValueType & result() const
Get the output value.
Definition: Types.h:295
ChildOffCIter cbeginChildOff() const
Definition: RootNode.h:403
Index64 onLeafVoxelCount() const
Definition: RootNode.h:1542
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: RootNode.h:1675
ChildOnCIter cbeginChildOn() const
Definition: RootNode.h:402
void addTile(Index level, const Coord &xyz, const ValueType &value, bool state)
Add a tile containing voxel (x, y, z) at the specified tree level, creating a new branch if necessary...
Definition: RootNode.h:2420
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition: RootNode.h:1190
Index32 nonLeafCount() const
Definition: RootNode.h:1496
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition: RootNode.h:1810
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition: RootNode.h:2725
const ValueType & background() const
Return this node's background value.
Definition: RootNode.h:445
boost::mpl::vector< typename HeadT::ChildNodeType, HeadT >::type Type
Definition: RootNode.h:954
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1884
const NodeT * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2558
void topologyIntersection(const RootNode< OtherChildType > &other)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
Definition: RootNode.h:2873
void visit(VisitorOp &)
Definition: RootNode.h:3139
ChildAllCIter cbeginChildAll() const
Definition: RootNode.h:404
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition: RootNode.h:1104
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:265
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1047
const ValueType & getValue(const Coord &xyz) const
Definition: RootNode.h:1615
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: RootNode.h:1661
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1745
Definition: Exceptions.h:87
uint64_t Index64
Definition: Types.h:56
#define OPENVDB_VERSION_NAME
Definition: version.h:45
ChildType ChildNodeType
Definition: RootNode.h:72
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition: RootNode.h:394
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: RootNode.h:2496
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: RootNode.h:1398
void readBuffers(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2266
RootNode(const RootNode &other)
Definition: RootNode.h:104
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: RootNode.h:2350
Definition: RootNode.h:64
Definition: RootNode.h:69
static Index getLevel()
Definition: RootNode.h:470
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:351
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1788
void load(std::istream &is)
Definition: NodeMasks.h:1216
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:137
Definition: RootNode.h:65
ValueOffCIter cbeginValueOff() const
Definition: RootNode.h:413
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition: RootNode.h:397
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:497
void topologyDifference(const RootNode< OtherChildType > &other)
Difference this tree's set of active values with the active values of the other tree, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this tree and inactive in the other tree.
Definition: RootNode.h:2905
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition: RootNode.h:387
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2256
ChildType::LeafNodeType LeafNodeType
Definition: RootNode.h:73
void pruneTiles(const ValueType &tolerance)
Reduce the memory footprint of this tree by replacing with tiles any non-leaf nodes whose values are ...
Definition: RootNode.h:2318
NodeChain::Type is a boost::mpl::vector that lists the types of th...
Definition: RootNode.h:62
ValueAllIter beginValueAll()
Definition: RootNode.h:420
RootNode< typename ChildType::template ValueConverter< OtherValueType >::Type > Type
Definition: RootNode.h:86
uint32_t Index32
Definition: Types.h:55
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: RootNode.h:1920
int32_t Int32
Definition: Types.h:59
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: RootNode.h:1994
OPENVDB_IMPORT uint32_t getFormatVersion(std::istream &)
Return the file format version number associated with the given input stream.
NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: RootNode.h:947
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition: RootNode.h:1241
bool isOn(Index32 i) const
Definition: NodeMasks.h:1175
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
Helper class for use with Tree::pruneOp() to replace inactive branches with more memory-efficient ina...
Definition: tree/Util.h:74
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2114
void visit2(OtherRootNodeType &other, VisitorOp &)
Definition: RootNode.h:3175
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition: RootNode.h:391
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition: RootNode.h:433
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2540
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition: RootNode.h:3033
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition: RootNode.h:1202
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition: RootNode.h:463
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition: RootNode.h:1264
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Matrix multiplication.
Definition: Mat3.h:608
ValueAllCIter cbeginValueAll() const
Definition: RootNode.h:414
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1649
Definition: NodeMasks.h:911
ChildOffCIter beginChildOff() const
Definition: RootNode.h:406
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition: RootNode.h:1271
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: RootNode.h:1769
Index64 onTileCount() const
Definition: RootNode.h:1565
bool hasSameTopology(const RootNode< OtherChildType > &other) const
Return true if the given tree has the same node and active value topology as this tree (but possibly ...
Definition: RootNode.h:1292
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1065
void visitActiveBBox(BBoxOp &) const
Call the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes i...
Definition: RootNode.h:3118
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition: Vec3.h:454
bool isApproxEqual(const Hermite &lhs, const Hermite &rhs)
Definition: Hermite.h:470
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: RootNode.h:1852
RootNode()
Construct a new tree with a background value of 0.
Definition: RootNode.h:981
void voxelizeActiveTiles()
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: RootNode.h:2705
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition: RootNode.h:395
boost::mpl::push_back< SubtreeT, HeadT >::type Type
Definition: RootNode.h:948
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: RootNode.h:1255
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:107
RootNode(const RootNode< OtherChildType > &other)
Construct a new tree that reproduces the topology and active states of a tree of a different ValueTyp...
Definition: RootNode.h:113
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: RootNode.h:1698
ChildAllIter beginChildAll()
Definition: RootNode.h:410
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
ValueOffCIter beginValueOff() const
Definition: RootNode.h:416
Index getTableSize() const
Return the number of entries in this node's table.
Definition: RootNode.h:475
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition: RootNode.h:388
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition: Compression.h:115
OPENVDB_IMPORT void setGridBackgroundValuePtr(std::ios_base &, const void *background)
Specify (a pointer to) the background value of the grid currently being read from or written to the g...
Index getDepth() const
Definition: RootNode.h:479
Index getHeight() const
Definition: RootNode.h:478
void clear()
Definition: RootNode.h:460
ValueAllCIter beginValueAll() const
Definition: RootNode.h:417
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: RootNode.h:1978
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition: RootNode.h:1339
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given box to a constant value, if necessary subdividing tiles that intersect ...
Definition: RootNode.h:2014
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition: RootNode.h:389
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bbox so it includes the active tiles of this root node as well as all the active...
Definition: RootNode.h:1423
NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. ...
Definition: RootNode.h:79
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition: RootNode.h:3022
void setBackground(const ValueType &value, bool updateChildNodes=true)
Change inactive tiles or voxels with a value equal to +/- the old background to the specified value (...
Definition: RootNode.h:1140
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: RootNode.h:2575
bool readTopology(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2150