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