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