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