OpenVDB  3.0.0
Tree.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 //
32 
33 #ifndef OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
34 #define OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
35 
36 #include <iostream>
37 #include <sstream>
38 #include <vector>
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>
50 #include "RootNode.h"
51 #include "InternalNode.h"
52 #include "LeafNode.h"
53 #include "TreeIterator.h"
54 #include "ValueAccessor.h"
55 
56 
57 namespace openvdb {
59 namespace OPENVDB_VERSION_NAME {
60 namespace tree {
61 
64 {
65 public:
66  typedef boost::shared_ptr<TreeBase> Ptr;
67  typedef boost::shared_ptr<const TreeBase> ConstPtr;
68 
69  TreeBase() {}
70  virtual ~TreeBase() {}
71 
73  virtual const Name& type() const = 0;
74 
76  virtual Name valueType() const = 0;
77 
79  virtual TreeBase::Ptr copy() const = 0;
80 
81  //
82  // Tree methods
83  //
86  virtual Metadata::Ptr getBackgroundValue() const { return Metadata::Ptr(); }
87 
95  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const = 0;
96 
100  virtual bool evalLeafDim(Coord& dim) const = 0;
101 
109  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const = 0;
110 
114  virtual bool evalActiveVoxelDim(Coord& dim) const = 0;
115 
116  virtual void getIndexRange(CoordBBox& bbox) const = 0;
117 
118 #ifndef OPENVDB_2_ABI_COMPATIBLE
119  virtual void clipUnallocatedNodes() = 0;
125 #endif
126 
127 
128  //
129  // Statistics
130  //
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;
150 #endif
151 
153  virtual Index64 memUsage() const { return 0; }
154 
155 
156  //
157  // I/O methods
158  //
162  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
166  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
167 
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;
179 #endif
180  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const = 0;
182 
190  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
191 
192 private:
193  // Disallow copying of instances of this class.
194  //TreeBase(const TreeBase& other);
195  TreeBase& operator=(const TreeBase& other);
196 };
197 
198 
200 
201 
202 template<typename _RootNodeType>
203 class Tree: public TreeBase
204 {
205 public:
206  typedef boost::shared_ptr<Tree> Ptr;
207  typedef boost::shared_ptr<const Tree> ConstPtr;
208 
209  typedef _RootNodeType RootNodeType;
210  typedef typename RootNodeType::ValueType ValueType;
211  typedef typename RootNodeType::LeafNodeType LeafNodeType;
212 
213  static const Index DEPTH = RootNodeType::LEVEL + 1;
214 
221  template<typename OtherValueType>
222  struct ValueConverter {
224  };
225 
226 
227  Tree() {}
228 
230  Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
231  {
232  }
233 
240  template<typename OtherRootType>
241  explicit Tree(const Tree<OtherRootType>& other): TreeBase(other), mRoot(other.root())
242  {
243  }
244 
255  template<typename OtherTreeType>
256  Tree(const OtherTreeType& other,
257  const ValueType& inactiveValue,
258  const ValueType& activeValue,
259  TopologyCopy):
260  TreeBase(other),
261  mRoot(other.root(), inactiveValue, activeValue, TopologyCopy())
262  {
263  }
264 
276  template<typename OtherTreeType>
277  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
278  TreeBase(other),
279  mRoot(other.root(), background, TopologyCopy())
280  {
281  }
282 
284  Tree(const ValueType& background): mRoot(background) {}
285 
286  virtual ~Tree() { releaseAllAccessors(); }
287 
289  virtual TreeBase::Ptr copy() const { return TreeBase::Ptr(new Tree(*this)); }
290 
292  virtual Name valueType() const { return typeNameAsString<ValueType>(); }
293 
295  static const Name& treeType();
297  virtual const Name& type() const { return this->treeType(); }
298 
299  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
300  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
301 
303  RootNodeType& root() { return mRoot; }
305  const RootNodeType& root() const { return mRoot; }
307 
308 
309  //
310  // Tree methods
311  //
314  template<typename OtherRootNodeType>
315  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
316 
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;
321 
325  static void getNodeLog2Dims(std::vector<Index>& dims);
326 
327 
328  //
329  // I/O methods
330  //
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;
350 #endif
351  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const;
353 
354  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
355 
356 
357  //
358  // Statistics
359  //
363  virtual Index treeDepth() const { return DEPTH; }
365  virtual Index32 leafCount() const { return mRoot.leafCount(); }
367  virtual Index32 nonLeafCount() const { return mRoot.nonLeafCount(); }
369  virtual Index64 activeLeafVoxelCount() const { return mRoot.onLeafVoxelCount(); }
371  virtual Index64 inactiveLeafVoxelCount() const { return mRoot.offLeafVoxelCount(); }
373  virtual Index64 activeVoxelCount() const { return mRoot.onVoxelCount(); }
375  virtual Index64 inactiveVoxelCount() const;
377  Index64 activeTileCount() const { return mRoot.onTileCount(); }
378 
380  void evalMinMax(ValueType &min, ValueType &max) const;
381 
382  virtual Index64 memUsage() const { return sizeof(*this) + mRoot.memUsage(); }
383 
384 
385  //
386  // Voxel access methods (using signed indexing)
387  //
389  const ValueType& getValue(const Coord& xyz) const;
392  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
393 
397  int getValueDepth(const Coord& xyz) const;
398 
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);
416 
435  template<typename ModifyOp>
436  void modifyValue(const Coord& xyz, const ModifyOp& op);
437 
457  template<typename ModifyOp>
458  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
459 
462  bool probeValue(const Coord& xyz, ValueType& value) const;
463 
465  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
467  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
469  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
470 
472  void clip(const CoordBBox&);
473 
474 #ifndef OPENVDB_2_ABI_COMPATIBLE
475  virtual void clipUnallocatedNodes();
481 #endif
482 
492  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
493 
498  void prune(const ValueType& tolerance = zeroVal<ValueType>())
499  {
500  this->clearAllAccessors();
501  mRoot.prune(tolerance);
502  }
503 
506  void addLeaf(LeafNodeType& leaf) { mRoot.addLeaf(&leaf); }
507 
512  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
513 
518  template<typename NodeT>
519  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
520 
526  LeafNodeType* touchLeaf(const Coord& xyz);
527 
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;
535 
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); }
543 
544 
546  template<typename ArrayT> void getNodes(ArrayT& array) { mRoot.getNodes(array); }
569  template<typename ArrayT> void getNodes(ArrayT& array) const { mRoot.getNodes(array); }
571 
572  //
573  // Aux methods
574  //
577  bool empty() const { return mRoot.empty(); }
578 
580  void clear() { this->clearAllAccessors(); mRoot.clear(); }
581 
583  void clearAllAccessors();
584 
586  void attachAccessor(ValueAccessorBase<Tree>&) const;
589  void attachAccessor(ValueAccessorBase<const Tree>&) const;
591 
592  void releaseAccessor(ValueAccessorBase<Tree>&) const;
594  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
596 
599  virtual Metadata::Ptr getBackgroundValue() const;
600 
606  const ValueType& background() const { return mRoot.background(); }
607 
609  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
610 
612  void voxelizeActiveTiles();
613 
621  void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
622 
636  template<typename OtherRootNodeType>
637  void topologyUnion(const Tree<OtherRootNodeType>& other);
638 
652  template<typename OtherRootNodeType>
653  void topologyIntersection(const Tree<OtherRootNodeType>& other);
654 
665  template<typename OtherRootNodeType>
666  void topologyDifference(const Tree<OtherRootNodeType>& other);
667 
712  template<typename CombineOp>
713  void combine(Tree& other, CombineOp& op, bool prune = false);
714 #ifndef _MSC_VER
715  template<typename CombineOp>
716  void combine(Tree& other, const CombineOp& op, bool prune = false);
717 #endif
718 
757  template<typename ExtendedCombineOp>
758  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
759 #ifndef _MSC_VER
760  template<typename ExtendedCombineOp>
761  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
762 #endif
763 
792  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
793  void combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune = false);
794 #ifndef _MSC_VER
795  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
796  void combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune = false);
797 #endif
798 
872  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
873  void combine2Extended(const Tree& a, const OtherTreeType& b, ExtendedCombineOp& op,
874  bool prune = false);
875 #ifndef _MSC_VER
876  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
877  void combine2Extended(const Tree& a, const OtherTreeType& b, const ExtendedCombineOp&,
878  bool prune = false);
879 #endif
880 
921  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
922 
976  template<typename VisitorOp> void visit(VisitorOp& op);
977  template<typename VisitorOp> void visit(const VisitorOp& op);
978 
983  template<typename VisitorOp> void visit(VisitorOp& op) const;
984  template<typename VisitorOp> void visit(const VisitorOp& op) const;
985 
1033  template<typename OtherTreeType, typename VisitorOp>
1034  void visit2(OtherTreeType& other, VisitorOp& op);
1035  template<typename OtherTreeType, typename VisitorOp>
1036  void visit2(OtherTreeType& other, const VisitorOp& op);
1037 
1048  template<typename OtherTreeType, typename VisitorOp>
1049  void visit2(OtherTreeType& other, VisitorOp& op) const;
1050  template<typename OtherTreeType, typename VisitorOp>
1051  void visit2(OtherTreeType& other, const VisitorOp& op) const;
1052 
1053 
1054  //
1055  // Iteration
1056  //
1058  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
1060  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
1061  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
1063 
1065  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
1067  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
1068  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
1070 
1072  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
1074  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
1075  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
1077 
1078 
1084 
1090 
1092  NodeIter beginNode() { return NodeIter(*this); }
1094  NodeCIter beginNode() const { return NodeCIter(*this); }
1095  NodeCIter cbeginNode() const { return NodeCIter(*this); }
1097 
1099  LeafIter beginLeaf() { return LeafIter(*this); }
1101  LeafCIter beginLeaf() const { return LeafCIter(*this); }
1102  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
1104 
1111 
1113  ValueAllIter beginValueAll() { return ValueAllIter(*this); }
1115  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
1116  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
1118 
1119  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
1121  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
1122  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
1124 
1125  ValueOffIter beginValueOff() { return ValueOffIter(*this); }
1127  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1128  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1130 
1133  template<typename IterT> IterT begin();
1136  template<typename CIterT> CIterT cbegin() const;
1137 
1138 
1139 protected:
1140  typedef tbb::concurrent_hash_map<ValueAccessorBase<Tree>*, bool> AccessorRegistry;
1141  typedef tbb::concurrent_hash_map<ValueAccessorBase<const Tree>*, bool> ConstAccessorRegistry;
1142 
1143  // Disallow assignment of instances of this class.
1144  Tree& operator=(const Tree&);
1145 
1148  void releaseAllAccessors();
1149 
1150 
1151  //
1152  // Data members
1153  //
1154  RootNodeType mRoot; // root node of the tree
1155  mutable AccessorRegistry mAccessorRegistry;
1156  mutable ConstAccessorRegistry mConstAccessorRegistry;
1157 
1158  static tbb::atomic<const Name*> sTreeTypeName;
1159 }; // end of Tree class
1160 
1161 template<typename _RootNodeType>
1162 tbb::atomic<const Name*> Tree<_RootNodeType>::sTreeTypeName;
1163 
1164 
1169 template<typename T, Index N1, Index N2>
1170 struct Tree3 {
1172 };
1173 
1174 
1179 template<typename T, Index N1, Index N2, Index N3>
1180 struct Tree4 {
1182 };
1183 
1184 
1189 template<typename T, Index N1, Index N2, Index N3, Index N4>
1190 struct Tree5 {
1193 };
1194 
1195 
1197 
1198 
1199 inline void
1200 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1201 {
1202  int32_t bufferCount;
1203  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1204  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1205 }
1206 
1207 
1208 inline void
1209 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1210 {
1211  int32_t bufferCount = 1;
1212  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1213 }
1214 
1215 
1216 inline void
1217 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1218 {
1219  os << " Tree Type: " << type()
1220  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1221  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1222  << " Leaf Node Count: " << leafCount() << std::endl
1223  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1224 }
1225 
1226 
1228 
1229 
1230 //
1231 // Type traits for tree iterators
1232 //
1233 
1236 template<typename TreeT, typename IterT> struct TreeIterTraits;
1237 
1238 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1239  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1240  return tree.beginRootChildren();
1241  }
1242 };
1243 
1244 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1245  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1246  return tree.cbeginRootChildren();
1247  }
1248 };
1249 
1250 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1251  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1252  return tree.beginRootTiles();
1253  }
1254 };
1255 
1256 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1257  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1258  return tree.cbeginRootTiles();
1259  }
1260 };
1261 
1262 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1263  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1264  return tree.beginRootDense();
1265  }
1266 };
1267 
1268 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1269  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1270  return tree.cbeginRootDense();
1271  }
1272 };
1273 
1274 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1275  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1276 };
1277 
1278 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1279  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1280 };
1281 
1282 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1283  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1284 };
1285 
1286 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1287  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1288 };
1289 
1290 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1291  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1292 };
1293 
1294 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1295  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1296 };
1297 
1298 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1299  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1300 };
1301 
1302 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1303  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1304 };
1305 
1306 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1307  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1308 };
1309 
1310 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1311  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1312 };
1313 
1314 
1315 template<typename RootNodeType>
1316 template<typename IterT>
1317 inline IterT
1319 {
1320  return TreeIterTraits<Tree, IterT>::begin(*this);
1321 }
1322 
1323 
1324 template<typename RootNodeType>
1325 template<typename IterT>
1326 inline IterT
1328 {
1329  return TreeIterTraits<Tree, IterT>::begin(*this);
1330 }
1331 
1332 
1334 
1335 
1336 template<typename RootNodeType>
1337 void
1338 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1339 {
1340  this->clearAllAccessors();
1341  TreeBase::readTopology(is, saveFloatAsHalf);
1342  mRoot.readTopology(is, saveFloatAsHalf);
1343 }
1344 
1345 
1346 template<typename RootNodeType>
1347 void
1348 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1349 {
1350  TreeBase::writeTopology(os, saveFloatAsHalf);
1351  mRoot.writeTopology(os, saveFloatAsHalf);
1352 }
1353 
1354 
1355 template<typename RootNodeType>
1356 inline void
1357 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1358 {
1359  this->clearAllAccessors();
1360  mRoot.readBuffers(is, saveFloatAsHalf);
1361 }
1362 
1363 
1364 #ifndef OPENVDB_2_ABI_COMPATIBLE
1365 
1366 template<typename RootNodeType>
1367 inline void
1368 Tree<RootNodeType>::readBuffers(std::istream &is, const CoordBBox& bbox, bool saveFloatAsHalf)
1369 {
1370  this->clearAllAccessors();
1371  mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1372 }
1373 
1374 
1375 template<typename RootNodeType>
1376 inline void
1378 {
1379  for (LeafCIter it = this->cbeginLeaf(); it; ++it) {
1380  // Retrieving the value of a leaf voxel forces loading of the leaf node's voxel buffer.
1381  it->getValue(Index(0));
1382  }
1383 }
1384 
1385 #endif // !OPENVDB_2_ABI_COMPATIBLE
1386 
1387 
1388 template<typename RootNodeType>
1389 inline void
1390 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1391 {
1392  mRoot.writeBuffers(os, saveFloatAsHalf);
1393 }
1394 
1395 
1397 
1398 
1399 template<typename RootNodeType>
1400 inline void
1402 {
1403  typename AccessorRegistry::accessor a;
1404  mAccessorRegistry.insert(a, &accessor);
1405 }
1406 
1407 
1408 template<typename RootNodeType>
1409 inline void
1411 {
1412  typename ConstAccessorRegistry::accessor a;
1413  mConstAccessorRegistry.insert(a, &accessor);
1414 }
1415 
1416 
1417 template<typename RootNodeType>
1418 inline void
1420 {
1421  mAccessorRegistry.erase(&accessor);
1422 }
1423 
1424 
1425 template<typename RootNodeType>
1426 inline void
1428 {
1429  mConstAccessorRegistry.erase(&accessor);
1430 }
1431 
1432 
1433 template<typename RootNodeType>
1434 inline void
1436 {
1437  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1438  it != mAccessorRegistry.end(); ++it)
1439  {
1440  if (it->first) it->first->clear();
1441  }
1442 
1443  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1444  it != mConstAccessorRegistry.end(); ++it)
1445  {
1446  if (it->first) it->first->clear();
1447  }
1448 }
1449 
1450 
1451 template<typename RootNodeType>
1452 inline void
1454 {
1455  mAccessorRegistry.erase(NULL);
1456  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1457  it != mAccessorRegistry.end(); ++it)
1458  {
1459  it->first->release();
1460  }
1461  mAccessorRegistry.clear();
1462 
1463  mAccessorRegistry.erase(NULL);
1464  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1465  it != mConstAccessorRegistry.end(); ++it)
1466  {
1467  it->first->release();
1468  }
1469  mConstAccessorRegistry.clear();
1470 }
1471 
1472 
1474 
1475 
1476 template<typename RootNodeType>
1477 inline const typename RootNodeType::ValueType&
1478 Tree<RootNodeType>::getValue(const Coord& xyz) const
1479 {
1480  return mRoot.getValue(xyz);
1481 }
1482 
1483 
1484 template<typename RootNodeType>
1485 template<typename AccessT>
1486 inline const typename RootNodeType::ValueType&
1487 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1488 {
1489  return accessor.getValue(xyz);
1490 }
1491 
1492 
1493 template<typename RootNodeType>
1494 inline int
1495 Tree<RootNodeType>::getValueDepth(const Coord& xyz) const
1496 {
1497  return mRoot.getValueDepth(xyz);
1498 }
1499 
1500 
1501 template<typename RootNodeType>
1502 inline void
1504 {
1505  mRoot.setValueOff(xyz);
1506 }
1507 
1508 
1509 template<typename RootNodeType>
1510 inline void
1511 Tree<RootNodeType>::setValueOff(const Coord& xyz, const ValueType& value)
1512 {
1513  mRoot.setValueOff(xyz, value);
1514 }
1515 
1516 
1517 template<typename RootNodeType>
1518 inline void
1519 Tree<RootNodeType>::setActiveState(const Coord& xyz, bool on)
1520 {
1521  mRoot.setActiveState(xyz, on);
1522 }
1523 
1524 
1525 template<typename RootNodeType>
1526 inline void
1527 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value)
1528 {
1529  mRoot.setValueOn(xyz, value);
1530 }
1531 
1532 template<typename RootNodeType>
1533 inline void
1534 Tree<RootNodeType>::setValueOnly(const Coord& xyz, const ValueType& value)
1535 {
1536  mRoot.setValueOnly(xyz, value);
1537 }
1538 
1539 template<typename RootNodeType>
1540 template<typename AccessT>
1541 inline void
1542 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1543 {
1544  accessor.setValue(xyz, value);
1545 }
1546 
1547 
1548 template<typename RootNodeType>
1549 inline void
1551 {
1552  mRoot.setActiveState(xyz, true);
1553 }
1554 
1555 
1556 template<typename RootNodeType>
1557 inline void
1558 Tree<RootNodeType>::setValueOn(const Coord& xyz, const ValueType& value)
1559 {
1560  mRoot.setValueOn(xyz, value);
1561 }
1562 
1563 
1564 template<typename RootNodeType>
1565 template<typename ModifyOp>
1566 inline void
1567 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1568 {
1569  mRoot.modifyValue(xyz, op);
1570 }
1571 
1572 
1573 template<typename RootNodeType>
1574 template<typename ModifyOp>
1575 inline void
1576 Tree<RootNodeType>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1577 {
1578  mRoot.modifyValueAndActiveState(xyz, op);
1579 }
1580 
1581 
1582 template<typename RootNodeType>
1583 inline bool
1584 Tree<RootNodeType>::probeValue(const Coord& xyz, ValueType& value) const
1585 {
1586  return mRoot.probeValue(xyz, value);
1587 }
1588 
1589 
1591 
1592 
1593 template<typename RootNodeType>
1594 inline void
1595 Tree<RootNodeType>::addTile(Index level, const Coord& xyz,
1596  const ValueType& value, bool active)
1597 {
1598  mRoot.addTile(level, xyz, value, active);
1599 }
1600 
1601 
1602 template<typename RootNodeType>
1603 template<typename NodeT>
1604 inline NodeT*
1605 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1606 {
1607  this->clearAllAccessors();
1608  return mRoot.template stealNode<NodeT>(xyz, value, active);
1609 }
1610 
1611 
1612 template<typename RootNodeType>
1613 inline typename RootNodeType::LeafNodeType*
1615 {
1616  return mRoot.touchLeaf(xyz);
1617 }
1618 
1619 
1620 template<typename RootNodeType>
1621 inline typename RootNodeType::LeafNodeType*
1623 {
1624  return mRoot.probeLeaf(xyz);
1625 }
1626 
1627 
1628 template<typename RootNodeType>
1629 inline const typename RootNodeType::LeafNodeType*
1630 Tree<RootNodeType>::probeConstLeaf(const Coord& xyz) const
1631 {
1632  return mRoot.probeConstLeaf(xyz);
1633 }
1634 
1635 
1636 template<typename RootNodeType>
1637 template<typename NodeType>
1638 inline NodeType*
1640 {
1641  return mRoot.template probeNode<NodeType>(xyz);
1642 }
1643 
1644 
1645 template<typename RootNodeType>
1646 template<typename NodeType>
1647 inline const NodeType*
1648 Tree<RootNodeType>::probeNode(const Coord& xyz) const
1649 {
1650  return this->template probeConstNode<NodeType>(xyz);
1651 }
1652 
1653 
1654 template<typename RootNodeType>
1655 template<typename NodeType>
1656 inline const NodeType*
1657 Tree<RootNodeType>::probeConstNode(const Coord& xyz) const
1658 {
1659  return mRoot.template probeConstNode<NodeType>(xyz);
1660 }
1661 
1662 
1664 
1665 
1666 template<typename RootNodeType>
1667 inline void
1668 Tree<RootNodeType>::clip(const CoordBBox& bbox)
1669 {
1670  this->clearAllAccessors();
1671  return mRoot.clip(bbox);
1672 }
1673 
1674 
1675 #ifndef OPENVDB_2_ABI_COMPATIBLE
1676 template<typename RootNodeType>
1677 inline void
1679 {
1680  this->clearAllAccessors();
1681  for (LeafIter it = this->beginLeaf(); it; ) {
1682  const LeafNodeType* leaf = it.getLeaf();
1683  ++it; // advance the iterator before deleting the leaf node
1684  if (!leaf->isAllocated()) {
1685  this->addTile(/*level=*/0, leaf->origin(), this->background(), /*active=*/false);
1686  }
1687  }
1688 }
1689 #endif
1690 
1691 
1692 template<typename RootNodeType>
1693 inline void
1694 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1695 {
1696  this->clearAllAccessors();
1697  return mRoot.fill(bbox, value, active);
1698 }
1699 
1700 
1701 template<typename RootNodeType>
1704 {
1705  Metadata::Ptr result;
1706  if (Metadata::isRegisteredType(valueType())) {
1707  typedef TypedMetadata<ValueType> MetadataT;
1708  result = Metadata::createMetadata(valueType());
1709  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1710  m->value() = mRoot.background();
1711  }
1712  }
1713  return result;
1714 }
1715 
1716 
1718 
1719 
1720 template<typename RootNodeType>
1721 inline void
1723 {
1724  this->clearAllAccessors();
1725  mRoot.voxelizeActiveTiles();
1726 }
1727 
1728 
1729 template<typename RootNodeType>
1730 inline void
1732 {
1733  this->clearAllAccessors();
1734  other.clearAllAccessors();
1735  switch (policy) {
1736  case MERGE_ACTIVE_STATES:
1737  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1738  case MERGE_NODES:
1739  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1741  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1742  }
1743 }
1744 
1745 
1746 template<typename RootNodeType>
1747 template<typename OtherRootNodeType>
1748 inline void
1750 {
1751  this->clearAllAccessors();
1752  mRoot.topologyUnion(other.root());
1753 }
1754 
1755 template<typename RootNodeType>
1756 template<typename OtherRootNodeType>
1757 inline void
1759 {
1760  this->clearAllAccessors();
1761  mRoot.topologyIntersection(other.root());
1762 }
1763 
1764 template<typename RootNodeType>
1765 template<typename OtherRootNodeType>
1766 inline void
1768 {
1769  this->clearAllAccessors();
1770  mRoot.topologyDifference(other.root());
1771 }
1772 
1774 
1775 
1778 template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1780 {
1781  CombineOpAdapter(CombineOp& _op): op(_op) {}
1782 
1784  op(args.a(), args.b(), args.result());
1785  }
1786 
1787  CombineOp& op;
1788 };
1789 
1790 
1791 template<typename RootNodeType>
1792 template<typename CombineOp>
1793 inline void
1794 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1795 {
1797  this->combineExtended(other, extendedOp, prune);
1798 }
1799 
1800 
1803 #ifndef _MSC_VER
1804 template<typename RootNodeType>
1805 template<typename CombineOp>
1806 inline void
1807 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1808 {
1810  this->combineExtended(other, extendedOp, prune);
1811 }
1812 #endif
1813 
1814 
1815 template<typename RootNodeType>
1816 template<typename ExtendedCombineOp>
1817 inline void
1818 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1819 {
1820  this->clearAllAccessors();
1821  mRoot.combine(other.root(), op, prune);
1822 }
1823 
1824 
1827 #ifndef _MSC_VER
1828 template<typename RootNodeType>
1829 template<typename ExtendedCombineOp>
1830 inline void
1831 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1832 {
1833  this->clearAllAccessors();
1834  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1835 }
1836 #endif
1837 
1838 
1839 template<typename RootNodeType>
1840 template<typename CombineOp, typename OtherTreeType>
1841 inline void
1842 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1843 {
1845  this->combine2Extended(a, b, extendedOp, prune);
1846 }
1847 
1848 
1851 #ifndef _MSC_VER
1852 template<typename RootNodeType>
1853 template<typename CombineOp, typename OtherTreeType>
1854 inline void
1855 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1856 {
1858  this->combine2Extended(a, b, extendedOp, prune);
1859 }
1860 #endif
1861 
1862 
1863 template<typename RootNodeType>
1864 template<typename ExtendedCombineOp, typename OtherTreeType>
1865 inline void
1866 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1867  ExtendedCombineOp& op, bool prune)
1868 {
1869  this->clearAllAccessors();
1870  mRoot.combine2(a.root(), b.root(), op, prune);
1871 }
1872 
1873 
1877 #ifndef _MSC_VER
1878 template<typename RootNodeType>
1879 template<typename ExtendedCombineOp, typename OtherTreeType>
1880 inline void
1881 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1882  const ExtendedCombineOp& op, bool prune)
1883 {
1884  this->clearAllAccessors();
1885  mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
1886 }
1887 #endif
1888 
1889 
1891 
1892 
1893 template<typename RootNodeType>
1894 template<typename VisitorOp>
1895 inline void
1897 {
1898  this->clearAllAccessors();
1899  mRoot.template visit<VisitorOp>(op);
1900 }
1901 
1902 
1903 template<typename RootNodeType>
1904 template<typename VisitorOp>
1905 inline void
1906 Tree<RootNodeType>::visit(VisitorOp& op) const
1907 {
1908  mRoot.template visit<VisitorOp>(op);
1909 }
1910 
1911 
1914 template<typename RootNodeType>
1915 template<typename VisitorOp>
1916 inline void
1917 Tree<RootNodeType>::visit(const VisitorOp& op)
1918 {
1919  this->clearAllAccessors();
1920  mRoot.template visit<const VisitorOp>(op);
1921 }
1922 
1923 
1926 template<typename RootNodeType>
1927 template<typename VisitorOp>
1928 inline void
1929 Tree<RootNodeType>::visit(const VisitorOp& op) const
1930 {
1931  mRoot.template visit<const VisitorOp>(op);
1932 }
1933 
1934 
1936 
1937 
1938 template<typename RootNodeType>
1939 template<typename OtherTreeType, typename VisitorOp>
1940 inline void
1941 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1942 {
1943  this->clearAllAccessors();
1944  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1945  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
1946 }
1947 
1948 
1949 template<typename RootNodeType>
1950 template<typename OtherTreeType, typename VisitorOp>
1951 inline void
1952 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1953 {
1954  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1955  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
1956 }
1957 
1958 
1961 template<typename RootNodeType>
1962 template<typename OtherTreeType, typename VisitorOp>
1963 inline void
1964 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1965 {
1966  this->clearAllAccessors();
1967  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1968  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
1969 }
1970 
1971 
1974 template<typename RootNodeType>
1975 template<typename OtherTreeType, typename VisitorOp>
1976 inline void
1977 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1978 {
1979  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1980  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
1981 }
1982 
1983 
1985 
1986 
1987 template<typename RootNodeType>
1988 inline const Name&
1990 {
1991  if (sTreeTypeName == NULL) {
1992  std::vector<Index> dims;
1993  Tree::getNodeLog2Dims(dims);
1994  std::ostringstream ostr;
1995  ostr << "Tree_" << typeNameAsString<ValueType>();
1996  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1997  ostr << "_" << dims[i];
1998  }
1999  Name* s = new Name(ostr.str());
2000  if (sTreeTypeName.compare_and_swap(s, NULL) != NULL) delete s;
2001  }
2002  return *sTreeTypeName;
2003 }
2004 
2005 
2006 template<typename RootNodeType>
2007 template<typename OtherRootNodeType>
2008 inline bool
2010 {
2011  return mRoot.hasSameTopology(other.root());
2012 }
2013 
2014 
2015 template<typename RootNodeType>
2016 Index64
2018 {
2019  Coord dim(0, 0, 0);
2020  this->evalActiveVoxelDim(dim);
2021  const Index64
2022  totalVoxels = dim.x() * dim.y() * dim.z(),
2023  activeVoxels = this->activeVoxelCount();
2024  assert(totalVoxels >= activeVoxels);
2025  return totalVoxels - activeVoxels;
2026 }
2027 
2028 
2029 template<typename RootNodeType>
2030 inline bool
2032 {
2033  bbox.reset(); // default invalid bbox
2034 
2035  if (this->empty()) return false; // empty
2036 
2037  mRoot.evalActiveBoundingBox(bbox, false);
2038 
2039  return true;// not empty
2040 }
2041 
2042 template<typename RootNodeType>
2043 inline bool
2045 {
2046  bbox.reset(); // default invalid bbox
2047 
2048  if (this->empty()) return false; // empty
2049 
2050  mRoot.evalActiveBoundingBox(bbox, true);
2051 
2052  return true;// not empty
2053 }
2054 
2055 
2056 template<typename RootNodeType>
2057 inline bool
2059 {
2060  CoordBBox bbox;
2061  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
2062  dim = bbox.extents();
2063  return notEmpty;
2064 }
2065 
2066 
2067 template<typename RootNodeType>
2068 inline bool
2070 {
2071  CoordBBox bbox;
2072  bool notEmpty = this->evalLeafBoundingBox(bbox);
2073  dim = bbox.extents();
2074  return notEmpty;
2075 }
2076 
2077 
2078 template<typename RootNodeType>
2079 inline void
2080 Tree<RootNodeType>::evalMinMax(ValueType& minVal, ValueType& maxVal) const
2081 {
2082  minVal = maxVal = zeroVal<ValueType>();
2083  if (ValueOnCIter iter = this->cbeginValueOn()) {
2084  minVal = maxVal = *iter;
2085  for (++iter; iter; ++iter) {
2086  const ValueType& val = *iter;
2087  if (val < minVal) minVal = val;
2088  if (val > maxVal) maxVal = val;
2089  }
2090  }
2091 }
2092 
2093 
2094 template<typename RootNodeType>
2095 inline void
2096 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
2097 {
2098  dims.clear();
2099  RootNodeType::getNodeLog2Dims(dims);
2100 }
2101 
2102 
2103 template<typename RootNodeType>
2104 inline void
2105 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
2106 {
2107  if (verboseLevel <= 0) return;
2108 
2110  struct OnExit {
2111  std::ostream& os;
2112  std::streamsize savedPrecision;
2113  OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
2114  ~OnExit() { os.precision(savedPrecision); }
2115  };
2116  OnExit restorePrecision(os);
2117 
2118  std::vector<Index> dims;
2119  Tree::getNodeLog2Dims(dims);
2120 
2121  os << "Information about Tree:\n"
2122  << " Type: " << this->type() << "\n";
2123 
2124  os << " Configuration:\n";
2125 
2126  if (verboseLevel <= 1) {
2127  // Print node types and sizes.
2128  os << " Root(" << mRoot.getTableSize() << ")";
2129  if (dims.size() > 1) {
2130  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2131  os << ", Internal(" << (1 << dims[i]) << "^3)";
2132  }
2133  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
2134  }
2135  os << " Background value: " << mRoot.background() << "\n";
2136  return;
2137  }
2138 
2139  // The following is tree information that is expensive to extract.
2140 
2141  ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
2142  if (verboseLevel > 3) {
2143  // This forces loading of all non-resident nodes.
2144  this->evalMinMax(minVal, maxVal);
2145  }
2146 
2147  std::vector<Index64> nodeCount(dims.size());
2148 #ifndef OPENVDB_2_ABI_COMPATIBLE
2149  Index64 unallocatedLeafCount = 0;
2150 #endif
2151  for (NodeCIter it = cbeginNode(); it; ++it) {
2152  ++(nodeCount[it.getDepth()]);
2153 
2154 #ifndef OPENVDB_2_ABI_COMPATIBLE
2155  if (it.getLevel() == 0) {
2156  const LeafNodeType* leaf = NULL;
2157  it.getNode(leaf);
2158  if (leaf && !leaf->isAllocated()) ++unallocatedLeafCount;
2159  }
2160 #endif
2161  }
2162  Index64 totalNodeCount = 0;
2163  for (size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
2164 
2165  // Print node types, counts and sizes.
2166  os << " Root(1 x " << mRoot.getTableSize() << ")";
2167  if (dims.size() > 1) {
2168  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2169  os << ", Internal(" << util::formattedInt(nodeCount[i]);
2170  os << " x " << (1 << dims[i]) << "^3)";
2171  }
2172  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
2173  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
2174  }
2175  os << " Background value: " << mRoot.background() << "\n";
2176 
2177  // Statistics of topology and values
2178 
2179  if (verboseLevel > 3) {
2180  os << " Min value: " << minVal << "\n";
2181  os << " Max value: " << maxVal << "\n";
2182  }
2183 
2184  const uint64_t
2185  leafCount = *nodeCount.rbegin(),
2186  numActiveVoxels = this->activeVoxelCount(),
2187  numActiveLeafVoxels = this->activeLeafVoxelCount();
2188 
2189  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
2190 
2191  Coord dim(0, 0, 0);
2192  uint64_t totalVoxels = 0;
2193  if (numActiveVoxels) { // nonempty
2194  CoordBBox bbox;
2195  this->evalActiveVoxelBoundingBox(bbox);
2196  dim = bbox.extents();
2197  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2198 
2199  os << " Bounding box of active voxels: " << bbox << "\n";
2200  os << " Dimensions of active voxels: "
2201  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
2202 
2203  const double activeRatio = (100.0 * double(numActiveVoxels)) / double(totalVoxels);
2204  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2205 
2206  if (leafCount > 0) {
2207  const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2208  / (double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2209  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2210  }
2211 
2212 #ifndef OPENVDB_2_ABI_COMPATIBLE
2213  if (verboseLevel > 2) {
2214  os << " Number of unallocated nodes: "
2215  << util::formattedInt(unallocatedLeafCount) << " ("
2216  << (100.0 * double(unallocatedLeafCount) / double(totalNodeCount)) << "%)\n";
2217  }
2218 #endif
2219  } else {
2220  os << " Tree is empty!\n";
2221  }
2222  os << std::flush;
2223 
2224  if (verboseLevel == 2) return;
2225 
2226  // Memory footprint in bytes
2227  const uint64_t
2228  actualMem = this->memUsage(),
2229  denseMem = sizeof(ValueType) * totalVoxels,
2230  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2232 
2233  os << "Memory footprint:\n";
2234  util::printBytes(os, actualMem, " Actual: ");
2235  util::printBytes(os, voxelsMem, " Active leaf voxels: ");
2236 
2237  if (numActiveVoxels) {
2238  util::printBytes(os, denseMem, " Dense equivalent: ");
2239  os << " Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2240  << "% of an equivalent dense volume\n";
2241  os << " Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2242  << "% of actual footprint\n";
2243  }
2244 }
2245 
2246 } // namespace tree
2247 } // namespace OPENVDB_VERSION_NAME
2248 } // namespace openvdb
2249 
2250 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
2251 
2252 // Copyright (c) 2012-2014 DreamWorks Animation LLC
2253 // All rights reserved. This software is distributed under the
2254 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
virtual Metadata::Ptr getBackgroundValue() const
Return this tree's background value wrapped as metadata.
Definition: Tree.h:86
virtual ~TreeBase()
Definition: Tree.h:70
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:1190
TreeBase()
Definition: Tree.h:69
Templated metadata class to hold specific types.
Definition: metadata/Metadata.h:137
Definition: Types.h:424
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1200
#define OPENVDB_API
Helper macros for defining library symbol visibility.
Definition: Platform.h:187
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:153
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1155
boost::shared_ptr< const TreeBase > ConstPtr
Definition: Tree.h:67
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1303
std::string Name
Definition: Name.h:44
static tbb::atomic< const Name * > sTreeTypeName
Definition: Tree.h:1158
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1102
_RootNodeType RootNodeType
Definition: Tree.h:209
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
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:1503
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1311
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:977
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1783
uint64_t Index64
Definition: Types.h:58
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1478
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
tbb::concurrent_hash_map< ValueAccessorBase< Tree > *, bool > AccessorRegistry
Definition: Tree.h:1140
NodeIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > NodeCIter
Iterator over all nodes in this tree.
Definition: Tree.h:1082
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
const ValueType & background() const
Return this tree's background value.
Definition: Tree.h:606
RootNodeType & root()
Return this tree's root node.
Definition: Tree.h:304
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1101
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1263
const RootNodeType & root() const
Return this tree's root node.
Definition: Tree.h:305
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1209
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:1595
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:284
boost::shared_ptr< Tree > Ptr
Definition: Tree.h:206
ValueConverter::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:222
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:1527
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1116
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1115
void getNodes(ArrayT &array) const
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:569
boost::shared_ptr< TreeBase > Ptr
Definition: Tree.h:66
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1279
bool operator==(const Tree &) const
Definition: Tree.h:299
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1068
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1257
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1094
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:1534
virtual void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const
Write out all data buffers for this tree.
Definition: Tree.h:1390
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1067
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1251
virtual void getIndexRange(CoordBBox &bbox) const
Min and max are both inclusive.
Definition: Tree.h:609
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1576
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:1180
virtual Name valueType() const
Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
Definition: Tree.h:292
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:1519
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1779
virtual Index32 leafCount() const
Return the number of leaf nodes.
Definition: Tree.h:365
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
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:403
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1060
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1307
Internal table nodes for OpenVDB trees.
virtual ~Tree()
Definition: Tree.h:286
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOnIter > ValueOnIter
Definition: Tree.h:1107
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:577
#define OPENVDB_VERSION_NAME
Definition: version.h:43
static bool isRegisteredType(const Name &typeName)
Return true if the given type is known by the metadata type registry.
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:130
Definition: Types.h:263
bool operator!=(const Tree &) const
Definition: Tree.h:300
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueAllCIter > ValueAllCIter
Definition: Tree.h:1106
virtual Index64 inactiveLeafVoxelCount() const
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:371
Index32 Index
Definition: Types.h:59
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOffIter > ValueOffIter
Definition: Tree.h:1109
#define OPENVDB_LOG_WARN(message)
Log a warning message of the form 'someVar << "some text" << ...'.
Definition: logging.h:39
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1287
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:309
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1269
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1228
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:465
virtual Index64 activeLeafVoxelCount() const
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:369
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1156
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1127
Tree< typename RootNodeType::template ValueConverter< OtherValueType >::Type > Type
Definition: Tree.h:223
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1075
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:1170
virtual Index64 activeVoxelCount() const
Return the total number of active voxels.
Definition: Tree.h:373
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:580
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
virtual const Name & type() const
Return the name of this type of tree.
Definition: Tree.h:297
const AValueType & a() const
Get the A input value.
Definition: Types.h:334
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1236
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1122
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1088
const AValueType & result() const
Get the output value.
Definition: Types.h:339
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:382
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1435
Tree< RootNode< InternalNode< InternalNode< LeafNode< T, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1181
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1239
MergePolicy
Definition: Types.h:261
OPENVDB_STATIC_SPECIALIZATION GridType::Ptr clip(const GridType &grid, const BBoxd &)
Clip the given grid against a world-space bounding box and return a new grid containing the result...
Definition: Clip.h:364
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:921
boost::shared_ptr< Metadata > Ptr
Definition: metadata/Metadata.h:52
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:230
virtual Index32 nonLeafCount() const
Return the number of non-leaf nodes.
Definition: Tree.h:367
Tree< RootNode< InternalNode< LeafNode< T, N2 >, N1 > > > Type
Definition: Tree.h:1171
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOnCIter > ValueOnCIter
Definition: Tree.h:1108
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1275
Tree< RootNode< InternalNode< InternalNode< InternalNode< LeafNode< T, N4 >, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1192
boost::shared_ptr< const Tree > ConstPtr
Definition: Tree.h:207
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:1614
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1283
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:277
CombineOp & op
Definition: Tree.h:1787
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:469
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:658
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1245
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:1567
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1095
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
Definition: Exceptions.h:84
The root node of an OpenVDB tree.
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:1630
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:1061
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1074
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:1121
TreeValueIteratorBase< Tree, typename RootNodeType::ValueAllIter > ValueAllIter
Definition: Tree.h:1105
RootNodeType mRoot
Definition: Tree.h:1154
Definition: Tree.h:203
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
Index64 activeTileCount() const
Return the total number of active tiles.
Definition: Tree.h:377
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1295
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:467
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:1584
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:1622
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:1495
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:102
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: Tree.h:1550
uint32_t Index32
Definition: Types.h:57
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1128
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:2009
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:1217
static Metadata::Ptr createMetadata(const Name &typeName)
Creates a new Metadata from the metadata type registry.
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1299
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)
Base class for typed trees.
Definition: Tree.h:63
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOffCIter > ValueOffCIter
Definition: Tree.h:1110
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1291
virtual Index treeDepth() const
Return the depth of this tree.
Definition: Tree.h:363
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:241
tbb::concurrent_hash_map< ValueAccessorBase< const Tree > *, bool > ConstAccessorRegistry
Definition: Tree.h:1141
RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:211
const BValueType & b() const
Get the B input value.
Definition: Types.h:336
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:314
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1781