OpenVDB  1.2.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;
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  RootNodeType& root() { return mRoot; }
259  const RootNodeType& root() const { return mRoot; }
260  // Deprecate the methods below
261  RootNodeType& getRootNode() { return mRoot; }
262  const RootNodeType& getRootNode() const { return mRoot; }
264 
265 
266  //
267  // Tree methods
268  //
271  template<typename OtherRootNodeType>
272  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
273 
274  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const;
275  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const;
276  virtual bool evalActiveVoxelDim(Coord& dim) const;
277  virtual bool evalLeafDim(Coord& dim) const;
278 
282  static void getNodeLog2Dims(std::vector<Index>& dims);
283 
284 
285  //
286  // I/O methods
287  //
291  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
295  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
297  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false);
299  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const;
300 
301  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
302 
303 
304  //
305  // Statistics
306  //
310  virtual Index treeDepth() const { return DEPTH; }
312  virtual Index32 leafCount() const { return mRoot.leafCount(); }
314  virtual Index32 nonLeafCount() const { return mRoot.nonLeafCount(); }
316  virtual Index64 activeLeafVoxelCount() const { return mRoot.onLeafVoxelCount(); }
318  virtual Index64 inactiveLeafVoxelCount() const { return mRoot.offLeafVoxelCount(); }
320  virtual Index64 activeVoxelCount() const { return mRoot.onVoxelCount(); }
322  virtual Index64 inactiveVoxelCount() const;
323 
325  void evalMinMax(ValueType &min, ValueType &max) const;
326 
327  virtual Index64 memUsage() const { return sizeof(*this) + mRoot.memUsage(); }
328 
329 
330  //
331  // Voxel access methods (using signed indexing)
332  //
334  const ValueType& getValue(const Coord& xyz) const;
337  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
338 
343  int getValueDepth(const Coord& xyz) const;
344 
346  void setValue(const Coord& xyz, const ValueType& value);
348  void setValueOnly(const Coord& xyz, const ValueType& value);
351  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
353  void setValueOn(const Coord& xyz);
355  void setValueOn(const Coord& xyz, const ValueType& value);
358  void setValueOnMin(const Coord& xyz, const ValueType& value);
361  void setValueOnMax(const Coord& xyz, const ValueType& value);
364  void setValueOnSum(const Coord& xyz, const ValueType& value);
365 
367  void setValueOff(const Coord& xyz);
369  void setValueOff(const Coord& xyz, const ValueType& value);
370 
372  void setActiveState(const Coord& xyz, bool on);
373 
376  bool probeValue(const Coord& xyz, ValueType& value) const;
377 
379  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
381  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
383  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
384 
394  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true);
395 
402  template<typename PruneOp> void pruneOp(PruneOp&);
403 
407  void prune(const ValueType& tolerance = zeroVal<ValueType>());
408 
411  void pruneInactive(const ValueType&);
412 
415  void pruneInactive();
416 
424  void pruneLevelSet();
425 
428  void addLeaf(LeafNodeType& leaf) { mRoot.addLeaf(&leaf); }
429 
435  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
436 
441  template<typename NodeT>
442  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
443 
450  LeafNodeType* touchLeaf(const Coord& xyz);
451 
454  LeafNodeType* probeLeaf(const Coord& xyz);
455 
458  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
459  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
460 
461  //
462  // Aux methods
463  //
466  bool empty() const { return mRoot.empty(); }
467 
469  void clear() { this->clearAllAccessors(); mRoot.clear(); }
470 
472  void clearAllAccessors();
473 
475  void attachAccessor(ValueAccessorBase<Tree>&) const;
478  void attachAccessor(ValueAccessorBase<const Tree>&) const;
480 
481  void releaseAccessor(ValueAccessorBase<Tree>&) const;
483  void releaseAccessor(ValueAccessorBase<const Tree>&) const;
485 
488  virtual Metadata::Ptr getBackgroundValue() const;
489 
491  const ValueType& background() const { return mRoot.background(); }
493  OPENVDB_DEPRECATED ValueType getBackground() const { return mRoot.background(); }
495  void setBackground(const ValueType& background) { mRoot.setBackground(background); }
496 
498  virtual void getIndexRange(CoordBBox& bbox) const { mRoot.getIndexRange(bbox); }
499 
505  void signedFloodFill() { mRoot.signedFloodFill(); }
506 
513  void signedFloodFill(const ValueType& outside, const ValueType& inside);
514 
520  void merge(Tree& other);
521 
523  void voxelizeActiveTiles();
524 
538  template<typename OtherRootNodeType>
539  void topologyUnion(const Tree<OtherRootNodeType>& other);
540 
586  template<typename CombineOp>
587  void combine(Tree& other, CombineOp& op, bool prune = false);
588 #ifndef _MSC_VER
589  template<typename CombineOp>
590  void combine(Tree& other, const CombineOp& op, bool prune = false);
591 #endif
592 
632  template<typename ExtendedCombineOp>
633  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
634 #ifndef _MSC_VER
635  template<typename ExtendedCombineOp>
636  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
637 #endif
638 
664  template<typename CombineOp>
665  void combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune = false);
666 #ifndef _MSC_VER
667  template<typename CombineOp>
668  void combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune = false);
669 #endif
670 
710  template<typename ExtendedCombineOp>
711  void combine2Extended(const Tree& a, const Tree& b, ExtendedCombineOp& op,
712  bool prune = false);
713 #ifndef _MSC_VER
714  template<typename ExtendedCombineOp>
715  void combine2Extended(const Tree& a, const Tree& b, const ExtendedCombineOp&,
716  bool prune = false);
717 #endif
718 
765  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
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  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  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  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 
930 
936 
938  NodeIter beginNode() { return NodeIter(*this); }
940  NodeCIter beginNode() const { return NodeCIter(*this); }
941  NodeCIter cbeginNode() const { return NodeCIter(*this); }
943 
945  LeafIter beginLeaf() { return LeafIter(*this); }
947  LeafCIter beginLeaf() const { return LeafCIter(*this); }
948  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
950 
957 
959  ValueAllIter beginValueAll() { return ValueAllIter(*this); }
961  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
962  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
964 
965  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
967  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
968  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
970 
971  ValueOffIter beginValueOff() { return ValueOffIter(*this); }
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 
1431 template<typename RootNodeType>
1432 inline void
1434 {
1435  LevelSetPrune<ValueType> op(this->background());
1436  this->pruneOp(op);
1437 }
1438 
1439 
1440 template<typename RootNodeType>
1441 inline void
1443  const ValueType& value, bool active)
1444 {
1445  mRoot.addTile(level, xyz, value, active);
1446 }
1447 
1448 template<typename RootNodeType>
1449 template<typename NodeT>
1450 inline NodeT*
1451 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1452 {
1453  this->clearAllAccessors();
1454  return mRoot.template stealNode<NodeT>(xyz, value, active);
1455 }
1456 
1457 template<typename RootNodeType>
1458 inline typename RootNodeType::LeafNodeType*
1460 {
1461  return mRoot.touchLeaf(xyz);
1462 }
1463 
1464 
1465 template<typename RootNodeType>
1466 inline typename RootNodeType::LeafNodeType*
1468 {
1469  return mRoot.probeLeaf(xyz);
1470 }
1471 
1472 
1473 template<typename RootNodeType>
1474 inline const typename RootNodeType::LeafNodeType*
1476 {
1477  return mRoot.probeConstLeaf(xyz);
1478 }
1479 
1480 
1482 
1483 
1484 template<typename RootNodeType>
1485 inline void
1486 Tree<RootNodeType>::fill(const CoordBBox& bbox, const ValueType& value, bool active)
1487 {
1488  this->clearAllAccessors();
1489  return mRoot.fill(bbox, value, active);
1490 }
1491 
1492 
1493 template<typename RootNodeType>
1494 inline void
1496 {
1497  mRoot.signedFloodFill(outside, inside);
1498 }
1499 
1500 
1501 template<typename RootNodeType>
1504 {
1505  Metadata::Ptr result;
1506  if (Metadata::isRegisteredType(valueType())) {
1507  typedef TypedMetadata<ValueType> MetadataT;
1508  result = Metadata::createMetadata(valueType());
1509  if (MetadataT* m = dynamic_cast<MetadataT*>(result.get())) {
1510  m->value() = mRoot.background();
1511  }
1512  }
1513  return result;
1514 }
1515 
1516 
1518 
1519 
1520 template<typename RootNodeType>
1521 inline void
1523 {
1524  this->clearAllAccessors();
1525  other.clearAllAccessors();
1526  mRoot.merge(other.mRoot);
1527 }
1528 
1529 
1530 template<typename RootNodeType>
1531 inline void
1533 {
1534  this->clearAllAccessors();
1535  mRoot.voxelizeActiveTiles();
1536 }
1537 
1538 
1539 template<typename RootNodeType>
1540 template<typename OtherRootNodeType>
1541 inline void
1543 {
1544  this->clearAllAccessors();
1545  mRoot.topologyUnion(other.getRootNode());
1546 }
1547 
1548 
1550 
1551 
1554 template<typename ValueT, typename CombineOp>
1556 {
1557  CombineOpAdapter(CombineOp& op): op(op) {}
1558 
1559  void operator()(CombineArgs<ValueT>& args) const {
1560  op(args.a(), args.b(), args.result());
1561  }
1562 
1563  CombineOp& op;
1564 };
1565 
1566 
1567 template<typename RootNodeType>
1568 template<typename CombineOp>
1569 inline void
1570 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1571 {
1573  this->combineExtended(other, extendedOp, prune);
1574 }
1575 
1576 
1579 #ifndef _MSC_VER
1580 template<typename RootNodeType>
1581 template<typename CombineOp>
1582 inline void
1583 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1584 {
1586  this->combineExtended(other, extendedOp, prune);
1587 }
1588 #endif
1589 
1590 
1591 template<typename RootNodeType>
1592 template<typename ExtendedCombineOp>
1593 inline void
1594 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1595 {
1596  this->clearAllAccessors();
1597  mRoot.combine(other.getRootNode(), op, prune);
1598 }
1599 
1600 
1603 #ifndef _MSC_VER
1604 template<typename RootNodeType>
1605 template<typename ExtendedCombineOp>
1606 inline void
1607 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1608 {
1609  this->clearAllAccessors();
1610  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1611 }
1612 #endif
1613 
1614 
1615 template<typename RootNodeType>
1616 template<typename CombineOp>
1617 inline void
1618 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, CombineOp& op, bool prune)
1619 {
1621  this->combine2Extended(a, b, extendedOp, prune);
1622 }
1623 
1624 
1627 #ifndef _MSC_VER
1628 template<typename RootNodeType>
1629 template<typename CombineOp>
1630 inline void
1631 Tree<RootNodeType>::combine2(const Tree& a, const Tree& b, const CombineOp& op, bool prune)
1632 {
1634  this->combine2Extended(a, b, extendedOp, prune);
1635 }
1636 #endif
1637 
1638 
1639 template<typename RootNodeType>
1640 template<typename ExtendedCombineOp>
1641 inline void
1643  ExtendedCombineOp& op, bool prune)
1644 {
1645  this->clearAllAccessors();
1646  mRoot.combine2(a.mRoot, b.mRoot, op, prune);
1647 }
1648 
1649 
1652 #ifndef _MSC_VER
1653 template<typename RootNodeType>
1654 template<typename ExtendedCombineOp>
1655 inline void
1657  const ExtendedCombineOp& op, bool prune)
1658 {
1659  this->clearAllAccessors();
1660  mRoot.template combine2<const ExtendedCombineOp>(a.mRoot, b.mRoot, op, prune);
1661 }
1662 #endif
1663 
1664 
1666 
1667 
1668 template<typename RootNodeType>
1669 template<typename VisitorOp>
1670 inline void
1672 {
1673  this->clearAllAccessors();
1674  mRoot.template visit<VisitorOp>(op);
1675 }
1676 
1677 
1678 template<typename RootNodeType>
1679 template<typename VisitorOp>
1680 inline void
1681 Tree<RootNodeType>::visit(VisitorOp& op) const
1682 {
1683  mRoot.template visit<VisitorOp>(op);
1684 }
1685 
1686 
1689 template<typename RootNodeType>
1690 template<typename VisitorOp>
1691 inline void
1692 Tree<RootNodeType>::visit(const VisitorOp& op)
1693 {
1694  this->clearAllAccessors();
1695  mRoot.template visit<const VisitorOp>(op);
1696 }
1697 
1698 
1701 template<typename RootNodeType>
1702 template<typename VisitorOp>
1703 inline void
1704 Tree<RootNodeType>::visit(const VisitorOp& op) const
1705 {
1706  mRoot.template visit<const VisitorOp>(op);
1707 }
1708 
1709 
1711 
1712 
1713 template<typename RootNodeType>
1714 template<typename OtherTreeType, typename VisitorOp>
1715 inline void
1716 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
1717 {
1718  this->clearAllAccessors();
1719  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1720  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1721 }
1722 
1723 
1724 template<typename RootNodeType>
1725 template<typename OtherTreeType, typename VisitorOp>
1726 inline void
1727 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
1728 {
1729  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1730  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.getRootNode(), op);
1731 }
1732 
1733 
1736 template<typename RootNodeType>
1737 template<typename OtherTreeType, typename VisitorOp>
1738 inline void
1739 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
1740 {
1741  this->clearAllAccessors();
1742  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1743  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1744 }
1745 
1746 
1749 template<typename RootNodeType>
1750 template<typename OtherTreeType, typename VisitorOp>
1751 inline void
1752 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
1753 {
1754  typedef typename OtherTreeType::RootNodeType OtherRootNodeType;
1755  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.getRootNode(), op);
1756 }
1757 
1758 
1760 
1761 
1762 template<typename RootNodeType>
1763 inline const Name&
1765 {
1766  static tbb::atomic<const Name*> sTypeName;
1767  if (sTypeName == NULL) {
1768  std::vector<Index> dims;
1769  Tree::getNodeLog2Dims(dims);
1770  std::ostringstream ostr;
1771  ostr << "Tree_" << typeNameAsString<ValueType>();
1772  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
1773  ostr << "_" << dims[i];
1774  }
1775  Name* s = new Name(ostr.str());
1776  sTypeName.compare_and_swap(s, NULL);
1777  if (sTypeName != s) delete s;
1778  }
1779  return *sTypeName;
1780 }
1781 
1782 
1783 template<typename RootNodeType>
1784 template<typename OtherRootNodeType>
1785 inline bool
1787 {
1788  return mRoot.hasSameTopology(other.getRootNode());
1789 }
1790 
1791 
1792 template<typename RootNodeType>
1793 Index64
1795 {
1796  Coord dim(0, 0, 0);
1797  this->evalActiveVoxelDim(dim);
1798  const Index64
1799  totalVoxels = dim.x() * dim.y() * dim.z(),
1800  activeVoxels = this->activeVoxelCount();
1801  assert(totalVoxels >= activeVoxels);
1802  return totalVoxels - activeVoxels;
1803 }
1804 
1805 
1806 template<typename RootNodeType>
1807 inline bool
1809 {
1810  if (this->empty()) {
1811  bbox = CoordBBox(); // return default bbox
1812  return false;// empty
1813  }
1814 
1815  bbox.min() = Coord::max();
1816  bbox.max() = -Coord::max();
1817 
1818  Coord ijk;
1819  for (LeafCIter bIter(*this); bIter; ++bIter) {
1820  bIter->getOrigin(ijk);
1821  bbox.expand(ijk);
1822  }
1823  bbox.max() += Coord(LeafNodeType::dim()-1);
1824  return true; // not empty
1825 }
1826 
1827 template<typename RootNodeType>
1828 inline bool
1830 {
1831  bbox = CoordBBox(); // default invalid bbox
1832  if (this->empty()) return false; // empty
1833 
1834  mRoot.evalActiveVoxelBoundingBox(bbox);
1835 
1836  return true;// not empty
1837 }
1838 
1839 
1840 template<typename RootNodeType>
1841 inline bool
1843 {
1844  CoordBBox bbox;
1845  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
1846  dim = bbox.extents();
1847  return notEmpty;
1848 }
1849 
1850 
1851 template<typename RootNodeType>
1852 inline bool
1854 {
1855  CoordBBox bbox;
1856  bool notEmpty = this->evalLeafBoundingBox(bbox);
1857  dim = bbox.extents();
1858  return notEmpty;
1859 }
1860 
1861 
1862 template<typename RootNodeType>
1863 inline void
1865 {
1866  minVal = maxVal = zeroVal<ValueType>();
1867  if (ValueOnCIter iter = this->cbeginValueOn()) {
1868  minVal = maxVal = *iter;
1869  for (++iter; iter; ++iter) {
1870  const ValueType& val = *iter;
1871  if (val < minVal) minVal = val;
1872  if (val > maxVal) maxVal = val;
1873  }
1874  }
1875 }
1876 
1877 
1878 template<typename RootNodeType>
1879 inline void
1880 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
1881 {
1882  dims.clear();
1883  RootNodeType::getNodeLog2Dims(dims);
1884 }
1885 
1886 
1887 template<typename RootNodeType>
1888 inline void
1889 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
1890 {
1891  if (verboseLevel <= 0) return;
1892 
1893  struct OnExit {
1894  std::ostream& os;
1895  std::streamsize savedPrecision;
1896  OnExit(std::ostream& os): os(os), savedPrecision(os.precision()) {}
1897  ~OnExit() { os.precision(savedPrecision); }
1898  };
1899  OnExit restorePrecision(os);
1900 
1901  std::vector<Index> dims;
1902  Tree::getNodeLog2Dims(dims);
1903 
1904  std::vector<Index64> nodeCount;
1905 
1906  os << "Information about Tree:\n"
1907  << " Type: " << this->type() << "\n";
1908 
1909  os << " Configuration:\n";
1910  if (verboseLevel <= 1) {
1911  // Print node types and sizes.
1912  os << " Root(" << mRoot.getTableSize() << ")";
1913  if (dims.size() > 1) {
1914  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1915  os << ", Internal(" << (1 << dims[i]) << "^3)";
1916  }
1917  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
1918  }
1919  } else {
1920  // Print node types, counts and sizes.
1921  nodeCount.resize(dims.size());
1922  for (NodeCIter it = cbeginNode(); it; ++it) {
1923  ++(nodeCount[it.getDepth()]);
1924  }
1925  os << " Root(1 x " << mRoot.getTableSize() << ")";
1926  if (dims.size() > 1) {
1927  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
1928  os << ", Internal(" << util::formattedInt(nodeCount[i]);
1929  os << " x " << (1 << dims[i]) << "^3)";
1930  }
1931  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
1932  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
1933  }
1934  }
1935  os << " Background value: " << mRoot.background() << "\n";
1936 
1937  if (verboseLevel == 1) return;
1938 
1939  // The following is tree information that is expensive to extract.
1940 
1941  if (nodeCount.empty()) {
1942  nodeCount.resize(dims.size());
1943  for (NodeCIter it = cbeginNode(); it; ++it) {
1944  ++(nodeCount[it.getDepth()]);
1945  }
1946  }
1947 
1948  // Statistics of topology and values
1949  ValueType minVal, maxVal;
1950  this->evalMinMax(minVal, maxVal);
1951  os << " Min value: " << minVal << "\n";
1952  os << " Max value: " << maxVal << "\n";
1953 
1954  const uint64_t
1955  leafCount = *nodeCount.rbegin(),
1956  numActiveVoxels = this->activeVoxelCount(),
1957  numActiveLeafVoxels = this->activeLeafVoxelCount();
1958 
1959  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
1960 
1961  Coord dim(0, 0, 0);
1962  uint64_t totalVoxels = 0;
1963  if (numActiveVoxels) { // nonempty
1964  CoordBBox bbox;
1965  this->evalActiveVoxelBoundingBox(bbox);
1966  dim = bbox.extents();
1967  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
1968 
1969  os << " Bounding box of active voxels: " << bbox << "\n";
1970  os << " Dimensions of active voxels: "
1971  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
1972 
1973  const double activeRatio = (100.0 * numActiveVoxels) / totalVoxels;
1974  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
1975 
1976  if (leafCount>0) {
1977  const double fillRatio =
1978  (100.0 * numActiveLeafVoxels) / (leafCount * LeafNodeType::NUM_VOXELS);
1979  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
1980  }
1981  } else {
1982  os << " Tree is empty!\n";
1983  }
1984  os << std::flush;
1985 
1986  if (verboseLevel == 2) return;
1987 
1988  // Memory footprint in bytes
1989  const uint64_t
1990  actualMem = this->memUsage(),
1991  denseMem = sizeof(ValueType) * totalVoxels,
1992  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
1994 
1995  os << "Memory footprint:\n";
1996  util::printBytes(os, actualMem, " Actual footprint: ");
1997  util::printBytes(os, voxelsMem, " Voxel footprint: ");
1998 
1999  if (numActiveVoxels) {
2000  util::printBytes(os, denseMem, " Dense* footprint: ");
2001  os << " Actual footprint is " << (100.0 * actualMem / denseMem)
2002  << "% of dense* footprint\n";
2003  os << " Leaf voxel footprint is " << (100.0 * voxelsMem / actualMem)
2004  << "% of actual footprint\n";
2005  os << " *Dense refers to the smallest equivalent non-sparse volume" << std::endl;
2006  }
2007 }
2008 
2009 } // namespace tree
2010 } // namespace OPENVDB_VERSION_NAME
2011 } // namespace openvdb
2012 
2013 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
2014 
2015 // Copyright (c) 2012-2013 DreamWorks Animation LLC
2016 // All rights reserved. This software is distributed under the
2017 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )