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