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