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