1 // Copyright Contributors to the OpenVDB Project 2 // SPDX-License-Identifier: MPL-2.0 3 /// 4 /// @file RootNode.h 5 /// 6 /// @brief The root node of an OpenVDB tree 7 8 #ifndef OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED 9 #define OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED 10 11 #include <openvdb/Exceptions.h> 12 #include <openvdb/Types.h> 13 #include <openvdb/io/Compression.h> // for truncateRealToHalf() 14 #include <openvdb/math/Math.h> // for isZero(), isExactlyEqual(), etc. 15 #include <openvdb/math/BBox.h> 16 #include <openvdb/util/NodeMasks.h> // for backward compatibility only (see readTopology()) 17 #include <openvdb/version.h> 18 #include <tbb/parallel_for.h> 19 #include <map> 20 #include <set> 21 #include <sstream> 22 #include <vector> 23 24 25 namespace openvdb { 26 OPENVDB_USE_VERSION_NAMESPACE 27 namespace OPENVDB_VERSION_NAME { 28 namespace tree { 29 30 // Forward declarations 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; 35 36 37 template<typename ChildType> 38 class RootNode 39 { 40 public: 41 using ChildNodeType = ChildType; 42 using LeafNodeType = typename ChildType::LeafNodeType; 43 using ValueType = typename ChildType::ValueType; 44 using BuildType = typename ChildType::BuildType; 45 46 static const Index LEVEL = 1 + ChildType::LEVEL; // level 0 = leaf 47 48 /// NodeChainType is a list of this tree's node types, from LeafNodeType to RootNode. 49 using NodeChainType = typename NodeChain<RootNode, LEVEL>::Type; 50 static_assert(NodeChainType::Size == LEVEL + 1, 51 "wrong number of entries in RootNode node chain"); 52 53 /// @brief ValueConverter<T>::Type is the type of a RootNode having the same 54 /// child hierarchy as this node but a different value type, T. 55 template<typename OtherValueType> 56 struct ValueConverter { 57 using Type = RootNode<typename ChildType::template ValueConverter<OtherValueType>::Type>; 58 }; 59 60 /// @brief SameConfiguration<OtherNodeType>::value is @c true if and only if 61 /// OtherNodeType is the type of a RootNode whose ChildNodeType has the same 62 /// configuration as this node's ChildNodeType. 63 template<typename OtherNodeType> 64 struct SameConfiguration { 65 static const bool value = SameRootConfig<ChildNodeType, OtherNodeType>::value; 66 }; 67 68 69 /// Construct a new tree with a background value of 0. 70 RootNode(); 71 72 /// Construct a new tree with the given background value. 73 explicit RootNode(const ValueType& background); 74 RootNode(const RootNode & other)75 RootNode(const RootNode& other) { *this = other; } 76 77 /// @brief Construct a new tree that reproduces the topology and active states 78 /// of a tree of a different ValueType but the same configuration (levels, 79 /// node dimensions and branching factors). Cast the other tree's values to 80 /// this tree's ValueType. 81 /// @throw TypeError if the other tree's configuration doesn't match this tree's 82 /// or if this tree's ValueType is not constructible from the other tree's ValueType. 83 template<typename OtherChildType> RootNode(const RootNode<OtherChildType> & other)84 explicit RootNode(const RootNode<OtherChildType>& other) { *this = other; } 85 86 /// @brief Construct a new tree that reproduces the topology and active states of 87 /// another tree (which may have a different ValueType), but not the other tree's values. 88 /// @details All tiles and voxels that are active in the other tree are set to 89 /// @a foreground in the new tree, and all inactive tiles and voxels are set to @a background. 90 /// @param other the root node of a tree having (possibly) a different ValueType 91 /// @param background the value to which inactive tiles and voxels are initialized 92 /// @param foreground the value to which active tiles and voxels are initialized 93 /// @throw TypeError if the other tree's configuration doesn't match this tree's. 94 template<typename OtherChildType> 95 RootNode(const RootNode<OtherChildType>& other, 96 const ValueType& background, const ValueType& foreground, TopologyCopy); 97 98 /// @brief Construct a new tree that reproduces the topology and active states of 99 /// another tree (which may have a different ValueType), but not the other tree's values. 100 /// All tiles and voxels in the new tree are set to @a background regardless of 101 /// their active states in the other tree. 102 /// @param other the root node of a tree having (possibly) a different ValueType 103 /// @param background the value to which inactive tiles and voxels are initialized 104 /// @note This copy constructor is generally faster than the one that takes both 105 /// a foreground and a background value. Its main application is in multithreaded 106 /// operations where the topology of the output tree exactly matches the input tree. 107 /// @throw TypeError if the other tree's configuration doesn't match this tree's. 108 template<typename OtherChildType> 109 RootNode(const RootNode<OtherChildType>& other, const ValueType& background, TopologyCopy); 110 111 /// @brief Copy a root node of the same type as this node. 112 RootNode& operator=(const RootNode& other); 113 /// @brief Copy a root node of the same tree configuration as this node 114 /// but a different ValueType. 115 /// @throw TypeError if the other tree's configuration doesn't match this tree's. 116 /// @note This node's ValueType must be constructible from the other node's ValueType. 117 /// For example, a root node with values of type float can be assigned to a root node 118 /// with values of type Vec3s, because a Vec3s can be constructed from a float. 119 /// But a Vec3s root node cannot be assigned to a float root node. 120 template<typename OtherChildType> 121 RootNode& operator=(const RootNode<OtherChildType>& other); 122 ~RootNode()123 ~RootNode() { this->clear(); } 124 125 private: 126 struct Tile { TileTile127 Tile(): value(zeroVal<ValueType>()), active(false) {} TileTile128 Tile(const ValueType& v, bool b): value(v), active(b) {} 129 ValueType value; 130 bool active; 131 }; 132 133 // This lightweight struct pairs child pointers and tiles. 134 struct NodeStruct { 135 ChildType* child; 136 Tile tile; 137 NodeStructNodeStruct138 NodeStruct(): child(nullptr) {} NodeStructNodeStruct139 NodeStruct(ChildType& c): child(&c) {} NodeStructNodeStruct140 NodeStruct(const Tile& t): child(nullptr), tile(t) {} 141 NodeStruct(const NodeStruct&) = default; 142 NodeStruct& operator=(const NodeStruct&) = default; ~NodeStructNodeStruct143 ~NodeStruct() {} ///< @note doesn't delete child 144 isChildNodeStruct145 bool isChild() const { return child != nullptr; } isTileNodeStruct146 bool isTile() const { return child == nullptr; } isTileOffNodeStruct147 bool isTileOff() const { return isTile() && !tile.active; } isTileOnNodeStruct148 bool isTileOn() const { return isTile() && tile.active; } 149 setNodeStruct150 void set(ChildType& c) { delete child; child = &c; } setNodeStruct151 void set(const Tile& t) { delete child; child = nullptr; tile = t; } stealNodeStruct152 ChildType& steal(const Tile& t) { ChildType* c=child; child=nullptr; tile=t; return *c; } 153 }; 154 155 using MapType = std::map<Coord, NodeStruct>; 156 using MapIter = typename MapType::iterator; 157 using MapCIter = typename MapType::const_iterator; 158 159 using CoordSet = std::set<Coord>; 160 using CoordSetIter = typename CoordSet::iterator; 161 using CoordSetCIter = typename CoordSet::const_iterator; 162 setTile(const MapIter & i,const Tile & t)163 static void setTile(const MapIter& i, const Tile& t) { i->second.set(t); } setChild(const MapIter & i,ChildType & c)164 static void setChild(const MapIter& i, ChildType& c) { i->second.set(c); } getTile(const MapIter & i)165 static Tile& getTile(const MapIter& i) { return i->second.tile; } getTile(const MapCIter & i)166 static const Tile& getTile(const MapCIter& i) { return i->second.tile; } getChild(const MapIter & i)167 static ChildType& getChild(const MapIter& i) { return *(i->second.child); } getChild(const MapCIter & i)168 static const ChildType& getChild(const MapCIter& i) { return *(i->second.child); } stealChild(const MapIter & i,const Tile & t)169 static ChildType& stealChild(const MapIter& i, const Tile& t) {return i->second.steal(t);} stealChild(const MapCIter & i,const Tile & t)170 static const ChildType& stealChild(const MapCIter& i,const Tile& t) {return i->second.steal(t);} 171 isChild(const MapCIter & i)172 static bool isChild(const MapCIter& i) { return i->second.isChild(); } isChild(const MapIter & i)173 static bool isChild(const MapIter& i) { return i->second.isChild(); } isTile(const MapCIter & i)174 static bool isTile(const MapCIter& i) { return i->second.isTile(); } isTile(const MapIter & i)175 static bool isTile(const MapIter& i) { return i->second.isTile(); } isTileOff(const MapCIter & i)176 static bool isTileOff(const MapCIter& i) { return i->second.isTileOff(); } isTileOff(const MapIter & i)177 static bool isTileOff(const MapIter& i) { return i->second.isTileOff(); } isTileOn(const MapCIter & i)178 static bool isTileOn(const MapCIter& i) { return i->second.isTileOn(); } isTileOn(const MapIter & i)179 static bool isTileOn(const MapIter& i) { return i->second.isTileOn(); } 180 181 struct NullPred { testNullPred182 static inline bool test(const MapIter&) { return true; } testNullPred183 static inline bool test(const MapCIter&) { return true; } 184 }; 185 struct ValueOnPred { testValueOnPred186 static inline bool test(const MapIter& i) { return isTileOn(i); } testValueOnPred187 static inline bool test(const MapCIter& i) { return isTileOn(i); } 188 }; 189 struct ValueOffPred { testValueOffPred190 static inline bool test(const MapIter& i) { return isTileOff(i); } testValueOffPred191 static inline bool test(const MapCIter& i) { return isTileOff(i); } 192 }; 193 struct ValueAllPred { testValueAllPred194 static inline bool test(const MapIter& i) { return isTile(i); } testValueAllPred195 static inline bool test(const MapCIter& i) { return isTile(i); } 196 }; 197 struct ChildOnPred { testChildOnPred198 static inline bool test(const MapIter& i) { return isChild(i); } testChildOnPred199 static inline bool test(const MapCIter& i) { return isChild(i); } 200 }; 201 struct ChildOffPred { testChildOffPred202 static inline bool test(const MapIter& i) { return isTile(i); } testChildOffPred203 static inline bool test(const MapCIter& i) { return isTile(i); } 204 }; 205 206 template<typename _RootNodeT, typename _MapIterT, typename FilterPredT> 207 class BaseIter 208 { 209 public: 210 using RootNodeT = _RootNodeT; 211 using MapIterT = _MapIterT; // either MapIter or MapCIter 212 213 bool operator==(const BaseIter& other) const 214 { 215 return (mParentNode == other.mParentNode) && (mIter == other.mIter); 216 } 217 bool operator!=(const BaseIter& other) const { return !(*this == other); } 218 getParentNode()219 RootNodeT* getParentNode() const { return mParentNode; } 220 /// Return a reference to the node over which this iterator iterates. parent()221 RootNodeT& parent() const 222 { 223 if (!mParentNode) OPENVDB_THROW(ValueError, "iterator references a null parent node"); 224 return *mParentNode; 225 } 226 test()227 bool test() const { assert(mParentNode); return mIter != mParentNode->mTable.end(); } 228 operator bool() const { return this->test(); } 229 increment()230 void increment() { if (this->test()) { ++mIter; } this->skip(); } next()231 bool next() { this->increment(); return this->test(); } increment(Index n)232 void increment(Index n) { for (Index i = 0; i < n && this->next(); ++i) {} } 233 234 /// @brief Return this iterator's position as an offset from 235 /// the beginning of the parent node's map. pos()236 Index pos() const 237 { 238 return !mParentNode ? 0U : Index(std::distance(mParentNode->mTable.begin(), mIter)); 239 } 240 isValueOn()241 bool isValueOn() const { return RootNodeT::isTileOn(mIter); } isValueOff()242 bool isValueOff() const { return RootNodeT::isTileOff(mIter); } 243 void setValueOn(bool on = true) const { mIter->second.tile.active = on; } setValueOff()244 void setValueOff() const { mIter->second.tile.active = false; } 245 246 /// Return the coordinates of the item to which this iterator is pointing. getCoord()247 Coord getCoord() const { return mIter->first; } 248 /// Return in @a xyz the coordinates of the item to which this iterator is pointing. getCoord(Coord & xyz)249 void getCoord(Coord& xyz) const { xyz = this->getCoord(); } 250 251 protected: BaseIter()252 BaseIter(): mParentNode(nullptr) {} BaseIter(RootNodeT & parent,const MapIterT & iter)253 BaseIter(RootNodeT& parent, const MapIterT& iter): mParentNode(&parent), mIter(iter) {} 254 skip()255 void skip() { while (this->test() && !FilterPredT::test(mIter)) ++mIter; } 256 257 RootNodeT* mParentNode; 258 MapIterT mIter; 259 }; // BaseIter 260 261 template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ChildNodeT> 262 class ChildIter: public BaseIter<RootNodeT, MapIterT, FilterPredT> 263 { 264 public: 265 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>; 266 using NodeType = RootNodeT; 267 using ValueType = NodeType; 268 using ChildNodeType = ChildNodeT; 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; 272 using BaseT::mIter; 273 ChildIter()274 ChildIter() {} ChildIter(RootNodeT & parent,const MapIterT & iter)275 ChildIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); } 276 277 ChildIter& operator++() { BaseT::increment(); return *this; } 278 getValue()279 ChildNodeT& getValue() const { return getChild(mIter); } 280 ChildNodeT& operator*() const { return this->getValue(); } 281 ChildNodeT* operator->() const { return &this->getValue(); } 282 }; // ChildIter 283 284 template<typename RootNodeT, typename MapIterT, typename FilterPredT, typename ValueT> 285 class ValueIter: public BaseIter<RootNodeT, MapIterT, FilterPredT> 286 { 287 public: 288 using BaseT = BaseIter<RootNodeT, MapIterT, FilterPredT>; 289 using NodeType = RootNodeT; 290 using ValueType = ValueT; 291 using NonConstNodeType = typename std::remove_const<NodeType>::type; 292 using NonConstValueType = typename std::remove_const<ValueT>::type; 293 using BaseT::mIter; 294 ValueIter()295 ValueIter() {} ValueIter(RootNodeT & parent,const MapIterT & iter)296 ValueIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) { BaseT::skip(); } 297 298 ValueIter& operator++() { BaseT::increment(); return *this; } 299 getValue()300 ValueT& getValue() const { return getTile(mIter).value; } 301 ValueT& operator*() const { return this->getValue(); } 302 ValueT* operator->() const { return &(this->getValue()); } 303 setValue(const ValueT & v)304 void setValue(const ValueT& v) const { assert(isTile(mIter)); getTile(mIter).value = v; } 305 306 template<typename ModifyOp> modifyValue(const ModifyOp & op)307 void modifyValue(const ModifyOp& op) const 308 { 309 assert(isTile(mIter)); 310 op(getTile(mIter).value); 311 } 312 }; // ValueIter 313 314 template<typename RootNodeT, typename MapIterT, typename ChildNodeT, typename ValueT> 315 class DenseIter: public BaseIter<RootNodeT, MapIterT, NullPred> 316 { 317 public: 318 using BaseT = BaseIter<RootNodeT, MapIterT, NullPred>; 319 using NodeType = RootNodeT; 320 using ValueType = ValueT; 321 using ChildNodeType = ChildNodeT; 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; 325 using BaseT::mIter; 326 DenseIter()327 DenseIter() {} DenseIter(RootNodeT & parent,const MapIterT & iter)328 DenseIter(RootNodeT& parent, const MapIterT& iter): BaseT(parent, iter) {} 329 330 DenseIter& operator++() { BaseT::increment(); return *this; } 331 isChildNode()332 bool isChildNode() const { return isChild(mIter); } 333 probeChild(NonConstValueType & value)334 ChildNodeT* probeChild(NonConstValueType& value) const 335 { 336 if (isChild(mIter)) return &getChild(mIter); 337 value = getTile(mIter).value; 338 return nullptr; 339 } probeChild(ChildNodeT * & child,NonConstValueType & value)340 bool probeChild(ChildNodeT*& child, NonConstValueType& value) const 341 { 342 child = this->probeChild(value); 343 return child != nullptr; 344 } probeValue(NonConstValueType & value)345 bool probeValue(NonConstValueType& value) const { return !this->probeChild(value); } 346 setChild(ChildNodeT & c)347 void setChild(ChildNodeT& c) const { RootNodeT::setChild(mIter, c); } setChild(ChildNodeT * c)348 void setChild(ChildNodeT* c) const { assert(c != nullptr); RootNodeT::setChild(mIter, *c); } setValue(const ValueT & v)349 void setValue(const ValueT& v) const 350 { 351 if (isTile(mIter)) getTile(mIter).value = v; 352 /// @internal For consistency with iterators for other node types 353 /// (see, e.g., InternalNode::DenseIter::unsetItem()), we don't call 354 /// setTile() here, because that would also delete the child. 355 else stealChild(mIter, Tile(v, /*active=*/true)); 356 } 357 }; // DenseIter 358 359 public: 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>; 366 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>; 373 374 cbeginChildOn()375 ChildOnCIter cbeginChildOn() const { return ChildOnCIter(*this, mTable.begin()); } cbeginChildOff()376 ChildOffCIter cbeginChildOff() const { return ChildOffCIter(*this, mTable.begin()); } cbeginChildAll()377 ChildAllCIter cbeginChildAll() const { return ChildAllCIter(*this, mTable.begin()); } beginChildOn()378 ChildOnCIter beginChildOn() const { return cbeginChildOn(); } beginChildOff()379 ChildOffCIter beginChildOff() const { return cbeginChildOff(); } beginChildAll()380 ChildAllCIter beginChildAll() const { return cbeginChildAll(); } beginChildOn()381 ChildOnIter beginChildOn() { return ChildOnIter(*this, mTable.begin()); } beginChildOff()382 ChildOffIter beginChildOff() { return ChildOffIter(*this, mTable.begin()); } beginChildAll()383 ChildAllIter beginChildAll() { return ChildAllIter(*this, mTable.begin()); } 384 cbeginValueOn()385 ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this, mTable.begin()); } cbeginValueOff()386 ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this, mTable.begin()); } cbeginValueAll()387 ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this, mTable.begin()); } beginValueOn()388 ValueOnCIter beginValueOn() const { return cbeginValueOn(); } beginValueOff()389 ValueOffCIter beginValueOff() const { return cbeginValueOff(); } beginValueAll()390 ValueAllCIter beginValueAll() const { return cbeginValueAll(); } beginValueOn()391 ValueOnIter beginValueOn() { return ValueOnIter(*this, mTable.begin()); } beginValueOff()392 ValueOffIter beginValueOff() { return ValueOffIter(*this, mTable.begin()); } beginValueAll()393 ValueAllIter beginValueAll() { return ValueAllIter(*this, mTable.begin()); } 394 395 /// Return the total amount of memory in bytes occupied by this node and its children. 396 Index64 memUsage() const; 397 398 /// @brief Expand the specified bbox so it includes the active tiles of 399 /// this root node as well as all the active values in its child 400 /// nodes. If visitVoxels is false LeafNodes will be approximated 401 /// as dense, i.e. with all voxels active. Else the individual 402 /// active voxels are visited to produce a tight bbox. 403 void evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels = true) const; 404 405 /// Return the bounding box of this RootNode, i.e., an infinite bounding box. getNodeBoundingBox()406 static CoordBBox getNodeBoundingBox() { return CoordBBox::inf(); } 407 408 #if OPENVDB_ABI_VERSION_NUMBER >= 9 409 /// Return the transient data value. transientData()410 Index32 transientData() const { return mTransientData; } 411 /// Set the transient data value. setTransientData(Index32 transientData)412 void setTransientData(Index32 transientData) { mTransientData = transientData; } 413 #endif 414 415 /// @brief Change inactive tiles or voxels with a value equal to +/- the 416 /// old background to the specified value (with the same sign). Active values 417 /// are unchanged. 418 /// 419 /// @param value The new background value 420 /// @param updateChildNodes If true the background values of the 421 /// child nodes is also updated. Else only the background value 422 /// stored in the RootNode itself is changed. 423 /// 424 /// @note Instead of setting @a updateChildNodes to true, consider 425 /// using tools::changeBackground or 426 /// tools::changeLevelSetBackground which are multi-threaded! 427 void setBackground(const ValueType& value, bool updateChildNodes); 428 429 /// Return this node's background value. background()430 const ValueType& background() const { return mBackground; } 431 432 /// Return @c true if the given tile is inactive and has the background value. 433 bool isBackgroundTile(const Tile&) const; 434 //@{ 435 /// Return @c true if the given iterator points to an inactive tile with the background value. 436 bool isBackgroundTile(const MapIter&) const; 437 bool isBackgroundTile(const MapCIter&) const; 438 //@} 439 440 /// Return the number of background tiles. 441 size_t numBackgroundTiles() const; 442 /// @brief Remove all background tiles. 443 /// @return the number of tiles removed. 444 size_t eraseBackgroundTiles(); 445 inline void clear(); 446 447 /// Return @c true if this node's table is either empty or contains only background tiles. empty()448 bool empty() const { return mTable.size() == numBackgroundTiles(); } 449 450 /// @brief Expand this node's table so that (x, y, z) is included in the index range. 451 /// @return @c true if an expansion was performed (i.e., if (x, y, z) was not already 452 /// included in the index range). 453 bool expand(const Coord& xyz); 454 getLevel()455 static Index getLevel() { return LEVEL; } 456 static void getNodeLog2Dims(std::vector<Index>& dims); getChildDim()457 static Index getChildDim() { return ChildType::DIM; } 458 459 /// Return the number of entries in this node's table. getTableSize()460 Index getTableSize() const { return static_cast<Index>(mTable.size()); } 461 getWidth()462 Index getWidth() const { return this->getMaxIndex()[0] - this->getMinIndex()[0]; } getHeight()463 Index getHeight() const { return this->getMaxIndex()[1] - this->getMinIndex()[1]; } getDepth()464 Index getDepth() const { return this->getMaxIndex()[2] - this->getMinIndex()[2]; } 465 466 /// Return the smallest index of the current tree. 467 Coord getMinIndex() const; 468 /// Return the largest index of the current tree. 469 Coord getMaxIndex() const; 470 /// Return the current index range. Both min and max are inclusive. 471 void getIndexRange(CoordBBox& bbox) const; 472 473 /// @brief Return @c true if the given tree has the same node and active value 474 /// topology as this tree (but possibly a different @c ValueType). 475 template<typename OtherChildType> 476 bool hasSameTopology(const RootNode<OtherChildType>& other) const; 477 478 /// Return @c false if the other node's dimensions don't match this node's. 479 template<typename OtherChildType> 480 static bool hasSameConfiguration(const RootNode<OtherChildType>& other); 481 482 /// Return @c true if values of the other node's ValueType can be converted 483 /// to values of this node's ValueType. 484 template<typename OtherChildType> 485 static bool hasCompatibleValueType(const RootNode<OtherChildType>& other); 486 487 Index32 leafCount() const; 488 Index32 nonLeafCount() const; 489 Index32 childCount() const; 490 Index64 onVoxelCount() const; 491 Index64 offVoxelCount() const; 492 Index64 onLeafVoxelCount() const; 493 Index64 offLeafVoxelCount() const; 494 Index64 onTileCount() const; 495 void nodeCount(std::vector<Index32> &vec) const; 496 497 bool isValueOn(const Coord& xyz) const; 498 499 /// Return @c true if this root node, or any of its child nodes, have active tiles. 500 bool hasActiveTiles() const; 501 502 const ValueType& getValue(const Coord& xyz) const; 503 bool probeValue(const Coord& xyz, ValueType& value) const; 504 505 /// @brief Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides. 506 /// @details If (x, y, z) isn't explicitly represented in the tree (i.e., 507 /// it is implicitly a background voxel), return -1. 508 int getValueDepth(const Coord& xyz) const; 509 510 /// Set the active state of the voxel at the given coordinates but don't change its value. 511 void setActiveState(const Coord& xyz, bool on); 512 /// Set the value of the voxel at the given coordinates but don't change its active state. 513 void setValueOnly(const Coord& xyz, const ValueType& value); 514 /// Set the value of the voxel at the given coordinates and mark the voxel as active. 515 void setValueOn(const Coord& xyz, const ValueType& value); 516 /// Mark the voxel at the given coordinates as inactive but don't change its value. 517 void setValueOff(const Coord& xyz); 518 /// Set the value of the voxel at the given coordinates and mark the voxel as inactive. 519 void setValueOff(const Coord& xyz, const ValueType& value); 520 521 /// @brief Apply a functor to the value of the voxel at the given coordinates 522 /// and mark the voxel as active. 523 template<typename ModifyOp> 524 void modifyValue(const Coord& xyz, const ModifyOp& op); 525 /// Apply a functor to the voxel at the given coordinates. 526 template<typename ModifyOp> 527 void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op); 528 529 //@{ 530 /// @brief Set all voxels within a given axis-aligned box to a constant value. 531 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box 532 /// @param value the value to which to set voxels within the box 533 /// @param active if true, mark voxels within the box as active, 534 /// otherwise mark them as inactive 535 /// @note This operation generates a sparse, but not always optimally sparse, 536 /// representation of the filled box. Follow fill operations with a prune() 537 /// operation for optimal sparseness. 538 void fill(const CoordBBox& bbox, const ValueType& value, bool active = true); 539 void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true) 540 { 541 this->fill(bbox, value, active); 542 } 543 //@} 544 545 /// @brief Set all voxels within a given axis-aligned box to a constant value 546 /// and ensure that those voxels are all represented at the leaf level. 547 /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box. 548 /// @param value the value to which to set voxels within the box. 549 /// @param active if true, mark voxels within the box as active, 550 /// otherwise mark them as inactive. 551 /// @sa voxelizeActiveTiles() 552 void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true); 553 554 /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels. 555 /// 556 /// @param threaded if true, this operation is multi-threaded (over the internal nodes). 557 /// 558 /// @warning This method can explode the tree's memory footprint, especially if it 559 /// contains active tiles at the upper levels (in particular the root level)! 560 /// 561 /// @sa denseFill() 562 void voxelizeActiveTiles(bool threaded = true); 563 564 /// @brief Copy into a dense grid the values of all voxels, both active and inactive, 565 /// that intersect a given bounding box. 566 /// @param bbox inclusive bounding box of the voxels to be copied into the dense grid 567 /// @param dense dense grid with a stride in @e z of one (see tools::Dense 568 /// in tools/Dense.h for the required API) 569 template<typename DenseT> 570 void copyToDense(const CoordBBox& bbox, DenseT& dense) const; 571 572 573 // 574 // I/O 575 // 576 bool writeTopology(std::ostream&, bool toHalf = false) const; 577 bool readTopology(std::istream&, bool fromHalf = false); 578 579 void writeBuffers(std::ostream&, bool toHalf = false) const; 580 void readBuffers(std::istream&, bool fromHalf = false); 581 void readBuffers(std::istream&, const CoordBBox&, bool fromHalf = false); 582 583 584 // 585 // Voxel access 586 // 587 /// Return the value of the voxel at the given coordinates and, if necessary, update 588 /// the accessor with pointers to the nodes along the path from the root node to 589 /// the node containing the voxel. 590 /// @note Used internally by ValueAccessor. 591 template<typename AccessorT> 592 const ValueType& getValueAndCache(const Coord& xyz, AccessorT&) const; 593 /// Return @c true if the voxel at the given coordinates is active and, if necessary, 594 /// update the accessor with pointers to the nodes along the path from the root node 595 /// to the node containing the voxel. 596 /// @note Used internally by ValueAccessor. 597 template<typename AccessorT> 598 bool isValueOnAndCache(const Coord& xyz, AccessorT&) const; 599 600 /// Change the value of the voxel at the given coordinates and mark it as active. 601 /// If necessary, update the accessor with pointers to the nodes along the path 602 /// from the root node to the node containing the voxel. 603 /// @note Used internally by ValueAccessor. 604 template<typename AccessorT> 605 void setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT&); 606 607 /// Set the value of the voxel at the given coordinates without changing its active state. 608 /// If necessary, update the accessor with pointers to the nodes along the path 609 /// from the root node to the node containing the voxel. 610 /// @note Used internally by ValueAccessor. 611 template<typename AccessorT> 612 void setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT&); 613 614 /// Apply a functor to the value of the voxel at the given coordinates 615 /// and mark the voxel as active. 616 /// If necessary, update the accessor with pointers to the nodes along the path 617 /// from the root node to the node containing the voxel. 618 /// @note Used internally by ValueAccessor. 619 template<typename ModifyOp, typename AccessorT> 620 void modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&); 621 622 /// Apply a functor to the voxel at the given coordinates. 623 /// If necessary, update the accessor with pointers to the nodes along the path 624 /// from the root node to the node containing the voxel. 625 /// @note Used internally by ValueAccessor. 626 template<typename ModifyOp, typename AccessorT> 627 void modifyValueAndActiveStateAndCache(const Coord& xyz, const ModifyOp& op, AccessorT&); 628 629 /// Change the value of the voxel at the given coordinates and mark it as inactive. 630 /// If necessary, update the accessor with pointers to the nodes along the path 631 /// from the root node to the node containing the voxel. 632 /// @note Used internally by ValueAccessor. 633 template<typename AccessorT> 634 void setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT&); 635 636 /// Set the active state of the voxel at the given coordinates without changing its value. 637 /// If necessary, update the accessor with pointers to the nodes along the path 638 /// from the root node to the node containing the voxel. 639 /// @note Used internally by ValueAccessor. 640 template<typename AccessorT> 641 void setActiveStateAndCache(const Coord& xyz, bool on, AccessorT&); 642 643 /// Return, in @a value, the value of the voxel at the given coordinates and, 644 /// if necessary, update the accessor with pointers to the nodes along 645 /// the path from the root node to the node containing the voxel. 646 /// @return @c true if the voxel at the given coordinates is active 647 /// @note Used internally by ValueAccessor. 648 template<typename AccessorT> 649 bool probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT&) const; 650 651 /// Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides. 652 /// If (x, y, z) isn't explicitly represented in the tree (i.e., it is implicitly 653 /// a background voxel), return -1. If necessary, update the accessor with pointers 654 /// to the nodes along the path from the root node to the node containing the voxel. 655 /// @note Used internally by ValueAccessor. 656 template<typename AccessorT> 657 int getValueDepthAndCache(const Coord& xyz, AccessorT&) const; 658 659 /// Set all voxels that lie outside the given axis-aligned box to the background. 660 void clip(const CoordBBox&); 661 662 /// @brief Reduce the memory footprint of this tree by replacing with tiles 663 /// any nodes whose values are all the same (optionally to within a tolerance) 664 /// and have the same active state. 665 /// 666 /// @note Consider instead using tools::prune which is multi-threaded! 667 void prune(const ValueType& tolerance = zeroVal<ValueType>()); 668 669 /// @brief Add the given leaf node to this tree, creating a new branch if necessary. 670 /// If a leaf node with the same origin already exists, replace it. 671 void addLeaf(LeafNodeType* leaf); 672 673 /// @brief Same as addLeaf() but, if necessary, update the given accessor with pointers 674 /// to the nodes along the path from the root node to the node containing the coordinate. 675 template<typename AccessorT> 676 void addLeafAndCache(LeafNodeType* leaf, AccessorT&); 677 678 /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z) 679 /// and replace it with a tile of the specified value and state. 680 /// If no such node exists, leave the tree unchanged and return @c nullptr. 681 /// 682 /// @note The caller takes ownership of the node and is responsible for deleting it. 683 /// 684 /// @warning Since this method potentially removes nodes and branches of the tree, 685 /// it is important to clear the caches of all ValueAccessors associated with this tree. 686 template<typename NodeT> 687 NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state); 688 689 /// @brief Add the given child node at the root level. 690 /// If a child node with the same origin already exists, delete the old node and add 691 /// the new node in its place (i.e. ownership of the new child node is transferred 692 /// to this RootNode). 693 /// @return @c true (for consistency with InternalNode::addChild) 694 bool addChild(ChildType* child); 695 696 /// @brief Add a tile containing voxel (x, y, z) at the root level, 697 /// deleting the existing branch if necessary. 698 void addTile(const Coord& xyz, const ValueType& value, bool state); 699 700 /// @brief Add a tile containing voxel (x, y, z) at the specified tree level, 701 /// creating a new branch if necessary. Delete any existing lower-level nodes 702 /// that contain (x, y, z). 703 void addTile(Index level, const Coord& xyz, const ValueType& value, bool state); 704 705 /// @brief Same as addTile() but, if necessary, update the given accessor with pointers 706 /// to the nodes along the path from the root node to the node containing the coordinate. 707 template<typename AccessorT> 708 void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&); 709 710 /// @brief Return a pointer to the leaf node that contains voxel (x, y, z). 711 /// If no such node exists, create one that preserves the values and 712 /// active states of all voxels. 713 /// @details Use this method to preallocate a static tree topology 714 /// over which to safely perform multithreaded processing. 715 LeafNodeType* touchLeaf(const Coord& xyz); 716 717 /// @brief Same as touchLeaf() but, if necessary, update the given accessor with pointers 718 /// to the nodes along the path from the root node to the node containing the coordinate. 719 template<typename AccessorT> 720 LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT& acc); 721 722 //@{ 723 /// @brief Return a pointer to the node that contains voxel (x, y, z). 724 /// If no such node exists, return @c nullptr. 725 template <typename NodeT> 726 NodeT* probeNode(const Coord& xyz); 727 template <typename NodeT> 728 const NodeT* probeConstNode(const Coord& xyz) const; 729 //@} 730 731 //@{ 732 /// @brief Same as probeNode() but, if necessary, update the given accessor with pointers 733 /// to the nodes along the path from the root node to the node containing the coordinate. 734 template<typename NodeT, typename AccessorT> 735 NodeT* probeNodeAndCache(const Coord& xyz, AccessorT& acc); 736 template<typename NodeT, typename AccessorT> 737 const NodeT* probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const; 738 //@} 739 740 //@{ 741 /// @brief Return a pointer to the leaf node that contains voxel (x, y, z). 742 /// If no such node exists, return @c nullptr. 743 LeafNodeType* probeLeaf(const Coord& xyz); 744 const LeafNodeType* probeConstLeaf(const Coord& xyz) const; 745 const LeafNodeType* probeLeaf(const Coord& xyz) const; 746 //@} 747 748 //@{ 749 /// @brief Same as probeLeaf() but, if necessary, update the given accessor with pointers 750 /// to the nodes along the path from the root node to the node containing the coordinate. 751 template<typename AccessorT> 752 LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc); 753 template<typename AccessorT> 754 const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const; 755 template<typename AccessorT> 756 const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const; 757 //@} 758 759 760 // 761 // Aux methods 762 // 763 764 //@{ 765 /// @brief Adds all nodes of a certain type to a container with the following API: 766 /// @code 767 /// struct ArrayT { 768 /// using value_type = ...;// defines the type of nodes to be added to the array 769 /// void push_back(value_type nodePtr);// method that add nodes to the array 770 /// }; 771 /// @endcode 772 /// @details An example of a wrapper around a c-style array is: 773 /// @code 774 /// struct MyArray { 775 /// using value_type = LeafType*; 776 /// value_type* ptr; 777 /// MyArray(value_type* array) : ptr(array) {} 778 /// void push_back(value_type leaf) { *ptr++ = leaf; } 779 ///}; 780 /// @endcode 781 /// @details An example that constructs a list of pointer to all leaf nodes is: 782 /// @code 783 /// std::vector<const LeafNodeType*> array;//most std contains have the required API 784 /// array.reserve(tree.leafCount());//this is a fast preallocation. 785 /// tree.getNodes(array); 786 /// @endcode 787 template<typename ArrayT> void getNodes(ArrayT& array); 788 template<typename ArrayT> void getNodes(ArrayT& array) const; 789 //@} 790 791 //@{ 792 /// @brief Steals all nodes of a certain type from the tree and 793 /// adds them to a container with the following API: 794 /// @code 795 /// struct ArrayT { 796 /// using value_type = ...;// defines the type of nodes to be added to the array 797 /// void push_back(value_type nodePtr);// method that add nodes to the array 798 /// }; 799 /// @endcode 800 /// @details An example of a wrapper around a c-style array is: 801 /// @code 802 /// struct MyArray { 803 /// using value_type = LeafType*; 804 /// value_type* ptr; 805 /// MyArray(value_type* array) : ptr(array) {} 806 /// void push_back(value_type leaf) { *ptr++ = leaf; } 807 ///}; 808 /// @endcode 809 /// @details An example that constructs a list of pointer to all leaf nodes is: 810 /// @code 811 /// std::vector<const LeafNodeType*> array;//most std contains have the required API 812 /// array.reserve(tree.leafCount());//this is a fast preallocation. 813 /// tree.stealNodes(array); 814 /// @endcode 815 template<typename ArrayT> 816 void stealNodes(ArrayT& array, const ValueType& value, bool state); 817 template<typename ArrayT> stealNodes(ArrayT & array)818 void stealNodes(ArrayT& array) { this->stealNodes(array, mBackground, false); } 819 //@} 820 821 /// @brief Efficiently merge another tree into this tree using one of several schemes. 822 /// @details This operation is primarily intended to combine trees that are mostly 823 /// non-overlapping (for example, intermediate trees from computations that are 824 /// parallelized across disjoint regions of space). 825 /// @note This operation is not guaranteed to produce an optimally sparse tree. 826 /// Follow merge() with prune() for optimal sparseness. 827 /// @warning This operation always empties the other tree. 828 template<MergePolicy Policy> void merge(RootNode& other); 829 830 /// @brief Union this tree's set of active values with the active values 831 /// of the other tree, whose @c ValueType may be different. 832 /// @details The resulting state of a value is active if the corresponding value 833 /// was already active OR if it is active in the other tree. Also, a resulting 834 /// value maps to a voxel if the corresponding value already mapped to a voxel 835 /// OR if it is a voxel in the other tree. Thus, a resulting value can only 836 /// map to a tile if the corresponding value already mapped to a tile 837 /// AND if it is a tile value in other tree. 838 /// 839 /// @note This operation modifies only active states, not values. 840 /// Specifically, active tiles and voxels in this tree are not changed, and 841 /// tiles or voxels that were inactive in this tree but active in the other tree 842 /// are marked as active in this tree but left with their original values. 843 /// 844 /// @note If preserveTiles is true, any active tile in this topology 845 /// will not be densified by overlapping child topology. 846 template<typename OtherChildType> 847 void topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles = false); 848 849 /// @brief Intersects this tree's set of active values with the active values 850 /// of the other tree, whose @c ValueType may be different. 851 /// @details The resulting state of a value is active only if the corresponding 852 /// value was already active AND if it is active in the other tree. Also, a 853 /// resulting value maps to a voxel if the corresponding value 854 /// already mapped to an active voxel in either of the two grids 855 /// and it maps to an active tile or voxel in the other grid. 856 /// 857 /// @note This operation can delete branches in this grid if they 858 /// overlap with inactive tiles in the other grid. Likewise active 859 /// voxels can be turned into inactive voxels resulting in leaf 860 /// nodes with no active values. Thus, it is recommended to 861 /// subsequently call prune. 862 template<typename OtherChildType> 863 void topologyIntersection(const RootNode<OtherChildType>& other); 864 865 /// @brief Difference this tree's set of active values with the active values 866 /// of the other tree, whose @c ValueType may be different. So a 867 /// resulting voxel will be active only if the original voxel is 868 /// active in this tree and inactive in the other tree. 869 /// 870 /// @note This operation can delete branches in this grid if they 871 /// overlap with active tiles in the other grid. Likewise active 872 /// voxels can be turned into inactive voxels resulting in leaf 873 /// nodes with no active values. Thus, it is recommended to 874 /// subsequently call prune. 875 template<typename OtherChildType> 876 void topologyDifference(const RootNode<OtherChildType>& other); 877 878 template<typename CombineOp> 879 void combine(RootNode& other, CombineOp&, bool prune = false); 880 881 template<typename CombineOp, typename OtherRootNode /*= RootNode*/> 882 void combine2(const RootNode& other0, const OtherRootNode& other1, 883 CombineOp& op, bool prune = false); 884 885 /// @brief Call the templated functor BBoxOp with bounding box 886 /// information for all active tiles and leaf nodes in the tree. 887 /// An additional level argument is provided for each callback. 888 /// 889 /// @note The bounding boxes are guaranteed to be non-overlapping. 890 template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const; 891 892 template<typename VisitorOp> void visit(VisitorOp&); 893 template<typename VisitorOp> void visit(VisitorOp&) const; 894 895 template<typename OtherRootNodeType, typename VisitorOp> 896 void visit2(OtherRootNodeType& other, VisitorOp&); 897 template<typename OtherRootNodeType, typename VisitorOp> 898 void visit2(OtherRootNodeType& other, VisitorOp&) const; 899 900 private: 901 /// During topology-only construction, access is needed 902 /// to protected/private members of other template instances. 903 template<typename> friend class RootNode; 904 905 template<typename, typename, bool> friend struct RootNodeCopyHelper; 906 template<typename, typename, typename, bool> friend struct RootNodeCombineHelper; 907 908 /// Currently no-op, but can be used to define empty and delete keys for mTable initTable()909 void initTable() {} 910 //@{ 911 /// @internal Used by doVisit2(). resetTable(MapType & table)912 void resetTable(MapType& table) { mTable.swap(table); table.clear(); } resetTable(const MapType &)913 void resetTable(const MapType&) const {} 914 //@} 915 916 #if OPENVDB_ABI_VERSION_NUMBER < 8 917 Index getChildCount() const; 918 #endif 919 Index getTileCount() const; 920 Index getActiveTileCount() const; 921 Index getInactiveTileCount() const; 922 923 /// Return a MapType key for the given coordinates. coordToKey(const Coord & xyz)924 static Coord coordToKey(const Coord& xyz) { return xyz & ~(ChildType::DIM - 1); } 925 926 /// Insert this node's mTable keys into the given set. 927 void insertKeys(CoordSet&) const; 928 929 /// Return @c true if this node's mTable contains the given key. hasKey(const Coord & key)930 bool hasKey(const Coord& key) const { return mTable.find(key) != mTable.end(); } 931 //@{ 932 /// @brief Look up the given key in this node's mTable. 933 /// @return an iterator pointing to the matching mTable entry or to mTable.end(). findKey(const Coord & key)934 MapIter findKey(const Coord& key) { return mTable.find(key); } findKey(const Coord & key)935 MapCIter findKey(const Coord& key) const { return mTable.find(key); } 936 //@} 937 //@{ 938 /// @brief Convert the given coordinates to a key and look the key up in this node's mTable. 939 /// @return an iterator pointing to the matching mTable entry or to mTable.end(). findCoord(const Coord & xyz)940 MapIter findCoord(const Coord& xyz) { return mTable.find(coordToKey(xyz)); } findCoord(const Coord & xyz)941 MapCIter findCoord(const Coord& xyz) const { return mTable.find(coordToKey(xyz)); } 942 //@} 943 /// @brief Convert the given coordinates to a key and look the key up in this node's mTable. 944 /// @details If the key is not found, insert a background tile with that key. 945 /// @return an iterator pointing to the matching mTable entry. 946 MapIter findOrAddCoord(const Coord& xyz); 947 948 /// @brief Verify that the tree rooted at @a other has the same configuration 949 /// (levels, branching factors and node dimensions) as this tree, but allow 950 /// their ValueTypes to differ. 951 /// @throw TypeError if the other tree's configuration doesn't match this tree's. 952 template<typename OtherChildType> 953 static void enforceSameConfiguration(const RootNode<OtherChildType>& other); 954 955 /// @brief Verify that @a other has values of a type that can be converted 956 /// to this node's ValueType. 957 /// @details For example, values of type float are compatible with values of type Vec3s, 958 /// because a Vec3s can be constructed from a float. But the reverse is not true. 959 /// @throw TypeError if the other node's ValueType is not convertible into this node's. 960 template<typename OtherChildType> 961 static void enforceCompatibleValueTypes(const RootNode<OtherChildType>& other); 962 963 template<typename CombineOp, typename OtherRootNode /*= RootNode*/> 964 void doCombine2(const RootNode&, const OtherRootNode&, CombineOp&, bool prune); 965 966 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT> 967 static inline void doVisit(RootNodeT&, VisitorOp&); 968 969 template<typename RootNodeT, typename OtherRootNodeT, typename VisitorOp, 970 typename ChildAllIterT, typename OtherChildAllIterT> 971 static inline void doVisit2(RootNodeT&, OtherRootNodeT&, VisitorOp&); 972 973 974 MapType mTable; 975 ValueType mBackground; 976 #if OPENVDB_ABI_VERSION_NUMBER >= 9 977 /// Transient Data (not serialized) 978 Index32 mTransientData = 0; 979 #endif 980 }; // end of RootNode class 981 982 983 //////////////////////////////////////// 984 985 986 /// @brief NodeChain<RootNodeType, RootNodeType::LEVEL>::Type is a openvdb::TypeList 987 /// that lists the types of the nodes of the tree rooted at RootNodeType in reverse order, 988 /// from LeafNode to RootNode. 989 /// @details For example, if RootNodeType is 990 /// @code 991 /// RootNode<InternalNode<InternalNode<LeafNode> > > 992 /// @endcode 993 /// then NodeChain::Type is 994 /// @code 995 /// openvdb::TypeList< 996 /// LeafNode, 997 /// InternalNode<LeafNode>, 998 /// InternalNode<InternalNode<LeafNode> >, 999 /// RootNode<InternalNode<InternalNode<LeafNode> > > > 1000 /// @endcode 1001 /// 1002 /// @note Use the following to get the Nth node type, where N=0 is the LeafNodeType: 1003 /// @code 1004 /// NodeChainType::Get<N>; 1005 /// @endcode 1006 template<typename HeadT, int HeadLevel> 1007 struct NodeChain { 1008 using SubtreeT = typename NodeChain<typename HeadT::ChildNodeType, HeadLevel-1>::Type; 1009 using Type = typename SubtreeT::template Append<HeadT>; 1010 }; 1011 1012 /// Specialization to terminate NodeChain 1013 template<typename HeadT> 1014 struct NodeChain<HeadT, /*HeadLevel=*/1> { 1015 using Type = TypeList<typename HeadT::ChildNodeType, HeadT>; 1016 }; 1017 1018 1019 //////////////////////////////////////// 1020 1021 1022 //@{ 1023 /// Helper metafunction used to implement RootNode::SameConfiguration 1024 /// (which, as an inner class, can't be independently specialized) 1025 template<typename ChildT1, typename NodeT2> 1026 struct SameRootConfig { 1027 static const bool value = false; 1028 }; 1029 1030 template<typename ChildT1, typename ChildT2> 1031 struct SameRootConfig<ChildT1, RootNode<ChildT2> > { 1032 static const bool value = ChildT1::template SameConfiguration<ChildT2>::value; 1033 }; 1034 //@} 1035 1036 1037 //////////////////////////////////////// 1038 1039 1040 template<typename ChildT> 1041 inline 1042 RootNode<ChildT>::RootNode(): mBackground(zeroVal<ValueType>()) 1043 { 1044 this->initTable(); 1045 } 1046 1047 1048 template<typename ChildT> 1049 inline 1050 RootNode<ChildT>::RootNode(const ValueType& background): mBackground(background) 1051 { 1052 this->initTable(); 1053 } 1054 1055 1056 template<typename ChildT> 1057 template<typename OtherChildType> 1058 inline 1059 RootNode<ChildT>::RootNode(const RootNode<OtherChildType>& other, 1060 const ValueType& backgd, const ValueType& foregd, TopologyCopy) 1061 : mBackground(backgd) 1062 #if OPENVDB_ABI_VERSION_NUMBER >= 9 1063 , mTransientData(other.mTransientData) 1064 #endif 1065 { 1066 using OtherRootT = RootNode<OtherChildType>; 1067 1068 enforceSameConfiguration(other); 1069 1070 const Tile bgTile(backgd, /*active=*/false), fgTile(foregd, true); 1071 this->initTable(); 1072 1073 for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) { 1074 mTable[i->first] = OtherRootT::isTile(i) 1075 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile) 1076 : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, foregd, TopologyCopy()))); 1077 } 1078 } 1079 1080 1081 template<typename ChildT> 1082 template<typename OtherChildType> 1083 inline 1084 RootNode<ChildT>::RootNode(const RootNode<OtherChildType>& other, 1085 const ValueType& backgd, TopologyCopy) 1086 : mBackground(backgd) 1087 #if OPENVDB_ABI_VERSION_NUMBER >= 9 1088 , mTransientData(other.mTransientData) 1089 #endif 1090 { 1091 using OtherRootT = RootNode<OtherChildType>; 1092 1093 enforceSameConfiguration(other); 1094 1095 const Tile bgTile(backgd, /*active=*/false), fgTile(backgd, true); 1096 this->initTable(); 1097 for (typename OtherRootT::MapCIter i=other.mTable.begin(), e=other.mTable.end(); i != e; ++i) { 1098 mTable[i->first] = OtherRootT::isTile(i) 1099 ? NodeStruct(OtherRootT::isTileOn(i) ? fgTile : bgTile) 1100 : NodeStruct(*(new ChildT(OtherRootT::getChild(i), backgd, TopologyCopy()))); 1101 } 1102 } 1103 1104 1105 //////////////////////////////////////// 1106 1107 1108 // This helper class is a friend of RootNode and is needed so that assignment 1109 // with value conversion can be specialized for compatible and incompatible 1110 // pairs of RootNode types. 1111 template<typename RootT, typename OtherRootT, bool Compatible = false> 1112 struct RootNodeCopyHelper 1113 { 1114 static inline void copyWithValueConversion(RootT& self, const OtherRootT& other) 1115 { 1116 // If the two root nodes have different configurations or incompatible ValueTypes, 1117 // throw an exception. 1118 self.enforceSameConfiguration(other); 1119 self.enforceCompatibleValueTypes(other); 1120 // One of the above two tests should throw, so we should never get here: 1121 std::ostringstream ostr; 1122 ostr << "cannot convert a " << typeid(OtherRootT).name() 1123 << " to a " << typeid(RootT).name(); 1124 OPENVDB_THROW(TypeError, ostr.str()); 1125 } 1126 }; 1127 1128 // Specialization for root nodes of compatible types 1129 template<typename RootT, typename OtherRootT> 1130 struct RootNodeCopyHelper<RootT, OtherRootT, /*Compatible=*/true> 1131 { 1132 static inline void copyWithValueConversion(RootT& self, const OtherRootT& other) 1133 { 1134 using ValueT = typename RootT::ValueType; 1135 using ChildT = typename RootT::ChildNodeType; 1136 using NodeStruct = typename RootT::NodeStruct; 1137 using Tile = typename RootT::Tile; 1138 using OtherValueT = typename OtherRootT::ValueType; 1139 using OtherMapCIter = typename OtherRootT::MapCIter; 1140 using OtherTile = typename OtherRootT::Tile; 1141 1142 struct Local { 1143 /// @todo Consider using a value conversion functor passed as an argument instead. 1144 static inline ValueT convertValue(const OtherValueT& val) { return ValueT(val); } 1145 }; 1146 1147 self.mBackground = Local::convertValue(other.mBackground); 1148 #if OPENVDB_ABI_VERSION_NUMBER >= 9 1149 self.mTransientData = other.mTransientData; 1150 #endif 1151 1152 self.clear(); 1153 self.initTable(); 1154 1155 for (OtherMapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 1156 if (other.isTile(i)) { 1157 // Copy the other node's tile, but convert its value to this node's ValueType. 1158 const OtherTile& otherTile = other.getTile(i); 1159 self.mTable[i->first] = NodeStruct( 1160 Tile(Local::convertValue(otherTile.value), otherTile.active)); 1161 } else { 1162 // Copy the other node's child, but convert its values to this node's ValueType. 1163 self.mTable[i->first] = NodeStruct(*(new ChildT(other.getChild(i)))); 1164 } 1165 } 1166 } 1167 }; 1168 1169 1170 // Overload for root nodes of the same type as this node 1171 template<typename ChildT> 1172 inline RootNode<ChildT>& 1173 RootNode<ChildT>::operator=(const RootNode& other) 1174 { 1175 if (&other != this) { 1176 mBackground = other.mBackground; 1177 #if OPENVDB_ABI_VERSION_NUMBER >= 9 1178 mTransientData = other.mTransientData; 1179 #endif 1180 1181 this->clear(); 1182 this->initTable(); 1183 1184 for (MapCIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 1185 mTable[i->first] = 1186 isTile(i) ? NodeStruct(getTile(i)) : NodeStruct(*(new ChildT(getChild(i)))); 1187 } 1188 } 1189 return *this; 1190 } 1191 1192 // Overload for root nodes of different types 1193 template<typename ChildT> 1194 template<typename OtherChildType> 1195 inline RootNode<ChildT>& 1196 RootNode<ChildT>::operator=(const RootNode<OtherChildType>& other) 1197 { 1198 using OtherRootT = RootNode<OtherChildType>; 1199 using OtherValueT = typename OtherRootT::ValueType; 1200 static const bool compatible = (SameConfiguration<OtherRootT>::value 1201 && CanConvertType</*from=*/OtherValueT, /*to=*/ValueType>::value); 1202 RootNodeCopyHelper<RootNode, OtherRootT, compatible>::copyWithValueConversion(*this, other); 1203 return *this; 1204 } 1205 1206 1207 //////////////////////////////////////// 1208 1209 template<typename ChildT> 1210 inline void 1211 RootNode<ChildT>::setBackground(const ValueType& background, bool updateChildNodes) 1212 { 1213 if (math::isExactlyEqual(background, mBackground)) return; 1214 1215 if (updateChildNodes) { 1216 // Traverse the tree, replacing occurrences of mBackground with background 1217 // and -mBackground with -background. 1218 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 1219 ChildT *child = iter->second.child; 1220 if (child) { 1221 child->resetBackground(/*old=*/mBackground, /*new=*/background); 1222 } else { 1223 Tile& tile = getTile(iter); 1224 if (tile.active) continue;//only change inactive tiles 1225 if (math::isApproxEqual(tile.value, mBackground)) { 1226 tile.value = background; 1227 } else if (math::isApproxEqual(tile.value, math::negative(mBackground))) { 1228 tile.value = math::negative(background); 1229 } 1230 } 1231 } 1232 } 1233 mBackground = background; 1234 } 1235 1236 template<typename ChildT> 1237 inline bool 1238 RootNode<ChildT>::isBackgroundTile(const Tile& tile) const 1239 { 1240 return !tile.active && math::isApproxEqual(tile.value, mBackground); 1241 } 1242 1243 template<typename ChildT> 1244 inline bool 1245 RootNode<ChildT>::isBackgroundTile(const MapIter& iter) const 1246 { 1247 return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground); 1248 } 1249 1250 template<typename ChildT> 1251 inline bool 1252 RootNode<ChildT>::isBackgroundTile(const MapCIter& iter) const 1253 { 1254 return isTileOff(iter) && math::isApproxEqual(getTile(iter).value, mBackground); 1255 } 1256 1257 1258 template<typename ChildT> 1259 inline size_t 1260 RootNode<ChildT>::numBackgroundTiles() const 1261 { 1262 size_t count = 0; 1263 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1264 if (this->isBackgroundTile(i)) ++count; 1265 } 1266 return count; 1267 } 1268 1269 1270 template<typename ChildT> 1271 inline size_t 1272 RootNode<ChildT>::eraseBackgroundTiles() 1273 { 1274 std::set<Coord> keysToErase; 1275 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1276 if (this->isBackgroundTile(i)) keysToErase.insert(i->first); 1277 } 1278 for (std::set<Coord>::iterator i = keysToErase.begin(), e = keysToErase.end(); i != e; ++i) { 1279 mTable.erase(*i); 1280 } 1281 return keysToErase.size(); 1282 } 1283 1284 1285 //////////////////////////////////////// 1286 1287 1288 template<typename ChildT> 1289 inline void 1290 RootNode<ChildT>::insertKeys(CoordSet& keys) const 1291 { 1292 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1293 keys.insert(i->first); 1294 } 1295 } 1296 1297 1298 template<typename ChildT> 1299 inline typename RootNode<ChildT>::MapIter 1300 RootNode<ChildT>::findOrAddCoord(const Coord& xyz) 1301 { 1302 const Coord key = coordToKey(xyz); 1303 std::pair<MapIter, bool> result = mTable.insert( 1304 typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false)))); 1305 return result.first; 1306 } 1307 1308 1309 template<typename ChildT> 1310 inline bool 1311 RootNode<ChildT>::expand(const Coord& xyz) 1312 { 1313 const Coord key = coordToKey(xyz); 1314 std::pair<MapIter, bool> result = mTable.insert( 1315 typename MapType::value_type(key, NodeStruct(Tile(mBackground, /*active=*/false)))); 1316 return result.second; // return true if the key did not already exist 1317 } 1318 1319 1320 //////////////////////////////////////// 1321 1322 1323 template<typename ChildT> 1324 inline void 1325 RootNode<ChildT>::getNodeLog2Dims(std::vector<Index>& dims) 1326 { 1327 dims.push_back(0); // magic number; RootNode has no Log2Dim 1328 ChildT::getNodeLog2Dims(dims); 1329 } 1330 1331 1332 template<typename ChildT> 1333 inline Coord 1334 RootNode<ChildT>::getMinIndex() const 1335 { 1336 return mTable.empty() ? Coord(0) : mTable.begin()->first; 1337 } 1338 1339 template<typename ChildT> 1340 inline Coord 1341 RootNode<ChildT>::getMaxIndex() const 1342 { 1343 return mTable.empty() ? Coord(0) : mTable.rbegin()->first + Coord(ChildT::DIM - 1); 1344 } 1345 1346 1347 template<typename ChildT> 1348 inline void 1349 RootNode<ChildT>::getIndexRange(CoordBBox& bbox) const 1350 { 1351 bbox.min() = this->getMinIndex(); 1352 bbox.max() = this->getMaxIndex(); 1353 } 1354 1355 1356 //////////////////////////////////////// 1357 1358 1359 template<typename ChildT> 1360 template<typename OtherChildType> 1361 inline bool 1362 RootNode<ChildT>::hasSameTopology(const RootNode<OtherChildType>& other) const 1363 { 1364 using OtherRootT = RootNode<OtherChildType>; 1365 using OtherMapT = typename OtherRootT::MapType; 1366 using OtherIterT = typename OtherRootT::MapIter; 1367 using OtherCIterT = typename OtherRootT::MapCIter; 1368 1369 if (!hasSameConfiguration(other)) return false; 1370 1371 // Create a local copy of the other node's table. 1372 OtherMapT copyOfOtherTable = other.mTable; 1373 1374 // For each entry in this node's table... 1375 for (MapCIter thisIter = mTable.begin(); thisIter != mTable.end(); ++thisIter) { 1376 if (this->isBackgroundTile(thisIter)) continue; // ignore background tiles 1377 1378 // Fail if there is no corresponding entry in the other node's table. 1379 OtherCIterT otherIter = other.findKey(thisIter->first); 1380 if (otherIter == other.mTable.end()) return false; 1381 1382 // Fail if this entry is a tile and the other is a child or vice-versa. 1383 if (isChild(thisIter)) {//thisIter points to a child 1384 if (OtherRootT::isTile(otherIter)) return false; 1385 // Fail if both entries are children, but the children have different topology. 1386 if (!getChild(thisIter).hasSameTopology(&OtherRootT::getChild(otherIter))) return false; 1387 } else {//thisIter points to a tile 1388 if (OtherRootT::isChild(otherIter)) return false; 1389 if (getTile(thisIter).active != OtherRootT::getTile(otherIter).active) return false; 1390 } 1391 1392 // Remove tiles and child nodes with matching topology from 1393 // the copy of the other node's table. This is required since 1394 // the two root tables can include an arbitrary number of 1395 // background tiles and still have the same topology! 1396 copyOfOtherTable.erase(otherIter->first); 1397 } 1398 // Fail if the remaining entries in copyOfOtherTable are not all background tiles. 1399 for (OtherIterT i = copyOfOtherTable.begin(), e = copyOfOtherTable.end(); i != e; ++i) { 1400 if (!other.isBackgroundTile(i)) return false; 1401 } 1402 return true; 1403 } 1404 1405 1406 template<typename ChildT> 1407 template<typename OtherChildType> 1408 inline bool 1409 RootNode<ChildT>::hasSameConfiguration(const RootNode<OtherChildType>&) 1410 { 1411 std::vector<Index> thisDims, otherDims; 1412 RootNode::getNodeLog2Dims(thisDims); 1413 RootNode<OtherChildType>::getNodeLog2Dims(otherDims); 1414 return (thisDims == otherDims); 1415 } 1416 1417 1418 template<typename ChildT> 1419 template<typename OtherChildType> 1420 inline void 1421 RootNode<ChildT>::enforceSameConfiguration(const RootNode<OtherChildType>&) 1422 { 1423 std::vector<Index> thisDims, otherDims; 1424 RootNode::getNodeLog2Dims(thisDims); 1425 RootNode<OtherChildType>::getNodeLog2Dims(otherDims); 1426 if (thisDims != otherDims) { 1427 std::ostringstream ostr; 1428 ostr << "grids have incompatible configurations (" << thisDims[0]; 1429 for (size_t i = 1, N = thisDims.size(); i < N; ++i) ostr << " x " << thisDims[i]; 1430 ostr << " vs. " << otherDims[0]; 1431 for (size_t i = 1, N = otherDims.size(); i < N; ++i) ostr << " x " << otherDims[i]; 1432 ostr << ")"; 1433 OPENVDB_THROW(TypeError, ostr.str()); 1434 } 1435 } 1436 1437 1438 template<typename ChildT> 1439 template<typename OtherChildType> 1440 inline bool 1441 RootNode<ChildT>::hasCompatibleValueType(const RootNode<OtherChildType>&) 1442 { 1443 using OtherValueType = typename OtherChildType::ValueType; 1444 return CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value; 1445 } 1446 1447 1448 template<typename ChildT> 1449 template<typename OtherChildType> 1450 inline void 1451 RootNode<ChildT>::enforceCompatibleValueTypes(const RootNode<OtherChildType>&) 1452 { 1453 using OtherValueType = typename OtherChildType::ValueType; 1454 if (!CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value) { 1455 std::ostringstream ostr; 1456 ostr << "values of type " << typeNameAsString<OtherValueType>() 1457 << " cannot be converted to type " << typeNameAsString<ValueType>(); 1458 OPENVDB_THROW(TypeError, ostr.str()); 1459 } 1460 } 1461 1462 1463 //////////////////////////////////////// 1464 1465 1466 template<typename ChildT> 1467 inline Index64 1468 RootNode<ChildT>::memUsage() const 1469 { 1470 Index64 sum = sizeof(*this); 1471 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 1472 if (const ChildT *child = iter->second.child) { 1473 sum += child->memUsage(); 1474 } 1475 } 1476 return sum; 1477 } 1478 1479 1480 template<typename ChildT> 1481 inline void 1482 RootNode<ChildT>::clear() 1483 { 1484 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1485 delete i->second.child; 1486 } 1487 mTable.clear(); 1488 } 1489 1490 1491 template<typename ChildT> 1492 inline void 1493 RootNode<ChildT>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const 1494 { 1495 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 1496 if (const ChildT *child = iter->second.child) { 1497 child->evalActiveBoundingBox(bbox, visitVoxels); 1498 } else if (isTileOn(iter)) { 1499 bbox.expand(iter->first, ChildT::DIM); 1500 } 1501 } 1502 } 1503 1504 1505 #if OPENVDB_ABI_VERSION_NUMBER < 8 1506 template<typename ChildT> 1507 inline Index 1508 RootNode<ChildT>::getChildCount() const { 1509 return this->childCount(); 1510 } 1511 #endif 1512 1513 1514 template<typename ChildT> 1515 inline Index 1516 RootNode<ChildT>::getTileCount() const 1517 { 1518 Index sum = 0; 1519 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1520 if (isTile(i)) ++sum; 1521 } 1522 return sum; 1523 } 1524 1525 1526 template<typename ChildT> 1527 inline Index 1528 RootNode<ChildT>::getActiveTileCount() const 1529 { 1530 Index sum = 0; 1531 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1532 if (isTileOn(i)) ++sum; 1533 } 1534 return sum; 1535 } 1536 1537 1538 template<typename ChildT> 1539 inline Index 1540 RootNode<ChildT>::getInactiveTileCount() const 1541 { 1542 Index sum = 0; 1543 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1544 if (isTileOff(i)) ++sum; 1545 } 1546 return sum; 1547 } 1548 1549 1550 template<typename ChildT> 1551 inline Index32 1552 RootNode<ChildT>::leafCount() const 1553 { 1554 Index32 sum = 0; 1555 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1556 if (isChild(i)) sum += getChild(i).leafCount(); 1557 } 1558 return sum; 1559 } 1560 1561 1562 template<typename ChildT> 1563 inline Index32 1564 RootNode<ChildT>::nonLeafCount() const 1565 { 1566 Index32 sum = 1; 1567 if (ChildT::LEVEL != 0) { 1568 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1569 if (isChild(i)) sum += getChild(i).nonLeafCount(); 1570 } 1571 } 1572 return sum; 1573 } 1574 1575 1576 template<typename ChildT> 1577 inline Index32 1578 RootNode<ChildT>::childCount() const 1579 { 1580 Index sum = 0; 1581 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1582 if (isChild(i)) ++sum; 1583 } 1584 return sum; 1585 } 1586 1587 1588 template<typename ChildT> 1589 inline Index64 1590 RootNode<ChildT>::onVoxelCount() const 1591 { 1592 Index64 sum = 0; 1593 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1594 if (isChild(i)) { 1595 sum += getChild(i).onVoxelCount(); 1596 } else if (isTileOn(i)) { 1597 sum += ChildT::NUM_VOXELS; 1598 } 1599 } 1600 return sum; 1601 } 1602 1603 1604 template<typename ChildT> 1605 inline Index64 1606 RootNode<ChildT>::offVoxelCount() const 1607 { 1608 Index64 sum = 0; 1609 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1610 if (isChild(i)) { 1611 sum += getChild(i).offVoxelCount(); 1612 } else if (isTileOff(i) && !this->isBackgroundTile(i)) { 1613 sum += ChildT::NUM_VOXELS; 1614 } 1615 } 1616 return sum; 1617 } 1618 1619 1620 template<typename ChildT> 1621 inline Index64 1622 RootNode<ChildT>::onLeafVoxelCount() const 1623 { 1624 Index64 sum = 0; 1625 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1626 if (isChild(i)) sum += getChild(i).onLeafVoxelCount(); 1627 } 1628 return sum; 1629 } 1630 1631 1632 template<typename ChildT> 1633 inline Index64 1634 RootNode<ChildT>::offLeafVoxelCount() const 1635 { 1636 Index64 sum = 0; 1637 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1638 if (isChild(i)) sum += getChild(i).offLeafVoxelCount(); 1639 } 1640 return sum; 1641 } 1642 1643 template<typename ChildT> 1644 inline Index64 1645 RootNode<ChildT>::onTileCount() const 1646 { 1647 Index64 sum = 0; 1648 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1649 if (isChild(i)) { 1650 sum += getChild(i).onTileCount(); 1651 } else if (isTileOn(i)) { 1652 sum += 1; 1653 } 1654 } 1655 return sum; 1656 } 1657 1658 template<typename ChildT> 1659 inline void 1660 RootNode<ChildT>::nodeCount(std::vector<Index32> &vec) const 1661 { 1662 assert(vec.size() > LEVEL); 1663 Index32 sum = 0; 1664 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1665 if (isChild(i)) { 1666 ++sum; 1667 getChild(i).nodeCount(vec); 1668 } 1669 } 1670 vec[LEVEL] = 1;// one root node 1671 vec[ChildNodeType::LEVEL] = sum; 1672 } 1673 1674 //////////////////////////////////////// 1675 1676 1677 template<typename ChildT> 1678 inline bool 1679 RootNode<ChildT>::isValueOn(const Coord& xyz) const 1680 { 1681 MapCIter iter = this->findCoord(xyz); 1682 if (iter == mTable.end() || isTileOff(iter)) return false; 1683 return isTileOn(iter) ? true : getChild(iter).isValueOn(xyz); 1684 } 1685 1686 template<typename ChildT> 1687 inline bool 1688 RootNode<ChildT>::hasActiveTiles() const 1689 { 1690 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 1691 if (isChild(i) ? getChild(i).hasActiveTiles() : getTile(i).active) return true; 1692 } 1693 return false; 1694 } 1695 1696 template<typename ChildT> 1697 template<typename AccessorT> 1698 inline bool 1699 RootNode<ChildT>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const 1700 { 1701 MapCIter iter = this->findCoord(xyz); 1702 if (iter == mTable.end() || isTileOff(iter)) return false; 1703 if (isTileOn(iter)) return true; 1704 acc.insert(xyz, &getChild(iter)); 1705 return getChild(iter).isValueOnAndCache(xyz, acc); 1706 } 1707 1708 1709 template<typename ChildT> 1710 inline const typename ChildT::ValueType& 1711 RootNode<ChildT>::getValue(const Coord& xyz) const 1712 { 1713 MapCIter iter = this->findCoord(xyz); 1714 return iter == mTable.end() ? mBackground 1715 : (isTile(iter) ? getTile(iter).value : getChild(iter).getValue(xyz)); 1716 } 1717 1718 template<typename ChildT> 1719 template<typename AccessorT> 1720 inline const typename ChildT::ValueType& 1721 RootNode<ChildT>::getValueAndCache(const Coord& xyz, AccessorT& acc) const 1722 { 1723 MapCIter iter = this->findCoord(xyz); 1724 if (iter == mTable.end()) return mBackground; 1725 if (isChild(iter)) { 1726 acc.insert(xyz, &getChild(iter)); 1727 return getChild(iter).getValueAndCache(xyz, acc); 1728 } 1729 return getTile(iter).value; 1730 } 1731 1732 1733 template<typename ChildT> 1734 inline int 1735 RootNode<ChildT>::getValueDepth(const Coord& xyz) const 1736 { 1737 MapCIter iter = this->findCoord(xyz); 1738 return iter == mTable.end() ? -1 1739 : (isTile(iter) ? 0 : int(LEVEL) - int(getChild(iter).getValueLevel(xyz))); 1740 } 1741 1742 template<typename ChildT> 1743 template<typename AccessorT> 1744 inline int 1745 RootNode<ChildT>::getValueDepthAndCache(const Coord& xyz, AccessorT& acc) const 1746 { 1747 MapCIter iter = this->findCoord(xyz); 1748 if (iter == mTable.end()) return -1; 1749 if (isTile(iter)) return 0; 1750 acc.insert(xyz, &getChild(iter)); 1751 return int(LEVEL) - int(getChild(iter).getValueLevelAndCache(xyz, acc)); 1752 } 1753 1754 1755 template<typename ChildT> 1756 inline void 1757 RootNode<ChildT>::setValueOff(const Coord& xyz) 1758 { 1759 MapIter iter = this->findCoord(xyz); 1760 if (iter != mTable.end() && !isTileOff(iter)) { 1761 if (isTileOn(iter)) { 1762 setChild(iter, *new ChildT(xyz, getTile(iter).value, /*active=*/true)); 1763 } 1764 getChild(iter).setValueOff(xyz); 1765 } 1766 } 1767 1768 1769 template<typename ChildT> 1770 inline void 1771 RootNode<ChildT>::setActiveState(const Coord& xyz, bool on) 1772 { 1773 ChildT* child = nullptr; 1774 MapIter iter = this->findCoord(xyz); 1775 if (iter == mTable.end()) { 1776 if (on) { 1777 child = new ChildT(xyz, mBackground); 1778 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1779 } else { 1780 // Nothing to do; (x, y, z) is background and therefore already inactive. 1781 } 1782 } else if (isChild(iter)) { 1783 child = &getChild(iter); 1784 } else if (on != getTile(iter).active) { 1785 child = new ChildT(xyz, getTile(iter).value, !on); 1786 setChild(iter, *child); 1787 } 1788 if (child) child->setActiveState(xyz, on); 1789 } 1790 1791 template<typename ChildT> 1792 template<typename AccessorT> 1793 inline void 1794 RootNode<ChildT>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc) 1795 { 1796 ChildT* child = nullptr; 1797 MapIter iter = this->findCoord(xyz); 1798 if (iter == mTable.end()) { 1799 if (on) { 1800 child = new ChildT(xyz, mBackground); 1801 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1802 } else { 1803 // Nothing to do; (x, y, z) is background and therefore already inactive. 1804 } 1805 } else if (isChild(iter)) { 1806 child = &getChild(iter); 1807 } else if (on != getTile(iter).active) { 1808 child = new ChildT(xyz, getTile(iter).value, !on); 1809 setChild(iter, *child); 1810 } 1811 if (child) { 1812 acc.insert(xyz, child); 1813 child->setActiveStateAndCache(xyz, on, acc); 1814 } 1815 } 1816 1817 1818 template<typename ChildT> 1819 inline void 1820 RootNode<ChildT>::setValueOff(const Coord& xyz, const ValueType& value) 1821 { 1822 ChildT* child = nullptr; 1823 MapIter iter = this->findCoord(xyz); 1824 if (iter == mTable.end()) { 1825 if (!math::isExactlyEqual(mBackground, value)) { 1826 child = new ChildT(xyz, mBackground); 1827 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1828 } 1829 } else if (isChild(iter)) { 1830 child = &getChild(iter); 1831 } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) { 1832 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1833 setChild(iter, *child); 1834 } 1835 if (child) child->setValueOff(xyz, value); 1836 } 1837 1838 template<typename ChildT> 1839 template<typename AccessorT> 1840 inline void 1841 RootNode<ChildT>::setValueOffAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc) 1842 { 1843 ChildT* child = nullptr; 1844 MapIter iter = this->findCoord(xyz); 1845 if (iter == mTable.end()) { 1846 if (!math::isExactlyEqual(mBackground, value)) { 1847 child = new ChildT(xyz, mBackground); 1848 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1849 } 1850 } else if (isChild(iter)) { 1851 child = &getChild(iter); 1852 } else if (isTileOn(iter) || !math::isExactlyEqual(getTile(iter).value, value)) { 1853 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1854 setChild(iter, *child); 1855 } 1856 if (child) { 1857 acc.insert(xyz, child); 1858 child->setValueOffAndCache(xyz, value, acc); 1859 } 1860 } 1861 1862 1863 template<typename ChildT> 1864 inline void 1865 RootNode<ChildT>::setValueOn(const Coord& xyz, const ValueType& value) 1866 { 1867 ChildT* child = nullptr; 1868 MapIter iter = this->findCoord(xyz); 1869 if (iter == mTable.end()) { 1870 child = new ChildT(xyz, mBackground); 1871 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1872 } else if (isChild(iter)) { 1873 child = &getChild(iter); 1874 } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) { 1875 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1876 setChild(iter, *child); 1877 } 1878 if (child) child->setValueOn(xyz, value); 1879 } 1880 1881 template<typename ChildT> 1882 template<typename AccessorT> 1883 inline void 1884 RootNode<ChildT>::setValueAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc) 1885 { 1886 ChildT* child = nullptr; 1887 MapIter iter = this->findCoord(xyz); 1888 if (iter == mTable.end()) { 1889 child = new ChildT(xyz, mBackground); 1890 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1891 } else if (isChild(iter)) { 1892 child = &getChild(iter); 1893 } else if (isTileOff(iter) || !math::isExactlyEqual(getTile(iter).value, value)) { 1894 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1895 setChild(iter, *child); 1896 } 1897 if (child) { 1898 acc.insert(xyz, child); 1899 child->setValueAndCache(xyz, value, acc); 1900 } 1901 } 1902 1903 1904 template<typename ChildT> 1905 inline void 1906 RootNode<ChildT>::setValueOnly(const Coord& xyz, const ValueType& value) 1907 { 1908 ChildT* child = nullptr; 1909 MapIter iter = this->findCoord(xyz); 1910 if (iter == mTable.end()) { 1911 child = new ChildT(xyz, mBackground); 1912 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1913 } else if (isChild(iter)) { 1914 child = &getChild(iter); 1915 } else if (!math::isExactlyEqual(getTile(iter).value, value)) { 1916 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1917 setChild(iter, *child); 1918 } 1919 if (child) child->setValueOnly(xyz, value); 1920 } 1921 1922 template<typename ChildT> 1923 template<typename AccessorT> 1924 inline void 1925 RootNode<ChildT>::setValueOnlyAndCache(const Coord& xyz, const ValueType& value, AccessorT& acc) 1926 { 1927 ChildT* child = nullptr; 1928 MapIter iter = this->findCoord(xyz); 1929 if (iter == mTable.end()) { 1930 child = new ChildT(xyz, mBackground); 1931 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1932 } else if (isChild(iter)) { 1933 child = &getChild(iter); 1934 } else if (!math::isExactlyEqual(getTile(iter).value, value)) { 1935 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1936 setChild(iter, *child); 1937 } 1938 if (child) { 1939 acc.insert(xyz, child); 1940 child->setValueOnlyAndCache(xyz, value, acc); 1941 } 1942 } 1943 1944 1945 template<typename ChildT> 1946 template<typename ModifyOp> 1947 inline void 1948 RootNode<ChildT>::modifyValue(const Coord& xyz, const ModifyOp& op) 1949 { 1950 ChildT* child = nullptr; 1951 MapIter iter = this->findCoord(xyz); 1952 if (iter == mTable.end()) { 1953 child = new ChildT(xyz, mBackground); 1954 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1955 } else if (isChild(iter)) { 1956 child = &getChild(iter); 1957 } else { 1958 // Need to create a child if the tile is inactive, 1959 // in order to activate voxel (x, y, z). 1960 bool createChild = isTileOff(iter); 1961 if (!createChild) { 1962 // Need to create a child if applying the functor 1963 // to the tile value produces a different value. 1964 const ValueType& tileVal = getTile(iter).value; 1965 ValueType modifiedVal = tileVal; 1966 op(modifiedVal); 1967 createChild = !math::isExactlyEqual(tileVal, modifiedVal); 1968 } 1969 if (createChild) { 1970 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 1971 setChild(iter, *child); 1972 } 1973 } 1974 if (child) child->modifyValue(xyz, op); 1975 } 1976 1977 template<typename ChildT> 1978 template<typename ModifyOp, typename AccessorT> 1979 inline void 1980 RootNode<ChildT>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op, AccessorT& acc) 1981 { 1982 ChildT* child = nullptr; 1983 MapIter iter = this->findCoord(xyz); 1984 if (iter == mTable.end()) { 1985 child = new ChildT(xyz, mBackground); 1986 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 1987 } else if (isChild(iter)) { 1988 child = &getChild(iter); 1989 } else { 1990 // Need to create a child if the tile is inactive, 1991 // in order to activate voxel (x, y, z). 1992 bool createChild = isTileOff(iter); 1993 if (!createChild) { 1994 // Need to create a child if applying the functor 1995 // to the tile value produces a different value. 1996 const ValueType& tileVal = getTile(iter).value; 1997 ValueType modifiedVal = tileVal; 1998 op(modifiedVal); 1999 createChild = !math::isExactlyEqual(tileVal, modifiedVal); 2000 } 2001 if (createChild) { 2002 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2003 setChild(iter, *child); 2004 } 2005 } 2006 if (child) { 2007 acc.insert(xyz, child); 2008 child->modifyValueAndCache(xyz, op, acc); 2009 } 2010 } 2011 2012 2013 template<typename ChildT> 2014 template<typename ModifyOp> 2015 inline void 2016 RootNode<ChildT>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op) 2017 { 2018 ChildT* child = nullptr; 2019 MapIter iter = this->findCoord(xyz); 2020 if (iter == mTable.end()) { 2021 child = new ChildT(xyz, mBackground); 2022 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2023 } else if (isChild(iter)) { 2024 child = &getChild(iter); 2025 } else { 2026 const Tile& tile = getTile(iter); 2027 bool modifiedState = tile.active; 2028 ValueType modifiedVal = tile.value; 2029 op(modifiedVal, modifiedState); 2030 // Need to create a child if applying the functor to the tile 2031 // produces a different value or active state. 2032 if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) { 2033 child = new ChildT(xyz, tile.value, tile.active); 2034 setChild(iter, *child); 2035 } 2036 } 2037 if (child) child->modifyValueAndActiveState(xyz, op); 2038 } 2039 2040 template<typename ChildT> 2041 template<typename ModifyOp, typename AccessorT> 2042 inline void 2043 RootNode<ChildT>::modifyValueAndActiveStateAndCache( 2044 const Coord& xyz, const ModifyOp& op, AccessorT& acc) 2045 { 2046 ChildT* child = nullptr; 2047 MapIter iter = this->findCoord(xyz); 2048 if (iter == mTable.end()) { 2049 child = new ChildT(xyz, mBackground); 2050 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2051 } else if (isChild(iter)) { 2052 child = &getChild(iter); 2053 } else { 2054 const Tile& tile = getTile(iter); 2055 bool modifiedState = tile.active; 2056 ValueType modifiedVal = tile.value; 2057 op(modifiedVal, modifiedState); 2058 // Need to create a child if applying the functor to the tile 2059 // produces a different value or active state. 2060 if (modifiedState != tile.active || !math::isExactlyEqual(modifiedVal, tile.value)) { 2061 child = new ChildT(xyz, tile.value, tile.active); 2062 setChild(iter, *child); 2063 } 2064 } 2065 if (child) { 2066 acc.insert(xyz, child); 2067 child->modifyValueAndActiveStateAndCache(xyz, op, acc); 2068 } 2069 } 2070 2071 2072 template<typename ChildT> 2073 inline bool 2074 RootNode<ChildT>::probeValue(const Coord& xyz, ValueType& value) const 2075 { 2076 MapCIter iter = this->findCoord(xyz); 2077 if (iter == mTable.end()) { 2078 value = mBackground; 2079 return false; 2080 } else if (isChild(iter)) { 2081 return getChild(iter).probeValue(xyz, value); 2082 } 2083 value = getTile(iter).value; 2084 return isTileOn(iter); 2085 } 2086 2087 template<typename ChildT> 2088 template<typename AccessorT> 2089 inline bool 2090 RootNode<ChildT>::probeValueAndCache(const Coord& xyz, ValueType& value, AccessorT& acc) const 2091 { 2092 MapCIter iter = this->findCoord(xyz); 2093 if (iter == mTable.end()) { 2094 value = mBackground; 2095 return false; 2096 } else if (isChild(iter)) { 2097 acc.insert(xyz, &getChild(iter)); 2098 return getChild(iter).probeValueAndCache(xyz, value, acc); 2099 } 2100 value = getTile(iter).value; 2101 return isTileOn(iter); 2102 } 2103 2104 2105 //////////////////////////////////////// 2106 2107 2108 template<typename ChildT> 2109 inline void 2110 RootNode<ChildT>::fill(const CoordBBox& bbox, const ValueType& value, bool active) 2111 { 2112 if (bbox.empty()) return; 2113 2114 // Iterate over the fill region in axis-aligned, tile-sized chunks. 2115 // (The first and last chunks along each axis might be smaller than a tile.) 2116 Coord xyz, tileMax; 2117 for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) { 2118 xyz.setX(x); 2119 for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) { 2120 xyz.setY(y); 2121 for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) { 2122 xyz.setZ(z); 2123 2124 // Get the bounds of the tile that contains voxel (x, y, z). 2125 Coord tileMin = coordToKey(xyz); 2126 tileMax = tileMin.offsetBy(ChildT::DIM - 1); 2127 2128 if (xyz != tileMin || Coord::lessThan(bbox.max(), tileMax)) { 2129 // If the box defined by (xyz, bbox.max()) doesn't completely enclose 2130 // the tile to which xyz belongs, create a child node (or retrieve 2131 // the existing one). 2132 ChildT* child = nullptr; 2133 MapIter iter = this->findKey(tileMin); 2134 if (iter == mTable.end()) { 2135 // No child or tile exists. Create a child and initialize it 2136 // with the background value. 2137 child = new ChildT(xyz, mBackground); 2138 mTable[tileMin] = NodeStruct(*child); 2139 } else if (isTile(iter)) { 2140 // Replace the tile with a newly-created child that is filled 2141 // with the tile's value and active state. 2142 const Tile& tile = getTile(iter); 2143 child = new ChildT(xyz, tile.value, tile.active); 2144 mTable[tileMin] = NodeStruct(*child); 2145 } else if (isChild(iter)) { 2146 child = &getChild(iter); 2147 } 2148 // Forward the fill request to the child. 2149 if (child) { 2150 const Coord tmp = Coord::minComponent(bbox.max(), tileMax); 2151 child->fill(CoordBBox(xyz, tmp), value, active); 2152 } 2153 } else { 2154 // If the box given by (xyz, bbox.max()) completely encloses 2155 // the tile to which xyz belongs, create the tile (if it 2156 // doesn't already exist) and give it the fill value. 2157 MapIter iter = this->findOrAddCoord(tileMin); 2158 setTile(iter, Tile(value, active)); 2159 } 2160 } 2161 } 2162 } 2163 } 2164 2165 2166 template<typename ChildT> 2167 inline void 2168 RootNode<ChildT>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active) 2169 { 2170 if (bbox.empty()) return; 2171 2172 if (active && mTable.empty()) { 2173 // If this tree is empty, then a sparse fill followed by (threaded) 2174 // densification of active tiles is the more efficient approach. 2175 sparseFill(bbox, value, active); 2176 voxelizeActiveTiles(/*threaded=*/true); 2177 return; 2178 } 2179 2180 // Iterate over the fill region in axis-aligned, tile-sized chunks. 2181 // (The first and last chunks along each axis might be smaller than a tile.) 2182 Coord xyz, tileMin, tileMax; 2183 for (int x = bbox.min().x(); x <= bbox.max().x(); x = tileMax.x() + 1) { 2184 xyz.setX(x); 2185 for (int y = bbox.min().y(); y <= bbox.max().y(); y = tileMax.y() + 1) { 2186 xyz.setY(y); 2187 for (int z = bbox.min().z(); z <= bbox.max().z(); z = tileMax.z() + 1) { 2188 xyz.setZ(z); 2189 2190 // Get the bounds of the tile that contains voxel (x, y, z). 2191 tileMin = coordToKey(xyz); 2192 tileMax = tileMin.offsetBy(ChildT::DIM - 1); 2193 2194 // Retrieve the table entry for the tile that contains xyz, 2195 // or, if there is no table entry, add a background tile. 2196 const auto iter = findOrAddCoord(tileMin); 2197 2198 if (isTile(iter)) { 2199 // If the table entry is a tile, replace it with a child node 2200 // that is filled with the tile's value and active state. 2201 const auto& tile = getTile(iter); 2202 auto* child = new ChildT{tileMin, tile.value, tile.active}; 2203 setChild(iter, *child); 2204 } 2205 // Forward the fill request to the child. 2206 getChild(iter).denseFill(bbox, value, active); 2207 } 2208 } 2209 } 2210 } 2211 2212 2213 //////////////////////////////////////// 2214 2215 2216 template<typename ChildT> 2217 inline void 2218 RootNode<ChildT>::voxelizeActiveTiles(bool threaded) 2219 { 2220 // There is little point in threading over the root table since each tile 2221 // spans a huge index space (by default 4096^3) and hence we expect few 2222 // active tiles if any at all. In fact, you're very likely to run out of 2223 // memory if this method is called on a tree with root-level active tiles! 2224 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2225 if (this->isTileOff(i)) continue; 2226 ChildT* child = i->second.child; 2227 if (child == nullptr) { 2228 // If this table entry is an active tile (i.e., not off and not a child node), 2229 // replace it with a child node filled with active tiles of the same value. 2230 child = new ChildT{i->first, this->getTile(i).value, true}; 2231 i->second.child = child; 2232 } 2233 child->voxelizeActiveTiles(threaded); 2234 } 2235 } 2236 2237 2238 //////////////////////////////////////// 2239 2240 2241 template<typename ChildT> 2242 template<typename DenseT> 2243 inline void 2244 RootNode<ChildT>::copyToDense(const CoordBBox& bbox, DenseT& dense) const 2245 { 2246 using DenseValueType = typename DenseT::ValueType; 2247 2248 const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride(); 2249 const Coord& min = dense.bbox().min(); 2250 CoordBBox nodeBBox; 2251 for (Coord xyz = bbox.min(); xyz[0] <= bbox.max()[0]; xyz[0] = nodeBBox.max()[0] + 1) { 2252 for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = nodeBBox.max()[1] + 1) { 2253 for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = nodeBBox.max()[2] + 1) { 2254 2255 // Get the coordinate bbox of the child node that contains voxel xyz. 2256 nodeBBox = CoordBBox::createCube(coordToKey(xyz), ChildT::DIM); 2257 2258 // Get the coordinate bbox of the interection of inBBox and nodeBBox 2259 CoordBBox sub(xyz, Coord::minComponent(bbox.max(), nodeBBox.max())); 2260 2261 MapCIter iter = this->findKey(nodeBBox.min()); 2262 if (iter != mTable.end() && isChild(iter)) {//is a child 2263 getChild(iter).copyToDense(sub, dense); 2264 } else {//is background or a tile value 2265 const ValueType value = iter==mTable.end() ? mBackground : getTile(iter).value; 2266 sub.translate(-min); 2267 DenseValueType* a0 = dense.data() + zStride*sub.min()[2]; 2268 for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) { 2269 DenseValueType* a1 = a0 + x*xStride; 2270 for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) { 2271 DenseValueType* a2 = a1 + y*yStride; 2272 for (Int32 z=sub.min()[2], ez=sub.max()[2]+1; z<ez; ++z, a2 += zStride) { 2273 *a2 = DenseValueType(value); 2274 } 2275 } 2276 } 2277 } 2278 } 2279 } 2280 } 2281 } 2282 2283 //////////////////////////////////////// 2284 2285 2286 template<typename ChildT> 2287 inline bool 2288 RootNode<ChildT>::writeTopology(std::ostream& os, bool toHalf) const 2289 { 2290 if (!toHalf) { 2291 os.write(reinterpret_cast<const char*>(&mBackground), sizeof(ValueType)); 2292 } else { 2293 ValueType truncatedVal = io::truncateRealToHalf(mBackground); 2294 os.write(reinterpret_cast<const char*>(&truncatedVal), sizeof(ValueType)); 2295 } 2296 io::setGridBackgroundValuePtr(os, &mBackground); 2297 2298 const Index numTiles = this->getTileCount(), numChildren = this->childCount(); 2299 os.write(reinterpret_cast<const char*>(&numTiles), sizeof(Index)); 2300 os.write(reinterpret_cast<const char*>(&numChildren), sizeof(Index)); 2301 2302 if (numTiles == 0 && numChildren == 0) return false; 2303 2304 // Write tiles. 2305 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2306 if (isChild(i)) continue; 2307 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32)); 2308 os.write(reinterpret_cast<const char*>(&getTile(i).value), sizeof(ValueType)); 2309 os.write(reinterpret_cast<const char*>(&getTile(i).active), sizeof(bool)); 2310 } 2311 // Write child nodes. 2312 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2313 if (isTile(i)) continue; 2314 os.write(reinterpret_cast<const char*>(i->first.asPointer()), 3 * sizeof(Int32)); 2315 getChild(i).writeTopology(os, toHalf); 2316 } 2317 2318 return true; // not empty 2319 } 2320 2321 2322 template<typename ChildT> 2323 inline bool 2324 RootNode<ChildT>::readTopology(std::istream& is, bool fromHalf) 2325 { 2326 // Delete the existing tree. 2327 this->clear(); 2328 2329 if (io::getFormatVersion(is) < OPENVDB_FILE_VERSION_ROOTNODE_MAP) { 2330 // Read and convert an older-format RootNode. 2331 2332 // For backward compatibility with older file formats, read both 2333 // outside and inside background values. 2334 is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType)); 2335 ValueType inside; 2336 is.read(reinterpret_cast<char*>(&inside), sizeof(ValueType)); 2337 2338 io::setGridBackgroundValuePtr(is, &mBackground); 2339 2340 // Read the index range. 2341 Coord rangeMin, rangeMax; 2342 is.read(reinterpret_cast<char*>(rangeMin.asPointer()), 3 * sizeof(Int32)); 2343 is.read(reinterpret_cast<char*>(rangeMax.asPointer()), 3 * sizeof(Int32)); 2344 2345 this->initTable(); 2346 Index tableSize = 0, log2Dim[4] = { 0, 0, 0, 0 }; 2347 Int32 offset[3]; 2348 for (int i = 0; i < 3; ++i) { 2349 offset[i] = rangeMin[i] >> ChildT::TOTAL; 2350 rangeMin[i] = offset[i] << ChildT::TOTAL; 2351 log2Dim[i] = 1 + util::FindHighestOn((rangeMax[i] >> ChildT::TOTAL) - offset[i]); 2352 tableSize += log2Dim[i]; 2353 rangeMax[i] = (((1 << log2Dim[i]) + offset[i]) << ChildT::TOTAL) - 1; 2354 } 2355 log2Dim[3] = log2Dim[1] + log2Dim[2]; 2356 tableSize = 1U << tableSize; 2357 2358 // Read masks. 2359 util::RootNodeMask childMask(tableSize), valueMask(tableSize); 2360 childMask.load(is); 2361 valueMask.load(is); 2362 2363 // Read child nodes/values. 2364 for (Index i = 0; i < tableSize; ++i) { 2365 // Compute origin = offset2coord(i). 2366 Index n = i; 2367 Coord origin; 2368 origin[0] = (n >> log2Dim[3]) + offset[0]; 2369 n &= (1U << log2Dim[3]) - 1; 2370 origin[1] = (n >> log2Dim[2]) + offset[1]; 2371 origin[2] = (n & ((1U << log2Dim[2]) - 1)) + offset[1]; 2372 origin <<= ChildT::TOTAL; 2373 2374 if (childMask.isOn(i)) { 2375 // Read in and insert a child node. 2376 ChildT* child = new ChildT(PartialCreate(), origin, mBackground); 2377 child->readTopology(is); 2378 mTable[origin] = NodeStruct(*child); 2379 } else { 2380 // Read in a tile value and insert a tile, but only if the value 2381 // is either active or non-background. 2382 ValueType value; 2383 is.read(reinterpret_cast<char*>(&value), sizeof(ValueType)); 2384 if (valueMask.isOn(i) || (!math::isApproxEqual(value, mBackground))) { 2385 mTable[origin] = NodeStruct(Tile(value, valueMask.isOn(i))); 2386 } 2387 } 2388 } 2389 return true; 2390 } 2391 2392 // Read a RootNode that was stored in the current format. 2393 2394 is.read(reinterpret_cast<char*>(&mBackground), sizeof(ValueType)); 2395 io::setGridBackgroundValuePtr(is, &mBackground); 2396 2397 Index numTiles = 0, numChildren = 0; 2398 is.read(reinterpret_cast<char*>(&numTiles), sizeof(Index)); 2399 is.read(reinterpret_cast<char*>(&numChildren), sizeof(Index)); 2400 2401 if (numTiles == 0 && numChildren == 0) return false; 2402 2403 Int32 vec[3]; 2404 ValueType value; 2405 bool active; 2406 2407 // Read tiles. 2408 for (Index n = 0; n < numTiles; ++n) { 2409 is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32)); 2410 is.read(reinterpret_cast<char*>(&value), sizeof(ValueType)); 2411 is.read(reinterpret_cast<char*>(&active), sizeof(bool)); 2412 mTable[Coord(vec)] = NodeStruct(Tile(value, active)); 2413 } 2414 2415 // Read child nodes. 2416 for (Index n = 0; n < numChildren; ++n) { 2417 is.read(reinterpret_cast<char*>(vec), 3 * sizeof(Int32)); 2418 Coord origin(vec); 2419 ChildT* child = new ChildT(PartialCreate(), origin, mBackground); 2420 child->readTopology(is, fromHalf); 2421 mTable[Coord(vec)] = NodeStruct(*child); 2422 } 2423 2424 return true; // not empty 2425 } 2426 2427 2428 template<typename ChildT> 2429 inline void 2430 RootNode<ChildT>::writeBuffers(std::ostream& os, bool toHalf) const 2431 { 2432 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2433 if (isChild(i)) getChild(i).writeBuffers(os, toHalf); 2434 } 2435 } 2436 2437 2438 template<typename ChildT> 2439 inline void 2440 RootNode<ChildT>::readBuffers(std::istream& is, bool fromHalf) 2441 { 2442 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2443 if (isChild(i)) getChild(i).readBuffers(is, fromHalf); 2444 } 2445 } 2446 2447 2448 template<typename ChildT> 2449 inline void 2450 RootNode<ChildT>::readBuffers(std::istream& is, const CoordBBox& clipBBox, bool fromHalf) 2451 { 2452 const Tile bgTile(mBackground, /*active=*/false); 2453 2454 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2455 if (isChild(i)) { 2456 // Stream in and clip the branch rooted at this child. 2457 // (We can't skip over children that lie outside the clipping region, 2458 // because buffers are serialized in depth-first order and need to be 2459 // unserialized in the same order.) 2460 ChildT& child = getChild(i); 2461 child.readBuffers(is, clipBBox, fromHalf); 2462 } 2463 } 2464 // Clip root-level tiles and prune children that were clipped. 2465 this->clip(clipBBox); 2466 } 2467 2468 2469 //////////////////////////////////////// 2470 2471 2472 template<typename ChildT> 2473 inline void 2474 RootNode<ChildT>::clip(const CoordBBox& clipBBox) 2475 { 2476 const Tile bgTile(mBackground, /*active=*/false); 2477 2478 // Iterate over a copy of this node's table so that we can modify the original. 2479 // (Copying the table copies child node pointers, not the nodes themselves.) 2480 MapType copyOfTable(mTable); 2481 for (MapIter i = copyOfTable.begin(), e = copyOfTable.end(); i != e; ++i) { 2482 const Coord& xyz = i->first; // tile or child origin 2483 CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds 2484 if (!clipBBox.hasOverlap(tileBBox)) { 2485 // This table entry lies completely outside the clipping region. Delete it. 2486 setTile(this->findCoord(xyz), bgTile); // delete any existing child node first 2487 mTable.erase(xyz); 2488 } else if (!clipBBox.isInside(tileBBox)) { 2489 // This table entry does not lie completely inside the clipping region 2490 // and must be clipped. 2491 if (isChild(i)) { 2492 getChild(i).clip(clipBBox, mBackground); 2493 } else { 2494 // Replace this tile with a background tile, then fill the clip region 2495 // with the tile's original value. (This might create a child branch.) 2496 tileBBox.intersect(clipBBox); 2497 const Tile& origTile = getTile(i); 2498 setTile(this->findCoord(xyz), bgTile); 2499 this->sparseFill(tileBBox, origTile.value, origTile.active); 2500 } 2501 } else { 2502 // This table entry lies completely inside the clipping region. Leave it intact. 2503 } 2504 } 2505 this->prune(); // also erases root-level background tiles 2506 } 2507 2508 2509 //////////////////////////////////////// 2510 2511 2512 template<typename ChildT> 2513 inline void 2514 RootNode<ChildT>::prune(const ValueType& tolerance) 2515 { 2516 bool state = false; 2517 ValueType value = zeroVal<ValueType>(); 2518 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 2519 if (this->isTile(i)) continue; 2520 this->getChild(i).prune(tolerance); 2521 if (this->getChild(i).isConstant(value, state, tolerance)) { 2522 this->setTile(i, Tile(value, state)); 2523 } 2524 } 2525 this->eraseBackgroundTiles(); 2526 } 2527 2528 2529 //////////////////////////////////////// 2530 2531 2532 template<typename ChildT> 2533 template<typename NodeT> 2534 inline NodeT* 2535 RootNode<ChildT>::stealNode(const Coord& xyz, const ValueType& value, bool state) 2536 { 2537 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) || 2538 NodeT::LEVEL > ChildT::LEVEL) return nullptr; 2539 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2540 MapIter iter = this->findCoord(xyz); 2541 if (iter == mTable.end() || isTile(iter)) return nullptr; 2542 return (std::is_same<NodeT, ChildT>::value) 2543 ? reinterpret_cast<NodeT*>(&stealChild(iter, Tile(value, state))) 2544 : getChild(iter).template stealNode<NodeT>(xyz, value, state); 2545 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2546 } 2547 2548 2549 //////////////////////////////////////// 2550 2551 2552 template<typename ChildT> 2553 inline void 2554 RootNode<ChildT>::addLeaf(LeafNodeType* leaf) 2555 { 2556 if (leaf == nullptr) return; 2557 ChildT* child = nullptr; 2558 const Coord& xyz = leaf->origin(); 2559 MapIter iter = this->findCoord(xyz); 2560 if (iter == mTable.end()) { 2561 if (ChildT::LEVEL>0) { 2562 child = new ChildT(xyz, mBackground, false); 2563 } else { 2564 child = reinterpret_cast<ChildT*>(leaf); 2565 } 2566 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2567 } else if (isChild(iter)) { 2568 if (ChildT::LEVEL>0) { 2569 child = &getChild(iter); 2570 } else { 2571 child = reinterpret_cast<ChildT*>(leaf); 2572 setChild(iter, *child);//this also deletes the existing child node 2573 } 2574 } else {//tile 2575 if (ChildT::LEVEL>0) { 2576 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2577 } else { 2578 child = reinterpret_cast<ChildT*>(leaf); 2579 } 2580 setChild(iter, *child); 2581 } 2582 child->addLeaf(leaf); 2583 } 2584 2585 2586 template<typename ChildT> 2587 template<typename AccessorT> 2588 inline void 2589 RootNode<ChildT>::addLeafAndCache(LeafNodeType* leaf, AccessorT& acc) 2590 { 2591 if (leaf == nullptr) return; 2592 ChildT* child = nullptr; 2593 const Coord& xyz = leaf->origin(); 2594 MapIter iter = this->findCoord(xyz); 2595 if (iter == mTable.end()) { 2596 if (ChildT::LEVEL>0) { 2597 child = new ChildT(xyz, mBackground, false); 2598 } else { 2599 child = reinterpret_cast<ChildT*>(leaf); 2600 } 2601 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2602 } else if (isChild(iter)) { 2603 if (ChildT::LEVEL>0) { 2604 child = &getChild(iter); 2605 } else { 2606 child = reinterpret_cast<ChildT*>(leaf); 2607 setChild(iter, *child);//this also deletes the existing child node 2608 } 2609 } else {//tile 2610 if (ChildT::LEVEL>0) { 2611 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2612 } else { 2613 child = reinterpret_cast<ChildT*>(leaf); 2614 } 2615 setChild(iter, *child); 2616 } 2617 acc.insert(xyz, child); 2618 child->addLeafAndCache(leaf, acc); 2619 } 2620 2621 template<typename ChildT> 2622 inline bool 2623 RootNode<ChildT>::addChild(ChildT* child) 2624 { 2625 if (!child) return false; 2626 const Coord& xyz = child->origin(); 2627 MapIter iter = this->findCoord(xyz); 2628 if (iter == mTable.end()) {//background 2629 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2630 } else {//child or tile 2631 setChild(iter, *child);//this also deletes the existing child node 2632 } 2633 return true; 2634 } 2635 2636 template<typename ChildT> 2637 inline void 2638 RootNode<ChildT>::addTile(const Coord& xyz, const ValueType& value, bool state) 2639 { 2640 MapIter iter = this->findCoord(xyz); 2641 if (iter == mTable.end()) {//background 2642 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state)); 2643 } else {//child or tile 2644 setTile(iter, Tile(value, state));//this also deletes the existing child node 2645 } 2646 } 2647 2648 template<typename ChildT> 2649 inline void 2650 RootNode<ChildT>::addTile(Index level, const Coord& xyz, 2651 const ValueType& value, bool state) 2652 { 2653 if (LEVEL >= level) { 2654 MapIter iter = this->findCoord(xyz); 2655 if (iter == mTable.end()) {//background 2656 if (LEVEL > level) { 2657 ChildT* child = new ChildT(xyz, mBackground, false); 2658 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2659 child->addTile(level, xyz, value, state); 2660 } else { 2661 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state)); 2662 } 2663 } else if (isChild(iter)) {//child 2664 if (LEVEL > level) { 2665 getChild(iter).addTile(level, xyz, value, state); 2666 } else { 2667 setTile(iter, Tile(value, state));//this also deletes the existing child node 2668 } 2669 } else {//tile 2670 if (LEVEL > level) { 2671 ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2672 setChild(iter, *child); 2673 child->addTile(level, xyz, value, state); 2674 } else { 2675 setTile(iter, Tile(value, state)); 2676 } 2677 } 2678 } 2679 } 2680 2681 2682 template<typename ChildT> 2683 template<typename AccessorT> 2684 inline void 2685 RootNode<ChildT>::addTileAndCache(Index level, const Coord& xyz, const ValueType& value, 2686 bool state, AccessorT& acc) 2687 { 2688 if (LEVEL >= level) { 2689 MapIter iter = this->findCoord(xyz); 2690 if (iter == mTable.end()) {//background 2691 if (LEVEL > level) { 2692 ChildT* child = new ChildT(xyz, mBackground, false); 2693 acc.insert(xyz, child); 2694 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2695 child->addTileAndCache(level, xyz, value, state, acc); 2696 } else { 2697 mTable[this->coordToKey(xyz)] = NodeStruct(Tile(value, state)); 2698 } 2699 } else if (isChild(iter)) {//child 2700 if (LEVEL > level) { 2701 ChildT* child = &getChild(iter); 2702 acc.insert(xyz, child); 2703 child->addTileAndCache(level, xyz, value, state, acc); 2704 } else { 2705 setTile(iter, Tile(value, state));//this also deletes the existing child node 2706 } 2707 } else {//tile 2708 if (LEVEL > level) { 2709 ChildT* child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2710 acc.insert(xyz, child); 2711 setChild(iter, *child); 2712 child->addTileAndCache(level, xyz, value, state, acc); 2713 } else { 2714 setTile(iter, Tile(value, state)); 2715 } 2716 } 2717 } 2718 } 2719 2720 2721 //////////////////////////////////////// 2722 2723 2724 template<typename ChildT> 2725 inline typename ChildT::LeafNodeType* 2726 RootNode<ChildT>::touchLeaf(const Coord& xyz) 2727 { 2728 ChildT* child = nullptr; 2729 MapIter iter = this->findCoord(xyz); 2730 if (iter == mTable.end()) { 2731 child = new ChildT(xyz, mBackground, false); 2732 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2733 } else if (isChild(iter)) { 2734 child = &getChild(iter); 2735 } else { 2736 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2737 setChild(iter, *child); 2738 } 2739 return child->touchLeaf(xyz); 2740 } 2741 2742 2743 template<typename ChildT> 2744 template<typename AccessorT> 2745 inline typename ChildT::LeafNodeType* 2746 RootNode<ChildT>::touchLeafAndCache(const Coord& xyz, AccessorT& acc) 2747 { 2748 ChildT* child = nullptr; 2749 MapIter iter = this->findCoord(xyz); 2750 if (iter == mTable.end()) { 2751 child = new ChildT(xyz, mBackground, false); 2752 mTable[this->coordToKey(xyz)] = NodeStruct(*child); 2753 } else if (isChild(iter)) { 2754 child = &getChild(iter); 2755 } else { 2756 child = new ChildT(xyz, getTile(iter).value, isTileOn(iter)); 2757 setChild(iter, *child); 2758 } 2759 acc.insert(xyz, child); 2760 return child->touchLeafAndCache(xyz, acc); 2761 } 2762 2763 2764 //////////////////////////////////////// 2765 2766 2767 template<typename ChildT> 2768 template<typename NodeT> 2769 inline NodeT* 2770 RootNode<ChildT>::probeNode(const Coord& xyz) 2771 { 2772 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) || 2773 NodeT::LEVEL > ChildT::LEVEL) return nullptr; 2774 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2775 MapIter iter = this->findCoord(xyz); 2776 if (iter == mTable.end() || isTile(iter)) return nullptr; 2777 ChildT* child = &getChild(iter); 2778 return (std::is_same<NodeT, ChildT>::value) 2779 ? reinterpret_cast<NodeT*>(child) 2780 : child->template probeNode<NodeT>(xyz); 2781 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2782 } 2783 2784 2785 template<typename ChildT> 2786 template<typename NodeT> 2787 inline const NodeT* 2788 RootNode<ChildT>::probeConstNode(const Coord& xyz) const 2789 { 2790 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) || 2791 NodeT::LEVEL > ChildT::LEVEL) return nullptr; 2792 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2793 MapCIter iter = this->findCoord(xyz); 2794 if (iter == mTable.end() || isTile(iter)) return nullptr; 2795 const ChildT* child = &getChild(iter); 2796 return (std::is_same<NodeT, ChildT>::value) 2797 ? reinterpret_cast<const NodeT*>(child) 2798 : child->template probeConstNode<NodeT>(xyz); 2799 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2800 } 2801 2802 2803 template<typename ChildT> 2804 inline typename ChildT::LeafNodeType* 2805 RootNode<ChildT>::probeLeaf(const Coord& xyz) 2806 { 2807 return this->template probeNode<LeafNodeType>(xyz); 2808 } 2809 2810 2811 template<typename ChildT> 2812 inline const typename ChildT::LeafNodeType* 2813 RootNode<ChildT>::probeConstLeaf(const Coord& xyz) const 2814 { 2815 return this->template probeConstNode<LeafNodeType>(xyz); 2816 } 2817 2818 2819 template<typename ChildT> 2820 template<typename AccessorT> 2821 inline typename ChildT::LeafNodeType* 2822 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) 2823 { 2824 return this->template probeNodeAndCache<LeafNodeType>(xyz, acc); 2825 } 2826 2827 2828 template<typename ChildT> 2829 template<typename AccessorT> 2830 inline const typename ChildT::LeafNodeType* 2831 RootNode<ChildT>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const 2832 { 2833 return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc); 2834 } 2835 2836 2837 template<typename ChildT> 2838 template<typename AccessorT> 2839 inline const typename ChildT::LeafNodeType* 2840 RootNode<ChildT>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const 2841 { 2842 return this->probeConstLeafAndCache(xyz, acc); 2843 } 2844 2845 2846 template<typename ChildT> 2847 template<typename NodeT, typename AccessorT> 2848 inline NodeT* 2849 RootNode<ChildT>::probeNodeAndCache(const Coord& xyz, AccessorT& acc) 2850 { 2851 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) || 2852 NodeT::LEVEL > ChildT::LEVEL) return nullptr; 2853 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2854 MapIter iter = this->findCoord(xyz); 2855 if (iter == mTable.end() || isTile(iter)) return nullptr; 2856 ChildT* child = &getChild(iter); 2857 acc.insert(xyz, child); 2858 return (std::is_same<NodeT, ChildT>::value) 2859 ? reinterpret_cast<NodeT*>(child) 2860 : child->template probeNodeAndCache<NodeT>(xyz, acc); 2861 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2862 } 2863 2864 2865 template<typename ChildT> 2866 template<typename NodeT,typename AccessorT> 2867 inline const NodeT* 2868 RootNode<ChildT>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const 2869 { 2870 if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) || 2871 NodeT::LEVEL > ChildT::LEVEL) return nullptr; 2872 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2873 MapCIter iter = this->findCoord(xyz); 2874 if (iter == mTable.end() || isTile(iter)) return nullptr; 2875 const ChildT* child = &getChild(iter); 2876 acc.insert(xyz, child); 2877 return (std::is_same<NodeT, ChildT>::value) 2878 ? reinterpret_cast<const NodeT*>(child) 2879 : child->template probeConstNodeAndCache<NodeT>(xyz, acc); 2880 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2881 } 2882 2883 2884 //////////////////////////////////////// 2885 2886 template<typename ChildT> 2887 template<typename ArrayT> 2888 inline void 2889 RootNode<ChildT>::getNodes(ArrayT& array) 2890 { 2891 using NodePtr = typename ArrayT::value_type; 2892 static_assert(std::is_pointer<NodePtr>::value, 2893 "argument to getNodes() must be a pointer array"); 2894 using NodeType = typename std::remove_pointer<NodePtr>::type; 2895 using NonConstNodeType = typename std::remove_const<NodeType>::type; 2896 static_assert(NodeChainType::template Contains<NonConstNodeType>, 2897 "can't extract non-const nodes from a const tree"); 2898 using ArrayChildT = typename std::conditional< 2899 std::is_const<NodeType>::value, const ChildT, ChildT>::type; 2900 2901 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 2902 if (ChildT* child = iter->second.child) { 2903 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2904 if (std::is_same<NodePtr, ArrayChildT*>::value) { 2905 array.push_back(reinterpret_cast<NodePtr>(iter->second.child)); 2906 } else { 2907 child->getNodes(array);//descent 2908 } 2909 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2910 } 2911 } 2912 } 2913 2914 template<typename ChildT> 2915 template<typename ArrayT> 2916 inline void 2917 RootNode<ChildT>::getNodes(ArrayT& array) const 2918 { 2919 using NodePtr = typename ArrayT::value_type; 2920 static_assert(std::is_pointer<NodePtr>::value, 2921 "argument to getNodes() must be a pointer array"); 2922 using NodeType = typename std::remove_pointer<NodePtr>::type; 2923 static_assert(std::is_const<NodeType>::value, 2924 "argument to getNodes() must be an array of const node pointers"); 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 2929 for (MapCIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 2930 if (const ChildNodeType *child = iter->second.child) { 2931 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2932 if (std::is_same<NodePtr, const ChildT*>::value) { 2933 array.push_back(reinterpret_cast<NodePtr>(iter->second.child)); 2934 } else { 2935 child->getNodes(array);//descent 2936 } 2937 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2938 } 2939 } 2940 } 2941 2942 //////////////////////////////////////// 2943 2944 template<typename ChildT> 2945 template<typename ArrayT> 2946 inline void 2947 RootNode<ChildT>::stealNodes(ArrayT& array, const ValueType& value, bool state) 2948 { 2949 using NodePtr = typename ArrayT::value_type; 2950 static_assert(std::is_pointer<NodePtr>::value, 2951 "argument to stealNodes() must be a pointer array"); 2952 using NodeType = typename std::remove_pointer<NodePtr>::type; 2953 using NonConstNodeType = typename std::remove_const<NodeType>::type; 2954 static_assert(NodeChainType::template Contains<NonConstNodeType>, 2955 "can't extract non-const nodes from a const tree"); 2956 using ArrayChildT = typename std::conditional< 2957 std::is_const<NodeType>::value, const ChildT, ChildT>::type; 2958 2959 for (MapIter iter=mTable.begin(); iter!=mTable.end(); ++iter) { 2960 if (ChildT* child = iter->second.child) { 2961 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2962 if (std::is_same<NodePtr, ArrayChildT*>::value) { 2963 array.push_back(reinterpret_cast<NodePtr>(&stealChild(iter, Tile(value, state)))); 2964 } else { 2965 child->stealNodes(array, value, state);//descent 2966 } 2967 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 2968 } 2969 } 2970 } 2971 2972 2973 //////////////////////////////////////// 2974 2975 2976 template<typename ChildT> 2977 template<MergePolicy Policy> 2978 inline void 2979 RootNode<ChildT>::merge(RootNode& other) 2980 { 2981 OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN 2982 2983 switch (Policy) { 2984 2985 default: 2986 case MERGE_ACTIVE_STATES: 2987 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 2988 MapIter j = mTable.find(i->first); 2989 if (other.isChild(i)) { 2990 if (j == mTable.end()) { // insert other node's child 2991 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 2992 child.resetBackground(other.mBackground, mBackground); 2993 mTable[i->first] = NodeStruct(child); 2994 } else if (isTile(j)) { 2995 if (isTileOff(j)) { // replace inactive tile with other node's child 2996 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 2997 child.resetBackground(other.mBackground, mBackground); 2998 setChild(j, child); 2999 } 3000 } else { // merge both child nodes 3001 getChild(j).template merge<MERGE_ACTIVE_STATES>(getChild(i), 3002 other.mBackground, mBackground); 3003 } 3004 } else if (other.isTileOn(i)) { 3005 if (j == mTable.end()) { // insert other node's active tile 3006 mTable[i->first] = i->second; 3007 } else if (!isTileOn(j)) { 3008 // Replace anything except an active tile with the other node's active tile. 3009 setTile(j, Tile(other.getTile(i).value, true)); 3010 } 3011 } 3012 } 3013 break; 3014 3015 case MERGE_NODES: 3016 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 3017 MapIter j = mTable.find(i->first); 3018 if (other.isChild(i)) { 3019 if (j == mTable.end()) { // insert other node's child 3020 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 3021 child.resetBackground(other.mBackground, mBackground); 3022 mTable[i->first] = NodeStruct(child); 3023 } else if (isTile(j)) { // replace tile with other node's child 3024 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 3025 child.resetBackground(other.mBackground, mBackground); 3026 setChild(j, child); 3027 } else { // merge both child nodes 3028 getChild(j).template merge<MERGE_NODES>( 3029 getChild(i), other.mBackground, mBackground); 3030 } 3031 } 3032 } 3033 break; 3034 3035 case MERGE_ACTIVE_STATES_AND_NODES: 3036 for (MapIter i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 3037 MapIter j = mTable.find(i->first); 3038 if (other.isChild(i)) { 3039 if (j == mTable.end()) { 3040 // Steal and insert the other node's child. 3041 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 3042 child.resetBackground(other.mBackground, mBackground); 3043 mTable[i->first] = NodeStruct(child); 3044 } else if (isTile(j)) { 3045 // Replace this node's tile with the other node's child. 3046 ChildNodeType& child = stealChild(i, Tile(other.mBackground, /*on=*/false)); 3047 child.resetBackground(other.mBackground, mBackground); 3048 const Tile tile = getTile(j); 3049 setChild(j, child); 3050 if (tile.active) { 3051 // Merge the other node's child with this node's active tile. 3052 child.template merge<MERGE_ACTIVE_STATES_AND_NODES>( 3053 tile.value, tile.active); 3054 } 3055 } else /*if (isChild(j))*/ { 3056 // Merge the other node's child into this node's child. 3057 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>(getChild(i), 3058 other.mBackground, mBackground); 3059 } 3060 } else if (other.isTileOn(i)) { 3061 if (j == mTable.end()) { 3062 // Insert a copy of the other node's active tile. 3063 mTable[i->first] = i->second; 3064 } else if (isTileOff(j)) { 3065 // Replace this node's inactive tile with a copy of the other's active tile. 3066 setTile(j, Tile(other.getTile(i).value, true)); 3067 } else if (isChild(j)) { 3068 // Merge the other node's active tile into this node's child. 3069 const Tile& tile = getTile(i); 3070 getChild(j).template merge<MERGE_ACTIVE_STATES_AND_NODES>( 3071 tile.value, tile.active); 3072 } 3073 } // else if (other.isTileOff(i)) {} // ignore the other node's inactive tiles 3074 } 3075 break; 3076 } 3077 3078 // Empty the other tree so as not to leave it in a partially cannibalized state. 3079 other.clear(); 3080 3081 OPENVDB_NO_UNREACHABLE_CODE_WARNING_END 3082 } 3083 3084 3085 //////////////////////////////////////// 3086 3087 3088 template<typename ChildT> 3089 template<typename OtherChildType> 3090 inline void 3091 RootNode<ChildT>::topologyUnion(const RootNode<OtherChildType>& other, const bool preserveTiles) 3092 { 3093 using OtherRootT = RootNode<OtherChildType>; 3094 using OtherCIterT = typename OtherRootT::MapCIter; 3095 3096 enforceSameConfiguration(other); 3097 3098 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 3099 MapIter j = mTable.find(i->first); 3100 if (other.isChild(i)) { 3101 if (j == mTable.end()) { // create child branch with identical topology 3102 mTable[i->first] = NodeStruct( 3103 *(new ChildT(other.getChild(i), mBackground, TopologyCopy()))); 3104 } else if (this->isChild(j)) { // union with child branch 3105 this->getChild(j).topologyUnion(other.getChild(i), preserveTiles); 3106 } else {// this is a tile so replace it with a child branch with identical topology 3107 if (!preserveTiles || this->isTileOff(j)) { // force child topology 3108 ChildT* child = new ChildT( 3109 other.getChild(i), this->getTile(j).value, TopologyCopy()); 3110 if (this->isTileOn(j)) child->setValuesOn();//this is an active tile 3111 this->setChild(j, *child); 3112 } 3113 } 3114 } else if (other.isTileOn(i)) { // other is an active tile 3115 if (j == mTable.end()) { // insert an active tile 3116 mTable[i->first] = NodeStruct(Tile(mBackground, true)); 3117 } else if (this->isChild(j)) { 3118 this->getChild(j).setValuesOn(); 3119 } else if (this->isTileOff(j)) { 3120 this->setTile(j, Tile(this->getTile(j).value, true)); 3121 } 3122 } 3123 } 3124 } 3125 3126 template<typename ChildT> 3127 template<typename OtherChildType> 3128 inline void 3129 RootNode<ChildT>::topologyIntersection(const RootNode<OtherChildType>& other) 3130 { 3131 using OtherRootT = RootNode<OtherChildType>; 3132 using OtherCIterT = typename OtherRootT::MapCIter; 3133 3134 enforceSameConfiguration(other); 3135 3136 std::set<Coord> tmp;//keys to erase 3137 for (MapIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 3138 OtherCIterT j = other.mTable.find(i->first); 3139 if (this->isChild(i)) { 3140 if (j == other.mTable.end() || other.isTileOff(j)) { 3141 tmp.insert(i->first);//delete child branch 3142 } else if (other.isChild(j)) { // intersect with child branch 3143 this->getChild(i).topologyIntersection(other.getChild(j), mBackground); 3144 } 3145 } else if (this->isTileOn(i)) { 3146 if (j == other.mTable.end() || other.isTileOff(j)) { 3147 this->setTile(i, Tile(this->getTile(i).value, false));//turn inactive 3148 } else if (other.isChild(j)) { //replace with a child branch with identical topology 3149 ChildT* child = 3150 new ChildT(other.getChild(j), this->getTile(i).value, TopologyCopy()); 3151 this->setChild(i, *child); 3152 } 3153 } 3154 } 3155 for (std::set<Coord>::iterator i = tmp.begin(), e = tmp.end(); i != e; ++i) { 3156 MapIter it = this->findCoord(*i); 3157 setTile(it, Tile()); // delete any existing child node first 3158 mTable.erase(it); 3159 } 3160 } 3161 3162 template<typename ChildT> 3163 template<typename OtherChildType> 3164 inline void 3165 RootNode<ChildT>::topologyDifference(const RootNode<OtherChildType>& other) 3166 { 3167 using OtherRootT = RootNode<OtherChildType>; 3168 using OtherCIterT = typename OtherRootT::MapCIter; 3169 3170 enforceSameConfiguration(other); 3171 3172 for (OtherCIterT i = other.mTable.begin(), e = other.mTable.end(); i != e; ++i) { 3173 MapIter j = mTable.find(i->first); 3174 if (other.isChild(i)) { 3175 if (j == mTable.end() || this->isTileOff(j)) { 3176 //do nothing 3177 } else if (this->isChild(j)) { // difference with child branch 3178 this->getChild(j).topologyDifference(other.getChild(i), mBackground); 3179 } else if (this->isTileOn(j)) { 3180 // this is an active tile so create a child node and descent 3181 ChildT* child = new ChildT(j->first, this->getTile(j).value, true); 3182 child->topologyDifference(other.getChild(i), mBackground); 3183 this->setChild(j, *child); 3184 } 3185 } else if (other.isTileOn(i)) { // other is an active tile 3186 if (j == mTable.end() || this->isTileOff(j)) { 3187 // do nothing 3188 } else if (this->isChild(j)) { 3189 setTile(j, Tile()); // delete any existing child node first 3190 mTable.erase(j); 3191 } else if (this->isTileOn(j)) { 3192 this->setTile(j, Tile(this->getTile(j).value, false)); 3193 } 3194 } 3195 } 3196 } 3197 3198 //////////////////////////////////////// 3199 3200 3201 template<typename ChildT> 3202 template<typename CombineOp> 3203 inline void 3204 RootNode<ChildT>::combine(RootNode& other, CombineOp& op, bool prune) 3205 { 3206 CombineArgs<ValueType> args; 3207 3208 CoordSet keys; 3209 this->insertKeys(keys); 3210 other.insertKeys(keys); 3211 3212 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) { 3213 MapIter iter = findOrAddCoord(*i), otherIter = other.findOrAddCoord(*i); 3214 if (isTile(iter) && isTile(otherIter)) { 3215 // Both this node and the other node have constant values (tiles). 3216 // Combine the two values and store the result as this node's new tile value. 3217 op(args.setARef(getTile(iter).value) 3218 .setAIsActive(isTileOn(iter)) 3219 .setBRef(getTile(otherIter).value) 3220 .setBIsActive(isTileOn(otherIter))); 3221 setTile(iter, Tile(args.result(), args.resultIsActive())); 3222 3223 } else if (isChild(iter) && isTile(otherIter)) { 3224 // Combine this node's child with the other node's constant value. 3225 ChildT& child = getChild(iter); 3226 child.combine(getTile(otherIter).value, isTileOn(otherIter), op); 3227 3228 } else if (isTile(iter) && isChild(otherIter)) { 3229 // Combine this node's constant value with the other node's child, 3230 // but use a new functor in which the A and B values are swapped, 3231 // since the constant value is the A value, not the B value. 3232 SwappedCombineOp<ValueType, CombineOp> swappedOp(op); 3233 ChildT& child = getChild(otherIter); 3234 child.combine(getTile(iter).value, isTileOn(iter), swappedOp); 3235 3236 // Steal the other node's child. 3237 setChild(iter, stealChild(otherIter, Tile())); 3238 3239 } else /*if (isChild(iter) && isChild(otherIter))*/ { 3240 // Combine this node's child with the other node's child. 3241 ChildT &child = getChild(iter), &otherChild = getChild(otherIter); 3242 child.combine(otherChild, op); 3243 } 3244 if (prune && isChild(iter)) getChild(iter).prune(); 3245 } 3246 3247 // Combine background values. 3248 op(args.setARef(mBackground).setBRef(other.mBackground)); 3249 mBackground = args.result(); 3250 3251 // Empty the other tree so as not to leave it in a partially cannibalized state. 3252 other.clear(); 3253 } 3254 3255 3256 //////////////////////////////////////// 3257 3258 3259 // This helper class is a friend of RootNode and is needed so that combine2 3260 // can be specialized for compatible and incompatible pairs of RootNode types. 3261 template<typename CombineOp, typename RootT, typename OtherRootT, bool Compatible = false> 3262 struct RootNodeCombineHelper 3263 { 3264 static inline void combine2(RootT& self, const RootT&, const OtherRootT& other1, 3265 CombineOp&, bool) 3266 { 3267 // If the two root nodes have different configurations or incompatible ValueTypes, 3268 // throw an exception. 3269 self.enforceSameConfiguration(other1); 3270 self.enforceCompatibleValueTypes(other1); 3271 // One of the above two tests should throw, so we should never get here: 3272 std::ostringstream ostr; 3273 ostr << "cannot combine a " << typeid(OtherRootT).name() 3274 << " into a " << typeid(RootT).name(); 3275 OPENVDB_THROW(TypeError, ostr.str()); 3276 } 3277 }; 3278 3279 // Specialization for root nodes of compatible types 3280 template<typename CombineOp, typename RootT, typename OtherRootT> 3281 struct RootNodeCombineHelper<CombineOp, RootT, OtherRootT, /*Compatible=*/true> 3282 { 3283 static inline void combine2(RootT& self, const RootT& other0, const OtherRootT& other1, 3284 CombineOp& op, bool prune) 3285 { 3286 self.doCombine2(other0, other1, op, prune); 3287 } 3288 }; 3289 3290 3291 template<typename ChildT> 3292 template<typename CombineOp, typename OtherRootNode> 3293 inline void 3294 RootNode<ChildT>::combine2(const RootNode& other0, const OtherRootNode& other1, 3295 CombineOp& op, bool prune) 3296 { 3297 using OtherValueType = typename OtherRootNode::ValueType; 3298 static const bool compatible = (SameConfiguration<OtherRootNode>::value 3299 && CanConvertType</*from=*/OtherValueType, /*to=*/ValueType>::value); 3300 RootNodeCombineHelper<CombineOp, RootNode, OtherRootNode, compatible>::combine2( 3301 *this, other0, other1, op, prune); 3302 } 3303 3304 3305 template<typename ChildT> 3306 template<typename CombineOp, typename OtherRootNode> 3307 inline void 3308 RootNode<ChildT>::doCombine2(const RootNode& other0, const OtherRootNode& other1, 3309 CombineOp& op, bool prune) 3310 { 3311 enforceSameConfiguration(other1); 3312 3313 using OtherValueT = typename OtherRootNode::ValueType; 3314 using OtherTileT = typename OtherRootNode::Tile; 3315 using OtherNodeStructT = typename OtherRootNode::NodeStruct; 3316 using OtherMapCIterT = typename OtherRootNode::MapCIter; 3317 3318 CombineArgs<ValueType, OtherValueT> args; 3319 3320 CoordSet keys; 3321 other0.insertKeys(keys); 3322 other1.insertKeys(keys); 3323 3324 const NodeStruct bg0(Tile(other0.mBackground, /*active=*/false)); 3325 const OtherNodeStructT bg1(OtherTileT(other1.mBackground, /*active=*/false)); 3326 3327 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) { 3328 MapIter thisIter = this->findOrAddCoord(*i); 3329 MapCIter iter0 = other0.findKey(*i); 3330 OtherMapCIterT iter1 = other1.findKey(*i); 3331 const NodeStruct& ns0 = (iter0 != other0.mTable.end()) ? iter0->second : bg0; 3332 const OtherNodeStructT& ns1 = (iter1 != other1.mTable.end()) ? iter1->second : bg1; 3333 if (ns0.isTile() && ns1.isTile()) { 3334 // Both input nodes have constant values (tiles). 3335 // Combine the two values and add a new tile to this node with the result. 3336 op(args.setARef(ns0.tile.value) 3337 .setAIsActive(ns0.isTileOn()) 3338 .setBRef(ns1.tile.value) 3339 .setBIsActive(ns1.isTileOn())); 3340 setTile(thisIter, Tile(args.result(), args.resultIsActive())); 3341 } else { 3342 if (!isChild(thisIter)) { 3343 // Add a new child with the same coordinates, etc. as the other node's child. 3344 const Coord& childOrigin = 3345 ns0.isChild() ? ns0.child->origin() : ns1.child->origin(); 3346 setChild(thisIter, *(new ChildT(childOrigin, getTile(thisIter).value))); 3347 } 3348 ChildT& child = getChild(thisIter); 3349 3350 if (ns0.isTile()) { 3351 // Combine node1's child with node0's constant value 3352 // and write the result into this node's child. 3353 child.combine2(ns0.tile.value, *ns1.child, ns0.isTileOn(), op); 3354 } else if (ns1.isTile()) { 3355 // Combine node0's child with node1's constant value 3356 // and write the result into this node's child. 3357 child.combine2(*ns0.child, ns1.tile.value, ns1.isTileOn(), op); 3358 } else { 3359 // Combine node0's child with node1's child 3360 // and write the result into this node's child. 3361 child.combine2(*ns0.child, *ns1.child, op); 3362 } 3363 } 3364 if (prune && isChild(thisIter)) getChild(thisIter).prune(); 3365 } 3366 3367 // Combine background values. 3368 op(args.setARef(other0.mBackground).setBRef(other1.mBackground)); 3369 mBackground = args.result(); 3370 } 3371 3372 3373 //////////////////////////////////////// 3374 3375 3376 template<typename ChildT> 3377 template<typename BBoxOp> 3378 inline void 3379 RootNode<ChildT>::visitActiveBBox(BBoxOp& op) const 3380 { 3381 const bool descent = op.template descent<LEVEL>(); 3382 for (MapCIter i = mTable.begin(), e = mTable.end(); i != e; ++i) { 3383 if (this->isTileOff(i)) continue; 3384 if (this->isChild(i) && descent) { 3385 this->getChild(i).visitActiveBBox(op); 3386 } else { 3387 op.template operator()<LEVEL>(CoordBBox::createCube(i->first, ChildT::DIM)); 3388 } 3389 } 3390 } 3391 3392 3393 template<typename ChildT> 3394 template<typename VisitorOp> 3395 inline void 3396 RootNode<ChildT>::visit(VisitorOp& op) 3397 { 3398 doVisit<RootNode, VisitorOp, ChildAllIter>(*this, op); 3399 } 3400 3401 3402 template<typename ChildT> 3403 template<typename VisitorOp> 3404 inline void 3405 RootNode<ChildT>::visit(VisitorOp& op) const 3406 { 3407 doVisit<const RootNode, VisitorOp, ChildAllCIter>(*this, op); 3408 } 3409 3410 3411 template<typename ChildT> 3412 template<typename RootNodeT, typename VisitorOp, typename ChildAllIterT> 3413 inline void 3414 RootNode<ChildT>::doVisit(RootNodeT& self, VisitorOp& op) 3415 { 3416 typename RootNodeT::ValueType val; 3417 for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) { 3418 if (op(iter)) continue; 3419 if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) { 3420 child->visit(op); 3421 } 3422 } 3423 } 3424 3425 3426 //////////////////////////////////////// 3427 3428 3429 template<typename ChildT> 3430 template<typename OtherRootNodeType, typename VisitorOp> 3431 inline void 3432 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) 3433 { 3434 doVisit2<RootNode, OtherRootNodeType, VisitorOp, ChildAllIter, 3435 typename OtherRootNodeType::ChildAllIter>(*this, other, op); 3436 } 3437 3438 3439 template<typename ChildT> 3440 template<typename OtherRootNodeType, typename VisitorOp> 3441 inline void 3442 RootNode<ChildT>::visit2(OtherRootNodeType& other, VisitorOp& op) const 3443 { 3444 doVisit2<const RootNode, OtherRootNodeType, VisitorOp, ChildAllCIter, 3445 typename OtherRootNodeType::ChildAllCIter>(*this, other, op); 3446 } 3447 3448 3449 template<typename ChildT> 3450 template< 3451 typename RootNodeT, 3452 typename OtherRootNodeT, 3453 typename VisitorOp, 3454 typename ChildAllIterT, 3455 typename OtherChildAllIterT> 3456 inline void 3457 RootNode<ChildT>::doVisit2(RootNodeT& self, OtherRootNodeT& other, VisitorOp& op) 3458 { 3459 enforceSameConfiguration(other); 3460 3461 typename RootNodeT::ValueType val; 3462 typename OtherRootNodeT::ValueType otherVal; 3463 3464 // The two nodes are required to have corresponding table entries, 3465 // but since that might require background tiles to be added to one or both, 3466 // and the nodes might be const, we operate on shallow copies of the nodes instead. 3467 RootNodeT copyOfSelf(self.mBackground); 3468 copyOfSelf.mTable = self.mTable; 3469 OtherRootNodeT copyOfOther(other.mBackground); 3470 copyOfOther.mTable = other.mTable; 3471 3472 // Add background tiles to both nodes as needed. 3473 CoordSet keys; 3474 self.insertKeys(keys); 3475 other.insertKeys(keys); 3476 for (CoordSetCIter i = keys.begin(), e = keys.end(); i != e; ++i) { 3477 copyOfSelf.findOrAddCoord(*i); 3478 copyOfOther.findOrAddCoord(*i); 3479 } 3480 3481 ChildAllIterT iter = copyOfSelf.beginChildAll(); 3482 OtherChildAllIterT otherIter = copyOfOther.beginChildAll(); 3483 3484 for ( ; iter && otherIter; ++iter, ++otherIter) 3485 { 3486 const size_t skipBranch = static_cast<size_t>(op(iter, otherIter)); 3487 3488 typename ChildAllIterT::ChildNodeType* child = 3489 (skipBranch & 1U) ? nullptr : iter.probeChild(val); 3490 typename OtherChildAllIterT::ChildNodeType* otherChild = 3491 (skipBranch & 2U) ? nullptr : otherIter.probeChild(otherVal); 3492 3493 if (child != nullptr && otherChild != nullptr) { 3494 child->visit2Node(*otherChild, op); 3495 } else if (child != nullptr) { 3496 child->visit2(otherIter, op); 3497 } else if (otherChild != nullptr) { 3498 otherChild->visit2(iter, op, /*otherIsLHS=*/true); 3499 } 3500 } 3501 // Remove any background tiles that were added above, 3502 // as well as any that were created by the visitors. 3503 copyOfSelf.eraseBackgroundTiles(); 3504 copyOfOther.eraseBackgroundTiles(); 3505 3506 // If either input node is non-const, replace its table with 3507 // the (possibly modified) copy. 3508 self.resetTable(copyOfSelf.mTable); 3509 other.resetTable(copyOfOther.mTable); 3510 } 3511 3512 } // namespace tree 3513 } // namespace OPENVDB_VERSION_NAME 3514 } // namespace openvdb 3515 3516 #endif // OPENVDB_TREE_ROOTNODE_HAS_BEEN_INCLUDED 3517