OpenVDB  2.1.0
Tree.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2013 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 #include "Util.h"
56 
57 
58 namespace openvdb {
60 namespace OPENVDB_VERSION_NAME {
61 namespace tree {
62 
65 {
66 public:
67  typedef boost::shared_ptr<TreeBase> Ptr;
68  typedef boost::shared_ptr<const TreeBase> ConstPtr;
69 
70  TreeBase() {}
71  virtual ~TreeBase() {}
72 
74  virtual const Name& type() const = 0;
75 
77  virtual Name valueType() const = 0;
78 
80  virtual TreeBase::Ptr copy() const = 0;
81 
82  //
83  // Tree methods
84  //
87  virtual Metadata::Ptr getBackgroundValue() const { return Metadata::Ptr(); }
88 
96  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const = 0;
97 
101  virtual bool evalLeafDim(Coord& dim) const = 0;
102 
110  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const = 0;
111 
115  virtual bool evalActiveVoxelDim(Coord& dim) const = 0;
116 
117  virtual void getIndexRange(CoordBBox& bbox) const = 0;
118 
119 
120  //
121  // Statistics
122  //
126  virtual Index treeDepth() const = 0;
128  virtual Index32 leafCount() const = 0;
130  virtual Index32 nonLeafCount() const = 0;
132  virtual Index64 activeLeafVoxelCount() const = 0;
134  virtual Index64 inactiveLeafVoxelCount() const = 0;
136  virtual Index64 activeVoxelCount() const = 0;
138  virtual Index64 inactiveVoxelCount() const = 0;
139 
141  virtual Index64 memUsage() const { return 0; }
142 
143 
144  //
145  // I/O methods
146  //
150  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
154  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
155 
157  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false) = 0;
159  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const = 0;
160 
165  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
166 
167 private:
168  // Disallow copying of instances of this class.
169  //TreeBase(const TreeBase& other);
170  TreeBase& operator=(const TreeBase& other);
171 };
172 
173 
175 
176 
177 template<typename _RootNodeType>
178 class Tree: public TreeBase
179 {
180 public:
181  typedef boost::shared_ptr<Tree> Ptr;
182  typedef boost::shared_ptr<const Tree> ConstPtr;
183 
184  typedef _RootNodeType RootNodeType;
185  typedef typename RootNodeType::ValueType ValueType;
186  typedef typename RootNodeType::LeafNodeType LeafNodeType;
187 
188  static const Index DEPTH = RootNodeType::LEVEL + 1;
189 
196  template<typename OtherValueType>
197  struct ValueConverter {
199  };
200 
201 
202  Tree(){}
203 
205  Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
206  {
207  }
208 
218  template<typename OtherTreeType>
219  Tree(const OtherTreeType& other,
220  const ValueType& inactiveValue,
221  const ValueType& activeValue,
222  TopologyCopy):
223  TreeBase(other),
224  mRoot(other.getRootNode(), inactiveValue, activeValue, TopologyCopy())
225  {
226  }
227 
238  template<typename OtherTreeType>
239  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
240  TreeBase(other),
241  mRoot(other.getRootNode(), background, TopologyCopy())
242  {
243  }
244 
246  Tree(const ValueType& background): mRoot(background) {}
247 
248  virtual ~Tree() { releaseAllAccessors(); }
249 
251  virtual TreeBase::Ptr copy() const { return TreeBase::Ptr(new Tree(*this)); }
252 
254  virtual Name valueType() const { return typeNameAsString<ValueType>(); }
255 
257  static const Name& treeType();
259  virtual const Name& type() const { return this->treeType(); }
260 
261  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
262  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
263 
265  RootNodeType& root() { return mRoot; }
267  const RootNodeType& root() const { return mRoot; }
268  // Deprecate the methods below
269  RootNodeType& getRootNode() { return mRoot; }
270  const RootNodeType& getRootNode() const { return mRoot; }
272 
273 
274  //
275  // Tree methods
276  //
279  template<typename OtherRootNodeType>
280  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
281 
282  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const;
283  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
284  virtual bool evalActiveVoxelDim(Coord& dim) const;
285  virtual bool evalLeafDim(Coord& dim) const;
286 
290  static void getNodeLog2Dims(std::vector<Index>& dims);
291 
292 
293  //
294  // I/O methods
295  //
299  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
303  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
305  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false);
307  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const;
308 
309  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
310 
311 
312  //
313  // Statistics
314  //
318  virtual Index treeDepth() const { return DEPTH; }
320  virtual Index32 leafCount() const { return mRoot.leafCount(); }
322  virtual Index32 nonLeafCount() const { return mRoot.nonLeafCount(); }
324  virtual Index64 activeLeafVoxelCount() const { return mRoot.onLeafVoxelCount(); }
326  virtual Index64 inactiveLeafVoxelCount() const { return mRoot.offLeafVoxelCount(); }
328  virtual Index64 activeVoxelCount() const { return mRoot.onVoxelCount(); }
330  virtual Index64 inactiveVoxelCount() const;
331 
334  Index64 activeTileCount() const { return mRoot.onTileCount(); }
335 
337  void evalMinMax(ValueType &min, ValueType &max) const;
338 
339  virtual Index64 memUsage() const { return sizeof(*this) + mRoot.memUsage(); }
340 
341 
342  //
343  // Voxel access methods (using signed indexing)
344  //
346  const ValueType& getValue(const Coord& xyz) const;
349  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
350 
354  int getValueDepth(const Coord& xyz) const;
355 
357  void setActiveState(const Coord& xyz, bool on);
359  void setValueOnly(const Coord& xyz, const ValueType& value);
361  void setValueOn(const Coord& xyz);
363  void setValueOn(const Coord& xyz, const ValueType& value);
365  void setValue(const Coord& xyz, const ValueType& value);
368  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
370  void setValueOff(const Coord& xyz);
372  void setValueOff(const Coord& xyz, const ValueType& value);
373 
392  template<typename ModifyOp>
393  void modifyValue(const Coord& xyz, const ModifyOp& op);
394 
414  template<typename ModifyOp>
415  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
416 
419  bool probeValue(const Coord& xyz, ValueType& value) const;
420 
422  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
424  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
426  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
427 
437  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
438 
445  template<typename PruneOp> void pruneOp(PruneOp&);
446 
450  void prune(const ValueType& tolerance = zeroVal<ValueType>());
451 
454  void pruneInactive(const ValueType&);
455 
458  void pruneInactive();
459 
466  void pruneLevelSet();
467 
470  void addLeaf(LeafNodeType& leaf) { mRoot.addLeaf(&leaf); }
471 
476  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
477 
482  template<typename NodeT>
483  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
484 
490  LeafNodeType* touchLeaf(const Coord& xyz);
491 
493  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
496  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
497  template<typename NodeType> const NodeType* probeNode(const Coord& xyz) const;
499 
501  LeafNodeType* probeLeaf(const Coord& xyz);
504  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
505  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
507 
508 
509  //
510  // Aux methods
511  //
514  bool empty() const { return mRoot.empty(); }
515 
517  void clear() { this->clearAllAccessors(); mRoot.clear(); }
518 
520  void clearAllAccessors();
521 
523  void attachAccessor(ValueAccessorBase<Tree>&) const;
526  void attachAccessor(ValueAccessorBase<const Tree>&) const;
528 
529  void releaseAccessor(ValueAccessorBase<Tree>&) const;
531  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
533 
536  virtual Metadata::Ptr getBackgroundValue() const;
537 
539  const ValueType& background() const { return mRoot.background(); }
541  void setBackground(const ValueType& background) { mRoot.setBackground(background); }
542 
544  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
545 
550  void signedFloodFill() { mRoot.signedFloodFill(); }
551 
557  void signedFloodFill(const ValueType& outside, const ValueType& inside);
558 
560  void voxelizeActiveTiles();
561 
569  void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
570 
584  template<typename OtherRootNodeType>
585  void topologyUnion(const Tree<OtherRootNodeType>& other);
586 
600  template<typename OtherRootNodeType>
601  void topologyIntersection(const Tree<OtherRootNodeType>& other);
602 
613  template<typename OtherRootNodeType>
614  void topologyDifference(const Tree<OtherRootNodeType>& other);
615 
661  template<typename CombineOp>
662  void combine(Tree& other, CombineOp& op, bool prune = false);
663 #ifndef _MSC_VER
664  template<typename CombineOp>
665  void combine(Tree& other, const CombineOp& op, bool prune = false);
666 #endif
667 
707  template<typename ExtendedCombineOp>
708  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
709 #ifndef _MSC_VER
710  template<typename ExtendedCombineOp>
711  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
712 #endif
713 
739  template<typename CombineOp>
740  void combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune = false);
741 #ifndef _MSC_VER
742  template<typename CombineOp>
743  void combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune = false);
744 #endif
745 
785  template<typename ExtendedCombineOp>
786  void combine2Extended(const Tree& a, const Tree& b, ExtendedCombineOp& op,
787  bool prune = false);
788 #ifndef _MSC_VER
789  template<typename ExtendedCombineOp>
790  void combine2Extended(const Tree& a, const Tree& b, const ExtendedCombineOp&,
791  bool prune = false);
792 #endif
793 
840  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
841 
896  template<typename VisitorOp> void visit(VisitorOp& op);
897  template<typename VisitorOp> void visit(const VisitorOp& op);
898 
903  template<typename VisitorOp> void visit(VisitorOp& op) const;
904  template<typename VisitorOp> void visit(const VisitorOp& op) const;
905 
954  template<typename OtherTreeType, typename VisitorOp>
955  void visit2(OtherTreeType& other, VisitorOp& op);
956  template<typename OtherTreeType, typename VisitorOp>
957  void visit2(OtherTreeType& other, const VisitorOp& op);
958 
969  template<typename OtherTreeType, typename VisitorOp>
970  void visit2(OtherTreeType& other, VisitorOp& op) const;
971  template<typename OtherTreeType, typename VisitorOp>
972  void visit2(OtherTreeType& other, const VisitorOp& op) const;
973 
974 
975  //
976  // Iteration
977  //
979  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
981  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
982  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
984 
986  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
988  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
989  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
991 
993  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
995  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
996  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
998 
999 
1005 
1011 
1013  NodeIter beginNode() { return NodeIter(*this); }
1015  NodeCIter beginNode() const { return NodeCIter(*this); }
1016  NodeCIter cbeginNode() const { return NodeCIter(*this); }
1018 
1020  LeafIter beginLeaf() { return LeafIter(*this); }
1022  LeafCIter beginLeaf() const { return LeafCIter(*this); }
1023  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
1025 
1032 
1034  ValueAllIter beginValueAll() { return ValueAllIter(*this); }
1036  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
1037  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
1039 
1040  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
1042  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
1043  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
1045 
1046  ValueOffIter beginValueOff() { return ValueOffIter(*this); }
1048  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1049  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1051 
1054  template<typename IterT> IterT begin();
1057  template<typename CIterT> CIterT cbegin() const;
1058 
1059 
1060 protected:
1061  typedef tbb::concurrent_hash_map<ValueAccessorBase<Tree>*, bool> AccessorRegistry;
1062  typedef tbb::concurrent_hash_map<ValueAccessorBase<const Tree>*, bool> ConstAccessorRegistry;
1063 
1064  // Disallow assignment of instances of this class.
1065  Tree& operator=(const Tree&);
1066 
1069  void releaseAllAccessors();
1070 
1071 
1072  //
1073  // Data members
1074  //
1075  RootNodeType mRoot; // root node of the tree
1078 }; // end of Tree class
1079 
1080 
1085 template<typename T, Index N1, Index N2>
1086 struct Tree3 {
1088 };
1089 
1090 
1095 template<typename T, Index N1, Index N2, Index N3>
1096 struct Tree4 {
1098 };
1099 
1100 
1105 template<typename T, Index N1, Index N2, Index N3, Index N4>
1106 struct Tree5 {
1109 };
1110 
1111 
1113 
1114 
1115 inline void
1116 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1117 {
1118  int32_t bufferCount;
1119  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1120  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1121 }
1122 
1123 
1124 inline void
1125 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1126 {
1127  int32_t bufferCount = 1;
1128  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1129 }
1130 
1131 
1132 inline void
1133 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1134 {
1135  os << " Tree Type: " << type()
1136  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1137  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1138  << " Leaf Node Count: " << leafCount() << std::endl
1139  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1140 }
1141 
1142 
1144 
1145 
1146 //
1147 // Type traits for tree iterators
1148 //
1149 
1152 template<typename TreeT, typename IterT> struct TreeIterTraits;
1153 
1154 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1155  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1156  return tree.beginRootChildren();
1157  }
1158 };
1159 
1160 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1161  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1162  return tree.cbeginRootChildren();
1163  }
1164 };
1165 
1166 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1167  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1168  return tree.beginRootTiles();
1169  }
1170 };
1171 
1172 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1173  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1174  return tree.cbeginRootTiles();
1175  }
1176 };
1177 
1178 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1179  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1180  return tree.beginRootDense();
1181  }
1182 };
1183 
1184 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1185  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1186  return tree.cbeginRootDense();
1187  }
1188 };
1189 
1190 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1191  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1192 };
1193 
1194 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1195  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1196 };
1197 
1198 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1199  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1200 };
1201 
1202 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1203  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1204 };
1205 
1206 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1207  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1208 };
1209 
1210 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1211  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1212 };
1213 
1214 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1215  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1216 };
1217 
1218 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1219  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1220 };
1221 
1222 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1223  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1224 };
1225 
1226 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1227  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1228 };
1229 
1230 
1231 template<typename RootNodeType>
1232 template<typename IterT>
1233 inline IterT
1235 {
1236  return TreeIterTraits<Tree, IterT>::begin(*this);
1237 }
1238 
1239 
1240 template<typename RootNodeType>
1241 template<typename IterT>
1242 inline IterT
1244 {
1245  return TreeIterTraits<Tree, IterT>::begin(*this);
1246 }
1247 
1248 
1250 
1251 
1252 template<typename RootNodeType>
1253 void
1254 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1255 {
1256  this->clearAllAccessors();
1257  TreeBase::readTopology(is, saveFloatAsHalf);
1258  mRoot.readTopology(is, saveFloatAsHalf);
1259 }
1260 
1261 
1262 template<typename RootNodeType>
1263 void
1264 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1265 {
1266  TreeBase::writeTopology(os, saveFloatAsHalf);
1267  mRoot.writeTopology(os, saveFloatAsHalf);
1268 }
1269 
1270 
1271 template<typename RootNodeType>
1272 inline void
1273 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1274 {
1275  this->clearAllAccessors();
1276  mRoot.readBuffers(is, saveFloatAsHalf);
1277 }
1278 
1279 
1280 template<typename RootNodeType>
1281 inline void
1282 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1283 {
1284  mRoot.writeBuffers(os, saveFloatAsHalf);
1285 }
1286 
1287 
1289 
1290 
1291 template<typename RootNodeType>
1292 inline void
1294 {
1295  typename AccessorRegistry::accessor a;
1296  mAccessorRegistry.insert(a, &accessor);
1297 }
1298 
1299 
1300 template<typename RootNodeType>
1301 inline void
1303 {
1304  typename ConstAccessorRegistry::accessor a;
1305  mConstAccessorRegistry.insert(a, &accessor);
1306 }
1307 
1308 
1309 template<typename RootNodeType>
1310 inline void
1312 {
1313  mAccessorRegistry.erase(&accessor);
1314 }
1315 
1316 
1317 template<typename RootNodeType>
1318 inline void
1320 {
1321  mConstAccessorRegistry.erase(&accessor);
1322 }
1323 
1324 
1325 template<typename RootNodeType>
1326 inline void
1328 {
1329  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1330  it != mAccessorRegistry.end(); ++it)
1331  {
1332  if (it->first) it->first->clear();
1333  }
1334 
1335  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1336  it != mConstAccessorRegistry.end(); ++it)
1337  {
1338  if (it->first) it->first->clear();
1339  }
1340 }
1341 
1342 
1343 template<typename RootNodeType>
1344 inline void
1346 {
1347  mAccessorRegistry.erase(NULL);
1348  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1349  it != mAccessorRegistry.end(); ++it)
1350  {
1351  it->first->release();
1352  }
1353  mAccessorRegistry.clear();
1354 
1355  mAccessorRegistry.erase(NULL);
1356  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1357  it != mConstAccessorRegistry.end(); ++it)
1358  {
1359  it->first->release();
1360  }
1361  mConstAccessorRegistry.clear();
1362 }
1363 
1364 
1366 
1367 
1368 template<typename RootNodeType>
1369 inline const typename RootNodeType::ValueType&
1370 Tree<RootNodeType>::getValue(const Coord& xyz) const
1371 {
1372  return mRoot.getValue(xyz);
1373 }
1374 
1375 
1376 template<typename RootNodeType>
1377 template<typename AccessT>
1378 inline const typename RootNodeType::ValueType&
1379 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1380 {
1381  return accessor.getValue(xyz);
1382 }
1383 
1384 
1385 template<typename RootNodeType>
1386 inline int
1387 Tree<RootNodeType>::getValueDepth(const Coord& xyz) const
1388 {
1389  return mRoot.getValueDepth(xyz);
1390 }
1391 
1392 
1393 template<typename RootNodeType>
1394 inline void
1396 {
1397  mRoot.setValueOff(xyz);
1398 }
1399 
1400 
1401 template<typename RootNodeType>
1402 inline void
1403 Tree<RootNodeType>::setValueOff(const Coord& xyz, const ValueType& value)
1404 {
1405  mRoot.setValueOff(xyz, value);
1406 }
1407 
1408 
1409 template<typename RootNodeType>
1410 inline void
1411 Tree<RootNodeType>::setActiveState(const Coord& xyz, bool on)
1412 {
1413  mRoot.setActiveState(xyz, on);
1414 }
1415 
1416 
1417 template<typename RootNodeType>
1418 inline void
1419 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value)
1420 {
1421  mRoot.setValueOn(xyz, value);
1422 }
1423 
1424 template<typename RootNodeType>
1425 inline void
1426 Tree<RootNodeType>::setValueOnly(const Coord& xyz, const ValueType& value)
1427 {
1428  mRoot.setValueOnly(xyz, value);
1429 }
1430 
1431 template<typename RootNodeType>
1432 template<typename AccessT>
1433 inline void
1434 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1435 {
1436  accessor.setValue(xyz, value);
1437 }
1438 
1439 
1440 template<typename RootNodeType>
1441 inline void
1443 {
1444  mRoot.setActiveState(xyz, true);
1445 }
1446 
1447 
1448 template<typename RootNodeType>
1449 inline void
1450 Tree<RootNodeType>::setValueOn(const Coord& xyz, const ValueType& value)
1451 {
1452  mRoot.setValueOn(xyz, value);
1453 }
1454 
1455 
1456 template<typename RootNodeType>
1457 template<typename ModifyOp>
1458 inline void
1459 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1460 {
1461  mRoot.modifyValue(xyz, op);
1462 }
1463 
1464 
1465 template<typename RootNodeType>
1466 template<typename ModifyOp>
1467 inline void
1468 Tree<RootNodeType>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1469 {
1470  mRoot.modifyValueAndActiveState(xyz, op);
1471 }
1472 
1473 
1474 template<typename RootNodeType>
1475 inline bool
1476 Tree<RootNodeType>::probeValue(const Coord& xyz, ValueType& value) const
1477 {
1478  return mRoot.probeValue(xyz, value);
1479 }
1480 
1481 
1483 
1484 
1485 template<typename RootNodeType>
1486 template<typename PruneOp>
1487 inline void
1489 {
1490  this->clearAllAccessors();
1491  mRoot.pruneOp(op);
1492 }
1493 
1494 
1495 template<typename RootNodeType>
1496 inline void
1498 {
1499  TolerancePrune<ValueType> op(tolerance);
1500  this->pruneOp(op);
1501 }
1502 
1503 
1504 template<typename RootNodeType>
1505 inline void
1507 {
1508  InactivePrune<ValueType> op(bg);
1509  this->pruneOp(op);
1510 }
1511 
1512 
1513 template<typename RootNodeType>
1514 inline void
1516 {
1517  this->pruneInactive(this->background());
1518 }
1519 
1520 
1521 template<typename RootNodeType>
1522 inline void
1524 {
1525  LevelSetPrune<ValueType> op(this->background());
1526  this->pruneOp(op);
1527 }
1528 
1529 
1530 template<typename RootNodeType>
1531 inline void
1532 Tree<RootNodeType>::addTile(Index level, const Coord& xyz,
1533  const ValueType& value, bool active)
1534 {
1535  mRoot.addTile(level, xyz, value, active);
1536 }
1537 
1538 
1539 template<typename RootNodeType>
1540 template<typename NodeT>
1541 inline NodeT*
1542 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1543 {
1544  this->clearAllAccessors();
1545  return mRoot.template stealNode<NodeT>(xyz, value, active);
1546 }
1547 
1548 
1549 template<typename RootNodeType>
1550 inline typename RootNodeType::LeafNodeType*
1552 {
1553  return mRoot.touchLeaf(xyz);
1554 }
1555 
1556 
1557 template<typename RootNodeType>
1558 inline typename RootNodeType::LeafNodeType*
1560 {
1561  return mRoot.probeLeaf(xyz);
1562 }
1563 
1564 
1565 template<typename RootNodeType>
1566 inline const typename RootNodeType::LeafNodeType*
1567 Tree<RootNodeType>::probeConstLeaf(const Coord& xyz) const
1568 {
1569  return mRoot.probeConstLeaf(xyz);
1570 }
1571 
1572 
1573 template<typename RootNodeType>
1574 template<typename NodeType>
1575 inline NodeType*
1577 {
1578  return mRoot.template probeNode<NodeType>(xyz);
1579 }
1580 
1581 
1582 template<typename RootNodeType>
1583 template<typename NodeType>
1584 inline const NodeType*
1585 Tree<RootNodeType>::probeNode(const Coord& xyz) const
1586 {
1587  return this->template probeConstNode<NodeType>(xyz);
1588 }
1589 
1590 
1591 template<typename RootNodeType>
1592 template<typename NodeType>
1593 inline const NodeType*
1594 Tree<RootNodeType>::probeConstNode(const Coord& xyz) const
1595 {
1596  return mRoot.template probeConstNode<NodeType>(xyz);
1597 }
1598 
1599 
1601 
1602 
1603 template<typename RootNodeType>
1604 inline void
1605 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1606 {
1607  this->clearAllAccessors();
1608  return mRoot.fill(bbox, value, active);
1609 }
1610 
1611 
1612 template<typename RootNodeType>
1613 inline void
1615 {
1616  mRoot.signedFloodFill(outside, inside);
1617 }
1618 
1619 
1620 template<typename RootNodeType>
1623 {
1624  Metadata::Ptr result;
1625  if (Metadata::isRegisteredType(valueType())) {
1626  typedef TypedMetadata<ValueType> MetadataT;
1627  result = Metadata::createMetadata(valueType());
1628  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1629  m->value() = mRoot.background();
1630  }
1631  }
1632  return result;
1633 }
1634 
1635 
1637 
1638 
1639 template<typename RootNodeType>
1640 inline void
1642 {
1643  this->clearAllAccessors();
1644  mRoot.voxelizeActiveTiles();
1645 }
1646 
1647 
1648 template<typename RootNodeType>
1649 inline void
1651 {
1652  this->clearAllAccessors();
1653  other.clearAllAccessors();
1654  switch (policy) {
1655  case MERGE_ACTIVE_STATES:
1656  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1657  case MERGE_NODES:
1658  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1660  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1661  }
1662 }
1663 
1664 
1665 template<typename RootNodeType>
1666 template<typename OtherRootNodeType>
1667 inline void
1669 {
1670  this->clearAllAccessors();
1671  mRoot.topologyUnion(other.getRootNode());
1672 }
1673 
1674 template<typename RootNodeType>
1675 template<typename OtherRootNodeType>
1676 inline void
1678 {
1679  this->clearAllAccessors();
1680  mRoot.topologyIntersection(other.getRootNode());
1681 }
1682 
1683 template<typename RootNodeType>
1684 template<typename OtherRootNodeType>
1685 inline void
1687 {
1688  this->clearAllAccessors();
1689  mRoot.topologyDifference(other.getRootNode());
1690 }
1691 
1693 
1694 
1697 template<typename ValueT, typename CombineOp>
1699 {
1700  CombineOpAdapter(CombineOp& op): op(op) {}
1701 
1702  void operator()(CombineArgs<ValueT>& args) const {
1703  op(args.a(), args.b(), args.result());
1704  }
1705 
1706  CombineOp& op;
1707 };
1708 
1709 
1710 template<typename RootNodeType>
1711 template<typename CombineOp>
1712 inline void
1713 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1714 {
1716  this->combineExtended(other, extendedOp, prune);
1717 }
1718 
1719 
1722 #ifndef _MSC_VER
1723 template<typename RootNodeType>
1724 template<typename CombineOp>
1725 inline void
1726 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1727 {
1729  this->combineExtended(other, extendedOp, prune);
1730 }
1731 #endif
1732 
1733 
1734 template<typename RootNodeType>
1735 template<typename ExtendedCombineOp>
1736 inline void
1737 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1738 {
1739  this->clearAllAccessors();
1740  mRoot.combine(other.getRootNode(), op, prune);
1741 }
1742 
1743 
1746 #ifndef _MSC_VER
1747 template<typename RootNodeType>
1748 template<typename ExtendedCombineOp>
1749 inline void
1750 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1751 {
1752  this->clearAllAccessors();
1753  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1754 }
1755 #endif
1756 
1757 
1758 template<typename RootNodeType>
1759 template<typename CombineOp>
1760 inline void
1761 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune)
1762 {
1764  this->combine2Extended(a, b, extendedOp, prune);
1765 }
1766 
1767 
1770 #ifndef _MSC_VER
1771 template<typename RootNodeType>
1772 template<typename CombineOp>
1773 inline void
1774 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune)
1775 {
1777  this->combine2Extended(a, b, extendedOp, prune);
1778 }
1779 #endif
1780 
1781 
1782 template<typename RootNodeType>
1783 template<typename ExtendedCombineOp>
1784 inline void
1786  ExtendedCombineOp& op, bool prune)
1787 {
1788  this->clearAllAccessors();
1789  mRoot.combine2(a.mRoot, b.mRoot, op, prune);
1790 }
1791 
1792 
1795 #ifndef _MSC_VER
1796 template<typename RootNodeType>
1797 template<typename ExtendedCombineOp>
1798 inline void
1800  const ExtendedCombineOp& op, bool prune)
1801 {
1802  this->clearAllAccessors();
1803  mRoot.template combine2<const ExtendedCombineOp>(a.mRoot, b.mRoot, op, prune);
1804 }
1805 #endif
1806 
1807 
1809 
1810 
1811 template<typename RootNodeType>
1812 template<typename VisitorOp>
1813 inline void
1815 {
1816  this->clearAllAccessors();
1817  mRoot.template visit<VisitorOp>(op);
1818 }
1819 
1820 
1821 template<typename RootNodeType>
1822 template<typename VisitorOp>
1823 inline void
1824 Tree<RootNodeType>::visit(VisitorOp& op) const
1825 {
1826  mRoot.template visit<VisitorOp>(op);
1827 }
1828 
1829 
1832 template<typename RootNodeType>
1833 template<typename VisitorOp>
1834 inline void
1835 Tree<RootNodeType>::visit(const VisitorOp& op)
1836 {
1837  this->clearAllAccessors();
1838  mRoot.template visit<const VisitorOp>(op);
1839 }
1840 
1841 
1844 template<typename RootNodeType>
1845 template<typename VisitorOp>
1846 inline void
1847 Tree<RootNodeType>::visit(const VisitorOp& op) const
1848 {
1849  mRoot.template visit<const VisitorOp>(op);
1850 }
1851 
1852 
1854 
1855 
1856 template<typename RootNodeType>
1857 template<typename OtherTreeType, typename VisitorOp>
1858 inline void
1859 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1860 {
1861  this->clearAllAccessors();
1862  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1863  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1864 }
1865 
1866 
1867 template<typename RootNodeType>
1868 template<typename OtherTreeType, typename VisitorOp>
1869 inline void
1870 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1871 {
1872  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1873  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1874 }
1875 
1876 
1879 template<typename RootNodeType>
1880 template<typename OtherTreeType, typename VisitorOp>
1881 inline void
1882 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1883 {
1884  this->clearAllAccessors();
1885  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1886  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1887 }
1888 
1889 
1892 template<typename RootNodeType>
1893 template<typename OtherTreeType, typename VisitorOp>
1894 inline void
1895 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1896 {
1897  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1898  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1899 }
1900 
1901 
1903 
1904 
1905 template<typename RootNodeType>
1906 inline const Name&
1908 {
1909  static tbb::atomic<const Name*> sTypeName;
1910  if (sTypeName == NULL) {
1911  std::vector<Index> dims;
1912  Tree::getNodeLog2Dims(dims);
1913  std::ostringstream ostr;
1914  ostr << "Tree_" << typeNameAsString<ValueType>();
1915  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1916  ostr << "_" << dims[i];
1917  }
1918  Name* s = new Name(ostr.str());
1919  if (sTypeName.compare_and_swap(s, NULL) != NULL) delete s;
1920  }
1921  return *sTypeName;
1922 }
1923 
1924 
1925 template<typename RootNodeType>
1926 template<typename OtherRootNodeType>
1927 inline bool
1929 {
1930  return mRoot.hasSameTopology(other.getRootNode());
1931 }
1932 
1933 
1934 template<typename RootNodeType>
1935 Index64
1937 {
1938  Coord dim(0, 0, 0);
1939  this->evalActiveVoxelDim(dim);
1940  const Index64
1941  totalVoxels = dim.x() * dim.y() * dim.z(),
1942  activeVoxels = this->activeVoxelCount();
1943  assert(totalVoxels >= activeVoxels);
1944  return totalVoxels - activeVoxels;
1945 }
1946 
1947 
1948 template<typename RootNodeType>
1949 inline bool
1951 {
1952  bbox.reset(); // default invalid bbox
1953 
1954  if (this->empty()) return false; // empty
1955 
1956  mRoot.evalActiveBoundingBox(bbox, false);
1957 
1958  return true;// not empty
1959 }
1960 
1961 template<typename RootNodeType>
1962 inline bool
1964 {
1965 
1966  bbox.reset(); // default invalid bbox
1967 
1968  if (this->empty()) return false; // empty
1969 
1970  mRoot.evalActiveBoundingBox(bbox, true);
1971 
1972  return true;// not empty
1973 }
1974 
1975 
1976 template<typename RootNodeType>
1977 inline bool
1979 {
1980  CoordBBox bbox;
1981  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1982  dim = bbox.extents();
1983  return notEmpty;
1984 }
1985 
1986 
1987 template<typename RootNodeType>
1988 inline bool
1990 {
1991  CoordBBox bbox;
1992  bool notEmpty = this->evalLeafBoundingBox(bbox);
1993  dim = bbox.extents();
1994  return notEmpty;
1995 }
1996 
1997 
1998 template<typename RootNodeType>
1999 inline void
2001 {
2002  minVal = maxVal = zeroVal<ValueType>();
2003  if (ValueOnCIter iter = this->cbeginValueOn()) {
2004  minVal = maxVal = *iter;
2005  for (++iter; iter; ++iter) {
2006  const ValueType& val = *iter;
2007  if (val < minVal) minVal = val;
2008  if (val > maxVal) maxVal = val;
2009  }
2010  }
2011 }
2012 
2013 
2014 template<typename RootNodeType>
2015 inline void
2016 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
2017 {
2018  dims.clear();
2019  RootNodeType::getNodeLog2Dims(dims);
2020 }
2021 
2022 
2023 template<typename RootNodeType>
2024 inline void
2025 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
2026 {
2027  if (verboseLevel <= 0) return;
2028 
2029  struct OnExit {
2030  std::ostream& os;
2031  std::streamsize savedPrecision;
2032  OnExit(std::ostream& os): os(os), savedPrecision(os.precision()) {}
2033  ~OnExit() { os.precision(savedPrecision); }
2034  };
2035  OnExit restorePrecision(os);
2036 
2037  std::vector<Index> dims;
2038  Tree::getNodeLog2Dims(dims);
2039 
2040  std::vector<Index64> nodeCount;
2041 
2042  os << "Information about Tree:\n"
2043  << " Type: " << this->type() << "\n";
2044 
2045  os << " Configuration:\n";
2046  if (verboseLevel <= 1) {
2047  // Print node types and sizes.
2048  os << " Root(" << mRoot.getTableSize() << ")";
2049  if (dims.size() > 1) {
2050  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2051  os << ", Internal(" << (1 << dims[i]) << "^3)";
2052  }
2053  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
2054  }
2055  } else {
2056  // Print node types, counts and sizes.
2057  nodeCount.resize(dims.size());
2058  for (NodeCIter it = cbeginNode(); it; ++it) {
2059  ++(nodeCount[it.getDepth()]);
2060  }
2061  os << " Root(1 x " << mRoot.getTableSize() << ")";
2062  if (dims.size() > 1) {
2063  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2064  os << ", Internal(" << util::formattedInt(nodeCount[i]);
2065  os << " x " << (1 << dims[i]) << "^3)";
2066  }
2067  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
2068  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
2069  }
2070  }
2071  os << " Background value: " << mRoot.background() << "\n";
2072 
2073  if (verboseLevel == 1) return;
2074 
2075  // The following is tree information that is expensive to extract.
2076 
2077  if (nodeCount.empty()) {
2078  nodeCount.resize(dims.size());
2079  for (NodeCIter it = cbeginNode(); it; ++it) {
2080  ++(nodeCount[it.getDepth()]);
2081  }
2082  }
2083 
2084  // Statistics of topology and values
2085  ValueType minVal, maxVal;
2086  this->evalMinMax(minVal, maxVal);
2087  os << " Min value: " << minVal << "\n";
2088  os << " Max value: " << maxVal << "\n";
2089 
2090  const uint64_t
2091  leafCount = *nodeCount.rbegin(),
2092  numActiveVoxels = this->activeVoxelCount(),
2093  numActiveLeafVoxels = this->activeLeafVoxelCount();
2094 
2095  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
2096 
2097  Coord dim(0, 0, 0);
2098  uint64_t totalVoxels = 0;
2099  if (numActiveVoxels) { // nonempty
2100  CoordBBox bbox;
2101  this->evalActiveVoxelBoundingBox(bbox);
2102  dim = bbox.extents();
2103  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2104 
2105  os << " Bounding box of active voxels: " << bbox << "\n";
2106  os << " Dimensions of active voxels: "
2107  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
2108 
2109  const double activeRatio = (100.0 * numActiveVoxels) / totalVoxels;
2110  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2111 
2112  if (leafCount>0) {
2113  const double fillRatio =
2114  (100.0 * numActiveLeafVoxels) / (leafCount * LeafNodeType::NUM_VOXELS);
2115  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2116  }
2117  } else {
2118  os << " Tree is empty!\n";
2119  }
2120  os << std::flush;
2121 
2122  if (verboseLevel == 2) return;
2123 
2124  // Memory footprint in bytes
2125  const uint64_t
2126  actualMem = this->memUsage(),
2127  denseMem = sizeof(ValueType) * totalVoxels,
2128  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2130 
2131  os << "Memory footprint:\n";
2132  util::printBytes(os, actualMem, " Actual footprint: ");
2133  util::printBytes(os, voxelsMem, " Voxel footprint: ");
2134 
2135  if (numActiveVoxels) {
2136  util::printBytes(os, denseMem, " Dense* footprint: ");
2137  os << " Actual footprint is " << (100.0 * actualMem / denseMem)
2138  << "% of dense* footprint\n";
2139  os << " Leaf voxel footprint is " << (100.0 * voxelsMem / actualMem)
2140  << "% of actual footprint\n";
2141  os << " *Dense refers to the smallest equivalent non-sparse volume" << std::endl;
2142  }
2143 }
2144 
2145 } // namespace tree
2146 } // namespace OPENVDB_VERSION_NAME
2147 } // namespace openvdb
2148 
2149 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
2150 
2151 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2152 // All rights reserved. This software is distributed under the
2153 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
#define OPENVDB_API
Helper macros for defining library symbol visibility.
Definition: Platform.h:162
bool operator!=(const Tree &) const
Definition: Tree.h:262
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:205
boost::shared_ptr< const TreeBase > ConstPtr
Definition: Tree.h:68
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1211
Tree5&lt;T, N1, N2, N3, N4&gt;::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:1106
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1219
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:964
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOnCIter > ValueOnCIter
Definition: Tree.h:1029
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1227
virtual Index64 inactiveLeafVoxelCount() const
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:326
TreeValueIteratorBase< Tree, typename RootNodeType::ValueAllIter > ValueAllIter
Definition: Tree.h:1026
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOnIter > ValueOnIter
Definition: Tree.h:1028
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:996
virtual const Name & type() const
Return the name of this type of tree.
Definition: Tree.h:259
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOffIter > ValueOffIter
Definition: Tree.h:1030
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1199
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1043
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:239
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:517
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:339
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:1387
Tree< RootNode< InternalNode< LeafNode< T, N2 >, N1 > > > Type
Definition: Tree.h:1087
const ValueType & a() const
Get the A input value.
Definition: Types.h:256
Helper class for use with Tree::pruneOp() to replace constant branches (to within the provided tolera...
Definition: tree/Util.h:47
void visitActiveBBox(BBoxOp &op) const
Definition: Tree.h:840
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1116
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:424
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:426
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:422
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:995
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1016
Helper class for use with Tree::pruneOp() to replace inactive branches with more memory-efficient ina...
Definition: tree/Util.h:74
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:1567
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1042
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1327
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:1459
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1048
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1152
Index32 Index
Definition: Types.h:56
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1195
boost::shared_ptr< const Tree > ConstPtr
Definition: Tree.h:182
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1009
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:396
virtual Index32 nonLeafCount() const
Return the number of non-leaf nodes.
Definition: Tree.h:322
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1049
const ValueType & b() const
Get the B input value.
Definition: Types.h:258
Tree< RootNode< InternalNode< InternalNode< InternalNode< LeafNode< T, N4 >, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1108
RootNodeType::ValueType ValueType
Definition: Tree.h:185
MergePolicy
Definition: Types.h:188
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:1928
Helper class for use with Tree::pruneOp() to prune any branches whose values are all inactive and rep...
Definition: tree/Util.h:99
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1207
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1698
Definition: Types.h:190
static bool isRegisteredType(const Name &typeName)
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:1551
CombineOp & op
Definition: Tree.h:1706
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:658
Index64 activeTileCount() const
Definition: Tree.h:334
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:470
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOffCIter > ValueOffCIter
Definition: Tree.h:1031
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:982
virtual TreeBase::Ptr copy() const
Return a pointer to a deep copy of this tree.
Definition: Tree.h:251
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:102
virtual Metadata::Ptr getBackgroundValue() const
Return this tree&#39;s background value wrapped as metadata.
Definition: Tree.h:87
RootNodeType mRoot
Definition: Tree.h:1075
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1179
This struct collects both input and output arguments to &quot;grid combiner&quot; functors used with the tree::...
Definition: Types.h:232
Tree4&lt;T, N1, N2, N3&gt;::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:1096
boost::shared_ptr< Metadata > Ptr
Definition: metadata/Metadata.h:52
Tree< typename RootNodeType::template ValueConverter< OtherValueType >::Type > Type
Definition: Tree.h:198
Tree< RootNode< InternalNode< InternalNode< LeafNode< T, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1097
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: Tree.h:1442
Internal table nodes for OpenVDB trees.
NodeIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > NodeCIter
Iterator over all nodes in this tree.
Definition: Tree.h:1003
Base class for typed trees.
Definition: Tree.h:64
const RootNodeType & getRootNode() const
Return this tree&#39;s root node.
Definition: Tree.h:270
#define OPENVDB_VERSION_NAME
Definition: version.h:45
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:1559
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1223
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:505
#define OPENVDB_LOG_WARN(message)
Definition: logging.h:39
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:141
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1155
CombineOpAdapter(CombineOp &op)
Definition: Tree.h:1700
ValueConverter&lt;T&gt;::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:197
const ValueType & background() const
Return this tree&#39;s background value.
Definition: Tree.h:539
uint32_t Index32
Definition: Types.h:54
uint64_t Index64
Definition: Types.h:55
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1476
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1211
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1037
virtual Index treeDepth() const
Return the depth of this tree.
Definition: Tree.h:318
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1023
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:1532
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: Tree.h:1395
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
Tree3&lt;T, N1, N2&gt;::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1086
TreeBase()
Definition: Tree.h:70
RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:186
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1167
boost::shared_ptr< TreeBase > Ptr
Definition: Tree.h:67
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:1133
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1076
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:130
tbb::concurrent_hash_map< ValueAccessorBase< const Tree > *, bool > ConstAccessorRegistry
Definition: Tree.h:1062
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don&#39;t change its value.
Definition: Tree.h:1411
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1022
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:514
const ValueType & result() const
Get the output value.
Definition: Types.h:261
Definition: Exceptions.h:84
Tree()
Definition: Tree.h:202
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1185
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:1419
virtual ~Tree()
Definition: Tree.h:248
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)
The root node of an OpenVDB tree.
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1370
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1203
_RootNodeType RootNodeType
Definition: Tree.h:184
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1191
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1015
Definition: Types.h:346
virtual Index32 leafCount() const
Return the number of leaf nodes.
Definition: Tree.h:320
Tree(const OtherTreeType &other, const ValueType &inactiveValue, const ValueType &activeValue, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:219
void operator()(CombineArgs< ValueT > &args) const
Definition: Tree.h:1702
Templated metadata class to hold specific types.
Definition: metadata/Metadata.h:137
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1215
bool operator==(const Tree &) const
Definition: Tree.h:261
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don&#39;t change its active state.
Definition: Tree.h:1426
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1125
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1077
tbb::concurrent_hash_map< ValueAccessorBase< Tree > *, bool > AccessorRegistry
Definition: Tree.h:1061
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
RootNodeType & getRootNode()
Return this tree&#39;s root node.
Definition: Tree.h:269
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1468
std::string Name
Definition: Name.h:44
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:989
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:981
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:246
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueAllCIter > ValueAllCIter
Definition: Tree.h:1027
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1173
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1161
void setBackground(const ValueType &background)
Replace this tree&#39;s background value.
Definition: Tree.h:541
Definition: Tree.h:178
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1036
virtual ~TreeBase()
Definition: Tree.h:71
const RootNodeType & root() const
Return this tree&#39;s root node.
Definition: Tree.h:267
virtual Index64 activeLeafVoxelCount() const
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:324
static Metadata::Ptr createMetadata(const Name &typeName)
Creates a new Metadata from the metadata type registry.
boost::shared_ptr< Tree > Ptr
Definition: Tree.h:181
virtual Index64 activeVoxelCount() const
Return the total number of active voxels.
Definition: Tree.h:328
virtual void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const
Write out all data buffers for this tree.
Definition: Tree.h:1282
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:988
void signedFloodFill()
Set the values of all inactive voxels and tiles of a narrow-band level set from the signs of the acti...
Definition: Tree.h:550
virtual void getIndexRange(CoordBBox &bbox) const
Min and max are both inclusive.
Definition: Tree.h:544
virtual Name valueType() const
Return the name of the type of a voxel&#39;s value (e.g., &quot;float&quot; or &quot;vec3d&quot;)
Definition: Tree.h:254