OpenVDB  2.3.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 
215  template<typename OtherRootType>
216  explicit Tree(const Tree<OtherRootType>& other): TreeBase(other), mRoot(other.root())
217  {
218  }
219 
230  template<typename OtherTreeType>
231  Tree(const OtherTreeType& other,
232  const ValueType& inactiveValue,
233  const ValueType& activeValue,
234  TopologyCopy):
235  TreeBase(other),
236  mRoot(other.root(), inactiveValue, activeValue, TopologyCopy())
237  {
238  }
239 
251  template<typename OtherTreeType>
252  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
253  TreeBase(other),
254  mRoot(other.root(), background, TopologyCopy())
255  {
256  }
257 
259  Tree(const ValueType& background): mRoot(background) {}
260 
261  virtual ~Tree() { releaseAllAccessors(); }
262 
264  virtual TreeBase::Ptr copy() const { return TreeBase::Ptr(new Tree(*this)); }
265 
267  virtual Name valueType() const { return typeNameAsString<ValueType>(); }
268 
270  static const Name& treeType();
272  virtual const Name& type() const { return this->treeType(); }
273 
274  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
275  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
276 
278  RootNodeType& root() { return mRoot; }
280  const RootNodeType& root() const { return mRoot; }
282 
283  OPENVDB_DEPRECATED RootNodeType& getRootNode() { return mRoot; }
286  OPENVDB_DEPRECATED const RootNodeType& getRootNode() const { return mRoot; }
288 
289 
290  //
291  // Tree methods
292  //
295  template<typename OtherRootNodeType>
296  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
297 
298  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const;
299  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
300  virtual bool evalActiveVoxelDim(Coord& dim) const;
301  virtual bool evalLeafDim(Coord& dim) const;
302 
306  static void getNodeLog2Dims(std::vector<Index>& dims);
307 
308 
309  //
310  // I/O methods
311  //
315  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
319  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
321  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false);
323  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const;
324 
325  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
326 
327 
328  //
329  // Statistics
330  //
334  virtual Index treeDepth() const { return DEPTH; }
336  virtual Index32 leafCount() const { return mRoot.leafCount(); }
338  virtual Index32 nonLeafCount() const { return mRoot.nonLeafCount(); }
340  virtual Index64 activeLeafVoxelCount() const { return mRoot.onLeafVoxelCount(); }
342  virtual Index64 inactiveLeafVoxelCount() const { return mRoot.offLeafVoxelCount(); }
344  virtual Index64 activeVoxelCount() const { return mRoot.onVoxelCount(); }
346  virtual Index64 inactiveVoxelCount() const;
347 
350  Index64 activeTileCount() const { return mRoot.onTileCount(); }
351 
353  void evalMinMax(ValueType &min, ValueType &max) const;
354 
355  virtual Index64 memUsage() const { return sizeof(*this) + mRoot.memUsage(); }
356 
357 
358  //
359  // Voxel access methods (using signed indexing)
360  //
362  const ValueType& getValue(const Coord& xyz) const;
365  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
366 
370  int getValueDepth(const Coord& xyz) const;
371 
373  void setActiveState(const Coord& xyz, bool on);
375  void setValueOnly(const Coord& xyz, const ValueType& value);
377  void setValueOn(const Coord& xyz);
379  void setValueOn(const Coord& xyz, const ValueType& value);
381  void setValue(const Coord& xyz, const ValueType& value);
384  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
386  void setValueOff(const Coord& xyz);
388  void setValueOff(const Coord& xyz, const ValueType& value);
389 
408  template<typename ModifyOp>
409  void modifyValue(const Coord& xyz, const ModifyOp& op);
410 
430  template<typename ModifyOp>
431  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
432 
435  bool probeValue(const Coord& xyz, ValueType& value) const;
436 
438  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
440  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
442  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
443 
453  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
454 
461  template<typename PruneOp> void pruneOp(PruneOp&);
462 
466  void prune(const ValueType& tolerance = zeroVal<ValueType>());
467 
470  void pruneInactive(const ValueType&);
471 
474  void pruneInactive();
475 
482  void pruneLevelSet();
483 
486  void addLeaf(LeafNodeType& leaf) { mRoot.addLeaf(&leaf); }
487 
492  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
493 
498  template<typename NodeT>
499  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
500 
506  LeafNodeType* touchLeaf(const Coord& xyz);
507 
509  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
512  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
513  template<typename NodeType> const NodeType* probeNode(const Coord& xyz) const;
515 
517  LeafNodeType* probeLeaf(const Coord& xyz);
520  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
521  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
523 
524 
525  //
526  // Aux methods
527  //
530  bool empty() const { return mRoot.empty(); }
531 
533  void clear() { this->clearAllAccessors(); mRoot.clear(); }
534 
536  void clearAllAccessors();
537 
539  void attachAccessor(ValueAccessorBase<Tree>&) const;
542  void attachAccessor(ValueAccessorBase<const Tree>&) const;
544 
545  void releaseAccessor(ValueAccessorBase<Tree>&) const;
547  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
549 
552  virtual Metadata::Ptr getBackgroundValue() const;
553 
555  const ValueType& background() const { return mRoot.background(); }
557  void setBackground(const ValueType& background) { mRoot.setBackground(background); }
558 
560  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
561 
566  void signedFloodFill() { mRoot.signedFloodFill(); }
567 
573  void signedFloodFill(const ValueType& outside, const ValueType& inside);
574 
576  void voxelizeActiveTiles();
577 
585  void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
586 
600  template<typename OtherRootNodeType>
601  void topologyUnion(const Tree<OtherRootNodeType>& other);
602 
616  template<typename OtherRootNodeType>
617  void topologyIntersection(const Tree<OtherRootNodeType>& other);
618 
629  template<typename OtherRootNodeType>
630  void topologyDifference(const Tree<OtherRootNodeType>& other);
631 
676  template<typename CombineOp>
677  void combine(Tree& other, CombineOp& op, bool prune = false);
678 #ifndef _MSC_VER
679  template<typename CombineOp>
680  void combine(Tree& other, const CombineOp& op, bool prune = false);
681 #endif
682 
721  template<typename ExtendedCombineOp>
722  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
723 #ifndef _MSC_VER
724  template<typename ExtendedCombineOp>
725  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
726 #endif
727 
756  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
757  void combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune = false);
758 #ifndef _MSC_VER
759  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
760  void combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune = false);
761 #endif
762 
836  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
837  void combine2Extended(const Tree& a, const OtherTreeType& b, ExtendedCombineOp& op,
838  bool prune = false);
839 #ifndef _MSC_VER
840  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
841  void combine2Extended(const Tree& a, const OtherTreeType& b, const ExtendedCombineOp&,
842  bool prune = false);
843 #endif
844 
885  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
886 
940  template<typename VisitorOp> void visit(VisitorOp& op);
941  template<typename VisitorOp> void visit(const VisitorOp& op);
942 
947  template<typename VisitorOp> void visit(VisitorOp& op) const;
948  template<typename VisitorOp> void visit(const VisitorOp& op) const;
949 
997  template<typename OtherTreeType, typename VisitorOp>
998  void visit2(OtherTreeType& other, VisitorOp& op);
999  template<typename OtherTreeType, typename VisitorOp>
1000  void visit2(OtherTreeType& other, const VisitorOp& op);
1001 
1012  template<typename OtherTreeType, typename VisitorOp>
1013  void visit2(OtherTreeType& other, VisitorOp& op) const;
1014  template<typename OtherTreeType, typename VisitorOp>
1015  void visit2(OtherTreeType& other, const VisitorOp& op) const;
1016 
1017 
1018  //
1019  // Iteration
1020  //
1022  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
1024  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
1025  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
1027 
1029  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
1031  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
1032  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
1034 
1036  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
1038  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
1039  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
1041 
1042 
1048 
1054 
1056  NodeIter beginNode() { return NodeIter(*this); }
1058  NodeCIter beginNode() const { return NodeCIter(*this); }
1059  NodeCIter cbeginNode() const { return NodeCIter(*this); }
1061 
1063  LeafIter beginLeaf() { return LeafIter(*this); }
1065  LeafCIter beginLeaf() const { return LeafCIter(*this); }
1066  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
1068 
1075 
1077  ValueAllIter beginValueAll() { return ValueAllIter(*this); }
1079  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
1080  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
1082 
1083  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
1085  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
1086  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
1088 
1089  ValueOffIter beginValueOff() { return ValueOffIter(*this); }
1091  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1092  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1094 
1097  template<typename IterT> IterT begin();
1100  template<typename CIterT> CIterT cbegin() const;
1101 
1102 
1103 protected:
1104  typedef tbb::concurrent_hash_map<ValueAccessorBase<Tree>*, bool> AccessorRegistry;
1105  typedef tbb::concurrent_hash_map<ValueAccessorBase<const Tree>*, bool> ConstAccessorRegistry;
1106 
1107  // Disallow assignment of instances of this class.
1108  Tree& operator=(const Tree&);
1109 
1112  void releaseAllAccessors();
1113 
1114 
1115  //
1116  // Data members
1117  //
1118  RootNodeType mRoot; // root node of the tree
1121 }; // end of Tree class
1122 
1123 
1128 template<typename T, Index N1, Index N2>
1129 struct Tree3 {
1131 };
1132 
1133 
1138 template<typename T, Index N1, Index N2, Index N3>
1139 struct Tree4 {
1141 };
1142 
1143 
1148 template<typename T, Index N1, Index N2, Index N3, Index N4>
1149 struct Tree5 {
1152 };
1153 
1154 
1156 
1157 
1158 inline void
1159 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1160 {
1161  int32_t bufferCount;
1162  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1163  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1164 }
1165 
1166 
1167 inline void
1168 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1169 {
1170  int32_t bufferCount = 1;
1171  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1172 }
1173 
1174 
1175 inline void
1176 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1177 {
1178  os << " Tree Type: " << type()
1179  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1180  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1181  << " Leaf Node Count: " << leafCount() << std::endl
1182  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1183 }
1184 
1185 
1187 
1188 
1189 //
1190 // Type traits for tree iterators
1191 //
1192 
1195 template<typename TreeT, typename IterT> struct TreeIterTraits;
1196 
1197 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1198  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1199  return tree.beginRootChildren();
1200  }
1201 };
1202 
1203 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1204  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1205  return tree.cbeginRootChildren();
1206  }
1207 };
1208 
1209 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1210  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1211  return tree.beginRootTiles();
1212  }
1213 };
1214 
1215 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1216  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1217  return tree.cbeginRootTiles();
1218  }
1219 };
1220 
1221 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1222  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1223  return tree.beginRootDense();
1224  }
1225 };
1226 
1227 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1228  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1229  return tree.cbeginRootDense();
1230  }
1231 };
1232 
1233 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1234  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1235 };
1236 
1237 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1238  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1239 };
1240 
1241 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1242  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1243 };
1244 
1245 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1246  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1247 };
1248 
1249 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1250  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1251 };
1252 
1253 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1254  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1255 };
1256 
1257 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1258  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1259 };
1260 
1261 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1262  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1263 };
1264 
1265 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1266  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1267 };
1268 
1269 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1270  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1271 };
1272 
1273 
1274 template<typename RootNodeType>
1275 template<typename IterT>
1276 inline IterT
1278 {
1279  return TreeIterTraits<Tree, IterT>::begin(*this);
1280 }
1281 
1282 
1283 template<typename RootNodeType>
1284 template<typename IterT>
1285 inline IterT
1287 {
1288  return TreeIterTraits<Tree, IterT>::begin(*this);
1289 }
1290 
1291 
1293 
1294 
1295 template<typename RootNodeType>
1296 void
1297 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1298 {
1299  this->clearAllAccessors();
1300  TreeBase::readTopology(is, saveFloatAsHalf);
1301  mRoot.readTopology(is, saveFloatAsHalf);
1302 }
1303 
1304 
1305 template<typename RootNodeType>
1306 void
1307 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1308 {
1309  TreeBase::writeTopology(os, saveFloatAsHalf);
1310  mRoot.writeTopology(os, saveFloatAsHalf);
1311 }
1312 
1313 
1314 template<typename RootNodeType>
1315 inline void
1316 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1317 {
1318  this->clearAllAccessors();
1319  mRoot.readBuffers(is, saveFloatAsHalf);
1320 }
1321 
1322 
1323 template<typename RootNodeType>
1324 inline void
1325 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1326 {
1327  mRoot.writeBuffers(os, saveFloatAsHalf);
1328 }
1329 
1330 
1332 
1333 
1334 template<typename RootNodeType>
1335 inline void
1337 {
1338  typename AccessorRegistry::accessor a;
1339  mAccessorRegistry.insert(a, &accessor);
1340 }
1341 
1342 
1343 template<typename RootNodeType>
1344 inline void
1346 {
1347  typename ConstAccessorRegistry::accessor a;
1348  mConstAccessorRegistry.insert(a, &accessor);
1349 }
1350 
1351 
1352 template<typename RootNodeType>
1353 inline void
1355 {
1356  mAccessorRegistry.erase(&accessor);
1357 }
1358 
1359 
1360 template<typename RootNodeType>
1361 inline void
1363 {
1364  mConstAccessorRegistry.erase(&accessor);
1365 }
1366 
1367 
1368 template<typename RootNodeType>
1369 inline void
1371 {
1372  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1373  it != mAccessorRegistry.end(); ++it)
1374  {
1375  if (it->first) it->first->clear();
1376  }
1377 
1378  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1379  it != mConstAccessorRegistry.end(); ++it)
1380  {
1381  if (it->first) it->first->clear();
1382  }
1383 }
1384 
1385 
1386 template<typename RootNodeType>
1387 inline void
1389 {
1390  mAccessorRegistry.erase(NULL);
1391  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1392  it != mAccessorRegistry.end(); ++it)
1393  {
1394  it->first->release();
1395  }
1396  mAccessorRegistry.clear();
1397 
1398  mAccessorRegistry.erase(NULL);
1399  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1400  it != mConstAccessorRegistry.end(); ++it)
1401  {
1402  it->first->release();
1403  }
1404  mConstAccessorRegistry.clear();
1405 }
1406 
1407 
1409 
1410 
1411 template<typename RootNodeType>
1412 inline const typename RootNodeType::ValueType&
1413 Tree<RootNodeType>::getValue(const Coord& xyz) const
1414 {
1415  return mRoot.getValue(xyz);
1416 }
1417 
1418 
1419 template<typename RootNodeType>
1420 template<typename AccessT>
1421 inline const typename RootNodeType::ValueType&
1422 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1423 {
1424  return accessor.getValue(xyz);
1425 }
1426 
1427 
1428 template<typename RootNodeType>
1429 inline int
1430 Tree<RootNodeType>::getValueDepth(const Coord& xyz) const
1431 {
1432  return mRoot.getValueDepth(xyz);
1433 }
1434 
1435 
1436 template<typename RootNodeType>
1437 inline void
1439 {
1440  mRoot.setValueOff(xyz);
1441 }
1442 
1443 
1444 template<typename RootNodeType>
1445 inline void
1446 Tree<RootNodeType>::setValueOff(const Coord& xyz, const ValueType& value)
1447 {
1448  mRoot.setValueOff(xyz, value);
1449 }
1450 
1451 
1452 template<typename RootNodeType>
1453 inline void
1454 Tree<RootNodeType>::setActiveState(const Coord& xyz, bool on)
1455 {
1456  mRoot.setActiveState(xyz, on);
1457 }
1458 
1459 
1460 template<typename RootNodeType>
1461 inline void
1462 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value)
1463 {
1464  mRoot.setValueOn(xyz, value);
1465 }
1466 
1467 template<typename RootNodeType>
1468 inline void
1469 Tree<RootNodeType>::setValueOnly(const Coord& xyz, const ValueType& value)
1470 {
1471  mRoot.setValueOnly(xyz, value);
1472 }
1473 
1474 template<typename RootNodeType>
1475 template<typename AccessT>
1476 inline void
1477 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1478 {
1479  accessor.setValue(xyz, value);
1480 }
1481 
1482 
1483 template<typename RootNodeType>
1484 inline void
1486 {
1487  mRoot.setActiveState(xyz, true);
1488 }
1489 
1490 
1491 template<typename RootNodeType>
1492 inline void
1493 Tree<RootNodeType>::setValueOn(const Coord& xyz, const ValueType& value)
1494 {
1495  mRoot.setValueOn(xyz, value);
1496 }
1497 
1498 
1499 template<typename RootNodeType>
1500 template<typename ModifyOp>
1501 inline void
1502 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1503 {
1504  mRoot.modifyValue(xyz, op);
1505 }
1506 
1507 
1508 template<typename RootNodeType>
1509 template<typename ModifyOp>
1510 inline void
1511 Tree<RootNodeType>::modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op)
1512 {
1513  mRoot.modifyValueAndActiveState(xyz, op);
1514 }
1515 
1516 
1517 template<typename RootNodeType>
1518 inline bool
1519 Tree<RootNodeType>::probeValue(const Coord& xyz, ValueType& value) const
1520 {
1521  return mRoot.probeValue(xyz, value);
1522 }
1523 
1524 
1526 
1527 
1528 template<typename RootNodeType>
1529 template<typename PruneOp>
1530 inline void
1532 {
1533  this->clearAllAccessors();
1534  mRoot.pruneOp(op);
1535 }
1536 
1537 
1538 template<typename RootNodeType>
1539 inline void
1541 {
1542  TolerancePrune<ValueType> op(tolerance);
1543  this->pruneOp(op);
1544 }
1545 
1546 
1547 template<typename RootNodeType>
1548 inline void
1550 {
1551  InactivePrune<ValueType> op(bg);
1552  this->pruneOp(op);
1553 }
1554 
1555 
1556 template<typename RootNodeType>
1557 inline void
1559 {
1560  this->pruneInactive(this->background());
1561 }
1562 
1563 
1564 template<typename RootNodeType>
1565 inline void
1567 {
1568  LevelSetPrune<ValueType> op(this->background());
1569  this->pruneOp(op);
1570 }
1571 
1572 
1573 template<typename RootNodeType>
1574 inline void
1575 Tree<RootNodeType>::addTile(Index level, const Coord& xyz,
1576  const ValueType& value, bool active)
1577 {
1578  mRoot.addTile(level, xyz, value, active);
1579 }
1580 
1581 
1582 template<typename RootNodeType>
1583 template<typename NodeT>
1584 inline NodeT*
1585 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1586 {
1587  this->clearAllAccessors();
1588  return mRoot.template stealNode<NodeT>(xyz, value, active);
1589 }
1590 
1591 
1592 template<typename RootNodeType>
1593 inline typename RootNodeType::LeafNodeType*
1595 {
1596  return mRoot.touchLeaf(xyz);
1597 }
1598 
1599 
1600 template<typename RootNodeType>
1601 inline typename RootNodeType::LeafNodeType*
1603 {
1604  return mRoot.probeLeaf(xyz);
1605 }
1606 
1607 
1608 template<typename RootNodeType>
1609 inline const typename RootNodeType::LeafNodeType*
1610 Tree<RootNodeType>::probeConstLeaf(const Coord& xyz) const
1611 {
1612  return mRoot.probeConstLeaf(xyz);
1613 }
1614 
1615 
1616 template<typename RootNodeType>
1617 template<typename NodeType>
1618 inline NodeType*
1620 {
1621  return mRoot.template probeNode<NodeType>(xyz);
1622 }
1623 
1624 
1625 template<typename RootNodeType>
1626 template<typename NodeType>
1627 inline const NodeType*
1628 Tree<RootNodeType>::probeNode(const Coord& xyz) const
1629 {
1630  return this->template probeConstNode<NodeType>(xyz);
1631 }
1632 
1633 
1634 template<typename RootNodeType>
1635 template<typename NodeType>
1636 inline const NodeType*
1637 Tree<RootNodeType>::probeConstNode(const Coord& xyz) const
1638 {
1639  return mRoot.template probeConstNode<NodeType>(xyz);
1640 }
1641 
1642 
1644 
1645 
1646 template<typename RootNodeType>
1647 inline void
1648 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1649 {
1650  this->clearAllAccessors();
1651  return mRoot.fill(bbox, value, active);
1652 }
1653 
1654 
1655 template<typename RootNodeType>
1656 inline void
1658 {
1659  mRoot.signedFloodFill(outside, inside);
1660 }
1661 
1662 
1663 template<typename RootNodeType>
1666 {
1667  Metadata::Ptr result;
1668  if (Metadata::isRegisteredType(valueType())) {
1669  typedef TypedMetadata<ValueType> MetadataT;
1670  result = Metadata::createMetadata(valueType());
1671  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1672  m->value() = mRoot.background();
1673  }
1674  }
1675  return result;
1676 }
1677 
1678 
1680 
1681 
1682 template<typename RootNodeType>
1683 inline void
1685 {
1686  this->clearAllAccessors();
1687  mRoot.voxelizeActiveTiles();
1688 }
1689 
1690 
1691 template<typename RootNodeType>
1692 inline void
1694 {
1695  this->clearAllAccessors();
1696  other.clearAllAccessors();
1697  switch (policy) {
1698  case MERGE_ACTIVE_STATES:
1699  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1700  case MERGE_NODES:
1701  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1703  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1704  }
1705 }
1706 
1707 
1708 template<typename RootNodeType>
1709 template<typename OtherRootNodeType>
1710 inline void
1712 {
1713  this->clearAllAccessors();
1714  mRoot.topologyUnion(other.root());
1715 }
1716 
1717 template<typename RootNodeType>
1718 template<typename OtherRootNodeType>
1719 inline void
1721 {
1722  this->clearAllAccessors();
1723  mRoot.topologyIntersection(other.root());
1724 }
1725 
1726 template<typename RootNodeType>
1727 template<typename OtherRootNodeType>
1728 inline void
1730 {
1731  this->clearAllAccessors();
1732  mRoot.topologyDifference(other.root());
1733 }
1734 
1736 
1737 
1740 template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1742 {
1743  CombineOpAdapter(CombineOp& _op): op(_op) {}
1744 
1746  op(args.a(), args.b(), args.result());
1747  }
1748 
1749  CombineOp& op;
1750 };
1751 
1752 
1753 template<typename RootNodeType>
1754 template<typename CombineOp>
1755 inline void
1756 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1757 {
1759  this->combineExtended(other, extendedOp, prune);
1760 }
1761 
1762 
1765 #ifndef _MSC_VER
1766 template<typename RootNodeType>
1767 template<typename CombineOp>
1768 inline void
1769 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1770 {
1772  this->combineExtended(other, extendedOp, prune);
1773 }
1774 #endif
1775 
1776 
1777 template<typename RootNodeType>
1778 template<typename ExtendedCombineOp>
1779 inline void
1780 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1781 {
1782  this->clearAllAccessors();
1783  mRoot.combine(other.root(), op, prune);
1784 }
1785 
1786 
1789 #ifndef _MSC_VER
1790 template<typename RootNodeType>
1791 template<typename ExtendedCombineOp>
1792 inline void
1793 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1794 {
1795  this->clearAllAccessors();
1796  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1797 }
1798 #endif
1799 
1800 
1801 template<typename RootNodeType>
1802 template<typename CombineOp, typename OtherTreeType>
1803 inline void
1804 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1805 {
1807  this->combine2Extended(a, b, extendedOp, prune);
1808 }
1809 
1810 
1813 #ifndef _MSC_VER
1814 template<typename RootNodeType>
1815 template<typename CombineOp, typename OtherTreeType>
1816 inline void
1817 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1818 {
1820  this->combine2Extended(a, b, extendedOp, prune);
1821 }
1822 #endif
1823 
1824 
1825 template<typename RootNodeType>
1826 template<typename ExtendedCombineOp, typename OtherTreeType>
1827 inline void
1828 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1829  ExtendedCombineOp& op, bool prune)
1830 {
1831  this->clearAllAccessors();
1832  mRoot.combine2(a.root(), b.root(), op, prune);
1833 }
1834 
1835 
1839 #ifndef _MSC_VER
1840 template<typename RootNodeType>
1841 template<typename ExtendedCombineOp, typename OtherTreeType>
1842 inline void
1843 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
1844  const ExtendedCombineOp& op, bool prune)
1845 {
1846  this->clearAllAccessors();
1847  mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
1848 }
1849 #endif
1850 
1851 
1853 
1854 
1855 template<typename RootNodeType>
1856 template<typename VisitorOp>
1857 inline void
1859 {
1860  this->clearAllAccessors();
1861  mRoot.template visit<VisitorOp>(op);
1862 }
1863 
1864 
1865 template<typename RootNodeType>
1866 template<typename VisitorOp>
1867 inline void
1868 Tree<RootNodeType>::visit(VisitorOp& op) const
1869 {
1870  mRoot.template visit<VisitorOp>(op);
1871 }
1872 
1873 
1876 template<typename RootNodeType>
1877 template<typename VisitorOp>
1878 inline void
1879 Tree<RootNodeType>::visit(const VisitorOp& op)
1880 {
1881  this->clearAllAccessors();
1882  mRoot.template visit<const VisitorOp>(op);
1883 }
1884 
1885 
1888 template<typename RootNodeType>
1889 template<typename VisitorOp>
1890 inline void
1891 Tree<RootNodeType>::visit(const VisitorOp& op) const
1892 {
1893  mRoot.template visit<const VisitorOp>(op);
1894 }
1895 
1896 
1898 
1899 
1900 template<typename RootNodeType>
1901 template<typename OtherTreeType, typename VisitorOp>
1902 inline void
1903 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1904 {
1905  this->clearAllAccessors();
1906  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1907  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
1908 }
1909 
1910 
1911 template<typename RootNodeType>
1912 template<typename OtherTreeType, typename VisitorOp>
1913 inline void
1914 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1915 {
1916  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1917  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
1918 }
1919 
1920 
1923 template<typename RootNodeType>
1924 template<typename OtherTreeType, typename VisitorOp>
1925 inline void
1926 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1927 {
1928  this->clearAllAccessors();
1929  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1930  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
1931 }
1932 
1933 
1936 template<typename RootNodeType>
1937 template<typename OtherTreeType, typename VisitorOp>
1938 inline void
1939 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1940 {
1941  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1942  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
1943 }
1944 
1945 
1947 
1948 
1949 template<typename RootNodeType>
1950 inline const Name&
1952 {
1953  static tbb::atomic<const Name*> sTypeName;
1954  if (sTypeName == NULL) {
1955  std::vector<Index> dims;
1956  Tree::getNodeLog2Dims(dims);
1957  std::ostringstream ostr;
1958  ostr << "Tree_" << typeNameAsString<ValueType>();
1959  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1960  ostr << "_" << dims[i];
1961  }
1962  Name* s = new Name(ostr.str());
1963  if (sTypeName.compare_and_swap(s, NULL) != NULL) delete s;
1964  }
1965  return *sTypeName;
1966 }
1967 
1968 
1969 template<typename RootNodeType>
1970 template<typename OtherRootNodeType>
1971 inline bool
1973 {
1974  return mRoot.hasSameTopology(other.root());
1975 }
1976 
1977 
1978 template<typename RootNodeType>
1979 Index64
1981 {
1982  Coord dim(0, 0, 0);
1983  this->evalActiveVoxelDim(dim);
1984  const Index64
1985  totalVoxels = dim.x() * dim.y() * dim.z(),
1986  activeVoxels = this->activeVoxelCount();
1987  assert(totalVoxels >= activeVoxels);
1988  return totalVoxels - activeVoxels;
1989 }
1990 
1991 
1992 template<typename RootNodeType>
1993 inline bool
1995 {
1996  bbox.reset(); // default invalid bbox
1997 
1998  if (this->empty()) return false; // empty
1999 
2000  mRoot.evalActiveBoundingBox(bbox, false);
2001 
2002  return true;// not empty
2003 }
2004 
2005 template<typename RootNodeType>
2006 inline bool
2008 {
2009  bbox.reset(); // default invalid bbox
2010 
2011  if (this->empty()) return false; // empty
2012 
2013  mRoot.evalActiveBoundingBox(bbox, true);
2014 
2015  return true;// not empty
2016 }
2017 
2018 
2019 template<typename RootNodeType>
2020 inline bool
2022 {
2023  CoordBBox bbox;
2024  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
2025  dim = bbox.extents();
2026  return notEmpty;
2027 }
2028 
2029 
2030 template<typename RootNodeType>
2031 inline bool
2033 {
2034  CoordBBox bbox;
2035  bool notEmpty = this->evalLeafBoundingBox(bbox);
2036  dim = bbox.extents();
2037  return notEmpty;
2038 }
2039 
2040 
2041 template<typename RootNodeType>
2042 inline void
2044 {
2045  minVal = maxVal = zeroVal<ValueType>();
2046  if (ValueOnCIter iter = this->cbeginValueOn()) {
2047  minVal = maxVal = *iter;
2048  for (++iter; iter; ++iter) {
2049  const ValueType& val = *iter;
2050  if (val < minVal) minVal = val;
2051  if (val > maxVal) maxVal = val;
2052  }
2053  }
2054 }
2055 
2056 
2057 template<typename RootNodeType>
2058 inline void
2059 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
2060 {
2061  dims.clear();
2062  RootNodeType::getNodeLog2Dims(dims);
2063 }
2064 
2065 
2066 template<typename RootNodeType>
2067 inline void
2068 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
2069 {
2070  if (verboseLevel <= 0) return;
2071 
2072  struct OnExit {
2073  std::ostream& os;
2074  std::streamsize savedPrecision;
2075  OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
2076  ~OnExit() { os.precision(savedPrecision); }
2077  };
2078  OnExit restorePrecision(os);
2079 
2080  std::vector<Index> dims;
2081  Tree::getNodeLog2Dims(dims);
2082 
2083  std::vector<Index64> nodeCount;
2084 
2085  os << "Information about Tree:\n"
2086  << " Type: " << this->type() << "\n";
2087 
2088  os << " Configuration:\n";
2089  if (verboseLevel <= 1) {
2090  // Print node types and sizes.
2091  os << " Root(" << mRoot.getTableSize() << ")";
2092  if (dims.size() > 1) {
2093  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2094  os << ", Internal(" << (1 << dims[i]) << "^3)";
2095  }
2096  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
2097  }
2098  } else {
2099  // Print node types, counts and sizes.
2100  nodeCount.resize(dims.size());
2101  for (NodeCIter it = cbeginNode(); it; ++it) {
2102  ++(nodeCount[it.getDepth()]);
2103  }
2104  os << " Root(1 x " << mRoot.getTableSize() << ")";
2105  if (dims.size() > 1) {
2106  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2107  os << ", Internal(" << util::formattedInt(nodeCount[i]);
2108  os << " x " << (1 << dims[i]) << "^3)";
2109  }
2110  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
2111  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
2112  }
2113  }
2114  os << " Background value: " << mRoot.background() << "\n";
2115 
2116  if (verboseLevel == 1) return;
2117 
2118  // The following is tree information that is expensive to extract.
2119 
2120  if (nodeCount.empty()) {
2121  nodeCount.resize(dims.size());
2122  for (NodeCIter it = cbeginNode(); it; ++it) {
2123  ++(nodeCount[it.getDepth()]);
2124  }
2125  }
2126 
2127  // Statistics of topology and values
2128  ValueType minVal, maxVal;
2129  this->evalMinMax(minVal, maxVal);
2130  os << " Min value: " << minVal << "\n";
2131  os << " Max value: " << maxVal << "\n";
2132 
2133  const uint64_t
2134  leafCount = *nodeCount.rbegin(),
2135  numActiveVoxels = this->activeVoxelCount(),
2136  numActiveLeafVoxels = this->activeLeafVoxelCount();
2137 
2138  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
2139 
2140  Coord dim(0, 0, 0);
2141  uint64_t totalVoxels = 0;
2142  if (numActiveVoxels) { // nonempty
2143  CoordBBox bbox;
2144  this->evalActiveVoxelBoundingBox(bbox);
2145  dim = bbox.extents();
2146  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2147 
2148  os << " Bounding box of active voxels: " << bbox << "\n";
2149  os << " Dimensions of active voxels: "
2150  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
2151 
2152  const double activeRatio = (100.0 * numActiveVoxels) / totalVoxels;
2153  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2154 
2155  if (leafCount>0) {
2156  const double fillRatio =
2157  (100.0 * numActiveLeafVoxels) / (leafCount * LeafNodeType::NUM_VOXELS);
2158  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2159  }
2160  } else {
2161  os << " Tree is empty!\n";
2162  }
2163  os << std::flush;
2164 
2165  if (verboseLevel == 2) return;
2166 
2167  // Memory footprint in bytes
2168  const uint64_t
2169  actualMem = this->memUsage(),
2170  denseMem = sizeof(ValueType) * totalVoxels,
2171  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2173 
2174  os << "Memory footprint:\n";
2175  util::printBytes(os, actualMem, " Actual footprint: ");
2176  util::printBytes(os, voxelsMem, " Voxel footprint: ");
2177 
2178  if (numActiveVoxels) {
2179  util::printBytes(os, denseMem, " Dense* footprint: ");
2180  os << " Actual footprint is " << (100.0 * actualMem / denseMem)
2181  << "% of dense* footprint\n";
2182  os << " Leaf voxel footprint is " << (100.0 * voxelsMem / actualMem)
2183  << "% of actual footprint\n";
2184  os << " *Dense refers to the smallest equivalent non-sparse volume" << std::endl;
2185  }
2186 }
2187 
2188 } // namespace tree
2189 } // namespace OPENVDB_VERSION_NAME
2190 } // namespace openvdb
2191 
2192 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
2193 
2194 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2195 // All rights reserved. This software is distributed under the
2196 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
Tree< RootNode< InternalNode< InternalNode< InternalNode< LeafNode< T, N4 >, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1151
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
virtual Index64 inactiveLeafVoxelCount() const
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:342
void setBackground(const ValueType &background)
Replace this tree's background value.
Definition: Tree.h:557
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOnIter > ValueOnIter
Definition: Tree.h:1071
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1039
Definition: Tree.h:178
TreeValueIteratorBase< Tree, typename RootNodeType::ValueOffIter > ValueOffIter
Definition: Tree.h:1073
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1086
#define OPENVDB_API
Helper macros for defining library symbol visibility.
Definition: Platform.h:187
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1238
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1254
static Metadata::Ptr createMetadata(const Name &typeName)
Creates a new Metadata from the metadata type registry.
virtual Index64 activeLeafVoxelCount() const
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:340
virtual Index64 activeVoxelCount() const
Return the total number of active voxels.
Definition: Tree.h:344
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:533
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:566
void combine(FloatTreeT &lhsDist, IntTreeT &lhsIndex, FloatTreeT &rhsDist, IntTreeT &rhsIndex)
Definition: MeshToVolume.h:396
#define OPENVDB_DEPRECATED
Definition: Platform.h:47
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1262
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)
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:1149
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:885
boost::shared_ptr< const TreeBase > ConstPtr
Definition: Tree.h:68
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:438
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1059
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:205
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1159
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1085
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1370
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:1502
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1091
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:964
Index32 Index
Definition: Types.h:57
boost::shared_ptr< const Tree > ConstPtr
Definition: Tree.h:182
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
LeafIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > LeafCIter
Iterator over all leaf nodes in this tree.
Definition: Tree.h:1052
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOnCIter > ValueOnCIter
Definition: Tree.h:1072
virtual Index32 nonLeafCount() const
Return the number of non-leaf nodes.
Definition: Tree.h:338
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1222
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1743
RootNodeType::ValueType ValueType
Definition: Tree.h:185
MergePolicy
Definition: Types.h:221
TreeValueIteratorBase< Tree, typename RootNodeType::ValueAllIter > ValueAllIter
Definition: Tree.h:1069
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1198
virtual const Name & type() const
Return the name of this type of tree.
Definition: Tree.h:272
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:1594
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1228
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:252
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:355
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:1430
Helper class for use with Tree::pruneOp() to replace constant branches (to within the provided tolera...
Definition: tree/Util.h:47
Index64 activeTileCount() const
Definition: Tree.h:350
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:486
OPENVDB_DEPRECATED const RootNodeType & getRootNode() const
Return this tree's root node.
Definition: Tree.h:286
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:440
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:442
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:1025
virtual TreeBase::Ptr copy() const
Return a pointer to a deep copy of this tree.
Definition: Tree.h:264
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node's table.
Definition: Tree.h:1038
RootNodeType mRoot
Definition: Tree.h:1118
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1242
const AValueType & result() const
Get the output value.
Definition: Types.h:295
Tree< RootNode< InternalNode< LeafNode< T, N2 >, N1 > > > Type
Definition: Tree.h:1130
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don't change its value.
Definition: Tree.h:1485
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1234
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:216
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:1610
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:1602
virtual Metadata::Ptr getBackgroundValue() const
Return this tree's background value wrapped as metadata.
Definition: Tree.h:87
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1270
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1745
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1092
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:265
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:102
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:1972
ValueConverter::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:197
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1216
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:1139
Internal table nodes for OpenVDB trees.
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:141
uint64_t Index64
Definition: Types.h:56
#define OPENVDB_VERSION_NAME
Definition: version.h:45
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1519
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1246
CombineOp & op
Definition: Tree.h:1749
virtual Index treeDepth() const
Return the depth of this tree.
Definition: Tree.h:334
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1066
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1266
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueOffCIter > ValueOffCIter
Definition: Tree.h:1074
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
#define OPENVDB_LOG_WARN(message)
Log a warning message of the form 'someVar << "some text" << ...'.
Definition: logging.h:39
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don't change its value.
Definition: Tree.h:1438
Definition: Types.h:223
boost::shared_ptr< Metadata > Ptr
Definition: metadata/Metadata.h:52
NodeIteratorBase< const Tree, typename RootNodeType::ChildOnCIter > NodeCIter
Iterator over all nodes in this tree.
Definition: Tree.h:1046
Base class for typed trees.
Definition: Tree.h:64
const AValueType & a() const
Get the A input value.
Definition: Types.h:290
RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:186
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1195
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:521
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1119
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::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1210
TreeBase()
Definition: Tree.h:70
tbb::concurrent_hash_map< ValueAccessorBase< const Tree > *, bool > ConstAccessorRegistry
Definition: Tree.h:1105
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1250
const ValueType & background() const
Return this tree's background value.
Definition: Tree.h:555
boost::shared_ptr< TreeBase > Ptr
Definition: Tree.h:67
uint32_t Index32
Definition: Types.h:55
Tree3::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1129
Tree()
Definition: Tree.h:202
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:658
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:1080
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1413
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:1575
const BValueType & b() const
Get the B input value.
Definition: Types.h:292
Helper class for use with Tree::pruneOp() to replace inactive branches with more memory-efficient ina...
Definition: tree/Util.h:74
_RootNodeType RootNodeType
Definition: Tree.h:184
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1058
Tree< RootNode< InternalNode< InternalNode< LeafNode< T, N3 >, N2 >, N1 > > > Type
Definition: Tree.h:1140
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:1176
Definition: Exceptions.h:84
tbb::concurrent_hash_map< ValueAccessorBase< Tree > *, bool > AccessorRegistry
Definition: Tree.h:1104
The root node of an OpenVDB tree.
RootNodeType & root()
Return this tree's root node.
Definition: Tree.h:279
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1032
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1024
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:259
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:1454
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1204
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1065
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:530
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1258
Templated metadata class to hold specific types.
Definition: metadata/Metadata.h:137
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1079
const RootNodeType & root() const
Return this tree's root node.
Definition: Tree.h:280
boost::shared_ptr< Tree > Ptr
Definition: Tree.h:181
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:1462
virtual void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const
Write out all data buffers for this tree.
Definition: Tree.h:1325
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node's table.
Definition: Tree.h:1031
virtual ~Tree()
Definition: Tree.h:261
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:67
virtual void getIndexRange(CoordBBox &bbox) const
Min and max are both inclusive.
Definition: Tree.h:560
virtual ~TreeBase()
Definition: Tree.h:71
virtual Name valueType() const
Return the name of the type of a voxel's value (e.g., "float" or "vec3d")
Definition: Tree.h:267
Definition: Types.h:380
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1168
Tree< typename RootNodeType::template ValueConverter< OtherValueType >::Type > Type
Definition: Tree.h:198
virtual Index32 leafCount() const
Return the number of leaf nodes.
Definition: Tree.h:336
Tree(const OtherTreeType &other, const ValueType &inactiveValue, const ValueType &activeValue, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:231
bool operator!=(const Tree &) const
Definition: Tree.h:275
bool operator==(const Tree &) const
Definition: Tree.h:274
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:1469
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1120
std::string Name
Definition: Name.h:44
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1511
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:130
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1741
TreeValueIteratorBase< const Tree, typename RootNodeType::ValueAllCIter > ValueAllCIter
Definition: Tree.h:1070