HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Tree.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /// @file tree/Tree.h
5 
6 #ifndef OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
7 #define OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
8 
9 #include <openvdb/Types.h>
10 #include <openvdb/Metadata.h>
11 #include <openvdb/math/Math.h>
12 #include <openvdb/math/BBox.h>
13 #include <openvdb/util/Formats.h>
14 #include <openvdb/util/logging.h>
15 #include <openvdb/Platform.h>
16 #include "RootNode.h"
17 #include "InternalNode.h"
18 #include "LeafNode.h"
19 #include "TreeIterator.h"
20 #include "ValueAccessor.h"
21 #include <tbb/concurrent_hash_map.h>
22 #include <cstdint>
23 #include <iostream>
24 #include <mutex>
25 #include <sstream>
26 #include <vector>
27 
28 
29 namespace openvdb {
31 namespace OPENVDB_VERSION_NAME {
32 namespace tree {
33 
34 /// @brief Base class for typed trees
36 {
37 public:
40 
41  TreeBase() = default;
42  TreeBase(const TreeBase&) = default;
43  TreeBase& operator=(const TreeBase&) = delete; // disallow assignment
44  virtual ~TreeBase() = default;
45 
46  /// Return the name of this tree's type.
47  virtual const Name& type() const = 0;
48 
49  /// Return the name of the type of a voxel's value (e.g., "float" or "vec3d").
50  virtual Name valueType() const = 0;
51 
52  /// Return a pointer to a deep copy of this tree
53  virtual TreeBase::Ptr copy() const = 0;
54 
55  //
56  // Tree methods
57  //
58  /// @brief Return this tree's background value wrapped as metadata.
59  /// @note Query the metadata object for the value's type.
60  virtual Metadata::Ptr getBackgroundValue() const { return Metadata::Ptr(); }
61 
62  /// @brief Return in @a bbox the axis-aligned bounding box of all
63  /// active tiles and leaf nodes with active values.
64  /// @details This is faster than calling evalActiveVoxelBoundingBox,
65  /// which visits the individual active voxels, and hence
66  /// evalLeafBoundingBox produces a less tight, i.e. approximate, bbox.
67  /// @return @c false if the bounding box is empty (in which case
68  /// the bbox is set to its default value).
69  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const = 0;
70 
71  /// @brief Return in @a dim the dimensions of the axis-aligned bounding box
72  /// of all leaf nodes.
73  /// @return @c false if the bounding box is empty.
74  virtual bool evalLeafDim(Coord& dim) const = 0;
75 
76  /// @brief Return in @a bbox the axis-aligned bounding box of all
77  /// active voxels and tiles.
78  /// @details This method produces a more accurate, i.e. tighter,
79  /// bounding box than evalLeafBoundingBox which is approximate but
80  /// faster.
81  /// @return @c false if the bounding box is empty (in which case
82  /// the bbox is set to its default value).
83  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const = 0;
84 
85  /// @brief Return in @a dim the dimensions of the axis-aligned bounding box of all
86  /// active voxels. This is a tighter bounding box than the leaf node bounding box.
87  /// @return @c false if the bounding box is empty.
88  virtual bool evalActiveVoxelDim(Coord& dim) const = 0;
89 
90  virtual void getIndexRange(CoordBBox& bbox) const = 0;
91 
92  /// @brief Replace with background tiles any nodes whose voxel buffers
93  /// have not yet been allocated.
94  /// @details Typically, unallocated nodes are leaf nodes whose voxel buffers
95  /// are not yet resident in memory because delayed loading is in effect.
96  /// @sa readNonresidentBuffers, io::File::open
97  virtual void clipUnallocatedNodes() = 0;
98  /// Return the total number of unallocated leaf nodes residing in this tree.
99  virtual Index32 unallocatedLeafCount() const = 0;
100 
101 
102  //
103  // Statistics
104  //
105  /// @brief Return the depth of this tree.
106  ///
107  /// A tree with only a root node and leaf nodes has depth 2, for example.
108  virtual Index treeDepth() const = 0;
109  /// Return the number of leaf nodes.
110  virtual Index32 leafCount() const = 0;
111 #if OPENVDB_ABI_VERSION_NUMBER >= 7
112  /// Return a vector with node counts. The number of nodes of type NodeType
113  /// is given as element NodeType::LEVEL in the return vector. Thus, the size
114  /// of this vector corresponds to the height (or depth) of this tree.
115  virtual std::vector<Index32> nodeCount() const = 0;
116 #endif
117  /// Return the number of non-leaf nodes.
118  virtual Index32 nonLeafCount() const = 0;
119  /// Return the number of active voxels stored in leaf nodes.
120  virtual Index64 activeLeafVoxelCount() const = 0;
121  /// Return the number of inactive voxels stored in leaf nodes.
122  virtual Index64 inactiveLeafVoxelCount() const = 0;
123  /// Return the total number of active voxels.
124  virtual Index64 activeVoxelCount() const = 0;
125  /// Return the number of inactive voxels within the bounding box of all active voxels.
126  virtual Index64 inactiveVoxelCount() const = 0;
127  /// Return the total number of active tiles.
128  virtual Index64 activeTileCount() const = 0;
129 
130  /// Return the total amount of memory in bytes occupied by this tree.
131  virtual Index64 memUsage() const { return 0; }
132 
133 
134  //
135  // I/O methods
136  //
137  /// @brief Read the tree topology from a stream.
138  ///
139  /// This will read the tree structure and tile values, but not voxel data.
140  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
141  /// @brief Write the tree topology to a stream.
142  ///
143  /// This will write the tree structure and tile values, but not voxel data.
144  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
145 
146  /// Read all data buffers for this tree.
147  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false) = 0;
148  /// Read all of this tree's data buffers that intersect the given bounding box.
149  virtual void readBuffers(std::istream&, const CoordBBox&, bool saveFloatAsHalf = false) = 0;
150  /// @brief Read all of this tree's data buffers that are not yet resident in memory
151  /// (because delayed loading is in effect).
152  /// @details If this tree was read from a memory-mapped file, this operation
153  /// disconnects the tree from the file.
154  /// @sa clipUnallocatedNodes, io::File::open, io::MappedFile
155  virtual void readNonresidentBuffers() const = 0;
156  /// Write out all the data buffers for this tree.
157  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const = 0;
158 
159  /// @brief Print statistics, memory usage and other information about this tree.
160  /// @param os a stream to which to write textual information
161  /// @param verboseLevel 1: print tree configuration only;
162  /// 2: include node and voxel statistics;
163  /// 3: include memory usage;
164  /// 4: include minimum and maximum voxel values
165  /// @warning @a verboseLevel 4 forces loading of any unallocated nodes.
166  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
167 };
168 
169 
170 ////////////////////////////////////////
171 
172 
173 template<typename _RootNodeType>
174 class Tree: public TreeBase
175 {
176 public:
179 
180  using RootNodeType = _RootNodeType;
181  using ValueType = typename RootNodeType::ValueType;
182  using BuildType = typename RootNodeType::BuildType;
183  using LeafNodeType = typename RootNodeType::LeafNodeType;
184 
185  static const Index DEPTH = RootNodeType::LEVEL + 1;
186 
187  /// @brief ValueConverter<T>::Type is the type of a tree having the same
188  /// hierarchy as this tree but a different value type, T.
189  ///
190  /// For example, FloatTree::ValueConverter<double>::Type is equivalent to DoubleTree.
191  /// @note If the source tree type is a template argument, it might be necessary
192  /// to write "typename SourceTree::template ValueConverter<T>::Type".
193  template<typename OtherValueType>
194  struct ValueConverter {
196  };
197 
198 
199  Tree() {}
200 
201  Tree& operator=(const Tree&) = delete; // disallow assignment
202 
203  /// Deep copy constructor
204  Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
205  {
206  }
207 
208  /// @brief Value conversion deep copy constructor
209  ///
210  /// Deep copy a tree of the same configuration as this tree type but a different
211  /// ValueType, casting the other tree's values to this tree's ValueType.
212  /// @throw TypeError if the other tree's configuration doesn't match this tree's
213  /// or if this tree's ValueType is not constructible from the other tree's ValueType.
214  template<typename OtherRootType>
215  explicit Tree(const Tree<OtherRootType>& other): TreeBase(other), mRoot(other.root())
216  {
217  }
218 
219  /// @brief Topology copy constructor from a tree of a different type
220  ///
221  /// Copy the structure, i.e., the active states of tiles and voxels, of another
222  /// tree of a possibly different type, but don't copy any tile or voxel values.
223  /// Instead, initialize tiles and voxels with the given active and inactive values.
224  /// @param other a tree having (possibly) a different ValueType
225  /// @param inactiveValue background value for this tree, and the value to which
226  /// all inactive tiles and voxels are initialized
227  /// @param activeValue value to which active tiles and voxels are initialized
228  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
229  template<typename OtherTreeType>
230  Tree(const OtherTreeType& other,
231  const ValueType& inactiveValue,
232  const ValueType& activeValue,
233  TopologyCopy):
234  TreeBase(other),
235  mRoot(other.root(), inactiveValue, activeValue, TopologyCopy())
236  {
237  }
238 
239  /// @brief Topology copy constructor from a tree of a different type
240  ///
241  /// @note This topology copy constructor is generally faster than
242  /// the one that takes both a foreground and a background value.
243  ///
244  /// Copy the structure, i.e., the active states of tiles and voxels, of another
245  /// tree of a possibly different type, but don't copy any tile or voxel values.
246  /// Instead, initialize tiles and voxels with the given background value.
247  /// @param other a tree having (possibly) a different ValueType
248  /// @param background the value to which tiles and voxels are initialized
249  /// @throw TypeError if the other tree's configuration doesn't match this tree's.
250  template<typename OtherTreeType>
251  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
252  TreeBase(other),
253  mRoot(other.root(), background, TopologyCopy())
254  {
255  }
256 
257  /// Empty tree constructor
258  Tree(const ValueType& background): mRoot(background) {}
259 
260  ~Tree() override { this->clear(); releaseAllAccessors(); }
261 
262  /// Return a pointer to a deep copy of this tree
263  TreeBase::Ptr copy() const override { return TreeBase::Ptr(new Tree(*this)); }
264 
265  /// Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
266  Name valueType() const override { return typeNameAsString<ValueType>(); }
267 
268  /// Return the name of this type of tree.
269  static const Name& treeType();
270  /// Return the name of this type of tree.
271  const Name& type() const override { return this->treeType(); }
272 
273  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
274  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
275 
276  //@{
277  /// Return this tree's root node.
278  RootNodeType& root() { return mRoot; }
279  const RootNodeType& root() const { return mRoot; }
280  //@}
281 
282 
283  //
284  // Tree methods
285  //
286  /// @brief Return @c true if the given tree has the same node and active value
287  /// topology as this tree, whether or not it has the same @c ValueType.
288  template<typename OtherRootNodeType>
289  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
290 
291  bool evalLeafBoundingBox(CoordBBox& bbox) const override;
292  bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const override;
293  bool evalActiveVoxelDim(Coord& dim) const override;
294  bool evalLeafDim(Coord& dim) const override;
295 
296  /// @brief Traverse the type hierarchy of nodes, and return, in @a dims, a list
297  /// of the Log2Dims of nodes in order from RootNode to LeafNode.
298  /// @note Because RootNodes are resizable, the RootNode Log2Dim is 0 for all trees.
299  static void getNodeLog2Dims(std::vector<Index>& dims);
300 
301 
302  //
303  // I/O methods
304  //
305  /// @brief Read the tree topology from a stream.
306  ///
307  /// This will read the tree structure and tile values, but not voxel data.
308  void readTopology(std::istream&, bool saveFloatAsHalf = false) override;
309  /// @brief Write the tree topology to a stream.
310  ///
311  /// This will write the tree structure and tile values, but not voxel data.
312  void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const override;
313  /// Read all data buffers for this tree.
314  void readBuffers(std::istream&, bool saveFloatAsHalf = false) override;
315  /// Read all of this tree's data buffers that intersect the given bounding box.
316  void readBuffers(std::istream&, const CoordBBox&, bool saveFloatAsHalf = false) override;
317  /// @brief Read all of this tree's data buffers that are not yet resident in memory
318  /// (because delayed loading is in effect).
319  /// @details If this tree was read from a memory-mapped file, this operation
320  /// disconnects the tree from the file.
321  /// @sa clipUnallocatedNodes, io::File::open, io::MappedFile
322  void readNonresidentBuffers() const override;
323  /// Write out all data buffers for this tree.
324  void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const override;
325 
326  void print(std::ostream& os = std::cout, int verboseLevel = 1) const override;
327 
328 
329  //
330  // Statistics
331  //
332  /// @brief Return the depth of this tree.
333  ///
334  /// A tree with only a root node and leaf nodes has depth 2, for example.
335  Index treeDepth() const override { return DEPTH; }
336  /// Return the number of leaf nodes.
337  Index32 leafCount() const override { return mRoot.leafCount(); }
338 #if OPENVDB_ABI_VERSION_NUMBER >= 7
339  /// Return a vector with node counts. The number of nodes of type NodeType
340  /// is given as element NodeType::LEVEL in the return vector. Thus, the size
341  /// of this vector corresponds to the height (or depth) of this tree.
342  std::vector<Index32> nodeCount() const override
343  {
344  std::vector<Index32> vec(DEPTH, 0);
345  mRoot.nodeCount( vec );
346  return vec;// Named Return Value Optimization
347  }
348 #endif
349  /// Return the number of non-leaf nodes.
350  Index32 nonLeafCount() const override { return mRoot.nonLeafCount(); }
351  /// Return the number of active voxels stored in leaf nodes.
352  Index64 activeLeafVoxelCount() const override { return mRoot.onLeafVoxelCount(); }
353  /// Return the number of inactive voxels stored in leaf nodes.
354  Index64 inactiveLeafVoxelCount() const override { return mRoot.offLeafVoxelCount(); }
355  /// Return the total number of active voxels.
356  Index64 activeVoxelCount() const override { return mRoot.onVoxelCount(); }
357  /// Return the number of inactive voxels within the bounding box of all active voxels.
358  Index64 inactiveVoxelCount() const override;
359  /// Return the total number of active tiles.
360  Index64 activeTileCount() const override { return mRoot.onTileCount(); }
361 
362  /// Return the minimum and maximum active values in this tree.
363  void evalMinMax(ValueType &min, ValueType &max) const;
364 
365  Index64 memUsage() const override { return sizeof(*this) + mRoot.memUsage(); }
366 
367 
368  //
369  // Voxel access methods (using signed indexing)
370  //
371  /// Return the value of the voxel at the given coordinates.
372  const ValueType& getValue(const Coord& xyz) const;
373  /// @brief Return the value of the voxel at the given coordinates
374  /// and update the given accessor's node cache.
375  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
376 
377  /// @brief Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
378  /// @details If (x, y, z) isn't explicitly represented in the tree (i.e., it is
379  /// implicitly a background voxel), return -1.
380  int getValueDepth(const Coord& xyz) const;
381 
382  /// Set the active state of the voxel at the given coordinates but don't change its value.
383  void setActiveState(const Coord& xyz, bool on);
384  /// Set the value of the voxel at the given coordinates but don't change its active state.
385  void setValueOnly(const Coord& xyz, const ValueType& value);
386  /// Mark the voxel at the given coordinates as active but don't change its value.
387  void setValueOn(const Coord& xyz);
388  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
389  void setValueOn(const Coord& xyz, const ValueType& value);
390  /// Set the value of the voxel at the given coordinates and mark the voxel as active.
391  void setValue(const Coord& xyz, const ValueType& value);
392  /// @brief Set the value of the voxel at the given coordinates, mark the voxel as active,
393  /// and update the given accessor's node cache.
394  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
395  /// Mark the voxel at the given coordinates as inactive but don't change its value.
396  void setValueOff(const Coord& xyz);
397  /// Set the value of the voxel at the given coordinates and mark the voxel as inactive.
398  void setValueOff(const Coord& xyz, const ValueType& value);
399 
400  /// @brief Apply a functor to the value of the voxel at the given coordinates
401  /// and mark the voxel as active.
402  /// @details Provided that the functor can be inlined, this is typically
403  /// significantly faster than calling getValue() followed by setValueOn().
404  /// @param xyz the coordinates of a voxel whose value is to be modified
405  /// @param op a functor of the form <tt>void op(ValueType&) const</tt> that modifies
406  /// its argument in place
407  /// @par Example:
408  /// @code
409  /// Coord xyz(1, 0, -2);
410  /// // Multiply the value of a voxel by a constant and mark the voxel as active.
411  /// floatTree.modifyValue(xyz, [](float& f) { f *= 0.25; }); // C++11
412  /// // Set the value of a voxel to the maximum of its current value and 0.25,
413  /// // and mark the voxel as active.
414  /// floatTree.modifyValue(xyz, [](float& f) { f = std::max(f, 0.25f); }); // C++11
415  /// @endcode
416  /// @note The functor is not guaranteed to be called only once.
417  /// @see tools::foreach()
418  template<typename ModifyOp>
419  void modifyValue(const Coord& xyz, const ModifyOp& op);
420 
421  /// @brief Apply a functor to the voxel at the given coordinates.
422  /// @details Provided that the functor can be inlined, this is typically
423  /// significantly faster than calling getValue() followed by setValue().
424  /// @param xyz the coordinates of a voxel to be modified
425  /// @param op a functor of the form <tt>void op(ValueType&, bool&) const</tt> that
426  /// modifies its arguments, a voxel's value and active state, in place
427  /// @par Example:
428  /// @code
429  /// Coord xyz(1, 0, -2);
430  /// // Multiply the value of a voxel by a constant and mark the voxel as inactive.
431  /// floatTree.modifyValueAndActiveState(xyz,
432  /// [](float& f, bool& b) { f *= 0.25; b = false; }); // C++11
433  /// // Set the value of a voxel to the maximum of its current value and 0.25,
434  /// // but don't change the voxel's active state.
435  /// floatTree.modifyValueAndActiveState(xyz,
436  /// [](float& f, bool&) { f = std::max(f, 0.25f); }); // C++11
437  /// @endcode
438  /// @note The functor is not guaranteed to be called only once.
439  /// @see tools::foreach()
440  template<typename ModifyOp>
441  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
442 
443  /// @brief Get the value of the voxel at the given coordinates.
444  /// @return @c true if the value is active.
445  bool probeValue(const Coord& xyz, ValueType& value) const;
446 
447  /// Return @c true if the value at the given coordinates is active.
448  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
449  /// Return @c true if the value at the given coordinates is inactive.
450  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
451  /// Return @c true if this tree has any active tiles.
452  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
453 
454  /// Set all voxels that lie outside the given axis-aligned box to the background.
455  void clip(const CoordBBox&);
456  /// @brief Replace with background tiles any nodes whose voxel buffers
457  /// have not yet been allocated.
458  /// @details Typically, unallocated nodes are leaf nodes whose voxel buffers
459  /// are not yet resident in memory because delayed loading is in effect.
460  /// @sa readNonresidentBuffers, io::File::open
461  void clipUnallocatedNodes() override;
462 
463  /// Return the total number of unallocated leaf nodes residing in this tree.
464  Index32 unallocatedLeafCount() const override;
465 
466  //@{
467  /// @brief Set all voxels within a given axis-aligned box to a constant value.
468  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box
469  /// @param value the value to which to set voxels within the box
470  /// @param active if true, mark voxels within the box as active,
471  /// otherwise mark them as inactive
472  /// @note This operation generates a sparse, but not always optimally sparse,
473  /// representation of the filled box. Follow fill operations with a prune()
474  /// operation for optimal sparseness.
475  void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
476  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true)
477  {
478  this->sparseFill(bbox, value, active);
479  }
480  //@}
481 
482  /// @brief Set all voxels within a given axis-aligned box to a constant value
483  /// and ensure that those voxels are all represented at the leaf level.
484  /// @param bbox inclusive coordinates of opposite corners of an axis-aligned box.
485  /// @param value the value to which to set voxels within the box.
486  /// @param active if true, mark voxels within the box as active,
487  /// otherwise mark them as inactive.
488  /// @sa voxelizeActiveTiles()
489  void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
490 
491  /// @brief Densify active tiles, i.e., replace them with leaf-level active voxels.
492  ///
493  /// @param threaded if true, this operation is multi-threaded (over the internal nodes).
494  ///
495  /// @warning This method can explode the tree's memory footprint, especially if it
496  /// contains active tiles at the upper levels (in particular the root level)!
497  ///
498  /// @sa denseFill()
499  void voxelizeActiveTiles(bool threaded = true);
500 
501  /// @brief Reduce the memory footprint of this tree by replacing with tiles
502  /// any nodes whose values are all the same (optionally to within a tolerance)
503  /// and have the same active state.
504  /// @warning Will soon be deprecated!
505  void prune(const ValueType& tolerance = zeroVal<ValueType>())
506  {
507  this->clearAllAccessors();
508  mRoot.prune(tolerance);
509  }
510 
511  /// @brief Add the given leaf node to this tree, creating a new branch if necessary.
512  /// If a leaf node with the same origin already exists, replace it.
513  ///
514  /// @warning Ownership of the leaf is transferred to the tree so
515  /// the client code should not attempt to delete the leaf pointer!
516  void addLeaf(LeafNodeType* leaf) { assert(leaf); mRoot.addLeaf(leaf); }
517 
518  /// @brief Add a tile containing voxel (x, y, z) at the specified tree level,
519  /// creating a new branch if necessary. Delete any existing lower-level nodes
520  /// that contain (x, y, z).
521  /// @note @a level must be less than this tree's depth.
522  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
523 
524  /// @brief Return a pointer to the node of type @c NodeT that contains voxel (x, y, z)
525  /// and replace it with a tile of the specified value and state.
526  /// If no such node exists, leave the tree unchanged and return @c nullptr.
527  /// @note The caller takes ownership of the node and is responsible for deleting it.
528  template<typename NodeT>
529  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
530 
531  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
532  /// If no such node exists, create one that preserves the values and
533  /// active states of all voxels.
534  /// @details Use this method to preallocate a static tree topology over which to
535  /// safely perform multithreaded processing.
536  LeafNodeType* touchLeaf(const Coord& xyz);
537 
538  //@{
539  /// @brief Return a pointer to the node of type @c NodeType that contains
540  /// voxel (x, y, z). If no such node exists, return @c nullptr.
541  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
542  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
543  template<typename NodeType> const NodeType* probeNode(const Coord& xyz) const;
544  //@}
545 
546  //@{
547  /// @brief Return a pointer to the leaf node that contains voxel (x, y, z).
548  /// If no such node exists, return @c nullptr.
549  LeafNodeType* probeLeaf(const Coord& xyz);
550  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
551  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
552  //@}
553 
554  //@{
555  /// @brief Adds all nodes of a certain type to a container with the following API:
556  /// @code
557  /// struct ArrayT {
558  /// using value_type = ...; // the type of node to be added to the array
559  /// void push_back(value_type nodePtr); // add a node to the array
560  /// };
561  /// @endcode
562  /// @details An example of a wrapper around a c-style array is:
563  /// @code
564  /// struct MyArray {
565  /// using value_type = LeafType*;
566  /// value_type* ptr;
567  /// MyArray(value_type* array) : ptr(array) {}
568  /// void push_back(value_type leaf) { *ptr++ = leaf; }
569  ///};
570  /// @endcode
571  /// @details An example that constructs a list of pointer to all leaf nodes is:
572  /// @code
573  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
574  /// array.reserve(tree.leafCount());//this is a fast preallocation.
575  /// tree.getNodes(array);
576  /// @endcode
577  template<typename ArrayT> void getNodes(ArrayT& array) { mRoot.getNodes(array); }
578  template<typename ArrayT> void getNodes(ArrayT& array) const { mRoot.getNodes(array); }
579  //@}
580 
581  /// @brief Steals all nodes of a certain type from the tree and
582  /// adds them to a container with the following API:
583  /// @code
584  /// struct ArrayT {
585  /// using value_type = ...; // the type of node to be added to the array
586  /// void push_back(value_type nodePtr); // add a node to the array
587  /// };
588  /// @endcode
589  /// @details An example of a wrapper around a c-style array is:
590  /// @code
591  /// struct MyArray {
592  /// using value_type = LeafType*;
593  /// value_type* ptr;
594  /// MyArray(value_type* array) : ptr(array) {}
595  /// void push_back(value_type leaf) { *ptr++ = leaf; }
596  ///};
597  /// @endcode
598  /// @details An example that constructs a list of pointer to all leaf nodes is:
599  /// @code
600  /// std::vector<const LeafNodeType*> array;//most std contains have the required API
601  /// array.reserve(tree.leafCount());//this is a fast preallocation.
602  /// tree.stealNodes(array);
603  /// @endcode
604  template<typename ArrayT>
605  void stealNodes(ArrayT& array) { this->clearAllAccessors(); mRoot.stealNodes(array); }
606  template<typename ArrayT>
607  void stealNodes(ArrayT& array, const ValueType& value, bool state)
608  {
609  this->clearAllAccessors();
610  mRoot.stealNodes(array, value, state);
611  }
612 
613  //
614  // Aux methods
615  //
616  /// @brief Return @c true if this tree contains no nodes other than
617  /// the root node and no tiles other than background tiles.
618  bool empty() const { return mRoot.empty(); }
619 
620  /// Remove all tiles from this tree and all nodes other than the root node.
621  void clear();
622 
623  /// Clear all registered accessors.
624  void clearAllAccessors();
625 
626  //@{
627  /// @brief Register an accessor for this tree. Registered accessors are
628  /// automatically cleared whenever one of this tree's nodes is deleted.
631  //@}
632 
633  //@{
634  /// Dummy implementations
637  //@}
638 
639  //@{
640  /// Deregister an accessor so that it is no longer automatically cleared.
643  //@}
644 
645  //@{
646  /// Dummy implementations
649  //@}
650 
651  /// @brief Return this tree's background value wrapped as metadata.
652  /// @note Query the metadata object for the value's type.
653  Metadata::Ptr getBackgroundValue() const override;
654 
655  /// @brief Return this tree's background value.
656  ///
657  /// @note Use tools::changeBackground to efficiently modify the
658  /// background values. Else use tree.root().setBackground, which
659  /// is serial and hence slower.
660  const ValueType& background() const { return mRoot.background(); }
661 
662  /// Min and max are both inclusive.
663  void getIndexRange(CoordBBox& bbox) const override { mRoot.getIndexRange(bbox); }
664 
665  /// @brief Efficiently merge another tree into this tree using one of several schemes.
666  /// @details This operation is primarily intended to combine trees that are mostly
667  /// non-overlapping (for example, intermediate trees from computations that are
668  /// parallelized across disjoint regions of space).
669  /// @note This operation is not guaranteed to produce an optimally sparse tree.
670  /// Follow merge() with prune() for optimal sparseness.
671  /// @warning This operation always empties the other tree.
672  void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
673 
674  /// @brief Union this tree's set of active values with the active values
675  /// of the other tree, whose @c ValueType may be different.
676  /// @details The resulting state of a value is active if the corresponding value
677  /// was already active OR if it is active in the other tree. Also, a resulting
678  /// value maps to a voxel if the corresponding value already mapped to a voxel
679  /// OR if it is a voxel in the other tree. Thus, a resulting value can only
680  /// map to a tile if the corresponding value already mapped to a tile
681  /// AND if it is a tile value in other tree.
682  ///
683  /// @note This operation modifies only active states, not values.
684  /// Specifically, active tiles and voxels in this tree are not changed, and
685  /// tiles or voxels that were inactive in this tree but active in the other tree
686  /// are marked as active in this tree but left with their original values.
687  template<typename OtherRootNodeType>
688  void topologyUnion(const Tree<OtherRootNodeType>& other);
689 
690  /// @brief Intersects this tree's set of active values with the active values
691  /// of the other tree, whose @c ValueType may be different.
692  /// @details The resulting state of a value is active only if the corresponding
693  /// value was already active AND if it is active in the other tree. Also, a
694  /// resulting value maps to a voxel if the corresponding value
695  /// already mapped to an active voxel in either of the two grids
696  /// and it maps to an active tile or voxel in the other grid.
697  ///
698  /// @note This operation can delete branches in this grid if they
699  /// overlap with inactive tiles in the other grid. Likewise active
700  /// voxels can be turned into unactive voxels resulting in leaf
701  /// nodes with no active values. Thus, it is recommended to
702  /// subsequently call tools::pruneInactive.
703  template<typename OtherRootNodeType>
705 
706  /// @brief Difference this tree's set of active values with the active values
707  /// of the other tree, whose @c ValueType may be different. So a
708  /// resulting voxel will be active only if the original voxel is
709  /// active in this tree and inactive in the other tree.
710  ///
711  /// @note This operation can delete branches in this grid if they
712  /// overlap with active tiles in the other grid. Likewise active
713  /// voxels can be turned into inactive voxels resulting in leaf
714  /// nodes with no active values. Thus, it is recommended to
715  /// subsequently call tools::pruneInactive.
716  template<typename OtherRootNodeType>
717  void topologyDifference(const Tree<OtherRootNodeType>& other);
718 
719  /// For a given function @c f, use sparse traversal to compute <tt>f(this, other)</tt>
720  /// over all corresponding pairs of values (tile or voxel) of this tree and the other tree
721  /// and store the result in this tree.
722  /// This method is typically more space-efficient than the two-tree combine2(),
723  /// since it moves rather than copies nodes from the other tree into this tree.
724  /// @note This operation always empties the other tree.
725  /// @param other a tree of the same type as this tree
726  /// @param op a functor of the form <tt>void op(const T& a, const T& b, T& result)</tt>,
727  /// where @c T is this tree's @c ValueType, that computes
728  /// <tt>result = f(a, b)</tt>
729  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
730  /// more space-efficient than pruning the entire tree in one pass)
731  ///
732  /// @par Example:
733  /// Compute the per-voxel difference between two floating-point trees,
734  /// @c aTree and @c bTree, and store the result in @c aTree (leaving @c bTree empty).
735  /// @code
736  /// {
737  /// struct Local {
738  /// static inline void diff(const float& a, const float& b, float& result) {
739  /// result = a - b;
740  /// }
741  /// };
742  /// aTree.combine(bTree, Local::diff);
743  /// }
744  /// @endcode
745  ///
746  /// @par Example:
747  /// Compute <tt>f * a + (1 - f) * b</tt> over all voxels of two floating-point trees,
748  /// @c aTree and @c bTree, and store the result in @c aTree (leaving @c bTree empty).
749  /// @code
750  /// namespace {
751  /// struct Blend {
752  /// Blend(float f): frac(f) {}
753  /// inline void operator()(const float& a, const float& b, float& result) const {
754  /// result = frac * a + (1.0 - frac) * b;
755  /// }
756  /// float frac;
757  /// };
758  /// }
759  /// {
760  /// aTree.combine(bTree, Blend(0.25)); // 0.25 * a + 0.75 * b
761  /// }
762  /// @endcode
763  template<typename CombineOp>
764  void combine(Tree& other, CombineOp& op, bool prune = false);
765 #ifndef _MSC_VER
766  template<typename CombineOp>
767  void combine(Tree& other, const CombineOp& op, bool prune = false);
768 #endif
769 
770  /// Like combine(), but with
771  /// @param other a tree of the same type as this tree
772  /// @param op a functor of the form <tt>void op(CombineArgs<ValueType>& args)</tt> that
773  /// computes <tt>args.setResult(f(args.a(), args.b()))</tt> and, optionally,
774  /// <tt>args.setResultIsActive(g(args.aIsActive(), args.bIsActive()))</tt>
775  /// for some functions @c f and @c g
776  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
777  /// more space-efficient than pruning the entire tree in one pass)
778  ///
779  /// This variant passes not only the @em a and @em b values but also the active states
780  /// of the @em a and @em b values to the functor, which may then return, by calling
781  /// @c args.setResultIsActive(), a computed active state for the result value.
782  /// By default, the result is active if either the @em a or the @em b value is active.
783  ///
784  /// @see openvdb/Types.h for the definition of the CombineArgs struct.
785  ///
786  /// @par Example:
787  /// Replace voxel values in floating-point @c aTree with corresponding values
788  /// from floating-point @c bTree (leaving @c bTree empty) wherever the @c bTree
789  /// values are larger. Also, preserve the active states of any transferred values.
790  /// @code
791  /// {
792  /// struct Local {
793  /// static inline void max(CombineArgs<float>& args) {
794  /// if (args.b() > args.a()) {
795  /// // Transfer the B value and its active state.
796  /// args.setResult(args.b());
797  /// args.setResultIsActive(args.bIsActive());
798  /// } else {
799  /// // Preserve the A value and its active state.
800  /// args.setResult(args.a());
801  /// args.setResultIsActive(args.aIsActive());
802  /// }
803  /// }
804  /// };
805  /// aTree.combineExtended(bTree, Local::max);
806  /// }
807  /// @endcode
808  template<typename ExtendedCombineOp>
809  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
810 #ifndef _MSC_VER
811  template<typename ExtendedCombineOp>
812  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
813 #endif
814 
815  /// For a given function @c f, use sparse traversal to compute <tt>f(a, b)</tt> over all
816  /// corresponding pairs of values (tile or voxel) of trees A and B and store the result
817  /// in this tree.
818  /// @param a,b two trees with the same configuration (levels and node dimensions)
819  /// as this tree but with the B tree possibly having a different value type
820  /// @param op a functor of the form <tt>void op(const T1& a, const T2& b, T1& result)</tt>,
821  /// where @c T1 is this tree's and the A tree's @c ValueType and @c T2 is the
822  /// B tree's @c ValueType, that computes <tt>result = f(a, b)</tt>
823  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
824  /// more space-efficient than pruning the entire tree in one pass)
825  ///
826  /// @throw TypeError if the B tree's configuration doesn't match this tree's
827  /// or if this tree's ValueType is not constructible from the B tree's ValueType.
828  ///
829  /// @par Example:
830  /// Compute the per-voxel difference between two floating-point trees,
831  /// @c aTree and @c bTree, and store the result in a third tree.
832  /// @code
833  /// {
834  /// struct Local {
835  /// static inline void diff(const float& a, const float& b, float& result) {
836  /// result = a - b;
837  /// }
838  /// };
839  /// FloatTree resultTree;
840  /// resultTree.combine2(aTree, bTree, Local::diff);
841  /// }
842  /// @endcode
843  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
844  void combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune = false);
845 #ifndef _MSC_VER
846  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
847  void combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune = false);
848 #endif
849 
850  /// Like combine2(), but with
851  /// @param a,b two trees with the same configuration (levels and node dimensions)
852  /// as this tree but with the B tree possibly having a different value type
853  /// @param op a functor of the form <tt>void op(CombineArgs<T1, T2>& args)</tt>, where
854  /// @c T1 is this tree's and the A tree's @c ValueType and @c T2 is the B tree's
855  /// @c ValueType, that computes <tt>args.setResult(f(args.a(), args.b()))</tt>
856  /// and, optionally,
857  /// <tt>args.setResultIsActive(g(args.aIsActive(), args.bIsActive()))</tt>
858  /// for some functions @c f and @c g
859  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
860  /// more space-efficient than pruning the entire tree in one pass)
861  /// This variant passes not only the @em a and @em b values but also the active states
862  /// of the @em a and @em b values to the functor, which may then return, by calling
863  /// <tt>args.setResultIsActive()</tt>, a computed active state for the result value.
864  /// By default, the result is active if either the @em a or the @em b value is active.
865  ///
866  /// @throw TypeError if the B tree's configuration doesn't match this tree's
867  /// or if this tree's ValueType is not constructible from the B tree's ValueType.
868  ///
869  /// @see openvdb/Types.h for the definition of the CombineArgs struct.
870  ///
871  /// @par Example:
872  /// Compute the per-voxel maximum values of two single-precision floating-point trees,
873  /// @c aTree and @c bTree, and store the result in a third tree. Set the active state
874  /// of each output value to that of the larger of the two input values.
875  /// @code
876  /// {
877  /// struct Local {
878  /// static inline void max(CombineArgs<float>& args) {
879  /// if (args.b() > args.a()) {
880  /// // Transfer the B value and its active state.
881  /// args.setResult(args.b());
882  /// args.setResultIsActive(args.bIsActive());
883  /// } else {
884  /// // Preserve the A value and its active state.
885  /// args.setResult(args.a());
886  /// args.setResultIsActive(args.aIsActive());
887  /// }
888  /// }
889  /// };
890  /// FloatTree aTree = ...;
891  /// FloatTree bTree = ...;
892  /// FloatTree resultTree;
893  /// resultTree.combine2Extended(aTree, bTree, Local::max);
894  /// }
895  /// @endcode
896  ///
897  /// @par Example:
898  /// Compute the per-voxel maximum values of a double-precision and a single-precision
899  /// floating-point tree, @c aTree and @c bTree, and store the result in a third,
900  /// double-precision tree. Set the active state of each output value to that of
901  /// the larger of the two input values.
902  /// @code
903  /// {
904  /// struct Local {
905  /// static inline void max(CombineArgs<double, float>& args) {
906  /// if (args.b() > args.a()) {
907  /// // Transfer the B value and its active state.
908  /// args.setResult(args.b());
909  /// args.setResultIsActive(args.bIsActive());
910  /// } else {
911  /// // Preserve the A value and its active state.
912  /// args.setResult(args.a());
913  /// args.setResultIsActive(args.aIsActive());
914  /// }
915  /// }
916  /// };
917  /// DoubleTree aTree = ...;
918  /// FloatTree bTree = ...;
919  /// DoubleTree resultTree;
920  /// resultTree.combine2Extended(aTree, bTree, Local::max);
921  /// }
922  /// @endcode
923  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
924  void combine2Extended(const Tree& a, const OtherTreeType& b, ExtendedCombineOp& op,
925  bool prune = false);
926 #ifndef _MSC_VER
927  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
928  void combine2Extended(const Tree& a, const OtherTreeType& b, const ExtendedCombineOp&,
929  bool prune = false);
930 #endif
931 
932  /// @brief Use sparse traversal to call the given functor with bounding box
933  /// information for all active tiles and leaf nodes or active voxels in the tree.
934  ///
935  /// @note The bounding boxes are guaranteed to be non-overlapping.
936  /// @param op a functor with a templated call operator of the form
937  /// <tt>template<Index LEVEL> void operator()(const CoordBBox& bbox)</tt>,
938  /// where <tt>bbox</tt> is the bounding box of either an active tile
939  /// (if @c LEVEL > 0), a leaf node or an active voxel.
940  /// The functor must also provide a templated method of the form
941  /// <tt>template<Index LEVEL> bool descent()</tt> that returns @c false
942  /// if bounding boxes below the specified tree level are not to be visited.
943  /// In such cases of early tree termination, a bounding box is instead
944  /// derived from each terminating child node.
945  ///
946  /// @par Example:
947  /// Visit and process all active tiles and leaf nodes in a tree, but don't
948  /// descend to the active voxels. The smallest bounding boxes that will be
949  /// visited are those of leaf nodes or level-1 active tiles.
950  /// @code
951  /// {
952  /// struct ProcessTilesAndLeafNodes {
953  /// // Descend to leaf nodes, but no further.
954  /// template<Index LEVEL> inline bool descent() { return LEVEL > 0; }
955  /// // Use this version to descend to voxels:
956  /// //template<Index LEVEL> inline bool descent() { return true; }
957  ///
958  /// template<Index LEVEL>
959  /// inline void operator()(const CoordBBox &bbox) {
960  /// if (LEVEL > 0) {
961  /// // code to process an active tile
962  /// } else {
963  /// // code to process a leaf node
964  /// }
965  /// }
966  /// };
967  /// ProcessTilesAndLeafNodes op;
968  /// aTree.visitActiveBBox(op);
969  /// }
970  /// @endcode
971  /// @see openvdb/unittest/TestTree.cc for another example.
972  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
973 
974  /// Traverse this tree in depth-first order, and at each node call the given functor
975  /// with a @c DenseIterator (see Iterator.h) that points to either a child node or a
976  /// tile value. If the iterator points to a child node and the functor returns true,
977  /// do not descend to the child node; instead, continue the traversal at the next
978  /// iterator position.
979  /// @param op a functor of the form <tt>template<typename IterT> bool op(IterT&)</tt>,
980  /// where @c IterT is either a RootNode::ChildAllIter,
981  /// an InternalNode::ChildAllIter or a LeafNode::ChildAllIter
982  ///
983  /// @note There is no iterator that points to a RootNode, so to visit the root node,
984  /// retrieve the @c parent() of a RootNode::ChildAllIter.
985  ///
986  /// @par Example:
987  /// Print information about the nodes and tiles of a tree, but not individual voxels.
988  /// @code
989  /// namespace {
990  /// template<typename TreeT>
991  /// struct PrintTreeVisitor
992  /// {
993  /// using RootT = typename TreeT::RootNodeType;
994  /// bool visitedRoot;
995  ///
996  /// PrintTreeVisitor(): visitedRoot(false) {}
997  ///
998  /// template<typename IterT>
999  /// inline bool operator()(IterT& iter)
1000  /// {
1001  /// if (!visitedRoot && iter.parent().getLevel() == RootT::LEVEL) {
1002  /// visitedRoot = true;
1003  /// std::cout << "Level-" << RootT::LEVEL << " node" << std::endl;
1004  /// }
1005  /// typename IterT::NonConstValueType value;
1006  /// typename IterT::ChildNodeType* child = iter.probeChild(value);
1007  /// if (child == nullptr) {
1008  /// std::cout << "Tile with value " << value << std::endl;
1009  /// return true; // no child to visit, so stop descending
1010  /// }
1011  /// std::cout << "Level-" << child->getLevel() << " node" << std::endl;
1012  /// return (child->getLevel() == 0); // don't visit leaf nodes
1013  /// }
1014  ///
1015  /// // The generic method, above, calls iter.probeChild(), which is not defined
1016  /// // for LeafNode::ChildAllIter. These overloads ensure that the generic
1017  /// // method template doesn't get instantiated for LeafNode iterators.
1018  /// bool operator()(typename TreeT::LeafNodeType::ChildAllIter&) { return true; }
1019  /// bool operator()(typename TreeT::LeafNodeType::ChildAllCIter&) { return true; }
1020  /// };
1021  /// }
1022  /// {
1023  /// PrintTreeVisitor visitor;
1024  /// tree.visit(visitor);
1025  /// }
1026  /// @endcode
1027  template<typename VisitorOp> void visit(VisitorOp& op);
1028  template<typename VisitorOp> void visit(const VisitorOp& op);
1029 
1030  /// Like visit(), but using @c const iterators, i.e., with
1031  /// @param op a functor of the form <tt>template<typename IterT> bool op(IterT&)</tt>,
1032  /// where @c IterT is either a RootNode::ChildAllCIter,
1033  /// an InternalNode::ChildAllCIter or a LeafNode::ChildAllCIter
1034  template<typename VisitorOp> void visit(VisitorOp& op) const;
1035  template<typename VisitorOp> void visit(const VisitorOp& op) const;
1036 
1037  /// Traverse this tree and another tree in depth-first order, and for corresponding
1038  /// subregions of index space call the given functor with two @c DenseIterators
1039  /// (see Iterator.h), each of which points to either a child node or a tile value
1040  /// of this tree and the other tree. If the A iterator points to a child node
1041  /// and the functor returns a nonzero value with bit 0 set (e.g., 1), do not descend
1042  /// to the child node; instead, continue the traversal at the next A iterator position.
1043  /// Similarly, if the B iterator points to a child node and the functor returns a value
1044  /// with bit 1 set (e.g., 2), continue the traversal at the next B iterator position.
1045  /// @note The other tree must have the same index space and fan-out factors as
1046  /// this tree, but it may have a different @c ValueType and a different topology.
1047  /// @param other a tree of the same type as this tree
1048  /// @param op a functor of the form
1049  /// <tt>template<class AIterT, class BIterT> int op(AIterT&, BIterT&)</tt>,
1050  /// where @c AIterT and @c BIterT are any combination of a
1051  /// RootNode::ChildAllIter, an InternalNode::ChildAllIter or a
1052  /// LeafNode::ChildAllIter with an @c OtherTreeType::RootNode::ChildAllIter,
1053  /// an @c OtherTreeType::InternalNode::ChildAllIter
1054  /// or an @c OtherTreeType::LeafNode::ChildAllIter
1055  ///
1056  /// @par Example:
1057  /// Given two trees of the same type, @c aTree and @c bTree, replace leaf nodes of
1058  /// @c aTree with corresponding leaf nodes of @c bTree, leaving @c bTree partially empty.
1059  /// @code
1060  /// namespace {
1061  /// template<typename AIterT, typename BIterT>
1062  /// inline int stealLeafNodes(AIterT& aIter, BIterT& bIter)
1063  /// {
1064  /// typename AIterT::NonConstValueType aValue;
1065  /// typename AIterT::ChildNodeType* aChild = aIter.probeChild(aValue);
1066  /// typename BIterT::NonConstValueType bValue;
1067  /// typename BIterT::ChildNodeType* bChild = bIter.probeChild(bValue);
1068  ///
1069  /// const Index aLevel = aChild->getLevel(), bLevel = bChild->getLevel();
1070  /// if (aChild && bChild && aLevel == 0 && bLevel == 0) { // both are leaf nodes
1071  /// aIter.setChild(bChild); // give B's child to A
1072  /// bIter.setValue(bValue); // replace B's child with a constant tile value
1073  /// }
1074  /// // Don't iterate over leaf node voxels of either A or B.
1075  /// int skipBranch = (aLevel == 0) ? 1 : 0;
1076  /// if (bLevel == 0) skipBranch = skipBranch | 2;
1077  /// return skipBranch;
1078  /// }
1079  /// }
1080  /// {
1081  /// aTree.visit2(bTree, stealLeafNodes);
1082  /// }
1083  /// @endcode
1084  template<typename OtherTreeType, typename VisitorOp>
1085  void visit2(OtherTreeType& other, VisitorOp& op);
1086  template<typename OtherTreeType, typename VisitorOp>
1087  void visit2(OtherTreeType& other, const VisitorOp& op);
1088 
1089  /// Like visit2(), but using @c const iterators, i.e., with
1090  /// @param other a tree of the same type as this tree
1091  /// @param op a functor of the form
1092  /// <tt>template<class AIterT, class BIterT> int op(AIterT&, BIterT&)</tt>,
1093  /// where @c AIterT and @c BIterT are any combination of a
1094  /// RootNode::ChildAllCIter, an InternalNode::ChildAllCIter
1095  /// or a LeafNode::ChildAllCIter with an
1096  /// @c OtherTreeType::RootNode::ChildAllCIter,
1097  /// an @c OtherTreeType::InternalNode::ChildAllCIter
1098  /// or an @c OtherTreeType::LeafNode::ChildAllCIter
1099  template<typename OtherTreeType, typename VisitorOp>
1100  void visit2(OtherTreeType& other, VisitorOp& op) const;
1101  template<typename OtherTreeType, typename VisitorOp>
1102  void visit2(OtherTreeType& other, const VisitorOp& op) const;
1103 
1104 
1105  //
1106  // Iteration
1107  //
1108  //@{
1109  /// Return an iterator over children of the root node.
1110  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
1111  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
1112  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
1113  //@}
1114 
1115  //@{
1116  /// Return an iterator over non-child entries of the root node's table.
1117  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
1118  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
1119  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
1120  //@}
1121 
1122  //@{
1123  /// Return an iterator over all entries of the root node's table.
1124  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
1125  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
1126  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
1127  //@}
1128 
1129 
1130  //@{
1131  /// Iterator over all nodes in this tree
1134  //@}
1135 
1136  //@{
1137  /// Iterator over all leaf nodes in this tree
1140  //@}
1141 
1142  //@{
1143  /// Return an iterator over all nodes in this tree.
1144  NodeIter beginNode() { return NodeIter(*this); }
1145  NodeCIter beginNode() const { return NodeCIter(*this); }
1146  NodeCIter cbeginNode() const { return NodeCIter(*this); }
1147  //@}
1148 
1149  //@{
1150  /// Return an iterator over all leaf nodes in this tree.
1151  LeafIter beginLeaf() { return LeafIter(*this); }
1152  LeafCIter beginLeaf() const { return LeafCIter(*this); }
1153  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
1154  //@}
1155 
1162 
1163  //@{
1164  /// Return an iterator over all values (tile and voxel) across all nodes.
1166  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
1167  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
1168  //@}
1169  //@{
1170  /// Return an iterator over active values (tile and voxel) across all nodes.
1171  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
1172  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
1173  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
1174  //@}
1175  //@{
1176  /// Return an iterator over inactive values (tile and voxel) across all nodes.
1178  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1179  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1180  //@}
1181 
1182  /// @brief Return an iterator of type @c IterT (for example, begin<ValueOnIter>() is
1183  /// equivalent to beginValueOn()).
1184  template<typename IterT> IterT begin();
1185  /// @brief Return a const iterator of type CIterT (for example, cbegin<ValueOnCIter>()
1186  /// is equivalent to cbeginValueOn()).
1187  template<typename CIterT> CIterT cbegin() const;
1188 
1189 
1190 protected:
1191  using AccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<Tree, true>*, bool>;
1192  using ConstAccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<const Tree, true>*, bool>;
1193 
1194  /// @brief Notify all registered accessors, by calling ValueAccessor::release(),
1195  /// that this tree is about to be deleted.
1196  void releaseAllAccessors();
1197 
1198  // TBB body object used to deallocates nodes in parallel.
1199  template<typename NodeType>
1201  DeallocateNodes(std::vector<NodeType*>& nodes)
1202  : mNodes(nodes.empty() ? nullptr : &nodes.front()) { }
1203  void operator()(const tbb::blocked_range<size_t>& range) const {
1204  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
1205  delete mNodes[n]; mNodes[n] = nullptr;
1206  }
1207  }
1208  NodeType ** const mNodes;
1209  };
1210 
1211  //
1212  // Data members
1213  //
1214  RootNodeType mRoot; // root node of the tree
1217 
1218  static std::unique_ptr<const Name> sTreeTypeName;
1219 }; // end of Tree class
1220 
1221 template<typename _RootNodeType>
1222 std::unique_ptr<const Name> Tree<_RootNodeType>::sTreeTypeName;
1223 
1224 
1225 /// @brief Tree3<T, N1, N2>::Type is the type of a three-level tree
1226 /// (Root, Internal, Leaf) with value type T and
1227 /// internal and leaf node log dimensions N1 and N2, respectively.
1228 /// @note This is NOT the standard tree configuration (Tree4 is).
1229 template<typename T, Index N1=4, Index N2=3>
1230 struct Tree3 {
1232 };
1233 
1234 
1235 /// @brief Tree4<T, N1, N2, N3>::Type is the type of a four-level tree
1236 /// (Root, Internal, Internal, Leaf) with value type T and
1237 /// internal and leaf node log dimensions N1, N2 and N3, respectively.
1238 /// @note This is the standard tree configuration.
1239 template<typename T, Index N1=5, Index N2=4, Index N3=3>
1240 struct Tree4 {
1242 };
1243 
1244 /// @brief Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree
1245 /// (Root, Internal, Internal, Internal, Leaf) with value type T and
1246 /// internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
1247 /// @note This is NOT the standard tree configuration (Tree4 is).
1248 template<typename T, Index N1=6, Index N2=5, Index N3=4, Index N4=3>
1249 struct Tree5 {
1250  using Type =
1252 };
1253 
1254 
1255 ////////////////////////////////////////
1256 
1257 
1258 inline void
1259 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1260 {
1261  int32_t bufferCount;
1262  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1263  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1264 }
1265 
1266 
1267 inline void
1268 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1269 {
1270  int32_t bufferCount = 1;
1271  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1272 }
1273 
1274 
1275 inline void
1276 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1277 {
1278  os << " Tree Type: " << type()
1279  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1280  << " Active tile Count: " << activeTileCount() << std::endl
1281  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1282  << " Leaf Node Count: " << leafCount() << std::endl
1283  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1284 }
1285 
1286 
1287 ////////////////////////////////////////
1288 
1289 
1290 //
1291 // Type traits for tree iterators
1292 //
1293 
1294 /// @brief TreeIterTraits provides, for all tree iterators, a begin(tree) function
1295 /// that returns an iterator over a tree of arbitrary type.
1296 template<typename TreeT, typename IterT> struct TreeIterTraits;
1297 
1298 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1299  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1300  return tree.beginRootChildren();
1301  }
1302 };
1303 
1304 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1305  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1306  return tree.cbeginRootChildren();
1307  }
1308 };
1309 
1310 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1311  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1312  return tree.beginRootTiles();
1313  }
1314 };
1315 
1316 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1317  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1318  return tree.cbeginRootTiles();
1319  }
1320 };
1321 
1322 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1323  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1324  return tree.beginRootDense();
1325  }
1326 };
1327 
1328 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1329  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1330  return tree.cbeginRootDense();
1331  }
1332 };
1333 
1334 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1335  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1336 };
1337 
1338 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1339  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1340 };
1341 
1342 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1343  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1344 };
1345 
1346 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1347  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1348 };
1349 
1350 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1351  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1352 };
1353 
1354 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1355  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1356 };
1357 
1358 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1359  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1360 };
1361 
1362 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1363  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1364 };
1365 
1366 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1367  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1368 };
1369 
1370 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1371  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1372 };
1373 
1374 
1375 template<typename RootNodeType>
1376 template<typename IterT>
1377 inline IterT
1379 {
1380  return TreeIterTraits<Tree, IterT>::begin(*this);
1381 }
1382 
1383 
1384 template<typename RootNodeType>
1385 template<typename IterT>
1386 inline IterT
1388 {
1389  return TreeIterTraits<Tree, IterT>::begin(*this);
1390 }
1391 
1392 
1393 ////////////////////////////////////////
1394 
1395 
1396 template<typename RootNodeType>
1397 void
1398 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1399 {
1400  this->clearAllAccessors();
1401  TreeBase::readTopology(is, saveFloatAsHalf);
1402  mRoot.readTopology(is, saveFloatAsHalf);
1403 }
1404 
1405 
1406 template<typename RootNodeType>
1407 void
1408 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1409 {
1410  TreeBase::writeTopology(os, saveFloatAsHalf);
1411  mRoot.writeTopology(os, saveFloatAsHalf);
1412 }
1413 
1414 
1415 template<typename RootNodeType>
1416 inline void
1417 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1418 {
1419  this->clearAllAccessors();
1420  mRoot.readBuffers(is, saveFloatAsHalf);
1421 }
1422 
1423 
1424 template<typename RootNodeType>
1425 inline void
1426 Tree<RootNodeType>::readBuffers(std::istream &is, const CoordBBox& bbox, bool saveFloatAsHalf)
1427 {
1428  this->clearAllAccessors();
1429  mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1430 }
1431 
1432 
1433 template<typename RootNodeType>
1434 inline void
1436 {
1437  for (LeafCIter it = this->cbeginLeaf(); it; ++it) {
1438  // Retrieving the value of a leaf voxel forces loading of the leaf node's voxel buffer.
1439  it->getValue(Index(0));
1440  }
1441 }
1442 
1443 
1444 template<typename RootNodeType>
1445 inline void
1446 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1447 {
1448  mRoot.writeBuffers(os, saveFloatAsHalf);
1449 }
1450 
1451 
1452 template<typename RootNodeType>
1453 inline void
1455 {
1456  std::vector<LeafNodeType*> leafnodes;
1457  this->stealNodes(leafnodes);
1458 
1459  tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
1460  DeallocateNodes<LeafNodeType>(leafnodes));
1461 
1462  std::vector<typename RootNodeType::ChildNodeType*> internalNodes;
1463  this->stealNodes(internalNodes);
1464 
1465  tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
1467 
1468  mRoot.clear();
1469 
1470  this->clearAllAccessors();
1471 }
1472 
1473 
1474 ////////////////////////////////////////
1475 
1476 
1477 template<typename RootNodeType>
1478 inline void
1480 {
1481  typename AccessorRegistry::accessor a;
1482  mAccessorRegistry.insert(a, &accessor);
1483 }
1484 
1485 
1486 template<typename RootNodeType>
1487 inline void
1489 {
1490  typename ConstAccessorRegistry::accessor a;
1491  mConstAccessorRegistry.insert(a, &accessor);
1492 }
1493 
1494 
1495 template<typename RootNodeType>
1496 inline void
1498 {
1499  mAccessorRegistry.erase(&accessor);
1500 }
1501 
1502 
1503 template<typename RootNodeType>
1504 inline void
1506 {
1507  mConstAccessorRegistry.erase(&accessor);
1508 }
1509 
1510 
1511 template<typename RootNodeType>
1512 inline void
1514 {
1515  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1516  it != mAccessorRegistry.end(); ++it)
1517  {
1518  if (it->first) it->first->clear();
1519  }
1520 
1521  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1522  it != mConstAccessorRegistry.end(); ++it)
1523  {
1524  if (it->first) it->first->clear();
1525  }
1526 }
1527 
1528 
1529 template<typename RootNodeType>
1530 inline void
1532 {
1533  mAccessorRegistry.erase(nullptr);
1534  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1535  it != mAccessorRegistry.end(); ++it)
1536  {
1537  it->first->release();
1538  }
1539  mAccessorRegistry.clear();
1540 
1541  mAccessorRegistry.erase(nullptr);
1542  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1543  it != mConstAccessorRegistry.end(); ++it)
1544  {
1545  it->first->release();
1546  }
1547  mConstAccessorRegistry.clear();
1548 }
1549 
1550 
1551 ////////////////////////////////////////
1552 
1553 
1554 template<typename RootNodeType>
1555 inline const typename RootNodeType::ValueType&
1556 Tree<RootNodeType>::getValue(const Coord& xyz) const
1557 {
1558  return mRoot.getValue(xyz);
1559 }
1560 
1561 
1562 template<typename RootNodeType>
1563 template<typename AccessT>
1564 inline const typename RootNodeType::ValueType&
1565 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1566 {
1567  return accessor.getValue(xyz);
1568 }
1569 
1570 
1571 template<typename RootNodeType>
1572 inline int
1573 Tree<RootNodeType>::getValueDepth(const Coord& xyz) const
1574 {
1575  return mRoot.getValueDepth(xyz);
1576 }
1577 
1578 
1579 template<typename RootNodeType>
1580 inline void
1582 {
1583  mRoot.setValueOff(xyz);
1584 }
1585 
1586 
1587 template<typename RootNodeType>
1588 inline void
1590 {
1591  mRoot.setValueOff(xyz, value);
1592 }
1593 
1594 
1595 template<typename RootNodeType>
1596 inline void
1597 Tree<RootNodeType>::setActiveState(const Coord& xyz, bool on)
1598 {
1599  mRoot.setActiveState(xyz, on);
1600 }
1601 
1602 
1603 template<typename RootNodeType>
1604 inline void
1606 {
1607  mRoot.setValueOn(xyz, value);
1608 }
1609 
1610 template<typename RootNodeType>
1611 inline void
1613 {
1614  mRoot.setValueOnly(xyz, value);
1615 }
1616 
1617 template<typename RootNodeType>
1618 template<typename AccessT>
1619 inline void
1620 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1621 {
1622  accessor.setValue(xyz, value);
1623 }
1624 
1625 
1626 template<typename RootNodeType>
1627 inline void
1629 {
1630  mRoot.setActiveState(xyz, true);
1631 }
1632 
1633 
1634 template<typename RootNodeType>
1635 inline void
1637 {
1638  mRoot.setValueOn(xyz, value);
1639 }
1640 
1641 
1642 template<typename RootNodeType>
1643 template<typename ModifyOp>
1644 inline void
1645 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1646 {
1647  mRoot.modifyValue(xyz, op);
1648 }
1649 
1650 
1651 template<typename RootNodeType>
1652 template<typename ModifyOp>
1653 inline void
1654 Tree<RootNodeType>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1655 {
1656  mRoot.modifyValueAndActiveState(xyz, op);
1657 }
1658 
1659 
1660 template<typename RootNodeType>
1661 inline bool
1663 {
1664  return mRoot.probeValue(xyz, value);
1665 }
1666 
1667 
1668 ////////////////////////////////////////
1669 
1670 
1671 template<typename RootNodeType>
1672 inline void
1674  const ValueType& value, bool active)
1675 {
1676  mRoot.addTile(level, xyz, value, active);
1677 }
1678 
1679 
1680 template<typename RootNodeType>
1681 template<typename NodeT>
1682 inline NodeT*
1683 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1684 {
1685  this->clearAllAccessors();
1686  return mRoot.template stealNode<NodeT>(xyz, value, active);
1687 }
1688 
1689 
1690 template<typename RootNodeType>
1691 inline typename RootNodeType::LeafNodeType*
1693 {
1694  return mRoot.touchLeaf(xyz);
1695 }
1696 
1697 
1698 template<typename RootNodeType>
1699 inline typename RootNodeType::LeafNodeType*
1701 {
1702  return mRoot.probeLeaf(xyz);
1703 }
1704 
1705 
1706 template<typename RootNodeType>
1707 inline const typename RootNodeType::LeafNodeType*
1708 Tree<RootNodeType>::probeConstLeaf(const Coord& xyz) const
1709 {
1710  return mRoot.probeConstLeaf(xyz);
1711 }
1712 
1713 
1714 template<typename RootNodeType>
1715 template<typename NodeType>
1716 inline NodeType*
1718 {
1719  return mRoot.template probeNode<NodeType>(xyz);
1720 }
1721 
1722 
1723 template<typename RootNodeType>
1724 template<typename NodeType>
1725 inline const NodeType*
1726 Tree<RootNodeType>::probeNode(const Coord& xyz) const
1727 {
1728  return this->template probeConstNode<NodeType>(xyz);
1729 }
1730 
1731 
1732 template<typename RootNodeType>
1733 template<typename NodeType>
1734 inline const NodeType*
1735 Tree<RootNodeType>::probeConstNode(const Coord& xyz) const
1736 {
1737  return mRoot.template probeConstNode<NodeType>(xyz);
1738 }
1739 
1740 
1741 ////////////////////////////////////////
1742 
1743 
1744 template<typename RootNodeType>
1745 inline void
1746 Tree<RootNodeType>::clip(const CoordBBox& bbox)
1747 {
1748  this->clearAllAccessors();
1749  return mRoot.clip(bbox);
1750 }
1751 
1752 
1753 template<typename RootNodeType>
1754 inline void
1756 {
1757  this->clearAllAccessors();
1758  for (LeafIter it = this->beginLeaf(); it; ) {
1759  const LeafNodeType* leaf = it.getLeaf();
1760  ++it; // advance the iterator before deleting the leaf node
1761  if (!leaf->isAllocated()) {
1762  this->addTile(/*level=*/0, leaf->origin(), this->background(), /*active=*/false);
1763  }
1764  }
1765 }
1766 
1767 template<typename RootNodeType>
1768 inline Index32
1770 {
1771  Index32 sum = 0;
1772  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
1773  return sum;
1774 }
1775 
1776 
1777 template<typename RootNodeType>
1778 inline void
1779 Tree<RootNodeType>::sparseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1780 {
1781  this->clearAllAccessors();
1782  return mRoot.sparseFill(bbox, value, active);
1783 }
1784 
1785 
1786 template<typename RootNodeType>
1787 inline void
1788 Tree<RootNodeType>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1789 {
1790  this->clearAllAccessors();
1791  return mRoot.denseFill(bbox, value, active);
1792 }
1793 
1794 
1795 template<typename RootNodeType>
1796 inline void
1798 {
1799  this->clearAllAccessors();
1800  mRoot.voxelizeActiveTiles(threaded);
1801 }
1802 
1803 
1804 template<typename RootNodeType>
1807 {
1809  if (Metadata::isRegisteredType(valueType())) {
1810  using MetadataT = TypedMetadata<ValueType>;
1811  result = Metadata::createMetadata(valueType());
1812  if (result->typeName() == MetadataT::staticTypeName()) {
1813  MetadataT* m = static_cast<MetadataT*>(result.get());
1814  m->value() = mRoot.background();
1815  }
1816  }
1817  return result;
1818 }
1819 
1820 
1821 ////////////////////////////////////////
1822 
1823 
1824 template<typename RootNodeType>
1825 inline void
1827 {
1828  this->clearAllAccessors();
1829  other.clearAllAccessors();
1830  switch (policy) {
1831  case MERGE_ACTIVE_STATES:
1832  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1833  case MERGE_NODES:
1834  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1836  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1837  }
1838 }
1839 
1840 
1841 template<typename RootNodeType>
1842 template<typename OtherRootNodeType>
1843 inline void
1845 {
1846  this->clearAllAccessors();
1847  mRoot.topologyUnion(other.root());
1848 }
1849 
1850 template<typename RootNodeType>
1851 template<typename OtherRootNodeType>
1852 inline void
1854 {
1855  this->clearAllAccessors();
1856  mRoot.topologyIntersection(other.root());
1857 }
1858 
1859 template<typename RootNodeType>
1860 template<typename OtherRootNodeType>
1861 inline void
1863 {
1864  this->clearAllAccessors();
1865  mRoot.topologyDifference(other.root());
1866 }
1867 
1868 ////////////////////////////////////////
1869 
1870 
1871 /// @brief Helper class to adapt a three-argument (a, b, result) CombineOp functor
1872 /// into a single-argument functor that accepts a CombineArgs struct
1873 template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1875 {
1876  CombineOpAdapter(CombineOp& _op): op(_op) {}
1877 
1879  op(args.a(), args.b(), args.result());
1880  }
1881 
1882  CombineOp& op;
1883 };
1884 
1885 
1886 template<typename RootNodeType>
1887 template<typename CombineOp>
1888 inline void
1889 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1890 {
1892  this->combineExtended(other, extendedOp, prune);
1893 }
1894 
1895 
1896 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1897 /// code like this: <tt>aTree.combine(bTree, MyCombineOp(...))</tt>.
1898 #ifndef _MSC_VER
1899 template<typename RootNodeType>
1900 template<typename CombineOp>
1901 inline void
1902 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1903 {
1905  this->combineExtended(other, extendedOp, prune);
1906 }
1907 #endif
1908 
1909 
1910 template<typename RootNodeType>
1911 template<typename ExtendedCombineOp>
1912 inline void
1913 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1914 {
1915  this->clearAllAccessors();
1916  mRoot.combine(other.root(), op, prune);
1917 }
1918 
1919 
1920 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1921 /// code like this: <tt>aTree.combineExtended(bTree, MyCombineOp(...))</tt>.
1922 #ifndef _MSC_VER
1923 template<typename RootNodeType>
1924 template<typename ExtendedCombineOp>
1925 inline void
1926 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1927 {
1928  this->clearAllAccessors();
1929  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1930 }
1931 #endif
1932 
1933 
1934 template<typename RootNodeType>
1935 template<typename CombineOp, typename OtherTreeType>
1936 inline void
1937 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1938 {
1940  this->combine2Extended(a, b, extendedOp, prune);
1941 }
1942 
1943 
1944 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1945 /// code like this: <tt>tree.combine2(aTree, bTree, MyCombineOp(...))</tt>.
1946 #ifndef _MSC_VER
1947 template<typename RootNodeType>
1948 template<typename CombineOp, typename OtherTreeType>
1949 inline void
1950 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1951 {
1953  this->combine2Extended(a, b, extendedOp, prune);
1954 }
1955 #endif
1956 
1957 
1958 template<typename RootNodeType>
1959 template<typename ExtendedCombineOp, typename OtherTreeType>
1960 inline void
1961 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1962  ExtendedCombineOp& op, bool prune)
1963 {
1964  this->clearAllAccessors();
1965  mRoot.combine2(a.root(), b.root(), op, prune);
1966 }
1967 
1968 
1969 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1970 /// code like the following, where the functor argument is a temporary:
1971 /// <tt>tree.combine2Extended(aTree, bTree, MyCombineOp(...))</tt>.
1972 #ifndef _MSC_VER
1973 template<typename RootNodeType>
1974 template<typename ExtendedCombineOp, typename OtherTreeType>
1975 inline void
1976 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1977  const ExtendedCombineOp& op, bool prune)
1978 {
1979  this->clearAllAccessors();
1980  mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
1981 }
1982 #endif
1983 
1984 
1985 ////////////////////////////////////////
1986 
1987 
1988 template<typename RootNodeType>
1989 template<typename VisitorOp>
1990 inline void
1992 {
1993  this->clearAllAccessors();
1994  mRoot.template visit<VisitorOp>(op);
1995 }
1996 
1997 
1998 template<typename RootNodeType>
1999 template<typename VisitorOp>
2000 inline void
2001 Tree<RootNodeType>::visit(VisitorOp& op) const
2002 {
2003  mRoot.template visit<VisitorOp>(op);
2004 }
2005 
2006 
2007 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
2008 /// code like this: <tt>tree.visit(MyVisitorOp(...))</tt>.
2009 template<typename RootNodeType>
2010 template<typename VisitorOp>
2011 inline void
2012 Tree<RootNodeType>::visit(const VisitorOp& op)
2013 {
2014  this->clearAllAccessors();
2015  mRoot.template visit<const VisitorOp>(op);
2016 }
2017 
2018 
2019 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
2020 /// code like this: <tt>tree.visit(MyVisitorOp(...))</tt>.
2021 template<typename RootNodeType>
2022 template<typename VisitorOp>
2023 inline void
2024 Tree<RootNodeType>::visit(const VisitorOp& op) const
2025 {
2026  mRoot.template visit<const VisitorOp>(op);
2027 }
2028 
2029 
2030 ////////////////////////////////////////
2031 
2032 
2033 template<typename RootNodeType>
2034 template<typename OtherTreeType, typename VisitorOp>
2035 inline void
2036 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
2037 {
2038  this->clearAllAccessors();
2039  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2040  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
2041 }
2042 
2043 
2044 template<typename RootNodeType>
2045 template<typename OtherTreeType, typename VisitorOp>
2046 inline void
2047 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
2048 {
2049  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2050  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
2051 }
2052 
2053 
2054 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
2055 /// code like this: <tt>aTree.visit2(bTree, MyVisitorOp(...))</tt>.
2056 template<typename RootNodeType>
2057 template<typename OtherTreeType, typename VisitorOp>
2058 inline void
2059 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
2060 {
2061  this->clearAllAccessors();
2062  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2063  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2064 }
2065 
2066 
2067 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
2068 /// code like this: <tt>aTree.visit2(bTree, MyVisitorOp(...))</tt>.
2069 template<typename RootNodeType>
2070 template<typename OtherTreeType, typename VisitorOp>
2071 inline void
2072 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
2073 {
2074  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2075  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2076 }
2077 
2078 
2079 ////////////////////////////////////////
2080 
2081 
2082 template<typename RootNodeType>
2083 inline const Name&
2085 {
2086  static std::once_flag once;
2087  std::call_once(once, []()
2088  {
2089  std::vector<Index> dims;
2090  Tree::getNodeLog2Dims(dims);
2091  std::ostringstream ostr;
2092  ostr << "Tree_" << typeNameAsString<BuildType>();
2093  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
2094  ostr << "_" << dims[i];
2095  }
2096  sTreeTypeName.reset(new Name(ostr.str()));
2097  });
2098  return *sTreeTypeName;
2099 }
2100 
2101 
2102 template<typename RootNodeType>
2103 template<typename OtherRootNodeType>
2104 inline bool
2106 {
2107  return mRoot.hasSameTopology(other.root());
2108 }
2109 
2110 
2111 template<typename RootNodeType>
2112 Index64
2114 {
2115  Coord dim(0, 0, 0);
2116  this->evalActiveVoxelDim(dim);
2117  const Index64
2118  totalVoxels = dim.x() * dim.y() * dim.z(),
2119  activeVoxels = this->activeVoxelCount();
2120  assert(totalVoxels >= activeVoxels);
2121  return totalVoxels - activeVoxels;
2122 }
2123 
2124 
2125 template<typename RootNodeType>
2126 inline bool
2128 {
2129  bbox.reset(); // default invalid bbox
2130 
2131  if (this->empty()) return false; // empty
2132 
2133  mRoot.evalActiveBoundingBox(bbox, false);
2134 
2135  return !bbox.empty();
2136 }
2137 
2138 template<typename RootNodeType>
2139 inline bool
2141 {
2142  bbox.reset(); // default invalid bbox
2143 
2144  if (this->empty()) return false; // empty
2145 
2146  mRoot.evalActiveBoundingBox(bbox, true);
2147 
2148  return !bbox.empty();
2149 }
2150 
2151 
2152 template<typename RootNodeType>
2153 inline bool
2155 {
2156  CoordBBox bbox;
2157  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
2158  dim = bbox.extents();
2159  return notEmpty;
2160 }
2161 
2162 
2163 template<typename RootNodeType>
2164 inline bool
2166 {
2167  CoordBBox bbox;
2168  bool notEmpty = this->evalLeafBoundingBox(bbox);
2169  dim = bbox.extents();
2170  return notEmpty;
2171 }
2172 
2173 
2174 template<typename RootNodeType>
2175 inline void
2177 {
2178  /// @todo optimize
2179  minVal = maxVal = zeroVal<ValueType>();
2180  if (ValueOnCIter iter = this->cbeginValueOn()) {
2181  minVal = maxVal = *iter;
2182  for (++iter; iter; ++iter) {
2183  const ValueType& val = *iter;
2184  if (val < minVal) minVal = val;
2185  if (val > maxVal) maxVal = val;
2186  }
2187  }
2188 }
2189 
2190 
2191 template<typename RootNodeType>
2192 inline void
2193 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
2194 {
2195  dims.clear();
2196  RootNodeType::getNodeLog2Dims(dims);
2197 }
2198 
2199 
2200 template<typename RootNodeType>
2201 inline void
2202 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
2203 {
2204  if (verboseLevel <= 0) return;
2205 
2206  /// @todo Consider using hboost::io::ios_precision_saver instead.
2207  struct OnExit {
2208  std::ostream& os;
2209  std::streamsize savedPrecision;
2210  OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
2211  ~OnExit() { os.precision(savedPrecision); }
2212  };
2213  OnExit restorePrecision(os);
2214 
2215  std::vector<Index> dims;
2216  Tree::getNodeLog2Dims(dims);// leaf is the last element
2217 
2218  os << "Information about Tree:\n"
2219  << " Type: " << this->type() << "\n";
2220 
2221  os << " Configuration:\n";
2222 
2223  if (verboseLevel <= 1) {
2224  // Print node types and sizes.
2225  os << " Root(" << mRoot.getTableSize() << ")";
2226  if (dims.size() > 1) {
2227  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2228  os << ", Internal(" << (1 << dims[i]) << "^3)";
2229  }
2230  os << ", Leaf(" << (1 << dims.back()) << "^3)\n";
2231  }
2232  os << " Background value: " << mRoot.background() << "\n";
2233  return;
2234  }
2235 
2236  // The following is tree information that is expensive to extract.
2237 
2238  ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
2239  if (verboseLevel > 3) {
2240  // This forces loading of all non-resident nodes.
2241  this->evalMinMax(minVal, maxVal);
2242  }
2243 
2244 #if OPENVDB_ABI_VERSION_NUMBER >= 7
2245  const auto nodeCount = this->nodeCount();//fast
2246  const Index32 leafCount = nodeCount.front();// leaf is the first element
2247 #else
2248  std::vector<Index64> nodeCount(dims.size());
2249  for (NodeCIter it = cbeginNode(); it; ++it) ++(nodeCount[it.getDepth()]);//slow
2250  const Index64 leafCount = *nodeCount.rbegin();// leaf is the last element
2251 #endif
2252  assert(dims.size() == nodeCount.size());
2253 
2254  Index64 totalNodeCount = 0;
2255  for (size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
2256 
2257  // Print node types, counts and sizes.
2258  os << " Root(1 x " << mRoot.getTableSize() << ")";
2259  if (dims.size() >= 2) {
2260  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2261 #if OPENVDB_ABI_VERSION_NUMBER >= 7
2262  os << ", Internal(" << util::formattedInt(nodeCount[N - i]);
2263 #else
2264  os << ", Internal(" << util::formattedInt(nodeCount[i]);
2265 #endif
2266  os << " x " << (1 << dims[i]) << "^3)";
2267  }
2268  os << ", Leaf(" << util::formattedInt(leafCount);
2269  os << " x " << (1 << dims.back()) << "^3)\n";
2270  }
2271  os << " Background value: " << mRoot.background() << "\n";
2272 
2273  // Statistics of topology and values
2274 
2275  if (verboseLevel > 3) {
2276  os << " Min value: " << minVal << "\n";
2277  os << " Max value: " << maxVal << "\n";
2278  }
2279 
2280  const Index64
2281  numActiveVoxels = this->activeVoxelCount(),
2282  numActiveLeafVoxels = this->activeLeafVoxelCount(),
2283  numActiveTiles = this->activeTileCount();
2284 
2285  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
2286  os << " Number of active tiles: " << util::formattedInt(numActiveTiles) << "\n";
2287 
2288  Coord dim(0, 0, 0);
2289  Index64 totalVoxels = 0;
2290  if (numActiveVoxels) { // nonempty
2291  CoordBBox bbox;
2292  this->evalActiveVoxelBoundingBox(bbox);
2293  dim = bbox.extents();
2294  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2295 
2296  os << " Bounding box of active voxels: " << bbox << "\n";
2297  os << " Dimensions of active voxels: "
2298  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
2299 
2300  const double activeRatio = (100.0 * double(numActiveVoxels)) / double(totalVoxels);
2301  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2302 
2303  if (leafCount > 0) {
2304  const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2305  / (double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2306  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2307  }
2308 
2309  if (verboseLevel > 2) {
2310  Index64 sum = 0;// count the number of unallocated leaf nodes
2311  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
2312  os << " Number of unallocated nodes: "
2313  << util::formattedInt(sum) << " ("
2314  << (100.0 * double(sum) / double(totalNodeCount)) << "%)\n";
2315  }
2316  } else {
2317  os << " Tree is empty!\n";
2318  }
2319  os << std::flush;
2320 
2321  if (verboseLevel == 2) return;
2322 
2323  // Memory footprint in bytes
2324  const Index64
2325  actualMem = this->memUsage(),
2326  denseMem = sizeof(ValueType) * totalVoxels,
2327  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2328  ///< @todo not accurate for BoolTree (and probably should count tile values)
2329 
2330  os << "Memory footprint:\n";
2331  util::printBytes(os, actualMem, " Actual: ");
2332  util::printBytes(os, voxelsMem, " Active leaf voxels: ");
2333 
2334  if (numActiveVoxels) {
2335  util::printBytes(os, denseMem, " Dense equivalent: ");
2336  os << " Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2337  << "% of an equivalent dense volume\n";
2338  os << " Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2339  << "% of actual footprint\n";
2340  }
2341 }
2342 
2343 } // namespace tree
2344 } // namespace OPENVDB_VERSION_NAME
2345 } // namespace openvdb
2346 
2347 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
virtual Index64 activeTileCount() const =0
Return the total number of active tiles.
const AValueType & result() const
Get the output value.
Definition: Types.h:976
tbb::concurrent_hash_map< ValueAccessorBase< Tree, true > *, bool > AccessorRegistry
Definition: Tree.h:1191
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOnCIter > ValueOnCIter
Definition: Tree.h:1159
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1259
ValueOffIter beginValueOff()
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1177
void releaseAccessor(ValueAccessorBase< Tree, true > &) const
Deregister an accessor so that it is no longer automatically cleared.
Definition: Tree.h:1497
bool operator==(const Tree &) const
Definition: Tree.h:273
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
void visit2(OtherTreeType &other, VisitorOp &op)
Definition: Tree.h:2036
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1268
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
Definition: parallel.h:153
bool hasSameTopology(const Tree< OtherRootNodeType > &other) const
Return true if the given tree has the same node and active value topology as this tree...
Definition: Tree.h:2105
GLenum GLint * range
Definition: glew.h:3500
Definition: ImfName.h:54
void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const override
Write out all data buffers for this tree.
Definition: Tree.h:1446
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:931
Index64 inactiveVoxelCount() const override
Return the number of inactive voxels within the bounding box of all active voxels.
Definition: Tree.h:2113
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: Tree.h:1628
#define OPENVDB_LOG_WARN(mesg)
Definition: logging.h:274
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:131
LeafIteratorBase< Tree, typename RootNodeType::ChildOnIter > LeafIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1138
hboost::math::policies::policy< hboost::math::policies::domain_error< hboost::math::policies::ignore_error >, hboost::math::policies::pole_error< hboost::math::policies::ignore_error >, hboost::math::policies::overflow_error< hboost::math::policies::ignore_error >, hboost::math::policies::underflow_error< hboost::math::policies::ignore_error >, hboost::math::policies::denorm_error< hboost::math::policies::ignore_error >, hboost::math::policies::rounding_error< hboost::math::policies::ignore_error >, hboost::math::policies::evaluation_error< hboost::math::policies::ignore_error >, hboost::math::policies::indeterminate_result_error< hboost::math::policies::ignore_error > > policy
Definition: SYS_MathCbrt.h:35
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: Tree.h:476
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Definition: Tree.h:607
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1153
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1654
void voxelizeActiveTiles(bool threaded=true)
Densify active tiles, i.e., replace them with leaf-level active voxels.
Definition: Tree.h:1797
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...
Definition: Tree.h:1645
virtual Metadata::Ptr getBackgroundValue() const
Return this tree's background value wrapped as metadata.
Definition: Tree.h:60
void attachAccessor(ValueAccessorBase< Tree, false > &) const
Dummy implementations.
Definition: Tree.h:635
static const Name & treeType()
Return the name of this type of tree.
Definition: Tree.h:2084
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOnIter > ValueOnIter
Definition: Tree.h:1158
FMT_CONSTEXPR auto begin(const C &c) -> decltype(c.begin())
Definition: format.h:251
const Args & args
Definition: printf.h:628
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: Tree.h:516
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1118
static Metadata::Ptr createMetadata(const Name &typeName)
Create new metadata of the given type.
void stealNodes(ArrayT &array)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: Tree.h:605
GLuint const GLfloat * val
Definition: glew.h:2794
void addTile(Index level, const Coord &xyz, const ValueType &value, bool active)
Add a tile containing voxel (x, y, z) at the specified tree level, creating a new branch if necessary...
Definition: Tree.h:1673
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: Tree.h:1573
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1296
void sparseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: Tree.h:1779
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:935
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1166
DeallocateNodes(std::vector< NodeType * > &nodes)
Definition: Tree.h:1201
RootNodeType::ChildOffCIter beginRootTiles() const
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1117
NodeIteratorBase< Tree, typename RootNodeType::ChildOnIter > NodeIter
Iterator over all nodes in this tree.
Definition: Tree.h:1132
Tree(const OtherTreeType &other, const ValueType &inactiveValue, const ValueType &activeValue, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:230
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1125
RootNodeType & root()
Return this tree's root node.
Definition: Tree.h:278
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:166
const GLdouble * m
Definition: glew.h:9124
virtual Index64 activeVoxelCount() const =0
Return the total number of active voxels.
tree::TreeBase TreeBase
Definition: Grid.h:26
TreeValueIteratorBase< Tree, typename RootNodeType::ValueAllIter > ValueAllIter
Definition: Tree.h:1156
virtual Index32 leafCount() const =0
Return the number of leaf nodes.
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueAllCIter > ValueAllCIter
Definition: Tree.h:1157
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:258
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:450
Index32 unallocatedLeafCount() const override
Return the total number of unallocated leaf nodes residing in this tree.
Definition: Tree.h:1769
void readNonresidentBuffers() const override
Read all of this tree's data buffers that are not yet resident in memory (because delayed loading is ...
Definition: Tree.h:1435
void clip(const CoordBBox &)
Set all voxels that lie outside the given axis-aligned box to the background.
Definition: Tree.h:1746
Index64 memUsage() const override
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:365
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1179
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1119
bool operator!=(const Tree &) const
Definition: Tree.h:274
void topologyIntersection(const Tree< OtherRootNodeType > &other)
Intersects this tree's set of active values with the active values of the other tree, whose ValueType may be different.
Definition: Tree.h:1853
void releaseAllAccessors()
Notify all registered accessors, by calling ValueAccessor::release(), that this tree is about to be d...
Definition: Tree.h:1531
virtual Index64 inactiveVoxelCount() const =0
Return the number of inactive voxels within the bounding box of all active voxels.
Tree4<T, N1, N2, N3>::Type is the type of a four-level tree (Root, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2 and N3, respectively.
Definition: Tree.h:1240
bool evalActiveVoxelBoundingBox(CoordBBox &bbox) const override
Return in bbox the axis-aligned bounding box of all active voxels and tiles.
Definition: Tree.h:2140
ValueAllIter beginValueAll()
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1165
Tree & operator=(const Tree &)=delete
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: Tree.h:1581
std::shared_ptr< T > SharedPtr
Definition: Types.h:91
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:1454
void topologyDifference(const Tree< OtherRootNodeType > &other)
Difference this tree's set of active values with the active values of the other tree, whose ValueType may be different. So a resulting voxel will be active only if the original voxel is active in this tree and inactive in the other tree.
Definition: Tree.h:1862
SYS_FORCE_INLINE const_iterator end() const
const AValueType & a() const
Get the A input value.
Definition: Types.h:971
static bool isRegisteredType(const Name &typeName)
Return true if the given type is known by the metadata type registry.
RootNodeType::ChildOnCIter beginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1110
Name valueType() const override
Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
Definition: Tree.h:266
Utility routines to output nicely-formatted numeric values.
void readBuffers(std::istream &, bool saveFloatAsHalf=false) override
Read all data buffers for this tree.
Definition: Tree.h:1417
const ValueType & background() const
Return this tree's background value.
Definition: Tree.h:660
tbb::concurrent_hash_map< ValueAccessorBase< const Tree, true > *, bool > ConstAccessorRegistry
Definition: Tree.h:1192
#define OPENVDB_API
Helper macros for defining library symbol visibility.
Definition: Platform.h:230
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1152
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:577
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1878
void print(std::ostream &os=std::cout, int verboseLevel=1) const override
Print statistics, memory usage and other information about this tree.
Definition: Tree.h:2202
void merge(Tree &other, MergePolicy=MERGE_ACTIVE_STATES)
Efficiently merge another tree into this tree using one of several schemes.
Definition: Tree.h:1826
Index64 activeTileCount() const override
Return the total number of active tiles.
Definition: Tree.h:360
Templated metadata class to hold specific types.
Definition: Metadata.h:121
LeafIter beginLeaf()
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1151
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
TreeBase::Ptr copy() const override
Return a pointer to a deep copy of this tree.
Definition: Tree.h:263
Index64 activeLeafVoxelCount() const override
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:352
void releaseAccessor(ValueAccessorBase< Tree, false > &) const
Dummy implementations.
Definition: Tree.h:647
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1139
Index32 leafCount() const override
Return the number of leaf nodes.
Definition: Tree.h:337
void attachAccessor(ValueAccessorBase< Tree, true > &) const
Register an accessor for this tree. Registered accessors are automatically cleared whenever one of th...
Definition: Tree.h:1479
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1145
bool evalActiveVoxelDim(Coord &dim) const override
Return in dim the dimensions of the axis-aligned bounding box of all active voxels. This is a tighter bounding box than the leaf node bounding box.
Definition: Tree.h:2154
ValueConverter<T>::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:194
GLsizei n
Definition: glew.h:4040
const RootNodeType & root() const
Return this tree's root node.
Definition: Tree.h:279
Tree3<T, N1, N2>::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1230
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1874
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1662
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1178
const NodeType * probeConstNode(const Coord &xyz) const
Return a pointer to the node of type NodeType that contains voxel (x, y, z). If no such node exists...
Definition: Tree.h:1735
Index64 inactiveLeafVoxelCount() const override
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:354
const LeafNodeType * probeLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:551
void attachAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:636
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Tree.h:1203
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:84
void getNodes(ArrayT &array) const
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:578
bool evalLeafBoundingBox(CoordBBox &bbox) const override
Return in bbox the axis-aligned bounding box of all active tiles and leaf nodes with active values...
Definition: Tree.h:2127
typename RootNodeType::ValueType ValueType
Definition: Tree.h:181
NodeIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > NodeCIter
Iterator over all nodes in this tree.
Definition: Tree.h:1133
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOffIter > ValueOffIter
Definition: Tree.h:1160
The root node of an OpenVDB tree.
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:452
void releaseAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:648
void evalMinMax(ValueType &min, ValueType &max) const
Return the minimum and maximum active values in this tree.
Definition: Tree.h:2176
CIterT cbegin() const
Return a const iterator of type CIterT (for example, cbegin<ValueOnCIter>() is equivalent to cbeginVa...
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1167
Base class for typed trees.
Definition: Tree.h:35
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
void topologyUnion(const Tree< OtherRootNodeType > &other)
Union this tree's set of active values with the active values of the other tree, whose ValueType may ...
Definition: Tree.h:1844
Index64 activeVoxelCount() const override
Return the total number of active voxels.
Definition: Tree.h:356
Index32 nonLeafCount() const override
Return the number of non-leaf nodes.
Definition: Tree.h:350
virtual Index32 nonLeafCount() const =0
Return the number of non-leaf nodes.
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOffCIter > ValueOffCIter
Definition: Tree.h:1161
static void getNodeLog2Dims(std::vector< Index > &dims)
Traverse the type hierarchy of nodes, and return, in dims, a list of the Log2Dims of nodes in order f...
Definition: Tree.h:2193
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1556
typename RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:183
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:204
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1216
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1172
void readTopology(std::istream &, bool saveFloatAsHalf=false) override
Read the tree topology from a stream.
Definition: Tree.h:1398
virtual void print(std::ostream &os=std::cout, int verboseLevel=1) const
Print statistics, memory usage and other information about this tree.
Definition: Tree.h:1276
typename RootNodeType::BuildType BuildType
Definition: Tree.h:182
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:1708
OIIO_API bool copy(string_view from, string_view to, std::string &err)
ValueOnIter beginValueOn()
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1171
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:616
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: Tree.h:1605
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1126
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1146
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:1112
NodeT * stealNode(const Coord &xyz, const ValueType &value, bool active)
Return a pointer to the node of type NodeT that contains voxel (x, y, z) and replace it with a tile o...
Definition: Tree.h:1683
void getIndexRange(CoordBBox &bbox) const override
Min and max are both inclusive.
Definition: Tree.h:663
GA_API const UT_StringHolder N
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:118
SharedPtr< const TreeBase > ConstPtr
Definition: Tree.h:39
static std::unique_ptr< const Name > sTreeTypeName
Definition: Tree.h:1218
void combine2Extended(const Tree &a, const OtherTreeType &b, ExtendedCombineOp &op, bool prune=false)
Definition: Tree.h:1961
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1111
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:1700
void combine2(const Tree &a, const OtherTreeType &b, CombineOp &op, bool prune=false)
Definition: Tree.h:1937
GLuint64EXT * result
Definition: glew.h:14007
OPENVDB_API int printBytes(std::ostream &os, uint64_t bytes, const std::string &head="", const std::string &tail="\n", bool exact=false, int width=8, int precision=3)
NodeType * probeNode(const Coord &xyz)
Return a pointer to the node of type NodeType that contains voxel (x, y, z). If no such node exists...
Definition: Tree.h:1717
const Name & type() const override
Return the name of this type of tree.
Definition: Tree.h:271
GLenum array
Definition: glew.h:9066
void clipUnallocatedNodes() override
Replace with background tiles any nodes whose voxel buffers have not yet been allocated.
Definition: Tree.h:1755
RootNodeType::ChildAllCIter beginRootDense() const
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1124
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:1045
const BValueType & b() const
Get the B input value.
Definition: Types.h:973
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1173
virtual const Name & type() const =0
Return the name of this tree's type.
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:334
Metadata::Ptr getBackgroundValue() const override
Return this tree's background value wrapped as metadata.
Definition: Tree.h:1806
NodeIter beginNode()
Return an iterator over all nodes in this tree.
Definition: Tree.h:1144
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:448
bool evalLeafDim(Coord &dim) const override
Return in dim the dimensions of the axis-aligned bounding box of all leaf nodes.
Definition: Tree.h:2165
IterT begin()
Return an iterator of type IterT (for example, begin<ValueOnIter>() is equivalent to beginValueOn())...
Definition: Tree.h:1378
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...
Definition: Tree.h:505
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: Tree.h:1692
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:251
bool empty() const
Return true if this tree contains no nodes other than the root node and no tiles other than backgroun...
Definition: Tree.h:618
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don't change its value.
Definition: Tree.h:1597
void denseFill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value and ensure that those voxels are a...
Definition: Tree.h:1788
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:112
GLsizei const GLfloat * value
Definition: glew.h:1849
void visitActiveBBox(BBoxOp &op) const
Use sparse traversal to call the given functor with bounding box information for all active tiles and...
Definition: Tree.h:972
GLint level
Definition: glew.h:1252
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.
Definition: Tree.h:1612
Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree (Root, Internal, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
Definition: Tree.h:1249
void combine(Tree &other, CombineOp &op, bool prune=false)
Definition: Tree.h:1889
Internal table nodes for OpenVDB trees.
Index treeDepth() const override
Return the depth of this tree.
Definition: Tree.h:335
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
void combineExtended(Tree &other, ExtendedCombineOp &op, bool prune=false)
Definition: Tree.h:1913
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1513
type
Definition: core.h:528
void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const override
Write the tree topology to a stream.
Definition: Tree.h:1408
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:215
std::enable_if< internal::is_string< S >::value >::type print(std::basic_ostream< FMT_CHAR(S)> &os, const S &format_str, const Args &...args)
Definition: ostream.h:146