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