OpenVDB 10.0.1
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>
199 };
200
201
202 Tree() {}
203
204 Tree& operator=(const Tree&) = delete; // disallow assignment
205
206 /// Deep copy constructor
207 Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
208 {
209 }
210
211 /// @brief Value conversion deep copy constructor
212 ///
213 /// Deep copy a tree of the same configuration as this tree type but a different
214 /// ValueType, casting the other tree's values to this tree's ValueType.
215 /// @throw TypeError if the other tree's configuration doesn't match this tree's
216 /// or if this tree's ValueType is not constructible from the other tree's ValueType.
217 template<typename OtherRootType>
218 explicit Tree(const Tree<OtherRootType>& other): TreeBase(other), mRoot(other.root())
219 {
220 }
221
222 /// @brief Topology copy constructor from a tree of a different type
223 ///
224 /// Copy the structure, i.e., the active states of tiles and voxels, of another
225 /// tree of a possibly different type, but don't copy any tile or voxel values.
226 /// Instead, initialize tiles and voxels with the given active and inactive values.
227 /// @param other a tree having (possibly) a different ValueType
228 /// @param inactiveValue background value for this tree, and the value to which
229 /// all inactive tiles and voxels are initialized
230 /// @param activeValue value to which active tiles and voxels are initialized
231 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
232 template<typename OtherTreeType>
233 Tree(const OtherTreeType& other,
234 const ValueType& inactiveValue,
235 const ValueType& activeValue,
237 TreeBase(other),
238 mRoot(other.root(), inactiveValue, activeValue, TopologyCopy())
239 {
240 }
241
242 /// @brief Topology copy constructor from a tree of a different type
243 ///
244 /// @note This topology copy constructor is generally faster than
245 /// the one that takes both a foreground and a background value.
246 ///
247 /// Copy the structure, i.e., the active states of tiles and voxels, of another
248 /// tree of a possibly different type, but don't copy any tile or voxel values.
249 /// Instead, initialize tiles and voxels with the given background value.
250 /// @param other a tree having (possibly) a different ValueType
251 /// @param background the value to which tiles and voxels are initialized
252 /// @throw TypeError if the other tree's configuration doesn't match this tree's.
253 template<typename OtherTreeType>
254 Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
255 TreeBase(other),
256 mRoot(other.root(), background, TopologyCopy())
257 {
258 }
259
260 /// Empty tree constructor
261 Tree(const ValueType& background): mRoot(background) {}
262
263 ~Tree() override { this->clear(); releaseAllAccessors(); }
264
265 /// Return a pointer to a deep copy of this tree
266 TreeBase::Ptr copy() const override { return TreeBase::Ptr(new Tree(*this)); }
267
268 /// Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
269 Name valueType() const override { return typeNameAsString<ValueType>(); }
270
271 /// Return the name of this type of tree.
272 static const Name& treeType();
273 /// Return the name of this type of tree.
274 const Name& type() const override { return this->treeType(); }
275
278
279 //@{
280 /// Return this tree's root node.
281 RootNodeType& root() { return mRoot; }
282 const RootNodeType& root() const { return mRoot; }
283 //@}
284
285
286 //
287 // Tree methods
288 //
289 /// @brief Return @c true if the given tree has the same node and active value
290 /// topology as this tree, whether or not it has the same @c ValueType.
291 template<typename OtherRootNodeType>
292 bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
293
294 bool evalLeafBoundingBox(CoordBBox& bbox) const override;
295 bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const override;
296 bool evalActiveVoxelDim(Coord& dim) const override;
297 bool evalLeafDim(Coord& dim) const override;
298
299 /// @brief Traverse the type hierarchy of nodes, and return, in @a dims, a list
300 /// of the Log2Dims of nodes in order from RootNode to LeafNode.
301 /// @note Because RootNodes are resizable, the RootNode Log2Dim is 0 for all trees.
302 static void getNodeLog2Dims(std::vector<Index>& dims);
303
304
305 //
306 // I/O methods
307 //
308 /// @brief Read the tree topology from a stream.
309 ///
310 /// This will read the tree structure and tile values, but not voxel data.
311 void readTopology(std::istream&, bool saveFloatAsHalf = false) override;
312 /// @brief Write the tree topology to a stream.
313 ///
314 /// This will write the tree structure and tile values, but not voxel data.
315 void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const override;
316 /// Read all data buffers for this tree.
317 void readBuffers(std::istream&, bool saveFloatAsHalf = false) override;
318 /// Read all of this tree's data buffers that intersect the given bounding box.
319 void readBuffers(std::istream&, const CoordBBox&, bool saveFloatAsHalf = false) override;
320 /// @brief Read all of this tree's data buffers that are not yet resident in memory
321 /// (because delayed loading is in effect).
322 /// @details If this tree was read from a memory-mapped file, this operation
323 /// disconnects the tree from the file.
324 /// @sa clipUnallocatedNodes, io::File::open, io::MappedFile
325 void readNonresidentBuffers() const override;
326 /// Write out all data buffers for this tree.
327 void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const override;
328
329 void print(std::ostream& os = std::cout, int verboseLevel = 1) const override;
330
331
332 //
333 // Statistics
334 //
335 /// @brief Return the depth of this tree.
336 ///
337 /// A tree with only a root node and leaf nodes has depth 2, for example.
338 Index treeDepth() const override { return DEPTH; }
339 /// Return the number of leaf nodes.
340 Index32 leafCount() const override { return mRoot.leafCount(); }
341 /// Return a vector with node counts. The number of nodes of type NodeType
342 /// is given as element NodeType::LEVEL in the return vector. Thus, the size
343 /// of this vector corresponds to the height (or depth) of this tree.
344 std::vector<Index32> nodeCount() const override
345 {
346 std::vector<Index32> vec(DEPTH, 0);
347 mRoot.nodeCount( vec );
348 return vec;// Named Return Value Optimization
349 }
350 /// Return the number of non-leaf nodes.
351 Index32 nonLeafCount() const override { return mRoot.nonLeafCount(); }
352 /// Return the number of active voxels stored in leaf nodes.
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) { mRoot.getNodes(array); }
580 template<typename ArrayT> void getNodes(ArrayT& array) const { mRoot.getNodes(array); }
581 //@}
582
583 /// @brief Steals all nodes of a certain type from the tree and
584 /// adds them to a container with the following API:
585 /// @code
586 /// struct ArrayT {
587 /// using value_type = ...; // the type of node to be added to the array
588 /// void push_back(value_type nodePtr); // add a node to the array
589 /// };
590 /// @endcode
591 /// @details An example of a wrapper around a c-style array is:
592 /// @code
593 /// struct MyArray {
594 /// using value_type = LeafType*;
595 /// value_type* ptr;
596 /// MyArray(value_type* array) : ptr(array) {}
597 /// void push_back(value_type leaf) { *ptr++ = leaf; }
598 ///};
599 /// @endcode
600 /// @details An example that constructs a list of pointer to all leaf nodes is:
601 /// @code
602 /// std::vector<const LeafNodeType*> array;//most std contains have the required API
603 /// array.reserve(tree.leafCount());//this is a fast preallocation.
604 /// tree.stealNodes(array);
605 /// @endcode
606 template<typename ArrayT>
607 void stealNodes(ArrayT& array) { this->clearAllAccessors(); mRoot.stealNodes(array); }
608 template<typename ArrayT>
609 void stealNodes(ArrayT& array, const ValueType& value, bool state)
610 {
611 this->clearAllAccessors();
612 mRoot.stealNodes(array, value, state);
613 }
614
615 //
616 // Aux methods
617 //
618 /// @brief Return @c true if this tree contains no nodes other than
619 /// the root node and no tiles other than background tiles.
620 bool empty() const { return mRoot.empty(); }
621
622 /// Remove all tiles from this tree and all nodes other than the root node.
623 void clear();
624
625 /// Clear all registered accessors.
626 void clearAllAccessors();
627
628 //@{
629 /// @brief Register an accessor for this tree. Registered accessors are
630 /// automatically cleared whenever one of this tree's nodes is deleted.
631 void attachAccessor(ValueAccessorBase<Tree, true>&) const;
632 void attachAccessor(ValueAccessorBase<const Tree, true>&) const;
633 //@}
634
635 //@{
636 /// Dummy implementations
639 //@}
640
641 //@{
642 /// Deregister an accessor so that it is no longer automatically cleared.
643 void releaseAccessor(ValueAccessorBase<Tree, true>&) const;
644 void releaseAccessor(ValueAccessorBase<const Tree, true>&) const;
645 //@}
646
647 //@{
648 /// Dummy implementations
651 //@}
652
653 /// @brief Return this tree's background value wrapped as metadata.
654 /// @note Query the metadata object for the value's type.
655 Metadata::Ptr getBackgroundValue() const override;
656
657 /// @brief Return this tree's background value.
658 ///
659 /// @note Use tools::changeBackground to efficiently modify the
660 /// background values. Else use tree.root().setBackground, which
661 /// is serial and hence slower.
662 const ValueType& background() const { return mRoot.background(); }
663
664 /// Min and max are both inclusive.
665 void getIndexRange(CoordBBox& bbox) const override { mRoot.getIndexRange(bbox); }
666
667 /// @brief Efficiently merge another tree into this tree using one of several schemes.
668 /// @details This operation is primarily intended to combine trees that are mostly
669 /// non-overlapping (for example, intermediate trees from computations that are
670 /// parallelized across disjoint regions of space).
671 /// @note This operation is not guaranteed to produce an optimally sparse tree.
672 /// Follow merge() with prune() for optimal sparseness.
673 /// @warning This operation always empties the other tree.
674 void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
675
676 /// @brief Union this tree's set of active values with the active values
677 /// of the other tree, whose @c ValueType may be different.
678 /// @details The resulting state of a value is active if the corresponding value
679 /// was already active OR if it is active in the other tree. Also, a resulting
680 /// value maps to a voxel if the corresponding value already mapped to a voxel
681 /// OR if it is a voxel in the other tree. Thus, a resulting value can only
682 /// map to a tile if the corresponding value already mapped to a tile
683 /// AND if it is a tile value in other tree.
684 ///
685 /// @note This operation modifies only active states, not values.
686 /// Specifically, active tiles and voxels in this tree are not changed, and
687 /// tiles or voxels that were inactive in this tree but active in the other tree
688 /// are marked as active in this tree but left with their original values.
689 ///
690 /// @note If preserveTiles is true, any active tile in this topology
691 /// will not be densified by overlapping child topology.
692 template<typename OtherRootNodeType>
693 void topologyUnion(const Tree<OtherRootNodeType>& other, const bool preserveTiles = false);
694
695 /// @brief Intersects this tree's set of active values with the active values
696 /// of the other tree, whose @c ValueType may be different.
697 /// @details The resulting state of a value is active only if the corresponding
698 /// value was already active AND if it is active in the other tree. Also, a
699 /// resulting value maps to a voxel if the corresponding value
700 /// already mapped to an active voxel in either of the two grids
701 /// and it maps to an active tile or voxel in the other grid.
702 ///
703 /// @note This operation can delete branches in this grid if they
704 /// overlap with inactive tiles in the other grid. Likewise active
705 /// voxels can be turned into inactive voxels resulting in leaf
706 /// nodes with no active values. Thus, it is recommended to
707 /// subsequently call tools::pruneInactive.
708 template<typename OtherRootNodeType>
709 void topologyIntersection(const Tree<OtherRootNodeType>& other);
710
711 /// @brief Difference this tree's set of active values with the active values
712 /// of the other tree, whose @c ValueType may be different. So a
713 /// resulting voxel will be active only if the original voxel is
714 /// active in this tree and inactive in the other tree.
715 ///
716 /// @note This operation can delete branches in this grid if they
717 /// overlap with active tiles in the other grid. Likewise active
718 /// voxels can be turned into inactive voxels resulting in leaf
719 /// nodes with no active values. Thus, it is recommended to
720 /// subsequently call tools::pruneInactive.
721 template<typename OtherRootNodeType>
722 void topologyDifference(const Tree<OtherRootNodeType>& other);
723
724 /// For a given function @c f, use sparse traversal to compute <tt>f(this, other)</tt>
725 /// over all corresponding pairs of values (tile or voxel) of this tree and the other tree
726 /// and store the result in this tree.
727 /// This method is typically more space-efficient than the two-tree combine2(),
728 /// since it moves rather than copies nodes from the other tree into this tree.
729 /// @note This operation always empties the other tree.
730 /// @param other a tree of the same type as this tree
731 /// @param op a functor of the form <tt>void op(const T& a, const T& b, T& result)</tt>,
732 /// where @c T is this tree's @c ValueType, that computes
733 /// <tt>result = f(a, b)</tt>
734 /// @param prune if true, prune the resulting tree one branch at a time (this is usually
735 /// more space-efficient than pruning the entire tree in one pass)
736 ///
737 /// @par Example:
738 /// Compute the per-voxel difference between two floating-point trees,
739 /// @c aTree and @c bTree, and store the result in @c aTree (leaving @c bTree empty).
740 /// @code
741 /// {
742 /// struct Local {
743 /// static inline void diff(const float& a, const float& b, float& result) {
744 /// result = a - b;
745 /// }
746 /// };
747 /// aTree.combine(bTree, Local::diff);
748 /// }
749 /// @endcode
750 ///
751 /// @par Example:
752 /// Compute <tt>f * a + (1 - f) * b</tt> over all voxels of two floating-point trees,
753 /// @c aTree and @c bTree, and store the result in @c aTree (leaving @c bTree empty).
754 /// @code
755 /// namespace {
756 /// struct Blend {
757 /// Blend(float f): frac(f) {}
758 /// inline void operator()(const float& a, const float& b, float& result) const {
759 /// result = frac * a + (1.0 - frac) * b;
760 /// }
761 /// float frac;
762 /// };
763 /// }
764 /// {
765 /// aTree.combine(bTree, Blend(0.25)); // 0.25 * a + 0.75 * b
766 /// }
767 /// @endcode
768 template<typename CombineOp>
769 void combine(Tree& other, CombineOp& op, bool prune = false);
770 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
1042 static std::unique_ptr<const Name> sTreeTypeName;
1043}; // end of Tree class
1044
1045template<typename _RootNodeType>
1046std::unique_ptr<const Name> Tree<_RootNodeType>::sTreeTypeName;
1047
1048
1049/// @brief Tree3<T, N1, N2>::Type is the type of a three-level tree
1050/// (Root, Internal, Leaf) with value type T and
1051/// internal and leaf node log dimensions N1 and N2, respectively.
1052/// @note This is NOT the standard tree configuration (Tree4 is).
1053template<typename T, Index N1=4, Index N2=3>
1054struct Tree3 {
1056};
1057
1058
1059/// @brief Tree4<T, N1, N2, N3>::Type is the type of a four-level tree
1060/// (Root, Internal, Internal, Leaf) with value type T and
1061/// internal and leaf node log dimensions N1, N2 and N3, respectively.
1062/// @note This is the standard tree configuration.
1063template<typename T, Index N1=5, Index N2=4, Index N3=3>
1064struct Tree4 {
1066};
1067
1068/// @brief Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree
1069/// (Root, Internal, Internal, Internal, Leaf) with value type T and
1070/// internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
1071/// @note This is NOT the standard tree configuration (Tree4 is).
1072template<typename T, Index N1=6, Index N2=5, Index N3=4, Index N4=3>
1073struct Tree5 {
1074 using Type =
1076};
1077
1078
1079////////////////////////////////////////
1080
1081
1082inline void
1083TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1084{
1085 int32_t bufferCount;
1086 is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1087 if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1088}
1089
1090
1091inline void
1092TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1093{
1094 int32_t bufferCount = 1;
1095 os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1096}
1097
1098
1099inline void
1100TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1101{
1102 os << " Tree Type: " << type()
1103 << " Active Voxel Count: " << activeVoxelCount() << std::endl
1104 << " Active tile Count: " << activeTileCount() << std::endl
1105 << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1106 << " Leaf Node Count: " << leafCount() << std::endl
1107 << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1108}
1109
1110
1111////////////////////////////////////////
1112
1113
1114//
1115// Type traits for tree iterators
1116//
1117
1118/// @brief TreeIterTraits provides, for all tree iterators, a begin(tree) function
1119/// that returns an iterator over a tree of arbitrary type.
1120template<typename TreeT, typename IterT> struct TreeIterTraits;
1121
1122template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1123 static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1124 return tree.beginRootChildren();
1125 }
1126};
1127
1128template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1129 static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1130 return tree.cbeginRootChildren();
1131 }
1132};
1133
1134template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1135 static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1136 return tree.beginRootTiles();
1137 }
1138};
1139
1140template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1141 static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1142 return tree.cbeginRootTiles();
1143 }
1144};
1145
1146template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1147 static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1148 return tree.beginRootDense();
1149 }
1150};
1151
1152template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1153 static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1154 return tree.cbeginRootDense();
1155 }
1156};
1157
1158template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1159 static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1160};
1161
1162template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1163 static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1164};
1165
1166template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1167 static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1168};
1169
1170template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1171 static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1172};
1173
1174template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1175 static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1176};
1177
1178template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1179 static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1180};
1181
1182template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1183 static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1184};
1185
1186template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1187 static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1188};
1189
1190template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1191 static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1192};
1193
1194template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1195 static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1196};
1197
1198
1199template<typename RootNodeType>
1200template<typename IterT>
1201inline IterT
1203{
1205}
1206
1207
1208template<typename RootNodeType>
1209template<typename IterT>
1210inline IterT
1212{
1214}
1215
1216
1217////////////////////////////////////////
1218
1219
1220template<typename RootNodeType>
1221void
1222Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1223{
1224 this->clearAllAccessors();
1225 TreeBase::readTopology(is, saveFloatAsHalf);
1226 mRoot.readTopology(is, saveFloatAsHalf);
1227}
1228
1229
1230template<typename RootNodeType>
1231void
1232Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1233{
1234 TreeBase::writeTopology(os, saveFloatAsHalf);
1235 mRoot.writeTopology(os, saveFloatAsHalf);
1236}
1237
1238
1239template<typename RootNodeType>
1240inline void
1241Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1242{
1243 this->clearAllAccessors();
1244 mRoot.readBuffers(is, saveFloatAsHalf);
1245}
1246
1247
1248template<typename RootNodeType>
1249inline void
1250Tree<RootNodeType>::readBuffers(std::istream &is, const CoordBBox& bbox, bool saveFloatAsHalf)
1251{
1252 this->clearAllAccessors();
1253 mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1254}
1255
1256
1257template<typename RootNodeType>
1258inline void
1260{
1261 for (LeafCIter it = this->cbeginLeaf(); it; ++it) {
1262 // Retrieving the value of a leaf voxel forces loading of the leaf node's voxel buffer.
1263 it->getValue(Index(0));
1264 }
1265}
1266
1267
1268template<typename RootNodeType>
1269inline void
1270Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1271{
1272 mRoot.writeBuffers(os, saveFloatAsHalf);
1273}
1274
1275
1276template<typename RootNodeType>
1277inline void
1279{
1280 std::vector<LeafNodeType*> leafnodes;
1281 this->stealNodes(leafnodes);
1282
1283 tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
1285
1286 std::vector<typename RootNodeType::ChildNodeType*> internalNodes;
1287 this->stealNodes(internalNodes);
1288
1289 tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
1291
1292 mRoot.clear();
1293
1294 this->clearAllAccessors();
1295}
1296
1297
1298////////////////////////////////////////
1299
1300
1301template<typename RootNodeType>
1302inline void
1304{
1305 typename AccessorRegistry::accessor a;
1306 mAccessorRegistry.insert(a, &accessor);
1307}
1308
1309
1310template<typename RootNodeType>
1311inline void
1313{
1314 typename ConstAccessorRegistry::accessor a;
1315 mConstAccessorRegistry.insert(a, &accessor);
1316}
1317
1318
1319template<typename RootNodeType>
1320inline void
1322{
1323 mAccessorRegistry.erase(&accessor);
1324}
1325
1326
1327template<typename RootNodeType>
1328inline void
1330{
1331 mConstAccessorRegistry.erase(&accessor);
1332}
1333
1334
1335template<typename RootNodeType>
1336inline void
1338{
1339 for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1340 it != mAccessorRegistry.end(); ++it)
1341 {
1342 if (it->first) it->first->clear();
1343 }
1344
1345 for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1346 it != mConstAccessorRegistry.end(); ++it)
1347 {
1348 if (it->first) it->first->clear();
1349 }
1350}
1351
1352
1353template<typename RootNodeType>
1354inline void
1356{
1357 mAccessorRegistry.erase(nullptr);
1358 for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1359 it != mAccessorRegistry.end(); ++it)
1360 {
1361 it->first->release();
1362 }
1363 mAccessorRegistry.clear();
1364
1365 mAccessorRegistry.erase(nullptr);
1366 for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1367 it != mConstAccessorRegistry.end(); ++it)
1368 {
1369 it->first->release();
1370 }
1371 mConstAccessorRegistry.clear();
1372}
1373
1374
1375////////////////////////////////////////
1376
1377
1378template<typename RootNodeType>
1379inline const typename RootNodeType::ValueType&
1381{
1382 return mRoot.getValue(xyz);
1383}
1384
1385
1386template<typename RootNodeType>
1387template<typename AccessT>
1388inline const typename RootNodeType::ValueType&
1389Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1390{
1391 return accessor.getValue(xyz);
1392}
1393
1394
1395template<typename RootNodeType>
1396inline int
1398{
1399 return mRoot.getValueDepth(xyz);
1400}
1401
1402
1403template<typename RootNodeType>
1404inline void
1406{
1407 mRoot.setValueOff(xyz);
1408}
1409
1410
1411template<typename RootNodeType>
1412inline void
1414{
1415 mRoot.setValueOff(xyz, value);
1416}
1417
1418
1419template<typename RootNodeType>
1420inline void
1422{
1423 mRoot.setActiveState(xyz, on);
1424}
1425
1426
1427template<typename RootNodeType>
1428inline void
1430{
1431 mRoot.setValueOn(xyz, value);
1432}
1433
1434template<typename RootNodeType>
1435inline void
1437{
1438 mRoot.setValueOnly(xyz, value);
1439}
1440
1441template<typename RootNodeType>
1442template<typename AccessT>
1443inline void
1444Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1445{
1446 accessor.setValue(xyz, value);
1447}
1448
1449
1450template<typename RootNodeType>
1451inline void
1453{
1454 mRoot.setActiveState(xyz, true);
1455}
1456
1457
1458template<typename RootNodeType>
1459inline void
1461{
1462 mRoot.setValueOn(xyz, value);
1463}
1464
1465
1466template<typename RootNodeType>
1467template<typename ModifyOp>
1468inline void
1469Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1470{
1471 mRoot.modifyValue(xyz, op);
1472}
1473
1474
1475template<typename RootNodeType>
1476template<typename ModifyOp>
1477inline void
1479{
1480 mRoot.modifyValueAndActiveState(xyz, op);
1481}
1482
1483
1484template<typename RootNodeType>
1485inline bool
1487{
1488 return mRoot.probeValue(xyz, value);
1489}
1490
1491
1492////////////////////////////////////////
1493
1494
1495template<typename RootNodeType>
1496inline void
1498 const ValueType& value, bool active)
1499{
1500 mRoot.addTile(level, xyz, value, active);
1501}
1502
1503
1504template<typename RootNodeType>
1505template<typename NodeT>
1506inline NodeT*
1507Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1508{
1509 this->clearAllAccessors();
1510 return mRoot.template stealNode<NodeT>(xyz, value, active);
1511}
1512
1513
1514template<typename RootNodeType>
1515inline typename RootNodeType::LeafNodeType*
1517{
1518 return mRoot.touchLeaf(xyz);
1519}
1520
1521
1522template<typename RootNodeType>
1523inline typename RootNodeType::LeafNodeType*
1525{
1526 return mRoot.probeLeaf(xyz);
1527}
1528
1529
1530template<typename RootNodeType>
1531inline const typename RootNodeType::LeafNodeType*
1533{
1534 return mRoot.probeConstLeaf(xyz);
1535}
1536
1537
1538template<typename RootNodeType>
1539template<typename NodeType>
1540inline NodeType*
1542{
1543 return mRoot.template probeNode<NodeType>(xyz);
1544}
1545
1546
1547template<typename RootNodeType>
1548template<typename NodeType>
1549inline const NodeType*
1551{
1552 return this->template probeConstNode<NodeType>(xyz);
1553}
1554
1555
1556template<typename RootNodeType>
1557template<typename NodeType>
1558inline const NodeType*
1560{
1561 return mRoot.template probeConstNode<NodeType>(xyz);
1562}
1563
1564
1565////////////////////////////////////////
1566
1567
1568template<typename RootNodeType>
1569inline void
1571{
1572 this->clearAllAccessors();
1573 return mRoot.clip(bbox);
1574}
1575
1576
1577template<typename RootNodeType>
1578inline void
1580{
1581 this->clearAllAccessors();
1582 for (LeafIter it = this->beginLeaf(); it; ) {
1583 const LeafNodeType* leaf = it.getLeaf();
1584 ++it; // advance the iterator before deleting the leaf node
1585 if (!leaf->isAllocated()) {
1586 this->addTile(/*level=*/0, leaf->origin(), this->background(), /*active=*/false);
1587 }
1588 }
1589}
1590
1591template<typename RootNodeType>
1592inline Index32
1594{
1595 Index32 sum = 0;
1596 for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
1597 return sum;
1598}
1599
1600
1601template<typename RootNodeType>
1602inline void
1604{
1605 this->clearAllAccessors();
1606 return mRoot.sparseFill(bbox, value, active);
1607}
1608
1609
1610template<typename RootNodeType>
1611inline void
1613{
1614 this->clearAllAccessors();
1615 return mRoot.denseFill(bbox, value, active);
1616}
1617
1618
1619template<typename RootNodeType>
1620inline void
1622{
1623 this->clearAllAccessors();
1624 mRoot.voxelizeActiveTiles(threaded);
1625}
1626
1627
1628template<typename RootNodeType>
1631{
1632 Metadata::Ptr result;
1633 if (Metadata::isRegisteredType(valueType())) {
1634 using MetadataT = TypedMetadata<ValueType>;
1635 result = Metadata::createMetadata(valueType());
1636 if (result->typeName() == MetadataT::staticTypeName()) {
1637 MetadataT* m = static_cast<MetadataT*>(result.get());
1638 m->value() = mRoot.background();
1639 }
1640 }
1641 return result;
1642}
1643
1644
1645////////////////////////////////////////
1646
1647
1648template<typename RootNodeType>
1649inline void
1651{
1652 this->clearAllAccessors();
1653 other.clearAllAccessors();
1654 switch (policy) {
1656 mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1657 case MERGE_NODES:
1658 mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1660 mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1661 }
1662}
1663
1664
1665template<typename RootNodeType>
1666template<typename OtherRootNodeType>
1667inline void
1668Tree<RootNodeType>::topologyUnion(const Tree<OtherRootNodeType>& other, const bool preserveTiles)
1669{
1670 this->clearAllAccessors();
1671 mRoot.topologyUnion(other.root(), preserveTiles);
1672}
1673
1674template<typename RootNodeType>
1675template<typename OtherRootNodeType>
1676inline void
1678{
1679 this->clearAllAccessors();
1680 mRoot.topologyIntersection(other.root());
1681}
1682
1683template<typename RootNodeType>
1684template<typename OtherRootNodeType>
1685inline void
1687{
1688 this->clearAllAccessors();
1689 mRoot.topologyDifference(other.root());
1690}
1691
1692////////////////////////////////////////
1693
1694
1695/// @brief Helper class to adapt a three-argument (a, b, result) CombineOp functor
1696/// into a single-argument functor that accepts a CombineArgs struct
1697template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1699{
1700 CombineOpAdapter(CombineOp& _op): op(_op) {}
1701
1703 op(args.a(), args.b(), args.result());
1704 }
1705
1706 CombineOp& op;
1707};
1708
1709
1710template<typename RootNodeType>
1711template<typename CombineOp>
1712inline void
1713Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1714{
1716 this->combineExtended(other, extendedOp, prune);
1717}
1718
1719
1720/// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1721/// code like this: <tt>aTree.combine(bTree, MyCombineOp(...))</tt>.
1722template<typename RootNodeType>
1723template<typename CombineOp>
1724inline void
1725Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1726{
1728 this->combineExtended(other, extendedOp, prune);
1729}
1730
1731
1732template<typename RootNodeType>
1733template<typename ExtendedCombineOp>
1734inline void
1735Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1736{
1737 this->clearAllAccessors();
1738 mRoot.combine(other.root(), op, prune);
1739}
1740
1741
1742/// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1743/// code like this: <tt>aTree.combineExtended(bTree, MyCombineOp(...))</tt>.
1744template<typename RootNodeType>
1745template<typename ExtendedCombineOp>
1746inline void
1747Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1748{
1749 this->clearAllAccessors();
1750 mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1751}
1752
1753
1754template<typename RootNodeType>
1755template<typename CombineOp, typename OtherTreeType>
1756inline void
1757Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1758{
1760 this->combine2Extended(a, b, extendedOp, prune);
1761}
1762
1763
1764/// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1765/// code like this: <tt>tree.combine2(aTree, bTree, MyCombineOp(...))</tt>.
1766template<typename RootNodeType>
1767template<typename CombineOp, typename OtherTreeType>
1768inline void
1769Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1770{
1772 this->combine2Extended(a, b, extendedOp, prune);
1773}
1774
1775
1776template<typename RootNodeType>
1777template<typename ExtendedCombineOp, typename OtherTreeType>
1778inline void
1779Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1780 ExtendedCombineOp& op, bool prune)
1781{
1782 this->clearAllAccessors();
1783 mRoot.combine2(a.root(), b.root(), op, prune);
1784}
1785
1786
1787/// @internal This overload is needed (for ICC and GCC, but not for VC) to disambiguate
1788/// code like the following, where the functor argument is a temporary:
1789/// <tt>tree.combine2Extended(aTree, bTree, MyCombineOp(...))</tt>.
1790template<typename RootNodeType>
1791template<typename ExtendedCombineOp, typename OtherTreeType>
1792inline void
1793Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1794 const ExtendedCombineOp& op, bool prune)
1795{
1796 this->clearAllAccessors();
1797 mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
1798}
1799
1800
1801////////////////////////////////////////
1802
1803
1804template<typename RootNodeType>
1805inline const Name&
1807{
1808 static std::once_flag once;
1809 std::call_once(once, []()
1810 {
1811 std::vector<Index> dims;
1812 Tree::getNodeLog2Dims(dims);
1813 std::ostringstream ostr;
1814 ostr << "Tree_" << typeNameAsString<BuildType>();
1815 for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1816 ostr << "_" << dims[i];
1817 }
1818 sTreeTypeName.reset(new Name(ostr.str()));
1819 });
1820 return *sTreeTypeName;
1821}
1822
1823
1824template<typename RootNodeType>
1825template<typename OtherRootNodeType>
1826inline bool
1828{
1829 return mRoot.hasSameTopology(other.root());
1830}
1831
1832
1833template<typename RootNodeType>
1834inline bool
1836{
1837 bbox.reset(); // default invalid bbox
1838
1839 if (this->empty()) return false; // empty
1840
1841 mRoot.evalActiveBoundingBox(bbox, false);
1842
1843 return !bbox.empty();
1844}
1845
1846template<typename RootNodeType>
1847inline bool
1849{
1850 bbox.reset(); // default invalid bbox
1851
1852 if (this->empty()) return false; // empty
1853
1854 mRoot.evalActiveBoundingBox(bbox, true);
1855
1856 return !bbox.empty();
1857}
1858
1859
1860template<typename RootNodeType>
1861inline bool
1863{
1864 CoordBBox bbox;
1865 bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1866 dim = bbox.extents();
1867 return notEmpty;
1868}
1869
1870
1871template<typename RootNodeType>
1872inline bool
1874{
1875 CoordBBox bbox;
1876 bool notEmpty = this->evalLeafBoundingBox(bbox);
1877 dim = bbox.extents();
1878 return notEmpty;
1879}
1880
1881
1882template<typename RootNodeType>
1883inline void
1885{
1886 minVal = maxVal = zeroVal<ValueType>();
1887 if (ValueOnCIter iter = this->cbeginValueOn()) {
1888 minVal = maxVal = *iter;
1889 for (++iter; iter; ++iter) {
1890 const ValueType& val = *iter;
1891 if (math::cwiseLessThan(val, minVal)) minVal = val;
1892 if (math::cwiseGreaterThan(val, maxVal)) maxVal = val;
1893 }
1894 }
1895}
1896
1897
1898template<typename RootNodeType>
1899inline void
1901{
1902 dims.clear();
1903 RootNodeType::getNodeLog2Dims(dims);
1904}
1905
1906
1907template<typename RootNodeType>
1908inline void
1909Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
1910{
1911 if (verboseLevel <= 0) return;
1912
1913 /// @todo Consider using boost::io::ios_precision_saver instead.
1914 struct OnExit {
1915 std::ostream& os;
1916 std::streamsize savedPrecision;
1917 OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
1918 ~OnExit() { os.precision(savedPrecision); }
1919 };
1920 OnExit restorePrecision(os);
1921
1922 std::vector<Index> dims;
1923 Tree::getNodeLog2Dims(dims);// leaf is the last element
1924
1925 os << "Information about Tree:\n"
1926 << " Type: " << this->type() << "\n";
1927
1928 os << " Configuration:\n";
1929
1930 if (verboseLevel <= 1) {
1931 // Print node types and sizes.
1932 os << " Root(" << mRoot.getTableSize() << ")";
1933 if (dims.size() > 1) {
1934 for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1935 os << ", Internal(" << (1 << dims[i]) << "^3)";
1936 }
1937 os << ", Leaf(" << (1 << dims.back()) << "^3)\n";
1938 }
1939 os << " Background value: " << mRoot.background() << "\n";
1940 return;
1941 }
1942
1943 // The following is tree information that is expensive to extract.
1944
1945 ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
1946 if (verboseLevel > 3) {
1947 // This forces loading of all non-resident nodes.
1948 const math::MinMax<ValueType> extrema = tools::minMax(*this);
1949 minVal = extrema.min();
1950 maxVal = extrema.max();
1951 }
1952
1953 const auto nodeCount = this->nodeCount();//fast
1954 const Index32 leafCount = nodeCount.front();// leaf is the first element
1955 assert(dims.size() == nodeCount.size());
1956
1957 Index64 totalNodeCount = 0;
1958 for (size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
1959
1960 // Print node types, counts and sizes.
1961 os << " Root(1 x " << mRoot.getTableSize() << ")";
1962 if (dims.size() >= 2) {
1963 for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1964 os << ", Internal(" << util::formattedInt(nodeCount[N - i]);
1965 os << " x " << (1 << dims[i]) << "^3)";
1966 }
1967 os << ", Leaf(" << util::formattedInt(leafCount);
1968 os << " x " << (1 << dims.back()) << "^3)\n";
1969 }
1970 os << " Background value: " << mRoot.background() << "\n";
1971
1972 // Statistics of topology and values
1973
1974 if (verboseLevel > 3) {
1975 os << " Min value: " << minVal << "\n";
1976 os << " Max value: " << maxVal << "\n";
1977 }
1978
1979 const Index64
1980 numActiveVoxels = this->activeVoxelCount(),
1981 numActiveLeafVoxels = this->activeLeafVoxelCount(),
1982 numActiveTiles = this->activeTileCount();
1983
1984 os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
1985 os << " Number of active tiles: " << util::formattedInt(numActiveTiles) << "\n";
1986
1987 Coord dim(0, 0, 0);
1988 Index64 totalVoxels = 0;
1989 if (numActiveVoxels) { // nonempty
1990 CoordBBox bbox;
1991 this->evalActiveVoxelBoundingBox(bbox);
1992 dim = bbox.extents();
1993 totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
1994
1995 os << " Bounding box of active voxels: " << bbox << "\n";
1996 os << " Dimensions of active voxels: "
1997 << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
1998
1999 const double activeRatio = (100.0 * double(numActiveVoxels)) / double(totalVoxels);
2000 os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2001
2002 if (leafCount > 0) {
2003 const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2004 / (double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2005 os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2006 }
2007
2008 if (verboseLevel > 2) {
2009 Index64 sum = 0;// count the number of unallocated leaf nodes
2010 for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
2011 os << " Number of unallocated nodes: "
2012 << util::formattedInt(sum) << " ("
2013 << (100.0 * double(sum) / double(totalNodeCount)) << "%)\n";
2014 }
2015 } else {
2016 os << " Tree is empty!\n";
2017 }
2018 os << std::flush;
2019
2020 if (verboseLevel == 2) return;
2021
2022 // Memory footprint in bytes
2023 const Index64
2024 actualMem = this->memUsage(),
2025 denseMem = sizeof(ValueType) * totalVoxels,
2026 voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2027 ///< @todo not accurate for BoolTree (and probably should count tile values)
2028
2029 os << "Memory footprint:\n";
2030 util::printBytes(os, actualMem, " Actual: ");
2031 util::printBytes(os, voxelsMem, " Active leaf voxels: ");
2032
2033 if (numActiveVoxels) {
2034 util::printBytes(os, denseMem, " Dense equivalent: ");
2035 os << " Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2036 << "% of an equivalent dense volume\n";
2037 os << " Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2038 << "% of actual footprint\n";
2039 }
2040}
2041
2042} // namespace tree
2043} // namespace OPENVDB_VERSION_NAME
2044} // namespace openvdb
2045
2046#endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
Functions to count tiles, nodes or voxels in a grid.
Utility routines to output nicely-formatted numeric values.
ValueT value
Definition: GridBuilder.h:1290
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:251
#define OPENVDB_DEPRECATED_MESSAGE(msg)
Definition: Platform.h:125
The root node of an OpenVDB tree.
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:530
const AValueType & result() const
Get the output value.
Definition: Types.h:574
const BValueType & b() const
Get the B input value.
Definition: Types.h:571
const AValueType & a() const
Get the A input value.
Definition: Types.h:569
SharedPtr< Metadata > Ptr
Definition: Metadata.h:26
Definition: Exceptions.h:61
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:644
Templated metadata class to hold specific types.
Definition: Metadata.h:122
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:249
Coord extents() const
Definition: Coord.h:382
bool empty() const
Return true if this bounding box is empty (i.e., encloses no coordinates).
Definition: Coord.h:356
void reset()
Definition: Coord.h:327
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:25
Int32 y() const
Definition: Coord.h:131
Int32 x() const
Definition: Coord.h:130
Int32 z() const
Definition: Coord.h:132
double min() const
Return the minimum value.
Definition: Stats.h:125
double max() const
Return the maximum value.
Definition: Stats.h:128
Templated class to compute the minimum and maximum values.
Definition: Stats.h:31
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:1397
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:1827
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:1270
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:1532
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1337
_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:579
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
static std::unique_ptr< const Name > sTreeTypeName
Definition: Tree.h:1042
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:1524
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:1516
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:1478
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:1436
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:1497
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1486
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:1421
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:1429
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:1405
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:1380
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:1469
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 getNodes(ArrayT &array) const
Definition: Tree.h:580
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Definition: Tree.h:609
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:1278
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:1452
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:93
#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:17
Index32 Index
Definition: Types.h:54
uint32_t Index32
Definition: Types.h:52
uint64_t Index64
Definition: Types.h:53
std::shared_ptr< T > SharedPtr
Definition: Types.h:114
MergePolicy
Definition: Types.h:467
@ MERGE_ACTIVE_STATES
Definition: Types.h:468
@ MERGE_NODES
Definition: Types.h:469
@ MERGE_ACTIVE_STATES_AND_NODES
Definition: Types.h:470
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:1699
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1702
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1700
CombineOp & op
Definition: Tree.h:1706
Tree3<T, N1, N2>::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1054
Tree4<T, N1, N2, N3>::Type is the type of a four-level tree (Root, Internal, Internal,...
Definition: Tree.h:1064
Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree (Root, Internal, Internal,...
Definition: Tree.h:1073
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1171
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1167
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1163
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1159
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1153
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1147
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1141
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1135
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1129
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1123
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1195
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1191
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1187
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1183
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1179
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1175
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1120
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