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