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