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