8 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
9 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
18 #include <boost/mpl/contains.hpp>
19 #include <boost/mpl/vector.hpp>
20 #include <boost/mpl/at.hpp>
21 #include <boost/mpl/push_back.hpp>
22 #include <boost/mpl/size.hpp>
23 #include <tbb/parallel_for.h>
36 template<
typename HeadType,
int HeadLevel>
struct NodeChain;
42 template<
typename ChildType>
51 static const Index LEVEL = 1 + ChildType::LEVEL;
55 static_assert(boost::mpl::size<NodeChainType>::value == LEVEL + 1,
56 "wrong number of entries in RootNode node chain");
60 template<
typename OtherValueType>
68 template<
typename OtherNodeType>
88 template<
typename OtherChildType>
99 template<
typename OtherChildType>
101 const ValueType& background,
const ValueType& foreground,
TopologyCopy);
113 template<
typename OtherChildType>
125 template<
typename OtherChildType>
132 Tile(): value(
zeroVal<ValueType>()), active(false) {}
133 Tile(
const ValueType& v,
bool b): value(v), active(b) {}
143 NodeStruct(): child(nullptr) {}
144 NodeStruct(ChildType& c): child(&c) {}
145 NodeStruct(
const Tile& t): child(nullptr), tile(t) {}
146 NodeStruct(
const NodeStruct&) =
default;
147 NodeStruct& operator=(
const NodeStruct&) =
default;
150 bool isChild()
const {
return child !=
nullptr; }
151 bool isTile()
const {
return child ==
nullptr; }
152 bool isTileOff()
const {
return isTile() && !tile.active; }
153 bool isTileOn()
const {
return isTile() && tile.active; }
155 void set(ChildType& c) {
delete child; child = &c; }
156 void set(
const Tile& t) {
delete child; child =
nullptr; tile = t; }
157 ChildType& steal(
const Tile& t) { ChildType* c=child; child=
nullptr; tile=t;
return *c; }
160 using MapType = std::map<Coord, NodeStruct>;
161 using MapIter =
typename MapType::iterator;
162 using MapCIter =
typename MapType::const_iterator;
164 using CoordSet = std::set<Coord>;
165 using CoordSetIter =
typename CoordSet::iterator;
166 using CoordSetCIter =
typename CoordSet::const_iterator;
168 static void setTile(
const MapIter& i,
const Tile& t) { i->second.set(t); }
169 static void setChild(
const MapIter& i, ChildType& c) { i->second.set(c); }
170 static Tile& getTile(
const MapIter& i) {
return i->second.tile; }
171 static const Tile& getTile(
const MapCIter& i) {
return i->second.tile; }
172 static ChildType& getChild(
const MapIter& i) {
return *(i->second.child); }
173 static const ChildType& getChild(
const MapCIter& i) {
return *(i->second.child); }
174 static ChildType& stealChild(
const MapIter& i,
const Tile& t) {
return i->second.steal(t);}
175 static const ChildType& stealChild(
const MapCIter& i,
const Tile& t) {
return i->second.steal(t);}
177 static bool isChild(
const MapCIter& i) {
return i->second.isChild(); }
178 static bool isChild(
const MapIter& i) {
return i->second.isChild(); }
179 static bool isTile(
const MapCIter& i) {
return i->second.isTile(); }
180 static bool isTile(
const MapIter& i) {
return i->second.isTile(); }
181 static bool isTileOff(
const MapCIter& i) {
return i->second.isTileOff(); }
182 static bool isTileOff(
const MapIter& i) {
return i->second.isTileOff(); }
183 static bool isTileOn(
const MapCIter& i) {
return i->second.isTileOn(); }
184 static bool isTileOn(
const MapIter& i) {
return i->second.isTileOn(); }
187 static inline bool test(
const MapIter&) {
return true; }
188 static inline bool test(
const MapCIter&) {
return true; }
191 static inline bool test(
const MapIter& i) {
return isTileOn(i); }
192 static inline bool test(
const MapCIter& i) {
return isTileOn(i); }
194 struct ValueOffPred {
195 static inline bool test(
const MapIter& i) {
return isTileOff(i); }
196 static inline bool test(
const MapCIter& i) {
return isTileOff(i); }
198 struct ValueAllPred {
199 static inline bool test(
const MapIter& i) {
return isTile(i); }
200 static inline bool test(
const MapCIter& i) {
return isTile(i); }
203 static inline bool test(
const MapIter& i) {
return isChild(i); }
204 static inline bool test(
const MapCIter& i) {
return isChild(i); }
206 struct ChildOffPred {
207 static inline bool test(
const MapIter& i) {
return isTile(i); }
208 static inline bool test(
const MapCIter& i) {
return isTile(i); }
211 template<
typename _RootNodeT,
typename _MapIterT,
typename FilterPredT>
215 using RootNodeT = _RootNodeT;
216 using MapIterT = _MapIterT;
220 return (mParentNode == other.mParentNode) && (mIter == other.mIter);
222 bool operator!=(
const BaseIter& other)
const {
return !(*
this == other); }
224 RootNodeT* getParentNode()
const {
return mParentNode; }
226 RootNodeT& parent()
const
228 if (!mParentNode)
OPENVDB_THROW(ValueError,
"iterator references a null parent node");
232 bool test()
const { assert(mParentNode);
return mIter != mParentNode->mTable.end(); }
233 operator bool()
const {
return this->test(); }
235 void increment() {
if (this->test()) { ++mIter; } this->skip(); }
236 bool next() { this->increment();
return this->test(); }
237 void increment(
Index n) {
for (
Index i = 0; i < n && this->next(); ++i) {} }
243 return !mParentNode ? 0U :
Index(std::distance(mParentNode->mTable.begin(), mIter));
246 bool isValueOn()
const {
return RootNodeT::isTileOn(mIter); }
247 bool isValueOff()
const {
return RootNodeT::isTileOff(mIter); }
248 void setValueOn(
bool on =
true)
const { mIter->second.tile.active = on; }
249 void setValueOff()
const { mIter->second.tile.active =
false; }
252 Coord getCoord()
const {
return mIter->first; }
254 void getCoord(Coord& xyz)
const { xyz = this->getCoord(); }
257 BaseIter(): mParentNode(nullptr) {}
258 BaseIter(RootNodeT& parent,
const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
260 void skip() {
while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
262 RootNodeT* mParentNode;
266 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ChildNodeT>
267 class ChildIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
270 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
271 using NodeType = RootNodeT;
272 using ValueType = NodeType;
273 using ChildNodeType = ChildNodeT;
274 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
275 using NonConstValueType =
typename std::remove_const<ValueType>::type;
276 using NonConstChildNodeType =
typename std::remove_const<ChildNodeType>::type;
280 ChildIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
282 ChildIter& operator++() { BaseT::increment();
return *
this; }
284 ChildNodeT& getValue()
const {
return getChild(mIter); }
285 ChildNodeT&
operator*()
const {
return this->getValue(); }
286 ChildNodeT* operator->()
const {
return &this->getValue(); }
289 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ValueT>
290 class ValueIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
293 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
294 using NodeType = RootNodeT;
295 using ValueType = ValueT;
296 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
297 using NonConstValueType =
typename std::remove_const<ValueT>::type;
301 ValueIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
303 ValueIter& operator++() { BaseT::increment();
return *
this; }
305 ValueT& getValue()
const {
return getTile(mIter).value; }
306 ValueT&
operator*()
const {
return this->getValue(); }
307 ValueT* operator->()
const {
return &(this->getValue()); }
309 void setValue(
const ValueT& v)
const { assert(isTile(mIter)); getTile(mIter).value = v; }
311 template<
typename ModifyOp>
312 void modifyValue(
const ModifyOp& op)
const
314 assert(isTile(mIter));
315 op(getTile(mIter).value);
319 template<
typename RootNodeT,
typename MapIterT,
typename ChildNodeT,
typename ValueT>
320 class DenseIter:
public BaseIter<RootNodeT, MapIterT, NullPred>
323 using BaseT = BaseIter<RootNodeT, MapIterT, NullPred>;
324 using NodeType = RootNodeT;
325 using ValueType = ValueT;
326 using ChildNodeType = ChildNodeT;
327 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
328 using NonConstValueType =
typename std::remove_const<ValueT>::type;
329 using NonConstChildNodeType =
typename std::remove_const<ChildNodeT>::type;
333 DenseIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) {}
335 DenseIter& operator++() { BaseT::increment();
return *
this; }
337 bool isChildNode()
const {
return isChild(mIter); }
339 ChildNodeT* probeChild(NonConstValueType& value)
const
341 if (isChild(mIter))
return &getChild(mIter);
342 value = getTile(mIter).value;
345 bool probeChild(ChildNodeT*& child, NonConstValueType& value)
const
347 child = this->probeChild(value);
348 return child !=
nullptr;
350 bool probeValue(NonConstValueType& value)
const {
return !this->probeChild(value); }
352 void setChild(ChildNodeT& c)
const { RootNodeT::setChild(mIter, c); }
353 void setChild(ChildNodeT* c)
const { assert(c !=
nullptr); RootNodeT::setChild(mIter, *c); }
354 void setValue(
const ValueT& v)
const
356 if (isTile(mIter)) getTile(mIter).value = v;
360 else stealChild(mIter, Tile(v,
true));
365 using ChildOnIter = ChildIter<RootNode, MapIter, ChildOnPred, ChildType>;
366 using ChildOnCIter = ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>;
367 using ChildOffIter = ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>;
368 using ChildOffCIter = ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>;
369 using ChildAllIter = DenseIter<RootNode, MapIter, ChildType, ValueType>;
370 using ChildAllCIter = DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>;
372 using ValueOnIter = ValueIter<RootNode, MapIter, ValueOnPred, ValueType>;
373 using ValueOnCIter = ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>;
374 using ValueOffIter = ValueIter<RootNode, MapIter, ValueOffPred, ValueType>;
375 using ValueOffCIter = ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>;
376 using ValueAllIter = ValueIter<RootNode, MapIter, ValueAllPred, ValueType>;
377 using ValueAllCIter = ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>;
408 void evalActiveBoundingBox(
CoordBBox& bbox,
bool visitVoxels =
true)
const;
425 void setBackground(
const ValueType& value,
bool updateChildNodes);
431 bool isBackgroundTile(
const Tile&)
const;
433 bool isBackgroundTile(
const MapIter&)
const;
435 bool isBackgroundTile(
const MapCIter&)
const;
439 size_t numBackgroundTiles()
const;
442 size_t eraseBackgroundTiles();
446 bool empty()
const {
return mTable.size() == numBackgroundTiles(); }
451 bool expand(
const Coord& xyz);
454 static void getNodeLog2Dims(std::vector<Index>& dims);
460 Index getWidth()
const {
return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
461 Index getHeight()
const {
return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
462 Index getDepth()
const {
return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
465 Coord getMinIndex()
const;
467 Coord getMaxIndex()
const;
469 void getIndexRange(
CoordBBox& bbox)
const;
473 template<
typename OtherChildType>
477 template<
typename OtherChildType>
482 template<
typename OtherChildType>
489 Index64 onLeafVoxelCount()
const;
490 Index64 offLeafVoxelCount()
const;
492 void nodeCount(std::vector<Index32> &vec)
const;
494 bool isValueOn(
const Coord& xyz)
const;
497 bool hasActiveTiles()
const;
499 const ValueType& getValue(
const Coord& xyz)
const;
500 bool probeValue(
const Coord& xyz, ValueType& value)
const;
505 int getValueDepth(
const Coord& xyz)
const;
508 void setActiveState(
const Coord& xyz,
bool on);
510 void setValueOnly(
const Coord& xyz,
const ValueType& value);
512 void setValueOn(
const Coord& xyz,
const ValueType& value);
514 void setValueOff(
const Coord& xyz);
516 void setValueOff(
const Coord& xyz,
const ValueType& value);
520 template<
typename ModifyOp>
521 void modifyValue(
const Coord& xyz,
const ModifyOp& op);
523 template<
typename ModifyOp>
524 void modifyValueAndActiveState(
const Coord& xyz,
const ModifyOp& op);
527 void fill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
538 this->fill(bbox, value, active);
549 void denseFill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
559 void voxelizeActiveTiles(
bool threaded =
true);
566 template<
typename DenseT>
573 bool writeTopology(std::ostream&,
bool toHalf =
false)
const;
574 bool readTopology(std::istream&,
bool fromHalf =
false);
576 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
577 void readBuffers(std::istream&,
bool fromHalf =
false);
578 void readBuffers(std::istream&,
const CoordBBox&,
bool fromHalf =
false);
588 template<
typename AccessorT>
594 template<
typename AccessorT>
595 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
601 template<
typename AccessorT>
602 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
608 template<
typename AccessorT>
609 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
616 template<
typename ModifyOp,
typename AccessorT>
617 void modifyValueAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
623 template<
typename ModifyOp,
typename AccessorT>
624 void modifyValueAndActiveStateAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
630 template<
typename AccessorT>
631 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
637 template<
typename AccessorT>
638 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
645 template<
typename AccessorT>
646 bool probeValueAndCache(
const Coord& xyz,
ValueType& value, AccessorT&)
const;
653 template<
typename AccessorT>
654 int getValueDepthAndCache(
const Coord& xyz, AccessorT&)
const;
672 template<
typename AccessorT>
683 template<
typename NodeT>
684 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool state);
691 bool addChild(ChildType* child);
695 void addTile(
const Coord& xyz,
const ValueType& value,
bool state);
704 template<
typename AccessorT>
705 void addTileAndCache(
Index level,
const Coord& xyz,
const ValueType&,
bool state, AccessorT&);
716 template<
typename AccessorT>
720 template <
typename NodeT>
723 NodeT* probeNode(
const Coord& xyz);
724 template <
typename NodeT>
725 const NodeT* probeConstNode(
const Coord& xyz)
const;
729 template<
typename NodeT,
typename AccessorT>
732 NodeT* probeNodeAndCache(
const Coord& xyz, AccessorT& acc);
733 template<
typename NodeT,
typename AccessorT>
734 const NodeT* probeConstNodeAndCache(
const Coord& xyz, AccessorT& acc)
const;
746 template<
typename AccessorT>
750 template<
typename AccessorT>
752 template<
typename AccessorT>
762 template<
typename ArrayT>
void getNodes(ArrayT& array);
785 template<
typename ArrayT>
void getNodes(ArrayT& array)
const;
789 template<
typename ArrayT>
813 void stealNodes(ArrayT& array,
const ValueType& value,
bool state);
814 template<
typename ArrayT>
825 template<MergePolicy Policy>
void merge(
RootNode& other);
840 template<
typename OtherChildType>
856 template<
typename OtherChildType>
869 template<
typename OtherChildType>
872 template<
typename CombineOp>
873 void combine(
RootNode& other, CombineOp&,
bool prune =
false);
875 template<
typename CombineOp,
typename OtherRootNode >
876 void combine2(
const RootNode& other0,
const OtherRootNode& other1,
877 CombineOp& op,
bool prune =
false);
884 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
886 template<
typename VisitorOp>
void visit(VisitorOp&);
887 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
889 template<
typename OtherRootNodeType,
typename VisitorOp>
890 void visit2(OtherRootNodeType& other, VisitorOp&);
891 template<
typename OtherRootNodeType,
typename VisitorOp>
892 void visit2(OtherRootNodeType& other, VisitorOp&)
const;
905 void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
907 void resetTable(
const MapType&)
const {}
910 Index getChildCount()
const;
911 Index getTileCount()
const;
912 Index getActiveTileCount()
const;
913 Index getInactiveTileCount()
const;
916 static Coord coordToKey(
const Coord& xyz) {
return xyz & ~(ChildType::DIM - 1); }
919 void insertKeys(CoordSet&)
const;
922 bool hasKey(
const Coord& key)
const {
return mTable.find(key) != mTable.end(); }
924 MapIter findKey(
const Coord& key) {
return mTable.find(key); }
927 MapCIter findKey(
const Coord& key)
const {
return mTable.find(key); }
930 MapIter findCoord(
const Coord& xyz) {
return mTable.find(coordToKey(xyz)); }
933 MapCIter findCoord(
const Coord& xyz)
const {
return mTable.find(coordToKey(xyz)); }
935 MapIter findOrAddCoord(
const Coord& xyz);
944 template<
typename OtherChildType>
945 static void enforceSameConfiguration(
const RootNode<OtherChildType>& other);
952 template<
typename OtherChildType>
953 static void enforceCompatibleValueTypes(
const RootNode<OtherChildType>& other);
955 template<
typename CombineOp,
typename OtherRootNode >
956 void doCombine2(
const RootNode&,
const OtherRootNode&, CombineOp&,
bool prune);
958 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
959 static inline void doVisit(RootNodeT&, VisitorOp&);
961 template<
typename RootNodeT,
typename OtherRootNodeT,
typename VisitorOp,
962 typename ChildAllIterT,
typename OtherChildAllIterT>
963 static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
967 ValueType mBackground;
994 template<
typename HeadT,
int HeadLevel>
997 using Type =
typename boost::mpl::push_back<SubtreeT, HeadT>::type;
1001 template<
typename HeadT>
1003 using Type =
typename boost::mpl::vector<typename HeadT::ChildNodeType, HeadT>::type;
1011 template<
typename ChildT1,
typename NodeT2>
1015 static const bool value =
false;
1018 template<
typename ChildT1,
typename ChildT2>
1020 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1028 template<
typename ChildT>
1036 template<
typename ChildT>
1044 template<
typename ChildT>
1045 template<
typename OtherChildType>
1053 enforceSameConfiguration(other);
1055 const Tile bgTile(backgd,
false), fgTile(foregd,
true);
1058 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1059 mTable[i->first] = OtherRootT::isTile(i)
1060 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1061 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd, foregd,
TopologyCopy())));
1066 template<
typename ChildT>
1067 template<
typename OtherChildType>
1075 enforceSameConfiguration(other);
1077 const Tile bgTile(backgd,
false), fgTile(backgd,
true);
1079 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1080 mTable[i->first] = OtherRootT::isTile(i)
1081 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1082 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd,
TopologyCopy())));
1093 template<
typename RootT,
typename OtherRootT,
bool Compatible = false>
1100 self.enforceSameConfiguration(other);
1101 self.enforceCompatibleValueTypes(other);
1103 std::ostringstream ostr;
1104 ostr <<
"cannot convert a " <<
typeid(OtherRootT).name()
1105 <<
" to a " <<
typeid(RootT).name();
1111 template<
typename RootT,
typename OtherRootT>
1116 using ValueT =
typename RootT::ValueType;
1117 using ChildT =
typename RootT::ChildNodeType;
1118 using NodeStruct =
typename RootT::NodeStruct;
1119 using Tile =
typename RootT::Tile;
1120 using OtherValueT =
typename OtherRootT::ValueType;
1121 using OtherMapCIter =
typename OtherRootT::MapCIter;
1122 using OtherTile =
typename OtherRootT::Tile;
1126 static inline ValueT convertValue(
const OtherValueT& val) {
return ValueT(val); }
1129 self.mBackground = Local::convertValue(other.mBackground);
1134 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1135 if (other.isTile(i)) {
1137 const OtherTile& otherTile = other.getTile(i);
1138 self.mTable[i->first] = NodeStruct(
1139 Tile(Local::convertValue(otherTile.value), otherTile.active));
1142 self.mTable[i->first] = NodeStruct(*(
new ChildT(other.getChild(i))));
1150 template<
typename ChildT>
1151 inline RootNode<ChildT>&
1154 if (&other !=
this) {
1155 mBackground = other.mBackground;
1160 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1162 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(
new ChildT(getChild(i))));
1169 template<
typename ChildT>
1170 template<
typename OtherChildType>
1175 using OtherValueT =
typename OtherRootT::ValueType;
1185 template<
typename ChildT>
1191 if (updateChildNodes) {
1194 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1195 ChildT *child = iter->second.child;
1197 child->resetBackground(mBackground, background);
1199 Tile& tile = getTile(iter);
1200 if (tile.active)
continue;
1202 tile.value = background;
1209 mBackground = background;
1212 template<
typename ChildT>
1219 template<
typename ChildT>
1226 template<
typename ChildT>
1234 template<
typename ChildT>
1239 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1240 if (this->isBackgroundTile(i)) ++count;
1246 template<
typename ChildT>
1250 std::set<Coord> keysToErase;
1251 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1252 if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1254 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1257 return keysToErase.size();
1264 template<
typename ChildT>
1268 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1269 keys.insert(i->first);
1274 template<
typename ChildT>
1275 inline typename RootNode<ChildT>::MapIter
1276 RootNode<ChildT>::findOrAddCoord(
const Coord& xyz)
1278 const Coord key = coordToKey(xyz);
1279 std::pair<MapIter, bool> result = mTable.insert(
1280 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1281 return result.first;
1285 template<
typename ChildT>
1289 const Coord key = coordToKey(xyz);
1290 std::pair<MapIter, bool> result = mTable.insert(
1291 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1292 return result.second;
1299 template<
typename ChildT>
1304 ChildT::getNodeLog2Dims(dims);
1308 template<
typename ChildT>
1312 return mTable.empty() ?
Coord(0) : mTable.begin()->first;
1315 template<
typename ChildT>
1319 return mTable.empty() ?
Coord(0) : mTable.rbegin()->first +
Coord(ChildT::DIM - 1);
1323 template<
typename ChildT>
1327 bbox.
min() = this->getMinIndex();
1328 bbox.
max() = this->getMaxIndex();
1335 template<
typename ChildT>
1336 template<
typename OtherChildType>
1341 using OtherMapT =
typename OtherRootT::MapType;
1342 using OtherIterT =
typename OtherRootT::MapIter;
1343 using OtherCIterT =
typename OtherRootT::MapCIter;
1345 if (!hasSameConfiguration(other))
return false;
1348 OtherMapT copyOfOtherTable = other.mTable;
1351 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1352 if (this->isBackgroundTile(thisIter))
continue;
1355 OtherCIterT otherIter = other.findKey(thisIter->first);
1356 if (otherIter == other.mTable.end())
return false;
1359 if (isChild(thisIter)) {
1360 if (OtherRootT::isTile(otherIter))
return false;
1362 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter)))
return false;
1364 if (OtherRootT::isChild(otherIter))
return false;
1365 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active)
return false;
1372 copyOfOtherTable.erase(otherIter->first);
1375 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1382 template<
typename ChildT>
1383 template<
typename OtherChildType>
1387 std::vector<Index> thisDims, otherDims;
1390 return (thisDims == otherDims);
1394 template<
typename ChildT>
1395 template<
typename OtherChildType>
1399 std::vector<Index> thisDims, otherDims;
1402 if (thisDims != otherDims) {
1403 std::ostringstream ostr;
1404 ostr <<
"grids have incompatible configurations (" << thisDims[0];
1405 for (
size_t i = 1, N = thisDims.size(); i < N; ++i) ostr <<
" x " << thisDims[i];
1406 ostr <<
" vs. " << otherDims[0];
1407 for (
size_t i = 1, N = otherDims.size(); i < N; ++i) ostr <<
" x " << otherDims[i];
1414 template<
typename ChildT>
1415 template<
typename OtherChildType>
1419 using OtherValueType =
typename OtherChildType::ValueType;
1424 template<
typename ChildT>
1425 template<
typename OtherChildType>
1429 using OtherValueType =
typename OtherChildType::ValueType;
1431 std::ostringstream ostr;
1432 ostr <<
"values of type " << typeNameAsString<OtherValueType>()
1433 <<
" cannot be converted to type " << typeNameAsString<ValueType>();
1442 template<
typename ChildT>
1447 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1448 if (
const ChildT *child = iter->second.child) {
1449 sum += child->memUsage();
1456 template<
typename ChildT>
1460 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1461 delete i->second.child;
1467 template<
typename ChildT>
1471 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1472 if (
const ChildT *child = iter->second.child) {
1473 child->evalActiveBoundingBox(bbox, visitVoxels);
1474 }
else if (isTileOn(iter)) {
1475 bbox.
expand(iter->first, ChildT::DIM);
1481 template<
typename ChildT>
1485 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1486 if (isChild(i)) ++sum;
1492 template<
typename ChildT>
1494 RootNode<ChildT>::getTileCount()
const
1497 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1498 if (isTile(i)) ++sum;
1504 template<
typename ChildT>
1506 RootNode<ChildT>::getActiveTileCount()
const
1509 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1510 if (isTileOn(i)) ++sum;
1516 template<
typename ChildT>
1518 RootNode<ChildT>::getInactiveTileCount()
const
1521 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1522 if (isTileOff(i)) ++sum;
1528 template<
typename ChildT>
1533 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1534 if (isChild(i)) sum += getChild(i).leafCount();
1540 template<
typename ChildT>
1545 if (ChildT::LEVEL != 0) {
1546 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1547 if (isChild(i)) sum += getChild(i).nonLeafCount();
1554 template<
typename ChildT>
1559 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1561 sum += getChild(i).onVoxelCount();
1562 }
else if (isTileOn(i)) {
1563 sum += ChildT::NUM_VOXELS;
1570 template<
typename ChildT>
1575 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1577 sum += getChild(i).offVoxelCount();
1578 }
else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1579 sum += ChildT::NUM_VOXELS;
1586 template<
typename ChildT>
1591 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1592 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1598 template<
typename ChildT>
1603 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1604 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1609 template<
typename ChildT>
1614 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1616 sum += getChild(i).onTileCount();
1617 }
else if (isTileOn(i)) {
1624 template<
typename ChildT>
1628 assert(vec.size() > LEVEL);
1630 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1633 getChild(i).nodeCount(vec);
1637 vec[ChildNodeType::LEVEL] = sum;
1643 template<
typename ChildT>
1647 MapCIter iter = this->findCoord(xyz);
1648 if (iter == mTable.end() || isTileOff(iter))
return false;
1649 return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1652 template<
typename ChildT>
1656 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1657 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active)
return true;
1662 template<
typename ChildT>
1663 template<
typename AccessorT>
1667 MapCIter iter = this->findCoord(xyz);
1668 if (iter == mTable.end() || isTileOff(iter))
return false;
1669 if (isTileOn(iter))
return true;
1670 acc.insert(xyz, &getChild(iter));
1671 return getChild(iter).isValueOnAndCache(xyz, acc);
1675 template<
typename ChildT>
1676 inline const typename ChildT::ValueType&
1679 MapCIter iter = this->findCoord(xyz);
1680 return iter == mTable.end() ? mBackground
1681 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1684 template<
typename ChildT>
1685 template<
typename AccessorT>
1686 inline const typename ChildT::ValueType&
1689 MapCIter iter = this->findCoord(xyz);
1690 if (iter == mTable.end())
return mBackground;
1691 if (isChild(iter)) {
1692 acc.insert(xyz, &getChild(iter));
1693 return getChild(iter).getValueAndCache(xyz, acc);
1695 return getTile(iter).value;
1699 template<
typename ChildT>
1703 MapCIter iter = this->findCoord(xyz);
1704 return iter == mTable.end() ? -1
1705 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1708 template<
typename ChildT>
1709 template<
typename AccessorT>
1713 MapCIter iter = this->findCoord(xyz);
1714 if (iter == mTable.end())
return -1;
1715 if (isTile(iter))
return 0;
1716 acc.insert(xyz, &getChild(iter));
1717 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1721 template<
typename ChildT>
1725 MapIter iter = this->findCoord(xyz);
1726 if (iter != mTable.end() && !isTileOff(iter)) {
1727 if (isTileOn(iter)) {
1728 setChild(iter, *
new ChildT(xyz, getTile(iter).value,
true));
1730 getChild(iter).setValueOff(xyz);
1735 template<
typename ChildT>
1739 ChildT* child =
nullptr;
1740 MapIter iter = this->findCoord(xyz);
1741 if (iter == mTable.end()) {
1743 child =
new ChildT(xyz, mBackground);
1744 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1748 }
else if (isChild(iter)) {
1749 child = &getChild(iter);
1750 }
else if (on != getTile(iter).active) {
1751 child =
new ChildT(xyz, getTile(iter).value, !on);
1752 setChild(iter, *child);
1754 if (child) child->setActiveState(xyz, on);
1757 template<
typename ChildT>
1758 template<
typename AccessorT>
1762 ChildT* child =
nullptr;
1763 MapIter iter = this->findCoord(xyz);
1764 if (iter == mTable.end()) {
1766 child =
new ChildT(xyz, mBackground);
1767 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1771 }
else if (isChild(iter)) {
1772 child = &getChild(iter);
1773 }
else if (on != getTile(iter).active) {
1774 child =
new ChildT(xyz, getTile(iter).value, !on);
1775 setChild(iter, *child);
1778 acc.insert(xyz, child);
1779 child->setActiveStateAndCache(xyz, on, acc);
1784 template<
typename ChildT>
1788 ChildT* child =
nullptr;
1789 MapIter iter = this->findCoord(xyz);
1790 if (iter == mTable.end()) {
1792 child =
new ChildT(xyz, mBackground);
1793 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);
1801 if (child) child->setValueOff(xyz, value);
1804 template<
typename ChildT>
1805 template<
typename AccessorT>
1809 ChildT* child =
nullptr;
1810 MapIter iter = this->findCoord(xyz);
1811 if (iter == mTable.end()) {
1813 child =
new ChildT(xyz, mBackground);
1814 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1816 }
else if (isChild(iter)) {
1817 child = &getChild(iter);
1819 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1820 setChild(iter, *child);
1823 acc.insert(xyz, child);
1824 child->setValueOffAndCache(xyz, value, acc);
1829 template<
typename ChildT>
1833 ChildT* child =
nullptr;
1834 MapIter iter = this->findCoord(xyz);
1835 if (iter == mTable.end()) {
1836 child =
new ChildT(xyz, mBackground);
1837 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1838 }
else if (isChild(iter)) {
1839 child = &getChild(iter);
1841 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1842 setChild(iter, *child);
1844 if (child) child->setValueOn(xyz, value);
1847 template<
typename ChildT>
1848 template<
typename AccessorT>
1852 ChildT* child =
nullptr;
1853 MapIter iter = this->findCoord(xyz);
1854 if (iter == mTable.end()) {
1855 child =
new ChildT(xyz, mBackground);
1856 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1857 }
else if (isChild(iter)) {
1858 child = &getChild(iter);
1860 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1861 setChild(iter, *child);
1864 acc.insert(xyz, child);
1865 child->setValueAndCache(xyz, value, acc);
1870 template<
typename ChildT>
1874 ChildT* child =
nullptr;
1875 MapIter iter = this->findCoord(xyz);
1876 if (iter == mTable.end()) {
1877 child =
new ChildT(xyz, mBackground);
1878 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1879 }
else if (isChild(iter)) {
1880 child = &getChild(iter);
1882 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1883 setChild(iter, *child);
1885 if (child) child->setValueOnly(xyz, value);
1888 template<
typename ChildT>
1889 template<
typename AccessorT>
1893 ChildT* child =
nullptr;
1894 MapIter iter = this->findCoord(xyz);
1895 if (iter == mTable.end()) {
1896 child =
new ChildT(xyz, mBackground);
1897 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1898 }
else if (isChild(iter)) {
1899 child = &getChild(iter);
1901 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1902 setChild(iter, *child);
1905 acc.insert(xyz, child);
1906 child->setValueOnlyAndCache(xyz, value, acc);
1911 template<
typename ChildT>
1912 template<
typename ModifyOp>
1916 ChildT* child =
nullptr;
1917 MapIter iter = this->findCoord(xyz);
1918 if (iter == mTable.end()) {
1919 child =
new ChildT(xyz, mBackground);
1920 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1921 }
else if (isChild(iter)) {
1922 child = &getChild(iter);
1926 bool createChild = isTileOff(iter);
1930 const ValueType& tileVal = getTile(iter).value;
1936 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1937 setChild(iter, *child);
1940 if (child) child->modifyValue(xyz, op);
1943 template<
typename ChildT>
1944 template<
typename ModifyOp,
typename AccessorT>
1948 ChildT* child =
nullptr;
1949 MapIter iter = this->findCoord(xyz);
1950 if (iter == mTable.end()) {
1951 child =
new ChildT(xyz, mBackground);
1952 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1953 }
else if (isChild(iter)) {
1954 child = &getChild(iter);
1958 bool createChild = isTileOff(iter);
1962 const ValueType& tileVal = getTile(iter).value;
1968 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1969 setChild(iter, *child);
1973 acc.insert(xyz, child);
1974 child->modifyValueAndCache(xyz, op, acc);
1979 template<
typename ChildT>
1980 template<
typename ModifyOp>
1984 ChildT* child =
nullptr;
1985 MapIter iter = this->findCoord(xyz);
1986 if (iter == mTable.end()) {
1987 child =
new ChildT(xyz, mBackground);
1988 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1989 }
else if (isChild(iter)) {
1990 child = &getChild(iter);
1992 const Tile& tile = getTile(iter);
1993 bool modifiedState = tile.active;
1995 op(modifiedVal, modifiedState);
1999 child =
new ChildT(xyz, tile.value, tile.active);
2000 setChild(iter, *child);
2003 if (child) child->modifyValueAndActiveState(xyz, op);
2006 template<
typename ChildT>
2007 template<
typename ModifyOp,
typename AccessorT>
2010 const Coord& xyz,
const ModifyOp& op, AccessorT& acc)
2012 ChildT* child =
nullptr;
2013 MapIter iter = this->findCoord(xyz);
2014 if (iter == mTable.end()) {
2015 child =
new ChildT(xyz, mBackground);
2016 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2017 }
else if (isChild(iter)) {
2018 child = &getChild(iter);
2020 const Tile& tile = getTile(iter);
2021 bool modifiedState = tile.active;
2023 op(modifiedVal, modifiedState);
2027 child =
new ChildT(xyz, tile.value, tile.active);
2028 setChild(iter, *child);
2032 acc.insert(xyz, child);
2033 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2038 template<
typename ChildT>
2042 MapCIter iter = this->findCoord(xyz);
2043 if (iter == mTable.end()) {
2044 value = mBackground;
2046 }
else if (isChild(iter)) {
2047 return getChild(iter).probeValue(xyz, value);
2049 value = getTile(iter).value;
2050 return isTileOn(iter);
2053 template<
typename ChildT>
2054 template<
typename AccessorT>
2058 MapCIter iter = this->findCoord(xyz);
2059 if (iter == mTable.end()) {
2060 value = mBackground;
2062 }
else if (isChild(iter)) {
2063 acc.insert(xyz, &getChild(iter));
2064 return getChild(iter).probeValueAndCache(xyz, value, acc);
2066 value = getTile(iter).value;
2067 return isTileOn(iter);
2074 template<
typename ChildT>
2078 if (bbox.
empty())
return;
2083 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
2085 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
2087 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
2091 Coord tileMin = coordToKey(xyz);
2092 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
2098 ChildT* child =
nullptr;
2099 MapIter iter = this->findKey(tileMin);
2100 if (iter == mTable.end()) {
2103 child =
new ChildT(xyz, mBackground);
2104 mTable[tileMin] = NodeStruct(*child);
2105 }
else if (isTile(iter)) {
2108 const Tile& tile = getTile(iter);
2109 child =
new ChildT(xyz, tile.value, tile.active);
2110 mTable[tileMin] = NodeStruct(*child);
2111 }
else if (isChild(iter)) {
2112 child = &getChild(iter);
2117 child->fill(
CoordBBox(xyz, tmp), value, active);
2123 MapIter iter = this->findOrAddCoord(tileMin);
2124 setTile(iter, Tile(value, active));
2132 template<
typename ChildT>
2136 if (bbox.
empty())
return;
2138 if (active && mTable.empty()) {
2141 sparseFill(bbox, value, active);
2142 voxelizeActiveTiles(
true);
2148 Coord xyz, tileMin, tileMax;
2149 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
2151 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
2153 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
2157 tileMin = coordToKey(xyz);
2158 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
2162 const auto iter = findOrAddCoord(tileMin);
2167 const auto& tile = getTile(iter);
2168 auto* child =
new ChildT{tileMin, tile.value, tile.active};
2169 setChild(iter, *child);
2172 getChild(iter).denseFill(bbox, value, active);
2182 template<
typename ChildT>
2190 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2191 if (this->isTileOff(i))
continue;
2192 ChildT* child = i->second.child;
2193 if (child ==
nullptr) {
2196 child =
new ChildT{i->first, this->getTile(i).value,
true};
2197 i->second.child = child;
2199 child->voxelizeActiveTiles(threaded);
2207 template<
typename ChildT>
2208 template<
typename DenseT>
2212 using DenseValueType =
typename DenseT::ValueType;
2214 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2215 const Coord&
min = dense.bbox().min();
2217 for (
Coord xyz = bbox.
min(); xyz[0] <= bbox.
max()[0]; xyz[0] = nodeBBox.
max()[0] + 1) {
2218 for (xyz[1] = bbox.
min()[1]; xyz[1] <= bbox.
max()[1]; xyz[1] = nodeBBox.
max()[1] + 1) {
2219 for (xyz[2] = bbox.
min()[2]; xyz[2] <= bbox.
max()[2]; xyz[2] = nodeBBox.
max()[2] + 1) {
2227 MapCIter iter = this->findKey(nodeBBox.
min());
2228 if (iter != mTable.end() && isChild(iter)) {
2229 getChild(iter).copyToDense(sub, dense);
2231 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2233 DenseValueType* a0 = dense.data() + zStride*sub.
min()[2];
2234 for (
Int32 x=sub.
min()[0], ex=sub.
max()[0]+1; x<ex; ++x) {
2235 DenseValueType* a1 = a0 + x*xStride;
2236 for (
Int32 y=sub.
min()[1], ey=sub.
max()[1]+1; y<ey; ++y) {
2237 DenseValueType* a2 = a1 + y*yStride;
2238 for (
Int32 z=sub.
min()[2], ez=sub.
max()[2]+1; z<ez; ++z, a2 += zStride) {
2239 *a2 = DenseValueType(value);
2252 template<
typename ChildT>
2257 os.write(
reinterpret_cast<const char*
>(&mBackground),
sizeof(
ValueType));
2260 os.write(
reinterpret_cast<const char*
>(&truncatedVal),
sizeof(
ValueType));
2264 const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
2265 os.write(
reinterpret_cast<const char*
>(&numTiles),
sizeof(
Index));
2266 os.write(
reinterpret_cast<const char*
>(&numChildren),
sizeof(
Index));
2268 if (numTiles == 0 && numChildren == 0)
return false;
2271 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2272 if (isChild(i))
continue;
2273 os.write(
reinterpret_cast<const char*
>(i->first.asPointer()), 3 *
sizeof(
Int32));
2274 os.write(
reinterpret_cast<const char*
>(&getTile(i).value),
sizeof(
ValueType));
2275 os.write(
reinterpret_cast<const char*
>(&getTile(i).active),
sizeof(
bool));
2278 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2279 if (isTile(i))
continue;
2280 os.write(
reinterpret_cast<const char*
>(i->first.asPointer()), 3 *
sizeof(
Int32));
2281 getChild(i).writeTopology(os, toHalf);
2288 template<
typename ChildT>
2300 is.read(
reinterpret_cast<char*
>(&mBackground),
sizeof(
ValueType));
2302 is.read(
reinterpret_cast<char*
>(&inside),
sizeof(
ValueType));
2307 Coord rangeMin, rangeMax;
2309 is.read(
reinterpret_cast<char*
>(rangeMax.
asPointer()), 3 *
sizeof(
Int32));
2312 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2314 for (
int i = 0; i < 3; ++i) {
2315 offset[i] = rangeMin[i] >> ChildT::TOTAL;
2316 rangeMin[i] = offset[i] << ChildT::TOTAL;
2318 tableSize += log2Dim[i];
2319 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2321 log2Dim[3] = log2Dim[1] + log2Dim[2];
2322 tableSize = 1U << tableSize;
2330 for (
Index i = 0; i < tableSize; ++i) {
2334 origin[0] = (n >> log2Dim[3]) + offset[0];
2335 n &= (1U << log2Dim[3]) - 1;
2336 origin[1] = (n >> log2Dim[2]) + offset[1];
2337 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2338 origin <<= ChildT::TOTAL;
2340 if (childMask.isOn(i)) {
2342 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2343 child->readTopology(is);
2344 mTable[origin] = NodeStruct(*child);
2349 is.read(
reinterpret_cast<char*
>(&value),
sizeof(
ValueType));
2351 mTable[origin] = NodeStruct(Tile(value, valueMask.
isOn(i)));
2360 is.read(
reinterpret_cast<char*
>(&mBackground),
sizeof(
ValueType));
2363 Index numTiles = 0, numChildren = 0;
2364 is.read(
reinterpret_cast<char*
>(&numTiles),
sizeof(
Index));
2365 is.read(
reinterpret_cast<char*
>(&numChildren),
sizeof(
Index));
2367 if (numTiles == 0 && numChildren == 0)
return false;
2374 for (
Index n = 0; n < numTiles; ++n) {
2375 is.read(
reinterpret_cast<char*
>(vec), 3 *
sizeof(
Int32));
2376 is.read(
reinterpret_cast<char*
>(&value),
sizeof(
ValueType));
2377 is.read(
reinterpret_cast<char*
>(&active),
sizeof(
bool));
2378 mTable[
Coord(vec)] = NodeStruct(Tile(value, active));
2382 for (
Index n = 0; n < numChildren; ++n) {
2383 is.read(
reinterpret_cast<char*
>(vec), 3 *
sizeof(
Int32));
2385 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2386 child->readTopology(is, fromHalf);
2387 mTable[
Coord(vec)] = NodeStruct(*child);
2394 template<
typename ChildT>
2398 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2399 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2404 template<
typename ChildT>
2408 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2409 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2414 template<
typename ChildT>
2418 const Tile bgTile(mBackground,
false);
2420 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2426 ChildT& child = getChild(i);
2427 child.readBuffers(is, clipBBox, fromHalf);
2431 this->
clip(clipBBox);
2438 template<
typename ChildT>
2442 const Tile bgTile(mBackground,
false);
2446 MapType copyOfTable(mTable);
2447 for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2448 const Coord& xyz = i->first;
2452 setTile(this->findCoord(xyz), bgTile);
2454 }
else if (!clipBBox.
isInside(tileBBox)) {
2458 getChild(i).clip(clipBBox, mBackground);
2463 const Tile& origTile = getTile(i);
2464 setTile(this->findCoord(xyz), bgTile);
2465 this->sparseFill(tileBBox, origTile.value, origTile.active);
2478 template<
typename ChildT>
2484 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2485 if (this->isTile(i))
continue;
2486 this->getChild(i).prune(tolerance);
2487 if (this->getChild(i).isConstant(value, state, tolerance)) {
2488 this->setTile(i, Tile(value, state));
2491 this->eraseBackgroundTiles();
2498 template<
typename ChildT>
2499 template<
typename NodeT>
2503 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2504 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2506 MapIter iter = this->findCoord(xyz);
2507 if (iter == mTable.end() || isTile(iter))
return nullptr;
2508 return (std::is_same<NodeT, ChildT>::value)
2509 ?
reinterpret_cast<NodeT*
>(&stealChild(iter, Tile(value, state)))
2510 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2518 template<
typename ChildT>
2522 if (leaf ==
nullptr)
return;
2523 ChildT* child =
nullptr;
2524 const Coord& xyz = leaf->origin();
2525 MapIter iter = this->findCoord(xyz);
2526 if (iter == mTable.end()) {
2527 if (ChildT::LEVEL>0) {
2528 child =
new ChildT(xyz, mBackground,
false);
2530 child =
reinterpret_cast<ChildT*
>(leaf);
2532 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2533 }
else if (isChild(iter)) {
2534 if (ChildT::LEVEL>0) {
2535 child = &getChild(iter);
2537 child =
reinterpret_cast<ChildT*
>(leaf);
2538 setChild(iter, *child);
2541 if (ChildT::LEVEL>0) {
2542 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2544 child =
reinterpret_cast<ChildT*
>(leaf);
2546 setChild(iter, *child);
2548 child->addLeaf(leaf);
2552 template<
typename ChildT>
2553 template<
typename AccessorT>
2557 if (leaf ==
nullptr)
return;
2558 ChildT* child =
nullptr;
2559 const Coord& xyz = leaf->origin();
2560 MapIter iter = this->findCoord(xyz);
2561 if (iter == mTable.end()) {
2562 if (ChildT::LEVEL>0) {
2563 child =
new ChildT(xyz, mBackground,
false);
2565 child =
reinterpret_cast<ChildT*
>(leaf);
2567 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2568 }
else if (isChild(iter)) {
2569 if (ChildT::LEVEL>0) {
2570 child = &getChild(iter);
2572 child =
reinterpret_cast<ChildT*
>(leaf);
2573 setChild(iter, *child);
2576 if (ChildT::LEVEL>0) {
2577 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2579 child =
reinterpret_cast<ChildT*
>(leaf);
2581 setChild(iter, *child);
2583 acc.insert(xyz, child);
2584 child->addLeafAndCache(leaf, acc);
2587 template<
typename ChildT>
2591 if (!child)
return false;
2592 const Coord& xyz = child->origin();
2593 MapIter iter = this->findCoord(xyz);
2594 if (iter == mTable.end()) {
2595 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2597 setChild(iter, *child);
2602 template<
typename ChildT>
2606 MapIter iter = this->findCoord(xyz);
2607 if (iter == mTable.end()) {
2608 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2610 setTile(iter, Tile(value, state));
2614 template<
typename ChildT>
2619 if (LEVEL >= level) {
2620 MapIter iter = this->findCoord(xyz);
2621 if (iter == mTable.end()) {
2622 if (LEVEL > level) {
2623 ChildT* child =
new ChildT(xyz, mBackground,
false);
2624 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2625 child->addTile(level, xyz, value, state);
2627 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2629 }
else if (isChild(iter)) {
2630 if (LEVEL > level) {
2631 getChild(iter).addTile(level, xyz, value, state);
2633 setTile(iter, Tile(value, state));
2636 if (LEVEL > level) {
2637 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2638 setChild(iter, *child);
2639 child->addTile(level, xyz, value, state);
2641 setTile(iter, Tile(value, state));
2648 template<
typename ChildT>
2649 template<
typename AccessorT>
2652 bool state, AccessorT& acc)
2654 if (LEVEL >= level) {
2655 MapIter iter = this->findCoord(xyz);
2656 if (iter == mTable.end()) {
2657 if (LEVEL > level) {
2658 ChildT* child =
new ChildT(xyz, mBackground,
false);
2659 acc.insert(xyz, child);
2660 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2661 child->addTileAndCache(level, xyz, value, state, acc);
2663 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2665 }
else if (isChild(iter)) {
2666 if (LEVEL > level) {
2667 ChildT* child = &getChild(iter);
2668 acc.insert(xyz, child);
2669 child->addTileAndCache(level, xyz, value, state, acc);
2671 setTile(iter, Tile(value, state));
2674 if (LEVEL > level) {
2675 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2676 acc.insert(xyz, child);
2677 setChild(iter, *child);
2678 child->addTileAndCache(level, xyz, value, state, acc);
2680 setTile(iter, Tile(value, state));
2690 template<
typename ChildT>
2691 inline typename ChildT::LeafNodeType*
2694 ChildT* child =
nullptr;
2695 MapIter iter = this->findCoord(xyz);
2696 if (iter == mTable.end()) {
2697 child =
new ChildT(xyz, mBackground,
false);
2698 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2699 }
else if (isChild(iter)) {
2700 child = &getChild(iter);
2702 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2703 setChild(iter, *child);
2705 return child->touchLeaf(xyz);
2709 template<
typename ChildT>
2710 template<
typename AccessorT>
2711 inline typename ChildT::LeafNodeType*
2714 ChildT* child =
nullptr;
2715 MapIter iter = this->findCoord(xyz);
2716 if (iter == mTable.end()) {
2717 child =
new ChildT(xyz, mBackground,
false);
2718 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2719 }
else if (isChild(iter)) {
2720 child = &getChild(iter);
2722 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2723 setChild(iter, *child);
2725 acc.insert(xyz, child);
2726 return child->touchLeafAndCache(xyz, acc);
2733 template<
typename ChildT>
2734 template<
typename NodeT>
2738 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2739 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2741 MapIter iter = this->findCoord(xyz);
2742 if (iter == mTable.end() || isTile(iter))
return nullptr;
2743 ChildT* child = &getChild(iter);
2744 return (std::is_same<NodeT, ChildT>::value)
2745 ?
reinterpret_cast<NodeT*
>(child)
2746 : child->template probeNode<NodeT>(xyz);
2751 template<
typename ChildT>
2752 template<
typename NodeT>
2756 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2757 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2759 MapCIter iter = this->findCoord(xyz);
2760 if (iter == mTable.end() || isTile(iter))
return nullptr;
2761 const ChildT* child = &getChild(iter);
2762 return (std::is_same<NodeT, ChildT>::value)
2763 ?
reinterpret_cast<const NodeT*
>(child)
2764 : child->template probeConstNode<NodeT>(xyz);
2769 template<
typename ChildT>
2770 inline typename ChildT::LeafNodeType*
2773 return this->
template probeNode<LeafNodeType>(xyz);
2777 template<
typename ChildT>
2778 inline const typename ChildT::LeafNodeType*
2781 return this->
template probeConstNode<LeafNodeType>(xyz);
2785 template<
typename ChildT>
2786 template<
typename AccessorT>
2787 inline typename ChildT::LeafNodeType*
2790 return this->
template probeNodeAndCache<LeafNodeType>(xyz, acc);
2794 template<
typename ChildT>
2795 template<
typename AccessorT>
2796 inline const typename ChildT::LeafNodeType*
2799 return this->
template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2803 template<
typename ChildT>
2804 template<
typename AccessorT>
2805 inline const typename ChildT::LeafNodeType*
2808 return this->probeConstLeafAndCache(xyz, acc);
2812 template<
typename ChildT>
2813 template<
typename NodeT,
typename AccessorT>
2817 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2818 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2820 MapIter iter = this->findCoord(xyz);
2821 if (iter == mTable.end() || isTile(iter))
return nullptr;
2822 ChildT* child = &getChild(iter);
2823 acc.insert(xyz, child);
2824 return (std::is_same<NodeT, ChildT>::value)
2825 ?
reinterpret_cast<NodeT*
>(child)
2826 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2831 template<
typename ChildT>
2832 template<
typename NodeT,
typename AccessorT>
2836 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2837 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2839 MapCIter iter = this->findCoord(xyz);
2840 if (iter == mTable.end() || isTile(iter))
return nullptr;
2841 const ChildT* child = &getChild(iter);
2842 acc.insert(xyz, child);
2843 return (std::is_same<NodeT, ChildT>::value)
2844 ?
reinterpret_cast<const NodeT*
>(child)
2845 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2852 template<
typename ChildT>
2853 template<
typename ArrayT>
2857 using NodePtr =
typename ArrayT::value_type;
2858 static_assert(std::is_pointer<NodePtr>::value,
2859 "argument to getNodes() must be a pointer array");
2860 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2861 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2862 using result =
typename boost::mpl::contains<NodeChainType, NonConstNodeType>::type;
2863 static_assert(result::value,
"can't extract non-const nodes from a const tree");
2864 using ArrayChildT =
typename std::conditional<
2865 std::is_const<NodeType>::value,
const ChildT, ChildT>::type;
2867 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2868 if (ChildT* child = iter->second.child) {
2870 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2871 array.push_back(
reinterpret_cast<NodePtr
>(iter->second.child));
2873 child->getNodes(array);
2880 template<
typename ChildT>
2881 template<
typename ArrayT>
2885 using NodePtr =
typename ArrayT::value_type;
2886 static_assert(std::is_pointer<NodePtr>::value,
2887 "argument to getNodes() must be a pointer array");
2888 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2889 static_assert(std::is_const<NodeType>::value,
2890 "argument to getNodes() must be an array of const node pointers");
2891 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2892 using result =
typename boost::mpl::contains<NodeChainType, NonConstNodeType>::type;
2893 static_assert(result::value,
"can't extract non-const nodes from a const tree");
2895 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2898 if (std::is_same<NodePtr, const ChildT*>::value) {
2899 array.push_back(
reinterpret_cast<NodePtr
>(iter->second.child));
2901 child->getNodes(array);
2910 template<
typename ChildT>
2911 template<
typename ArrayT>
2915 using NodePtr =
typename ArrayT::value_type;
2916 static_assert(std::is_pointer<NodePtr>::value,
2917 "argument to stealNodes() must be a pointer array");
2918 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2919 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2920 using result =
typename boost::mpl::contains<NodeChainType, NonConstNodeType>::type;
2921 static_assert(result::value,
"can't extract non-const nodes from a const tree");
2922 using ArrayChildT =
typename std::conditional<
2923 std::is_const<NodeType>::value,
const ChildT, ChildT>::type;
2925 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2926 if (ChildT* child = iter->second.child) {
2928 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2929 array.push_back(
reinterpret_cast<NodePtr
>(&stealChild(iter, Tile(value, state))));
2931 child->stealNodes(array, value, state);
2942 template<
typename ChildT>
2943 template<MergePolicy Policy>
2953 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2954 MapIter j = mTable.find(i->first);
2955 if (other.isChild(i)) {
2956 if (j == mTable.end()) {
2957 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2958 child.resetBackground(other.mBackground, mBackground);
2959 mTable[i->first] = NodeStruct(child);
2960 }
else if (isTile(j)) {
2962 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2963 child.resetBackground(other.mBackground, mBackground);
2967 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
2968 other.mBackground, mBackground);
2970 }
else if (other.isTileOn(i)) {
2971 if (j == mTable.end()) {
2972 mTable[i->first] = i->second;
2973 }
else if (!isTileOn(j)) {
2975 setTile(j, Tile(other.getTile(i).value,
true));
2982 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2983 MapIter j = mTable.find(i->first);
2984 if (other.isChild(i)) {
2985 if (j == mTable.end()) {
2986 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2987 child.resetBackground(other.mBackground, mBackground);
2988 mTable[i->first] = NodeStruct(child);
2989 }
else if (isTile(j)) {
2990 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2991 child.resetBackground(other.mBackground, mBackground);
2994 getChild(j).template merge<MERGE_NODES>(
2995 getChild(i), other.mBackground, mBackground);
3002 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3003 MapIter j = mTable.find(i->first);
3004 if (other.isChild(i)) {
3005 if (j == mTable.end()) {
3007 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3008 child.resetBackground(other.mBackground, mBackground);
3009 mTable[i->first] = NodeStruct(child);
3010 }
else if (isTile(j)) {
3012 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3013 child.resetBackground(other.mBackground, mBackground);
3014 const Tile tile = getTile(j);
3018 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3019 tile.value, tile.active);
3023 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
3024 other.mBackground, mBackground);
3026 }
else if (other.isTileOn(i)) {
3027 if (j == mTable.end()) {
3029 mTable[i->first] = i->second;
3030 }
else if (isTileOff(j)) {
3032 setTile(j, Tile(other.getTile(i).value,
true));
3033 }
else if (isChild(j)) {
3035 const Tile& tile = getTile(i);
3036 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3037 tile.value, tile.active);
3054 template<
typename ChildT>
3055 template<
typename OtherChildType>
3060 using OtherCIterT =
typename OtherRootT::MapCIter;
3062 enforceSameConfiguration(other);
3064 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3065 MapIter j = mTable.find(i->first);
3066 if (other.isChild(i)) {
3067 if (j == mTable.end()) {
3068 mTable[i->first] = NodeStruct(
3069 *(
new ChildT(other.getChild(i), mBackground,
TopologyCopy())));
3070 }
else if (this->isChild(j)) {
3071 this->getChild(j).topologyUnion(other.getChild(i));
3073 ChildT* child =
new ChildT(
3074 other.getChild(i), this->getTile(j).value,
TopologyCopy());
3075 if (this->isTileOn(j)) child->setValuesOn();
3076 this->setChild(j, *child);
3078 }
else if (other.isTileOn(i)) {
3079 if (j == mTable.end()) {
3080 mTable[i->first] = NodeStruct(Tile(mBackground,
true));
3081 }
else if (this->isChild(j)) {
3082 this->getChild(j).setValuesOn();
3083 }
else if (this->isTileOff(j)) {
3084 this->setTile(j, Tile(this->getTile(j).value,
true));
3090 template<
typename ChildT>
3091 template<
typename OtherChildType>
3096 using OtherCIterT =
typename OtherRootT::MapCIter;
3098 enforceSameConfiguration(other);
3100 std::set<Coord> tmp;
3101 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3102 OtherCIterT j = other.mTable.find(i->first);
3103 if (this->isChild(i)) {
3104 if (j == other.mTable.end() || other.isTileOff(j)) {
3105 tmp.insert(i->first);
3106 }
else if (other.isChild(j)) {
3107 this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3109 }
else if (this->isTileOn(i)) {
3110 if (j == other.mTable.end() || other.isTileOff(j)) {
3111 this->setTile(i, Tile(this->getTile(i).value,
false));
3112 }
else if (other.isChild(j)) {
3114 new ChildT(other.getChild(j), this->getTile(i).value,
TopologyCopy());
3115 this->setChild(i, *child);
3119 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3120 MapIter it = this->findCoord(*i);
3121 setTile(it, Tile());
3126 template<
typename ChildT>
3127 template<
typename OtherChildType>
3132 using OtherCIterT =
typename OtherRootT::MapCIter;
3134 enforceSameConfiguration(other);
3136 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3137 MapIter j = mTable.find(i->first);
3138 if (other.isChild(i)) {
3139 if (j == mTable.end() || this->isTileOff(j)) {
3141 }
else if (this->isChild(j)) {
3142 this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3143 }
else if (this->isTileOn(j)) {
3145 ChildT* child =
new ChildT(j->first, this->getTile(j).value,
true);
3146 child->topologyDifference(other.getChild(i), mBackground);
3147 this->setChild(j, *child);
3149 }
else if (other.isTileOn(i)) {
3150 if (j == mTable.end() || this->isTileOff(j)) {
3152 }
else if (this->isChild(j)) {
3155 }
else if (this->isTileOn(j)) {
3156 this->setTile(j, Tile(this->getTile(j).value,
false));
3165 template<
typename ChildT>
3166 template<
typename CombineOp>
3173 this->insertKeys(keys);
3174 other.insertKeys(keys);
3176 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3177 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3178 if (isTile(iter) && isTile(otherIter)) {
3181 op(args.
setARef(getTile(iter).value)
3182 .setAIsActive(isTileOn(iter))
3183 .setBRef(getTile(otherIter).value)
3184 .setBIsActive(isTileOn(otherIter)));
3187 }
else if (isChild(iter) && isTile(otherIter)) {
3189 ChildT& child = getChild(iter);
3190 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3192 }
else if (isTile(iter) && isChild(otherIter)) {
3197 ChildT& child = getChild(otherIter);
3198 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3201 setChild(iter, stealChild(otherIter, Tile()));
3205 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3206 child.combine(otherChild, op);
3208 if (
prune && isChild(iter)) getChild(iter).prune();
3212 op(args.
setARef(mBackground).setBRef(other.mBackground));
3213 mBackground = args.
result();
3225 template<
typename CombineOp,
typename RootT,
typename OtherRootT,
bool Compatible = false>
3228 static inline void combine2(RootT&
self,
const RootT&,
const OtherRootT& other1,
3233 self.enforceSameConfiguration(other1);
3234 self.enforceCompatibleValueTypes(other1);
3236 std::ostringstream ostr;
3237 ostr <<
"cannot combine a " <<
typeid(OtherRootT).name()
3238 <<
" into a " <<
typeid(RootT).name();
3244 template<
typename CombineOp,
typename RootT,
typename OtherRootT>
3247 static inline void combine2(RootT&
self,
const RootT& other0,
const OtherRootT& other1,
3248 CombineOp& op,
bool prune)
3250 self.doCombine2(other0, other1, op,
prune);
3255 template<
typename ChildT>
3256 template<
typename CombineOp,
typename OtherRootNode>
3259 CombineOp& op,
bool prune)
3261 using OtherValueType =
typename OtherRootNode::ValueType;
3265 *
this, other0, other1, op,
prune);
3269 template<
typename ChildT>
3270 template<
typename CombineOp,
typename OtherRootNode>
3273 CombineOp& op,
bool prune)
3275 enforceSameConfiguration(other1);
3277 using OtherValueT =
typename OtherRootNode::ValueType;
3278 using OtherTileT =
typename OtherRootNode::Tile;
3279 using OtherNodeStructT =
typename OtherRootNode::NodeStruct;
3280 using OtherMapCIterT =
typename OtherRootNode::MapCIter;
3285 other0.insertKeys(keys);
3286 other1.insertKeys(keys);
3288 const NodeStruct bg0(Tile(other0.mBackground,
false));
3289 const OtherNodeStructT bg1(OtherTileT(other1.mBackground,
false));
3291 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3292 MapIter thisIter = this->findOrAddCoord(*i);
3293 MapCIter iter0 = other0.findKey(*i);
3294 OtherMapCIterT iter1 = other1.findKey(*i);
3295 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3296 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3297 if (ns0.isTile() && ns1.isTile()) {
3300 op(args.
setARef(ns0.tile.value)
3301 .setAIsActive(ns0.isTileOn())
3302 .setBRef(ns1.tile.value)
3303 .setBIsActive(ns1.isTileOn()));
3306 if (!isChild(thisIter)) {
3308 const Coord& childOrigin =
3309 ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3310 setChild(thisIter, *(
new ChildT(childOrigin, getTile(thisIter).value)));
3312 ChildT& child = getChild(thisIter);
3317 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3318 }
else if (ns1.isTile()) {
3321 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3325 child.combine2(*ns0.child, *ns1.child, op);
3328 if (
prune && isChild(thisIter)) getChild(thisIter).prune();
3332 op(args.
setARef(other0.mBackground).setBRef(other1.mBackground));
3333 mBackground = args.
result();
3340 template<
typename ChildT>
3341 template<
typename BBoxOp>
3345 const bool descent = op.template descent<LEVEL>();
3346 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3347 if (this->isTileOff(i))
continue;
3348 if (this->isChild(i) && descent) {
3349 this->getChild(i).visitActiveBBox(op);
3361 template<
typename ChildT>
3362 template<
typename VisitorOp>
3366 doVisit<RootNode, VisitorOp, ChildAllIter>(*
this, op);
3370 template<
typename ChildT>
3371 template<
typename VisitorOp>
3375 doVisit<const RootNode, VisitorOp, ChildAllCIter>(*
this, op);
3379 template<
typename ChildT>
3380 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
3384 typename RootNodeT::ValueType val;
3385 for (ChildAllIterT iter =
self.beginChildAll(); iter; ++iter) {
3386 if (op(iter))
continue;
3387 if (
typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
3397 template<
typename ChildT>
3398 template<
typename OtherRootNodeType,
typename VisitorOp>
3403 typename OtherRootNodeType::ChildAllIter>(*
this, other, op);
3407 template<
typename ChildT>
3408 template<
typename OtherRootNodeType,
typename VisitorOp>
3413 typename OtherRootNodeType::ChildAllCIter>(*
this, other, op);
3417 template<
typename ChildT>
3420 typename OtherRootNodeT,
3422 typename ChildAllIterT,
3423 typename OtherChildAllIterT>
3427 enforceSameConfiguration(other);
3429 typename RootNodeT::ValueType val;
3430 typename OtherRootNodeT::ValueType otherVal;
3435 RootNodeT copyOfSelf(
self.mBackground);
3436 copyOfSelf.mTable =
self.mTable;
3437 OtherRootNodeT copyOfOther(other.mBackground);
3438 copyOfOther.mTable = other.mTable;
3442 self.insertKeys(keys);
3443 other.insertKeys(keys);
3444 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3445 copyOfSelf.findOrAddCoord(*i);
3446 copyOfOther.findOrAddCoord(*i);
3449 ChildAllIterT iter = copyOfSelf.beginChildAll();
3450 OtherChildAllIterT otherIter = copyOfOther.beginChildAll();
3452 for ( ; iter && otherIter; ++iter, ++otherIter)
3454 const size_t skipBranch =
static_cast<size_t>(op(iter, otherIter));
3456 typename ChildAllIterT::ChildNodeType* child =
3457 (skipBranch & 1U) ?
nullptr : iter.probeChild(val);
3458 typename OtherChildAllIterT::ChildNodeType* otherChild =
3459 (skipBranch & 2U) ?
nullptr : otherIter.probeChild(otherVal);
3461 if (child !=
nullptr && otherChild !=
nullptr) {
3462 child->visit2Node(*otherChild, op);
3463 }
else if (child !=
nullptr) {
3464 child->visit2(otherIter, op);
3465 }
else if (otherChild !=
nullptr) {
3466 otherChild->visit2(iter, op,
true);
3471 copyOfSelf.eraseBackgroundTiles();
3472 copyOfOther.eraseBackgroundTiles();
3476 self.resetTable(copyOfSelf.mTable);
3477 other.resetTable(copyOfOther.mTable);
3484 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED