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