8 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
9 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED
18 #include <tbb/parallel_for.h>
31 template<
typename HeadType,
int HeadLevel>
struct NodeChain;
32 template<
typename,
typename>
struct SameRootConfig;
33 template<
typename,
typename,
bool>
struct RootNodeCopyHelper;
34 template<
typename,
typename,
typename,
bool>
struct RootNodeCombineHelper;
37 template<
typename ChildType>
46 static const Index LEVEL = 1 + ChildType::LEVEL;
50 static_assert(NodeChainType::Size == LEVEL + 1,
51 "wrong number of entries in RootNode node chain");
55 template<
typename OtherValueType>
63 template<
typename OtherNodeType>
83 template<
typename OtherChildType>
94 template<
typename OtherChildType>
96 const ValueType& background,
const ValueType& foreground,
TopologyCopy);
108 template<
typename OtherChildType>
120 template<
typename OtherChildType>
127 Tile(): value(
zeroVal<ValueType>()), active(false) {}
128 Tile(
const ValueType& v,
bool b): value(v), active(b) {}
138 NodeStruct(): child(nullptr) {}
139 NodeStruct(ChildType& c): child(&c) {}
140 NodeStruct(
const Tile& t): child(nullptr), tile(t) {}
141 NodeStruct(
const NodeStruct&) =
default;
142 NodeStruct& operator=(
const NodeStruct&) =
default;
145 bool isChild()
const {
return child !=
nullptr; }
146 bool isTile()
const {
return child ==
nullptr; }
147 bool isTileOff()
const {
return isTile() && !tile.active; }
148 bool isTileOn()
const {
return isTile() && tile.active; }
150 void set(ChildType& c) {
delete child; child = &c; }
151 void set(
const Tile& t) {
delete child; child =
nullptr; tile = t; }
152 ChildType& steal(
const Tile& t) { ChildType* c=child; child=
nullptr; tile=t;
return *c; }
155 using MapType = std::map<Coord, NodeStruct>;
156 using MapIter =
typename MapType::iterator;
157 using MapCIter =
typename MapType::const_iterator;
159 using CoordSet = std::set<Coord>;
160 using CoordSetIter =
typename CoordSet::iterator;
161 using CoordSetCIter =
typename CoordSet::const_iterator;
163 static void setTile(
const MapIter& i,
const Tile& t) { i->second.set(t); }
164 static void setChild(
const MapIter& i, ChildType& c) { i->second.set(c); }
165 static Tile& getTile(
const MapIter& i) {
return i->second.tile; }
166 static const Tile& getTile(
const MapCIter& i) {
return i->second.tile; }
167 static ChildType& getChild(
const MapIter& i) {
return *(i->second.child); }
168 static const ChildType& getChild(
const MapCIter& i) {
return *(i->second.child); }
169 static ChildType& stealChild(
const MapIter& i,
const Tile& t) {
return i->second.steal(t);}
170 static const ChildType& stealChild(
const MapCIter& i,
const Tile& t) {
return i->second.steal(t);}
172 static bool isChild(
const MapCIter& i) {
return i->second.isChild(); }
173 static bool isChild(
const MapIter& i) {
return i->second.isChild(); }
174 static bool isTile(
const MapCIter& i) {
return i->second.isTile(); }
175 static bool isTile(
const MapIter& i) {
return i->second.isTile(); }
176 static bool isTileOff(
const MapCIter& i) {
return i->second.isTileOff(); }
177 static bool isTileOff(
const MapIter& i) {
return i->second.isTileOff(); }
178 static bool isTileOn(
const MapCIter& i) {
return i->second.isTileOn(); }
179 static bool isTileOn(
const MapIter& i) {
return i->second.isTileOn(); }
182 static inline bool test(
const MapIter&) {
return true; }
183 static inline bool test(
const MapCIter&) {
return true; }
186 static inline bool test(
const MapIter& i) {
return isTileOn(i); }
187 static inline bool test(
const MapCIter& i) {
return isTileOn(i); }
189 struct ValueOffPred {
190 static inline bool test(
const MapIter& i) {
return isTileOff(i); }
191 static inline bool test(
const MapCIter& i) {
return isTileOff(i); }
193 struct ValueAllPred {
194 static inline bool test(
const MapIter& i) {
return isTile(i); }
195 static inline bool test(
const MapCIter& i) {
return isTile(i); }
198 static inline bool test(
const MapIter& i) {
return isChild(i); }
199 static inline bool test(
const MapCIter& i) {
return isChild(i); }
201 struct ChildOffPred {
202 static inline bool test(
const MapIter& i) {
return isTile(i); }
203 static inline bool test(
const MapCIter& i) {
return isTile(i); }
206 template<
typename _RootNodeT,
typename _MapIterT,
typename FilterPredT>
210 using RootNodeT = _RootNodeT;
211 using MapIterT = _MapIterT;
215 return (mParentNode == other.mParentNode) && (mIter == other.mIter);
217 bool operator!=(
const BaseIter& other)
const {
return !(*
this == other); }
219 RootNodeT* getParentNode()
const {
return mParentNode; }
221 RootNodeT& parent()
const
223 if (!mParentNode)
OPENVDB_THROW(ValueError,
"iterator references a null parent node");
227 bool test()
const { assert(mParentNode);
return mIter != mParentNode->mTable.end(); }
228 operator bool()
const {
return this->test(); }
230 void increment() {
if (this->test()) { ++mIter; } this->skip(); }
231 bool next() { this->increment();
return this->test(); }
232 void increment(
Index n) {
for (
Index i = 0; i < n && this->next(); ++i) {} }
238 return !mParentNode ? 0U :
Index(std::distance(mParentNode->mTable.begin(), mIter));
241 bool isValueOn()
const {
return RootNodeT::isTileOn(mIter); }
242 bool isValueOff()
const {
return RootNodeT::isTileOff(mIter); }
243 void setValueOn(
bool on =
true)
const { mIter->second.tile.active = on; }
244 void setValueOff()
const { mIter->second.tile.active =
false; }
247 Coord getCoord()
const {
return mIter->first; }
249 void getCoord(Coord& xyz)
const { xyz = this->getCoord(); }
252 BaseIter(): mParentNode(nullptr) {}
253 BaseIter(RootNodeT& parent,
const MapIterT& iter): mParentNode(&parent), mIter(iter) {}
255 void skip() {
while (this->test() && !FilterPredT::test(mIter)) ++mIter; }
257 RootNodeT* mParentNode;
261 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ChildNodeT>
262 class ChildIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
265 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
266 using NodeType = RootNodeT;
267 using ValueType = NodeType;
268 using ChildNodeType = ChildNodeT;
275 ChildIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
277 ChildIter& operator++() { BaseT::increment();
return *
this; }
279 ChildNodeT& getValue()
const {
return getChild(mIter); }
280 ChildNodeT&
operator*()
const {
return this->getValue(); }
281 ChildNodeT* operator->()
const {
return &this->getValue(); }
284 template<
typename RootNodeT,
typename MapIterT,
typename FilterPredT,
typename ValueT>
285 class ValueIter:
public BaseIter<RootNodeT, MapIterT, FilterPredT>
288 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>;
289 using NodeType = RootNodeT;
290 using ValueType = ValueT;
296 ValueIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); }
298 ValueIter& operator++() { BaseT::increment();
return *
this; }
300 ValueT& getValue()
const {
return getTile(mIter).value; }
301 ValueT&
operator*()
const {
return this->getValue(); }
302 ValueT* operator->()
const {
return &(this->getValue()); }
304 void setValue(
const ValueT& v)
const { assert(isTile(mIter)); getTile(mIter).value = v; }
306 template<
typename ModifyOp>
307 void modifyValue(
const ModifyOp& op)
const
309 assert(isTile(mIter));
310 op(getTile(mIter).value);
314 template<
typename RootNodeT,
typename MapIterT,
typename ChildNodeT,
typename ValueT>
315 class DenseIter:
public BaseIter<RootNodeT, MapIterT, NullPred>
318 using BaseT = BaseIter<RootNodeT, MapIterT, NullPred>;
319 using NodeType = RootNodeT;
320 using ValueType = ValueT;
321 using ChildNodeType = ChildNodeT;
328 DenseIter(RootNodeT& parent,
const MapIterT& iter): BaseT(parent, iter) {}
330 DenseIter& operator++() { BaseT::increment();
return *
this; }
332 bool isChildNode()
const {
return isChild(mIter); }
334 ChildNodeT* probeChild(NonConstValueType& value)
const
336 if (isChild(mIter))
return &getChild(mIter);
337 value = getTile(mIter).value;
340 bool probeChild(ChildNodeT*& child, NonConstValueType& value)
const
342 child = this->probeChild(value);
343 return child !=
nullptr;
345 bool probeValue(NonConstValueType& value)
const {
return !this->probeChild(value); }
347 void setChild(ChildNodeT& c)
const { RootNodeT::setChild(mIter, c); }
348 void setChild(ChildNodeT* c)
const { assert(c !=
nullptr); RootNodeT::setChild(mIter, *c); }
349 void setValue(
const ValueT& v)
const
351 if (isTile(mIter)) getTile(mIter).value = v;
355 else stealChild(mIter, Tile(v,
true));
360 using ChildOnIter = ChildIter<RootNode, MapIter, ChildOnPred, ChildType>;
361 using ChildOnCIter = ChildIter<const RootNode, MapCIter, ChildOnPred, const ChildType>;
362 using ChildOffIter = ValueIter<RootNode, MapIter, ChildOffPred, const ValueType>;
363 using ChildOffCIter = ValueIter<const RootNode, MapCIter, ChildOffPred, ValueType>;
364 using ChildAllIter = DenseIter<RootNode, MapIter, ChildType, ValueType>;
365 using ChildAllCIter = DenseIter<const RootNode, MapCIter, const ChildType, const ValueType>;
367 using ValueOnIter = ValueIter<RootNode, MapIter, ValueOnPred, ValueType>;
368 using ValueOnCIter = ValueIter<const RootNode, MapCIter, ValueOnPred, const ValueType>;
369 using ValueOffIter = ValueIter<RootNode, MapIter, ValueOffPred, ValueType>;
370 using ValueOffCIter = ValueIter<const RootNode, MapCIter, ValueOffPred, const ValueType>;
371 using ValueAllIter = ValueIter<RootNode, MapIter, ValueAllPred, ValueType>;
372 using ValueAllCIter = ValueIter<const RootNode, MapCIter, ValueAllPred, const ValueType>;
403 void evalActiveBoundingBox(
CoordBBox& bbox,
bool visitVoxels =
true)
const;
420 void setBackground(
const ValueType& value,
bool updateChildNodes);
426 bool isBackgroundTile(
const Tile&)
const;
428 bool isBackgroundTile(
const MapIter&)
const;
430 bool isBackgroundTile(
const MapCIter&)
const;
434 size_t numBackgroundTiles()
const;
437 size_t eraseBackgroundTiles();
441 bool empty()
const {
return mTable.size() == numBackgroundTiles(); }
446 bool expand(
const Coord& xyz);
449 static void getNodeLog2Dims(std::vector<Index>& dims);
455 Index getWidth()
const {
return this->getMaxIndex()[0] - this->getMinIndex()[0]; }
456 Index getHeight()
const {
return this->getMaxIndex()[1] - this->getMinIndex()[1]; }
457 Index getDepth()
const {
return this->getMaxIndex()[2] - this->getMinIndex()[2]; }
460 Coord getMinIndex()
const;
462 Coord getMaxIndex()
const;
464 void getIndexRange(
CoordBBox& bbox)
const;
468 template<
typename OtherChildType>
472 template<
typename OtherChildType>
477 template<
typename OtherChildType>
485 Index64 onLeafVoxelCount()
const;
486 Index64 offLeafVoxelCount()
const;
488 void nodeCount(std::vector<Index32> &vec)
const;
490 bool isValueOn(
const Coord& xyz)
const;
493 bool hasActiveTiles()
const;
495 const ValueType& getValue(
const Coord& xyz)
const;
496 bool probeValue(
const Coord& xyz, ValueType& value)
const;
501 int getValueDepth(
const Coord& xyz)
const;
504 void setActiveState(
const Coord& xyz,
bool on);
506 void setValueOnly(
const Coord& xyz,
const ValueType& value);
508 void setValueOn(
const Coord& xyz,
const ValueType& value);
510 void setValueOff(
const Coord& xyz);
512 void setValueOff(
const Coord& xyz,
const ValueType& value);
516 template<
typename ModifyOp>
517 void modifyValue(
const Coord& xyz,
const ModifyOp& op);
519 template<
typename ModifyOp>
520 void modifyValueAndActiveState(
const Coord& xyz,
const ModifyOp& op);
523 void fill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
534 this->fill(bbox, value, active);
545 void denseFill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
555 void voxelizeActiveTiles(
bool threaded =
true);
562 template<
typename DenseT>
569 bool writeTopology(std::ostream&,
bool toHalf =
false)
const;
570 bool readTopology(std::istream&,
bool fromHalf =
false);
572 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
573 void readBuffers(std::istream&,
bool fromHalf =
false);
574 void readBuffers(std::istream&,
const CoordBBox&,
bool fromHalf =
false);
584 template<
typename AccessorT>
590 template<
typename AccessorT>
591 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
597 template<
typename AccessorT>
598 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
604 template<
typename AccessorT>
605 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
612 template<
typename ModifyOp,
typename AccessorT>
613 void modifyValueAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
619 template<
typename ModifyOp,
typename AccessorT>
620 void modifyValueAndActiveStateAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
626 template<
typename AccessorT>
627 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
633 template<
typename AccessorT>
634 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
641 template<
typename AccessorT>
642 bool probeValueAndCache(
const Coord& xyz,
ValueType& value, AccessorT&)
const;
649 template<
typename AccessorT>
650 int getValueDepthAndCache(
const Coord& xyz, AccessorT&)
const;
668 template<
typename AccessorT>
679 template<
typename NodeT>
680 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool state);
687 bool addChild(ChildType* child);
691 void addTile(
const Coord& xyz,
const ValueType& value,
bool state);
700 template<
typename AccessorT>
701 void addTileAndCache(
Index level,
const Coord& xyz,
const ValueType&,
bool state, AccessorT&);
712 template<
typename AccessorT>
716 template <
typename NodeT>
719 NodeT* probeNode(
const Coord& xyz);
720 template <
typename NodeT>
721 const NodeT* probeConstNode(
const Coord& xyz)
const;
725 template<
typename NodeT,
typename AccessorT>
728 NodeT* probeNodeAndCache(
const Coord& xyz, AccessorT& acc);
729 template<
typename NodeT,
typename AccessorT>
730 const NodeT* probeConstNodeAndCache(
const Coord& xyz, AccessorT& acc)
const;
742 template<
typename AccessorT>
746 template<
typename AccessorT>
748 template<
typename AccessorT>
758 template<
typename ArrayT>
void getNodes(ArrayT& array);
781 template<
typename ArrayT>
void getNodes(ArrayT& array)
const;
785 template<
typename ArrayT>
809 void stealNodes(ArrayT& array,
const ValueType& value,
bool state);
810 template<
typename ArrayT>
821 template<MergePolicy Policy>
void merge(
RootNode& other);
836 template<
typename OtherChildType>
852 template<
typename OtherChildType>
865 template<
typename OtherChildType>
868 template<
typename CombineOp>
871 template<
typename CombineOp,
typename OtherRootNode >
872 void combine2(
const RootNode& other0,
const OtherRootNode& other1,
873 CombineOp& op,
bool prune =
false);
880 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp&)
const;
882 template<
typename VisitorOp>
void visit(VisitorOp&);
883 template<
typename VisitorOp>
void visit(VisitorOp&)
const;
885 template<
typename OtherRootNodeType,
typename VisitorOp>
886 void visit2(OtherRootNodeType& other, VisitorOp&);
887 template<
typename OtherRootNodeType,
typename VisitorOp>
888 void visit2(OtherRootNodeType& other, VisitorOp&)
const;
901 void resetTable(MapType& table) { mTable.swap(table); table.clear(); }
903 void resetTable(
const MapType&)
const {}
906 Index getChildCount()
const;
907 Index getTileCount()
const;
908 Index getActiveTileCount()
const;
909 Index getInactiveTileCount()
const;
912 static Coord coordToKey(
const Coord& xyz) {
return xyz & ~(ChildType::DIM - 1); }
915 void insertKeys(CoordSet&)
const;
918 bool hasKey(
const Coord& key)
const {
return mTable.find(key) != mTable.end(); }
920 MapIter findKey(
const Coord& key) {
return mTable.find(key); }
923 MapCIter findKey(
const Coord& key)
const {
return mTable.find(key); }
926 MapIter findCoord(
const Coord& xyz) {
return mTable.find(coordToKey(xyz)); }
929 MapCIter findCoord(
const Coord& xyz)
const {
return mTable.find(coordToKey(xyz)); }
931 MapIter findOrAddCoord(
const Coord& xyz);
940 template<
typename OtherChildType>
941 static void enforceSameConfiguration(
const RootNode<OtherChildType>& other);
948 template<
typename OtherChildType>
949 static void enforceCompatibleValueTypes(
const RootNode<OtherChildType>& other);
951 template<
typename CombineOp,
typename OtherRootNode >
952 void doCombine2(
const RootNode&,
const OtherRootNode&, CombineOp&,
bool prune);
954 template<
typename RootNodeT,
typename VisitorOp,
typename ChildAllIterT>
955 static inline void doVisit(RootNodeT&, VisitorOp&);
957 template<
typename RootNodeT,
typename OtherRootNodeT,
typename VisitorOp,
958 typename ChildAllIterT,
typename OtherChildAllIterT>
959 static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&);
963 ValueType mBackground;
990 template<
typename HeadT,
int HeadLevel>
993 using Type =
typename SubtreeT::template Append<HeadT>;
997 template<
typename HeadT>
1007 template<
typename ChildT1,
typename NodeT2>
1011 static const bool value =
false;
1014 template<
typename ChildT1,
typename ChildT2>
1016 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1024 template<
typename ChildT>
1032 template<
typename ChildT>
1040 template<
typename ChildT>
1041 template<
typename OtherChildType>
1049 enforceSameConfiguration(other);
1051 const Tile bgTile(backgd,
false), fgTile(foregd,
true);
1054 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1055 mTable[i->first] = OtherRootT::isTile(i)
1056 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1057 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd, foregd,
TopologyCopy())));
1062 template<
typename ChildT>
1063 template<
typename OtherChildType>
1071 enforceSameConfiguration(other);
1073 const Tile bgTile(backgd,
false), fgTile(backgd,
true);
1075 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1076 mTable[i->first] = OtherRootT::isTile(i)
1077 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1078 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd,
TopologyCopy())));
1089 template<
typename RootT,
typename OtherRootT,
bool Compatible = false>
1096 self.enforceSameConfiguration(other);
1097 self.enforceCompatibleValueTypes(other);
1099 std::ostringstream ostr;
1100 ostr <<
"cannot convert a " <<
typeid(OtherRootT).
name()
1101 <<
" to a " <<
typeid(RootT).
name();
1107 template<
typename RootT,
typename OtherRootT>
1112 using ValueT =
typename RootT::ValueType;
1113 using ChildT =
typename RootT::ChildNodeType;
1114 using NodeStruct =
typename RootT::NodeStruct;
1115 using Tile =
typename RootT::Tile;
1116 using OtherValueT =
typename OtherRootT::ValueType;
1117 using OtherMapCIter =
typename OtherRootT::MapCIter;
1118 using OtherTile =
typename OtherRootT::Tile;
1122 static inline ValueT convertValue(
const OtherValueT& val) {
return ValueT(val); }
1125 self.mBackground = Local::convertValue(other.mBackground);
1130 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1131 if (other.isTile(i)) {
1133 const OtherTile& otherTile = other.getTile(i);
1134 self.mTable[i->first] = NodeStruct(
1135 Tile(Local::convertValue(otherTile.value), otherTile.active));
1138 self.mTable[i->first] = NodeStruct(*(
new ChildT(other.getChild(i))));
1146 template<
typename ChildT>
1147 inline RootNode<ChildT>&
1150 if (&other !=
this) {
1151 mBackground = other.mBackground;
1156 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1158 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(
new ChildT(getChild(i))));
1165 template<
typename ChildT>
1166 template<
typename OtherChildType>
1171 using OtherValueT =
typename OtherRootT::ValueType;
1181 template<
typename ChildT>
1187 if (updateChildNodes) {
1190 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1191 ChildT *child = iter->second.child;
1193 child->resetBackground(mBackground, background);
1195 Tile& tile = getTile(iter);
1196 if (tile.active)
continue;
1198 tile.value = background;
1205 mBackground = background;
1208 template<
typename ChildT>
1215 template<
typename ChildT>
1222 template<
typename ChildT>
1230 template<
typename ChildT>
1235 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1236 if (this->isBackgroundTile(i)) ++count;
1242 template<
typename ChildT>
1246 std::set<Coord> keysToErase;
1247 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1248 if (this->isBackgroundTile(i)) keysToErase.insert(i->first);
1250 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1253 return keysToErase.size();
1260 template<
typename ChildT>
1264 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1265 keys.insert(i->first);
1270 template<
typename ChildT>
1271 inline typename RootNode<ChildT>::MapIter
1272 RootNode<ChildT>::findOrAddCoord(
const Coord& xyz)
1274 const Coord key = coordToKey(xyz);
1275 std::pair<MapIter, bool> result = mTable.insert(
1276 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1277 return result.first;
1281 template<
typename ChildT>
1285 const Coord key = coordToKey(xyz);
1286 std::pair<MapIter, bool> result = mTable.insert(
1287 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1288 return result.second;
1295 template<
typename ChildT>
1300 ChildT::getNodeLog2Dims(dims);
1304 template<
typename ChildT>
1308 return mTable.empty() ?
Coord(0) : mTable.begin()->first;
1311 template<
typename ChildT>
1315 return mTable.empty() ?
Coord(0) : mTable.rbegin()->first +
Coord(ChildT::DIM - 1);
1319 template<
typename ChildT>
1323 bbox.
min() = this->getMinIndex();
1324 bbox.
max() = this->getMaxIndex();
1331 template<
typename ChildT>
1332 template<
typename OtherChildType>
1337 using OtherMapT =
typename OtherRootT::MapType;
1338 using OtherIterT =
typename OtherRootT::MapIter;
1339 using OtherCIterT =
typename OtherRootT::MapCIter;
1341 if (!hasSameConfiguration(other))
return false;
1344 OtherMapT copyOfOtherTable = other.mTable;
1347 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1348 if (this->isBackgroundTile(thisIter))
continue;
1351 OtherCIterT otherIter = other.findKey(thisIter->first);
1352 if (otherIter == other.mTable.end())
return false;
1355 if (isChild(thisIter)) {
1356 if (OtherRootT::isTile(otherIter))
return false;
1358 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter)))
return false;
1360 if (OtherRootT::isChild(otherIter))
return false;
1361 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active)
return false;
1368 copyOfOtherTable.erase(otherIter->first);
1371 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1378 template<
typename ChildT>
1379 template<
typename OtherChildType>
1383 std::vector<Index> thisDims, otherDims;
1386 return (thisDims == otherDims);
1390 template<
typename ChildT>
1391 template<
typename OtherChildType>
1395 std::vector<Index> thisDims, otherDims;
1398 if (thisDims != otherDims) {
1399 std::ostringstream ostr;
1400 ostr <<
"grids have incompatible configurations (" << thisDims[0];
1401 for (
size_t i = 1, N = thisDims.size(); i < N; ++i) ostr <<
" x " << thisDims[i];
1402 ostr <<
" vs. " << otherDims[0];
1403 for (
size_t i = 1, N = otherDims.size(); i < N; ++i) ostr <<
" x " << otherDims[i];
1410 template<
typename ChildT>
1411 template<
typename OtherChildType>
1415 using OtherValueType =
typename OtherChildType::ValueType;
1420 template<
typename ChildT>
1421 template<
typename OtherChildType>
1425 using OtherValueType =
typename OtherChildType::ValueType;
1427 std::ostringstream ostr;
1428 ostr <<
"values of type " << typeNameAsString<OtherValueType>()
1429 <<
" cannot be converted to type " << typeNameAsString<ValueType>();
1438 template<
typename ChildT>
1443 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1444 if (
const ChildT *child = iter->second.child) {
1445 sum += child->memUsage();
1452 template<
typename ChildT>
1456 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1457 delete i->second.child;
1463 template<
typename ChildT>
1467 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1468 if (
const ChildT *child = iter->second.child) {
1469 child->evalActiveBoundingBox(bbox, visitVoxels);
1470 }
else if (isTileOn(iter)) {
1471 bbox.
expand(iter->first, ChildT::DIM);
1477 template<
typename ChildT>
1481 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1482 if (isChild(i)) ++sum;
1488 template<
typename ChildT>
1490 RootNode<ChildT>::getTileCount()
const
1493 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1494 if (isTile(i)) ++sum;
1500 template<
typename ChildT>
1502 RootNode<ChildT>::getActiveTileCount()
const
1505 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1506 if (isTileOn(i)) ++sum;
1512 template<
typename ChildT>
1514 RootNode<ChildT>::getInactiveTileCount()
const
1517 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1518 if (isTileOff(i)) ++sum;
1524 template<
typename ChildT>
1529 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1530 if (isChild(i)) sum += getChild(i).leafCount();
1536 template<
typename ChildT>
1541 if (ChildT::LEVEL != 0) {
1542 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1543 if (isChild(i)) sum += getChild(i).nonLeafCount();
1550 template<
typename ChildT>
1554 return this->getChildCount();
1558 template<
typename ChildT>
1563 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1565 sum += getChild(i).onVoxelCount();
1566 }
else if (isTileOn(i)) {
1567 sum += ChildT::NUM_VOXELS;
1574 template<
typename ChildT>
1579 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1581 sum += getChild(i).offVoxelCount();
1582 }
else if (isTileOff(i) && !this->isBackgroundTile(i)) {
1583 sum += ChildT::NUM_VOXELS;
1590 template<
typename ChildT>
1595 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1596 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1602 template<
typename ChildT>
1607 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1608 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1613 template<
typename ChildT>
1618 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1620 sum += getChild(i).onTileCount();
1621 }
else if (isTileOn(i)) {
1628 template<
typename ChildT>
1632 assert(vec.size() > LEVEL);
1634 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1637 getChild(i).nodeCount(vec);
1641 vec[ChildNodeType::LEVEL] = sum;
1647 template<
typename ChildT>
1651 MapCIter iter = this->findCoord(xyz);
1652 if (iter == mTable.end() || isTileOff(iter))
return false;
1653 return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz);
1656 template<
typename ChildT>
1660 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1661 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active)
return true;
1666 template<
typename ChildT>
1667 template<
typename AccessorT>
1671 MapCIter iter = this->findCoord(xyz);
1672 if (iter == mTable.end() || isTileOff(iter))
return false;
1673 if (isTileOn(iter))
return true;
1674 acc.insert(xyz, &getChild(iter));
1675 return getChild(iter).isValueOnAndCache(xyz, acc);
1679 template<
typename ChildT>
1680 inline const typename ChildT::ValueType&
1683 MapCIter iter = this->findCoord(xyz);
1684 return iter == mTable.end() ? mBackground
1685 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1688 template<
typename ChildT>
1689 template<
typename AccessorT>
1690 inline const typename ChildT::ValueType&
1693 MapCIter iter = this->findCoord(xyz);
1694 if (iter == mTable.end())
return mBackground;
1695 if (isChild(iter)) {
1696 acc.insert(xyz, &getChild(iter));
1697 return getChild(iter).getValueAndCache(xyz, acc);
1699 return getTile(iter).value;
1703 template<
typename ChildT>
1707 MapCIter iter = this->findCoord(xyz);
1708 return iter == mTable.end() ? -1
1709 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1712 template<
typename ChildT>
1713 template<
typename AccessorT>
1717 MapCIter iter = this->findCoord(xyz);
1718 if (iter == mTable.end())
return -1;
1719 if (isTile(iter))
return 0;
1720 acc.insert(xyz, &getChild(iter));
1721 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1725 template<
typename ChildT>
1729 MapIter iter = this->findCoord(xyz);
1730 if (iter != mTable.end() && !isTileOff(iter)) {
1731 if (isTileOn(iter)) {
1732 setChild(iter, *
new ChildT(xyz, getTile(iter).value,
true));
1734 getChild(iter).setValueOff(xyz);
1739 template<
typename ChildT>
1743 ChildT* child =
nullptr;
1744 MapIter iter = this->findCoord(xyz);
1745 if (iter == mTable.end()) {
1747 child =
new ChildT(xyz, mBackground);
1748 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1752 }
else if (isChild(iter)) {
1753 child = &getChild(iter);
1754 }
else if (on != getTile(iter).active) {
1755 child =
new ChildT(xyz, getTile(iter).value, !on);
1756 setChild(iter, *child);
1758 if (child) child->setActiveState(xyz, on);
1761 template<
typename ChildT>
1762 template<
typename AccessorT>
1766 ChildT* child =
nullptr;
1767 MapIter iter = this->findCoord(xyz);
1768 if (iter == mTable.end()) {
1770 child =
new ChildT(xyz, mBackground);
1771 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1775 }
else if (isChild(iter)) {
1776 child = &getChild(iter);
1777 }
else if (on != getTile(iter).active) {
1778 child =
new ChildT(xyz, getTile(iter).value, !on);
1779 setChild(iter, *child);
1782 acc.insert(xyz, child);
1783 child->setActiveStateAndCache(xyz, on, acc);
1788 template<
typename ChildT>
1792 ChildT* child =
nullptr;
1793 MapIter iter = this->findCoord(xyz);
1794 if (iter == mTable.end()) {
1796 child =
new ChildT(xyz, mBackground);
1797 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1799 }
else if (isChild(iter)) {
1800 child = &getChild(iter);
1802 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1803 setChild(iter, *child);
1805 if (child) child->setValueOff(xyz, value);
1808 template<
typename ChildT>
1809 template<
typename AccessorT>
1813 ChildT* child =
nullptr;
1814 MapIter iter = this->findCoord(xyz);
1815 if (iter == mTable.end()) {
1817 child =
new ChildT(xyz, mBackground);
1818 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1820 }
else if (isChild(iter)) {
1821 child = &getChild(iter);
1823 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1824 setChild(iter, *child);
1827 acc.insert(xyz, child);
1828 child->setValueOffAndCache(xyz, value, acc);
1833 template<
typename ChildT>
1837 ChildT* child =
nullptr;
1838 MapIter iter = this->findCoord(xyz);
1839 if (iter == mTable.end()) {
1840 child =
new ChildT(xyz, mBackground);
1841 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1842 }
else if (isChild(iter)) {
1843 child = &getChild(iter);
1845 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1846 setChild(iter, *child);
1848 if (child) child->setValueOn(xyz, value);
1851 template<
typename ChildT>
1852 template<
typename AccessorT>
1856 ChildT* child =
nullptr;
1857 MapIter iter = this->findCoord(xyz);
1858 if (iter == mTable.end()) {
1859 child =
new ChildT(xyz, mBackground);
1860 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1861 }
else if (isChild(iter)) {
1862 child = &getChild(iter);
1864 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1865 setChild(iter, *child);
1868 acc.insert(xyz, child);
1869 child->setValueAndCache(xyz, value, acc);
1874 template<
typename ChildT>
1878 ChildT* child =
nullptr;
1879 MapIter iter = this->findCoord(xyz);
1880 if (iter == mTable.end()) {
1881 child =
new ChildT(xyz, mBackground);
1882 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1883 }
else if (isChild(iter)) {
1884 child = &getChild(iter);
1886 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1887 setChild(iter, *child);
1889 if (child) child->setValueOnly(xyz, value);
1892 template<
typename ChildT>
1893 template<
typename AccessorT>
1897 ChildT* child =
nullptr;
1898 MapIter iter = this->findCoord(xyz);
1899 if (iter == mTable.end()) {
1900 child =
new ChildT(xyz, mBackground);
1901 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1902 }
else if (isChild(iter)) {
1903 child = &getChild(iter);
1905 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1906 setChild(iter, *child);
1909 acc.insert(xyz, child);
1910 child->setValueOnlyAndCache(xyz, value, acc);
1915 template<
typename ChildT>
1916 template<
typename ModifyOp>
1920 ChildT* child =
nullptr;
1921 MapIter iter = this->findCoord(xyz);
1922 if (iter == mTable.end()) {
1923 child =
new ChildT(xyz, mBackground);
1924 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1925 }
else if (isChild(iter)) {
1926 child = &getChild(iter);
1930 bool createChild = isTileOff(iter);
1934 const ValueType& tileVal = getTile(iter).value;
1940 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1941 setChild(iter, *child);
1944 if (child) child->modifyValue(xyz, op);
1947 template<
typename ChildT>
1948 template<
typename ModifyOp,
typename AccessorT>
1952 ChildT* child =
nullptr;
1953 MapIter iter = this->findCoord(xyz);
1954 if (iter == mTable.end()) {
1955 child =
new ChildT(xyz, mBackground);
1956 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1957 }
else if (isChild(iter)) {
1958 child = &getChild(iter);
1962 bool createChild = isTileOff(iter);
1966 const ValueType& tileVal = getTile(iter).value;
1972 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1973 setChild(iter, *child);
1977 acc.insert(xyz, child);
1978 child->modifyValueAndCache(xyz, op, acc);
1983 template<
typename ChildT>
1984 template<
typename ModifyOp>
1988 ChildT* child =
nullptr;
1989 MapIter iter = this->findCoord(xyz);
1990 if (iter == mTable.end()) {
1991 child =
new ChildT(xyz, mBackground);
1992 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1993 }
else if (isChild(iter)) {
1994 child = &getChild(iter);
1996 const Tile& tile = getTile(iter);
1997 bool modifiedState = tile.active;
1999 op(modifiedVal, modifiedState);
2003 child =
new ChildT(xyz, tile.value, tile.active);
2004 setChild(iter, *child);
2007 if (child) child->modifyValueAndActiveState(xyz, op);
2010 template<
typename ChildT>
2011 template<
typename ModifyOp,
typename AccessorT>
2014 const Coord& xyz,
const ModifyOp& op, AccessorT& acc)
2016 ChildT* child =
nullptr;
2017 MapIter iter = this->findCoord(xyz);
2018 if (iter == mTable.end()) {
2019 child =
new ChildT(xyz, mBackground);
2020 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2021 }
else if (isChild(iter)) {
2022 child = &getChild(iter);
2024 const Tile& tile = getTile(iter);
2025 bool modifiedState = tile.active;
2027 op(modifiedVal, modifiedState);
2031 child =
new ChildT(xyz, tile.value, tile.active);
2032 setChild(iter, *child);
2036 acc.insert(xyz, child);
2037 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2042 template<
typename ChildT>
2046 MapCIter iter = this->findCoord(xyz);
2047 if (iter == mTable.end()) {
2048 value = mBackground;
2050 }
else if (isChild(iter)) {
2051 return getChild(iter).probeValue(xyz, value);
2053 value = getTile(iter).value;
2054 return isTileOn(iter);
2057 template<
typename ChildT>
2058 template<
typename AccessorT>
2062 MapCIter iter = this->findCoord(xyz);
2063 if (iter == mTable.end()) {
2064 value = mBackground;
2066 }
else if (isChild(iter)) {
2067 acc.insert(xyz, &getChild(iter));
2068 return getChild(iter).probeValueAndCache(xyz, value, acc);
2070 value = getTile(iter).value;
2071 return isTileOn(iter);
2078 template<
typename ChildT>
2082 if (bbox.
empty())
return;
2087 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
2089 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
2091 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
2095 Coord tileMin = coordToKey(xyz);
2096 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
2102 ChildT* child =
nullptr;
2103 MapIter iter = this->findKey(tileMin);
2104 if (iter == mTable.end()) {
2107 child =
new ChildT(xyz, mBackground);
2108 mTable[tileMin] = NodeStruct(*child);
2109 }
else if (isTile(iter)) {
2112 const Tile& tile = getTile(iter);
2113 child =
new ChildT(xyz, tile.value, tile.active);
2114 mTable[tileMin] = NodeStruct(*child);
2115 }
else if (isChild(iter)) {
2116 child = &getChild(iter);
2121 child->fill(
CoordBBox(xyz, tmp), value, active);
2127 MapIter iter = this->findOrAddCoord(tileMin);
2128 setTile(iter, Tile(value, active));
2136 template<
typename ChildT>
2140 if (bbox.
empty())
return;
2142 if (active && mTable.empty()) {
2145 sparseFill(bbox, value, active);
2146 voxelizeActiveTiles(
true);
2152 Coord xyz, tileMin, tileMax;
2153 for (
int x = bbox.
min().
x(); x <= bbox.
max().
x(); x = tileMax.
x() + 1) {
2155 for (
int y = bbox.
min().
y(); y <= bbox.
max().
y(); y = tileMax.
y() + 1) {
2157 for (
int z = bbox.
min().
z(); z <= bbox.
max().
z(); z = tileMax.
z() + 1) {
2161 tileMin = coordToKey(xyz);
2162 tileMax = tileMin.
offsetBy(ChildT::DIM - 1);
2166 const auto iter = findOrAddCoord(tileMin);
2171 const auto& tile = getTile(iter);
2172 auto* child =
new ChildT{tileMin, tile.value, tile.active};
2173 setChild(iter, *child);
2176 getChild(iter).denseFill(bbox, value, active);
2186 template<
typename ChildT>
2194 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2195 if (this->isTileOff(i))
continue;
2196 ChildT* child = i->second.child;
2197 if (child ==
nullptr) {
2200 child =
new ChildT{i->first, this->getTile(i).value,
true};
2201 i->second.child = child;
2203 child->voxelizeActiveTiles(threaded);
2211 template<
typename ChildT>
2212 template<
typename DenseT>
2216 using DenseValueType =
typename DenseT::ValueType;
2218 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2219 const Coord&
min = dense.bbox().min();
2221 for (
Coord xyz = bbox.
min(); xyz[0] <= bbox.
max()[0]; xyz[0] = nodeBBox.
max()[0] + 1) {
2222 for (xyz[1] = bbox.
min()[1]; xyz[1] <= bbox.
max()[1]; xyz[1] = nodeBBox.
max()[1] + 1) {
2223 for (xyz[2] = bbox.
min()[2]; xyz[2] <= bbox.
max()[2]; xyz[2] = nodeBBox.
max()[2] + 1) {
2231 MapCIter iter = this->findKey(nodeBBox.
min());
2232 if (iter != mTable.end() && isChild(iter)) {
2233 getChild(iter).copyToDense(sub, dense);
2235 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2237 DenseValueType* a0 = dense.data() + zStride*sub.
min()[2];
2238 for (
Int32 x=sub.
min()[0], ex=sub.
max()[0]+1; x<ex; ++x) {
2239 DenseValueType* a1 = a0 + x*xStride;
2240 for (
Int32 y=sub.
min()[1], ey=sub.
max()[1]+1; y<ey; ++y) {
2241 DenseValueType* a2 = a1 + y*yStride;
2242 for (
Int32 z=sub.
min()[2], ez=sub.
max()[2]+1; z<ez; ++z, a2 += zStride) {
2243 *a2 = DenseValueType(value);
2256 template<
typename ChildT>
2261 os.write(
reinterpret_cast<const char*
>(&mBackground),
sizeof(
ValueType));
2264 os.write(
reinterpret_cast<const char*
>(&truncatedVal),
sizeof(
ValueType));
2268 const Index numTiles = this->getTileCount(), numChildren = this->getChildCount();
2269 os.write(
reinterpret_cast<const char*
>(&numTiles),
sizeof(
Index));
2270 os.write(
reinterpret_cast<const char*
>(&numChildren),
sizeof(
Index));
2272 if (numTiles == 0 && numChildren == 0)
return false;
2275 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2276 if (isChild(i))
continue;
2277 os.write(
reinterpret_cast<const char*
>(i->first.asPointer()), 3 *
sizeof(
Int32));
2278 os.write(
reinterpret_cast<const char*
>(&getTile(i).value),
sizeof(
ValueType));
2279 os.write(
reinterpret_cast<const char*
>(&getTile(i).active),
sizeof(
bool));
2282 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2283 if (isTile(i))
continue;
2284 os.write(
reinterpret_cast<const char*
>(i->first.asPointer()), 3 *
sizeof(
Int32));
2285 getChild(i).writeTopology(os, toHalf);
2292 template<
typename ChildT>
2304 is.read(
reinterpret_cast<char*
>(&mBackground),
sizeof(
ValueType));
2306 is.read(
reinterpret_cast<char*
>(&inside),
sizeof(
ValueType));
2311 Coord rangeMin, rangeMax;
2313 is.read(
reinterpret_cast<char*
>(rangeMax.
asPointer()), 3 *
sizeof(
Int32));
2316 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2318 for (
int i = 0; i < 3; ++i) {
2319 offset[i] = rangeMin[i] >> ChildT::TOTAL;
2320 rangeMin[i] = offset[i] << ChildT::TOTAL;
2322 tableSize += log2Dim[i];
2323 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2325 log2Dim[3] = log2Dim[1] + log2Dim[2];
2326 tableSize = 1U << tableSize;
2334 for (
Index i = 0; i < tableSize; ++i) {
2338 origin[0] = (n >> log2Dim[3]) + offset[0];
2339 n &= (1U << log2Dim[3]) - 1;
2340 origin[1] = (n >> log2Dim[2]) + offset[1];
2341 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2342 origin <<= ChildT::TOTAL;
2344 if (childMask.isOn(i)) {
2346 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2347 child->readTopology(is);
2348 mTable[origin] = NodeStruct(*child);
2353 is.read(
reinterpret_cast<char*
>(&value),
sizeof(
ValueType));
2355 mTable[origin] = NodeStruct(Tile(value, valueMask.
isOn(i)));
2364 is.read(
reinterpret_cast<char*
>(&mBackground),
sizeof(
ValueType));
2367 Index numTiles = 0, numChildren = 0;
2368 is.read(
reinterpret_cast<char*
>(&numTiles),
sizeof(
Index));
2369 is.read(
reinterpret_cast<char*
>(&numChildren),
sizeof(
Index));
2371 if (numTiles == 0 && numChildren == 0)
return false;
2378 for (
Index n = 0; n < numTiles; ++n) {
2379 is.read(
reinterpret_cast<char*
>(vec), 3 *
sizeof(
Int32));
2380 is.read(
reinterpret_cast<char*
>(&value),
sizeof(
ValueType));
2381 is.read(
reinterpret_cast<char*
>(&active),
sizeof(
bool));
2382 mTable[
Coord(vec)] = NodeStruct(Tile(value, active));
2386 for (
Index n = 0; n < numChildren; ++n) {
2387 is.read(
reinterpret_cast<char*
>(vec), 3 *
sizeof(
Int32));
2389 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2390 child->readTopology(is, fromHalf);
2391 mTable[
Coord(vec)] = NodeStruct(*child);
2398 template<
typename ChildT>
2402 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2403 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2408 template<
typename ChildT>
2412 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2413 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2418 template<
typename ChildT>
2422 const Tile bgTile(mBackground,
false);
2424 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2430 ChildT& child = getChild(i);
2431 child.readBuffers(is, clipBBox, fromHalf);
2435 this->
clip(clipBBox);
2442 template<
typename ChildT>
2446 const Tile bgTile(mBackground,
false);
2450 MapType copyOfTable(mTable);
2451 for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2452 const Coord& xyz = i->first;
2456 setTile(this->findCoord(xyz), bgTile);
2458 }
else if (!clipBBox.
isInside(tileBBox)) {
2462 getChild(i).clip(clipBBox, mBackground);
2467 const Tile& origTile = getTile(i);
2468 setTile(this->findCoord(xyz), bgTile);
2469 this->sparseFill(tileBBox, origTile.value, origTile.active);
2482 template<
typename ChildT>
2488 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2489 if (this->isTile(i))
continue;
2490 this->getChild(i).prune(tolerance);
2491 if (this->getChild(i).isConstant(value, state, tolerance)) {
2492 this->setTile(i, Tile(value, state));
2495 this->eraseBackgroundTiles();
2502 template<
typename ChildT>
2503 template<
typename NodeT>
2507 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2508 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2510 MapIter iter = this->findCoord(xyz);
2511 if (iter == mTable.end() || isTile(iter))
return nullptr;
2512 return (std::is_same<NodeT, ChildT>::value)
2513 ?
reinterpret_cast<NodeT*
>(&stealChild(iter, Tile(value, state)))
2514 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2522 template<
typename ChildT>
2526 if (leaf ==
nullptr)
return;
2527 ChildT* child =
nullptr;
2528 const Coord& xyz = leaf->origin();
2529 MapIter iter = this->findCoord(xyz);
2530 if (iter == mTable.end()) {
2531 if (ChildT::LEVEL>0) {
2532 child =
new ChildT(xyz, mBackground,
false);
2534 child =
reinterpret_cast<ChildT*
>(leaf);
2536 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2537 }
else if (isChild(iter)) {
2538 if (ChildT::LEVEL>0) {
2539 child = &getChild(iter);
2541 child =
reinterpret_cast<ChildT*
>(leaf);
2542 setChild(iter, *child);
2545 if (ChildT::LEVEL>0) {
2546 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2548 child =
reinterpret_cast<ChildT*
>(leaf);
2550 setChild(iter, *child);
2552 child->addLeaf(leaf);
2556 template<
typename ChildT>
2557 template<
typename AccessorT>
2561 if (leaf ==
nullptr)
return;
2562 ChildT* child =
nullptr;
2563 const Coord& xyz = leaf->origin();
2564 MapIter iter = this->findCoord(xyz);
2565 if (iter == mTable.end()) {
2566 if (ChildT::LEVEL>0) {
2567 child =
new ChildT(xyz, mBackground,
false);
2569 child =
reinterpret_cast<ChildT*
>(leaf);
2571 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2572 }
else if (isChild(iter)) {
2573 if (ChildT::LEVEL>0) {
2574 child = &getChild(iter);
2576 child =
reinterpret_cast<ChildT*
>(leaf);
2577 setChild(iter, *child);
2580 if (ChildT::LEVEL>0) {
2581 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2583 child =
reinterpret_cast<ChildT*
>(leaf);
2585 setChild(iter, *child);
2587 acc.insert(xyz, child);
2588 child->addLeafAndCache(leaf, acc);
2591 template<
typename ChildT>
2595 if (!child)
return false;
2596 const Coord& xyz = child->origin();
2597 MapIter iter = this->findCoord(xyz);
2598 if (iter == mTable.end()) {
2599 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2601 setChild(iter, *child);
2606 template<
typename ChildT>
2610 MapIter iter = this->findCoord(xyz);
2611 if (iter == mTable.end()) {
2612 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2614 setTile(iter, Tile(value, state));
2618 template<
typename ChildT>
2623 if (LEVEL >= level) {
2624 MapIter iter = this->findCoord(xyz);
2625 if (iter == mTable.end()) {
2626 if (LEVEL > level) {
2627 ChildT* child =
new ChildT(xyz, mBackground,
false);
2628 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2629 child->addTile(level, xyz, value, state);
2631 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2633 }
else if (isChild(iter)) {
2634 if (LEVEL > level) {
2635 getChild(iter).addTile(level, xyz, value, state);
2637 setTile(iter, Tile(value, state));
2640 if (LEVEL > level) {
2641 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2642 setChild(iter, *child);
2643 child->addTile(level, xyz, value, state);
2645 setTile(iter, Tile(value, state));
2652 template<
typename ChildT>
2653 template<
typename AccessorT>
2656 bool state, AccessorT& acc)
2658 if (LEVEL >= level) {
2659 MapIter iter = this->findCoord(xyz);
2660 if (iter == mTable.end()) {
2661 if (LEVEL > level) {
2662 ChildT* child =
new ChildT(xyz, mBackground,
false);
2663 acc.insert(xyz, child);
2664 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2665 child->addTileAndCache(level, xyz, value, state, acc);
2667 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2669 }
else if (isChild(iter)) {
2670 if (LEVEL > level) {
2671 ChildT* child = &getChild(iter);
2672 acc.insert(xyz, child);
2673 child->addTileAndCache(level, xyz, value, state, acc);
2675 setTile(iter, Tile(value, state));
2678 if (LEVEL > level) {
2679 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2680 acc.insert(xyz, child);
2681 setChild(iter, *child);
2682 child->addTileAndCache(level, xyz, value, state, acc);
2684 setTile(iter, Tile(value, state));
2694 template<
typename ChildT>
2695 inline typename ChildT::LeafNodeType*
2698 ChildT* child =
nullptr;
2699 MapIter iter = this->findCoord(xyz);
2700 if (iter == mTable.end()) {
2701 child =
new ChildT(xyz, mBackground,
false);
2702 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2703 }
else if (isChild(iter)) {
2704 child = &getChild(iter);
2706 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2707 setChild(iter, *child);
2709 return child->touchLeaf(xyz);
2713 template<
typename ChildT>
2714 template<
typename AccessorT>
2715 inline typename ChildT::LeafNodeType*
2718 ChildT* child =
nullptr;
2719 MapIter iter = this->findCoord(xyz);
2720 if (iter == mTable.end()) {
2721 child =
new ChildT(xyz, mBackground,
false);
2722 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2723 }
else if (isChild(iter)) {
2724 child = &getChild(iter);
2726 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2727 setChild(iter, *child);
2729 acc.insert(xyz, child);
2730 return child->touchLeafAndCache(xyz, acc);
2737 template<
typename ChildT>
2738 template<
typename NodeT>
2742 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2743 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2745 MapIter iter = this->findCoord(xyz);
2746 if (iter == mTable.end() || isTile(iter))
return nullptr;
2747 ChildT* child = &getChild(iter);
2748 return (std::is_same<NodeT, ChildT>::value)
2749 ?
reinterpret_cast<NodeT*
>(child)
2750 : child->template probeNode<NodeT>(xyz);
2755 template<
typename ChildT>
2756 template<
typename NodeT>
2760 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2761 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2763 MapCIter iter = this->findCoord(xyz);
2764 if (iter == mTable.end() || isTile(iter))
return nullptr;
2765 const ChildT* child = &getChild(iter);
2766 return (std::is_same<NodeT, ChildT>::value)
2767 ?
reinterpret_cast<const NodeT*
>(child)
2768 : child->template probeConstNode<NodeT>(xyz);
2773 template<
typename ChildT>
2774 inline typename ChildT::LeafNodeType*
2777 return this->
template probeNode<LeafNodeType>(xyz);
2781 template<
typename ChildT>
2782 inline const typename ChildT::LeafNodeType*
2785 return this->
template probeConstNode<LeafNodeType>(xyz);
2789 template<
typename ChildT>
2790 template<
typename AccessorT>
2791 inline typename ChildT::LeafNodeType*
2794 return this->
template probeNodeAndCache<LeafNodeType>(xyz, acc);
2798 template<
typename ChildT>
2799 template<
typename AccessorT>
2800 inline const typename ChildT::LeafNodeType*
2803 return this->
template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2807 template<
typename ChildT>
2808 template<
typename AccessorT>
2809 inline const typename ChildT::LeafNodeType*
2812 return this->probeConstLeafAndCache(xyz, acc);
2816 template<
typename ChildT>
2817 template<
typename NodeT,
typename AccessorT>
2821 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2822 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2824 MapIter iter = this->findCoord(xyz);
2825 if (iter == mTable.end() || isTile(iter))
return nullptr;
2826 ChildT* child = &getChild(iter);
2827 acc.insert(xyz, child);
2828 return (std::is_same<NodeT, ChildT>::value)
2829 ?
reinterpret_cast<NodeT*
>(child)
2830 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2835 template<
typename ChildT>
2836 template<
typename NodeT,
typename AccessorT>
2840 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2841 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2843 MapCIter iter = this->findCoord(xyz);
2844 if (iter == mTable.end() || isTile(iter))
return nullptr;
2845 const ChildT* child = &getChild(iter);
2846 acc.insert(xyz, child);
2847 return (std::is_same<NodeT, ChildT>::value)
2848 ?
reinterpret_cast<const NodeT*
>(child)
2849 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2856 template<
typename ChildT>
2857 template<
typename ArrayT>
2861 using NodePtr =
typename ArrayT::value_type;
2862 static_assert(std::is_pointer<NodePtr>::value,
2863 "argument to getNodes() must be a pointer array");
2866 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2867 "can't extract non-const nodes from a const tree");
2868 using ArrayChildT =
typename std::conditional<
2869 std::is_const<NodeType>::value,
const ChildT, ChildT>
::type;
2871 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2872 if (ChildT* child = iter->second.child) {
2874 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2875 array.push_back(
reinterpret_cast<NodePtr
>(iter->second.child));
2877 child->getNodes(array);
2884 template<
typename ChildT>
2885 template<
typename ArrayT>
2889 using NodePtr =
typename ArrayT::value_type;
2890 static_assert(std::is_pointer<NodePtr>::value,
2891 "argument to getNodes() must be a pointer array");
2893 static_assert(std::is_const<NodeType>::value,
2894 "argument to getNodes() must be an array of const node pointers");
2896 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2897 "can't extract non-const nodes from a const tree");
2899 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2902 if (std::is_same<NodePtr, const ChildT*>::value) {
2903 array.push_back(
reinterpret_cast<NodePtr
>(iter->second.child));
2905 child->getNodes(array);
2914 template<
typename ChildT>
2915 template<
typename ArrayT>
2919 using NodePtr =
typename ArrayT::value_type;
2920 static_assert(std::is_pointer<NodePtr>::value,
2921 "argument to stealNodes() must be a pointer array");
2924 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2925 "can't extract non-const nodes from a const tree");
2926 using ArrayChildT =
typename std::conditional<
2927 std::is_const<NodeType>::value,
const ChildT, ChildT>
::type;
2929 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2930 if (ChildT* child = iter->second.child) {
2932 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2933 array.push_back(
reinterpret_cast<NodePtr
>(&stealChild(iter, Tile(value, state))));
2935 child->stealNodes(array, value, state);
2946 template<
typename ChildT>
2947 template<MergePolicy Policy>
2957 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2958 MapIter j = mTable.find(i->first);
2959 if (other.isChild(i)) {
2960 if (j == mTable.end()) {
2961 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2962 child.resetBackground(other.mBackground, mBackground);
2963 mTable[i->first] = NodeStruct(child);
2964 }
else if (isTile(j)) {
2966 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2967 child.resetBackground(other.mBackground, mBackground);
2971 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
2972 other.mBackground, mBackground);
2974 }
else if (other.isTileOn(i)) {
2975 if (j == mTable.end()) {
2976 mTable[i->first] = i->second;
2977 }
else if (!isTileOn(j)) {
2979 setTile(j, Tile(other.getTile(i).value,
true));
2986 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
2987 MapIter j = mTable.find(i->first);
2988 if (other.isChild(i)) {
2989 if (j == mTable.end()) {
2990 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2991 child.resetBackground(other.mBackground, mBackground);
2992 mTable[i->first] = NodeStruct(child);
2993 }
else if (isTile(j)) {
2994 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
2995 child.resetBackground(other.mBackground, mBackground);
2998 getChild(j).template merge<MERGE_NODES>(
2999 getChild(i), other.mBackground, mBackground);
3006 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3007 MapIter j = mTable.find(i->first);
3008 if (other.isChild(i)) {
3009 if (j == mTable.end()) {
3011 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3012 child.resetBackground(other.mBackground, mBackground);
3013 mTable[i->first] = NodeStruct(child);
3014 }
else if (isTile(j)) {
3016 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3017 child.resetBackground(other.mBackground, mBackground);
3018 const Tile tile = getTile(j);
3022 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3023 tile.value, tile.active);
3027 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
3028 other.mBackground, mBackground);
3030 }
else if (other.isTileOn(i)) {
3031 if (j == mTable.end()) {
3033 mTable[i->first] = i->second;
3034 }
else if (isTileOff(j)) {
3036 setTile(j, Tile(other.getTile(i).value,
true));
3037 }
else if (isChild(j)) {
3039 const Tile& tile = getTile(i);
3040 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3041 tile.value, tile.active);
3058 template<
typename ChildT>
3059 template<
typename OtherChildType>
3064 using OtherCIterT =
typename OtherRootT::MapCIter;
3066 enforceSameConfiguration(other);
3068 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3069 MapIter j = mTable.find(i->first);
3070 if (other.isChild(i)) {
3071 if (j == mTable.end()) {
3072 mTable[i->first] = NodeStruct(
3073 *(
new ChildT(other.getChild(i), mBackground,
TopologyCopy())));
3074 }
else if (this->isChild(j)) {
3075 this->getChild(j).topologyUnion(other.getChild(i));
3077 ChildT* child =
new ChildT(
3078 other.getChild(i), this->getTile(j).value,
TopologyCopy());
3079 if (this->isTileOn(j)) child->setValuesOn();
3080 this->setChild(j, *child);
3082 }
else if (other.isTileOn(i)) {
3083 if (j == mTable.end()) {
3084 mTable[i->first] = NodeStruct(Tile(mBackground,
true));
3085 }
else if (this->isChild(j)) {
3086 this->getChild(j).setValuesOn();
3087 }
else if (this->isTileOff(j)) {
3088 this->setTile(j, Tile(this->getTile(j).value,
true));
3094 template<
typename ChildT>
3095 template<
typename OtherChildType>
3100 using OtherCIterT =
typename OtherRootT::MapCIter;
3102 enforceSameConfiguration(other);
3104 std::set<Coord> tmp;
3105 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3106 OtherCIterT j = other.mTable.find(i->first);
3107 if (this->isChild(i)) {
3108 if (j == other.mTable.end() || other.isTileOff(j)) {
3109 tmp.insert(i->first);
3110 }
else if (other.isChild(j)) {
3111 this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3113 }
else if (this->isTileOn(i)) {
3114 if (j == other.mTable.end() || other.isTileOff(j)) {
3115 this->setTile(i, Tile(this->getTile(i).value,
false));
3116 }
else if (other.isChild(j)) {
3118 new ChildT(other.getChild(j), this->getTile(i).value,
TopologyCopy());
3119 this->setChild(i, *child);
3123 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3124 MapIter it = this->findCoord(*i);
3125 setTile(it, Tile());
3130 template<
typename ChildT>
3131 template<
typename OtherChildType>
3136 using OtherCIterT =
typename OtherRootT::MapCIter;
3138 enforceSameConfiguration(other);
3140 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3141 MapIter j = mTable.find(i->first);
3142 if (other.isChild(i)) {
3143 if (j == mTable.end() || this->isTileOff(j)) {
3145 }
else if (this->isChild(j)) {
3146 this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3147 }
else if (this->isTileOn(j)) {
3149 ChildT* child =
new ChildT(j->first, this->getTile(j).value,
true);
3150 child->topologyDifference(other.getChild(i), mBackground);
3151 this->setChild(j, *child);
3153 }
else if (other.isTileOn(i)) {
3154 if (j == mTable.end() || this->isTileOff(j)) {
3156 }
else if (this->isChild(j)) {
3159 }
else if (this->isTileOn(j)) {
3160 this->setTile(j, Tile(this->getTile(j).value,
false));
3169 template<
typename ChildT>
3170 template<
typename CombineOp>
3177 this->insertKeys(keys);
3178 other.insertKeys(keys);
3180 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3181 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3182 if (isTile(iter) && isTile(otherIter)) {
3185 op(args.
setARef(getTile(iter).value)
3186 .setAIsActive(isTileOn(iter))
3187 .setBRef(getTile(otherIter).value)
3188 .setBIsActive(isTileOn(otherIter)));
3191 }
else if (isChild(iter) && isTile(otherIter)) {
3193 ChildT& child = getChild(iter);
3194 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3196 }
else if (isTile(iter) && isChild(otherIter)) {
3201 ChildT& child = getChild(otherIter);
3202 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3205 setChild(iter, stealChild(otherIter, Tile()));
3209 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3210 child.combine(otherChild, op);
3212 if (
prune && isChild(iter)) getChild(iter).prune();
3216 op(args.
setARef(mBackground).setBRef(other.mBackground));
3217 mBackground = args.
result();
3229 template<
typename CombineOp,
typename RootT,
typename OtherRootT,
bool Compatible = false>
3232 static inline void combine2(RootT&
self,
const RootT&,
const OtherRootT& other1,
3237 self.enforceSameConfiguration(other1);
3238 self.enforceCompatibleValueTypes(other1);
3240 std::ostringstream ostr;
3241 ostr <<
"cannot combine a " <<
typeid(OtherRootT).
name()
3242 <<
" into a " <<
typeid(RootT).
name();
3248 template<
typename CombineOp,
typename RootT,
typename OtherRootT>
3251 static inline void combine2(RootT&
self,
const RootT& other0,
const OtherRootT& other1,
3252 CombineOp& op,
bool prune)
3254 self.doCombine2(other0, other1, op,
prune);
3259 template<
typename ChildT>
3260 template<
typename CombineOp,
typename OtherRootNode>
3263 CombineOp& op,
bool prune)
3265 using OtherValueType =
typename OtherRootNode::ValueType;
3269 *
this, other0, other1, op,
prune);
3273 template<
typename ChildT>
3274 template<
typename CombineOp,
typename OtherRootNode>
3277 CombineOp& op,
bool prune)
3279 enforceSameConfiguration(other1);
3281 using OtherValueT =
typename OtherRootNode::ValueType;
3282 using OtherTileT =
typename OtherRootNode::Tile;
3283 using OtherNodeStructT =
typename OtherRootNode::NodeStruct;
3284 using OtherMapCIterT =
typename OtherRootNode::MapCIter;
3289 other0.insertKeys(keys);
3290 other1.insertKeys(keys);
3292 const NodeStruct bg0(Tile(other0.mBackground,
false));
3293 const OtherNodeStructT bg1(OtherTileT(other1.mBackground,
false));
3295 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3296 MapIter thisIter = this->findOrAddCoord(*i);
3297 MapCIter iter0 = other0.findKey(*i);
3298 OtherMapCIterT iter1 = other1.findKey(*i);
3299 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3300 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3301 if (ns0.isTile() && ns1.isTile()) {
3304 op(args.
setARef(ns0.tile.value)
3305 .setAIsActive(ns0.isTileOn())
3306 .setBRef(ns1.tile.value)
3307 .setBIsActive(ns1.isTileOn()));
3310 if (!isChild(thisIter)) {
3312 const Coord& childOrigin =
3313 ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3314 setChild(thisIter, *(
new ChildT(childOrigin, getTile(thisIter).value)));
3316 ChildT& child = getChild(thisIter);
3321 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3322 }
else if (ns1.isTile()) {
3325 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3329 child.combine2(*ns0.child, *ns1.child, op);
3332 if (
prune && isChild(thisIter)) getChild(thisIter).prune();
3336 op(args.
setARef(other0.mBackground).setBRef(other1.mBackground));
3337 mBackground = args.
result();
3344 template<
typename ChildT>
3345 template<
typename BBoxOp>
3349 const bool descent = op.template descent<LEVEL>();
3350 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3351 if (this->isTileOff(i))
continue;
3352 if (this->isChild(i) && descent) {
3353 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