33 #ifndef OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
34 #define OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
39 #include <boost/shared_ptr.hpp>
40 #include <boost/cstdint.hpp>
41 #include <tbb/atomic.h>
42 #include <tbb/concurrent_hash_map.h>
43 #include <openvdb/Types.h>
44 #include <openvdb/metadata/Metadata.h>
45 #include <openvdb/math/Math.h>
46 #include <openvdb/math/BBox.h>
47 #include <openvdb/util/Formats.h>
48 #include <openvdb/util/logging.h>
49 #include <openvdb/Platform.h>
66 typedef boost::shared_ptr<TreeBase>
Ptr;
67 typedef boost::shared_ptr<const TreeBase>
ConstPtr;
73 virtual const Name& type()
const = 0;
76 virtual Name valueType()
const = 0;
95 virtual bool evalLeafBoundingBox(CoordBBox& bbox)
const = 0;
100 virtual bool evalLeafDim(Coord& dim)
const = 0;
109 virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox)
const = 0;
114 virtual bool evalActiveVoxelDim(Coord& dim)
const = 0;
116 virtual void getIndexRange(CoordBBox& bbox)
const = 0;
118 #ifndef OPENVDB_2_ABI_COMPATIBLE
119 virtual void clipUnallocatedNodes() = 0;
134 virtual Index treeDepth()
const = 0;
136 virtual Index32 leafCount()
const = 0;
138 virtual Index32 nonLeafCount()
const = 0;
140 virtual Index64 activeLeafVoxelCount()
const = 0;
142 virtual Index64 inactiveLeafVoxelCount()
const = 0;
144 virtual Index64 activeVoxelCount()
const = 0;
146 virtual Index64 inactiveVoxelCount()
const = 0;
147 #ifndef OPENVDB_2_ABI_COMPATIBLE
148 virtual Index64 activeTileCount()
const = 0;
162 virtual void readTopology(std::istream&,
bool saveFloatAsHalf =
false);
166 virtual void writeTopology(std::ostream&,
bool saveFloatAsHalf =
false)
const;
169 virtual void readBuffers(std::istream&,
bool saveFloatAsHalf =
false) = 0;
170 #ifndef OPENVDB_2_ABI_COMPATIBLE
171 virtual void readBuffers(std::istream&,
const CoordBBox&,
bool saveFloatAsHalf =
false) = 0;
178 virtual void readNonresidentBuffers()
const = 0;
180 virtual void writeBuffers(std::ostream&,
bool saveFloatAsHalf =
false)
const = 0;
190 virtual void print(std::ostream& os = std::cout,
int verboseLevel = 1)
const;
202 template<
typename _RootNodeType>
206 typedef boost::shared_ptr<Tree>
Ptr;
213 static const Index DEPTH = RootNodeType::LEVEL + 1;
221 template<
typename OtherValueType>
240 template<
typename OtherRootType>
255 template<
typename OtherTreeType>
256 Tree(
const OtherTreeType& other,
257 const ValueType& inactiveValue,
258 const ValueType& activeValue,
261 mRoot(other.root(), inactiveValue, activeValue,
TopologyCopy())
276 template<
typename OtherTreeType>
284 Tree(
const ValueType& background): mRoot(background) {}
286 virtual ~Tree() { releaseAllAccessors(); }
295 static const Name& treeType();
297 virtual const Name&
type()
const {
return this->treeType(); }
303 RootNodeType& root() {
return mRoot; }
305 const RootNodeType&
root()
const {
return mRoot; }
314 template<
typename OtherRootNodeType>
317 virtual bool evalLeafBoundingBox(CoordBBox& bbox)
const;
318 virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox)
const;
319 virtual bool evalActiveVoxelDim(Coord& dim)
const;
320 virtual bool evalLeafDim(Coord& dim)
const;
325 static void getNodeLog2Dims(std::vector<Index>& dims);
334 virtual void readTopology(std::istream&,
bool saveFloatAsHalf =
false);
338 virtual void writeTopology(std::ostream&,
bool saveFloatAsHalf =
false)
const;
340 virtual void readBuffers(std::istream&,
bool saveFloatAsHalf =
false);
341 #ifndef OPENVDB_2_ABI_COMPATIBLE
342 virtual void readBuffers(std::istream&,
const CoordBBox&,
bool saveFloatAsHalf =
false);
349 virtual void readNonresidentBuffers()
const;
351 virtual void writeBuffers(std::ostream&,
bool saveFloatAsHalf =
false)
const;
354 virtual void print(std::ostream& os = std::cout,
int verboseLevel = 1)
const;
375 virtual Index64 inactiveVoxelCount()
const;
380 void evalMinMax(ValueType &
min, ValueType &
max)
const;
389 const ValueType& getValue(
const Coord& xyz)
const;
392 template<
typename AccessT>
const ValueType& getValue(
const Coord& xyz, AccessT&)
const;
397 int getValueDepth(
const Coord& xyz)
const;
400 void setActiveState(
const Coord& xyz,
bool on);
402 void setValueOnly(
const Coord& xyz,
const ValueType& value);
404 void setValueOn(
const Coord& xyz);
406 void setValueOn(
const Coord& xyz,
const ValueType& value);
408 void setValue(
const Coord& xyz,
const ValueType& value);
411 template<
typename AccessT>
void setValue(
const Coord& xyz,
const ValueType& value, AccessT&);
413 void setValueOff(
const Coord& xyz);
415 void setValueOff(
const Coord& xyz,
const ValueType& value);
435 template<
typename ModifyOp>
436 void modifyValue(
const Coord& xyz,
const ModifyOp& op);
457 template<
typename ModifyOp>
458 void modifyValueAndActiveState(
const Coord& xyz,
const ModifyOp& op);
462 bool probeValue(
const Coord& xyz, ValueType& value)
const;
465 bool isValueOn(
const Coord& xyz)
const {
return mRoot.isValueOn(xyz); }
467 bool isValueOff(
const Coord& xyz)
const {
return !this->isValueOn(xyz); }
472 void clip(
const CoordBBox&);
474 #ifndef OPENVDB_2_ABI_COMPATIBLE
475 virtual void clipUnallocatedNodes();
492 void fill(
const CoordBBox& bbox,
const ValueType& value,
bool active =
true);
498 void prune(
const ValueType& tolerance = zeroVal<ValueType>())
500 this->clearAllAccessors();
501 mRoot.prune(tolerance);
506 void addLeaf(LeafNodeType& leaf) { mRoot.addLeaf(&leaf); }
512 void addTile(
Index level,
const Coord& xyz,
const ValueType& value,
bool active);
518 template<
typename NodeT>
519 NodeT* stealNode(
const Coord& xyz,
const ValueType& value,
bool active);
526 LeafNodeType* touchLeaf(
const Coord& xyz);
529 template<
typename NodeType> NodeType* probeNode(
const Coord& xyz);
532 template<
typename NodeType>
const NodeType* probeConstNode(
const Coord& xyz)
const;
533 template<
typename NodeType>
const NodeType* probeNode(
const Coord& xyz)
const;
537 LeafNodeType* probeLeaf(
const Coord& xyz);
540 const LeafNodeType* probeConstLeaf(
const Coord& xyz)
const;
541 const LeafNodeType*
probeLeaf(
const Coord& xyz)
const {
return this->probeConstLeaf(xyz); }
545 template<
typename ArrayT>
void getNodes(ArrayT& array) { mRoot.getNodes(array); }
568 template<
typename ArrayT>
void getNodes(ArrayT& array)
const { mRoot.getNodes(array); }
594 template<
typename ArrayT>
596 template<
typename ArrayT>
597 void stealNodes(ArrayT& array,
const ValueType& value,
bool state)
599 mRoot.stealNodes(array, value, state);
607 bool empty()
const {
return mRoot.empty(); }
610 void clear() { this->clearAllAccessors(); mRoot.clear(); }
613 void clearAllAccessors();
649 const ValueType&
background()
const {
return mRoot.background(); }
652 virtual void getIndexRange(CoordBBox& bbox)
const { mRoot.getIndexRange(bbox); }
655 void voxelizeActiveTiles();
679 template<
typename OtherRootNodeType>
695 template<
typename OtherRootNodeType>
708 template<
typename OtherRootNodeType>
755 template<
typename CombineOp>
756 void combine(
Tree& other, CombineOp& op,
bool prune =
false);
758 template<
typename CombineOp>
759 void combine(
Tree& other,
const CombineOp& op,
bool prune =
false);
800 template<
typename ExtendedCombineOp>
801 void combineExtended(
Tree& other, ExtendedCombineOp& op,
bool prune =
false);
803 template<
typename ExtendedCombineOp>
804 void combineExtended(
Tree& other,
const ExtendedCombineOp& op,
bool prune =
false);
835 template<
typename CombineOp,
typename OtherTreeType >
836 void combine2(
const Tree& a,
const OtherTreeType& b, CombineOp& op,
bool prune =
false);
838 template<
typename CombineOp,
typename OtherTreeType >
839 void combine2(
const Tree& a,
const OtherTreeType& b,
const CombineOp& op,
bool prune =
false);
915 template<
typename ExtendedCombineOp,
typename OtherTreeType >
916 void combine2Extended(
const Tree& a,
const OtherTreeType& b, ExtendedCombineOp& op,
919 template<
typename ExtendedCombineOp,
typename OtherTreeType >
920 void combine2Extended(
const Tree& a,
const OtherTreeType& b,
const ExtendedCombineOp&,
964 template<
typename BBoxOp>
void visitActiveBBox(BBoxOp& op)
const { mRoot.visitActiveBBox(op); }
1019 template<
typename VisitorOp>
void visit(VisitorOp& op);
1020 template<
typename VisitorOp>
void visit(
const VisitorOp& op);
1026 template<
typename VisitorOp>
void visit(VisitorOp& op)
const;
1027 template<
typename VisitorOp>
void visit(
const VisitorOp& op)
const;
1076 template<
typename OtherTreeType,
typename VisitorOp>
1077 void visit2(OtherTreeType& other, VisitorOp& op);
1078 template<
typename OtherTreeType,
typename VisitorOp>
1079 void visit2(OtherTreeType& other,
const VisitorOp& op);
1091 template<
typename OtherTreeType,
typename VisitorOp>
1092 void visit2(OtherTreeType& other, VisitorOp& op)
const;
1093 template<
typename OtherTreeType,
typename VisitorOp>
1094 void visit2(OtherTreeType& other,
const VisitorOp& op)
const;
1101 typename RootNodeType::ChildOnCIter beginRootChildren()
const {
return mRoot.cbeginChildOn(); }
1108 typename RootNodeType::ChildOffCIter beginRootTiles()
const {
return mRoot.cbeginChildOff(); }
1110 typename RootNodeType::ChildOffCIter
cbeginRootTiles()
const {
return mRoot.cbeginChildOff(); }
1111 typename RootNodeType::ChildOffIter
beginRootTiles() {
return mRoot.beginChildOff(); }
1115 typename RootNodeType::ChildAllCIter beginRootDense()
const {
return mRoot.cbeginChildAll(); }
1117 typename RootNodeType::ChildAllCIter
cbeginRootDense()
const {
return mRoot.cbeginChildAll(); }
1118 typename RootNodeType::ChildAllIter
beginRootDense() {
return mRoot.beginChildAll(); }
1135 NodeIter beginNode() {
return NodeIter(*
this); }
1142 LeafIter beginLeaf() {
return LeafIter(*
this); }
1156 ValueAllIter beginValueAll() {
return ValueAllIter(*
this); }
1162 ValueOnIter beginValueOn() {
return ValueOnIter(*
this); }
1168 ValueOffIter beginValueOff() {
return ValueOffIter(*
this); }
1176 template<
typename IterT> IterT begin();
1179 template<
typename CIterT> CIterT cbegin()
const;
1191 void releaseAllAccessors();
1204 template<
typename _RootNodeType>
1212 template<
typename T, Index N1=4, Index N2=3>
1222 template<
typename T, Index N1=5, Index N2=4, Index N3=3>
1231 template<
typename T, Index N1=6, Index N2=5, Index N3=4, Index N4=3>
1244 int32_t bufferCount;
1245 is.read(reinterpret_cast<char*>(&bufferCount),
sizeof(int32_t));
1246 if (bufferCount != 1)
OPENVDB_LOG_WARN(
"multi-buffer trees are no longer supported");
1253 int32_t bufferCount = 1;
1254 os.write(reinterpret_cast<char*>(&bufferCount),
sizeof(int32_t));
1261 os <<
" Tree Type: " << type()
1262 <<
" Active Voxel Count: " << activeVoxelCount() << std::endl
1263 <<
" Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1264 <<
" Leaf Node Count: " << leafCount() << std::endl
1265 <<
" Non-leaf Node Count: " << nonLeafCount() << std::endl;
1280 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1281 static typename TreeT::RootNodeType::ChildOnIter
begin(TreeT& tree) {
1282 return tree.beginRootChildren();
1286 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1287 static typename TreeT::RootNodeType::ChildOnCIter
begin(
const TreeT& tree) {
1288 return tree.cbeginRootChildren();
1292 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1293 static typename TreeT::RootNodeType::ChildOffIter
begin(TreeT& tree) {
1294 return tree.beginRootTiles();
1298 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1299 static typename TreeT::RootNodeType::ChildOffCIter
begin(
const TreeT& tree) {
1300 return tree.cbeginRootTiles();
1304 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1305 static typename TreeT::RootNodeType::ChildAllIter
begin(TreeT& tree) {
1306 return tree.beginRootDense();
1310 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1311 static typename TreeT::RootNodeType::ChildAllCIter
begin(
const TreeT& tree) {
1312 return tree.cbeginRootDense();
1317 static typename TreeT::NodeIter
begin(TreeT& tree) {
return tree.beginNode(); }
1321 static typename TreeT::NodeCIter
begin(
const TreeT& tree) {
return tree.cbeginNode(); }
1325 static typename TreeT::LeafIter
begin(TreeT& tree) {
return tree.beginLeaf(); }
1329 static typename TreeT::LeafCIter
begin(
const TreeT& tree) {
return tree.cbeginLeaf(); }
1333 static typename TreeT::ValueOnIter
begin(TreeT& tree) {
return tree.beginValueOn(); }
1336 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1337 static typename TreeT::ValueOnCIter
begin(
const TreeT& tree) {
return tree.cbeginValueOn(); }
1340 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1341 static typename TreeT::ValueOffIter
begin(TreeT& tree) {
return tree.beginValueOff(); }
1344 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1345 static typename TreeT::ValueOffCIter
begin(
const TreeT& tree) {
return tree.cbeginValueOff(); }
1348 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1349 static typename TreeT::ValueAllIter
begin(TreeT& tree) {
return tree.beginValueAll(); }
1352 template<
typename TreeT>
struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1353 static typename TreeT::ValueAllCIter
begin(
const TreeT& tree) {
return tree.cbeginValueAll(); }
1357 template<
typename RootNodeType>
1358 template<
typename IterT>
1366 template<
typename RootNodeType>
1367 template<
typename IterT>
1378 template<
typename RootNodeType>
1382 this->clearAllAccessors();
1384 mRoot.readTopology(is, saveFloatAsHalf);
1388 template<
typename RootNodeType>
1393 mRoot.writeTopology(os, saveFloatAsHalf);
1397 template<
typename RootNodeType>
1401 this->clearAllAccessors();
1402 mRoot.readBuffers(is, saveFloatAsHalf);
1406 #ifndef OPENVDB_2_ABI_COMPATIBLE
1408 template<
typename RootNodeType>
1412 this->clearAllAccessors();
1413 mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1417 template<
typename RootNodeType>
1421 for (
LeafCIter it = this->cbeginLeaf(); it; ++it) {
1427 #endif // !OPENVDB_2_ABI_COMPATIBLE
1430 template<
typename RootNodeType>
1441 template<
typename RootNodeType>
1445 typename AccessorRegistry::accessor a;
1446 mAccessorRegistry.insert(a, &accessor);
1450 template<
typename RootNodeType>
1454 typename ConstAccessorRegistry::accessor a;
1455 mConstAccessorRegistry.insert(a, &accessor);
1459 template<
typename RootNodeType>
1463 mAccessorRegistry.erase(&accessor);
1467 template<
typename RootNodeType>
1471 mConstAccessorRegistry.erase(&accessor);
1475 template<
typename RootNodeType>
1479 for (
typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1480 it != mAccessorRegistry.end(); ++it)
1482 if (it->first) it->first->
clear();
1485 for (
typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1486 it != mConstAccessorRegistry.end(); ++it)
1488 if (it->first) it->first->clear();
1493 template<
typename RootNodeType>
1497 mAccessorRegistry.erase(NULL);
1498 for (
typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1499 it != mAccessorRegistry.end(); ++it)
1501 it->first->release();
1503 mAccessorRegistry.
clear();
1505 mAccessorRegistry.erase(NULL);
1506 for (
typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1507 it != mConstAccessorRegistry.end(); ++it)
1509 it->first->release();
1511 mConstAccessorRegistry.clear();
1518 template<
typename RootNodeType>
1519 inline const typename RootNodeType::ValueType&
1526 template<
typename RootNodeType>
1527 template<
typename AccessT>
1528 inline const typename RootNodeType::ValueType&
1535 template<
typename RootNodeType>
1543 template<
typename RootNodeType>
1551 template<
typename RootNodeType>
1559 template<
typename RootNodeType>
1567 template<
typename RootNodeType>
1574 template<
typename RootNodeType>
1581 template<
typename RootNodeType>
1582 template<
typename AccessT>
1590 template<
typename RootNodeType>
1598 template<
typename RootNodeType>
1606 template<
typename RootNodeType>
1607 template<
typename ModifyOp>
1615 template<
typename RootNodeType>
1616 template<
typename ModifyOp>
1624 template<
typename RootNodeType>
1635 template<
typename RootNodeType>
1638 const ValueType& value,
bool active)
1640 mRoot.
addTile(level, xyz, value, active);
1644 template<
typename RootNodeType>
1645 template<
typename NodeT>
1649 this->clearAllAccessors();
1650 return mRoot.template stealNode<NodeT>(xyz, value, active);
1654 template<
typename RootNodeType>
1655 inline typename RootNodeType::LeafNodeType*
1662 template<
typename RootNodeType>
1663 inline typename RootNodeType::LeafNodeType*
1670 template<
typename RootNodeType>
1671 inline const typename RootNodeType::LeafNodeType*
1678 template<
typename RootNodeType>
1679 template<
typename NodeType>
1683 return mRoot.template probeNode<NodeType>(xyz);
1687 template<
typename RootNodeType>
1688 template<
typename NodeType>
1689 inline const NodeType*
1692 return this->
template probeConstNode<NodeType>(xyz);
1696 template<
typename RootNodeType>
1697 template<
typename NodeType>
1698 inline const NodeType*
1701 return mRoot.template probeConstNode<NodeType>(xyz);
1708 template<
typename RootNodeType>
1712 this->clearAllAccessors();
1713 return mRoot.clip(bbox);
1717 #ifndef OPENVDB_2_ABI_COMPATIBLE
1718 template<
typename RootNodeType>
1722 this->clearAllAccessors();
1723 for (
LeafIter it = this->beginLeaf(); it; ) {
1724 const LeafNodeType* leaf = it.getLeaf();
1726 if (!leaf->isAllocated()) {
1727 this->addTile(0, leaf->origin(), this->background(),
false);
1734 template<
typename RootNodeType>
1738 this->clearAllAccessors();
1739 return mRoot.fill(bbox, value, active);
1743 template<
typename RootNodeType>
1751 if (result->typeName() == MetadataT::staticTypeName()) {
1752 MetadataT* m =
static_cast<MetadataT*
>(result.get());
1753 m->value() = mRoot.background();
1763 template<
typename RootNodeType>
1767 this->clearAllAccessors();
1768 mRoot.voxelizeActiveTiles();
1772 template<
typename RootNodeType>
1776 this->clearAllAccessors();
1780 mRoot.template merge<MERGE_ACTIVE_STATES>(other.
mRoot);
break;
1782 mRoot.template merge<MERGE_NODES>(other.
mRoot);
break;
1784 mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.
mRoot);
break;
1789 template<
typename RootNodeType>
1790 template<
typename OtherRootNodeType>
1794 this->clearAllAccessors();
1795 mRoot.topologyUnion(other.
root());
1798 template<
typename RootNodeType>
1799 template<
typename OtherRootNodeType>
1803 this->clearAllAccessors();
1804 mRoot.topologyIntersection(other.
root());
1807 template<
typename RootNodeType>
1808 template<
typename OtherRootNodeType>
1812 this->clearAllAccessors();
1813 mRoot.topologyDifference(other.
root());
1821 template<
typename AValueT,
typename CombineOp,
typename BValueT = AValueT>
1827 op(args.
a(), args.
b(), args.
result());
1834 template<
typename RootNodeType>
1835 template<
typename CombineOp>
1840 this->combineExtended(other, extendedOp, prune);
1847 template<
typename RootNodeType>
1848 template<
typename CombineOp>
1853 this->combineExtended(other, extendedOp, prune);
1858 template<
typename RootNodeType>
1859 template<
typename ExtendedCombineOp>
1863 this->clearAllAccessors();
1871 template<
typename RootNodeType>
1872 template<
typename ExtendedCombineOp>
1876 this->clearAllAccessors();
1877 mRoot.template combine<const ExtendedCombineOp>(other.
mRoot, op,
prune);
1882 template<
typename RootNodeType>
1883 template<
typename CombineOp,
typename OtherTreeType>
1888 this->combine2Extended(a, b, extendedOp, prune);
1895 template<
typename RootNodeType>
1896 template<
typename CombineOp,
typename OtherTreeType>
1901 this->combine2Extended(a, b, extendedOp, prune);
1906 template<
typename RootNodeType>
1907 template<
typename ExtendedCombineOp,
typename OtherTreeType>
1910 ExtendedCombineOp& op,
bool prune)
1912 this->clearAllAccessors();
1913 mRoot.combine2(a.
root(), b.root(), op,
prune);
1921 template<
typename RootNodeType>
1922 template<
typename ExtendedCombineOp,
typename OtherTreeType>
1925 const ExtendedCombineOp& op,
bool prune)
1927 this->clearAllAccessors();
1928 mRoot.template combine2<const ExtendedCombineOp>(a.
root(), b.root(), op,
prune);
1936 template<
typename RootNodeType>
1937 template<
typename VisitorOp>
1941 this->clearAllAccessors();
1942 mRoot.template visit<VisitorOp>(op);
1946 template<
typename RootNodeType>
1947 template<
typename VisitorOp>
1951 mRoot.template visit<VisitorOp>(op);
1957 template<
typename RootNodeType>
1958 template<
typename VisitorOp>
1962 this->clearAllAccessors();
1963 mRoot.template visit<const VisitorOp>(op);
1969 template<
typename RootNodeType>
1970 template<
typename VisitorOp>
1974 mRoot.template visit<const VisitorOp>(op);
1981 template<
typename RootNodeType>
1982 template<
typename OtherTreeType,
typename VisitorOp>
1986 this->clearAllAccessors();
1987 typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1988 mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
1992 template<
typename RootNodeType>
1993 template<
typename OtherTreeType,
typename VisitorOp>
1997 typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1998 mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
2004 template<
typename RootNodeType>
2005 template<
typename OtherTreeType,
typename VisitorOp>
2009 this->clearAllAccessors();
2010 typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
2011 mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2017 template<
typename RootNodeType>
2018 template<
typename OtherTreeType,
typename VisitorOp>
2022 typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
2023 mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2030 template<
typename RootNodeType>
2034 if (sTreeTypeName == NULL) {
2035 std::vector<Index> dims;
2036 Tree::getNodeLog2Dims(dims);
2037 std::ostringstream ostr;
2038 ostr <<
"Tree_" << typeNameAsString<ValueType>();
2039 for (
size_t i = 1, N = dims.size(); i < N; ++i) {
2040 ostr <<
"_" << dims[i];
2043 if (sTreeTypeName.compare_and_swap(s, NULL) != NULL)
delete s;
2045 return *sTreeTypeName;
2049 template<
typename RootNodeType>
2050 template<
typename OtherRootNodeType>
2058 template<
typename RootNodeType>
2063 this->evalActiveVoxelDim(dim);
2065 totalVoxels = dim.x() * dim.y() * dim.z(),
2066 activeVoxels = this->activeVoxelCount();
2067 assert(totalVoxels >= activeVoxels);
2068 return totalVoxels - activeVoxels;
2072 template<
typename RootNodeType>
2078 if (this->empty())
return false;
2080 mRoot.evalActiveBoundingBox(bbox,
false);
2085 template<
typename RootNodeType>
2091 if (this->empty())
return false;
2093 mRoot.evalActiveBoundingBox(bbox,
true);
2099 template<
typename RootNodeType>
2104 bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
2105 dim = bbox.extents();
2110 template<
typename RootNodeType>
2115 bool notEmpty = this->evalLeafBoundingBox(bbox);
2116 dim = bbox.extents();
2121 template<
typename RootNodeType>
2125 minVal = maxVal = zeroVal<ValueType>();
2127 minVal = maxVal = *iter;
2128 for (++iter; iter; ++iter) {
2129 const ValueType& val = *iter;
2130 if (val < minVal) minVal = val;
2131 if (val > maxVal) maxVal = val;
2137 template<
typename RootNodeType>
2142 RootNodeType::getNodeLog2Dims(dims);
2146 template<
typename RootNodeType>
2150 if (verboseLevel <= 0)
return;
2155 std::streamsize savedPrecision;
2156 OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
2157 ~OnExit() { os.precision(savedPrecision); }
2159 OnExit restorePrecision(os);
2161 std::vector<Index> dims;
2162 Tree::getNodeLog2Dims(dims);
2164 os <<
"Information about Tree:\n"
2165 <<
" Type: " << this->type() <<
"\n";
2167 os <<
" Configuration:\n";
2169 if (verboseLevel <= 1) {
2171 os <<
" Root(" << mRoot.getTableSize() <<
")";
2172 if (dims.size() > 1) {
2173 for (
size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2174 os <<
", Internal(" << (1 << dims[i]) <<
"^3)";
2176 os <<
", Leaf(" << (1 << *dims.rbegin()) <<
"^3)\n";
2178 os <<
" Background value: " << mRoot.background() <<
"\n";
2184 ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
2185 if (verboseLevel > 3) {
2187 this->evalMinMax(minVal, maxVal);
2190 std::vector<Index64> nodeCount(dims.size());
2191 #ifndef OPENVDB_2_ABI_COMPATIBLE
2192 Index64 unallocatedLeafCount = 0;
2194 for (
NodeCIter it = cbeginNode(); it; ++it) {
2195 ++(nodeCount[it.getDepth()]);
2197 #ifndef OPENVDB_2_ABI_COMPATIBLE
2198 if (it.getLevel() == 0) {
2199 const LeafNodeType* leaf = NULL;
2201 if (leaf && !leaf->isAllocated()) ++unallocatedLeafCount;
2206 for (
size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
2209 os <<
" Root(1 x " << mRoot.getTableSize() <<
")";
2210 if (dims.size() > 1) {
2211 for (
size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2213 os <<
" x " << (1 << dims[i]) <<
"^3)";
2216 os <<
" x " << (1 << *dims.rbegin()) <<
"^3)\n";
2218 os <<
" Background value: " << mRoot.background() <<
"\n";
2222 if (verboseLevel > 3) {
2223 os <<
" Min value: " << minVal <<
"\n";
2224 os <<
" Max value: " << maxVal <<
"\n";
2228 leafCount = *nodeCount.rbegin(),
2229 numActiveVoxels = this->activeVoxelCount(),
2230 numActiveLeafVoxels = this->activeLeafVoxelCount();
2235 uint64_t totalVoxels = 0;
2236 if (numActiveVoxels) {
2238 this->evalActiveVoxelBoundingBox(bbox);
2239 dim = bbox.extents();
2240 totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2242 os <<
" Bounding box of active voxels: " << bbox <<
"\n";
2243 os <<
" Dimensions of active voxels: "
2244 << dim[0] <<
" x " << dim[1] <<
" x " << dim[2] <<
"\n";
2246 const double activeRatio = (100.0 * double(numActiveVoxels)) /
double(totalVoxels);
2247 os <<
" Percentage of active voxels: " << std::setprecision(3) << activeRatio <<
"%\n";
2249 if (leafCount > 0) {
2250 const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2251 / (
double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2252 os <<
" Average leaf node fill ratio: " << fillRatio <<
"%\n";
2255 #ifndef OPENVDB_2_ABI_COMPATIBLE
2256 if (verboseLevel > 2) {
2257 os <<
" Number of unallocated nodes: "
2259 << (100.0 * double(unallocatedLeafCount) / double(totalNodeCount)) <<
"%)\n";
2263 os <<
" Tree is empty!\n";
2267 if (verboseLevel == 2)
return;
2271 actualMem = this->memUsage(),
2272 denseMem =
sizeof(ValueType) * totalVoxels,
2273 voxelsMem =
sizeof(ValueType) * numActiveLeafVoxels;
2276 os <<
"Memory footprint:\n";
2280 if (numActiveVoxels) {
2282 os <<
" Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2283 <<
"% of an equivalent dense volume\n";
2284 os <<
" Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2285 <<
"% of actual footprint\n";
2293 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
Tree5::Type is the type of a five-level tree (Root, Internal, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
Definition: Tree.h:1232
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1242
virtual Name valueType() const
Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
Definition: Tree.h:292
virtual Index64 activeVoxelCount() const
Return the total number of active voxels.
Definition: Tree.h:373
virtual ~TreeBase()
Definition: Tree.h:70
virtual Index64 inactiveLeafVoxelCount() const
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:371
Index32 Index
Definition: Types.h:58
TreeBase()
Definition: Tree.h:69
const BValueType & b() const
Get the B input value.
Definition: Types.h:331
virtual const Name & type() const
Return the name of this type of tree.
Definition: Tree.h:297
boost::shared_ptr< const TreeBase > ConstPtr
Definition: Tree.h:67
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:277
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:153
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:382
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:658
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOnIter > ValueOnIter
Definition: Tree.h:1150
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1333
bool operator!=(const Tree &) const
Definition: Tree.h:300
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:230
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOnCIter > ValueOnCIter
Definition: Tree.h:1151
tbb::concurrent_hash_map< ValueAccessorBase< Tree, true > *, bool > AccessorRegistry
Definition: Tree.h:1183
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:610
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1117
TreeValueIteratorBase< Tree, typename RootNodeType::ValueAllIter > ValueAllIter
Definition: Tree.h:1148
Tree< RootNode< InternalNode< InternalNode< LeafNode< T, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1224
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOffIter > ValueOffIter
Definition: Tree.h:1152
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1165
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:469
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:465
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1477
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
void releaseAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:637
MergePolicy
Definition: Types.h:257
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:1537
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1170
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1118
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1251
void visitActiveBBox(BBoxOp &op) const
Use sparse traversal to call the given functor with bounding box information for all active tiles and...
Definition: Tree.h:964
virtual Index32 nonLeafCount() const
Return the number of non-leaf nodes.
Definition: Tree.h:367
uint32_t Index32
Definition: Types.h:56
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: Tree.h:1672
boost::shared_ptr< const Tree > ConstPtr
Definition: Tree.h:207
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1311
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: Tree.h:1656
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1278
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1321
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:467
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1131
boost::shared_ptr< TreeBase > Ptr
Definition: Tree.h:66
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:1609
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1138
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:130
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1171
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:1104
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1353
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:2052
RootNodeType::ValueType ValueType
Definition: Tree.h:210
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1164
Index64 activeTileCount() const
Return the total number of active tiles.
Definition: Tree.h:377
Tree4::Type is the type of a four-level tree (Root, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2 and N3, respectively.
Definition: Tree.h:1223
CombineOp & op
Definition: Tree.h:1830
Base class for typed trees.
Definition: Tree.h:63
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOffCIter > ValueOffCIter
Definition: Tree.h:1153
const AValueType & a() const
Get the A input value.
Definition: Types.h:329
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: Tree.h:1664
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1325
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1281
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: Tree.h:1592
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:506
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1349
Tree< typename RootNodeType::template ValueConverter< OtherValueType >::Type > Type
Definition: Tree.h:223
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1305
Internal table nodes for OpenVDB trees.
RootNodeType mRoot
Definition: Tree.h:1197
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1317
#define OPENVDB_VERSION_NAME
Definition: version.h:43
static tbb::atomic< const Name * > sTreeTypeName
Definition: Tree.h:1201
const LeafNodeType * probeLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return NULL.
Definition: Tree.h:541
virtual TreeBase::Ptr copy() const
Return a pointer to a deep copy of this tree.
Definition: Tree.h:289
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1626
Tree< RootNode< InternalNode< InternalNode< InternalNode< LeafNode< T, N4 >, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1234
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:977
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1826
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:498
#define OPENVDB_LOG_WARN(message)
Log a warning message of the form 'someVar << "some text" << ...'.
Definition: logging.h:39
NodeIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > NodeCIter
Iterator over all nodes in this tree.
Definition: Tree.h:1125
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:241
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1824
const ValueType & background() const
Return this tree's background value.
Definition: Tree.h:649
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1293
std::string Name
Definition: Name.h:44
Definition: Exceptions.h:39
Tree3::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1213
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1299
virtual Index treeDepth() const
Return the depth of this tree.
Definition: Tree.h:363
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:595
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1198
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:1637
RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:211
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1159
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1144
tbb::concurrent_hash_map< ValueAccessorBase< const Tree, true > *, bool > ConstAccessorRegistry
Definition: Tree.h:1184
OPENVDB_API int printBytes(std::ostream &os, uint64_t bytes, const std::string &head="", const std::string &tail="\n", bool exact=false, int width=8, int precision=3)
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1145
void attachAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:625
Tree()
Definition: Tree.h:227
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: Tree.h:1545
const AValueType & result() const
Get the output value.
Definition: Types.h:334
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1520
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:1561
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:1569
virtual Index32 leafCount() const
Return the number of leaf nodes.
Definition: Tree.h:365
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Definition: Tree.h:597
Tree(const OtherTreeType &other, const ValueType &inactiveValue, const ValueType &activeValue, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:256
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:304
_RootNodeType RootNodeType
Definition: Tree.h:209
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1329
Definition: Exceptions.h:84
bool operator==(const Tree &) const
Definition: Tree.h:299
The root node of an OpenVDB tree.
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:1576
uint64_t Index64
Definition: Types.h:57
virtual ~Tree()
Definition: Tree.h:286
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:607
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1618
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1337
ValueConverter::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:222
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1822
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:121
RootNodeType & root()
Return this tree's root node.
Definition: Tree.h:304
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1158
void getNodes(ArrayT &array) const
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:568
const RootNodeType & root() const
Return this tree's root node.
Definition: Tree.h:305
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1345
virtual void print(std::ostream &os=std::cout, int verboseLevel=1) const
Print statistics, memory usage and other information about this tree.
Definition: Tree.h:1259
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1111
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1137
virtual void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const
Write out all data buffers for this tree.
Definition: Tree.h:1432
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1110
Tree< RootNode< InternalNode< LeafNode< T, N2 >, N1 > > > Type
Definition: Tree.h:1214
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1199
virtual void getIndexRange(CoordBBox &bbox) const
Min and max are both inclusive.
Definition: Tree.h:652
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1341
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:284
boost::shared_ptr< Tree > Ptr
Definition: Tree.h:206
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueAllCIter > ValueAllCIter
Definition: Tree.h:1149
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1287
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1103
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1228
virtual Index64 activeLeafVoxelCount() const
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:369
virtual Metadata::Ptr getBackgroundValue() const
Return this tree's background value wrapped as metadata.
Definition: Tree.h:86