OpenVDB  1.1.0
Tree.h
Go to the documentation of this file.
1 
2 //
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;
76  virtual Name valueType() const = 0;
77 
79  virtual TreeBase::Ptr copy() const = 0;
80 
81 
82  //
83  // Tree methods
84  //
87  virtual Metadata::Ptr getBackgroundValue() const { return Metadata::Ptr(); }
88 
92  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const = 0;
96  virtual bool evalLeafDim(Coord& dim) const = 0;
97 
103  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const = 0;
107  virtual bool evalActiveVoxelDim(Coord& dim) const = 0;
108 
109  virtual void getIndexRange(CoordBBox& bbox) const = 0;
110 
111 
112  //
113  // Statistics
114  //
118  virtual Index treeDepth() const = 0;
120  virtual Index32 leafCount() const = 0;
122  virtual Index32 nonLeafCount() const = 0;
124  virtual Index64 activeLeafVoxelCount() const = 0;
126  virtual Index64 inactiveLeafVoxelCount() const = 0;
128  virtual Index64 activeVoxelCount() const = 0;
130  virtual Index64 inactiveVoxelCount() const = 0;
131 
133  virtual Index64 memUsage() const { return 0; }
134 
135 
136  //
137  // I/O methods
138  //
142  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
146  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
147 
149  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false) = 0;
151  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const = 0;
152 
157  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
158 
159 private:
160  // Disallow copying of instances of this class.
161  //TreeBase(const TreeBase& other);
162  TreeBase& operator=(const TreeBase& other);
163 };
164 
165 
167 
168 
169 template<typename _RootNodeType>
170 class Tree: public TreeBase
171 {
172 public:
173  typedef boost::shared_ptr<Tree> Ptr;
174  typedef boost::shared_ptr<const Tree> ConstPtr;
175 
176  typedef _RootNodeType RootNodeType;
177  typedef typename RootNodeType::ValueType ValueType;
178  typedef typename RootNodeType::LeafNodeType LeafNodeType;
179 
180  static const Index DEPTH = RootNodeType::LEVEL + 1;
181 
188  template<typename OtherValueType>
189  struct ValueConverter {
191  };
192 
193 
194  Tree(){}
195 
197  Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
198  {
199  }
200 
210  template<typename OtherTreeType>
211  Tree(const OtherTreeType& other,
212  const ValueType& inactiveValue,
213  const ValueType& activeValue,
214  TopologyCopy):
215  TreeBase(other),
216  mRoot(other.getRootNode(), inactiveValue, activeValue, TopologyCopy())
217  {
218  }
219 
230  template<typename OtherTreeType>
231  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
232  TreeBase(other),
233  mRoot(other.getRootNode(), background, TopologyCopy())
234  {
235  }
236 
238  Tree(const ValueType& background): mRoot(background) {}
239 
240  virtual ~Tree() { releaseAllAccessors(); }
241 
243  virtual TreeBase::Ptr copy() const { return TreeBase::Ptr(new Tree(*this)); }
244 
246  virtual Name valueType() const { return typeNameAsString<ValueType>(); }
247 
249  static const Name& treeType();
251  virtual const Name& type() const { return treeType(); }
252 
253  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
254  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
255 
257 
258  RootNodeType& getRootNode() { return mRoot; }
259  const RootNodeType& getRootNode() const { return mRoot; }
261 
262 
263  //
264  // Tree methods
265  //
268  template<typename OtherRootNodeType>
269  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
270 
271  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const;
272  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
273  virtual bool evalActiveVoxelDim(Coord& dim) const;
274  virtual bool evalLeafDim(Coord& dim) const;
275 
279  static void getNodeLog2Dims(std::vector<Index>& dims);
280 
281 
282  //
283  // I/O methods
284  //
288  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
292  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
294  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false);
296  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const;
297 
298  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
299 
300 
301  //
302  // Statistics
303  //
307  virtual Index treeDepth() const { return DEPTH; }
309  virtual Index32 leafCount() const { return mRoot.leafCount(); }
311  virtual Index32 nonLeafCount() const { return mRoot.nonLeafCount(); }
313  virtual Index64 activeLeafVoxelCount() const { return mRoot.onLeafVoxelCount(); }
315  virtual Index64 inactiveLeafVoxelCount() const { return mRoot.offLeafVoxelCount(); }
317  virtual Index64 activeVoxelCount() const { return mRoot.onVoxelCount(); }
319  virtual Index64 inactiveVoxelCount() const;
320 
322  void evalMinMax(ValueType &min, ValueType &max) const;
323 
324  virtual Index64 memUsage() const { return sizeof(*this) + mRoot.memUsage(); }
325 
326 
327  //
328  // Voxel access methods (using signed indexing)
329  //
331  const ValueType& getValue(const Coord& xyz) const;
334  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
335 
340  int getValueDepth(const Coord& xyz) const;
341 
343  void setValue(const Coord& xyz, const ValueType& value);
345  void setValueOnly(const Coord& xyz, const ValueType& value);
348  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
350  void setValueOn(const Coord& xyz);
352  void setValueOn(const Coord& xyz, const ValueType& value);
355  void setValueOnMin(const Coord& xyz, const ValueType& value);
358  void setValueOnMax(const Coord& xyz, const ValueType& value);
361  void setValueOnSum(const Coord& xyz, const ValueType& value);
362 
364  void setValueOff(const Coord& xyz);
366  void setValueOff(const Coord& xyz, const ValueType& value);
367 
369  void setActiveState(const Coord& xyz, bool on);
370 
373  bool probeValue(const Coord& xyz, ValueType& value) const;
374 
376  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
378  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
380  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
381 
391  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
392 
399  template<typename PruneOp> void pruneOp(PruneOp&);
400 
404  void prune(const ValueType& tolerance = zeroVal<ValueType>());
405 
408  void pruneInactive(const ValueType&);
409 
412  void pruneInactive();
413 
421  void pruneLevelSet();
422 
429  LeafNodeType* touchLeaf(const Coord& xyz);
430 
433  LeafNodeType* probeLeaf(const Coord& xyz);
436  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
437 
438 
439  //
440  // Aux methods
441  //
444  bool empty() const { return mRoot.empty(); }
445 
447  void clear() { this->clearAllAccessors(); mRoot.clear(); }
448 
450  void clearAllAccessors();
451 
453 
454 
455  void attachAccessor(ValueAccessorBase<Tree>&) const;
456  void attachAccessor(ValueAccessorBase<const Tree>&) const;
458 
459 
460  void releaseAccessor(ValueAccessorBase<Tree>&) const;
461  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
463 
466  virtual Metadata::Ptr getBackgroundValue() const;
467 
469  const ValueType& background() const { return mRoot.background(); }
471  OPENVDB_DEPRECATED ValueType getBackground() const { return mRoot.background(); }
473  void setBackground(const ValueType& background) { mRoot.setBackground(background); }
474 
476  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
477 
483  void signedFloodFill() { mRoot.signedFloodFill(); }
484 
491  void signedFloodFill(const ValueType& outside, const ValueType& inside)
492  {
493  mRoot.signedFloodFill(outside, inside);
494  }
495 
501  void merge(Tree& other)
502  {
503  this->clearAllAccessors();
504  other.clearAllAccessors();
505  mRoot.merge(other.mRoot);
506  }
507 
509  void voxelizeActiveTiles()
510  {
511  this->clearAllAccessors();
512  mRoot.voxelizeActiveTiles();
513  }
514 
515 
529  template<typename OtherRootNodeType>
530  void topologyUnion(const Tree<OtherRootNodeType>& other)
531  {
532  this->clearAllAccessors();
533  mRoot.topologyUnion(other.getRootNode());
534  }
535 
581  template<typename CombineOp>
582  void combine(Tree& other, CombineOp& op, bool prune = false);
583 #ifndef _MSC_VER
584  template<typename CombineOp>
585  void combine(Tree& other, const CombineOp& op, bool prune = false);
586 #endif
587 
627  template<typename ExtendedCombineOp>
628  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
629 #ifndef _MSC_VER
630  template<typename ExtendedCombineOp>
631  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
632 #endif
633 
659  template<typename CombineOp>
660  void combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune = false);
661 #ifndef _MSC_VER
662  template<typename CombineOp>
663  void combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune = false);
664 #endif
665 
705  template<typename ExtendedCombineOp>
706  void combine2Extended(const Tree& a, const Tree& b, ExtendedCombineOp& op,
707  bool prune = false);
708 #ifndef _MSC_VER
709  template<typename ExtendedCombineOp>
710  void combine2Extended(const Tree& a, const Tree& b, const ExtendedCombineOp&,
711  bool prune = false);
712 #endif
713 
761  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const
762  {
763  mRoot.visitActiveBBox(op);
764  }
765 
766 
821  template<typename VisitorOp> void visit(VisitorOp& op);
822  template<typename VisitorOp> void visit(const VisitorOp& op);
823 
828  template<typename VisitorOp> void visit(VisitorOp& op) const;
829  template<typename VisitorOp> void visit(const VisitorOp& op) const;
830 
879  template<typename OtherTreeType, typename VisitorOp>
880  void visit2(OtherTreeType& other, VisitorOp& op);
881  template<typename OtherTreeType, typename VisitorOp>
882  void visit2(OtherTreeType& other, const VisitorOp& op);
883 
894  template<typename OtherTreeType, typename VisitorOp>
895  void visit2(OtherTreeType& other, VisitorOp& op) const;
896  template<typename OtherTreeType, typename VisitorOp>
897  void visit2(OtherTreeType& other, const VisitorOp& op) const;
898 
899 
900  //
901  // Iteration
902  //
904 
905  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
906  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
907  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
909 
911 
912  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
913  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
914  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
916 
918 
919  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
920  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
921  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
923 
924 
926 
930 
932 
936 
938 
939  NodeIter beginNode() { return NodeIter(*this); }
940  NodeCIter beginNode() const { return NodeCIter(*this); }
941  NodeCIter cbeginNode() const { return NodeCIter(*this); }
943 
945 
946  LeafIter beginLeaf() { return LeafIter(*this); }
947  LeafCIter beginLeaf() const { return LeafCIter(*this); }
948  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
950 
957 
959 
961  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
962  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
964 
965 
966  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
967  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
968  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
970 
971 
973  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
974  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
976 
979  template<typename IterT> IterT begin();
982  template<typename CIterT> CIterT cbegin() const;
983 
984 
985 protected:
986  typedef tbb::concurrent_hash_map<ValueAccessorBase<Tree>*, bool> AccessorRegistry;
987  typedef tbb::concurrent_hash_map<ValueAccessorBase<const Tree>*, bool> ConstAccessorRegistry;
988 
989  // Disallow assignment of instances of this class.
990  Tree& operator=(const Tree&);
991 
994  void releaseAllAccessors();
995 
996 
997  //
998  // Data members
999  //
1000  RootNodeType mRoot; // root node of the tree
1003 }; // end of Tree class
1004 
1005 
1010 template<typename T, Index N1, Index N2, Index N3>
1011 struct Tree4 {
1013 };
1014 
1015 
1017 
1018 
1019 inline void
1020 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1021 {
1022  int32_t bufferCount;
1023  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1024  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1025 }
1026 
1027 
1028 inline void
1029 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1030 {
1031  int32_t bufferCount = 1;
1032  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1033 }
1034 
1035 
1036 inline void
1037 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1038 {
1039  os << " Tree Type: " << type()
1040  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1041  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1042  << " Leaf Node Count: " << leafCount() << std::endl
1043  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1044 }
1045 
1046 
1048 
1049 
1050 //
1051 // Type traits for tree iterators
1052 //
1053 
1056 template<typename TreeT, typename IterT> struct TreeIterTraits;
1057 
1058 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1059  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1060  return tree.beginRootChildren();
1061  }
1062 };
1063 
1064 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1065  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1066  return tree.cbeginRootChildren();
1067  }
1068 };
1069 
1070 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1071  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1072  return tree.beginRootTiles();
1073  }
1074 };
1075 
1076 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1077  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1078  return tree.cbeginRootTiles();
1079  }
1080 };
1081 
1082 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1083  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1084  return tree.beginRootDense();
1085  }
1086 };
1087 
1088 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1089  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1090  return tree.cbeginRootDense();
1091  }
1092 };
1093 
1094 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1095  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1096 };
1097 
1098 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1099  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1100 };
1101 
1102 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1103  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1104 };
1105 
1106 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1107  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1108 };
1109 
1110 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1111  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1112 };
1113 
1114 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1115  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1116 };
1117 
1118 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1119  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1120 };
1121 
1122 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1123  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1124 };
1125 
1126 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1127  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1128 };
1129 
1130 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1131  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1132 };
1133 
1134 
1135 template<typename RootNodeType>
1136 template<typename IterT>
1137 inline IterT
1139 {
1140  return TreeIterTraits<Tree, IterT>::begin(*this);
1141 }
1142 
1143 
1144 template<typename RootNodeType>
1145 template<typename IterT>
1146 inline IterT
1148 {
1149  return TreeIterTraits<Tree, IterT>::begin(*this);
1150 }
1151 
1152 
1154 
1155 
1156 template<typename RootNodeType>
1157 void
1158 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1159 {
1160  this->clearAllAccessors();
1161  TreeBase::readTopology(is, saveFloatAsHalf);
1162  mRoot.readTopology(is, saveFloatAsHalf);
1163 }
1164 
1165 
1166 template<typename RootNodeType>
1167 void
1168 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1169 {
1170  TreeBase::writeTopology(os, saveFloatAsHalf);
1171  mRoot.writeTopology(os, saveFloatAsHalf);
1172 }
1173 
1174 
1175 template<typename RootNodeType>
1176 inline void
1177 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1178 {
1179  this->clearAllAccessors();
1180  mRoot.readBuffers(is, saveFloatAsHalf);
1181 }
1182 
1183 
1184 template<typename RootNodeType>
1185 inline void
1186 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1187 {
1188  mRoot.writeBuffers(os, saveFloatAsHalf);
1189 }
1190 
1191 
1193 
1194 
1195 template<typename RootNodeType>
1196 inline void
1198 {
1199  typename AccessorRegistry::accessor a;
1200  mAccessorRegistry.insert(a, &accessor);
1201 }
1202 
1203 
1204 template<typename RootNodeType>
1205 inline void
1207 {
1208  typename ConstAccessorRegistry::accessor a;
1209  mConstAccessorRegistry.insert(a, &accessor);
1210 }
1211 
1212 
1213 template<typename RootNodeType>
1214 inline void
1216 {
1217  mAccessorRegistry.erase(&accessor);
1218 }
1219 
1220 
1221 template<typename RootNodeType>
1222 inline void
1224 {
1225  mConstAccessorRegistry.erase(&accessor);
1226 }
1227 
1228 
1229 template<typename RootNodeType>
1230 inline void
1232 {
1233  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1234  it != mAccessorRegistry.end(); ++it)
1235  {
1236  if (it->first) it->first->clear();
1237  }
1238 
1239  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1240  it != mConstAccessorRegistry.end(); ++it)
1241  {
1242  if (it->first) it->first->clear();
1243  }
1244 }
1245 
1246 
1247 template<typename RootNodeType>
1248 inline void
1250 {
1251  mAccessorRegistry.erase(NULL);
1252  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1253  it != mAccessorRegistry.end(); ++it)
1254  {
1255  it->first->release();
1256  }
1257  mAccessorRegistry.clear();
1258 
1259  mAccessorRegistry.erase(NULL);
1260  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1261  it != mConstAccessorRegistry.end(); ++it)
1262  {
1263  it->first->release();
1264  }
1265  mConstAccessorRegistry.clear();
1266 }
1267 
1268 
1270 
1271 
1272 template<typename RootNodeType>
1273 inline const typename RootNodeType::ValueType&
1275 {
1276  return mRoot.getValue(xyz);
1277 }
1278 
1279 
1280 template<typename RootNodeType>
1281 template<typename AccessT>
1282 inline const typename RootNodeType::ValueType&
1283 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1284 {
1285  return accessor.getValue(xyz);
1286 }
1287 
1288 
1289 template<typename RootNodeType>
1290 inline int
1292 {
1293  return mRoot.getValueDepth(xyz);
1294 }
1295 
1296 
1297 template<typename RootNodeType>
1298 inline void
1300 {
1301  mRoot.setValueOff(xyz);
1302 }
1303 
1304 
1305 template<typename RootNodeType>
1306 inline void
1308 {
1309  mRoot.setValueOff(xyz, value);
1310 }
1311 
1312 
1313 template<typename RootNodeType>
1314 inline void
1316 {
1317  mRoot.setActiveState(xyz, on);
1318 }
1319 
1320 
1321 template<typename RootNodeType>
1322 inline void
1324 {
1325  mRoot.setValueOn(xyz, value);
1326 }
1327 
1328 template<typename RootNodeType>
1329 inline void
1331 {
1332  mRoot.setValueOnly(xyz, value);
1333 }
1334 
1335 template<typename RootNodeType>
1336 template<typename AccessT>
1337 inline void
1338 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1339 {
1340  accessor.setValue(xyz, value);
1341 }
1342 
1343 
1344 template<typename RootNodeType>
1345 inline void
1347 {
1348  mRoot.setActiveState(xyz, true);
1349 }
1350 
1351 
1352 template<typename RootNodeType>
1353 inline void
1355 {
1356  mRoot.setValueOn(xyz, value);
1357 }
1358 
1359 
1360 template<typename RootNodeType>
1361 inline void
1363 {
1364  mRoot.setValueOnMin(xyz, value);
1365 }
1366 
1367 
1368 template<typename RootNodeType>
1369 inline void
1371 {
1372  mRoot.setValueOnMax(xyz, value);
1373 }
1374 
1375 
1376 template<typename RootNodeType>
1377 inline void
1379 {
1380  mRoot.setValueOnSum(xyz, value);
1381 }
1382 
1383 
1384 template<typename RootNodeType>
1385 inline bool
1387 {
1388  return mRoot.probeValue(xyz, value);
1389 }
1390 
1391 
1393 
1394 
1395 template<typename RootNodeType>
1396 template<typename PruneOp>
1397 inline void
1399 {
1400  this->clearAllAccessors();
1401  mRoot.pruneOp(op);
1402 }
1403 
1404 
1405 template<typename RootNodeType>
1406 inline void
1408 {
1409  TolerancePrune<ValueType> op(tolerance);
1410  this->pruneOp(op);
1411 }
1412 
1413 
1414 template<typename RootNodeType>
1415 inline void
1417 {
1418  InactivePrune<ValueType> op(bg);
1419  this->pruneOp(op);
1420 }
1421 
1422 
1423 template<typename RootNodeType>
1424 inline void
1426 {
1427  this->pruneInactive(this->background());
1428 }
1429 
1430 template<typename RootNodeType>
1431 inline void
1433 {
1434  LevelSetPrune<ValueType> op(this->background());
1435  this->pruneOp(op);
1436 }
1437 
1438 template<typename RootNodeType>
1439 inline typename RootNodeType::LeafNodeType*
1441 {
1442  return mRoot.touchLeaf(xyz);
1443 }
1444 
1445 template<typename RootNodeType>
1446 inline typename RootNodeType::LeafNodeType*
1448 {
1449  return mRoot.probeLeaf(xyz);
1450 }
1451 
1452 template<typename RootNodeType>
1453 inline const typename RootNodeType::LeafNodeType*
1455 {
1456  return mRoot.probeConstLeaf(xyz);
1457 }
1458 
1460 
1461 
1462 template<typename RootNodeType>
1463 inline void
1464 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1465 {
1466  this->clearAllAccessors();
1467  return mRoot.fill(bbox, value, active);
1468 }
1469 
1470 
1471 template<typename RootNodeType>
1474 {
1475  Metadata::Ptr result;
1476  if (Metadata::isRegisteredType(valueType())) {
1477  typedef TypedMetadata<ValueType> MetadataT;
1478  result = Metadata::createMetadata(valueType());
1479  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1480  m->value() = mRoot.background();
1481  }
1482  }
1483  return result;
1484 }
1485 
1486 
1488 
1489 
1492 template<typename ValueT, typename CombineOp>
1494 {
1495  CombineOpAdapter(CombineOp& op): op(op) {}
1496 
1497  void operator()(CombineArgs<ValueT>& args) const {
1498  op(args.a(), args.b(), args.result());
1499  }
1500 
1501  CombineOp& op;
1502 };
1503 
1504 
1505 template<typename RootNodeType>
1506 template<typename CombineOp>
1507 inline void
1508 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1509 {
1511  this->combineExtended(other, extendedOp, prune);
1512 }
1513 
1514 
1517 #ifndef _MSC_VER
1518 template<typename RootNodeType>
1519 template<typename CombineOp>
1520 inline void
1521 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1522 {
1524  this->combineExtended(other, extendedOp, prune);
1525 }
1526 #endif
1527 
1528 
1529 template<typename RootNodeType>
1530 template<typename ExtendedCombineOp>
1531 inline void
1532 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1533 {
1534  this->clearAllAccessors();
1535  mRoot.combine(other.getRootNode(), op, prune);
1536 }
1537 
1538 
1541 #ifndef _MSC_VER
1542 template<typename RootNodeType>
1543 template<typename ExtendedCombineOp>
1544 inline void
1545 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1546 {
1547  this->clearAllAccessors();
1548  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1549 }
1550 #endif
1551 
1552 
1553 template<typename RootNodeType>
1554 template<typename CombineOp>
1555 inline void
1556 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune)
1557 {
1559  this->combine2Extended(a, b, extendedOp, prune);
1560 }
1561 
1562 
1565 #ifndef _MSC_VER
1566 template<typename RootNodeType>
1567 template<typename CombineOp>
1568 inline void
1569 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune)
1570 {
1572  this->combine2Extended(a, b, extendedOp, prune);
1573 }
1574 #endif
1575 
1576 
1577 template<typename RootNodeType>
1578 template<typename ExtendedCombineOp>
1579 inline void
1581  ExtendedCombineOp& op, bool prune)
1582 {
1583  this->clearAllAccessors();
1584  mRoot.combine2(a.mRoot, b.mRoot, op, prune);
1585 }
1586 
1587 
1590 #ifndef _MSC_VER
1591 template<typename RootNodeType>
1592 template<typename ExtendedCombineOp>
1593 inline void
1595  const ExtendedCombineOp& op, bool prune)
1596 {
1597  this->clearAllAccessors();
1598  mRoot.template combine2<const ExtendedCombineOp>(a.mRoot, b.mRoot, op, prune);
1599 }
1600 #endif
1601 
1602 
1604 
1605 
1606 template<typename RootNodeType>
1607 template<typename VisitorOp>
1608 inline void
1610 {
1611  this->clearAllAccessors();
1612  mRoot.template visit<VisitorOp>(op);
1613 }
1614 
1615 
1616 template<typename RootNodeType>
1617 template<typename VisitorOp>
1618 inline void
1619 Tree<RootNodeType>::visit(VisitorOp& op) const
1620 {
1621  mRoot.template visit<VisitorOp>(op);
1622 }
1623 
1624 
1627 template<typename RootNodeType>
1628 template<typename VisitorOp>
1629 inline void
1630 Tree<RootNodeType>::visit(const VisitorOp& op)
1631 {
1632  this->clearAllAccessors();
1633  mRoot.template visit<const VisitorOp>(op);
1634 }
1635 
1636 
1639 template<typename RootNodeType>
1640 template<typename VisitorOp>
1641 inline void
1642 Tree<RootNodeType>::visit(const VisitorOp& op) const
1643 {
1644  mRoot.template visit<const VisitorOp>(op);
1645 }
1646 
1647 
1649 
1650 
1651 template<typename RootNodeType>
1652 template<typename OtherTreeType, typename VisitorOp>
1653 inline void
1654 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1655 {
1656  this->clearAllAccessors();
1657  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1658  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1659 }
1660 
1661 
1662 template<typename RootNodeType>
1663 template<typename OtherTreeType, typename VisitorOp>
1664 inline void
1665 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1666 {
1667  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1668  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1669 }
1670 
1671 
1674 template<typename RootNodeType>
1675 template<typename OtherTreeType, typename VisitorOp>
1676 inline void
1677 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1678 {
1679  this->clearAllAccessors();
1680  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1681  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1682 }
1683 
1684 
1687 template<typename RootNodeType>
1688 template<typename OtherTreeType, typename VisitorOp>
1689 inline void
1690 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1691 {
1692  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1693  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1694 }
1695 
1696 
1698 
1699 
1700 template<typename RootNodeType>
1701 inline const Name&
1703 {
1704  static tbb::atomic<const Name*> sTypeName;
1705  if (sTypeName == NULL) {
1706  std::vector<Index> dims;
1707  Tree::getNodeLog2Dims(dims);
1708  std::ostringstream ostr;
1709  ostr << "Tree_" << typeNameAsString<ValueType>();
1710  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1711  ostr << "_" << dims[i];
1712  }
1713  Name* s = new Name(ostr.str());
1714  sTypeName.compare_and_swap(s, NULL);
1715  if (sTypeName != s) delete s;
1716  }
1717  return *sTypeName;
1718 }
1719 
1720 
1721 template<typename RootNodeType>
1722 template<typename OtherRootNodeType>
1723 inline bool
1725 {
1726  return mRoot.hasSameTopology(other.getRootNode());
1727 }
1728 
1729 
1730 template<typename RootNodeType>
1731 Index64
1733 {
1734  Coord dim(0, 0, 0);
1735  this->evalActiveVoxelDim(dim);
1736  const Index64
1737  totalVoxels = dim.x() * dim.y() * dim.z(),
1738  activeVoxels = this->activeVoxelCount();
1739  assert(totalVoxels >= activeVoxels);
1740  return totalVoxels - activeVoxels;
1741 }
1742 
1743 
1744 template<typename RootNodeType>
1745 inline bool
1747 {
1748  if (this->empty()) {
1749  bbox = CoordBBox(); // return default bbox
1750  return false;// empty
1751  }
1752 
1753  bbox.min() = Coord::max();
1754  bbox.max() = -Coord::max();
1755 
1756  Coord ijk;
1757  for (LeafCIter bIter(*this); bIter; ++bIter) {
1758  bIter->getOrigin(ijk);
1759  bbox.expand(ijk);
1760  }
1761  bbox.max() += Coord(LeafNodeType::dim()-1);
1762  return true; // not empty
1763 }
1764 
1765 template<typename RootNodeType>
1766 inline bool
1768 {
1769  bbox = CoordBBox(); // default invalid bbox
1770  if (this->empty()) return false; // empty
1771 
1772  mRoot.evalActiveVoxelBoundingBox(bbox);
1773 
1774  return true;// not empty
1775 }
1776 
1777 
1778 template<typename RootNodeType>
1779 inline bool
1781 {
1782  CoordBBox bbox;
1783  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1784  dim = bbox.extents();
1785  return notEmpty;
1786 }
1787 
1788 
1789 template<typename RootNodeType>
1790 inline bool
1792 {
1793  CoordBBox bbox;
1794  bool notEmpty = this->evalLeafBoundingBox(bbox);
1795  dim = bbox.extents();
1796  return notEmpty;
1797 }
1798 
1799 
1800 template<typename RootNodeType>
1801 inline void
1803 {
1804  minVal = maxVal = zeroVal<ValueType>();
1805  if (ValueOnCIter iter = this->cbeginValueOn()) {
1806  minVal = maxVal = *iter;
1807  for (++iter; iter; ++iter) {
1808  const ValueType& val = *iter;
1809  if (val < minVal) minVal = val;
1810  if (val > maxVal) maxVal = val;
1811  }
1812  }
1813 }
1814 
1815 
1816 template<typename RootNodeType>
1817 inline void
1818 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
1819 {
1820  dims.clear();
1821  RootNodeType::getNodeLog2Dims(dims);
1822 }
1823 
1824 
1825 template<typename RootNodeType>
1826 inline void
1827 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
1828 {
1829  if (verboseLevel <= 0) return;
1830 
1831  struct OnExit {
1832  std::ostream& os;
1833  std::streamsize savedPrecision;
1834  OnExit(std::ostream& os): os(os), savedPrecision(os.precision()) {}
1835  ~OnExit() { os.precision(savedPrecision); }
1836  };
1837  OnExit restorePrecision(os);
1838 
1839  std::vector<Index> dims;
1840  Tree::getNodeLog2Dims(dims);
1841 
1842  std::vector<Index64> nodeCount;
1843 
1844  os << "Information about Tree:\n"
1845  << " Type: " << this->type() << "\n";
1846 
1847  os << " Configuration:\n";
1848  if (verboseLevel <= 1) {
1849  // Print node types and sizes.
1850  os << " Root(" << mRoot.getTableSize() << ")";
1851  if (dims.size() > 1) {
1852  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1853  os << ", Internal(" << (1 << dims[i]) << "^3)";
1854  }
1855  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
1856  }
1857  } else {
1858  // Print node types, counts and sizes.
1859  nodeCount.resize(dims.size());
1860  for (NodeCIter it = cbeginNode(); it; ++it) {
1861  ++(nodeCount[it.getDepth()]);
1862  }
1863  os << " Root(1 x " << mRoot.getTableSize() << ")";
1864  if (dims.size() > 1) {
1865  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1866  os << ", Internal(" << util::formattedInt(nodeCount[i]);
1867  os << " x " << (1 << dims[i]) << "^3)";
1868  }
1869  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
1870  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
1871  }
1872  }
1873  os << " Background value: " << mRoot.background() << "\n";
1874 
1875  if (verboseLevel == 1) return;
1876 
1877  // The following is tree information that is expensive to extract.
1878 
1879  if (nodeCount.empty()) {
1880  nodeCount.resize(dims.size());
1881  for (NodeCIter it = cbeginNode(); it; ++it) {
1882  ++(nodeCount[it.getDepth()]);
1883  }
1884  }
1885 
1886  // Statistics of topology and values
1887  ValueType minVal, maxVal;
1888  this->evalMinMax(minVal, maxVal);
1889  os << " Min value: " << minVal << "\n";
1890  os << " Max value: " << maxVal << "\n";
1891 
1892  const uint64_t
1893  leafCount = *nodeCount.rbegin(),
1894  numActiveVoxels = this->activeVoxelCount(),
1895  numActiveLeafVoxels = this->activeLeafVoxelCount();
1896 
1897  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
1898 
1899  Coord dim(0, 0, 0);
1900  uint64_t totalVoxels = 0;
1901  if (numActiveVoxels) { // nonempty
1902  CoordBBox bbox;
1903  this->evalActiveVoxelBoundingBox(bbox);
1904  dim = bbox.extents();
1905  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
1906 
1907  os << " Bounding box of active voxels: " << bbox << "\n";
1908  os << " Dimensions of active voxels: "
1909  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
1910 
1911  const double activeRatio = (100.0 * numActiveVoxels) / totalVoxels;
1912  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
1913 
1914  if (leafCount>0) {
1915  const double fillRatio =
1916  (100.0 * numActiveLeafVoxels) / (leafCount * LeafNodeType::NUM_VOXELS);
1917  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
1918  }
1919  } else {
1920  os << " Tree is empty!\n";
1921  }
1922  os << std::flush;
1923 
1924  if (verboseLevel == 2) return;
1925 
1926  // Memory footprint in bytes
1927  const uint64_t
1928  actualMem = this->memUsage(),
1929  denseMem = sizeof(ValueType) * totalVoxels,
1930  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
1932 
1933  os << "Memory footprint:\n";
1934  util::printBytes(os, actualMem, " Actual footprint: ");
1935  util::printBytes(os, voxelsMem, " Voxel footprint: ");
1936 
1937  if (numActiveVoxels) {
1938  util::printBytes(os, denseMem, " Dense* footprint: ");
1939  os << " Actual footprint is " << (100.0 * actualMem / denseMem)
1940  << "% of dense* footprint\n";
1941  os << " Leaf voxel footprint is " << (100.0 * voxelsMem / actualMem)
1942  << "% of actual footprint\n";
1943  os << " *Dense refers to the smallest equivalent non-sparse volume" << std::endl;
1944  }
1945 }
1946 
1947 } // namespace tree
1948 } // namespace OPENVDB_VERSION_NAME
1949 } // namespace openvdb
1950 
1951 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
1952 
1953 // Copyright (c) 2012-2013 DreamWorks Animation LLC
1954 // All rights reserved. This software is distributed under the
1955 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )