OpenVDB  10.0.0
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  template<typename CombineOp>
771  void combine(Tree& other, const CombineOp& op, bool prune = false);
772 
773  /// Like combine(), but with
774  /// @param other a tree of the same type as this tree
775  /// @param op a functor of the form <tt>void op(CombineArgs<ValueType>& args)</tt> that
776  /// computes <tt>args.setResult(f(args.a(), args.b()))</tt> and, optionally,
777  /// <tt>args.setResultIsActive(g(args.aIsActive(), args.bIsActive()))</tt>
778  /// for some functions @c f and @c g
779  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
780  /// more space-efficient than pruning the entire tree in one pass)
781  ///
782  /// This variant passes not only the @em a and @em b values but also the active states
783  /// of the @em a and @em b values to the functor, which may then return, by calling
784  /// @c args.setResultIsActive(), a computed active state for the result value.
785  /// By default, the result is active if either the @em a or the @em b value is active.
786  ///
787  /// @see openvdb/Types.h for the definition of the CombineArgs struct.
788  ///
789  /// @par Example:
790  /// Replace voxel values in floating-point @c aTree with corresponding values
791  /// from floating-point @c bTree (leaving @c bTree empty) wherever the @c bTree
792  /// values are larger. Also, preserve the active states of any transferred values.
793  /// @code
794  /// {
795  /// struct Local {
796  /// static inline void max(CombineArgs<float>& args) {
797  /// if (args.b() > args.a()) {
798  /// // Transfer the B value and its active state.
799  /// args.setResult(args.b());
800  /// args.setResultIsActive(args.bIsActive());
801  /// } else {
802  /// // Preserve the A value and its active state.
803  /// args.setResult(args.a());
804  /// args.setResultIsActive(args.aIsActive());
805  /// }
806  /// }
807  /// };
808  /// aTree.combineExtended(bTree, Local::max);
809  /// }
810  /// @endcode
811  template<typename ExtendedCombineOp>
812  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
813  template<typename ExtendedCombineOp>
814  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
815 
816  /// For a given function @c f, use sparse traversal to compute <tt>f(a, b)</tt> over all
817  /// corresponding pairs of values (tile or voxel) of trees A and B and store the result
818  /// in this tree.
819  /// @param a,b two trees with the same configuration (levels and node dimensions)
820  /// as this tree but with the B tree possibly having a different value type
821  /// @param op a functor of the form <tt>void op(const T1& a, const T2& b, T1& result)</tt>,
822  /// where @c T1 is this tree's and the A tree's @c ValueType and @c T2 is the
823  /// B tree's @c ValueType, that computes <tt>result = f(a, b)</tt>
824  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
825  /// more space-efficient than pruning the entire tree in one pass)
826  ///
827  /// @throw TypeError if the B tree's configuration doesn't match this tree's
828  /// or if this tree's ValueType is not constructible from the B tree's ValueType.
829  ///
830  /// @par Example:
831  /// Compute the per-voxel difference between two floating-point trees,
832  /// @c aTree and @c bTree, and store the result in a third tree.
833  /// @code
834  /// {
835  /// struct Local {
836  /// static inline void diff(const float& a, const float& b, float& result) {
837  /// result = a - b;
838  /// }
839  /// };
840  /// FloatTree resultTree;
841  /// resultTree.combine2(aTree, bTree, Local::diff);
842  /// }
843  /// @endcode
844  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
845  void combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune = false);
846  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
847  void combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune = false);
848 
849  /// Like combine2(), but with
850  /// @param a,b two trees with the same configuration (levels and node dimensions)
851  /// as this tree but with the B tree possibly having a different value type
852  /// @param op a functor of the form <tt>void op(CombineArgs<T1, T2>& args)</tt>, where
853  /// @c T1 is this tree's and the A tree's @c ValueType and @c T2 is the B tree's
854  /// @c ValueType, that computes <tt>args.setResult(f(args.a(), args.b()))</tt>
855  /// and, optionally,
856  /// <tt>args.setResultIsActive(g(args.aIsActive(), args.bIsActive()))</tt>
857  /// for some functions @c f and @c g
858  /// @param prune if true, prune the resulting tree one branch at a time (this is usually
859  /// more space-efficient than pruning the entire tree in one pass)
860  /// This variant passes not only the @em a and @em b values but also the active states
861  /// of the @em a and @em b values to the functor, which may then return, by calling
862  /// <tt>args.setResultIsActive()</tt>, a computed active state for the result value.
863  /// By default, the result is active if either the @em a or the @em b value is active.
864  ///
865  /// @throw TypeError if the B tree's configuration doesn't match this tree's
866  /// or if this tree's ValueType is not constructible from the B tree's ValueType.
867  ///
868  /// @see openvdb/Types.h for the definition of the CombineArgs struct.
869  ///
870  /// @par Example:
871  /// Compute the per-voxel maximum values of two single-precision floating-point trees,
872  /// @c aTree and @c bTree, and store the result in a third tree. Set the active state
873  /// of each output value to that of the larger of the two input values.
874  /// @code
875  /// {
876  /// struct Local {
877  /// static inline void max(CombineArgs<float>& args) {
878  /// if (args.b() > args.a()) {
879  /// // Transfer the B value and its active state.
880  /// args.setResult(args.b());
881  /// args.setResultIsActive(args.bIsActive());
882  /// } else {
883  /// // Preserve the A value and its active state.
884  /// args.setResult(args.a());
885  /// args.setResultIsActive(args.aIsActive());
886  /// }
887  /// }
888  /// };
889  /// FloatTree aTree = ...;
890  /// FloatTree bTree = ...;
891  /// FloatTree resultTree;
892  /// resultTree.combine2Extended(aTree, bTree, Local::max);
893  /// }
894  /// @endcode
895  ///
896  /// @par Example:
897  /// Compute the per-voxel maximum values of a double-precision and a single-precision
898  /// floating-point tree, @c aTree and @c bTree, and store the result in a third,
899  /// double-precision tree. Set the active state of each output value to that of
900  /// the larger of the two input values.
901  /// @code
902  /// {
903  /// struct Local {
904  /// static inline void max(CombineArgs<double, float>& args) {
905  /// if (args.b() > args.a()) {
906  /// // Transfer the B value and its active state.
907  /// args.setResult(args.b());
908  /// args.setResultIsActive(args.bIsActive());
909  /// } else {
910  /// // Preserve the A value and its active state.
911  /// args.setResult(args.a());
912  /// args.setResultIsActive(args.aIsActive());
913  /// }
914  /// }
915  /// };
916  /// DoubleTree aTree = ...;
917  /// FloatTree bTree = ...;
918  /// DoubleTree resultTree;
919  /// resultTree.combine2Extended(aTree, bTree, Local::max);
920  /// }
921  /// @endcode
922  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
923  void combine2Extended(const Tree& a, const OtherTreeType& b, ExtendedCombineOp& op,
924  bool prune = false);
925  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
926  void combine2Extended(const Tree& a, const OtherTreeType& b, const ExtendedCombineOp&,
927  bool prune = false);
928 
929  //
930  // Iteration
931  //
932  //@{
933  /// Return an iterator over children of the root node.
934  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
935  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
936  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
937  //@}
938 
939  //@{
940  /// Return an iterator over non-child entries of the root node's table.
941  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
942  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
943  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
944  //@}
945 
946  //@{
947  /// Return an iterator over all entries of the root node's table.
948  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
949  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
950  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
951  //@}
952 
953 
954  //@{
955  /// Iterator over all nodes in this tree
958  //@}
959 
960  //@{
961  /// Iterator over all leaf nodes in this tree
964  //@}
965 
966  //@{
967  /// Return an iterator over all nodes in this tree.
968  NodeIter beginNode() { return NodeIter(*this); }
969  NodeCIter beginNode() const { return NodeCIter(*this); }
970  NodeCIter cbeginNode() const { return NodeCIter(*this); }
971  //@}
972 
973  //@{
974  /// Return an iterator over all leaf nodes in this tree.
975  LeafIter beginLeaf() { return LeafIter(*this); }
976  LeafCIter beginLeaf() const { return LeafCIter(*this); }
977  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
978  //@}
979 
986 
987  //@{
988  /// Return an iterator over all values (tile and voxel) across all nodes.
990  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
991  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
992  //@}
993  //@{
994  /// Return an iterator over active values (tile and voxel) across all nodes.
995  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
996  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
997  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
998  //@}
999  //@{
1000  /// Return an iterator over inactive values (tile and voxel) across all nodes.
1002  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1003  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1004  //@}
1005 
1006  /// @brief Return an iterator of type @c IterT (for example, begin<ValueOnIter>() is
1007  /// equivalent to beginValueOn()).
1008  template<typename IterT> IterT begin();
1009  /// @brief Return a const iterator of type CIterT (for example, cbegin<ValueOnCIter>()
1010  /// is equivalent to cbeginValueOn()).
1011  template<typename CIterT> CIterT cbegin() const;
1012 
1013 
1014 protected:
1015  using AccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<Tree, true>*, bool>;
1016  using ConstAccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<const Tree, true>*, bool>;
1017 
1018  /// @brief Notify all registered accessors, by calling ValueAccessor::release(),
1019  /// that this tree is about to be deleted.
1020  void releaseAllAccessors();
1021 
1022  // TBB body object used to deallocates nodes in parallel.
1023  template<typename NodeType>
1025  DeallocateNodes(std::vector<NodeType*>& nodes)
1026  : mNodes(nodes.empty() ? nullptr : &nodes.front()) { }
1027  void operator()(const tbb::blocked_range<size_t>& range) const {
1028  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
1029  delete mNodes[n]; mNodes[n] = nullptr;
1030  }
1031  }
1032  NodeType ** const mNodes;
1033  };
1034 
1035  //
1036  // Data members
1037  //
1038  RootNodeType mRoot; // root node of the tree
1041 
1042  static std::unique_ptr<const Name> sTreeTypeName;
1043 }; // end of Tree class
1044 
1045 template<typename _RootNodeType>
1046 std::unique_ptr<const Name> Tree<_RootNodeType>::sTreeTypeName;
1047 
1048 
1049 /// @brief Tree3<T, N1, N2>::Type is the type of a three-level tree
1050 /// (Root, Internal, Leaf) with value type T and
1051 /// internal and leaf node log dimensions N1 and N2, respectively.
1052 /// @note This is NOT the standard tree configuration (Tree4 is).
1053 template<typename T, Index N1=4, Index N2=3>
1054 struct Tree3 {
1056 };
1057 
1058 
1059 /// @brief Tree4<T, N1, N2, N3>::Type is the type of a four-level tree
1060 /// (Root, Internal, Internal, Leaf) with value type T and
1061 /// internal and leaf node log dimensions N1, N2 and N3, respectively.
1062 /// @note This is the standard tree configuration.
1063 template<typename T, Index N1=5, Index N2=4, Index N3=3>
1064 struct Tree4 {
1066 };
1067 
1068 /// @brief Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree
1069 /// (Root, Internal, Internal, Internal, Leaf) with value type T and
1070 /// internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
1071 /// @note This is NOT the standard tree configuration (Tree4 is).
1072 template<typename T, Index N1=6, Index N2=5, Index N3=4, Index N4=3>
1073 struct Tree5 {
1074  using Type =
1076 };
1077 
1078 
1079 ////////////////////////////////////////
1080 
1081 
1082 inline void
1083 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1084 {
1085  int32_t bufferCount;
1086  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1087  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1088 }
1089 
1090 
1091 inline void
1092 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1093 {
1094  int32_t bufferCount = 1;
1095  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1096 }
1097 
1098 
1099 inline void
1100 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1101 {
1102  os << " Tree Type: " << type()
1103  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1104  << " Active tile Count: " << activeTileCount() << std::endl
1105  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1106  << " Leaf Node Count: " << leafCount() << std::endl
1107  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1108 }
1109 
1110 
1111 ////////////////////////////////////////
1112 
1113 
1114 //
1115 // Type traits for tree iterators
1116 //
1117 
1118 /// @brief TreeIterTraits provides, for all tree iterators, a begin(tree) function
1119 /// that returns an iterator over a tree of arbitrary type.
1120 template<typename TreeT, typename IterT> struct TreeIterTraits;
1121 
1122 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1123  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1124  return tree.beginRootChildren();
1125  }
1126 };
1127 
1128 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1129  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1130  return tree.cbeginRootChildren();
1131  }
1132 };
1133 
1134 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1135  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1136  return tree.beginRootTiles();
1137  }
1138 };
1139 
1140 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1141  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1142  return tree.cbeginRootTiles();
1143  }
1144 };
1145 
1146 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1147  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1148  return tree.beginRootDense();
1149  }
1150 };
1151 
1152 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1153  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1154  return tree.cbeginRootDense();
1155  }
1156 };
1157 
1158 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1159  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1160 };
1161 
1162 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1163  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1164 };
1165 
1166 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1167  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1168 };
1169 
1170 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1171  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1172 };
1173 
1174 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1175  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1176 };
1177 
1178 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1179  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1180 };
1181 
1182 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1183  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1184 };
1185 
1186 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1187  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1188 };
1189 
1190 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1191  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1192 };
1193 
1194 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1195  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1196 };
1197 
1198 
1199 template<typename RootNodeType>
1200 template<typename IterT>
1201 inline IterT
1203 {
1204  return TreeIterTraits<Tree, IterT>::begin(*this);
1205 }
1206 
1207 
1208 template<typename RootNodeType>
1209 template<typename IterT>
1210 inline IterT
1212 {
1213  return TreeIterTraits<Tree, IterT>::begin(*this);
1214 }
1215 
1216 
1217 ////////////////////////////////////////
1218 
1219 
1220 template<typename RootNodeType>
1221 void
1222 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1223 {
1224  this->clearAllAccessors();
1225  TreeBase::readTopology(is, saveFloatAsHalf);
1226  mRoot.readTopology(is, saveFloatAsHalf);
1227 }
1228 
1229 
1230 template<typename RootNodeType>
1231 void
1232 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1233 {
1234  TreeBase::writeTopology(os, saveFloatAsHalf);
1235  mRoot.writeTopology(os, saveFloatAsHalf);
1236 }
1237 
1238 
1239 template<typename RootNodeType>
1240 inline void
1241 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1242 {
1243  this->clearAllAccessors();
1244  mRoot.readBuffers(is, saveFloatAsHalf);
1245 }
1246 
1247 
1248 template<typename RootNodeType>
1249 inline void
1250 Tree<RootNodeType>::readBuffers(std::istream &is, const CoordBBox& bbox, bool saveFloatAsHalf)
1251 {
1252  this->clearAllAccessors();
1253  mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1254 }
1255 
1256 
1257 template<typename RootNodeType>
1258 inline void
1260 {
1261  for (LeafCIter it = this->cbeginLeaf(); it; ++it) {
1262  // Retrieving the value of a leaf voxel forces loading of the leaf node's voxel buffer.
1263  it->getValue(Index(0));
1264  }
1265 }
1266 
1267 
1268 template<typename RootNodeType>
1269 inline void
1270 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1271 {
1272  mRoot.writeBuffers(os, saveFloatAsHalf);
1273 }
1274 
1275 
1276 template<typename RootNodeType>
1277 inline void
1279 {
1280  std::vector<LeafNodeType*> leafnodes;
1281  this->stealNodes(leafnodes);
1282 
1283  tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
1284  DeallocateNodes<LeafNodeType>(leafnodes));
1285 
1286  std::vector<typename RootNodeType::ChildNodeType*> internalNodes;
1287  this->stealNodes(internalNodes);
1288 
1289  tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
1291 
1292  mRoot.clear();
1293 
1294  this->clearAllAccessors();
1295 }
1296 
1297 
1298 ////////////////////////////////////////
1299 
1300 
1301 template<typename RootNodeType>
1302 inline void
1304 {
1305  typename AccessorRegistry::accessor a;
1306  mAccessorRegistry.insert(a, &accessor);
1307 }
1308 
1309 
1310 template<typename RootNodeType>
1311 inline void
1313 {
1314  typename ConstAccessorRegistry::accessor a;
1315  mConstAccessorRegistry.insert(a, &accessor);
1316 }
1317 
1318 
1319 template<typename RootNodeType>
1320 inline void
1322 {
1323  mAccessorRegistry.erase(&accessor);
1324 }
1325 
1326 
1327 template<typename RootNodeType>
1328 inline void
1330 {
1331  mConstAccessorRegistry.erase(&accessor);
1332 }
1333 
1334 
1335 template<typename RootNodeType>
1336 inline void
1338 {
1339  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1340  it != mAccessorRegistry.end(); ++it)
1341  {
1342  if (it->first) it->first->clear();
1343  }
1344 
1345  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1346  it != mConstAccessorRegistry.end(); ++it)
1347  {
1348  if (it->first) it->first->clear();
1349  }
1350 }
1351 
1352 
1353 template<typename RootNodeType>
1354 inline void
1356 {
1357  mAccessorRegistry.erase(nullptr);
1358  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1359  it != mAccessorRegistry.end(); ++it)
1360  {
1361  it->first->release();
1362  }
1363  mAccessorRegistry.clear();
1364 
1365  mAccessorRegistry.erase(nullptr);
1366  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1367  it != mConstAccessorRegistry.end(); ++it)
1368  {
1369  it->first->release();
1370  }
1371  mConstAccessorRegistry.clear();
1372 }
1373 
1374 
1375 ////////////////////////////////////////
1376 
1377 
1378 template<typename RootNodeType>
1379 inline const typename RootNodeType::ValueType&
1380 Tree<RootNodeType>::getValue(const Coord& xyz) const
1381 {
1382  return mRoot.getValue(xyz);
1383 }
1384 
1385 
1386 template<typename RootNodeType>
1387 template<typename AccessT>
1388 inline const typename RootNodeType::ValueType&
1389 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1390 {
1391  return accessor.getValue(xyz);
1392 }
1393 
1394 
1395 template<typename RootNodeType>
1396 inline int
1397 Tree<RootNodeType>::getValueDepth(const Coord& xyz) const
1398 {
1399  return mRoot.getValueDepth(xyz);
1400 }
1401 
1402 
1403 template<typename RootNodeType>
1404 inline void
1406 {
1407  mRoot.setValueOff(xyz);
1408 }
1409 
1410 
1411 template<typename RootNodeType>
1412 inline void
1413 Tree<RootNodeType>::setValueOff(const Coord& xyz, const ValueType& value)
1414 {
1415  mRoot.setValueOff(xyz, value);
1416 }
1417 
1418 
1419 template<typename RootNodeType>
1420 inline void
1421 Tree<RootNodeType>::setActiveState(const Coord& xyz, bool on)
1422 {
1423  mRoot.setActiveState(xyz, on);
1424 }
1425 
1426 
1427 template<typename RootNodeType>
1428 inline void
1429 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value)
1430 {
1431  mRoot.setValueOn(xyz, value);
1432 }
1433 
1434 template<typename RootNodeType>
1435 inline void
1436 Tree<RootNodeType>::setValueOnly(const Coord& xyz, const ValueType& value)
1437 {
1438  mRoot.setValueOnly(xyz, value);
1439 }
1440 
1441 template<typename RootNodeType>
1442 template<typename AccessT>
1443 inline void
1444 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1445 {
1446  accessor.setValue(xyz, value);
1447 }
1448 
1449 
1450 template<typename RootNodeType>
1451 inline void
1453 {
1454  mRoot.setActiveState(xyz, true);
1455 }
1456 
1457 
1458 template<typename RootNodeType>
1459 inline void
1460 Tree<RootNodeType>::setValueOn(const Coord& xyz, const ValueType& value)
1461 {
1462  mRoot.setValueOn(xyz, value);
1463 }
1464 
1465 
1466 template<typename RootNodeType>
1467 template<typename ModifyOp>
1468 inline void
1469 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1470 {
1471  mRoot.modifyValue(xyz, op);
1472 }
1473 
1474 
1475 template<typename RootNodeType>
1476 template<typename ModifyOp>
1477 inline void
1478 Tree<RootNodeType>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1479 {
1480  mRoot.modifyValueAndActiveState(xyz, op);
1481 }
1482 
1483 
1484 template<typename RootNodeType>
1485 inline bool
1486 Tree<RootNodeType>::probeValue(const Coord& xyz, ValueType& value) const
1487 {
1488  return mRoot.probeValue(xyz, value);
1489 }
1490 
1491 
1492 ////////////////////////////////////////
1493 
1494 
1495 template<typename RootNodeType>
1496 inline void
1497 Tree<RootNodeType>::addTile(Index level, const Coord& xyz,
1498  const ValueType& value, bool active)
1499 {
1500  mRoot.addTile(level, xyz, value, active);
1501 }
1502 
1503 
1504 template<typename RootNodeType>
1505 template<typename NodeT>
1506 inline NodeT*
1507 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1508 {
1509  this->clearAllAccessors();
1510  return mRoot.template stealNode<NodeT>(xyz, value, active);
1511 }
1512 
1513 
1514 template<typename RootNodeType>
1515 inline typename RootNodeType::LeafNodeType*
1517 {
1518  return mRoot.touchLeaf(xyz);
1519 }
1520 
1521 
1522 template<typename RootNodeType>
1523 inline typename RootNodeType::LeafNodeType*
1525 {
1526  return mRoot.probeLeaf(xyz);
1527 }
1528 
1529 
1530 template<typename RootNodeType>
1531 inline const typename RootNodeType::LeafNodeType*
1532 Tree<RootNodeType>::probeConstLeaf(const Coord& xyz) const
1533 {
1534  return mRoot.probeConstLeaf(xyz);
1535 }
1536 
1537 
1538 template<typename RootNodeType>
1539 template<typename NodeType>
1540 inline NodeType*
1542 {
1543  return mRoot.template probeNode<NodeType>(xyz);
1544 }
1545 
1546 
1547 template<typename RootNodeType>
1548 template<typename NodeType>
1549 inline const NodeType*
1550 Tree<RootNodeType>::probeNode(const Coord& xyz) const
1551 {
1552  return this->template probeConstNode<NodeType>(xyz);
1553 }
1554 
1555 
1556 template<typename RootNodeType>
1557 template<typename NodeType>
1558 inline const NodeType*
1559 Tree<RootNodeType>::probeConstNode(const Coord& xyz) const
1560 {
1561  return mRoot.template probeConstNode<NodeType>(xyz);
1562 }
1563 
1564 
1565 ////////////////////////////////////////
1566 
1567 
1568 template<typename RootNodeType>
1569 inline void
1571 {
1572  this->clearAllAccessors();
1573  return mRoot.clip(bbox);
1574 }
1575 
1576 
1577 template<typename RootNodeType>
1578 inline void
1580 {
1581  this->clearAllAccessors();
1582  for (LeafIter it = this->beginLeaf(); it; ) {
1583  const LeafNodeType* leaf = it.getLeaf();
1584  ++it; // advance the iterator before deleting the leaf node
1585  if (!leaf->isAllocated()) {
1586  this->addTile(/*level=*/0, leaf->origin(), this->background(), /*active=*/false);
1587  }
1588  }
1589 }
1590 
1591 template<typename RootNodeType>
1592 inline Index32
1594 {
1595  Index32 sum = 0;
1596  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
1597  return sum;
1598 }
1599 
1600 
1601 template<typename RootNodeType>
1602 inline void
1603 Tree<RootNodeType>::sparseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1604 {
1605  this->clearAllAccessors();
1606  return mRoot.sparseFill(bbox, value, active);
1607 }
1608 
1609 
1610 template<typename RootNodeType>
1611 inline void
1612 Tree<RootNodeType>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1613 {
1614  this->clearAllAccessors();
1615  return mRoot.denseFill(bbox, value, active);
1616 }
1617 
1618 
1619 template<typename RootNodeType>
1620 inline void
1622 {
1623  this->clearAllAccessors();
1624  mRoot.voxelizeActiveTiles(threaded);
1625 }
1626 
1627 
1628 template<typename RootNodeType>
1631 {
1632  Metadata::Ptr result;
1633  if (Metadata::isRegisteredType(valueType())) {
1634  using MetadataT = TypedMetadata<ValueType>;
1635  result = Metadata::createMetadata(valueType());
1636  if (result->typeName() == MetadataT::staticTypeName()) {
1637  MetadataT* m = static_cast<MetadataT*>(result.get());
1638  m->value() = mRoot.background();
1639  }
1640  }
1641  return result;
1642 }
1643 
1644 
1645 ////////////////////////////////////////
1646 
1647 
1648 template<typename RootNodeType>
1649 inline void
1651 {
1652  this->clearAllAccessors();
1653  other.clearAllAccessors();
1654  switch (policy) {
1655  case MERGE_ACTIVE_STATES:
1656  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1657  case MERGE_NODES:
1658  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1660  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1661  }
1662 }
1663 
1664 
1665 template<typename RootNodeType>
1666 template<typename OtherRootNodeType>
1667 inline void
1668 Tree<RootNodeType>::topologyUnion(const Tree<OtherRootNodeType>& other, const bool preserveTiles)
1669 {
1670  this->clearAllAccessors();
1671  mRoot.topologyUnion(other.root(), preserveTiles);
1672 }
1673 
1674 template<typename RootNodeType>
1675 template<typename OtherRootNodeType>
1676 inline void
1678 {
1679  this->clearAllAccessors();
1680  mRoot.topologyIntersection(other.root());
1681 }
1682 
1683 template<typename RootNodeType>
1684 template<typename OtherRootNodeType>
1685 inline void
1687 {
1688  this->clearAllAccessors();
1689  mRoot.topologyDifference(other.root());
1690 }
1691 
1692 ////////////////////////////////////////
1693 
1694 
1695 /// @brief Helper class to adapt a three-argument (a, b, result) CombineOp functor
1696 /// into a single-argument functor that accepts a CombineArgs struct
1697 template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1699 {
1700  CombineOpAdapter(CombineOp& _op): op(_op) {}
1701 
1703  op(args.a(), args.b(), args.result());
1704  }
1705 
1706  CombineOp& op;
1707 };
1708 
1709 
1710 template<typename RootNodeType>
1711 template<typename CombineOp>
1712 inline void
1713 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1714 {
1716  this->combineExtended(other, extendedOp, prune);
1717 }
1718 
1719 
1720 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1721 /// code like this: <tt>aTree.combine(bTree, MyCombineOp(...))</tt>.
1722 template<typename RootNodeType>
1723 template<typename CombineOp>
1724 inline void
1725 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1726 {
1728  this->combineExtended(other, extendedOp, prune);
1729 }
1730 
1731 
1732 template<typename RootNodeType>
1733 template<typename ExtendedCombineOp>
1734 inline void
1735 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1736 {
1737  this->clearAllAccessors();
1738  mRoot.combine(other.root(), op, prune);
1739 }
1740 
1741 
1742 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1743 /// code like this: <tt>aTree.combineExtended(bTree, MyCombineOp(...))</tt>.
1744 template<typename RootNodeType>
1745 template<typename ExtendedCombineOp>
1746 inline void
1747 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1748 {
1749  this->clearAllAccessors();
1750  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1751 }
1752 
1753 
1754 template<typename RootNodeType>
1755 template<typename CombineOp, typename OtherTreeType>
1756 inline void
1757 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1758 {
1760  this->combine2Extended(a, b, extendedOp, prune);
1761 }
1762 
1763 
1764 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1765 /// code like this: <tt>tree.combine2(aTree, bTree, MyCombineOp(...))</tt>.
1766 template<typename RootNodeType>
1767 template<typename CombineOp, typename OtherTreeType>
1768 inline void
1769 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1770 {
1772  this->combine2Extended(a, b, extendedOp, prune);
1773 }
1774 
1775 
1776 template<typename RootNodeType>
1777 template<typename ExtendedCombineOp, typename OtherTreeType>
1778 inline void
1779 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1780  ExtendedCombineOp& op, bool prune)
1781 {
1782  this->clearAllAccessors();
1783  mRoot.combine2(a.root(), b.root(), op, prune);
1784 }
1785 
1786 
1787 /// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1788 /// code like the following, where the functor argument is a temporary:
1789 /// <tt>tree.combine2Extended(aTree, bTree, MyCombineOp(...))</tt>.
1790 template<typename RootNodeType>
1791 template<typename ExtendedCombineOp, typename OtherTreeType>
1792 inline void
1793 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1794  const ExtendedCombineOp& op, bool prune)
1795 {
1796  this->clearAllAccessors();
1797  mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
1798 }
1799 
1800 
1801 ////////////////////////////////////////
1802 
1803 
1804 template<typename RootNodeType>
1805 inline const Name&
1807 {
1808  static std::once_flag once;
1809  std::call_once(once, []()
1810  {
1811  std::vector<Index> dims;
1812  Tree::getNodeLog2Dims(dims);
1813  std::ostringstream ostr;
1814  ostr << "Tree_" << typeNameAsString<BuildType>();
1815  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1816  ostr << "_" << dims[i];
1817  }
1818  sTreeTypeName.reset(new Name(ostr.str()));
1819  });
1820  return *sTreeTypeName;
1821 }
1822 
1823 
1824 template<typename RootNodeType>
1825 template<typename OtherRootNodeType>
1826 inline bool
1828 {
1829  return mRoot.hasSameTopology(other.root());
1830 }
1831 
1832 
1833 template<typename RootNodeType>
1834 inline bool
1836 {
1837  bbox.reset(); // default invalid bbox
1838 
1839  if (this->empty()) return false; // empty
1840 
1841  mRoot.evalActiveBoundingBox(bbox, false);
1842 
1843  return !bbox.empty();
1844 }
1845 
1846 template<typename RootNodeType>
1847 inline bool
1849 {
1850  bbox.reset(); // default invalid bbox
1851 
1852  if (this->empty()) return false; // empty
1853 
1854  mRoot.evalActiveBoundingBox(bbox, true);
1855 
1856  return !bbox.empty();
1857 }
1858 
1859 
1860 template<typename RootNodeType>
1861 inline bool
1863 {
1864  CoordBBox bbox;
1865  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1866  dim = bbox.extents();
1867  return notEmpty;
1868 }
1869 
1870 
1871 template<typename RootNodeType>
1872 inline bool
1874 {
1875  CoordBBox bbox;
1876  bool notEmpty = this->evalLeafBoundingBox(bbox);
1877  dim = bbox.extents();
1878  return notEmpty;
1879 }
1880 
1881 
1882 template<typename RootNodeType>
1883 inline void
1885 {
1886  minVal = maxVal = zeroVal<ValueType>();
1887  if (ValueOnCIter iter = this->cbeginValueOn()) {
1888  minVal = maxVal = *iter;
1889  for (++iter; iter; ++iter) {
1890  const ValueType& val = *iter;
1891  if (math::cwiseLessThan(val, minVal)) minVal = val;
1892  if (math::cwiseGreaterThan(val, maxVal)) maxVal = val;
1893  }
1894  }
1895 }
1896 
1897 
1898 template<typename RootNodeType>
1899 inline void
1900 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
1901 {
1902  dims.clear();
1903  RootNodeType::getNodeLog2Dims(dims);
1904 }
1905 
1906 
1907 template<typename RootNodeType>
1908 inline void
1909 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
1910 {
1911  if (verboseLevel <= 0) return;
1912 
1913  /// @todo Consider using boost::io::ios_precision_saver instead.
1914  struct OnExit {
1915  std::ostream& os;
1916  std::streamsize savedPrecision;
1917  OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
1918  ~OnExit() { os.precision(savedPrecision); }
1919  };
1920  OnExit restorePrecision(os);
1921 
1922  std::vector<Index> dims;
1923  Tree::getNodeLog2Dims(dims);// leaf is the last element
1924 
1925  os << "Information about Tree:\n"
1926  << " Type: " << this->type() << "\n";
1927 
1928  os << " Configuration:\n";
1929 
1930  if (verboseLevel <= 1) {
1931  // Print node types and sizes.
1932  os << " Root(" << mRoot.getTableSize() << ")";
1933  if (dims.size() > 1) {
1934  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1935  os << ", Internal(" << (1 << dims[i]) << "^3)";
1936  }
1937  os << ", Leaf(" << (1 << dims.back()) << "^3)\n";
1938  }
1939  os << " Background value: " << mRoot.background() << "\n";
1940  return;
1941  }
1942 
1943  // The following is tree information that is expensive to extract.
1944 
1945  ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
1946  if (verboseLevel > 3) {
1947  // This forces loading of all non-resident nodes.
1949  minVal = extrema.min();
1950  maxVal = extrema.max();
1951  }
1952 
1953  const auto nodeCount = this->nodeCount();//fast
1954  const Index32 leafCount = nodeCount.front();// leaf is the first element
1955  assert(dims.size() == nodeCount.size());
1956 
1957  Index64 totalNodeCount = 0;
1958  for (size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
1959 
1960  // Print node types, counts and sizes.
1961  os << " Root(1 x " << mRoot.getTableSize() << ")";
1962  if (dims.size() >= 2) {
1963  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1964  os << ", Internal(" << util::formattedInt(nodeCount[N - i]);
1965  os << " x " << (1 << dims[i]) << "^3)";
1966  }
1967  os << ", Leaf(" << util::formattedInt(leafCount);
1968  os << " x " << (1 << dims.back()) << "^3)\n";
1969  }
1970  os << " Background value: " << mRoot.background() << "\n";
1971 
1972  // Statistics of topology and values
1973 
1974  if (verboseLevel > 3) {
1975  os << " Min value: " << minVal << "\n";
1976  os << " Max value: " << maxVal << "\n";
1977  }
1978 
1979  const Index64
1980  numActiveVoxels = this->activeVoxelCount(),
1981  numActiveLeafVoxels = this->activeLeafVoxelCount(),
1982  numActiveTiles = this->activeTileCount();
1983 
1984  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
1985  os << " Number of active tiles: " << util::formattedInt(numActiveTiles) << "\n";
1986 
1987  Coord dim(0, 0, 0);
1988  Index64 totalVoxels = 0;
1989  if (numActiveVoxels) { // nonempty
1990  CoordBBox bbox;
1991  this->evalActiveVoxelBoundingBox(bbox);
1992  dim = bbox.extents();
1993  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
1994 
1995  os << " Bounding box of active voxels: " << bbox << "\n";
1996  os << " Dimensions of active voxels: "
1997  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
1998 
1999  const double activeRatio = (100.0 * double(numActiveVoxels)) / double(totalVoxels);
2000  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2001 
2002  if (leafCount > 0) {
2003  const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2004  / (double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2005  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2006  }
2007 
2008  if (verboseLevel > 2) {
2009  Index64 sum = 0;// count the number of unallocated leaf nodes
2010  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
2011  os << " Number of unallocated nodes: "
2012  << util::formattedInt(sum) << " ("
2013  << (100.0 * double(sum) / double(totalNodeCount)) << "%)\n";
2014  }
2015  } else {
2016  os << " Tree is empty!\n";
2017  }
2018  os << std::flush;
2019 
2020  if (verboseLevel == 2) return;
2021 
2022  // Memory footprint in bytes
2023  const Index64
2024  actualMem = this->memUsage(),
2025  denseMem = sizeof(ValueType) * totalVoxels,
2026  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2027  ///< @todo not accurate for BoolTree (and probably should count tile values)
2028 
2029  os << "Memory footprint:\n";
2030  util::printBytes(os, actualMem, " Actual: ");
2031  util::printBytes(os, voxelsMem, " Active leaf voxels: ");
2032 
2033  if (numActiveVoxels) {
2034  util::printBytes(os, denseMem, " Dense equivalent: ");
2035  os << " Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2036  << "% of an equivalent dense volume\n";
2037  os << " Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2038  << "% of actual footprint\n";
2039  }
2040 }
2041 
2042 } // namespace tree
2043 } // namespace OPENVDB_VERSION_NAME
2044 } // namespace openvdb
2045 
2046 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
void getNodes(ArrayT &array)
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:579
Index32 Index
Definition: Types.h:54
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:450
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:1064
#define OPENVDB_API
Definition: Platform.h:251
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
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.
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
uint64_t Index64
Definition: Types.h:53
SharedPtr< TreeBase > Ptr
Definition: Tree.h:39
ValueAllIter beginValueAll()
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:989
std::vector< Index32 > nodeCount() const override
Definition: Tree.h:344
Index64 countInactiveLeafVoxels(const TreeT &tree, bool threaded=true)
Return the total number of inactive voxels stored in leaf nodes.
Definition: Count.h:471
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:106
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: Tree.h:1405
Utility routines to output nicely-formatted numeric values.
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
Index64 activeVoxelCount() const override
Return the total number of active voxels.
Definition: Tree.h:357
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1163
Index64 activeLeafVoxelCount() const override
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:353
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1120
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:969
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
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
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1380
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:970
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
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1083
NodeIter beginNode()
Return an iterator over all nodes in this tree.
Definition: Tree.h:968
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Tree.h:1027
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:118
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1040
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:110
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1003
void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const override
Write out all data buffers for this tree.
Definition: Tree.h:1270
bool cwiseLessThan(const Mat< SIZE, T > &m0, const Mat< SIZE, T > &m1)
Definition: Mat.h:1015
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1167
Templated class to compute the minimum and maximum values.
Definition: Stats.h:30
bool cwiseGreaterThan(const Mat< SIZE, T > &m0, const Mat< SIZE, T > &m1)
Definition: Mat.h:1029
RootNodeType mRoot
Definition: Tree.h:1038
const ValueType & max() const
Return the maximum value.
Definition: Stats.h:63
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
bool operator!=(const Tree &) const
Definition: Tree.h:277
CombineOp & op
Definition: Tree.h:1706
Index64 countActiveVoxels(const TreeT &tree, bool threaded=true)
Return the total number of active voxels in the tree.
Definition: Count.h:413
Index64 countActiveLeafVoxels(const TreeT &tree, bool threaded=true)
Return the total number of active voxels stored in leaf nodes.
Definition: Count.h:436
static bool isRegisteredType(const Name &typeName)
Return true if the given type is known by the metadata type registry.
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:1073
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1153
_RootNodeType RootNodeType
Definition: Tree.h:183
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:92
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:1429
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:997
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 clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:1278
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:134
void getNodes(ArrayT &array) const
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:580
tbb::concurrent_hash_map< ValueAccessorBase< const Tree, true > *, bool > ConstAccessorRegistry
Definition: Tree.h:1016
const AValueType & a() const
Get the A input value.
Definition: Types.h:569
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1186
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:1436
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1175
typename RootNodeType::BuildType BuildType
Definition: Tree.h:185
const BValueType & b() const
Get the B input value.
Definition: Types.h:571
const Name & type() const override
Return the name of this type of tree.
Definition: Tree.h:274
const ValueType & background() const
Return this tree&#39;s background value.
Definition: Tree.h:662
static std::unique_ptr< const Name > sTreeTypeName
Definition: Tree.h:1042
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:454
Definition: Tree.h:177
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:976
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:261
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1129
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1187
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:452
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1135
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1337
RootNodeType::ChildAllCIter beginRootDense() const
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:948
Index64 activeTileCount() const override
Return the total number of active tiles.
Definition: Tree.h:361
Index64 inactiveLeafVoxelCount() const override
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:355
BBox< Coord > CoordBBox
Definition: NanoVDB.h:1809
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1171
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
SharedPtr< const TreeBase > ConstPtr
Definition: Tree.h:40
void releaseAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:650
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: Tree.h:1452
const RootNodeType & root() const
Return this tree&#39;s root node.
Definition: Tree.h:282
Base class for typed trees.
Definition: Tree.h:36
LeafIter beginLeaf()
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:975
void releaseAccessor(ValueAccessorBase< Tree, false > &) const
Dummy implementations.
Definition: Tree.h:649
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:218
void attachAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:638
Internal table nodes for OpenVDB trees.
NodeType **const mNodes
Definition: Tree.h:1032
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1159
Templated metadata class to hold specific types.
Definition: Metadata.h:121
void attachAccessor(ValueAccessorBase< Tree, false > &) const
Dummy implementations.
Definition: Tree.h:637
SharedPtr< Metadata > Ptr
Definition: Metadata.h:26
RootNodeType::ChildOnCIter beginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:934
typename RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:186
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1141
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1191
DeallocateNodes(std::vector< NodeType * > &nodes)
Definition: Tree.h:1025
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:616
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1179
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:254
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
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1486
Definition: Exceptions.h:13
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:949
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1478
ValueT value
Definition: GridBuilder.h:1290
ValueOffIter beginValueOff()
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1001
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:990
RootNodeType::ChildOffCIter beginRootTiles() const
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:941
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:936
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:935
uint32_t Index32
Definition: Types.h:52
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:1532
Tree()
Definition: Tree.h:202
ValueConverter<T>::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:197
MergePolicy
Definition: Types.h:467
const ValueType & min() const
Return the minimum value.
Definition: Stats.h:60
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:1397
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
Functions to count tiles, nodes or voxels in a grid.
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
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1195
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:1516
bool isType() const
Return true if this tree is of the same type as the template parameter.
Definition: Tree.h:55
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)
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1183
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1002
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:977
RootNodeType & root()
Return this tree&#39;s root node.
Definition: Tree.h:281
tree::TreeBase TreeBase
Definition: Grid.h:26
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:1497
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1092
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:1827
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:1469
Index32 nonLeafCount() const override
Return the number of non-leaf nodes.
Definition: Tree.h:351
std::shared_ptr< T > SharedPtr
Definition: Types.h:114
tbb::concurrent_hash_map< ValueAccessorBase< Tree, true > *, bool > AccessorRegistry
Definition: Tree.h:1015
Definition: Exceptions.h:61
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:1421
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:935
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
~Tree() override
Definition: Tree.h:263
The root node of an OpenVDB tree.
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Definition: Tree.h:609
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:644
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1698
#define OPENVDB_LOG_WARN(message)
Log a warning message of the form &#39;someVar << "some text" << ...&#39;.
Definition: logging.h:256
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1123
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:943
void getIndexRange(CoordBBox &bbox) const override
Min and max are both inclusive.
Definition: Tree.h:665
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:1100
Index64 countActiveTiles(const TreeT &tree, bool threaded=true)
Return the total number of active tiles in the tree.
Definition: Count.h:482
Index64 memUsage() const override
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:367
Tree3<T, N1, N2>::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1054
Index treeDepth() const override
Return the depth of this tree.
Definition: Tree.h:338
bool operator==(const Tree &) const
Definition: Tree.h:276
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
TreeBase::Ptr copy() const override
Return a pointer to a deep copy of this tree.
Definition: Tree.h:266
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
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:942
virtual Metadata::Ptr getBackgroundValue() const
Return this tree&#39;s background value wrapped as metadata.
Definition: Tree.h:65
typename RootNodeType::ValueType ValueType
Definition: Tree.h:184
static Metadata::Ptr createMetadata(const Name &typeName)
Create new metadata of the given type.
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:996
ValueOnIter beginValueOn()
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:995
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:950
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:529
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
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
Index32 leafCount() const override
Return the number of leaf nodes.
Definition: Tree.h:340
ValueType combine(const ValueType &v0, const ValueType &v1, const ValueType &v2, const openvdb::Vec3d &w)
Combine different value types.
Definition: AttributeTransferUtil.h:141
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1702
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:207
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:991
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:1524
Definition: Types.h:469
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1700
#define OPENVDB_DEPRECATED_MESSAGE(msg)
Definition: Platform.h:125
std::string Name
Definition: Name.h:17
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1147
const AValueType & result() const
Get the output value.
Definition: Types.h:574
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1039