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