8 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED 9 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED 17 #include <openvdb/version.h> 18 #include <tbb/parallel_for.h> 31 template<
typename HeadType,
int HeadLevel>
struct NodeChain;
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>
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 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;
269 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
270 using NonConstValueType =
typename std::remove_const<ValueType>::type;
271 using NonConstChildNodeType =
typename std::remove_const<ChildNodeType>::type;
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;
291 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
292 using NonConstValueType =
typename std::remove_const<ValueT>::type;
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;
322 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
323 using NonConstValueType =
typename std::remove_const<ValueT>::type;
324 using NonConstChildNodeType =
typename std::remove_const<ChildNodeT>::type;
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;
425 void setBackground(
const ValueType& value,
bool updateChildNodes);
431 bool isBackgroundTile(
const Tile&)
const;
434 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>
490 Index64 onLeafVoxelCount()
const;
491 Index64 offLeafVoxelCount()
const;
493 void nodeCount(std::vector<Index32> &vec)
const;
495 bool isValueOn(
const Coord& xyz)
const;
498 bool hasActiveTiles()
const;
500 const ValueType& getValue(
const Coord& xyz)
const;
501 bool probeValue(
const Coord& xyz,
ValueType& value)
const;
506 int getValueDepth(
const Coord& xyz)
const;
509 void setActiveState(
const Coord& xyz,
bool on);
511 void setValueOnly(
const Coord& xyz,
const ValueType& value);
513 void setValueOn(
const Coord& xyz,
const ValueType& value);
515 void setValueOff(
const Coord& xyz);
517 void setValueOff(
const Coord& xyz,
const ValueType& value);
521 template<
typename ModifyOp>
522 void modifyValue(
const Coord& xyz,
const ModifyOp& op);
524 template<
typename ModifyOp>
525 void modifyValueAndActiveState(
const Coord& xyz,
const ModifyOp& op);
539 this->fill(bbox, value, active);
560 void voxelizeActiveTiles(
bool threaded =
true);
567 template<
typename DenseT>
574 bool writeTopology(std::ostream&,
bool toHalf =
false)
const;
575 bool readTopology(std::istream&,
bool fromHalf =
false);
577 void writeBuffers(std::ostream&,
bool toHalf =
false)
const;
578 void readBuffers(std::istream&,
bool fromHalf =
false);
579 void readBuffers(std::istream&,
const CoordBBox&,
bool fromHalf =
false);
589 template<
typename AccessorT>
590 const ValueType& getValueAndCache(
const Coord& xyz, AccessorT&)
const;
595 template<
typename AccessorT>
596 bool isValueOnAndCache(
const Coord& xyz, AccessorT&)
const;
602 template<
typename AccessorT>
603 void setValueAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
609 template<
typename AccessorT>
610 void setValueOnlyAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
617 template<
typename ModifyOp,
typename AccessorT>
618 void modifyValueAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
624 template<
typename ModifyOp,
typename AccessorT>
625 void modifyValueAndActiveStateAndCache(
const Coord& xyz,
const ModifyOp& op, AccessorT&);
631 template<
typename AccessorT>
632 void setValueOffAndCache(
const Coord& xyz,
const ValueType& value, AccessorT&);
638 template<
typename AccessorT>
639 void setActiveStateAndCache(
const Coord& xyz,
bool on, AccessorT&);
646 template<
typename AccessorT>
647 bool probeValueAndCache(
const Coord& xyz,
ValueType& value, AccessorT&)
const;
654 template<
typename AccessorT>
655 int getValueDepthAndCache(
const Coord& xyz, AccessorT&)
const;
673 template<
typename AccessorT>
684 template<
typename NodeT>
685 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool state);
692 bool addChild(ChildType* child);
696 void addTile(
const Coord& xyz,
const ValueType& value,
bool state);
701 void addTile(
Index level,
const Coord& xyz,
const ValueType& value,
bool state);
705 template<
typename AccessorT>
706 void addTileAndCache(
Index level,
const Coord& xyz,
const ValueType&,
bool state, AccessorT&);
717 template<
typename AccessorT>
718 LeafNodeType* touchLeafAndCache(
const Coord& xyz, AccessorT& acc);
723 template <
typename NodeT>
724 NodeT* probeNode(
const Coord& xyz);
725 template <
typename NodeT>
726 const NodeT* probeConstNode(
const Coord& xyz)
const;
732 template<
typename NodeT,
typename AccessorT>
733 NodeT* probeNodeAndCache(
const Coord& xyz, AccessorT& acc);
734 template<
typename NodeT,
typename AccessorT>
735 const NodeT* probeConstNodeAndCache(
const Coord& xyz, AccessorT& acc)
const;
742 const LeafNodeType* probeConstLeaf(
const Coord& xyz)
const;
749 template<
typename AccessorT>
750 LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT& acc);
751 template<
typename AccessorT>
752 const LeafNodeType* probeConstLeafAndCache(
const Coord& xyz, AccessorT& acc)
const;
753 template<
typename AccessorT>
754 const LeafNodeType* probeLeafAndCache(
const Coord& xyz, AccessorT& acc)
const;
785 template<
typename ArrayT>
void getNodes(ArrayT& array);
786 template<
typename ArrayT>
void getNodes(ArrayT& array)
const;
813 template<
typename ArrayT>
814 void stealNodes(ArrayT& array,
const ValueType& value,
bool state);
815 template<
typename ArrayT>
826 template<MergePolicy Policy>
void merge(
RootNode& other);
844 template<
typename OtherChildType>
860 template<
typename OtherChildType>
873 template<
typename OtherChildType>
876 template<
typename CombineOp>
879 template<
typename CombineOp,
typename OtherRootNode >
880 void combine2(
const RootNode& other0,
const OtherRootNode& other1,
881 CombineOp& op,
bool prune =
false);
883 #if OPENVDB_ABI_VERSION_NUMBER >= 10 885 const Coord&
origin()
const {
return mOrigin; }
891 void setOrigin(
const Coord &origin);
906 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;
915 #if OPENVDB_ABI_VERSION_NUMBER < 10 917 static Coord coordToKey(
const Coord& xyz) {
return xyz & ~(ChildType::DIM - 1); }
920 Coord coordToKey(
const Coord& xyz)
const {
return (xyz - mOrigin) & ~(ChildType::DIM - 1); }
924 void insertKeys(CoordSet&)
const;
927 bool hasKey(
const Coord& key)
const {
return mTable.find(key) != mTable.end(); }
931 MapIter findKey(
const Coord& key) {
return mTable.find(key); }
932 MapCIter findKey(
const Coord& key)
const {
return mTable.find(key); }
937 MapIter findCoord(
const Coord& xyz) {
return mTable.find(coordToKey(xyz)); }
938 MapCIter findCoord(
const Coord& xyz)
const {
return mTable.find(coordToKey(xyz)); }
943 MapIter findOrAddCoord(
const Coord& xyz);
949 template<
typename OtherChildType>
957 template<
typename OtherChildType>
960 template<
typename CombineOp,
typename OtherRootNode >
961 void doCombine2(
const RootNode&,
const OtherRootNode&, CombineOp&,
bool prune);
965 #if OPENVDB_ABI_VERSION_NUMBER >= 10 996 template<
typename HeadT,
int HeadLevel>
999 using Type =
typename SubtreeT::template Append<HeadT>;
1003 template<
typename HeadT>
1015 template<
typename ChildT1,
typename NodeT2>
1017 static const bool value =
false;
1020 template<
typename ChildT1,
typename ChildT2>
1022 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
1030 template<
typename ChildT>
1034 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1042 template<
typename ChildT>
1045 : mBackground(background)
1046 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1054 template<
typename ChildT>
1055 template<
typename OtherChildType>
1059 : mBackground(backgd)
1060 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1061 , mOrigin(other.mOrigin)
1063 , mTransientData(other.mTransientData)
1067 #if OPENVDB_ABI_VERSION_NUMBER >= 10 1068 if (mOrigin != Coord(0,0,0)) {
1073 enforceSameConfiguration(other);
1075 const Tile bgTile(backgd,
false), fgTile(foregd,
true);
1078 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1079 mTable[i->first] = OtherRootT::isTile(i)
1080 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1081 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd, foregd,
TopologyCopy())));
1086 template<
typename ChildT>
1087 template<
typename OtherChildType>
1091 : mBackground(backgd)
1092 #if OPENVDB_ABI_VERSION_NUMBER >= 10
1093 , mOrigin(other.mOrigin)
1095 , mTransientData(other.mTransientData)
1099 #if OPENVDB_ABI_VERSION_NUMBER >= 10 1100 if (mOrigin != Coord(0,0,0)) {
1105 enforceSameConfiguration(other);
1107 const Tile bgTile(backgd,
false), fgTile(backgd,
true);
1109 for (
typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) {
1110 mTable[i->first] = OtherRootT::isTile(i)
1111 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile)
1112 : NodeStruct(*(
new ChildT(OtherRootT::getChild(i), backgd,
TopologyCopy())));
1123 template<
typename RootT,
typename OtherRootT,
bool Compatible = false>
1130 self.enforceSameConfiguration(other);
1131 self.enforceCompatibleValueTypes(other);
1133 std::ostringstream ostr;
1134 ostr <<
"cannot convert a " <<
typeid(OtherRootT).name()
1135 <<
" to a " <<
typeid(RootT).name();
1141 template<
typename RootT,
typename OtherRootT>
1146 using ValueT =
typename RootT::ValueType;
1147 using ChildT =
typename RootT::ChildNodeType;
1148 using NodeStruct =
typename RootT::NodeStruct;
1149 using Tile =
typename RootT::Tile;
1150 using OtherValueT =
typename OtherRootT::ValueType;
1151 using OtherMapCIter =
typename OtherRootT::MapCIter;
1152 using OtherTile =
typename OtherRootT::Tile;
1156 static inline ValueT convertValue(
const OtherValueT& val) {
return ValueT(val); }
1159 self.mBackground = Local::convertValue(other.mBackground);
1160 #if OPENVDB_ABI_VERSION_NUMBER >= 10 1161 if (other.mOrigin != Coord(0,0,0)) {
1162 OPENVDB_THROW(
ValueError,
"RootNodeCopyHelper::copyWithValueConversion: non-zero offsets are currently not supported");
1164 self.mOrigin = other.mOrigin;
1166 self.mTransientData = other.mTransientData;
1171 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1172 if (other.isTile(i)) {
1174 const OtherTile& otherTile = other.getTile(i);
1175 self.mTable[i->first] = NodeStruct(
1176 Tile(Local::convertValue(otherTile.value), otherTile.active));
1179 self.mTable[i->first] = NodeStruct(*(
new ChildT(other.getChild(i))));
1187 template<
typename ChildT>
1191 if (&other !=
this) {
1192 mBackground = other.mBackground;
1193 #if OPENVDB_ABI_VERSION_NUMBER >= 10 1194 mOrigin = other.mOrigin;
1195 if (mOrigin != Coord(0,0,0)) {
1199 mTransientData = other.mTransientData;
1204 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
1206 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(
new ChildT(getChild(i))));
1213 template<
typename ChildT>
1214 template<
typename OtherChildType>
1219 using OtherValueT =
typename OtherRootT::ValueType;
1229 template<
typename ChildT>
1235 if (updateChildNodes) {
1238 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1239 ChildT *child = iter->second.child;
1241 child->resetBackground(mBackground, background);
1243 Tile& tile = getTile(iter);
1244 if (tile.active)
continue;
1256 template<
typename ChildT>
1263 template<
typename ChildT>
1270 template<
typename ChildT>
1278 template<
typename ChildT>
1283 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1290 template<
typename ChildT>
1294 std::set<Coord> keysToErase;
1295 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1298 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) {
1301 return keysToErase.size();
1308 template<
typename ChildT>
1312 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1313 keys.insert(i->first);
1318 template<
typename ChildT>
1319 inline typename RootNode<ChildT>::MapIter
1322 const Coord key = coordToKey(xyz);
1323 std::pair<MapIter, bool> result = mTable.insert(
1324 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1325 return result.first;
1329 template<
typename ChildT>
1333 const Coord key = coordToKey(xyz);
1334 std::pair<MapIter, bool> result = mTable.insert(
1335 typename MapType::value_type(key, NodeStruct(Tile(mBackground,
false))));
1336 return result.second;
1343 template<
typename ChildT>
1348 ChildT::getNodeLog2Dims(dims);
1352 template<
typename ChildT>
1356 return mTable.empty() ? Coord(0) : mTable.begin()->first;
1359 template<
typename ChildT>
1363 return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1);
1367 template<
typename ChildT>
1379 template<
typename ChildT>
1380 template<
typename OtherChildType>
1385 using OtherMapT =
typename OtherRootT::MapType;
1386 using OtherIterT =
typename OtherRootT::MapIter;
1387 using OtherCIterT =
typename OtherRootT::MapCIter;
1392 OtherMapT copyOfOtherTable = other.mTable;
1395 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) {
1399 OtherCIterT otherIter = other.findKey(thisIter->first);
1400 if (otherIter == other.mTable.end())
return false;
1403 if (isChild(thisIter)) {
1404 if (OtherRootT::isTile(otherIter))
return false;
1406 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter)))
return false;
1408 if (OtherRootT::isChild(otherIter))
return false;
1409 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active)
return false;
1416 copyOfOtherTable.erase(otherIter->first);
1419 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) {
1426 template<
typename ChildT>
1427 template<
typename OtherChildType>
1431 std::vector<Index> thisDims, otherDims;
1434 return (thisDims == otherDims);
1438 template<
typename ChildT>
1439 template<
typename OtherChildType>
1443 std::vector<Index> thisDims, otherDims;
1446 if (thisDims != otherDims) {
1447 std::ostringstream ostr;
1448 ostr <<
"grids have incompatible configurations (" << thisDims[0];
1449 for (
size_t i = 1, N = thisDims.size(); i < N; ++i) ostr <<
" x " << thisDims[i];
1450 ostr <<
" vs. " << otherDims[0];
1451 for (
size_t i = 1, N = otherDims.size(); i < N; ++i) ostr <<
" x " << otherDims[i];
1458 template<
typename ChildT>
1459 template<
typename OtherChildType>
1463 using OtherValueType =
typename OtherChildType::ValueType;
1468 template<
typename ChildT>
1469 template<
typename OtherChildType>
1473 using OtherValueType =
typename OtherChildType::ValueType;
1475 std::ostringstream ostr;
1476 ostr <<
"values of type " << typeNameAsString<OtherValueType>()
1477 <<
" cannot be converted to type " << typeNameAsString<ValueType>();
1486 template<
typename ChildT>
1491 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1492 if (
const ChildT *child = iter->second.child) {
1493 sum += child->memUsage();
1500 template<
typename ChildT>
1504 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1505 delete i->second.child;
1511 template<
typename ChildT>
1515 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
1516 if (
const ChildT *child = iter->second.child) {
1517 child->evalActiveBoundingBox(bbox, visitVoxels);
1518 }
else if (isTileOn(iter)) {
1519 bbox.expand(iter->first, ChildT::DIM);
1525 template<
typename ChildT>
1532 template<
typename ChildT>
1537 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1538 if (isTile(i)) ++sum;
1544 template<
typename ChildT>
1549 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1550 if (isTileOn(i)) ++sum;
1556 template<
typename ChildT>
1561 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1562 if (isTileOff(i)) ++sum;
1568 template<
typename ChildT>
1573 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1574 if (isChild(i)) sum += getChild(i).leafCount();
1580 template<
typename ChildT>
1585 if (ChildT::LEVEL != 0) {
1586 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1587 if (isChild(i)) sum += getChild(i).nonLeafCount();
1594 template<
typename ChildT>
1599 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1600 if (isChild(i)) ++sum;
1606 template<
typename ChildT>
1611 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1613 sum += getChild(i).onVoxelCount();
1614 }
else if (isTileOn(i)) {
1615 sum += ChildT::NUM_VOXELS;
1622 template<
typename ChildT>
1627 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1629 sum += getChild(i).offVoxelCount();
1631 sum += ChildT::NUM_VOXELS;
1638 template<
typename ChildT>
1643 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1644 if (isChild(i)) sum += getChild(i).onLeafVoxelCount();
1650 template<
typename ChildT>
1655 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1656 if (isChild(i)) sum += getChild(i).offLeafVoxelCount();
1661 template<
typename ChildT>
1666 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1668 sum += getChild(i).onTileCount();
1669 }
else if (isTileOn(i)) {
1676 template<
typename ChildT>
1680 assert(vec.size() >
LEVEL);
1682 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1685 getChild(i).nodeCount(vec);
1689 vec[ChildNodeType::LEVEL] = sum;
1695 template<
typename ChildT>
1699 MapCIter iter = this->findCoord(xyz);
1700 if (iter == mTable.end() || isTileOff(iter))
return false;
1701 return isTileOn(iter) ?
true : getChild(iter).isValueOn(xyz);
1704 template<
typename ChildT>
1708 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
1709 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active)
return true;
1714 template<
typename ChildT>
1715 template<
typename AccessorT>
1719 MapCIter iter = this->findCoord(xyz);
1720 if (iter == mTable.end() || isTileOff(iter))
return false;
1721 if (isTileOn(iter))
return true;
1722 acc.insert(xyz, &getChild(iter));
1723 return getChild(iter).isValueOnAndCache(xyz, acc);
1727 template<
typename ChildT>
1728 inline const typename ChildT::ValueType&
1731 MapCIter iter = this->findCoord(xyz);
1732 return iter == mTable.end() ? mBackground
1733 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz));
1736 template<
typename ChildT>
1737 template<
typename AccessorT>
1738 inline const typename ChildT::ValueType&
1741 MapCIter iter = this->findCoord(xyz);
1742 if (iter == mTable.end())
return mBackground;
1743 if (isChild(iter)) {
1744 acc.insert(xyz, &getChild(iter));
1745 return getChild(iter).getValueAndCache(xyz, acc);
1747 return getTile(iter).value;
1751 template<
typename ChildT>
1755 MapCIter iter = this->findCoord(xyz);
1756 return iter == mTable.end() ? -1
1757 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz)));
1760 template<
typename ChildT>
1761 template<
typename AccessorT>
1765 MapCIter iter = this->findCoord(xyz);
1766 if (iter == mTable.end())
return -1;
1767 if (isTile(iter))
return 0;
1768 acc.insert(xyz, &getChild(iter));
1769 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc));
1773 template<
typename ChildT>
1777 MapIter iter = this->findCoord(xyz);
1778 if (iter != mTable.end() && !isTileOff(iter)) {
1779 if (isTileOn(iter)) {
1780 setChild(iter, *
new ChildT(xyz, getTile(iter).value,
true));
1782 getChild(iter).setValueOff(xyz);
1787 template<
typename ChildT>
1791 ChildT* child =
nullptr;
1792 MapIter iter = this->findCoord(xyz);
1793 if (iter == mTable.end()) {
1795 child =
new ChildT(xyz, mBackground);
1796 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1800 }
else if (isChild(iter)) {
1801 child = &getChild(iter);
1802 }
else if (on != getTile(iter).active) {
1803 child =
new ChildT(xyz, getTile(iter).value, !on);
1804 setChild(iter, *child);
1806 if (child) child->setActiveState(xyz, on);
1809 template<
typename ChildT>
1810 template<
typename AccessorT>
1814 ChildT* child =
nullptr;
1815 MapIter iter = this->findCoord(xyz);
1816 if (iter == mTable.end()) {
1818 child =
new ChildT(xyz, mBackground);
1819 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1823 }
else if (isChild(iter)) {
1824 child = &getChild(iter);
1825 }
else if (on != getTile(iter).active) {
1826 child =
new ChildT(xyz, getTile(iter).value, !on);
1827 setChild(iter, *child);
1830 acc.insert(xyz, child);
1831 child->setActiveStateAndCache(xyz, on, acc);
1836 template<
typename ChildT>
1840 ChildT* child =
nullptr;
1841 MapIter iter = this->findCoord(xyz);
1842 if (iter == mTable.end()) {
1844 child =
new ChildT(xyz, mBackground);
1845 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1847 }
else if (isChild(iter)) {
1848 child = &getChild(iter);
1850 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1851 setChild(iter, *child);
1853 if (child) child->setValueOff(xyz, value);
1856 template<
typename ChildT>
1857 template<
typename AccessorT>
1861 ChildT* child =
nullptr;
1862 MapIter iter = this->findCoord(xyz);
1863 if (iter == mTable.end()) {
1865 child =
new ChildT(xyz, mBackground);
1866 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1868 }
else if (isChild(iter)) {
1869 child = &getChild(iter);
1871 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1872 setChild(iter, *child);
1875 acc.insert(xyz, child);
1876 child->setValueOffAndCache(xyz, value, acc);
1881 template<
typename ChildT>
1885 ChildT* child =
nullptr;
1886 MapIter iter = this->findCoord(xyz);
1887 if (iter == mTable.end()) {
1888 child =
new ChildT(xyz, mBackground);
1889 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1890 }
else if (isChild(iter)) {
1891 child = &getChild(iter);
1893 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1894 setChild(iter, *child);
1896 if (child) child->setValueOn(xyz, value);
1899 template<
typename ChildT>
1900 template<
typename AccessorT>
1904 ChildT* child =
nullptr;
1905 MapIter iter = this->findCoord(xyz);
1906 if (iter == mTable.end()) {
1907 child =
new ChildT(xyz, mBackground);
1908 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1909 }
else if (isChild(iter)) {
1910 child = &getChild(iter);
1912 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1913 setChild(iter, *child);
1916 acc.insert(xyz, child);
1917 child->setValueAndCache(xyz, value, acc);
1922 template<
typename ChildT>
1926 ChildT* child =
nullptr;
1927 MapIter iter = this->findCoord(xyz);
1928 if (iter == mTable.end()) {
1929 child =
new ChildT(xyz, mBackground);
1930 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1931 }
else if (isChild(iter)) {
1932 child = &getChild(iter);
1934 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1935 setChild(iter, *child);
1937 if (child) child->setValueOnly(xyz, value);
1940 template<
typename ChildT>
1941 template<
typename AccessorT>
1945 ChildT* child =
nullptr;
1946 MapIter iter = this->findCoord(xyz);
1947 if (iter == mTable.end()) {
1948 child =
new ChildT(xyz, mBackground);
1949 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1950 }
else if (isChild(iter)) {
1951 child = &getChild(iter);
1953 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1954 setChild(iter, *child);
1957 acc.insert(xyz, child);
1958 child->setValueOnlyAndCache(xyz, value, acc);
1963 template<
typename ChildT>
1964 template<
typename ModifyOp>
1968 ChildT* child =
nullptr;
1969 MapIter iter = this->findCoord(xyz);
1970 if (iter == mTable.end()) {
1971 child =
new ChildT(xyz, mBackground);
1972 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
1973 }
else if (isChild(iter)) {
1974 child = &getChild(iter);
1978 bool createChild = isTileOff(iter);
1982 const ValueType& tileVal = getTile(iter).value;
1988 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
1989 setChild(iter, *child);
1992 if (child) child->modifyValue(xyz, op);
1995 template<
typename ChildT>
1996 template<
typename ModifyOp,
typename AccessorT>
2000 ChildT* child =
nullptr;
2001 MapIter iter = this->findCoord(xyz);
2002 if (iter == mTable.end()) {
2003 child =
new ChildT(xyz, mBackground);
2004 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2005 }
else if (isChild(iter)) {
2006 child = &getChild(iter);
2010 bool createChild = isTileOff(iter);
2014 const ValueType& tileVal = getTile(iter).value;
2020 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2021 setChild(iter, *child);
2025 acc.insert(xyz, child);
2026 child->modifyValueAndCache(xyz, op, acc);
2031 template<
typename ChildT>
2032 template<
typename ModifyOp>
2036 ChildT* child =
nullptr;
2037 MapIter iter = this->findCoord(xyz);
2038 if (iter == mTable.end()) {
2039 child =
new ChildT(xyz, mBackground);
2040 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2041 }
else if (isChild(iter)) {
2042 child = &getChild(iter);
2044 const Tile& tile = getTile(iter);
2045 bool modifiedState = tile.active;
2047 op(modifiedVal, modifiedState);
2051 child =
new ChildT(xyz, tile.value, tile.active);
2052 setChild(iter, *child);
2055 if (child) child->modifyValueAndActiveState(xyz, op);
2058 template<
typename ChildT>
2059 template<
typename ModifyOp,
typename AccessorT>
2062 const Coord& xyz,
const ModifyOp& op, AccessorT& acc)
2064 ChildT* child =
nullptr;
2065 MapIter iter = this->findCoord(xyz);
2066 if (iter == mTable.end()) {
2067 child =
new ChildT(xyz, mBackground);
2068 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2069 }
else if (isChild(iter)) {
2070 child = &getChild(iter);
2072 const Tile& tile = getTile(iter);
2073 bool modifiedState = tile.active;
2075 op(modifiedVal, modifiedState);
2079 child =
new ChildT(xyz, tile.value, tile.active);
2080 setChild(iter, *child);
2084 acc.insert(xyz, child);
2085 child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2090 template<
typename ChildT>
2094 MapCIter iter = this->findCoord(xyz);
2095 if (iter == mTable.end()) {
2096 value = mBackground;
2098 }
else if (isChild(iter)) {
2099 return getChild(iter).probeValue(xyz, value);
2101 value = getTile(iter).value;
2102 return isTileOn(iter);
2105 template<
typename ChildT>
2106 template<
typename AccessorT>
2110 MapCIter iter = this->findCoord(xyz);
2111 if (iter == mTable.end()) {
2112 value = mBackground;
2114 }
else if (isChild(iter)) {
2115 acc.insert(xyz, &getChild(iter));
2116 return getChild(iter).probeValueAndCache(xyz, value, acc);
2118 value = getTile(iter).value;
2119 return isTileOn(iter);
2126 template<
typename ChildT>
2130 if (bbox.empty())
return;
2135 for (
int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2137 for (
int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2139 for (
int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2143 Coord tileMin = coordToKey(xyz);
2144 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2146 if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) {
2150 ChildT* child =
nullptr;
2151 MapIter iter = this->findKey(tileMin);
2152 if (iter == mTable.end()) {
2155 child =
new ChildT(xyz, mBackground);
2156 mTable[tileMin] = NodeStruct(*child);
2157 }
else if (isTile(iter)) {
2160 const Tile& tile = getTile(iter);
2161 child =
new ChildT(xyz, tile.value, tile.active);
2162 mTable[tileMin] = NodeStruct(*child);
2163 }
else if (isChild(iter)) {
2164 child = &getChild(iter);
2169 child->fill(
CoordBBox(xyz, tmp), value, active);
2175 MapIter iter = this->findOrAddCoord(tileMin);
2176 setTile(iter, Tile(value, active));
2184 template<
typename ChildT>
2188 if (bbox.empty())
return;
2190 if (active && mTable.empty()) {
2200 Coord xyz, tileMin, tileMax;
2201 for (
int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) {
2203 for (
int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) {
2205 for (
int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) {
2209 tileMin = coordToKey(xyz);
2210 tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2214 const auto iter = findOrAddCoord(tileMin);
2219 const auto& tile = getTile(iter);
2220 auto* child =
new ChildT{tileMin, tile.value, tile.active};
2221 setChild(iter, *child);
2224 getChild(iter).denseFill(bbox, value, active);
2234 template<
typename ChildT>
2242 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2243 if (this->isTileOff(i))
continue;
2244 ChildT* child = i->second.child;
2245 if (child ==
nullptr) {
2248 child =
new ChildT{i->first, this->getTile(i).value,
true};
2249 i->second.child = child;
2251 child->voxelizeActiveTiles(threaded);
2259 template<
typename ChildT>
2260 template<
typename DenseT>
2264 using DenseValueType =
typename DenseT::ValueType;
2266 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2267 const Coord&
min = dense.bbox().min();
2269 for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) {
2270 for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) {
2271 for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) {
2274 nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM);
2279 MapCIter iter = this->findKey(nodeBBox.min());
2280 if (iter != mTable.end() && isChild(iter)) {
2281 getChild(iter).copyToDense(sub, dense);
2283 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value;
2284 sub.translate(-min);
2285 DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2286 for (
Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2287 DenseValueType* a1 = a0 + x*xStride;
2288 for (
Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2289 DenseValueType* a2 = a1 + y*yStride;
2290 for (
Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) {
2291 *a2 = DenseValueType(value);
2304 template<
typename ChildT>
2309 os.write(reinterpret_cast<const char*>(&mBackground),
sizeof(
ValueType));
2312 os.write(reinterpret_cast<const char*>(&truncatedVal),
sizeof(
ValueType));
2316 const Index numTiles = this->getTileCount(), numChildren = this->
childCount();
2317 os.write(reinterpret_cast<const char*>(&numTiles),
sizeof(
Index));
2318 os.write(reinterpret_cast<const char*>(&numChildren),
sizeof(
Index));
2320 if (numTiles == 0 && numChildren == 0)
return false;
2323 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2324 if (isChild(i))
continue;
2325 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
2326 os.write(reinterpret_cast<const char*>(&getTile(i).value),
sizeof(
ValueType));
2327 os.write(reinterpret_cast<const char*>(&getTile(i).active),
sizeof(
bool));
2330 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2331 if (isTile(i))
continue;
2332 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 *
sizeof(
Int32));
2333 getChild(i).writeTopology(os, toHalf);
2340 template<
typename ChildT>
2352 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
2354 is.read(reinterpret_cast<char*>(&inside),
sizeof(
ValueType));
2359 Coord rangeMin, rangeMax;
2360 is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 *
sizeof(
Int32));
2361 is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 *
sizeof(
Int32));
2364 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 };
2366 for (
int i = 0; i < 3; ++i) {
2367 offset[i] = rangeMin[i] >> ChildT::TOTAL;
2368 rangeMin[i] = offset[i] << ChildT::TOTAL;
2370 tableSize += log2Dim[i];
2371 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1;
2373 log2Dim[3] = log2Dim[1] + log2Dim[2];
2374 tableSize = 1U << tableSize;
2382 for (
Index i = 0; i < tableSize; ++i) {
2386 origin[0] = (n >> log2Dim[3]) + offset[0];
2387 n &= (1U << log2Dim[3]) - 1;
2388 origin[1] = (n >> log2Dim[2]) + offset[1];
2389 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1];
2390 origin <<= ChildT::TOTAL;
2392 if (childMask.isOn(i)) {
2394 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2395 child->readTopology(is);
2396 mTable[
origin] = NodeStruct(*child);
2401 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
2403 mTable[
origin] = NodeStruct(Tile(value, valueMask.
isOn(i)));
2412 is.read(reinterpret_cast<char*>(&mBackground),
sizeof(
ValueType));
2415 Index numTiles = 0, numChildren = 0;
2416 is.read(reinterpret_cast<char*>(&numTiles),
sizeof(
Index));
2417 is.read(reinterpret_cast<char*>(&numChildren),
sizeof(
Index));
2419 if (numTiles == 0 && numChildren == 0)
return false;
2426 for (
Index n = 0; n < numTiles; ++n) {
2427 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
2428 is.read(reinterpret_cast<char*>(&value),
sizeof(
ValueType));
2429 is.read(reinterpret_cast<char*>(&active),
sizeof(
bool));
2430 mTable[Coord(vec)] = NodeStruct(Tile(value, active));
2434 for (
Index n = 0; n < numChildren; ++n) {
2435 is.read(reinterpret_cast<char*>(vec), 3 *
sizeof(
Int32));
2437 ChildT* child =
new ChildT(
PartialCreate(), origin, mBackground);
2438 child->readTopology(is, fromHalf);
2439 mTable[Coord(vec)] = NodeStruct(*child);
2446 template<
typename ChildT>
2450 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2451 if (isChild(i)) getChild(i).writeBuffers(os, toHalf);
2456 template<
typename ChildT>
2460 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2461 if (isChild(i)) getChild(i).readBuffers(is, fromHalf);
2466 template<
typename ChildT>
2470 const Tile bgTile(mBackground,
false);
2472 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2478 ChildT& child = getChild(i);
2479 child.readBuffers(is, clipBBox, fromHalf);
2483 this->
clip(clipBBox);
2490 template<
typename ChildT>
2494 const Tile bgTile(mBackground,
false);
2498 MapType copyOfTable(mTable);
2499 for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) {
2500 const Coord& xyz = i->first;
2501 CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1));
2502 if (!clipBBox.hasOverlap(tileBBox)) {
2504 setTile(this->findCoord(xyz), bgTile);
2506 }
else if (!clipBBox.isInside(tileBBox)) {
2510 getChild(i).clip(clipBBox, mBackground);
2514 tileBBox.intersect(clipBBox);
2515 const Tile& origTile = getTile(i);
2516 setTile(this->findCoord(xyz), bgTile);
2517 this->
sparseFill(tileBBox, origTile.value, origTile.active);
2530 template<
typename ChildT>
2536 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
2537 if (this->isTile(i))
continue;
2538 this->getChild(i).prune(tolerance);
2539 if (this->getChild(i).isConstant(value, state, tolerance)) {
2540 this->setTile(i, Tile(value, state));
2550 template<
typename ChildT>
2551 template<
typename NodeT>
2555 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2556 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2558 MapIter iter = this->findCoord(xyz);
2559 if (iter == mTable.end() || isTile(iter))
return nullptr;
2560 return (std::is_same<NodeT, ChildT>::value)
2561 ?
reinterpret_cast<NodeT*
>(&stealChild(iter, Tile(value, state)))
2562 : getChild(iter).template stealNode<NodeT>(xyz, value, state);
2570 template<
typename ChildT>
2574 if (leaf ==
nullptr)
return;
2575 ChildT* child =
nullptr;
2576 const Coord& xyz = leaf->origin();
2577 MapIter iter = this->findCoord(xyz);
2578 if (iter == mTable.end()) {
2579 if (ChildT::LEVEL>0) {
2580 child =
new ChildT(xyz, mBackground,
false);
2582 child =
reinterpret_cast<ChildT*
>(leaf);
2584 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2585 }
else if (isChild(iter)) {
2586 if (ChildT::LEVEL>0) {
2587 child = &getChild(iter);
2589 child =
reinterpret_cast<ChildT*
>(leaf);
2590 setChild(iter, *child);
2593 if (ChildT::LEVEL>0) {
2594 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2596 child =
reinterpret_cast<ChildT*
>(leaf);
2598 setChild(iter, *child);
2600 child->addLeaf(leaf);
2604 template<
typename ChildT>
2605 template<
typename AccessorT>
2609 if (leaf ==
nullptr)
return;
2610 ChildT* child =
nullptr;
2611 const Coord& xyz = leaf->origin();
2612 MapIter iter = this->findCoord(xyz);
2613 if (iter == mTable.end()) {
2614 if (ChildT::LEVEL>0) {
2615 child =
new ChildT(xyz, mBackground,
false);
2617 child =
reinterpret_cast<ChildT*
>(leaf);
2619 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2620 }
else if (isChild(iter)) {
2621 if (ChildT::LEVEL>0) {
2622 child = &getChild(iter);
2624 child =
reinterpret_cast<ChildT*
>(leaf);
2625 setChild(iter, *child);
2628 if (ChildT::LEVEL>0) {
2629 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2631 child =
reinterpret_cast<ChildT*
>(leaf);
2633 setChild(iter, *child);
2635 acc.insert(xyz, child);
2636 child->addLeafAndCache(leaf, acc);
2639 template<
typename ChildT>
2643 if (!child)
return false;
2644 const Coord& xyz = child->origin();
2645 MapIter iter = this->findCoord(xyz);
2646 if (iter == mTable.end()) {
2647 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2649 setChild(iter, *child);
2654 #if OPENVDB_ABI_VERSION_NUMBER >= 10 2655 template<
typename ChildT>
2660 if (mOrigin != Coord(0,0,0)) {
2666 template<
typename ChildT>
2670 MapIter iter = this->findCoord(xyz);
2671 if (iter == mTable.end()) {
2672 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2674 setTile(iter, Tile(value, state));
2678 template<
typename ChildT>
2683 if (LEVEL >= level) {
2684 MapIter iter = this->findCoord(xyz);
2685 if (iter == mTable.end()) {
2686 if (LEVEL > level) {
2687 ChildT* child =
new ChildT(xyz, mBackground,
false);
2688 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2689 child->addTile(level, xyz, value, state);
2691 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2693 }
else if (isChild(iter)) {
2694 if (LEVEL > level) {
2695 getChild(iter).addTile(level, xyz, value, state);
2697 setTile(iter, Tile(value, state));
2700 if (LEVEL > level) {
2701 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2702 setChild(iter, *child);
2703 child->addTile(level, xyz, value, state);
2705 setTile(iter, Tile(value, state));
2712 template<
typename ChildT>
2713 template<
typename AccessorT>
2716 bool state, AccessorT& acc)
2718 if (LEVEL >= level) {
2719 MapIter iter = this->findCoord(xyz);
2720 if (iter == mTable.end()) {
2721 if (LEVEL > level) {
2722 ChildT* child =
new ChildT(xyz, mBackground,
false);
2723 acc.insert(xyz, child);
2724 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2725 child->addTileAndCache(level, xyz, value, state, acc);
2727 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state));
2729 }
else if (isChild(iter)) {
2730 if (LEVEL > level) {
2731 ChildT* child = &getChild(iter);
2732 acc.insert(xyz, child);
2733 child->addTileAndCache(level, xyz, value, state, acc);
2735 setTile(iter, Tile(value, state));
2738 if (LEVEL > level) {
2739 ChildT* child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2740 acc.insert(xyz, child);
2741 setChild(iter, *child);
2742 child->addTileAndCache(level, xyz, value, state, acc);
2744 setTile(iter, Tile(value, state));
2754 template<
typename ChildT>
2755 inline typename ChildT::LeafNodeType*
2758 ChildT* child =
nullptr;
2759 MapIter iter = this->findCoord(xyz);
2760 if (iter == mTable.end()) {
2761 child =
new ChildT(xyz, mBackground,
false);
2762 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2763 }
else if (isChild(iter)) {
2764 child = &getChild(iter);
2766 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2767 setChild(iter, *child);
2769 return child->touchLeaf(xyz);
2773 template<
typename ChildT>
2774 template<
typename AccessorT>
2775 inline typename ChildT::LeafNodeType*
2778 ChildT* child =
nullptr;
2779 MapIter iter = this->findCoord(xyz);
2780 if (iter == mTable.end()) {
2781 child =
new ChildT(xyz, mBackground,
false);
2782 mTable[this->coordToKey(xyz)] = NodeStruct(*child);
2783 }
else if (isChild(iter)) {
2784 child = &getChild(iter);
2786 child =
new ChildT(xyz, getTile(iter).value, isTileOn(iter));
2787 setChild(iter, *child);
2789 acc.insert(xyz, child);
2790 return child->touchLeafAndCache(xyz, acc);
2797 template<
typename ChildT>
2798 template<
typename NodeT>
2802 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2803 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2805 MapIter iter = this->findCoord(xyz);
2806 if (iter == mTable.end() || isTile(iter))
return nullptr;
2807 ChildT* child = &getChild(iter);
2808 return (std::is_same<NodeT, ChildT>::value)
2809 ?
reinterpret_cast<NodeT*
>(child)
2810 : child->template probeNode<NodeT>(xyz);
2815 template<
typename ChildT>
2816 template<
typename NodeT>
2820 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2821 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2823 MapCIter iter = this->findCoord(xyz);
2824 if (iter == mTable.end() || isTile(iter))
return nullptr;
2825 const ChildT* child = &getChild(iter);
2826 return (std::is_same<NodeT, ChildT>::value)
2827 ?
reinterpret_cast<const NodeT*
>(child)
2828 : child->template probeConstNode<NodeT>(xyz);
2833 template<
typename ChildT>
2834 inline typename ChildT::LeafNodeType*
2837 return this->
template probeNode<LeafNodeType>(xyz);
2841 template<
typename ChildT>
2842 inline const typename ChildT::LeafNodeType*
2845 return this->
template probeConstNode<LeafNodeType>(xyz);
2849 template<
typename ChildT>
2850 template<
typename AccessorT>
2851 inline typename ChildT::LeafNodeType*
2854 return this->
template probeNodeAndCache<LeafNodeType>(xyz, acc);
2858 template<
typename ChildT>
2859 template<
typename AccessorT>
2860 inline const typename ChildT::LeafNodeType*
2863 return this->
template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
2867 template<
typename ChildT>
2868 template<
typename AccessorT>
2869 inline const typename ChildT::LeafNodeType*
2876 template<
typename ChildT>
2877 template<
typename NodeT,
typename AccessorT>
2881 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2882 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2884 MapIter iter = this->findCoord(xyz);
2885 if (iter == mTable.end() || isTile(iter))
return nullptr;
2886 ChildT* child = &getChild(iter);
2887 acc.insert(xyz, child);
2888 return (std::is_same<NodeT, ChildT>::value)
2889 ?
reinterpret_cast<NodeT*
>(child)
2890 : child->template probeNodeAndCache<NodeT>(xyz, acc);
2895 template<
typename ChildT>
2896 template<
typename NodeT,
typename AccessorT>
2900 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
2901 NodeT::LEVEL > ChildT::LEVEL)
return nullptr;
2903 MapCIter iter = this->findCoord(xyz);
2904 if (iter == mTable.end() || isTile(iter))
return nullptr;
2905 const ChildT* child = &getChild(iter);
2906 acc.insert(xyz, child);
2907 return (std::is_same<NodeT, ChildT>::value)
2908 ?
reinterpret_cast<const NodeT*
>(child)
2909 : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
2916 template<
typename ChildT>
2917 template<
typename ArrayT>
2921 using NodePtr =
typename ArrayT::value_type;
2922 static_assert(std::is_pointer<NodePtr>::value,
2923 "argument to getNodes() must be a pointer array");
2924 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2925 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2926 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2927 "can't extract non-const nodes from a const tree");
2928 using ArrayChildT =
typename std::conditional<
2929 std::is_const<NodeType>::value,
const ChildT, ChildT>::type;
2931 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2932 if (ChildT* child = iter->second.child) {
2934 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2935 array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2937 child->getNodes(array);
2944 template<
typename ChildT>
2945 template<
typename ArrayT>
2949 using NodePtr =
typename ArrayT::value_type;
2950 static_assert(std::is_pointer<NodePtr>::value,
2951 "argument to getNodes() must be a pointer array");
2952 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2953 static_assert(std::is_const<NodeType>::value,
2954 "argument to getNodes() must be an array of const node pointers");
2955 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2956 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2957 "can't extract non-const nodes from a const tree");
2959 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2962 if (std::is_same<NodePtr, const ChildT*>::value) {
2963 array.push_back(reinterpret_cast<NodePtr>(iter->second.child));
2965 child->getNodes(array);
2974 template<
typename ChildT>
2975 template<
typename ArrayT>
2979 using NodePtr =
typename ArrayT::value_type;
2980 static_assert(std::is_pointer<NodePtr>::value,
2981 "argument to stealNodes() must be a pointer array");
2982 using NodeType =
typename std::remove_pointer<NodePtr>::type;
2983 using NonConstNodeType =
typename std::remove_const<NodeType>::type;
2984 static_assert(NodeChainType::template Contains<NonConstNodeType>,
2985 "can't extract non-const nodes from a const tree");
2986 using ArrayChildT =
typename std::conditional<
2987 std::is_const<NodeType>::value,
const ChildT, ChildT>::type;
2989 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) {
2990 if (ChildT* child = iter->second.child) {
2992 if (std::is_same<NodePtr, ArrayChildT*>::value) {
2993 array.push_back(reinterpret_cast<NodePtr>(&stealChild(iter, Tile(value, state))));
2995 child->stealNodes(array, value, state);
3006 template<
typename ChildT>
3007 template<MergePolicy Policy>
3017 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3018 MapIter j = mTable.find(i->first);
3019 if (other.isChild(i)) {
3020 if (j == mTable.end()) {
3021 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3022 child.resetBackground(other.mBackground, mBackground);
3023 mTable[i->first] = NodeStruct(child);
3024 }
else if (isTile(j)) {
3026 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3027 child.resetBackground(other.mBackground, mBackground);
3031 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i),
3032 other.mBackground, mBackground);
3034 }
else if (other.isTileOn(i)) {
3035 if (j == mTable.end()) {
3036 mTable[i->first] = i->second;
3037 }
else if (!isTileOn(j)) {
3039 setTile(j, Tile(other.getTile(i).value,
true));
3046 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3047 MapIter j = mTable.find(i->first);
3048 if (other.isChild(i)) {
3049 if (j == mTable.end()) {
3050 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3051 child.resetBackground(other.mBackground, mBackground);
3052 mTable[i->first] = NodeStruct(child);
3053 }
else if (isTile(j)) {
3054 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3055 child.resetBackground(other.mBackground, mBackground);
3058 getChild(j).template merge<MERGE_NODES>(
3059 getChild(i), other.mBackground, mBackground);
3066 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3067 MapIter j = mTable.find(i->first);
3068 if (other.isChild(i)) {
3069 if (j == mTable.end()) {
3071 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3072 child.resetBackground(other.mBackground, mBackground);
3073 mTable[i->first] = NodeStruct(child);
3074 }
else if (isTile(j)) {
3076 ChildNodeType& child = stealChild(i, Tile(other.mBackground,
false));
3077 child.resetBackground(other.mBackground, mBackground);
3078 const Tile tile = getTile(j);
3082 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3083 tile.value, tile.active);
3087 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i),
3088 other.mBackground, mBackground);
3090 }
else if (other.isTileOn(i)) {
3091 if (j == mTable.end()) {
3093 mTable[i->first] = i->second;
3094 }
else if (isTileOff(j)) {
3096 setTile(j, Tile(other.getTile(i).value,
true));
3097 }
else if (isChild(j)) {
3099 const Tile& tile = getTile(i);
3100 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(
3101 tile.value, tile.active);
3118 template<
typename ChildT>
3119 template<
typename OtherChildType>
3124 using OtherCIterT =
typename OtherRootT::MapCIter;
3126 enforceSameConfiguration(other);
3128 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3129 MapIter j = mTable.find(i->first);
3130 if (other.isChild(i)) {
3131 if (j == mTable.end()) {
3132 mTable[i->first] = NodeStruct(
3133 *(
new ChildT(other.getChild(i), mBackground,
TopologyCopy())));
3134 }
else if (this->isChild(j)) {
3135 this->getChild(j).topologyUnion(other.getChild(i), preserveTiles);
3137 if (!preserveTiles || this->isTileOff(j)) {
3138 ChildT* child =
new ChildT(
3139 other.getChild(i), this->getTile(j).value,
TopologyCopy());
3140 if (this->isTileOn(j)) child->setValuesOn();
3141 this->setChild(j, *child);
3144 }
else if (other.isTileOn(i)) {
3145 if (j == mTable.end()) {
3146 mTable[i->first] = NodeStruct(Tile(mBackground,
true));
3147 }
else if (this->isChild(j)) {
3148 this->getChild(j).setValuesOn();
3149 }
else if (this->isTileOff(j)) {
3150 this->setTile(j, Tile(this->getTile(j).value,
true));
3156 template<
typename ChildT>
3157 template<
typename OtherChildType>
3162 using OtherCIterT =
typename OtherRootT::MapCIter;
3164 enforceSameConfiguration(other);
3166 std::set<Coord> tmp;
3167 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) {
3168 OtherCIterT j = other.mTable.find(i->first);
3169 if (this->isChild(i)) {
3170 if (j == other.mTable.end() || other.isTileOff(j)) {
3171 tmp.insert(i->first);
3172 }
else if (other.isChild(j)) {
3173 this->getChild(i).topologyIntersection(other.getChild(j), mBackground);
3175 }
else if (this->isTileOn(i)) {
3176 if (j == other.mTable.end() || other.isTileOff(j)) {
3177 this->setTile(i, Tile(this->getTile(i).value,
false));
3178 }
else if (other.isChild(j)) {
3180 new ChildT(other.getChild(j), this->getTile(i).value,
TopologyCopy());
3181 this->setChild(i, *child);
3185 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) {
3186 MapIter it = this->findCoord(*i);
3187 setTile(it, Tile());
3192 template<
typename ChildT>
3193 template<
typename OtherChildType>
3198 using OtherCIterT =
typename OtherRootT::MapCIter;
3200 enforceSameConfiguration(other);
3202 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) {
3203 MapIter j = mTable.find(i->first);
3204 if (other.isChild(i)) {
3205 if (j == mTable.end() || this->isTileOff(j)) {
3207 }
else if (this->isChild(j)) {
3208 this->getChild(j).topologyDifference(other.getChild(i), mBackground);
3209 }
else if (this->isTileOn(j)) {
3211 ChildT* child =
new ChildT(j->first, this->getTile(j).value,
true);
3212 child->topologyDifference(other.getChild(i), mBackground);
3213 this->setChild(j, *child);
3215 }
else if (other.isTileOn(i)) {
3216 if (j == mTable.end() || this->isTileOff(j)) {
3218 }
else if (this->isChild(j)) {
3221 }
else if (this->isTileOn(j)) {
3222 this->setTile(j, Tile(this->getTile(j).value,
false));
3231 template<
typename ChildT>
3232 template<
typename CombineOp>
3239 this->insertKeys(keys);
3240 other.insertKeys(keys);
3242 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3243 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i);
3244 if (isTile(iter) && isTile(otherIter)) {
3247 op(args.
setARef(getTile(iter).value)
3248 .setAIsActive(isTileOn(iter))
3249 .setBRef(getTile(otherIter).value)
3250 .setBIsActive(isTileOn(otherIter)));
3253 }
else if (isChild(iter) && isTile(otherIter)) {
3255 ChildT& child = getChild(iter);
3256 child.combine(getTile(otherIter).value, isTileOn(otherIter), op);
3258 }
else if (isTile(iter) && isChild(otherIter)) {
3263 ChildT& child = getChild(otherIter);
3264 child.combine(getTile(iter).value, isTileOn(iter), swappedOp);
3267 setChild(iter, stealChild(otherIter, Tile()));
3271 ChildT &child = getChild(iter), &otherChild = getChild(otherIter);
3272 child.combine(otherChild, op);
3274 if (prune && isChild(iter)) getChild(iter).prune();
3278 op(args.
setARef(mBackground).setBRef(other.mBackground));
3279 mBackground = args.
result();
3291 template<
typename CombineOp,
typename RootT,
typename OtherRootT,
bool Compatible = false>
3294 static inline void combine2(RootT&
self,
const RootT&,
const OtherRootT& other1,
3299 self.enforceSameConfiguration(other1);
3300 self.enforceCompatibleValueTypes(other1);
3302 std::ostringstream ostr;
3303 ostr <<
"cannot combine a " <<
typeid(OtherRootT).name()
3304 <<
" into a " <<
typeid(RootT).name();
3310 template<
typename CombineOp,
typename RootT,
typename OtherRootT>
3313 static inline void combine2(RootT&
self,
const RootT& other0,
const OtherRootT& other1,
3314 CombineOp& op,
bool prune)
3316 self.doCombine2(other0, other1, op, prune);
3321 template<
typename ChildT>
3322 template<
typename CombineOp,
typename OtherRootNode>
3325 CombineOp& op,
bool prune)
3327 using OtherValueType =
typename OtherRootNode::ValueType;
3331 *
this, other0, other1, op, prune);
3335 template<
typename ChildT>
3336 template<
typename CombineOp,
typename OtherRootNode>
3339 CombineOp& op,
bool prune)
3341 enforceSameConfiguration(other1);
3343 using OtherValueT =
typename OtherRootNode::ValueType;
3344 using OtherTileT =
typename OtherRootNode::Tile;
3345 using OtherNodeStructT =
typename OtherRootNode::NodeStruct;
3346 using OtherMapCIterT =
typename OtherRootNode::MapCIter;
3351 other0.insertKeys(keys);
3352 other1.insertKeys(keys);
3354 const NodeStruct bg0(Tile(other0.mBackground,
false));
3355 const OtherNodeStructT bg1(OtherTileT(other1.mBackground,
false));
3357 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) {
3358 MapIter thisIter = this->findOrAddCoord(*i);
3359 MapCIter iter0 = other0.findKey(*i);
3360 OtherMapCIterT iter1 = other1.findKey(*i);
3361 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0;
3362 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1;
3363 if (ns0.isTile() && ns1.isTile()) {
3366 op(args.
setARef(ns0.tile.value)
3367 .setAIsActive(ns0.isTileOn())
3368 .setBRef(ns1.tile.value)
3369 .setBIsActive(ns1.isTileOn()));
3372 if (!isChild(thisIter)) {
3374 const Coord& childOrigin =
3375 ns0.isChild() ? ns0.child->origin() : ns1.child->origin();
3376 setChild(thisIter, *(
new ChildT(childOrigin, getTile(thisIter).value)));
3378 ChildT& child = getChild(thisIter);
3383 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op);
3384 }
else if (ns1.isTile()) {
3387 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op);
3391 child.combine2(*ns0.child, *ns1.child, op);
3394 if (prune && isChild(thisIter)) getChild(thisIter).prune();
3398 op(args.
setARef(other0.mBackground).setBRef(other1.mBackground));
3399 mBackground = args.
result();
3407 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: RootNode.h:1789
Definition: RootNode.h:32
RootNode(const RootNode< OtherChildType > &other)
Construct a new tree that reproduces the topology and active states of a tree of a different ValueTyp...
Definition: RootNode.h:84
typename ChildType::LeafNodeType LeafNodeType
Definition: RootNode.h:42
Definition: Exceptions.h:65
const Coord & origin() const
Return the grid index coordinates of this node's local origin.
Definition: RootNode.h:885
OPENVDB_API uint32_t getFormatVersion(std::ios_base &)
Return the file format version number associated with the given input stream.
Coord getMinIndex() const
Return the smallest index of the current tree.
Definition: RootNode.h:1354
size_t eraseBackgroundTiles()
Remove all background tiles.
Definition: RootNode.h:1292
CanConvertType<FromType, ToType>::value is true if a value of type ToType can be constructed from a v...
Definition: Types.h:403
const ValueType & getValueAndCache(const Coord &xyz, AccessorT &) const
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:504
ValueOffIter beginValueOff()
Definition: RootNode.h:392
ChildAllCIter beginChildAll() const
Definition: RootNode.h:380
void denseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value and ensure that those voxels are a...
Definition: RootNode.h:2186
static CoordBBox getNodeBoundingBox()
Return the bounding box of this RootNode, i.e., an infinite bounding box.
Definition: RootNode.h:406
bool isOn(Index32 i) const
Definition: NodeMasks.h:1331
bool probeValueAndCache(const Coord &xyz, ValueType &value, AccessorT &) const
Definition: RootNode.h:2108
Index32 nonLeafCount() const
Definition: RootNode.h:1582
ValueIter< RootNode, MapIter, ValueOnPred, ValueType > ValueOnIter
Definition: RootNode.h:367
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
ValueAllCIter cbeginValueAll() const
Definition: RootNode.h:387
constexpr T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:70
static void combine2(RootT &self, const RootT &other0, const OtherRootT &other1, CombineOp &op, bool prune)
Definition: RootNode.h:3313
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: RootNode.h:2919
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
void copyToDense(const CoordBBox &bbox, DenseT &dense) const
Copy into a dense grid the values of all voxels, both active and inactive, that intersect a given bou...
Definition: RootNode.h:2262
void nodeCount(std::vector< Index32 > &vec) const
Definition: RootNode.h:1678
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:443
Index32 FindHighestOn(Index32 v)
Return the most significant on bit of the given 32-bit value.
Definition: NodeMasks.h:159
CombineArgs & setARef(const AValueType &a)
Redirect the A value to a new external source.
Definition: Types.h:621
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2835
static const Index LEVEL
Definition: RootNode.h:46
void setBackground(const ValueType &value, bool updateChildNodes)
Change inactive tiles or voxels with a value equal to +/- the old background to the specified value (...
Definition: RootNode.h:1231
bool operator!=(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Inequality operator, does exact floating point comparisons.
Definition: Vec3.h:481
ValueOnCIter beginValueOn() const
Definition: RootNode.h:388
ValueOnCIter cbeginValueOn() const
Definition: RootNode.h:385
ValueAllCIter beginValueAll() const
Definition: RootNode.h:390
Index32 childCount() const
Definition: RootNode.h:1596
void modifyValueAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:1998
ValueIter< const RootNode, MapCIter, ChildOffPred, ValueType > ChildOffCIter
Definition: RootNode.h:363
A list of types (not necessarily unique)
Definition: TypeList.h:577
Definition: RootNode.h:34
Definition: RootNode.h:38
void addLeafAndCache(LeafNodeType *leaf, AccessorT &)
Same as addLeaf() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2607
const AValueType & result() const
Get the output value.
Definition: Types.h:613
void sparseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:537
typename ChildType::ValueType ValueType
Definition: RootNode.h:43
void writeBuffers(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2448
Index getHeight() const
Definition: RootNode.h:461
void load(std::istream &is)
Definition: NodeMasks.h:1372
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:568
bool writeTopology(std::ostream &, bool toHalf=false) const
Definition: RootNode.h:2306
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: RootNode.h:1966
DenseIter< const RootNode, MapCIter, const ChildType, const ValueType > ChildAllCIter
Definition: RootNode.h:365
Index getTableSize() const
Return the number of entries in this node's table.
Definition: RootNode.h:458
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:597
void combine2(const RootNode &other0, const OtherRootNode &other1, CombineOp &op, bool prune=false)
Definition: RootNode.h:3324
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:2977
static void combine2(RootT &self, const RootT &, const OtherRootT &other1, CombineOp &, bool)
Definition: RootNode.h:3294
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: RootNode.h:2034
Index64 onLeafVoxelCount() const
Definition: RootNode.h:1640
LeafNodeType * probeLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don't change its active state.
Definition: RootNode.h:1924
ChildOffIter beginChildOff()
Definition: RootNode.h:382
void evalActiveBoundingBox(CoordBBox &bbox, bool visitVoxels=true) const
Expand the specified bbox so it includes the active tiles of this root node as well as all the active...
Definition: RootNode.h:1513
ChildOnCIter beginChildOn() const
Definition: RootNode.h:378
bool readTopology(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2342
NodeT * probeNodeAndCache(const Coord &xyz, AccessorT &acc)
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2879
ChildOnCIter cbeginChildOn() const
Definition: RootNode.h:375
void setTransientData(Index32 transientData)
Set the transient data value.
Definition: RootNode.h:411
BBox< Coord > CoordBBox
Definition: NanoVDB.h:2535
size_t numBackgroundTiles() const
Return the number of background tiles.
Definition: RootNode.h:1280
void setValueOn(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: RootNode.h:1883
uint64_t Index64
Definition: Types.h:53
void readBuffers(std::istream &, bool fromHalf=false)
Definition: RootNode.h:2458
static bool hasSameConfiguration(const RootNode< OtherChildType > &other)
Return false if the other node's dimensions don't match this node's.
Definition: RootNode.h:1429
ChildOffCIter beginChildOff() const
Definition: RootNode.h:379
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:683
RootNode()
Construct a new tree with a background value of 0.
Definition: RootNode.h:1032
T truncateRealToHalf(const T &val)
Return the given value truncated to 16-bit float precision.
Definition: Compression.h:216
static Index getLevel()
Definition: RootNode.h:453
bool addChild(ChildType *child)
Add the given child node at the root level. If a child node with the same origin already exists...
bool isBackgroundTile(const Tile &) const
Return true if the given tile is inactive and has the background value.
Definition: RootNode.h:1258
void topologyIntersection(const RootNode< OtherChildType > &other)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
Definition: RootNode.h:3159
void setValueAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1902
ChildIter< const RootNode, MapCIter, ChildOnPred, const ChildType > ChildOnCIter
Definition: RootNode.h:361
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: RootNode.h:2756
bool probeValue(const Coord &xyz, ValueType &value) const
Definition: RootNode.h:2092
static Index getChildDim()
Definition: RootNode.h:455
const NodeT * probeConstNode(const Coord &xyz) const
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2818
void merge(RootNode &other)
Efficiently merge another tree into this tree using one of several schemes.
Definition: RootNode.h:3009
Definition: RootNode.h:33
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2843
Index64 onVoxelCount() const
Definition: RootNode.h:1608
int getValueDepthAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1763
NodeT * probeNode(const Coord &xyz)
Return a pointer to the node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: RootNode.h:2800
void modifyValueAndActiveStateAndCache(const Coord &xyz, const ModifyOp &op, AccessorT &)
Definition: RootNode.h:2061
ChildOnIter beginChildOn()
Definition: RootNode.h:381
void setValueOffAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1859
Index64 offVoxelCount() const
Definition: RootNode.h:1624
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: RootNode.h:2128
bool isApproxEqual(const Type &a, const Type &b, const Type &tolerance)
Return true if a is equal to b to within the given tolerance.
Definition: Math.h:406
Index64 offLeafVoxelCount() const
Definition: RootNode.h:1652
Definition: Exceptions.h:13
RootNode & operator=(const RootNode &other)
Copy a root node of the same type as this node.
Definition: RootNode.h:1189
Definition: Exceptions.h:64
Index getDepth() const
Definition: RootNode.h:462
ValueOffCIter beginValueOff() const
Definition: RootNode.h:389
ChildAllCIter cbeginChildAll() const
Definition: RootNode.h:377
void stealNodes(ArrayT &array)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: RootNode.h:816
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: RootNode.h:2572
ValueIter< RootNode, MapIter, ChildOffPred, const ValueType > ChildOffIter
Definition: RootNode.h:362
bool expand(const Coord &xyz)
Expand this node's table so that (x, y, z) is included in the index range.
Definition: RootNode.h:1331
typename ChildType::BuildType BuildType
Definition: RootNode.h:44
ValueIter< const RootNode, MapCIter, ValueAllPred, const ValueType > ValueAllCIter
Definition: RootNode.h:372
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition: RootNode.h:2532
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: RootNode.h:1753
Index32 leafCount() const
Definition: RootNode.h:1570
ChildType ChildNodeType
Definition: RootNode.h:41
Index32 Index
Definition: Types.h:54
ValueIter< RootNode, MapIter, ValueAllPred, ValueType > ValueAllIter
Definition: RootNode.h:371
void setValueOnlyAndCache(const Coord &xyz, const ValueType &value, AccessorT &)
Definition: RootNode.h:1943
Index32 transientData() const
Return the transient data value.
Definition: RootNode.h:409
ValueConverter<T>::Type is the type of a RootNode having the same child hierarchy as this node but a ...
Definition: RootNode.h:56
void clear()
Definition: RootNode.h:1502
Index64 onTileCount() const
Definition: RootNode.h:1663
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool state)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition: RootNode.h:2553
Index64 memUsage() const
Return the total amount of memory in bytes occupied by this node and its children.
Definition: RootNode.h:1488
bool hasActiveTiles() const
Return true if this root node, or any of its child nodes, have active tiles.
Definition: RootNode.h:1706
static void getNodeLog2Dims(std::vector< Index > &dims)
Definition: RootNode.h:1345
const LeafNodeType * probeConstLeafAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
RootNode(const RootNode &other)
Definition: RootNode.h:75
void setActiveStateAndCache(const Coord &xyz, bool on, AccessorT &)
Definition: RootNode.h:1812
Coord getMaxIndex() const
Return the largest index of the current tree.
Definition: RootNode.h:1361
bool empty() const
Return true if this node's table is either empty or contains only background tiles.
Definition: RootNode.h:446
void topologyDifference(const RootNode< OtherChildType > &other)
Difference this tree's set of active values with the active values of the other tree, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this tree and inactive in the other tree.
Definition: RootNode.h:3195
const ValueType & background() const
Return this node's background value.
Definition: RootNode.h:428
void setOrigin(const Coord &origin)
change the origin on this root node
Definition: RootNode.h:2657
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: RootNode.h:1775
ValueAllIter beginValueAll()
Definition: RootNode.h:393
ValueOffCIter cbeginValueOff() const
Definition: RootNode.h:386
DenseIter< RootNode, MapIter, ChildType, ValueType > ChildAllIter
Definition: RootNode.h:364
ValueIter< const RootNode, MapCIter, ValueOffPred, const ValueType > ValueOffCIter
Definition: RootNode.h:370
static bool hasCompatibleValueType(const RootNode< OtherChildType > &other)
Definition: RootNode.h:1461
Definition: version.h.in:246
Definition: NodeMasks.h:1066
SameConfiguration<OtherNodeType>::value is true if and only if OtherNodeType is the type of a RootNod...
Definition: RootNode.h:64
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1144
LeafNodeType * touchLeafAndCache(const Coord &xyz, AccessorT &acc)
Same as touchLeaf() but, if necessary, update the given accessor with pointers to the nodes along the...
ValueOnIter beginValueOn()
Definition: RootNode.h:391
Index getWidth() const
Definition: RootNode.h:460
typename NodeChain< RootNode, LEVEL >::Type NodeChainType
NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. ...
Definition: RootNode.h:49
void addTile(const Coord &xyz, const ValueType &value, bool state)
Add a tile containing voxel (x, y, z) at the root level, deleting the existing branch if necessary...
Definition: RootNode.h:2668
static void copyWithValueConversion(RootT &self, const OtherRootT &other)
Definition: RootNode.h:1126
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
ValueIter< const RootNode, MapCIter, ValueOnPred, const ValueType > ValueOnCIter
Definition: RootNode.h:368
bool resultIsActive() const
Definition: Types.h:632
void combine(RootNode &other, CombineOp &, bool prune=false)
Definition: RootNode.h:3234
ValueType combine(const ValueType &v0, const ValueType &v1, const ValueType &v2, const openvdb::Vec3d &w)
Combine different value types.
Definition: AttributeTransferUtil.h:141
const NodeT * probeConstNodeAndCache(const Coord &xyz, AccessorT &acc) const
Same as probeNode() but, if necessary, update the given accessor with pointers to the nodes along the...
Definition: RootNode.h:2898
bool isValueOn(const Coord &xyz) const
Definition: RootNode.h:1697
bool hasSameTopology(const RootNode< OtherChildType > &other) const
Return true if the given tree has the same node and active value topology as this tree (but possibly ...
Definition: RootNode.h:1382
int32_t Int32
Definition: Types.h:56
void getIndexRange(CoordBBox &bbox) const
Return the current index range. Both min and max are inclusive.
Definition: RootNode.h:1369
void addTileAndCache(Index level, const Coord &xyz, const ValueType &, bool state, AccessorT &)
Same as addTile() but, if necessary, update the given accessor with pointers to the nodes along the p...
Definition: RootNode.h:2715
void topologyUnion(const RootNode< OtherChildType > &other, const bool preserveTiles=false)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition: RootNode.h:3121
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: RootNode.h:2492
ValueIter< RootNode, MapIter, ValueOffPred, ValueType > ValueOffIter
Definition: RootNode.h:369
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:473
NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList that lists the types of the...
Definition: RootNode.h:31
~RootNode()
Definition: RootNode.h:123
typename NodeChain< typename HeadT::ChildNodeType, HeadLevel-1 >::Type SubtreeT
Definition: RootNode.h:998
bool isValueOnAndCache(const Coord &xyz, AccessorT &) const
Definition: RootNode.h:1717
uint32_t Index32
Definition: Types.h:52
typename SubtreeT::template Append< HeadT > Type
Definition: RootNode.h:999
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
const ValueType & getValue(const Coord &xyz) const
Definition: RootNode.h:1729
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: RootNode.h:2236
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:128
ChildAllIter beginChildAll()
Definition: RootNode.h:383
ChildIter< RootNode, MapIter, ChildOnPred, ChildType > ChildOnIter
Definition: RootNode.h:360
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:689
ChildOffCIter cbeginChildOff() const
Definition: RootNode.h:376
OPENVDB_API void setGridBackgroundValuePtr(std::ios_base &, const void *background)
Specify (a pointer to) the background value of the grid currently being read from or written to the g...