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