OpenVDB  0.104.0
Tree.h
Go to the documentation of this file.
1 
2 //
3 // Copyright (c) 2012 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 
439  OPENVDB_DEPRECATED bool expand(const Coord& xyz) { return mRoot.expand(xyz); }
440 
441 
442  //
443  // Aux methods
444  //
447  bool empty() const { return mRoot.empty(); }
448 
450  void clear() { this->clearAllAccessors(); mRoot.clear(); }
451 
453  void clearAllAccessors();
454 
456 
457 
458  void attachAccessor(ValueAccessorBase<Tree>&) const;
459  void attachAccessor(ValueAccessorBase<const Tree>&) const;
461 
462 
463  void releaseAccessor(ValueAccessorBase<Tree>&) const;
464  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
466 
469  virtual Metadata::Ptr getBackgroundValue() const;
470 
472  ValueType getBackground() const { return mRoot.getBackground(); }
474  void setBackground(const ValueType& background) { mRoot.setBackground(background); }
475 
476  OPENVDB_DEPRECATED Index getWidth() const { return mRoot.getWidth(); }
477  OPENVDB_DEPRECATED Index getHeight() const { return mRoot.getHeight(); }
478  OPENVDB_DEPRECATED Index getDepth() const { return mRoot.getDepth(); }
479 
481  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
482 
485  void signedFloodFill() { mRoot.signedFloodFill(); }
486 
487 
493  void merge(Tree& other)
494  {
495  this->clearAllAccessors();
496  other.clearAllAccessors();
497  mRoot.merge(other.mRoot);
498  }
499 
501  void voxelizeActiveTiles()
502  {
503  this->clearAllAccessors();
504  mRoot.voxelizeActiveTiles();
505  }
506 
507 
515  template<typename OtherRootNodeType>
516  void topologyUnion(const Tree<OtherRootNodeType>& other)
517  {
518  this->clearAllAccessors();
519  mRoot.topologyUnion(other.getRootNode());
520  }
521 
567  template<typename CombineOp>
568  void combine(Tree& other, CombineOp& op, bool prune = false);
569 #ifndef _MSC_VER
570  template<typename CombineOp>
571  void combine(Tree& other, const CombineOp& op, bool prune = false);
572 #endif
573 
613  template<typename ExtendedCombineOp>
614  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
615 #ifndef _MSC_VER
616  template<typename ExtendedCombineOp>
617  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
618 #endif
619 
645  template<typename CombineOp>
646  void combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune = false);
647 #ifndef _MSC_VER
648  template<typename CombineOp>
649  void combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune = false);
650 #endif
651 
691  template<typename ExtendedCombineOp>
692  void combine2Extended(const Tree& a, const Tree& b, ExtendedCombineOp& op,
693  bool prune = false);
694 #ifndef _MSC_VER
695  template<typename ExtendedCombineOp>
696  void combine2Extended(const Tree& a, const Tree& b, const ExtendedCombineOp&,
697  bool prune = false);
698 #endif
699 
747  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const
748  {
749  mRoot.visitActiveBBox(op);
750  }
751 
752 
807  template<typename VisitorOp> void visit(VisitorOp& op);
808  template<typename VisitorOp> void visit(const VisitorOp& op);
809 
814  template<typename VisitorOp> void visit(VisitorOp& op) const;
815  template<typename VisitorOp> void visit(const VisitorOp& op) const;
816 
865  template<typename OtherTreeType, typename VisitorOp>
866  void visit2(OtherTreeType& other, VisitorOp& op);
867  template<typename OtherTreeType, typename VisitorOp>
868  void visit2(OtherTreeType& other, const VisitorOp& op);
869 
880  template<typename OtherTreeType, typename VisitorOp>
881  void visit2(OtherTreeType& other, VisitorOp& op) const;
882  template<typename OtherTreeType, typename VisitorOp>
883  void visit2(OtherTreeType& other, const VisitorOp& op) const;
884 
885 
886  //
887  // Iteration
888  //
890 
891  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
892  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
893  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
895 
897 
898  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
899  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
900  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
902 
904 
905  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
906  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
907  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
909 
910 
912 
916 
918 
922 
924 
925  NodeIter beginNode() { return NodeIter(*this); }
926  NodeCIter beginNode() const { return NodeCIter(*this); }
927  NodeCIter cbeginNode() const { return NodeCIter(*this); }
929 
931 
932  LeafIter beginLeaf() { return LeafIter(*this); }
933  LeafCIter beginLeaf() const { return LeafCIter(*this); }
934  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
936 
943 
945 
947  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
948  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
950 
951 
952  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
953  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
954  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
956 
957 
959  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
960  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
962 
965  template<typename IterT> IterT begin();
968  template<typename CIterT> CIterT cbegin() const;
969 
970 
971 protected:
972  typedef tbb::concurrent_hash_map<ValueAccessorBase<Tree>*, bool> AccessorRegistry;
973  typedef tbb::concurrent_hash_map<ValueAccessorBase<const Tree>*, bool> ConstAccessorRegistry;
974 
975  // Disallow assignment of instances of this class.
976  Tree& operator=(const Tree&);
977 
980  void releaseAllAccessors();
981 
982 
983  //
984  // Data members
985  //
986  RootNodeType mRoot; // root node of the tree
989 }; // end of Tree class
990 
991 
996 template<typename T, Index N1, Index N2, Index N3>
997 struct Tree4 {
999 };
1000 
1001 
1003 
1004 
1005 inline void
1006 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1007 {
1008  int32_t bufferCount;
1009  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1010  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1011 }
1012 
1013 
1014 inline void
1015 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1016 {
1017  int32_t bufferCount = 1;
1018  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1019 }
1020 
1021 
1022 inline void
1023 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1024 {
1025  os << " Tree Type: " << type()
1026  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1027  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1028  << " Leaf Node Count: " << leafCount() << std::endl
1029  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1030 }
1031 
1032 
1034 
1035 
1036 //
1037 // Type traits for tree iterators
1038 //
1039 
1042 template<typename TreeT, typename IterT> struct TreeIterTraits;
1043 
1044 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1045  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1046  return tree.beginRootChildren();
1047  }
1048 };
1049 
1050 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1051  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1052  return tree.cbeginRootChildren();
1053  }
1054 };
1055 
1056 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1057  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1058  return tree.beginRootTiles();
1059  }
1060 };
1061 
1062 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1063  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1064  return tree.cbeginRootTiles();
1065  }
1066 };
1067 
1068 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1069  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1070  return tree.beginRootDense();
1071  }
1072 };
1073 
1074 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1075  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1076  return tree.cbeginRootDense();
1077  }
1078 };
1079 
1080 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1081  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1082 };
1083 
1084 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1085  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1086 };
1087 
1088 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1089  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1090 };
1091 
1092 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1093  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1094 };
1095 
1096 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1097  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1098 };
1099 
1100 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1101  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1102 };
1103 
1104 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1105  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1106 };
1107 
1108 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1109  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1110 };
1111 
1112 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1113  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1114 };
1115 
1116 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1117  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1118 };
1119 
1120 
1121 template<typename RootNodeType>
1122 template<typename IterT>
1123 inline IterT
1125 {
1126  return TreeIterTraits<Tree, IterT>::begin(*this);
1127 }
1128 
1129 
1130 template<typename RootNodeType>
1131 template<typename IterT>
1132 inline IterT
1134 {
1135  return TreeIterTraits<Tree, IterT>::begin(*this);
1136 }
1137 
1138 
1140 
1141 
1142 template<typename RootNodeType>
1143 void
1144 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1145 {
1146  this->clearAllAccessors();
1147  TreeBase::readTopology(is, saveFloatAsHalf);
1148  mRoot.readTopology(is, saveFloatAsHalf);
1149 }
1150 
1151 
1152 template<typename RootNodeType>
1153 void
1154 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1155 {
1156  TreeBase::writeTopology(os, saveFloatAsHalf);
1157  mRoot.writeTopology(os, saveFloatAsHalf);
1158 }
1159 
1160 
1161 template<typename RootNodeType>
1162 inline void
1163 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1164 {
1165  this->clearAllAccessors();
1166  mRoot.readBuffers(is, saveFloatAsHalf);
1167 }
1168 
1169 
1170 template<typename RootNodeType>
1171 inline void
1172 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1173 {
1174  mRoot.writeBuffers(os, saveFloatAsHalf);
1175 }
1176 
1177 
1179 
1180 
1181 template<typename RootNodeType>
1182 inline void
1184 {
1185  typename AccessorRegistry::accessor a;
1186  mAccessorRegistry.insert(a, &accessor);
1187 }
1188 
1189 
1190 template<typename RootNodeType>
1191 inline void
1193 {
1194  typename ConstAccessorRegistry::accessor a;
1195  mConstAccessorRegistry.insert(a, &accessor);
1196 }
1197 
1198 
1199 template<typename RootNodeType>
1200 inline void
1202 {
1203  mAccessorRegistry.erase(&accessor);
1204 }
1205 
1206 
1207 template<typename RootNodeType>
1208 inline void
1210 {
1211  mConstAccessorRegistry.erase(&accessor);
1212 }
1213 
1214 
1215 template<typename RootNodeType>
1216 inline void
1218 {
1219  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1220  it != mAccessorRegistry.end(); ++it)
1221  {
1222  if (it->first) it->first->clear();
1223  }
1224 
1225  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1226  it != mConstAccessorRegistry.end(); ++it)
1227  {
1228  if (it->first) it->first->clear();
1229  }
1230 }
1231 
1232 
1233 template<typename RootNodeType>
1234 inline void
1236 {
1237  mAccessorRegistry.erase(NULL);
1238  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1239  it != mAccessorRegistry.end(); ++it)
1240  {
1241  it->first->release();
1242  }
1243  mAccessorRegistry.clear();
1244 
1245  mAccessorRegistry.erase(NULL);
1246  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1247  it != mConstAccessorRegistry.end(); ++it)
1248  {
1249  it->first->release();
1250  }
1251  mConstAccessorRegistry.clear();
1252 }
1253 
1254 
1256 
1257 
1258 template<typename RootNodeType>
1259 inline const typename RootNodeType::ValueType&
1261 {
1262  return mRoot.getValue(xyz);
1263 }
1264 
1265 
1266 template<typename RootNodeType>
1267 template<typename AccessT>
1268 inline const typename RootNodeType::ValueType&
1269 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1270 {
1271  return accessor.getValue(xyz);
1272 }
1273 
1274 
1275 template<typename RootNodeType>
1276 inline int
1278 {
1279  return mRoot.getValueDepth(xyz);
1280 }
1281 
1282 
1283 template<typename RootNodeType>
1284 inline void
1286 {
1287  mRoot.setValueOff(xyz);
1288 }
1289 
1290 
1291 template<typename RootNodeType>
1292 inline void
1294 {
1295  mRoot.setValueOff(xyz, value);
1296 }
1297 
1298 
1299 template<typename RootNodeType>
1300 inline void
1302 {
1303  mRoot.setActiveState(xyz, on);
1304 }
1305 
1306 
1307 template<typename RootNodeType>
1308 inline void
1310 {
1311  mRoot.setValueOn(xyz, value);
1312 }
1313 
1314 template<typename RootNodeType>
1315 inline void
1317 {
1318  mRoot.setValueOnly(xyz, value);
1319 }
1320 
1321 template<typename RootNodeType>
1322 template<typename AccessT>
1323 inline void
1324 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1325 {
1326  accessor.setValue(xyz, value);
1327 }
1328 
1329 
1330 template<typename RootNodeType>
1331 inline void
1333 {
1334  mRoot.setActiveState(xyz, true);
1335 }
1336 
1337 
1338 template<typename RootNodeType>
1339 inline void
1341 {
1342  mRoot.setValueOn(xyz, value);
1343 }
1344 
1345 
1346 template<typename RootNodeType>
1347 inline void
1349 {
1350  mRoot.setValueOnMin(xyz, value);
1351 }
1352 
1353 
1354 template<typename RootNodeType>
1355 inline void
1357 {
1358  mRoot.setValueOnMax(xyz, value);
1359 }
1360 
1361 
1362 template<typename RootNodeType>
1363 inline void
1365 {
1366  mRoot.setValueOnSum(xyz, value);
1367 }
1368 
1369 
1370 template<typename RootNodeType>
1371 inline bool
1373 {
1374  return mRoot.probeValue(xyz, value);
1375 }
1376 
1377 
1379 
1380 
1381 template<typename RootNodeType>
1382 template<typename PruneOp>
1383 inline void
1385 {
1386  this->clearAllAccessors();
1387  mRoot.pruneOp(op);
1388 }
1389 
1390 
1391 template<typename RootNodeType>
1392 inline void
1394 {
1395  TolerancePrune<ValueType> op(tolerance);
1396  this->pruneOp(op);
1397 }
1398 
1399 
1400 template<typename RootNodeType>
1401 inline void
1403 {
1404  InactivePrune<ValueType> op(bg);
1405  this->pruneOp(op);
1406 }
1407 
1408 
1409 template<typename RootNodeType>
1410 inline void
1412 {
1413  this->pruneInactive(this->getBackground());
1414 }
1415 
1416 template<typename RootNodeType>
1417 inline void
1419 {
1421  this->pruneOp(op);
1422 }
1423 
1424 template<typename RootNodeType>
1425 inline typename RootNodeType::LeafNodeType*
1427 {
1428  return mRoot.touchLeaf(xyz);
1429 }
1430 
1431 template<typename RootNodeType>
1432 inline typename RootNodeType::LeafNodeType*
1434 {
1435  return mRoot.probeLeaf(xyz);
1436 }
1437 
1438 template<typename RootNodeType>
1439 inline const typename RootNodeType::LeafNodeType*
1441 {
1442  return mRoot.probeConstLeaf(xyz);
1443 }
1444 
1446 
1447 
1448 template<typename RootNodeType>
1449 inline void
1450 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1451 {
1452  this->clearAllAccessors();
1453  return mRoot.fill(bbox, value, active);
1454 }
1455 
1456 
1457 template<typename RootNodeType>
1460 {
1461  Metadata::Ptr result;
1462  if (Metadata::isRegisteredType(valueType())) {
1463  typedef TypedMetadata<ValueType> MetadataT;
1464  result = Metadata::createMetadata(valueType());
1465  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1466  m->value() = mRoot.getBackground();
1467  }
1468  }
1469  return result;
1470 }
1471 
1472 
1474 
1475 
1478 template<typename ValueT, typename CombineOp>
1480 {
1481  CombineOpAdapter(CombineOp& op): op(op) {}
1482 
1483  void operator()(CombineArgs<ValueT>& args) const {
1484  op(args.a(), args.b(), args.result());
1485  }
1486 
1487  CombineOp& op;
1488 };
1489 
1490 
1491 template<typename RootNodeType>
1492 template<typename CombineOp>
1493 inline void
1494 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1495 {
1497  this->combineExtended(other, extendedOp, prune);
1498 }
1499 
1500 
1503 #ifndef _MSC_VER
1504 template<typename RootNodeType>
1505 template<typename CombineOp>
1506 inline void
1507 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1508 {
1510  this->combineExtended(other, extendedOp, prune);
1511 }
1512 #endif
1513 
1514 
1515 template<typename RootNodeType>
1516 template<typename ExtendedCombineOp>
1517 inline void
1518 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1519 {
1520  this->clearAllAccessors();
1521  mRoot.combine(other.getRootNode(), op, prune);
1522 }
1523 
1524 
1527 #ifndef _MSC_VER
1528 template<typename RootNodeType>
1529 template<typename ExtendedCombineOp>
1530 inline void
1531 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1532 {
1533  this->clearAllAccessors();
1534  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1535 }
1536 #endif
1537 
1538 
1539 template<typename RootNodeType>
1540 template<typename CombineOp>
1541 inline void
1542 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune)
1543 {
1545  this->combine2Extended(a, b, extendedOp, prune);
1546 }
1547 
1548 
1551 #ifndef _MSC_VER
1552 template<typename RootNodeType>
1553 template<typename CombineOp>
1554 inline void
1555 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune)
1556 {
1558  this->combine2Extended(a, b, extendedOp, prune);
1559 }
1560 #endif
1561 
1562 
1563 template<typename RootNodeType>
1564 template<typename ExtendedCombineOp>
1565 inline void
1567  ExtendedCombineOp& op, bool prune)
1568 {
1569  this->clearAllAccessors();
1570  mRoot.combine2(a.mRoot, b.mRoot, op, prune);
1571 }
1572 
1573 
1576 #ifndef _MSC_VER
1577 template<typename RootNodeType>
1578 template<typename ExtendedCombineOp>
1579 inline void
1581  const ExtendedCombineOp& op, bool prune)
1582 {
1583  this->clearAllAccessors();
1584  mRoot.template combine2<const ExtendedCombineOp>(a.mRoot, b.mRoot, op, prune);
1585 }
1586 #endif
1587 
1588 
1590 
1591 
1592 template<typename RootNodeType>
1593 template<typename VisitorOp>
1594 inline void
1596 {
1597  this->clearAllAccessors();
1598  mRoot.template visit<VisitorOp>(op);
1599 }
1600 
1601 
1602 template<typename RootNodeType>
1603 template<typename VisitorOp>
1604 inline void
1605 Tree<RootNodeType>::visit(VisitorOp& op) const
1606 {
1607  mRoot.template visit<VisitorOp>(op);
1608 }
1609 
1610 
1613 template<typename RootNodeType>
1614 template<typename VisitorOp>
1615 inline void
1616 Tree<RootNodeType>::visit(const VisitorOp& op)
1617 {
1618  this->clearAllAccessors();
1619  mRoot.template visit<const VisitorOp>(op);
1620 }
1621 
1622 
1625 template<typename RootNodeType>
1626 template<typename VisitorOp>
1627 inline void
1628 Tree<RootNodeType>::visit(const VisitorOp& op) const
1629 {
1630  mRoot.template visit<const VisitorOp>(op);
1631 }
1632 
1633 
1635 
1636 
1637 template<typename RootNodeType>
1638 template<typename OtherTreeType, typename VisitorOp>
1639 inline void
1640 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1641 {
1642  this->clearAllAccessors();
1643  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1644  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1645 }
1646 
1647 
1648 template<typename RootNodeType>
1649 template<typename OtherTreeType, typename VisitorOp>
1650 inline void
1651 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1652 {
1653  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1654  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1655 }
1656 
1657 
1660 template<typename RootNodeType>
1661 template<typename OtherTreeType, typename VisitorOp>
1662 inline void
1663 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1664 {
1665  this->clearAllAccessors();
1666  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1667  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1668 }
1669 
1670 
1673 template<typename RootNodeType>
1674 template<typename OtherTreeType, typename VisitorOp>
1675 inline void
1676 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1677 {
1678  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1679  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1680 }
1681 
1682 
1684 
1685 
1686 template<typename RootNodeType>
1687 inline const Name&
1689 {
1690  static tbb::atomic<const Name*> sTypeName;
1691  if (sTypeName == NULL) {
1692  std::vector<Index> dims;
1693  Tree::getNodeLog2Dims(dims);
1694  std::ostringstream ostr;
1695  ostr << "Tree_" << typeNameAsString<ValueType>();
1696  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1697  ostr << "_" << dims[i];
1698  }
1699  Name* s = new Name(ostr.str());
1700  sTypeName.compare_and_swap(s, NULL);
1701  if (sTypeName != s) delete s;
1702  }
1703  return *sTypeName;
1704 }
1705 
1706 
1707 template<typename RootNodeType>
1708 template<typename OtherRootNodeType>
1709 inline bool
1711 {
1712  return mRoot.hasSameTopology(other.getRootNode());
1713 }
1714 
1715 
1716 template<typename RootNodeType>
1717 Index64
1719 {
1720  Coord dim(0, 0, 0);
1721  this->evalActiveVoxelDim(dim);
1722  const Index64
1723  totalVoxels = dim.x() * dim.y() * dim.z(),
1724  activeVoxels = this->activeVoxelCount();
1725  assert(totalVoxels >= activeVoxels);
1726  return totalVoxels - activeVoxels;
1727 }
1728 
1729 
1730 template<typename RootNodeType>
1731 inline bool
1733 {
1734  if (this->empty()) {
1735  bbox = CoordBBox(); // return default bbox
1736  return false;// empty
1737  }
1738 
1739  bbox.min() = Coord::max();
1740  bbox.max() = -Coord::max();
1741 
1742  Coord ijk;
1743  for (LeafCIter bIter(*this); bIter; ++bIter) {
1744  bIter->getOrigin(ijk);
1745  bbox.expand(ijk);
1746  }
1747  bbox.max() += Coord(LeafNodeType::dim()-1);
1748  return true; // not empty
1749 }
1750 
1751 template<typename RootNodeType>
1752 inline bool
1754 {
1755  bbox = CoordBBox(); // default invalid bbox
1756  if (this->empty()) return false; // empty
1757 
1758  mRoot.evalActiveVoxelBoundingBox(bbox);
1759 
1760  return true;// not empty
1761 }
1762 
1763 
1764 template<typename RootNodeType>
1765 inline bool
1767 {
1768  CoordBBox bbox;
1769  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1770  dim = bbox.extents();
1771  return notEmpty;
1772 }
1773 
1774 
1775 template<typename RootNodeType>
1776 inline bool
1778 {
1779  CoordBBox bbox;
1780  bool notEmpty = this->evalLeafBoundingBox(bbox);
1781  dim = bbox.extents();
1782  return notEmpty;
1783 }
1784 
1785 
1786 template<typename RootNodeType>
1787 inline void
1789 {
1790  minVal = maxVal = zeroVal<ValueType>();
1791  if (ValueOnCIter iter = this->cbeginValueOn()) {
1792  minVal = maxVal = *iter;
1793  for (++iter; iter; ++iter) {
1794  const ValueType& val = *iter;
1795  if (val < minVal) minVal = val;
1796  if (val > maxVal) maxVal = val;
1797  }
1798  }
1799 }
1800 
1801 
1802 template<typename RootNodeType>
1803 inline void
1804 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
1805 {
1806  dims.clear();
1807  RootNodeType::getNodeLog2Dims(dims);
1808 }
1809 
1810 
1811 template<typename RootNodeType>
1812 inline void
1813 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
1814 {
1815  if (verboseLevel <= 0) return;
1816 
1817  struct OnExit {
1818  std::ostream& os;
1819  std::streamsize savedPrecision;
1820  OnExit(std::ostream& os): os(os), savedPrecision(os.precision()) {}
1821  ~OnExit() { os.precision(savedPrecision); }
1822  };
1823  OnExit restorePrecision(os);
1824 
1825  std::vector<Index> dims;
1826  Tree::getNodeLog2Dims(dims);
1827 
1828  std::vector<Index64> nodeCount;
1829 
1830  os << "Information about Tree:\n"
1831  << " Type: " << this->type() << "\n";
1832 
1833  os << " Configuration:\n";
1834  if (verboseLevel <= 1) {
1835  // Print node types and sizes.
1836  os << " Root(" << mRoot.getTableSize() << ")";
1837  if (dims.size() > 1) {
1838  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1839  os << ", Internal(" << (1 << dims[i]) << "^3)";
1840  }
1841  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
1842  }
1843  } else {
1844  // Print node types, counts and sizes.
1845  nodeCount.resize(dims.size());
1846  for (NodeCIter it = cbeginNode(); it; ++it) {
1847  ++(nodeCount[it.getDepth()]);
1848  }
1849  os << " Root(1 x " << mRoot.getTableSize() << ")";
1850  if (dims.size() > 1) {
1851  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1852  os << ", Internal(" << util::formattedInt(nodeCount[i]);
1853  os << " x " << (1 << dims[i]) << "^3)";
1854  }
1855  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
1856  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
1857  }
1858  }
1859  os << " Background value: " << mRoot.getBackground() << "\n";
1860 
1861  if (verboseLevel == 1) return;
1862 
1863  // The following is tree information that is expensive to extract.
1864 
1865  if (nodeCount.empty()) {
1866  nodeCount.resize(dims.size());
1867  for (NodeCIter it = cbeginNode(); it; ++it) {
1868  ++(nodeCount[it.getDepth()]);
1869  }
1870  }
1871 
1872  // Statistics of topology and values
1873  ValueType minVal, maxVal;
1874  this->evalMinMax(minVal, maxVal);
1875  os << " Min value: " << minVal << "\n";
1876  os << " Max value: " << maxVal << "\n";
1877 
1878  const uint64_t
1879  leafCount = *nodeCount.rbegin(),
1880  numActiveVoxels = this->activeVoxelCount(),
1881  numActiveLeafVoxels = this->activeLeafVoxelCount();
1882 
1883  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
1884 
1885  Coord dim(0, 0, 0);
1886  uint64_t totalVoxels = 0;
1887  if (numActiveVoxels) { // nonempty
1888  CoordBBox bbox;
1889  this->evalActiveVoxelBoundingBox(bbox);
1890  dim = bbox.extents();
1891  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
1892 
1893  os << " Bounding box of active voxels: " << bbox << "\n";
1894  os << " Dimensions of active voxels: "
1895  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
1896 
1897  const double activeRatio = (100.0 * numActiveVoxels) / totalVoxels;
1898  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
1899 
1900  if (leafCount>0) {
1901  const double fillRatio =
1902  (100.0 * numActiveLeafVoxels) / (leafCount * LeafNodeType::NUM_VOXELS);
1903  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
1904  }
1905  } else {
1906  os << " Tree is empty!\n";
1907  }
1908  os << std::flush;
1909 
1910  if (verboseLevel == 2) return;
1911 
1912  // Memory footprint in bytes
1913  const uint64_t
1914  actualMem = this->memUsage(),
1915  denseMem = sizeof(ValueType) * totalVoxels,
1916  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
1918 
1919  os << "Memory footprint:\n";
1920  util::printBytes(os, actualMem, " Actual footprint: ");
1921  util::printBytes(os, voxelsMem, " Voxel footprint: ");
1922 
1923  if (numActiveVoxels) {
1924  util::printBytes(os, denseMem, " Dense* footprint: ");
1925  os << " Actual footprint is " << (100.0 * actualMem / denseMem)
1926  << "% of dense* footprint\n";
1927  os << " Leaf voxel footprint is " << (100.0 * voxelsMem / actualMem)
1928  << "% of actual footprint\n";
1929  os << " *Dense refers to the smallest equivalent non-sparse volume" << std::endl;
1930  }
1931 }
1932 
1933 } // namespace tree
1934 } // namespace OPENVDB_VERSION_NAME
1935 } // namespace openvdb
1936 
1937 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
1938 
1939 // Copyright (c) 2012 DreamWorks Animation LLC
1940 // All rights reserved. This software is distributed under the
1941 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )