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  /// @brief Calls the templated functor BBoxOp with bounding box
572  /// information for all active tiles and leaf nodes in this node.
573  /// An additional level argument is provided for each callback.
574  ///
575  /// @note The bounding boxes are guaranteed to be non-overlapping.
576  template<typename BBoxOp> void visitActiveBBox(BBoxOp&) const;
577 
578  template<typename VisitorOp> void visit(VisitorOp&);
579  template<typename VisitorOp> void visit(VisitorOp&) const;
580 
581  template<typename OtherNodeType, typename VisitorOp>
582  void visit2Node(OtherNodeType& other, VisitorOp&);
583  template<typename OtherNodeType, typename VisitorOp>
584  void visit2Node(OtherNodeType& other, VisitorOp&) const;
585  template<typename IterT, typename VisitorOp>
586  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false);
587  template<typename IterT, typename VisitorOp>
588  void visit2(IterT& otherIter, VisitorOp&, bool otherIsLHS = false) const;
589 
590  /// Set all voxels that lie outside the given axis-aligned box to the background.
591  void clip(const CoordBBox&, const ValueType& background);
592 
593  /// @brief Reduce the memory footprint of this tree by replacing with tiles
594  /// any nodes whose values are all the same (optionally to within a tolerance)
595  /// and have the same active state.
596  void prune(const ValueType& tolerance = zeroVal<ValueType>());
597 
598  /// @brief Add the specified leaf to this node, possibly creating a child branch
599  /// in the process. If the leaf node already exists, replace it.
600  void addLeaf(LeafNodeType* leaf);
601 
602  /// @brief Same as addLeaf() except, if necessary, update the accessor with pointers
603  /// to the nodes along the path from the root node to the node containing the coordinate.
604  template<typename AccessorT>
605  void addLeafAndCache(LeafNodeType* leaf, AccessorT&);
606 
607  /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
608  /// and replace it with a tile of the specified value and state.
609  /// If no such node exists, leave the tree unchanged and return @c nullptr.
610  ///
611  /// @note The caller takes ownership of the node and is responsible for deleting it.
612  ///
613  /// @warning Since this method potentially removes nodes and branches of the tree,
614  /// it is important to clear the caches of all ValueAccessors associated with this tree.
615  template<typename NodeT>
616  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool state);
617 
618  /// @brief Add the given child node at this level deducing the offset from it's origin.
619  /// If a child node with this offset already exists, delete the old node and add the
620  /// new node in its place (i.e. ownership of the new child node is transferred to
621  /// this InternalNode)
622  /// @return @c true if inserting the child has been successful, otherwise the caller
623  /// retains ownership of the node and is responsible for deleting it.
624  bool addChild(ChildNodeType* child);
625 
626  /// @brief Add a tile at the specified tree level that contains voxel (x, y, z),
627  /// possibly creating a parent branch or deleting a child branch in the process.
628  void addTile(Index level, const Coord& xyz, const ValueType& value, bool state);
629 
630  /// @brief Delete any existing child branch at the specified offset and add a tile.
631  void addTile(Index offset, const ValueType& value, bool state);
632 
633  /// @brief Same as addTile() except, if necessary, update the accessor with pointers
634  /// to the nodes along the path from the root node to the node containing (x, y, z).
635  template<typename AccessorT>
636  void addTileAndCache(Index level, const Coord& xyz, const ValueType&, bool state, AccessorT&);
637 
638  //@{
639  /// @brief Return a pointer to the node that contains voxel (x, y, z).
640  /// If no such node exists, return nullptr.
641  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
642  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
643  //@}
644 
645  //@{
646  /// @brief Same as probeNode() except, if necessary, update the accessor with pointers
647  /// to the nodes along the path from the root node to the node containing (x, y, z).
648  template<typename NodeType, typename AccessorT>
649  NodeType* probeNodeAndCache(const Coord& xyz, AccessorT&);
650  template<typename NodeType, typename AccessorT>
651  const NodeType* probeConstNodeAndCache(const Coord& xyz, AccessorT&) const;
652  //@}
653 
654  //@{
655  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
656  /// If no such node exists, return @c nullptr.
657  LeafNodeType* probeLeaf(const Coord& xyz);
658  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
659  const LeafNodeType* probeLeaf(const Coord& xyz) const;
660  //@}
661 
662  //@{
663  /// @brief Same as probeLeaf() except, if necessary, update the accessor with pointers
664  /// to the nodes along the path from the root node to the node containing (x, y, z).
665  template<typename AccessorT>
666  LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc);
667  template<typename AccessorT>
668  const LeafNodeType* probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const;
669  template<typename AccessorT>
670  const LeafNodeType* probeLeafAndCache(const Coord& xyz, AccessorT& acc) const;
671  //@}
672 
673  /// @brief Return the leaf node that contains voxel (x, y, z).
674  /// If no such node exists, create one, but preserve the values and
675  /// active states of all voxels.
676  ///
677  /// @details Use this method to preallocate a static tree topology
678  /// over which to safely perform multithreaded processing.
679  LeafNodeType* touchLeaf(const Coord& xyz);
680 
681  /// @brief Same as touchLeaf() except, if necessary, update the accessor with pointers
682  /// to the nodes along the path from the root node to the node containing the coordinate.
683  template<typename AccessorT>
684  LeafNodeType* touchLeafAndCache(const Coord& xyz, AccessorT&);
685 
686  //@{
687  /// @brief Adds all nodes of a certain type to a container with the following API:
688  /// @code
689  /// struct ArrayT {
690  /// using value_type = ...;// defines the type of nodes to be added to the array
691  /// void push_back(value_type nodePtr);// method that add nodes to the array
692  /// };
693  /// @endcode
694  /// @details An example of a wrapper around a c-style array is:
695  /// @code
696  /// struct MyArray {
697  /// using value_type = LeafType*;
698  /// value_type* ptr;
699  /// MyArray(value_type* array) : ptr(array) {}
700  /// void push_back(value_type leaf) { *ptr++ = leaf; }
701  ///};
702  /// @endcode
703  /// @details An example that constructs a list of pointer to all leaf nodes is:
704  /// @code
705  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
706  /// array.reserve(tree.leafCount());//this is a fast preallocation.
707  /// tree.getNodes(array);
708  /// @endcode
709  template<typename ArrayT>
710  void getNodes(ArrayT& array);
711  template<typename ArrayT>
712  void getNodes(ArrayT& array) const;
713  //@}
714 
715  /// @brief Steals all nodes of a certain type from the tree and
716  /// adds them to a container with the following API:
717  /// @code
718  /// struct ArrayT {
719  /// using value_type = ...;// defines the type of nodes to be added to the array
720  /// void push_back(value_type nodePtr);// method that add nodes to the array
721  /// };
722  /// @endcode
723  /// @details An example of a wrapper around a c-style array is:
724  /// @code
725  /// struct MyArray {
726  /// using value_type = LeafType*;
727  /// value_type* ptr;
728  /// MyArray(value_type* array) : ptr(array) {}
729  /// void push_back(value_type leaf) { *ptr++ = leaf; }
730  ///};
731  /// @endcode
732  /// @details An example that constructs a list of pointer to all leaf nodes is:
733  /// @code
734  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
735  /// array.reserve(tree.leafCount());//this is a fast preallocation.
736  /// tree.stealNodes(array);
737  /// @endcode
738  template<typename ArrayT>
739  void stealNodes(ArrayT& array, const ValueType& value, bool state);
740 
741  /// @brief Change inactive tiles or voxels with value oldBackground to newBackground
742  /// or -oldBackground to -newBackground. Active values are unchanged.
743  void resetBackground(const ValueType& oldBackground, const ValueType& newBackground);
744 
745  /// @brief Return @c true if the given tree branch has the same node and active value
746  /// topology as this tree branch (but possibly a different @c ValueType).
747  template<typename OtherChildNodeType, Index OtherLog2Dim>
749 
750 protected:
751  //@{
752  /// Allow iterators to call mask accessor methods (setValueMask(), setChildMask(), etc.).
753  /// @todo Make mask accessors public?
757  //@}
758 
759  /// @brief During topology-only construction, access is needed
760  /// to protected/private members of other template instances.
761  template<typename, Index> friend class InternalNode;
762 
763  // Mask accessors
764 public:
765  bool isValueMaskOn(Index n) const { return mValueMask.isOn(n); }
766  bool isValueMaskOn() const { return mValueMask.isOn(); }
767  bool isValueMaskOff(Index n) const { return mValueMask.isOff(n); }
768  bool isValueMaskOff() const { return mValueMask.isOff(); }
769  bool isChildMaskOn(Index n) const { return mChildMask.isOn(n); }
770  bool isChildMaskOff(Index n) const { return mChildMask.isOff(n); }
771  bool isChildMaskOff() const { return mChildMask.isOff(); }
772  const NodeMaskType& getValueMask() const { return mValueMask; }
773  const NodeMaskType& getChildMask() const { return mChildMask; }
775  {
777  mask |= mChildMask;
778  mask.toggle();
779  return mask;
780  }
781  const UnionType* getTable() const { return mNodes; }
782 protected:
783  //@{
784  /// Use a mask accessor to ensure consistency between the child and value masks;
785  /// i.e., the value mask should always be off wherever the child mask is on.
786  void setValueMask(Index n, bool on) { mValueMask.set(n, mChildMask.isOn(n) ? false : on); }
787  //@}
788 
789  void makeChildNodeEmpty(Index n, const ValueType& value);
790  void setChildNode( Index i, ChildNodeType* child);//assumes a tile
791  void resetChildNode(Index i, ChildNodeType* child);//checks for an existing child
793 
794  template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
795  static inline void doVisit(NodeT&, VisitorOp&);
796 
797  template<typename NodeT, typename OtherNodeT, typename VisitorOp,
798  typename ChildAllIterT, typename OtherChildAllIterT>
799  static inline void doVisit2Node(NodeT&, OtherNodeT&, VisitorOp&);
800 
801  template<typename NodeT, typename VisitorOp,
802  typename ChildAllIterT, typename OtherChildAllIterT>
803  static inline void doVisit2(NodeT&, OtherChildAllIterT&, VisitorOp&, bool otherIsLHS);
804 
805  ///@{
806  /// @brief Returns a pointer to the child node at the linear offset n.
807  /// @warning This protected method assumes that a child node exists at
808  /// the specified linear offset!
810  const ChildNodeType* getChildNode(Index n) const;
811  ///@}
812 
813  ///@{
814  /// @brief Protected member classes for recursive multi-threading
815  struct VoxelizeActiveTiles;
816  template<typename OtherInternalNode> struct DeepCopy;
817  template<typename OtherInternalNode> struct TopologyCopy1;
818  template<typename OtherInternalNode> struct TopologyCopy2;
819  template<typename OtherInternalNode> struct TopologyUnion;
820  template<typename OtherInternalNode> struct TopologyDifference;
821  template<typename OtherInternalNode> struct TopologyIntersection;
822  ///@}
823 
826  /// Global grid index coordinates (x,y,z) of the local origin of this node
827  Coord mOrigin;
828 #if OPENVDB_ABI_VERSION_NUMBER >= 9
829  /// Transient data (not serialized)
830  Index32 mTransientData = 0;
831 #endif
832 }; // class InternalNode
833 
834 
835 ////////////////////////////////////////
836 
837 
838 //@{
839 /// Helper metafunction used to implement InternalNode::SameConfiguration
840 /// (which, as an inner class, can't be independently specialized)
841 template<typename ChildT1, Index Dim1, typename NodeT2>
842 struct SameInternalConfig {
843  static const bool value = false;
844 };
845 
846 template<typename ChildT1, Index Dim1, typename ChildT2>
847 struct SameInternalConfig<ChildT1, Dim1, InternalNode<ChildT2, Dim1> > {
848  static const bool value = ChildT1::template SameConfiguration<ChildT2>::value;
849 };
850 //@}
851 
852 
853 ////////////////////////////////////////
854 
855 
856 template<typename ChildT, Index Log2Dim>
857 inline
859 {
860  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(background);
861 }
862 
863 
864 template<typename ChildT, Index Log2Dim>
865 inline
866 InternalNode<ChildT, Log2Dim>::InternalNode(const Coord& origin, const ValueType& val, bool active):
867  mOrigin(origin[0] & ~(DIM - 1), // zero out the low-order bits
868  origin[1] & ~(DIM - 1),
869  origin[2] & ~(DIM - 1))
870 {
871  if (active) mValueMask.setOn();
872  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
873 }
874 
875 
876 // For InternalNodes, the PartialCreate constructor is identical to its
877 // non-PartialCreate counterpart.
878 template<typename ChildT, Index Log2Dim>
879 inline
881  const Coord& origin, const ValueType& val, bool active)
882  : mOrigin(origin[0] & ~(DIM-1), origin[1] & ~(DIM-1), origin[2] & ~(DIM-1))
883 {
884  if (active) mValueMask.setOn();
885  for (Index i = 0; i < NUM_VALUES; ++i) mNodes[i].setValue(val);
886 }
887 
888 template<typename ChildT, Index Log2Dim>
889 template<typename OtherInternalNode>
890 struct InternalNode<ChildT, Log2Dim>::DeepCopy
891 {
892  DeepCopy(const OtherInternalNode* source, InternalNode* target) : s(source), t(target) {
893  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
894  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
895  }
896  void operator()(const tbb::blocked_range<Index> &r) const {
897  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
898  if (s->mChildMask.isOff(i)) {
899  t->mNodes[i].setValue(ValueType(s->mNodes[i].getValue()));
900  } else {
901  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild())));
902  }
903  }
904  }
905  const OtherInternalNode* s;
907 };// DeepCopy
908 
909 template<typename ChildT, Index Log2Dim>
910 inline
912  : mChildMask(other.mChildMask)
913  , mValueMask(other.mValueMask)
914  , mOrigin(other.mOrigin)
916  , mTransientData(other.mTransientData)
917 #endif
918 {
919  DeepCopy<InternalNode<ChildT, Log2Dim> > tmp(&other, this);
920 }
921 
922 
923 // Copy-construct from a node with the same configuration but a different ValueType.
924 template<typename ChildT, Index Log2Dim>
925 template<typename OtherChildNodeType>
926 inline
928  : mChildMask(other.mChildMask)
929  , mValueMask(other.mValueMask)
930  , mOrigin(other.mOrigin)
932  , mTransientData(other.mTransientData)
933 #endif
934 {
936 }
937 
938 template<typename ChildT, Index Log2Dim>
939 template<typename OtherInternalNode>
940 struct InternalNode<ChildT, Log2Dim>::TopologyCopy1
941 {
942  TopologyCopy1(const OtherInternalNode* source, InternalNode* target,
943  const ValueType& background) : s(source), t(target), b(background) {
944  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
945  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//serial
946  }
947  void operator()(const tbb::blocked_range<Index> &r) const {
948  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
949  if (s->isChildMaskOn(i)) {
950  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
951  b, TopologyCopy()));
952  } else {
953  t->mNodes[i].setValue(b);
954  }
955  }
956  }
957  const OtherInternalNode* s;
959  const ValueType &b;
960 };// TopologyCopy1
961 
962 template<typename ChildT, Index Log2Dim>
963 template<typename OtherChildNodeType>
964 inline
966  const ValueType& background, TopologyCopy)
967  : mChildMask(other.mChildMask)
968  , mValueMask(other.mValueMask)
969  , mOrigin(other.mOrigin)
971  , mTransientData(other.mTransientData)
972 #endif
973 {
974  TopologyCopy1<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, background);
975 }
976 
977 template<typename ChildT, Index Log2Dim>
978 template<typename OtherInternalNode>
979 struct InternalNode<ChildT, Log2Dim>::TopologyCopy2
980 {
981  TopologyCopy2(const OtherInternalNode* source, InternalNode* target,
982  const ValueType& offValue, const ValueType& onValue)
983  : s(source), t(target), offV(offValue), onV(onValue) {
984  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
985  }
986  void operator()(const tbb::blocked_range<Index> &r) const {
987  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
988  if (s->isChildMaskOn(i)) {
989  t->mNodes[i].setChild(new ChildNodeType(*(s->mNodes[i].getChild()),
990  offV, onV, TopologyCopy()));
991  } else {
992  t->mNodes[i].setValue(s->isValueMaskOn(i) ? onV : offV);
993  }
994  }
995  }
996  const OtherInternalNode* s;
998  const ValueType &offV, &onV;
999  };// TopologyCopy2
1000 
1001 template<typename ChildT, Index Log2Dim>
1002 template<typename OtherChildNodeType>
1003 inline
1005  const ValueType& offValue,
1006  const ValueType& onValue, TopologyCopy)
1007  : mChildMask(other.mChildMask)
1008  , mValueMask(other.mValueMask)
1009  , mOrigin(other.mOrigin)
1011  , mTransientData(other.mTransientData)
1012 #endif
1013 {
1014  TopologyCopy2<InternalNode<OtherChildNodeType, Log2Dim> > tmp(&other, this, offValue, onValue);
1015 }
1016 
1017 
1018 template<typename ChildT, Index Log2Dim>
1019 inline
1021 {
1022  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1023  delete mNodes[iter.pos()].getChild();
1024  }
1025 }
1026 
1027 
1028 ////////////////////////////////////////
1029 
1030 
1031 template<typename ChildT, Index Log2Dim>
1032 inline Index32
1034 {
1035  if (ChildNodeType::getLevel() == 0) return mChildMask.countOn();
1036  Index32 sum = 0;
1037  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1038  sum += iter->leafCount();
1039  }
1040  return sum;
1041 }
1042 
1043 template<typename ChildT, Index Log2Dim>
1044 inline void
1045 InternalNode<ChildT, Log2Dim>::nodeCount(std::vector<Index32> &vec) const
1046 {
1047  assert(vec.size() > ChildNodeType::LEVEL);
1048  const auto count = mChildMask.countOn();
1049  if (ChildNodeType::LEVEL > 0 && count > 0) {
1050  for (auto iter = this->cbeginChildOn(); iter; ++iter) iter->nodeCount(vec);
1051  }
1052  vec[ChildNodeType::LEVEL] += count;
1053 }
1054 
1055 
1056 template<typename ChildT, Index Log2Dim>
1057 inline Index32
1059 {
1060  Index32 sum = 1;
1061  if (ChildNodeType::getLevel() == 0) return sum;
1062  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1063  sum += iter->nonLeafCount();
1064  }
1065  return sum;
1066 }
1067 
1068 
1069 template<typename ChildT, Index Log2Dim>
1070 inline Index32
1072 {
1073  return this->getChildMask().countOn();
1074 }
1075 
1076 
1077 template<typename ChildT, Index Log2Dim>
1078 inline Index64
1080 {
1081  Index64 sum = ChildT::NUM_VOXELS * mValueMask.countOn();
1082  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1083  sum += iter->onVoxelCount();
1084  }
1085  return sum;
1086 }
1087 
1088 
1089 template<typename ChildT, Index Log2Dim>
1090 inline Index64
1092 {
1093  Index64 sum = ChildT::NUM_VOXELS * (NUM_VALUES-mValueMask.countOn()-mChildMask.countOn());
1094  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1095  sum += iter->offVoxelCount();
1096  }
1097  return sum;
1098 }
1099 
1100 
1101 template<typename ChildT, Index Log2Dim>
1102 inline Index64
1104 {
1105  Index64 sum = 0;
1106  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1107  sum += mNodes[iter.pos()].getChild()->onLeafVoxelCount();
1108  }
1109  return sum;
1110 }
1111 
1112 
1113 template<typename ChildT, Index Log2Dim>
1114 inline Index64
1116 {
1117  Index64 sum = 0;
1118  for (ChildOnCIter iter = this->beginChildOn(); iter; ++iter) {
1119  sum += mNodes[iter.pos()].getChild()->offLeafVoxelCount();
1120  }
1121  return sum;
1122 }
1123 
1124 template<typename ChildT, Index Log2Dim>
1125 inline Index64
1127 {
1128  Index64 sum = mValueMask.countOn();
1129  for (ChildOnCIter iter = this->cbeginChildOn(); LEVEL>1 && iter; ++iter) {
1130  sum += iter->onTileCount();
1131  }
1132  return sum;
1133 }
1134 
1135 template<typename ChildT, Index Log2Dim>
1136 inline Index64
1138 {
1139  Index64 sum = NUM_VALUES * sizeof(UnionType) + mChildMask.memUsage()
1140  + mValueMask.memUsage() + sizeof(mOrigin);
1141  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1142  sum += iter->memUsage();
1143  }
1144  return sum;
1145 }
1146 
1147 
1148 template<typename ChildT, Index Log2Dim>
1149 inline void
1150 InternalNode<ChildT, Log2Dim>::evalActiveBoundingBox(CoordBBox& bbox, bool visitVoxels) const
1151 {
1152  if (bbox.isInside(this->getNodeBoundingBox())) return;
1153 
1154  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
1155  bbox.expand(i.getCoord(), ChildT::DIM);
1156  }
1157  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
1158  i->evalActiveBoundingBox(bbox, visitVoxels);
1159  }
1160 }
1161 
1162 
1163 ////////////////////////////////////////
1164 
1165 
1166 template<typename ChildT, Index Log2Dim>
1167 inline void
1169 {
1170  bool state = false;
1171  ValueType value = zeroVal<ValueType>();
1172  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1173  const Index i = iter.pos();
1174  ChildT* child = mNodes[i].getChild();
1175  child->prune(tolerance);
1176  if (child->isConstant(value, state, tolerance)) {
1177  delete child;
1178  mChildMask.setOff(i);
1179  mValueMask.set(i, state);
1180  mNodes[i].setValue(value);
1181  }
1182  }
1183 }
1184 
1185 
1186 ////////////////////////////////////////
1187 
1188 
1189 template<typename ChildT, Index Log2Dim>
1190 template<typename NodeT>
1191 inline NodeT*
1192 InternalNode<ChildT, Log2Dim>::stealNode(const Coord& xyz, const ValueType& value, bool state)
1193 {
1194  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1195  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1197  const Index n = this->coordToOffset(xyz);
1198  if (mChildMask.isOff(n)) return nullptr;
1199  ChildT* child = mNodes[n].getChild();
1201  mChildMask.setOff(n);
1202  mValueMask.set(n, state);
1203  mNodes[n].setValue(value);
1204  }
1206  ? reinterpret_cast<NodeT*>(child)
1207  : child->template stealNode<NodeT>(xyz, value, state);
1209 }
1210 
1211 
1212 ////////////////////////////////////////
1213 
1214 
1215 template<typename ChildT, Index Log2Dim>
1216 template<typename NodeT>
1217 inline NodeT*
1219 {
1220  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1221  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1223  const Index n = this->coordToOffset(xyz);
1224  if (mChildMask.isOff(n)) return nullptr;
1225  ChildT* child = mNodes[n].getChild();
1227  ? reinterpret_cast<NodeT*>(child)
1228  : child->template probeNode<NodeT>(xyz);
1230 }
1231 
1232 
1233 template<typename ChildT, Index Log2Dim>
1234 template<typename NodeT, typename AccessorT>
1235 inline NodeT*
1236 InternalNode<ChildT, Log2Dim>::probeNodeAndCache(const Coord& xyz, AccessorT& acc)
1237 {
1238  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1239  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1241  const Index n = this->coordToOffset(xyz);
1242  if (mChildMask.isOff(n)) return nullptr;
1243  ChildT* child = mNodes[n].getChild();
1244  acc.insert(xyz, child);
1246  ? reinterpret_cast<NodeT*>(child)
1247  : child->template probeNodeAndCache<NodeT>(xyz, acc);
1249 }
1250 
1251 
1252 template<typename ChildT, Index Log2Dim>
1253 template<typename NodeT>
1254 inline const NodeT*
1256 {
1257  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1258  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1260  const Index n = this->coordToOffset(xyz);
1261  if (mChildMask.isOff(n)) return nullptr;
1262  const ChildT* child = mNodes[n].getChild();
1264  ? reinterpret_cast<const NodeT*>(child)
1265  : child->template probeConstNode<NodeT>(xyz);
1267 }
1268 
1269 
1270 template<typename ChildT, Index Log2Dim>
1271 template<typename NodeT, typename AccessorT>
1272 inline const NodeT*
1273 InternalNode<ChildT, Log2Dim>::probeConstNodeAndCache(const Coord& xyz, AccessorT& acc) const
1274 {
1275  if ((NodeT::LEVEL == ChildT::LEVEL && !(std::is_same<NodeT, ChildT>::value)) ||
1276  NodeT::LEVEL > ChildT::LEVEL) return nullptr;
1278  const Index n = this->coordToOffset(xyz);
1279  if (mChildMask.isOff(n)) return nullptr;
1280  const ChildT* child = mNodes[n].getChild();
1281  acc.insert(xyz, child);
1283  ? reinterpret_cast<const NodeT*>(child)
1284  : child->template probeConstNodeAndCache<NodeT>(xyz, acc);
1286 }
1287 
1288 
1289 ////////////////////////////////////////
1290 
1291 
1292 template<typename ChildT, Index Log2Dim>
1293 inline typename ChildT::LeafNodeType*
1295 {
1296  return this->template probeNode<LeafNodeType>(xyz);
1297 }
1298 
1299 
1300 template<typename ChildT, Index Log2Dim>
1301 template<typename AccessorT>
1302 inline typename ChildT::LeafNodeType*
1303 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc)
1304 {
1305  return this->template probeNodeAndCache<LeafNodeType>(xyz, acc);
1306 }
1307 
1308 
1309 template<typename ChildT, Index Log2Dim>
1310 template<typename AccessorT>
1311 inline const typename ChildT::LeafNodeType*
1312 InternalNode<ChildT, Log2Dim>::probeLeafAndCache(const Coord& xyz, AccessorT& acc) const
1313 {
1314  return this->probeConstLeafAndCache(xyz, acc);
1315 }
1316 
1317 
1318 template<typename ChildT, Index Log2Dim>
1319 inline const typename ChildT::LeafNodeType*
1321 {
1322  return this->template probeConstNode<LeafNodeType>(xyz);
1323 }
1324 
1325 
1326 template<typename ChildT, Index Log2Dim>
1327 template<typename AccessorT>
1328 inline const typename ChildT::LeafNodeType*
1329 InternalNode<ChildT, Log2Dim>::probeConstLeafAndCache(const Coord& xyz, AccessorT& acc) const
1330 {
1331  return this->template probeConstNodeAndCache<LeafNodeType>(xyz, acc);
1332 }
1333 
1334 
1335 ////////////////////////////////////////
1336 
1337 
1338 template<typename ChildT, Index Log2Dim>
1339 inline void
1341 {
1342  assert(leaf != nullptr);
1343  const Coord& xyz = leaf->origin();
1344  const Index n = this->coordToOffset(xyz);
1345  ChildT* child = nullptr;
1346  if (mChildMask.isOff(n)) {
1347  if (ChildT::LEVEL>0) {
1348  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1349  } else {
1350  child = reinterpret_cast<ChildT*>(leaf);
1351  }
1352  this->setChildNode(n, child);
1353  } else {
1354  if (ChildT::LEVEL>0) {
1355  child = mNodes[n].getChild();
1356  } else {
1357  delete mNodes[n].getChild();
1358  child = reinterpret_cast<ChildT*>(leaf);
1359  mNodes[n].setChild(child);
1360  }
1361  }
1362  child->addLeaf(leaf);
1363 }
1364 
1365 
1366 template<typename ChildT, Index Log2Dim>
1367 template<typename AccessorT>
1368 inline void
1370 {
1371  assert(leaf != nullptr);
1372  const Coord& xyz = leaf->origin();
1373  const Index n = this->coordToOffset(xyz);
1374  ChildT* child = nullptr;
1375  if (mChildMask.isOff(n)) {
1376  if (ChildT::LEVEL>0) {
1377  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1378  acc.insert(xyz, child);//we only cache internal nodes
1379  } else {
1380  child = reinterpret_cast<ChildT*>(leaf);
1381  }
1382  this->setChildNode(n, child);
1383  } else {
1384  if (ChildT::LEVEL>0) {
1385  child = mNodes[n].getChild();
1386  acc.insert(xyz, child);//we only cache internal nodes
1387  } else {
1388  delete mNodes[n].getChild();
1389  child = reinterpret_cast<ChildT*>(leaf);
1390  mNodes[n].setChild(child);
1391  }
1392  }
1393  child->addLeafAndCache(leaf, acc);
1394 }
1395 
1396 
1397 ////////////////////////////////////////
1398 
1399 
1400 template<typename ChildT, Index Log2Dim>
1401 inline bool
1403 {
1404  assert(child);
1405  const Coord& xyz = child->origin();
1406  // verify that the child belongs in this internal node
1407  if (Coord((xyz & ~(DIM-1))) != this->origin()) return false;
1408  // compute the offset and insert the child node
1409  const Index n = this->coordToOffset(xyz);
1410  // this also deletes an existing child node
1411  this->resetChildNode(n, child);
1412  return true;
1413 }
1414 
1415 
1416 template<typename ChildT, Index Log2Dim>
1417 inline void
1419 {
1420  assert(n < NUM_VALUES);
1421  this->makeChildNodeEmpty(n, value);
1422  mValueMask.set(n, state);
1423 }
1424 
1425 
1426 template<typename ChildT, Index Log2Dim>
1427 inline void
1429  const ValueType& value, bool state)
1430 {
1431  if (LEVEL >= level) {
1432  const Index n = this->coordToOffset(xyz);
1433  if (mChildMask.isOff(n)) {// tile case
1434  if (LEVEL > level) {
1435  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1436  this->setChildNode(n, child);
1437  child->addTile(level, xyz, value, state);
1438  } else {
1439  mValueMask.set(n, state);
1440  mNodes[n].setValue(value);
1441  }
1442  } else {// child branch case
1443  ChildT* child = mNodes[n].getChild();
1444  if (LEVEL > level) {
1445  child->addTile(level, xyz, value, state);
1446  } else {
1447  delete child;
1448  mChildMask.setOff(n);
1449  mValueMask.set(n, state);
1450  mNodes[n].setValue(value);
1451  }
1452  }
1453  }
1454 }
1455 
1456 
1457 template<typename ChildT, Index Log2Dim>
1458 template<typename AccessorT>
1459 inline void
1461  const ValueType& value, bool state, AccessorT& acc)
1462 {
1463  if (LEVEL >= level) {
1464  const Index n = this->coordToOffset(xyz);
1465  if (mChildMask.isOff(n)) {// tile case
1466  if (LEVEL > level) {
1467  ChildT* child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1468  this->setChildNode(n, child);
1469  acc.insert(xyz, child);
1470  child->addTileAndCache(level, xyz, value, state, acc);
1471  } else {
1472  mValueMask.set(n, state);
1473  mNodes[n].setValue(value);
1474  }
1475  } else {// child branch case
1476  ChildT* child = mNodes[n].getChild();
1477  if (LEVEL > level) {
1478  acc.insert(xyz, child);
1479  child->addTileAndCache(level, xyz, value, state, acc);
1480  } else {
1481  delete child;
1482  mChildMask.setOff(n);
1483  mValueMask.set(n, state);
1484  mNodes[n].setValue(value);
1485  }
1486  }
1487  }
1488 }
1489 
1490 
1491 ////////////////////////////////////////
1492 
1493 
1494 template<typename ChildT, Index Log2Dim>
1495 inline typename ChildT::LeafNodeType*
1497 {
1498  const Index n = this->coordToOffset(xyz);
1499  ChildT* child = nullptr;
1500  if (mChildMask.isOff(n)) {
1501  child = new ChildT(xyz, mNodes[n].getValue(), mValueMask.isOn(n));
1502  this->setChildNode(n, child);
1503  } else {
1504  child = mNodes[n].getChild();
1505  }
1506  return child->touchLeaf(xyz);
1507 }
1508 
1509 
1510 template<typename ChildT, Index Log2Dim>
1511 template<typename AccessorT>
1512 inline typename ChildT::LeafNodeType*
1513 InternalNode<ChildT, Log2Dim>::touchLeafAndCache(const Coord& xyz, AccessorT& acc)
1514 {
1515  const Index n = this->coordToOffset(xyz);
1516  if (mChildMask.isOff(n)) {
1517  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), mValueMask.isOn(n)));
1518  }
1519  acc.insert(xyz, mNodes[n].getChild());
1520  return mNodes[n].getChild()->touchLeafAndCache(xyz, acc);
1521 }
1522 
1523 
1524 ////////////////////////////////////////
1525 
1526 
1527 template<typename ChildT, Index Log2Dim>
1528 inline bool
1530  const ValueType& tolerance) const
1531 {
1532  if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1533 
1534  firstValue = mNodes[0].getValue();
1535  for (Index i = 1; i < NUM_VALUES; ++i) {
1536  if (!math::isApproxEqual(mNodes[i].getValue(), firstValue, tolerance)) {
1537  return false; // early termination
1538  }
1539  }
1540  return true;
1541 }
1542 
1543 
1544 ////////////////////////////////////////
1545 
1546 
1547 template<typename ChildT, Index Log2Dim>
1548 inline bool
1550  ValueType& maxValue,
1551  bool& state,
1552  const ValueType& tolerance) const
1553 {
1554 
1555  if (!mChildMask.isOff() || !mValueMask.isConstant(state)) return false;// early termination
1556  minValue = maxValue = mNodes[0].getValue();
1557  for (Index i = 1; i < NUM_VALUES; ++i) {
1558  const ValueType& v = mNodes[i].getValue();
1559  if (v < minValue) {
1560  if ((maxValue - v) > tolerance) return false;// early termination
1561  minValue = v;
1562  } else if (v > maxValue) {
1563  if ((v - minValue) > tolerance) return false;// early termination
1564  maxValue = v;
1565  }
1566  }
1567  return true;
1568 }
1569 
1570 
1571 ////////////////////////////////////////
1572 
1573 
1574 template<typename ChildT, Index Log2Dim>
1575 inline bool
1577 {
1579  const bool anyActiveTiles = !mValueMask.isOff();
1580  if (LEVEL==1 || anyActiveTiles) return anyActiveTiles;
1581  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
1582  if (iter->hasActiveTiles()) return true;
1583  }
1584  return false;
1586 }
1587 
1588 
1589 template<typename ChildT, Index Log2Dim>
1590 inline bool
1592 {
1593  const Index n = this->coordToOffset(xyz);
1594  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1595  return mNodes[n].getChild()->isValueOn(xyz);
1596 }
1597 
1598 template<typename ChildT, Index Log2Dim>
1599 template<typename AccessorT>
1600 inline bool
1601 InternalNode<ChildT, Log2Dim>::isValueOnAndCache(const Coord& xyz, AccessorT& acc) const
1602 {
1603  const Index n = this->coordToOffset(xyz);
1604  if (this->isChildMaskOff(n)) return this->isValueMaskOn(n);
1605  acc.insert(xyz, mNodes[n].getChild());
1606  return mNodes[n].getChild()->isValueOnAndCache(xyz, acc);
1607 }
1608 
1609 
1610 template<typename ChildT, Index Log2Dim>
1611 inline const typename ChildT::ValueType&
1613 {
1614  const Index n = this->coordToOffset(xyz);
1615  return this->isChildMaskOff(n) ? mNodes[n].getValue()
1616  : mNodes[n].getChild()->getValue(xyz);
1617 }
1618 
1619 template<typename ChildT, Index Log2Dim>
1620 template<typename AccessorT>
1621 inline const typename ChildT::ValueType&
1622 InternalNode<ChildT, Log2Dim>::getValueAndCache(const Coord& xyz, AccessorT& acc) const
1623 {
1624  const Index n = this->coordToOffset(xyz);
1625  if (this->isChildMaskOn(n)) {
1626  acc.insert(xyz, mNodes[n].getChild());
1627  return mNodes[n].getChild()->getValueAndCache(xyz, acc);
1628  }
1629  return mNodes[n].getValue();
1630 }
1631 
1632 
1633 template<typename ChildT, Index Log2Dim>
1634 inline Index
1636 {
1637  const Index n = this->coordToOffset(xyz);
1638  return this->isChildMaskOff(n) ? LEVEL : mNodes[n].getChild()->getValueLevel(xyz);
1639 }
1640 
1641 template<typename ChildT, Index Log2Dim>
1642 template<typename AccessorT>
1643 inline Index
1644 InternalNode<ChildT, Log2Dim>::getValueLevelAndCache(const Coord& xyz, AccessorT& acc) const
1645 {
1646  const Index n = this->coordToOffset(xyz);
1647  if (this->isChildMaskOn(n)) {
1648  acc.insert(xyz, mNodes[n].getChild());
1649  return mNodes[n].getChild()->getValueLevelAndCache(xyz, acc);
1650  }
1651  return LEVEL;
1652 }
1653 
1654 
1655 template<typename ChildT, Index Log2Dim>
1656 inline bool
1658 {
1659  const Index n = this->coordToOffset(xyz);
1660  if (this->isChildMaskOff(n)) {
1661  value = mNodes[n].getValue();
1662  return this->isValueMaskOn(n);
1663  }
1664  return mNodes[n].getChild()->probeValue(xyz, value);
1665 }
1666 
1667 template<typename ChildT, Index Log2Dim>
1668 template<typename AccessorT>
1669 inline bool
1671  ValueType& value, AccessorT& acc) const
1672 {
1673  const Index n = this->coordToOffset(xyz);
1674  if (this->isChildMaskOn(n)) {
1675  acc.insert(xyz, mNodes[n].getChild());
1676  return mNodes[n].getChild()->probeValueAndCache(xyz, value, acc);
1677  }
1678  value = mNodes[n].getValue();
1679  return this->isValueMaskOn(n);
1680 }
1681 
1682 
1683 template<typename ChildT, Index Log2Dim>
1684 inline void
1686 {
1687  const Index n = this->coordToOffset(xyz);
1688  bool hasChild = this->isChildMaskOn(n);
1689  if (!hasChild && this->isValueMaskOn(n)) {
1690  // If the voxel belongs to a constant tile that is active,
1691  // a child subtree must be constructed.
1692  hasChild = true;
1693  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/true));
1694  }
1695  if (hasChild) mNodes[n].getChild()->setValueOff(xyz);
1696 }
1697 
1698 
1699 template<typename ChildT, Index Log2Dim>
1700 inline void
1702 {
1703  const Index n = this->coordToOffset(xyz);
1704  bool hasChild = this->isChildMaskOn(n);
1705  if (!hasChild && !this->isValueMaskOn(n)) {
1706  // If the voxel belongs to a constant tile that is inactive,
1707  // a child subtree must be constructed.
1708  hasChild = true;
1709  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), /*active=*/false));
1710  }
1711  if (hasChild) mNodes[n].getChild()->setValueOn(xyz);
1712 }
1713 
1714 
1715 template<typename ChildT, Index Log2Dim>
1716 inline void
1718 {
1719  const Index n = InternalNode::coordToOffset(xyz);
1720  bool hasChild = this->isChildMaskOn(n);
1721  if (!hasChild) {
1722  const bool active = this->isValueMaskOn(n);
1723  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1724  // If the voxel belongs to a tile that is either active or that
1725  // has a constant value that is different from the one provided,
1726  // a child subtree must be constructed.
1727  hasChild = true;
1728  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1729  }
1730  }
1731  if (hasChild) mNodes[n].getChild()->setValueOff(xyz, value);
1732 }
1733 
1734 template<typename ChildT, Index Log2Dim>
1735 template<typename AccessorT>
1736 inline void
1738  const ValueType& value, AccessorT& acc)
1739 {
1740  const Index n = InternalNode::coordToOffset(xyz);
1741  bool hasChild = this->isChildMaskOn(n);
1742  if (!hasChild) {
1743  const bool active = this->isValueMaskOn(n);
1744  if (active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1745  // If the voxel belongs to a tile that is either active or that
1746  // has a constant value that is different from the one provided,
1747  // a child subtree must be constructed.
1748  hasChild = true;
1749  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1750  }
1751  }
1752  if (hasChild) {
1753  ChildT* child = mNodes[n].getChild();
1754  acc.insert(xyz, child);
1755  child->setValueOffAndCache(xyz, value, acc);
1756  }
1757 }
1758 
1759 
1760 template<typename ChildT, Index Log2Dim>
1761 inline void
1763 {
1764  const Index n = this->coordToOffset(xyz);
1765  bool hasChild = this->isChildMaskOn(n);
1766  if (!hasChild) {
1767  const bool active = this->isValueMaskOn(n); // tile's active state
1768  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1769  // If the voxel belongs to a tile that is either inactive or that
1770  // has a constant value that is different from the one provided,
1771  // a child subtree must be constructed.
1772  hasChild = true;
1773  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1774  }
1775  }
1776  if (hasChild) mNodes[n].getChild()->setValueOn(xyz, value);
1777 }
1778 
1779 template<typename ChildT, Index Log2Dim>
1780 template<typename AccessorT>
1781 inline void
1783  const ValueType& value, AccessorT& acc)
1784 {
1785  const Index n = this->coordToOffset(xyz);
1786  bool hasChild = this->isChildMaskOn(n);
1787  if (!hasChild) {
1788  const bool active = this->isValueMaskOn(n);
1789  if (!active || !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1790  // If the voxel belongs to a tile that is either inactive or that
1791  // has a constant value that is different from the one provided,
1792  // a child subtree must be constructed.
1793  hasChild = true;
1794  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1795  }
1796  }
1797  if (hasChild) {
1798  acc.insert(xyz, mNodes[n].getChild());
1799  mNodes[n].getChild()->setValueAndCache(xyz, value, acc);
1800  }
1801 }
1802 
1803 
1804 template<typename ChildT, Index Log2Dim>
1805 inline void
1807 {
1808  const Index n = this->coordToOffset(xyz);
1809  bool hasChild = this->isChildMaskOn(n);
1810  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1811  // If the voxel has a tile value that is different from the one provided,
1812  // a child subtree must be constructed.
1813  const bool active = this->isValueMaskOn(n);
1814  hasChild = true;
1815  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1816  }
1817  if (hasChild) mNodes[n].getChild()->setValueOnly(xyz, value);
1818 }
1819 
1820 template<typename ChildT, Index Log2Dim>
1821 template<typename AccessorT>
1822 inline void
1824  const ValueType& value, AccessorT& acc)
1825 {
1826  const Index n = this->coordToOffset(xyz);
1827  bool hasChild = this->isChildMaskOn(n);
1828  if (!hasChild && !math::isExactlyEqual(mNodes[n].getValue(), value)) {
1829  // If the voxel has a tile value that is different from the one provided,
1830  // a child subtree must be constructed.
1831  const bool active = this->isValueMaskOn(n);
1832  hasChild = true;
1833  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1834  }
1835  if (hasChild) {
1836  acc.insert(xyz, mNodes[n].getChild());
1837  mNodes[n].getChild()->setValueOnlyAndCache(xyz, value, acc);
1838  }
1839 }
1840 
1841 
1842 template<typename ChildT, Index Log2Dim>
1843 inline void
1845 {
1846  const Index n = this->coordToOffset(xyz);
1847  bool hasChild = this->isChildMaskOn(n);
1848  if (!hasChild) {
1849  if (on != this->isValueMaskOn(n)) {
1850  // If the voxel belongs to a tile with the wrong active state,
1851  // then a child subtree must be constructed.
1852  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1853  hasChild = true;
1854  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1855  }
1856  }
1857  if (hasChild) mNodes[n].getChild()->setActiveState(xyz, on);
1858 }
1859 
1860 template<typename ChildT, Index Log2Dim>
1861 template<typename AccessorT>
1862 inline void
1863 InternalNode<ChildT, Log2Dim>::setActiveStateAndCache(const Coord& xyz, bool on, AccessorT& acc)
1864 {
1865  const Index n = this->coordToOffset(xyz);
1866  bool hasChild = this->isChildMaskOn(n);
1867  if (!hasChild) {
1868  if (on != this->isValueMaskOn(n)) {
1869  // If the voxel belongs to a tile with the wrong active state,
1870  // then a child subtree must be constructed.
1871  // 'on' is the voxel's new state, therefore '!on' is the tile's current state
1872  hasChild = true;
1873  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), !on));
1874  }
1875  }
1876  if (hasChild) {
1877  ChildT* child = mNodes[n].getChild();
1878  acc.insert(xyz, child);
1879  child->setActiveStateAndCache(xyz, on, acc);
1880  }
1881 }
1882 
1883 
1884 template<typename ChildT, Index Log2Dim>
1885 inline void
1887 {
1888  mValueMask = !mChildMask;
1889  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
1890  mNodes[iter.pos()].getChild()->setValuesOn();
1891  }
1892 }
1893 
1894 
1895 template<typename ChildT, Index Log2Dim>
1896 template<typename ModifyOp>
1897 inline void
1898 InternalNode<ChildT, Log2Dim>::modifyValue(const Coord& xyz, const ModifyOp& op)
1899 {
1900  const Index n = InternalNode::coordToOffset(xyz);
1901  bool hasChild = this->isChildMaskOn(n);
1902  if (!hasChild) {
1903  // Need to create a child if the tile is inactive,
1904  // in order to activate voxel (x, y, z).
1905  const bool active = this->isValueMaskOn(n);
1906  bool createChild = !active;
1907  if (!createChild) {
1908  // Need to create a child if applying the functor
1909  // to the tile value produces a different value.
1910  const ValueType& tileVal = mNodes[n].getValue();
1911  ValueType modifiedVal = tileVal;
1912  op(modifiedVal);
1913  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1914  }
1915  if (createChild) {
1916  hasChild = true;
1917  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1918  }
1919  }
1920  if (hasChild) mNodes[n].getChild()->modifyValue(xyz, op);
1921 }
1922 
1923 template<typename ChildT, Index Log2Dim>
1924 template<typename ModifyOp, typename AccessorT>
1925 inline void
1926 InternalNode<ChildT, Log2Dim>::modifyValueAndCache(const Coord& xyz, const ModifyOp& op,
1927  AccessorT& acc)
1928 {
1929  const Index n = InternalNode::coordToOffset(xyz);
1930  bool hasChild = this->isChildMaskOn(n);
1931  if (!hasChild) {
1932  // Need to create a child if the tile is inactive,
1933  // in order to activate voxel (x, y, z).
1934  const bool active = this->isValueMaskOn(n);
1935  bool createChild = !active;
1936  if (!createChild) {
1937  // Need to create a child if applying the functor
1938  // to the tile value produces a different value.
1939  const ValueType& tileVal = mNodes[n].getValue();
1940  ValueType modifiedVal = tileVal;
1941  op(modifiedVal);
1942  createChild = !math::isExactlyEqual(tileVal, modifiedVal);
1943  }
1944  if (createChild) {
1945  hasChild = true;
1946  this->setChildNode(n, new ChildNodeType(xyz, mNodes[n].getValue(), active));
1947  }
1948  }
1949  if (hasChild) {
1950  ChildNodeType* child = mNodes[n].getChild();
1951  acc.insert(xyz, child);
1952  child->modifyValueAndCache(xyz, op, acc);
1953  }
1954 }
1955 
1956 
1957 template<typename ChildT, Index Log2Dim>
1958 template<typename ModifyOp>
1959 inline void
1961 {
1962  const Index n = InternalNode::coordToOffset(xyz);
1963  bool hasChild = this->isChildMaskOn(n);
1964  if (!hasChild) {
1965  const bool tileState = this->isValueMaskOn(n);
1966  const ValueType& tileVal = mNodes[n].getValue();
1967  bool modifiedState = !tileState;
1968  ValueType modifiedVal = tileVal;
1969  op(modifiedVal, modifiedState);
1970  // Need to create a child if applying the functor to the tile
1971  // produces a different value or active state.
1972  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1973  hasChild = true;
1974  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1975  }
1976  }
1977  if (hasChild) mNodes[n].getChild()->modifyValueAndActiveState(xyz, op);
1978 }
1979 
1980 template<typename ChildT, Index Log2Dim>
1981 template<typename ModifyOp, typename AccessorT>
1982 inline void
1984  const Coord& xyz, const ModifyOp& op, AccessorT& acc)
1985 {
1986  const Index n = InternalNode::coordToOffset(xyz);
1987  bool hasChild = this->isChildMaskOn(n);
1988  if (!hasChild) {
1989  const bool tileState = this->isValueMaskOn(n);
1990  const ValueType& tileVal = mNodes[n].getValue();
1991  bool modifiedState = !tileState;
1992  ValueType modifiedVal = tileVal;
1993  op(modifiedVal, modifiedState);
1994  // Need to create a child if applying the functor to the tile
1995  // produces a different value or active state.
1996  if (modifiedState != tileState || !math::isExactlyEqual(modifiedVal, tileVal)) {
1997  hasChild = true;
1998  this->setChildNode(n, new ChildNodeType(xyz, tileVal, tileState));
1999  }
2000  }
2001  if (hasChild) {
2002  ChildNodeType* child = mNodes[n].getChild();
2003  acc.insert(xyz, child);
2004  child->modifyValueAndActiveStateAndCache(xyz, op, acc);
2005  }
2006 }
2007 
2008 
2009 ////////////////////////////////////////
2010 
2011 
2012 template<typename ChildT, Index Log2Dim>
2013 inline void
2014 InternalNode<ChildT, Log2Dim>::clip(const CoordBBox& clipBBox, const ValueType& background)
2015 {
2016  CoordBBox nodeBBox = this->getNodeBoundingBox();
2017  if (!clipBBox.hasOverlap(nodeBBox)) {
2018  // This node lies completely outside the clipping region. Fill it with background tiles.
2019  this->fill(nodeBBox, background, /*active=*/false);
2020  } else if (clipBBox.isInside(nodeBBox)) {
2021  // This node lies completely inside the clipping region. Leave it intact.
2022  return;
2023  }
2024 
2025  // This node isn't completely contained inside the clipping region.
2026  // Clip tiles and children, and replace any that lie outside the region
2027  // with background tiles.
2028 
2029  for (Index pos = 0; pos < NUM_VALUES; ++pos) {
2030  const Coord xyz = this->offsetToGlobalCoord(pos); // tile or child origin
2031  CoordBBox tileBBox(xyz, xyz.offsetBy(ChildT::DIM - 1)); // tile or child bounds
2032  if (!clipBBox.hasOverlap(tileBBox)) {
2033  // This table entry lies completely outside the clipping region.
2034  // Replace it with a background tile.
2035  this->makeChildNodeEmpty(pos, background);
2036  mValueMask.setOff(pos);
2037  } else if (!clipBBox.isInside(tileBBox)) {
2038  // This table entry does not lie completely inside the clipping region
2039  // and must be clipped.
2040  if (this->isChildMaskOn(pos)) {
2041  mNodes[pos].getChild()->clip(clipBBox, background);
2042  } else {
2043  // Replace this tile with a background tile, then fill the clip region
2044  // with the tile's original value. (This might create a child branch.)
2045  tileBBox.intersect(clipBBox);
2046  const ValueType val = mNodes[pos].getValue();
2047  const bool on = this->isValueMaskOn(pos);
2048  mNodes[pos].setValue(background);
2049  mValueMask.setOff(pos);
2050  this->fill(tileBBox, val, on);
2051  }
2052  } else {
2053  // This table entry lies completely inside the clipping region. Leave it intact.
2054  }
2055  }
2056 }
2057 
2058 
2059 ////////////////////////////////////////
2060 
2061 
2062 template<typename ChildT, Index Log2Dim>
2063 inline void
2064 InternalNode<ChildT, Log2Dim>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
2065 {
2066  auto clippedBBox = this->getNodeBoundingBox();
2067  clippedBBox.intersect(bbox);
2068  if (!clippedBBox) return;
2069 
2070  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2071  // (The first and last chunks along each axis might be smaller than a tile.)
2072  Coord xyz, tileMin, tileMax;
2073  for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2074  xyz.setX(x);
2075  for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2076  xyz.setY(y);
2077  for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2078  xyz.setZ(z);
2079 
2080  // Get the bounds of the tile that contains voxel (x, y, z).
2081  const Index n = this->coordToOffset(xyz);
2082  tileMin = this->offsetToGlobalCoord(n);
2083  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2084 
2085  if (xyz != tileMin || Coord::lessThan(clippedBBox.max(), tileMax)) {
2086  // If the box defined by (xyz, clippedBBox.max()) doesn't completely enclose
2087  // the tile to which xyz belongs, create a child node (or retrieve
2088  // the existing one).
2089  ChildT* child = nullptr;
2090  if (this->isChildMaskOff(n)) {
2091  // Replace the tile with a newly-created child that is initialized
2092  // with the tile's value and active state.
2093  child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2094  this->setChildNode(n, child);
2095  } else {
2096  child = mNodes[n].getChild();
2097  }
2098 
2099  // Forward the fill request to the child.
2100  if (child) {
2101  const Coord tmp = Coord::minComponent(clippedBBox.max(), tileMax);
2102  child->fill(CoordBBox(xyz, tmp), value, active);
2103  }
2104 
2105  } else {
2106  // If the box given by (xyz, clippedBBox.max()) completely encloses
2107  // the tile to which xyz belongs, create the tile (if it
2108  // doesn't already exist) and give it the fill value.
2109  this->makeChildNodeEmpty(n, value);
2110  mValueMask.set(n, active);
2111  }
2112  }
2113  }
2114  }
2115 }
2116 
2117 
2118 template<typename ChildT, Index Log2Dim>
2119 inline void
2120 InternalNode<ChildT, Log2Dim>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
2121 {
2122  auto clippedBBox = this->getNodeBoundingBox();
2123  clippedBBox.intersect(bbox);
2124  if (!clippedBBox) return;
2125 
2126  // Iterate over the fill region in axis-aligned, tile-sized chunks.
2127  // (The first and last chunks along each axis might be smaller than a tile.)
2128  Coord xyz, tileMin, tileMax;
2129  for (int x = clippedBBox.min().x(); x <= clippedBBox.max().x(); x = tileMax.x() + 1) {
2130  xyz.setX(x);
2131  for (int y = clippedBBox.min().y(); y <= clippedBBox.max().y(); y = tileMax.y() + 1) {
2132  xyz.setY(y);
2133  for (int z = clippedBBox.min().z(); z <= clippedBBox.max().z(); z = tileMax.z() + 1) {
2134  xyz.setZ(z);
2135 
2136  // Get the table index of the tile that contains voxel (x, y, z).
2137  const auto n = this->coordToOffset(xyz);
2138 
2139  // Retrieve the child node at index n, or replace the tile at index n with a child.
2140  ChildT* child = nullptr;
2141  if (this->isChildMaskOn(n)) {
2142  child = mNodes[n].getChild();
2143  } else {
2144  // Replace the tile with a newly-created child that is filled
2145  // with the tile's value and active state.
2146  child = new ChildT{xyz, mNodes[n].getValue(), this->isValueMaskOn(n)};
2147  this->setChildNode(n, child);
2148  }
2149 
2150  // Get the bounds of the tile that contains voxel (x, y, z).
2151  tileMin = this->offsetToGlobalCoord(n);
2152  tileMax = tileMin.offsetBy(ChildT::DIM - 1);
2153 
2154  // Forward the fill request to the child.
2155  child->denseFill(CoordBBox{xyz, clippedBBox.max()}, value, active);
2156  }
2157  }
2158  }
2159 }
2160 
2161 
2162 ////////////////////////////////////////
2163 
2164 
2165 template<typename ChildT, Index Log2Dim>
2166 template<typename DenseT>
2167 inline void
2168 InternalNode<ChildT, Log2Dim>::copyToDense(const CoordBBox& bbox, DenseT& dense) const
2169 {
2170  using DenseValueType = typename DenseT::ValueType;
2171 
2172  const size_t xStride = dense.xStride(), yStride = dense.yStride(), zStride = dense.zStride();
2173  const Coord& min = dense.bbox().min();
2174  for (Coord xyz = bbox.min(), max; xyz[0] <= bbox.max()[0]; xyz[0] = max[0] + 1) {
2175  for (xyz[1] = bbox.min()[1]; xyz[1] <= bbox.max()[1]; xyz[1] = max[1] + 1) {
2176  for (xyz[2] = bbox.min()[2]; xyz[2] <= bbox.max()[2]; xyz[2] = max[2] + 1) {
2177  const Index n = this->coordToOffset(xyz);
2178  // Get max coordinates of the child node that contains voxel xyz.
2179  max = this->offsetToGlobalCoord(n).offsetBy(ChildT::DIM-1);
2180 
2181  // Get the bbox of the interection of bbox and the child node
2182  CoordBBox sub(xyz, Coord::minComponent(bbox.max(), max));
2183 
2184  if (this->isChildMaskOn(n)) {//is a child
2185  mNodes[n].getChild()->copyToDense(sub, dense);
2186  } else {//a tile value
2187  const ValueType value = mNodes[n].getValue();
2188  sub.translate(-min);
2189  DenseValueType* a0 = dense.data() + zStride*sub.min()[2];
2190  for (Int32 x=sub.min()[0], ex=sub.max()[0]+1; x<ex; ++x) {
2191  DenseValueType* a1 = a0 + x*xStride;
2192  for (Int32 y=sub.min()[1], ey=sub.max()[1]+1; y<ey; ++y) {
2193  DenseValueType* a2 = a1 + y*yStride;
2194  for (Int32 z = sub.min()[2], ez = sub.max()[2]+1;
2195  z < ez; ++z, a2 += zStride)
2196  {
2197  *a2 = DenseValueType(value);
2198  }
2199  }
2200  }
2201  }
2202  }
2203  }
2204  }
2205 }
2206 
2207 
2208 ////////////////////////////////////////
2209 
2210 
2211 template<typename ChildT, Index Log2Dim>
2212 inline void
2213 InternalNode<ChildT, Log2Dim>::writeTopology(std::ostream& os, bool toHalf) const
2214 {
2215  mChildMask.save(os);
2216  mValueMask.save(os);
2217 
2218  {
2219  // Copy all of this node's values into an array.
2220  std::unique_ptr<ValueType[]> valuePtr(new ValueType[NUM_VALUES]);
2221  ValueType* values = valuePtr.get();
2222  const ValueType zero = zeroVal<ValueType>();
2223  for (Index i = 0; i < NUM_VALUES; ++i) {
2224  values[i] = (mChildMask.isOff(i) ? mNodes[i].getValue() : zero);
2225  }
2226  // Compress (optionally) and write out the contents of the array.
2227  io::writeCompressedValues(os, values, NUM_VALUES, mValueMask, mChildMask, toHalf);
2228  }
2229  // Write out the child nodes in order.
2230  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
2231  iter->writeTopology(os, toHalf);
2232  }
2233 }
2234 
2235 
2236 template<typename ChildT, Index Log2Dim>
2237 inline void
2238 InternalNode<ChildT, Log2Dim>::readTopology(std::istream& is, bool fromHalf)
2239 {
2240  const ValueType background = (!io::getGridBackgroundValuePtr(is) ? zeroVal<ValueType>()
2241  : *static_cast<const ValueType*>(io::getGridBackgroundValuePtr(is)));
2242 
2243  mChildMask.load(is);
2244  mValueMask.load(is);
2245 
2247  for (Index i = 0; i < NUM_VALUES; ++i) {
2248  if (this->isChildMaskOn(i)) {
2249  ChildNodeType* child =
2250  new ChildNodeType(PartialCreate(), offsetToGlobalCoord(i), background);
2251  mNodes[i].setChild(child);
2252  child->readTopology(is);
2253  } else {
2254  ValueType value;
2255  is.read(reinterpret_cast<char*>(&value), sizeof(ValueType));
2256  mNodes[i].setValue(value);
2257  }
2258  }
2259  } else {
2260  const bool oldVersion =
2262  const Index numValues = (oldVersion ? mChildMask.countOff() : NUM_VALUES);
2263  {
2264  // Read in (and uncompress, if necessary) all of this node's values
2265  // into a contiguous array.
2266  std::unique_ptr<ValueType[]> valuePtr(new ValueType[numValues]);
2267  ValueType* values = valuePtr.get();
2268  io::readCompressedValues(is, values, numValues, mValueMask, fromHalf);
2269 
2270  // Copy values from the array into this node's table.
2271  if (oldVersion) {
2272  Index n = 0;
2273  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2274  mNodes[iter.pos()].setValue(values[n++]);
2275  }
2276  assert(n == numValues);
2277  } else {
2278  for (ValueAllIter iter = this->beginValueAll(); iter; ++iter) {
2279  mNodes[iter.pos()].setValue(values[iter.pos()]);
2280  }
2281  }
2282  }
2283  // Read in all child nodes and insert them into the table at their proper locations.
2284  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
2285  ChildNodeType* child = new ChildNodeType(PartialCreate(), iter.getCoord(), background);
2286  mNodes[iter.pos()].setChild(child);
2287  child->readTopology(is, fromHalf);
2288  }
2289  }
2290 }
2291 
2292 
2293 ////////////////////////////////////////
2294 
2295 
2296 template<typename ChildT, Index Log2Dim>
2297 inline const typename ChildT::ValueType&
2299 {
2300  return (this->isChildMaskOn(0) ? mNodes[0].getChild()->getFirstValue() : mNodes[0].getValue());
2301 }
2302 
2303 
2304 template<typename ChildT, Index Log2Dim>
2305 inline const typename ChildT::ValueType&
2307 {
2308  const Index n = NUM_VALUES - 1;
2309  return (this->isChildMaskOn(n) ? mNodes[n].getChild()->getLastValue() : mNodes[n].getValue());
2310 }
2311 
2312 
2313 ////////////////////////////////////////
2314 
2315 
2316 template<typename ChildT, Index Log2Dim>
2317 inline void
2319 {
2320  for (Index i = 0; i < NUM_VALUES; ++i) {
2321  if (this->isChildMaskOn(i)) {
2322  mNodes[i].getChild()->negate();
2323  } else {
2324  mNodes[i].setValue(math::negative(mNodes[i].getValue()));
2325  }
2326  }
2327 
2328 }
2329 
2330 
2331 ////////////////////////////////////////
2332 
2333 
2334 template<typename ChildT, Index Log2Dim>
2336 {
2337  VoxelizeActiveTiles(InternalNode &node) : mNode(&node) {
2338  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2339  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2340 
2341  node.mChildMask |= node.mValueMask;
2342  node.mValueMask.setOff();
2343  }
2344  void operator()(const tbb::blocked_range<Index> &r) const
2345  {
2346  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2347  if (mNode->mChildMask.isOn(i)) {// Loop over node's child nodes
2348  mNode->mNodes[i].getChild()->voxelizeActiveTiles(true);
2349  } else if (mNode->mValueMask.isOn(i)) {// Loop over node's active tiles
2350  const Coord &ijk = mNode->offsetToGlobalCoord(i);
2351  ChildNodeType *child = new ChildNodeType(ijk, mNode->mNodes[i].getValue(), true);
2352  child->voxelizeActiveTiles(true);
2353  mNode->mNodes[i].setChild(child);
2354  }
2355  }
2356  }
2358 };// VoxelizeActiveTiles
2359 
2360 template<typename ChildT, Index Log2Dim>
2361 inline void
2363 {
2364  if (threaded) {
2365  VoxelizeActiveTiles tmp(*this);
2366  } else {
2367  for (ValueOnIter iter = this->beginValueOn(); iter; ++iter) {
2368  this->setChildNode(iter.pos(),
2369  new ChildNodeType(iter.getCoord(), iter.getValue(), true));
2370  }
2371  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter)
2372  iter->voxelizeActiveTiles(false);
2373  }
2374 }
2375 
2376 
2377 ////////////////////////////////////////
2378 
2379 
2380 template<typename ChildT, Index Log2Dim>
2381 template<MergePolicy Policy>
2382 inline void
2384  const ValueType& background, const ValueType& otherBackground)
2385 {
2387 
2388  switch (Policy) {
2389 
2390  case MERGE_ACTIVE_STATES:
2391  default:
2392  {
2393  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2394  const Index n = iter.pos();
2395  if (mChildMask.isOn(n)) {
2396  // Merge this node's child with the other node's child.
2397  mNodes[n].getChild()->template merge<MERGE_ACTIVE_STATES>(*iter,
2398  background, otherBackground);
2399  } else if (mValueMask.isOff(n)) {
2400  // Replace this node's inactive tile with the other node's child
2401  // and replace the other node's child with a tile of undefined value
2402  // (which is okay since the other tree is assumed to be cannibalized
2403  // in the process of merging).
2404  ChildNodeType* child = other.mNodes[n].getChild();
2405  other.mChildMask.setOff(n);
2406  child->resetBackground(otherBackground, background);
2407  this->setChildNode(n, child);
2408  }
2409  }
2410 
2411  // Copy active tile values.
2412  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2413  const Index n = iter.pos();
2414  if (mValueMask.isOff(n)) {
2415  // Replace this node's child or inactive tile with the other node's active tile.
2416  this->makeChildNodeEmpty(n, iter.getValue());
2417  mValueMask.setOn(n);
2418  }
2419  }
2420  break;
2421  }
2422 
2423  case MERGE_NODES:
2424  {
2425  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2426  const Index n = iter.pos();
2427  if (mChildMask.isOn(n)) {
2428  // Merge this node's child with the other node's child.
2429  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2430  } else {
2431  // Replace this node's tile (regardless of its active state) with
2432  // the other node's child and replace the other node's child with
2433  // a tile of undefined value (which is okay since the other tree
2434  // is assumed to be cannibalized in the process of merging).
2435  ChildNodeType* child = other.mNodes[n].getChild();
2436  other.mChildMask.setOff(n);
2437  child->resetBackground(otherBackground, background);
2438  this->setChildNode(n, child);
2439  }
2440  }
2441  break;
2442  }
2443 
2445  {
2446  // Transfer children from the other tree to this tree.
2447  for (ChildOnIter iter = other.beginChildOn(); iter; ++iter) {
2448  const Index n = iter.pos();
2449  if (mChildMask.isOn(n)) {
2450  // Merge this node's child with the other node's child.
2451  mNodes[n].getChild()->template merge<Policy>(*iter, background, otherBackground);
2452  } else {
2453  // Replace this node's tile with the other node's child, leaving the other
2454  // node with an inactive tile of undefined value (which is okay since
2455  // the other tree is assumed to be cannibalized in the process of merging).
2456  ChildNodeType* child = other.mNodes[n].getChild();
2457  other.mChildMask.setOff(n);
2458  child->resetBackground(otherBackground, background);
2459  if (mValueMask.isOn(n)) {
2460  // Merge the child with this node's active tile.
2461  child->template merge<Policy>(mNodes[n].getValue(), /*on=*/true);
2462  mValueMask.setOff(n);
2463  }
2464  mChildMask.setOn(n);
2465  mNodes[n].setChild(child);
2466  }
2467  }
2468 
2469  // Merge active tiles into this tree.
2470  for (ValueOnCIter iter = other.cbeginValueOn(); iter; ++iter) {
2471  const Index n = iter.pos();
2472  if (mChildMask.isOn(n)) {
2473  // Merge the other node's active tile into this node's child.
2474  mNodes[n].getChild()->template merge<Policy>(iter.getValue(), /*on=*/true);
2475  } else if (mValueMask.isOff(n)) {
2476  // Replace this node's inactive tile with the other node's active tile.
2477  mNodes[n].setValue(iter.getValue());
2478  mValueMask.setOn(n);
2479  }
2480  }
2481  break;
2482  }
2483 
2484  }
2486 }
2487 
2488 
2489 template<typename ChildT, Index Log2Dim>
2490 template<MergePolicy Policy>
2491 inline void
2492 InternalNode<ChildT, Log2Dim>::merge(const ValueType& tileValue, bool tileActive)
2493 {
2495 
2496  if (Policy != MERGE_ACTIVE_STATES_AND_NODES) return;
2497 
2498  // For MERGE_ACTIVE_STATES_AND_NODES, inactive tiles in the other tree are ignored.
2499  if (!tileActive) return;
2500 
2501  // Iterate over this node's children and inactive tiles.
2502  for (ValueOffIter iter = this->beginValueOff(); iter; ++iter) {
2503  const Index n = iter.pos();
2504  if (mChildMask.isOn(n)) {
2505  // Merge the other node's active tile into this node's child.
2506  mNodes[n].getChild()->template merge<Policy>(tileValue, /*on=*/true);
2507  } else {
2508  // Replace this node's inactive tile with the other node's active tile.
2509  iter.setValue(tileValue);
2510  mValueMask.setOn(n);
2511  }
2512  }
2514 }
2515 
2516 
2517 ////////////////////////////////////////
2518 
2519 
2520 template<typename ChildT, Index Log2Dim>
2521 template<typename OtherInternalNode>
2523 {
2524  using W = typename NodeMaskType::Word;
2525  struct A { inline void operator()(W &tV, const W& sV, const W& tC) const
2526  { tV = (tV | sV) & ~tC; }
2527  };
2528  TopologyUnion(const OtherInternalNode* source, InternalNode* target, const bool preserveTiles)
2529  : s(source), t(target), mPreserveTiles(preserveTiles) {
2530  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2531  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2532 
2533  // Bit processing is done in a single thread!
2534  if (!mPreserveTiles) t->mChildMask |= s->mChildMask;//serial but very fast bitwise post-process
2535  else t->mChildMask |= (s->mChildMask & !t->mValueMask);
2536 
2537  A op;
2538  t->mValueMask.foreach(s->mValueMask, t->mChildMask, op);
2539  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2540  }
2541  void operator()(const tbb::blocked_range<Index> &r) const {
2542  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2543  if (s->mChildMask.isOn(i)) {// Loop over other node's child nodes
2544  const typename OtherInternalNode::ChildNodeType& other = *(s->mNodes[i].getChild());
2545  if (t->mChildMask.isOn(i)) {//this has a child node
2546  t->mNodes[i].getChild()->topologyUnion(other, mPreserveTiles);
2547  } else {// this is a tile so replace it with a child branch with identical topology
2548  if (!mPreserveTiles || t->mValueMask.isOff(i)) { // force child topology
2549  ChildT* child = new ChildT(other, t->mNodes[i].getValue(), TopologyCopy());
2550  if (t->mValueMask.isOn(i)) child->setValuesOn();//activate all values
2551  t->mNodes[i].setChild(child);
2552  }
2553  }
2554  } else if (s->mValueMask.isOn(i) && t->mChildMask.isOn(i)) {
2555  t->mNodes[i].getChild()->setValuesOn();
2556  }
2557  }
2558  }
2559  const OtherInternalNode* s;
2561  const bool mPreserveTiles;
2562 };// TopologyUnion
2563 
2564 template<typename ChildT, Index Log2Dim>
2565 template<typename OtherChildT>
2566 inline void
2568 {
2569  TopologyUnion<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, preserveTiles);
2570 }
2571 
2572 template<typename ChildT, Index Log2Dim>
2573 template<typename OtherInternalNode>
2574 struct InternalNode<ChildT, Log2Dim>::TopologyIntersection
2575 {
2576  using W = typename NodeMaskType::Word;
2577  struct A { inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2578  { tC = (tC & (sC | sV)) | (tV & sC); }
2579  };
2580  TopologyIntersection(const OtherInternalNode* source, InternalNode* target,
2581  const ValueType& background) : s(source), t(target), b(background) {
2582  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2583  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2584 
2585  // Bit processing is done in a single thread!
2586  A op;
2587  t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op);
2588 
2589  t->mValueMask &= s->mValueMask;
2590  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2591  }
2592  void operator()(const tbb::blocked_range<Index> &r) const {
2593  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2594  if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2595  ChildT* child = t->mNodes[i].getChild();
2596  if (s->mChildMask.isOn(i)) {//other also has a child node
2597  child->topologyIntersection(*(s->mNodes[i].getChild()), b);
2598  } else if (s->mValueMask.isOff(i)) {//other is an inactive tile
2599  delete child;//convert child to an inactive tile
2600  t->mNodes[i].setValue(b);
2601  }
2602  } else if (t->mValueMask.isOn(i) && s->mChildMask.isOn(i)) {//active tile -> a branch
2603  t->mNodes[i].setChild(new ChildT(*(s->mNodes[i].getChild()),
2604  t->mNodes[i].getValue(), TopologyCopy()));
2605  }
2606  }
2607  }
2608  const OtherInternalNode* s;
2610  const ValueType& b;
2611 };// TopologyIntersection
2612 
2613 template<typename ChildT, Index Log2Dim>
2614 template<typename OtherChildT>
2615 inline void
2617  const InternalNode<OtherChildT, Log2Dim>& other, const ValueType& background)
2618 {
2619  TopologyIntersection<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, background);
2620 }
2621 
2622 template<typename ChildT, Index Log2Dim>
2623 template<typename OtherInternalNode>
2624 struct InternalNode<ChildT, Log2Dim>::TopologyDifference
2625 {
2626  using W = typename NodeMaskType::Word;
2627  struct A {inline void operator()(W &tC, const W& sC, const W& sV, const W& tV) const
2628  { tC = (tC & (sC | ~sV)) | (tV & sC); }
2629  };
2630  struct B {inline void operator()(W &tV, const W& sC, const W& sV, const W& tC) const
2631  { tV &= ~((tC & sV) | (sC | sV)); }
2632  };
2633  TopologyDifference(const OtherInternalNode* source, InternalNode* target,
2634  const ValueType& background) : s(source), t(target), b(background) {
2635  //(*this)(tbb::blocked_range<Index>(0, NUM_VALUES));//single thread for debugging
2636  tbb::parallel_for(tbb::blocked_range<Index>(0, NUM_VALUES), *this);
2637 
2638  // Bit processing is done in a single thread!
2639  const NodeMaskType oldChildMask(t->mChildMask);//important to avoid cross pollution
2640  A op1;
2641  t->mChildMask.foreach(s->mChildMask, s->mValueMask, t->mValueMask, op1);
2642 
2643  B op2;
2644  t->mValueMask.foreach(t->mChildMask, s->mValueMask, oldChildMask, op2);
2645  assert((t->mValueMask & t->mChildMask).isOff());//no overlapping active tiles or child nodes
2646  }
2647  void operator()(const tbb::blocked_range<Index> &r) const {
2648  for (Index i = r.begin(), end=r.end(); i!=end; ++i) {
2649  if (t->mChildMask.isOn(i)) {// Loop over this node's child nodes
2650  ChildT* child = t->mNodes[i].getChild();
2651  if (s->mChildMask.isOn(i)) {
2652  child->topologyDifference(*(s->mNodes[i].getChild()), b);
2653  } else if (s->mValueMask.isOn(i)) {
2654  delete child;//convert child to an inactive tile
2655  t->mNodes[i].setValue(b);
2656  }
2657  } else if (t->mValueMask.isOn(i)) {//this is an active tile
2658  if (s->mChildMask.isOn(i)) {
2659  const typename OtherInternalNode::ChildNodeType& other =
2660  *(s->mNodes[i].getChild());
2661  ChildT* child = new ChildT(other.origin(), t->mNodes[i].getValue(), true);
2662  child->topologyDifference(other, b);
2663  t->mNodes[i].setChild(child);//replace the active tile with a child branch
2664  }
2665  }
2666  }
2667  }
2668  const OtherInternalNode* s;
2670  const ValueType& b;
2671 };// TopologyDifference
2672 
2673 template<typename ChildT, Index Log2Dim>
2674 template<typename OtherChildT>
2675 inline void
2677  const ValueType& background)
2678 {
2679  TopologyDifference<InternalNode<OtherChildT, Log2Dim> > tmp(&other, this, background);
2680 }
2681 
2682 
2683 ////////////////////////////////////////
2684 
2685 
2686 template<typename ChildT, Index Log2Dim>
2687 template<typename CombineOp>
2688 inline void
2690 {
2691  const ValueType zero = zeroVal<ValueType>();
2692 
2694 
2695  for (Index i = 0; i < NUM_VALUES; ++i) {
2696  if (this->isChildMaskOff(i) && other.isChildMaskOff(i)) {
2697  // Both this node and the other node have constant values (tiles).
2698  // Combine the two values and store the result as this node's new tile value.
2699  op(args.setARef(mNodes[i].getValue())
2700  .setAIsActive(isValueMaskOn(i))
2701  .setBRef(other.mNodes[i].getValue())
2702  .setBIsActive(other.isValueMaskOn(i)));
2703  mNodes[i].setValue(args.result());
2704  mValueMask.set(i, args.resultIsActive());
2705  } else if (this->isChildMaskOn(i) && other.isChildMaskOff(i)) {
2706  // Combine this node's child with the other node's constant value.
2707  ChildNodeType* child = mNodes[i].getChild();
2708  assert(child);
2709  if (child) {
2710  child->combine(other.mNodes[i].getValue(), other.isValueMaskOn(i), op);
2711  }
2712  } else if (this->isChildMaskOff(i) && other.isChildMaskOn(i)) {
2713  // Combine this node's constant value with the other node's child.
2714  ChildNodeType* child = other.mNodes[i].getChild();
2715  assert(child);
2716  if (child) {
2717  // Combine this node's constant value with the other node's child,
2718  // but use a new functor in which the A and B values are swapped,
2719  // since the constant value is the A value, not the B value.
2721  child->combine(mNodes[i].getValue(), isValueMaskOn(i), swappedOp);
2722 
2723  // Steal the other node's child.
2724  other.mChildMask.setOff(i);
2725  other.mNodes[i].setValue(zero);
2726  this->setChildNode(i, child);
2727  }
2728 
2729  } else /*if (isChildMaskOn(i) && other.isChildMaskOn(i))*/ {
2730  // Combine this node's child with the other node's child.
2732  *child = mNodes[i].getChild(),
2733  *otherChild = other.mNodes[i].getChild();
2734  assert(child);
2735  assert(otherChild);
2736  if (child && otherChild) {
2737  child->combine(*otherChild, op);
2738  }
2739  }
2740  }
2741 }
2742 
2743 
2744 template<typename ChildT, Index Log2Dim>
2745 template<typename CombineOp>
2746 inline void
2747 InternalNode<ChildT, Log2Dim>::combine(const ValueType& value, bool valueIsActive, CombineOp& op)
2748 {
2750 
2751  for (Index i = 0; i < NUM_VALUES; ++i) {
2752  if (this->isChildMaskOff(i)) {
2753  // Combine this node's constant value with the given constant value.
2754  op(args.setARef(mNodes[i].getValue())
2755  .setAIsActive(isValueMaskOn(i))
2756  .setBRef(value)
2757  .setBIsActive(valueIsActive));
2758  mNodes[i].setValue(args.result());
2759  mValueMask.set(i, args.resultIsActive());
2760  } else /*if (isChildMaskOn(i))*/ {
2761  // Combine this node's child with the given constant value.
2762  ChildNodeType* child = mNodes[i].getChild();
2763  assert(child);
2764  if (child) child->combine(value, valueIsActive, op);
2765  }
2766  }
2767 }
2768 
2769 
2770 ////////////////////////////////////////
2771 
2772 
2773 template<typename ChildT, Index Log2Dim>
2774 template<typename CombineOp, typename OtherNodeType>
2775 inline void
2776 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other0, const OtherNodeType& other1,
2777  CombineOp& op)
2778 {
2780 
2781  for (Index i = 0; i < NUM_VALUES; ++i) {
2782  if (other0.isChildMaskOff(i) && other1.isChildMaskOff(i)) {
2783  op(args.setARef(other0.mNodes[i].getValue())
2784  .setAIsActive(other0.isValueMaskOn(i))
2785  .setBRef(other1.mNodes[i].getValue())
2786  .setBIsActive(other1.isValueMaskOn(i)));
2787  // Replace child i with a constant value.
2788  this->makeChildNodeEmpty(i, args.result());
2789  mValueMask.set(i, args.resultIsActive());
2790  } else {
2791  if (this->isChildMaskOff(i)) {
2792  // Add a new child with the same coordinates, etc. as the other node's child.
2793  const Coord& childOrigin = other0.isChildMaskOn(i)
2794  ? other0.mNodes[i].getChild()->origin()
2795  : other1.mNodes[i].getChild()->origin();
2796  this->setChildNode(i, new ChildNodeType(childOrigin, mNodes[i].getValue()));
2797  }
2798 
2799  if (other0.isChildMaskOff(i)) {
2800  // Combine node1's child with node0's constant value
2801  // and write the result into child i.
2802  mNodes[i].getChild()->combine2(other0.mNodes[i].getValue(),
2803  *other1.mNodes[i].getChild(), other0.isValueMaskOn(i), op);
2804  } else if (other1.isChildMaskOff(i)) {
2805  // Combine node0's child with node1's constant value
2806  // and write the result into child i.
2807  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2808  other1.mNodes[i].getValue(), other1.isValueMaskOn(i), op);
2809  } else {
2810  // Combine node0's child with node1's child
2811  // and write the result into child i.
2812  mNodes[i].getChild()->combine2(*other0.mNodes[i].getChild(),
2813  *other1.mNodes[i].getChild(), op);
2814  }
2815  }
2816  }
2817 }
2818 
2819 
2820 template<typename ChildT, Index Log2Dim>
2821 template<typename CombineOp, typename OtherNodeType>
2822 inline void
2823 InternalNode<ChildT, Log2Dim>::combine2(const ValueType& value, const OtherNodeType& other,
2824  bool valueIsActive, CombineOp& op)
2825 {
2827 
2828  for (Index i = 0; i < NUM_VALUES; ++i) {
2829  if (other.isChildMaskOff(i)) {
2830  op(args.setARef(value)
2831  .setAIsActive(valueIsActive)
2832  .setBRef(other.mNodes[i].getValue())
2833  .setBIsActive(other.isValueMaskOn(i)));
2834  // Replace child i with a constant value.
2835  this->makeChildNodeEmpty(i, args.result());
2836  mValueMask.set(i, args.resultIsActive());
2837  } else {
2838  typename OtherNodeType::ChildNodeType* otherChild = other.mNodes[i].getChild();
2839  assert(otherChild);
2840  if (this->isChildMaskOff(i)) {
2841  // Add a new child with the same coordinates, etc.
2842  // as the other node's child.
2843  this->setChildNode(i, new ChildNodeType(*otherChild));
2844  }
2845  // Combine the other node's child with a constant value
2846  // and write the result into child i.
2847  mNodes[i].getChild()->combine2(value, *otherChild, valueIsActive, op);
2848  }
2849  }
2850 }
2851 
2852 
2853 template<typename ChildT, Index Log2Dim>
2854 template<typename CombineOp, typename OtherValueType>
2855 inline void
2856 InternalNode<ChildT, Log2Dim>::combine2(const InternalNode& other, const OtherValueType& value,
2857  bool valueIsActive, CombineOp& op)
2858 {
2860 
2861  for (Index i = 0; i < NUM_VALUES; ++i) {
2862  if (other.isChildMaskOff(i)) {
2863  op(args.setARef(other.mNodes[i].getValue())
2864  .setAIsActive(other.isValueMaskOn(i))
2865  .setBRef(value)
2866  .setBIsActive(valueIsActive));
2867  // Replace child i with a constant value.
2868  this->makeChildNodeEmpty(i, args.result());
2869  mValueMask.set(i, args.resultIsActive());
2870  } else {
2871  ChildNodeType* otherChild = other.mNodes[i].getChild();
2872  assert(otherChild);
2873  if (this->isChildMaskOff(i)) {
2874  // Add a new child with the same coordinates, etc. as the other node's child.
2875  this->setChildNode(i,
2876  new ChildNodeType(otherChild->origin(), mNodes[i].getValue()));
2877  }
2878  // Combine the other node's child with a constant value
2879  // and write the result into child i.
2880  mNodes[i].getChild()->combine2(*otherChild, value, valueIsActive, op);
2881  }
2882  }
2883 }
2884 
2885 
2886 ////////////////////////////////////////
2887 
2888 
2889 template<typename ChildT, Index Log2Dim>
2890 template<typename BBoxOp>
2891 inline void
2893 {
2894  for (ValueOnCIter i = this->cbeginValueOn(); i; ++i) {
2895  op.template operator()<LEVEL>(CoordBBox::createCube(i.getCoord(), ChildNodeType::DIM));
2896  }
2897  if (op.template descent<LEVEL>()) {
2898  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) i->visitActiveBBox(op);
2899  } else {
2900  for (ChildOnCIter i = this->cbeginChildOn(); i; ++i) {
2901  op.template operator()<LEVEL>(i->getNodeBoundingBox());
2902  }
2903  }
2904 }
2905 
2906 
2907 template<typename ChildT, Index Log2Dim>
2908 template<typename VisitorOp>
2909 inline void
2911 {
2912  doVisit<InternalNode, VisitorOp, ChildAllIter>(*this, op);
2913 }
2914 
2915 
2916 template<typename ChildT, Index Log2Dim>
2917 template<typename VisitorOp>
2918 inline void
2920 {
2921  doVisit<const InternalNode, VisitorOp, ChildAllCIter>(*this, op);
2922 }
2923 
2924 
2925 template<typename ChildT, Index Log2Dim>
2926 template<typename NodeT, typename VisitorOp, typename ChildAllIterT>
2927 inline void
2928 InternalNode<ChildT, Log2Dim>::doVisit(NodeT& self, VisitorOp& op)
2929 {
2930  typename NodeT::ValueType val;
2931  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
2932  if (op(iter)) continue;
2933  if (typename ChildAllIterT::ChildNodeType* child = iter.probeChild(val)) {
2934  child->visit(op);
2935  }
2936  }
2937 }
2938 
2939 
2940 ////////////////////////////////////////
2941 
2942 
2943 template<typename ChildT, Index Log2Dim>
2944 template<typename OtherNodeType, typename VisitorOp>
2945 inline void
2946 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op)
2947 {
2948  doVisit2Node<InternalNode, OtherNodeType, VisitorOp, ChildAllIter,
2949  typename OtherNodeType::ChildAllIter>(*this, other, op);
2950 }
2951 
2952 
2953 template<typename ChildT, Index Log2Dim>
2954 template<typename OtherNodeType, typename VisitorOp>
2955 inline void
2956 InternalNode<ChildT, Log2Dim>::visit2Node(OtherNodeType& other, VisitorOp& op) const
2957 {
2958  doVisit2Node<const InternalNode, OtherNodeType, VisitorOp, ChildAllCIter,
2959  typename OtherNodeType::ChildAllCIter>(*this, other, op);
2960 }
2961 
2962 
2963 template<typename ChildT, Index Log2Dim>
2964 template<
2965  typename NodeT,
2966  typename OtherNodeT,
2967  typename VisitorOp,
2968  typename ChildAllIterT,
2969  typename OtherChildAllIterT>
2970 inline void
2971 InternalNode<ChildT, Log2Dim>::doVisit2Node(NodeT& self, OtherNodeT& other, VisitorOp& op)
2972 {
2973  // Allow the two nodes to have different ValueTypes, but not different dimensions.
2974  static_assert(OtherNodeT::NUM_VALUES == NodeT::NUM_VALUES,
2975  "visit2() requires nodes to have the same dimensions");
2976  static_assert(OtherNodeT::LEVEL == NodeT::LEVEL,
2977  "visit2() requires nodes to be at the same tree level");
2978 
2979  typename NodeT::ValueType val;
2980  typename OtherNodeT::ValueType otherVal;
2981 
2982  ChildAllIterT iter = self.beginChildAll();
2983  OtherChildAllIterT otherIter = other.beginChildAll();
2984 
2985  for ( ; iter && otherIter; ++iter, ++otherIter)
2986  {
2987  const size_t skipBranch = static_cast<size_t>(op(iter, otherIter));
2988 
2989  typename ChildAllIterT::ChildNodeType* child =
2990  (skipBranch & 1U) ? nullptr : iter.probeChild(val);
2991  typename OtherChildAllIterT::ChildNodeType* otherChild =
2992  (skipBranch & 2U) ? nullptr : otherIter.probeChild(otherVal);
2993 
2994  if (child != nullptr && otherChild != nullptr) {
2995  child->visit2Node(*otherChild, op);
2996  } else if (child != nullptr) {
2997  child->visit2(otherIter, op);
2998  } else if (otherChild != nullptr) {
2999  otherChild->visit2(iter, op, /*otherIsLHS=*/true);
3000  }
3001  }
3002 }
3003 
3004 
3005 ////////////////////////////////////////
3006 
3007 
3008 template<typename ChildT, Index Log2Dim>
3009 template<typename OtherChildAllIterType, typename VisitorOp>
3010 inline void
3011 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
3012  VisitorOp& op, bool otherIsLHS)
3013 {
3014  doVisit2<InternalNode, VisitorOp, ChildAllIter, OtherChildAllIterType>(
3015  *this, otherIter, op, otherIsLHS);
3016 }
3017 
3018 
3019 template<typename ChildT, Index Log2Dim>
3020 template<typename OtherChildAllIterType, typename VisitorOp>
3021 inline void
3022 InternalNode<ChildT, Log2Dim>::visit2(OtherChildAllIterType& otherIter,
3023  VisitorOp& op, bool otherIsLHS) const
3024 {
3025  doVisit2<const InternalNode, VisitorOp, ChildAllCIter, OtherChildAllIterType>(
3026  *this, otherIter, op, otherIsLHS);
3027 }
3028 
3029 
3030 template<typename ChildT, Index Log2Dim>
3031 template<typename NodeT, typename VisitorOp, typename ChildAllIterT, typename OtherChildAllIterT>
3032 inline void
3033 InternalNode<ChildT, Log2Dim>::doVisit2(NodeT& self, OtherChildAllIterT& otherIter,
3034  VisitorOp& op, bool otherIsLHS)
3035 {
3036  if (!otherIter) return;
3037 
3038  const size_t skipBitMask = (otherIsLHS ? 2U : 1U);
3039 
3040  typename NodeT::ValueType val;
3041  for (ChildAllIterT iter = self.beginChildAll(); iter; ++iter) {
3042  const size_t skipBranch = static_cast<size_t>(
3043  otherIsLHS ? op(otherIter, iter) : op(iter, otherIter));
3044 
3045  typename ChildAllIterT::ChildNodeType* child =
3046  (skipBranch & skipBitMask) ? nullptr : iter.probeChild(val);
3047 
3048  if (child != nullptr) child->visit2(otherIter, op, otherIsLHS);
3049  }
3050 }
3051 
3052 
3053 ////////////////////////////////////////
3054 
3055 
3056 template<typename ChildT, Index Log2Dim>
3057 inline void
3058 InternalNode<ChildT, Log2Dim>::writeBuffers(std::ostream& os, bool toHalf) const
3059 {
3060  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3061  iter->writeBuffers(os, toHalf);
3062  }
3063 }
3064 
3065 
3066 template<typename ChildT, Index Log2Dim>
3067 inline void
3068 InternalNode<ChildT, Log2Dim>::readBuffers(std::istream& is, bool fromHalf)
3069 {
3070  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3071  iter->readBuffers(is, fromHalf);
3072  }
3073 }
3074 
3075 
3076 template<typename ChildT, Index Log2Dim>
3077 inline void
3079  const CoordBBox& clipBBox, bool fromHalf)
3080 {
3081  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3082  // Stream in the branch rooted at this child.
3083  // (We can't skip over children that lie outside the clipping region,
3084  // because buffers are serialized in depth-first order and need to be
3085  // unserialized in the same order.)
3086  iter->readBuffers(is, clipBBox, fromHalf);
3087  }
3088 
3089  // Get this tree's background value.
3090  ValueType background = zeroVal<ValueType>();
3091  if (const void* bgPtr = io::getGridBackgroundValuePtr(is)) {
3092  background = *static_cast<const ValueType*>(bgPtr);
3093  }
3094  this->clip(clipBBox, background);
3095 }
3096 
3097 
3098 ////////////////////////////////////////
3099 
3100 
3101 template<typename ChildT, Index Log2Dim>
3102 void
3104 {
3105  dims.push_back(Log2Dim);
3106  ChildNodeType::getNodeLog2Dims(dims);
3107 }
3108 
3109 
3110 template<typename ChildT, Index Log2Dim>
3111 inline void
3113 {
3114  assert(n<(1<<3*Log2Dim));
3115  xyz.setX(n >> 2*Log2Dim);
3116  n &= ((1<<2*Log2Dim)-1);
3117  xyz.setY(n >> Log2Dim);
3118  xyz.setZ(n & ((1<<Log2Dim)-1));
3119 }
3120 
3121 
3122 template<typename ChildT, Index Log2Dim>
3123 inline Index
3125 {
3126  return (((xyz[0] & (DIM-1u)) >> ChildNodeType::TOTAL) << 2*Log2Dim)
3127  + (((xyz[1] & (DIM-1u)) >> ChildNodeType::TOTAL) << Log2Dim)
3128  + ((xyz[2] & (DIM-1u)) >> ChildNodeType::TOTAL);
3129 }
3130 
3131 
3132 template<typename ChildT, Index Log2Dim>
3133 inline Coord
3135 {
3136  Coord local;
3137  this->offsetToLocalCoord(n, local);
3138  local <<= ChildT::TOTAL;
3139  return local + this->origin();
3140 }
3141 
3142 
3143 ////////////////////////////////////////
3144 
3145 
3146 template<typename ChildT, Index Log2Dim>
3147 template<typename ArrayT>
3148 inline void
3150 {
3151  using T = typename ArrayT::value_type;
3152  static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
3153  using ArrayChildT = typename std::conditional<
3155  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3158  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
3159  } else {
3160  iter->getNodes(array);//descent
3161  }
3163  }
3164 }
3165 
3166 template<typename ChildT, Index Log2Dim>
3167 template<typename ArrayT>
3168 inline void
3170 {
3171  using T = typename ArrayT::value_type;
3172  static_assert(std::is_pointer<T>::value, "argument to getNodes() must be a pointer array");
3173  static_assert(std::is_const<typename std::remove_pointer<T>::type>::value,
3174  "argument to getNodes() must be an array of const node pointers");
3175  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3178  array.push_back(reinterpret_cast<T>(mNodes[iter.pos()].getChild()));
3179  } else {
3180  iter->getNodes(array);//descent
3181  }
3183  }
3184 }
3185 
3186 
3187 ////////////////////////////////////////
3188 
3189 
3190 template<typename ChildT, Index Log2Dim>
3191 template<typename ArrayT>
3192 inline void
3194 {
3195  using T = typename ArrayT::value_type;
3196  static_assert(std::is_pointer<T>::value, "argument to stealNodes() must be a pointer array");
3197  using ArrayChildT = typename std::conditional<
3200  for (ChildOnIter iter = this->beginChildOn(); iter; ++iter) {
3201  const Index n = iter.pos();
3203  array.push_back(reinterpret_cast<T>(mNodes[n].getChild()));
3204  mValueMask.set(n, state);
3205  mNodes[n].setValue(value);
3206  } else {
3207  iter->stealNodes(array, value, state);//descent
3208  }
3209  }
3210  if (std::is_same<T, ArrayChildT*>::value) mChildMask.setOff();
3212 }
3213 
3214 
3215 ////////////////////////////////////////
3216 
3217 
3218 template<typename ChildT, Index Log2Dim>
3219 inline void
3221  const ValueType& newBackground)
3222 {
3223  if (math::isExactlyEqual(oldBackground, newBackground)) return;
3224  for (Index i = 0; i < NUM_VALUES; ++i) {
3225  if (this->isChildMaskOn(i)) {
3226  mNodes[i].getChild()->resetBackground(oldBackground, newBackground);
3227  } else if (this->isValueMaskOff(i)) {
3228  if (math::isApproxEqual(mNodes[i].getValue(), oldBackground)) {
3229  mNodes[i].setValue(newBackground);
3230  } else if (math::isApproxEqual(mNodes[i].getValue(), math::negative(oldBackground))) {
3231  mNodes[i].setValue(math::negative(newBackground));
3232  }
3233  }
3234  }
3235 }
3236 
3237 template<typename ChildT, Index Log2Dim>
3238 template<typename OtherChildNodeType, Index OtherLog2Dim>
3239 inline bool
3242 {
3243  if (Log2Dim != OtherLog2Dim || mChildMask != other->mChildMask ||
3244  mValueMask != other->mValueMask) return false;
3245  for (ChildOnCIter iter = this->cbeginChildOn(); iter; ++iter) {
3246  if (!iter->hasSameTopology(other->mNodes[iter.pos()].getChild())) return false;
3247  }
3248  return true;
3249 }
3250 
3251 
3252 template<typename ChildT, Index Log2Dim>
3253 inline void
3255 {
3256  assert(child);
3257  if (this->isChildMaskOn(i)) {
3258  delete mNodes[i].getChild();
3259  } else {
3260  mChildMask.setOn(i);
3261  mValueMask.setOff(i);
3262  }
3263  mNodes[i].setChild(child);
3264 }
3265 
3266 template<typename ChildT, Index Log2Dim>
3267 inline void
3269 {
3270  assert(child);
3271  assert(mChildMask.isOff(i));
3272  mChildMask.setOn(i);
3273  mValueMask.setOff(i);
3274  mNodes[i].setChild(child);
3275 }
3276 
3277 
3278 template<typename ChildT, Index Log2Dim>
3279 inline ChildT*
3281 {
3282  if (this->isChildMaskOff(i)) {
3283  mNodes[i].setValue(value);
3284  return nullptr;
3285  }
3286  ChildNodeType* child = mNodes[i].getChild();
3287  mChildMask.setOff(i);
3288  mNodes[i].setValue(value);
3289  return child;
3290 }
3291 
3292 
3293 template<typename ChildT, Index Log2Dim>
3294 inline void
3296 {
3297  delete this->unsetChildNode(n, value);
3298 }
3299 
3300 template<typename ChildT, Index Log2Dim>
3301 inline ChildT*
3303 {
3304  assert(this->isChildMaskOn(n));
3305  return mNodes[n].getChild();
3306 }
3307 
3308 
3309 template<typename ChildT, Index Log2Dim>
3310 inline const ChildT*
3312 {
3313  assert(this->isChildMaskOn(n));
3314  return mNodes[n].getChild();
3315 }
3316 
3317 } // namespace tree
3318 } // namespace OPENVDB_VERSION_NAME
3319 } // namespace openvdb
3320 
3321 #endif // OPENVDB_TREE_INTERNALNODE_HAS_BEEN_INCLUDED
bool probeValue(const Coord &xyz, ValueType &value) const
const AValueType & result() const
Get the output value.
Definition: Types.h:574
Vec2< T > minComponent(const Vec2< T > &v1, const Vec2< T > &v2)
Return component-wise minimum of the two vectors.
Definition: Vec2.h:508
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
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
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:529
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)
void visit2Node(OtherNodeType &other, VisitorOp &)
bool isExactlyEqual(const T0 &a, const T1 &b)
Return true if a is exactly equal to b.
Definition: Math.h:444
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
static void doVisit2(NodeT &, OtherChildAllIterT &, VisitorOp &, bool otherIsLHS)
T negative(const T &val)
Return the unary negation of the given value.
Definition: Math.h:127
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
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:773
const GLfloat * c
Definition: glew.h:16631
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
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)
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:207
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
bool hasActiveTiles() const
Return true if this node or any of its child nodes have any active tiles.
static void doVisit(NodeT &, VisitorOp &)
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.
GLdouble GLdouble t
Definition: glew.h:1403
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:947
uint64 value_type
Definition: GA_PrimCompat.h:29
Tag dispatch class that distinguishes constructors during file input.
Definition: Types.h:650
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
GLenum target
Definition: glcorearb.h:1667
DeepCopy(const OtherInternalNode *source, InternalNode *target)
Definition: InternalNode.h:892
bool isInactive() const
Return true if this node has no children and only contains inactive values.
Definition: InternalNode.h:330
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1602
GLint GLenum GLint x
Definition: glcorearb.h:409
void operator()(const tbb::blocked_range< Index > &r) const
Definition: InternalNode.h:986
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.
GLenum array
Definition: glew.h:9108
typename ChildNodeType::ValueType ValueType
Definition: InternalNode.h:38
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...
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:407
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)
GLint GLuint mask
Definition: glcorearb.h:124
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:772
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
const GLdouble * v
Definition: glcorearb.h:837
GLsizei GLsizei GLchar * source
Definition: glcorearb.h:803
GLuint GLuint end
Definition: glcorearb.h:475
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
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:896
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:848
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
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
GLint GLsizei count
Definition: glcorearb.h:405
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...
ValueIter< const InternalNode, const ValueType, MaskOffIterator, ChildOff > ChildOffCIter
Definition: InternalNode.h:209
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
void visitActiveBBox(BBoxOp &) const
Calls the templated functor BBoxOp with bounding box information for all active tiles and leaf nodes ...
void visit2(IterT &otherIter, VisitorOp &, bool otherIsLHS=false)
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
SIMD Intrinsic Headers.
Definition: Platform.h:115
TopologyCopy1(const OtherInternalNode *source, InternalNode *target, const ValueType &background)
Definition: InternalNode.h:942
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...
GLdouble n
Definition: glcorearb.h:2008
GLuint GLfloat * val
Definition: glcorearb.h:1608
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
static void doVisit2Node(NodeT &, OtherNodeT &, VisitorOp &)
DenseMaskIterator< NodeMask > DenseIterator
Definition: NodeMasks.h:350
Library and file format version numbers.
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)
if(num_boxed_items<=0)
Definition: UT_RTreeImpl.h:697
GLsizei const GLfloat * value
Definition: glcorearb.h:824
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:582
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:116
TopologyCopy2(const OtherInternalNode *source, InternalNode *target, const ValueType &offValue, const ValueType &onValue)
Definition: InternalNode.h:981
Definition: core.h:1131
void combine2(const InternalNode &other0, const OtherNodeType &other1, CombineOp &)
GLintptr offset
Definition: glcorearb.h:665
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:644
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...
Tag dispatch class that distinguishes constructors that deep copy.
Definition: Types.h:646
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
type
Definition: core.h:1059
GLboolean r
Definition: glcorearb.h:1222
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)
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.
GLdouble s
Definition: glew.h:1395
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:827
#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)
GLint y
Definition: glcorearb.h:103
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
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...