OpenVDB  6.2.1
Tree.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 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 <openvdb/Types.h>
37 #include <openvdb/Metadata.h>
38 #include <openvdb/math/Math.h>
39 #include <openvdb/math/BBox.h>
40 #include <openvdb/util/Formats.h>
41 #include <openvdb/util/logging.h>
42 #include <openvdb/Platform.h>
43 #include "RootNode.h"
44 #include "InternalNode.h"
45 #include "LeafNode.h"
46 #include "TreeIterator.h"
47 #include "ValueAccessor.h"
48 #include <tbb/atomic.h>
49 #include <tbb/concurrent_hash_map.h>
50 #include <cstdint>
51 #include <iostream>
52 #include <sstream>
53 #include <vector>
54 
55 
56 namespace openvdb {
58 namespace OPENVDB_VERSION_NAME {
59 namespace tree {
60 
63 {
64 public:
67 
68  TreeBase() = default;
69  TreeBase(const TreeBase&) = default;
70  TreeBase& operator=(const TreeBase&) = delete; // disallow assignment
71  virtual ~TreeBase() = default;
72 
74  virtual const Name& type() const = 0;
75 
77  virtual Name valueType() const = 0;
78 
80  virtual TreeBase::Ptr copy() const = 0;
81 
82  //
83  // Tree methods
84  //
87  virtual Metadata::Ptr getBackgroundValue() const { return Metadata::Ptr(); }
88 
96  virtual bool evalLeafBoundingBox(CoordBBox& bbox) const = 0;
97 
101  virtual bool evalLeafDim(Coord& dim) const = 0;
102 
110  virtual bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const = 0;
111 
115  virtual bool evalActiveVoxelDim(Coord& dim) const = 0;
116 
117  virtual void getIndexRange(CoordBBox& bbox) const = 0;
118 
119 #if OPENVDB_ABI_VERSION_NUMBER >= 3
120  virtual void clipUnallocatedNodes() = 0;
126 #endif
127 #if OPENVDB_ABI_VERSION_NUMBER >= 4
128  virtual Index32 unallocatedLeafCount() const = 0;
130 #endif
131 
132 
133  //
134  // Statistics
135  //
139  virtual Index treeDepth() const = 0;
141  virtual Index32 leafCount() const = 0;
143  virtual Index32 nonLeafCount() const = 0;
145  virtual Index64 activeLeafVoxelCount() const = 0;
147  virtual Index64 inactiveLeafVoxelCount() const = 0;
149  virtual Index64 activeVoxelCount() const = 0;
151  virtual Index64 inactiveVoxelCount() const = 0;
152 #if OPENVDB_ABI_VERSION_NUMBER >= 3
153  virtual Index64 activeTileCount() const = 0;
155 #endif
156 
158  virtual Index64 memUsage() const { return 0; }
159 
160 
161  //
162  // I/O methods
163  //
167  virtual void readTopology(std::istream&, bool saveFloatAsHalf = false);
171  virtual void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const;
172 
174  virtual void readBuffers(std::istream&, bool saveFloatAsHalf = false) = 0;
175 #if OPENVDB_ABI_VERSION_NUMBER >= 3
176  virtual void readBuffers(std::istream&, const CoordBBox&, bool saveFloatAsHalf = false) = 0;
183  virtual void readNonresidentBuffers() const = 0;
184 #endif
185  virtual void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const = 0;
187 
195  virtual void print(std::ostream& os = std::cout, int verboseLevel = 1) const;
196 };
197 
198 
200 
201 
202 template<typename _RootNodeType>
203 class Tree: public TreeBase
204 {
205 public:
208 
209  using RootNodeType = _RootNodeType;
210  using ValueType = typename RootNodeType::ValueType;
211  using BuildType = typename RootNodeType::BuildType;
212  using LeafNodeType = typename RootNodeType::LeafNodeType;
213 
214  static const Index DEPTH = RootNodeType::LEVEL + 1;
215 
222  template<typename OtherValueType>
223  struct ValueConverter {
225  };
226 
227 
228  Tree() {}
229 
230  Tree& operator=(const Tree&) = delete; // disallow assignment
231 
233  Tree(const Tree& other): TreeBase(other), mRoot(other.mRoot)
234  {
235  }
236 
243  template<typename OtherRootType>
244  explicit Tree(const Tree<OtherRootType>& other): TreeBase(other), mRoot(other.root())
245  {
246  }
247 
258  template<typename OtherTreeType>
259  Tree(const OtherTreeType& other,
260  const ValueType& inactiveValue,
261  const ValueType& activeValue,
262  TopologyCopy):
263  TreeBase(other),
264  mRoot(other.root(), inactiveValue, activeValue, TopologyCopy())
265  {
266  }
267 
279  template<typename OtherTreeType>
280  Tree(const OtherTreeType& other, const ValueType& background, TopologyCopy):
281  TreeBase(other),
282  mRoot(other.root(), background, TopologyCopy())
283  {
284  }
285 
287  Tree(const ValueType& background): mRoot(background) {}
288 
289  ~Tree() override { this->clear(); releaseAllAccessors(); }
290 
292  TreeBase::Ptr copy() const override { return TreeBase::Ptr(new Tree(*this)); }
293 
295  Name valueType() const override { return typeNameAsString<ValueType>(); }
296 
298  static const Name& treeType();
300  const Name& type() const override { return this->treeType(); }
301 
302  bool operator==(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
303  bool operator!=(const Tree&) const { OPENVDB_THROW(NotImplementedError, ""); }
304 
306  RootNodeType& root() { return mRoot; }
308  const RootNodeType& root() const { return mRoot; }
310 
311 
312  //
313  // Tree methods
314  //
317  template<typename OtherRootNodeType>
318  bool hasSameTopology(const Tree<OtherRootNodeType>& other) const;
319 
320  bool evalLeafBoundingBox(CoordBBox& bbox) const override;
321  bool evalActiveVoxelBoundingBox(CoordBBox& bbox) const override;
322  bool evalActiveVoxelDim(Coord& dim) const override;
323  bool evalLeafDim(Coord& dim) const override;
324 
328  static void getNodeLog2Dims(std::vector<Index>& dims);
329 
330 
331  //
332  // I/O methods
333  //
337  void readTopology(std::istream&, bool saveFloatAsHalf = false) override;
341  void writeTopology(std::ostream&, bool saveFloatAsHalf = false) const override;
343  void readBuffers(std::istream&, bool saveFloatAsHalf = false) override;
344 #if OPENVDB_ABI_VERSION_NUMBER >= 3
345  void readBuffers(std::istream&, const CoordBBox&, bool saveFloatAsHalf = false) override;
352  void readNonresidentBuffers() const override;
353 #endif
354  void writeBuffers(std::ostream&, bool saveFloatAsHalf = false) const override;
356 
357  void print(std::ostream& os = std::cout, int verboseLevel = 1) const override;
358 
359 
360  //
361  // Statistics
362  //
366  Index treeDepth() const override { return DEPTH; }
368  Index32 leafCount() const override { return mRoot.leafCount(); }
370  Index32 nonLeafCount() const override { return mRoot.nonLeafCount(); }
372  Index64 activeLeafVoxelCount() const override { return mRoot.onLeafVoxelCount(); }
374  Index64 inactiveLeafVoxelCount() const override { return mRoot.offLeafVoxelCount(); }
376  Index64 activeVoxelCount() const override { return mRoot.onVoxelCount(); }
378  Index64 inactiveVoxelCount() const override;
379 #if OPENVDB_ABI_VERSION_NUMBER >= 3
380  Index64 activeTileCount() const override { return mRoot.onTileCount(); }
382 #else
383  Index64 activeTileCount() const { return mRoot.onTileCount(); }
384 #endif
385 
387  void evalMinMax(ValueType &min, ValueType &max) const;
388 
389  Index64 memUsage() const override { return sizeof(*this) + mRoot.memUsage(); }
390 
391 
392  //
393  // Voxel access methods (using signed indexing)
394  //
396  const ValueType& getValue(const Coord& xyz) const;
399  template<typename AccessT> const ValueType& getValue(const Coord& xyz, AccessT&) const;
400 
404  int getValueDepth(const Coord& xyz) const;
405 
407  void setActiveState(const Coord& xyz, bool on);
409  void setValueOnly(const Coord& xyz, const ValueType& value);
411  void setValueOn(const Coord& xyz);
413  void setValueOn(const Coord& xyz, const ValueType& value);
415  void setValue(const Coord& xyz, const ValueType& value);
418  template<typename AccessT> void setValue(const Coord& xyz, const ValueType& value, AccessT&);
420  void setValueOff(const Coord& xyz);
422  void setValueOff(const Coord& xyz, const ValueType& value);
423 
442  template<typename ModifyOp>
443  void modifyValue(const Coord& xyz, const ModifyOp& op);
444 
464  template<typename ModifyOp>
465  void modifyValueAndActiveState(const Coord& xyz, const ModifyOp& op);
466 
469  bool probeValue(const Coord& xyz, ValueType& value) const;
470 
472  bool isValueOn(const Coord& xyz) const { return mRoot.isValueOn(xyz); }
474  bool isValueOff(const Coord& xyz) const { return !this->isValueOn(xyz); }
476  bool hasActiveTiles() const { return mRoot.hasActiveTiles(); }
477 
479  void clip(const CoordBBox&);
480 
481 #if OPENVDB_ABI_VERSION_NUMBER >= 3
482  void clipUnallocatedNodes() override;
488 #endif
489 #if OPENVDB_ABI_VERSION_NUMBER >= 4
490  Index32 unallocatedLeafCount() const override;
492 #endif
493 
495  void sparseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
504  void fill(const CoordBBox& bbox, const ValueType& value, bool active = true)
505  {
506  this->sparseFill(bbox, value, active);
507  }
509 
517  void denseFill(const CoordBBox& bbox, const ValueType& value, bool active = true);
518 
527  void voxelizeActiveTiles(bool threaded = true);
528 
533  void prune(const ValueType& tolerance = zeroVal<ValueType>())
534  {
535  this->clearAllAccessors();
536  mRoot.prune(tolerance);
537  }
538 
544  void addLeaf(LeafNodeType* leaf) { assert(leaf); mRoot.addLeaf(leaf); }
545 
550  void addTile(Index level, const Coord& xyz, const ValueType& value, bool active);
551 
556  template<typename NodeT>
557  NodeT* stealNode(const Coord& xyz, const ValueType& value, bool active);
558 
564  LeafNodeType* touchLeaf(const Coord& xyz);
565 
567  template<typename NodeType> NodeType* probeNode(const Coord& xyz);
570  template<typename NodeType> const NodeType* probeConstNode(const Coord& xyz) const;
571  template<typename NodeType> const NodeType* probeNode(const Coord& xyz) const;
573 
575  LeafNodeType* probeLeaf(const Coord& xyz);
578  const LeafNodeType* probeConstLeaf(const Coord& xyz) const;
579  const LeafNodeType* probeLeaf(const Coord& xyz) const { return this->probeConstLeaf(xyz); }
581 
583  template<typename ArrayT> void getNodes(ArrayT& array) { mRoot.getNodes(array); }
606  template<typename ArrayT> void getNodes(ArrayT& array) const { mRoot.getNodes(array); }
608 
632  template<typename ArrayT>
633  void stealNodes(ArrayT& array) { this->clearAllAccessors(); mRoot.stealNodes(array); }
634  template<typename ArrayT>
635  void stealNodes(ArrayT& array, const ValueType& value, bool state)
636  {
637  this->clearAllAccessors();
638  mRoot.stealNodes(array, value, state);
639  }
640 
641  //
642  // Aux methods
643  //
646  bool empty() const { return mRoot.empty(); }
647 
649  void clear();
650 
652  void clearAllAccessors();
653 
655  void attachAccessor(ValueAccessorBase<Tree, true>&) const;
658  void attachAccessor(ValueAccessorBase<const Tree, true>&) const;
660 
662  void attachAccessor(ValueAccessorBase<Tree, false>&) const {}
666 
668  void releaseAccessor(ValueAccessorBase<Tree, true>&) const;
670  void releaseAccessor(ValueAccessorBase<const Tree, true>&) const;
672 
674  void releaseAccessor(ValueAccessorBase<Tree, false>&) const {}
678 
681  Metadata::Ptr getBackgroundValue() const override;
682 
688  const ValueType& background() const { return mRoot.background(); }
689 
691  void getIndexRange(CoordBBox& bbox) const override { mRoot.getIndexRange(bbox); }
692 
700  void merge(Tree& other, MergePolicy = MERGE_ACTIVE_STATES);
701 
715  template<typename OtherRootNodeType>
716  void topologyUnion(const Tree<OtherRootNodeType>& other);
717 
731  template<typename OtherRootNodeType>
732  void topologyIntersection(const Tree<OtherRootNodeType>& other);
733 
744  template<typename OtherRootNodeType>
745  void topologyDifference(const Tree<OtherRootNodeType>& other);
746 
791  template<typename CombineOp>
792  void combine(Tree& other, CombineOp& op, bool prune = false);
793 #ifndef _MSC_VER
794  template<typename CombineOp>
795  void combine(Tree& other, const CombineOp& op, bool prune = false);
796 #endif
797 
836  template<typename ExtendedCombineOp>
837  void combineExtended(Tree& other, ExtendedCombineOp& op, bool prune = false);
838 #ifndef _MSC_VER
839  template<typename ExtendedCombineOp>
840  void combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune = false);
841 #endif
842 
871  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
872  void combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune = false);
873 #ifndef _MSC_VER
874  template<typename CombineOp, typename OtherTreeType /*= Tree*/>
875  void combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune = false);
876 #endif
877 
951  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
952  void combine2Extended(const Tree& a, const OtherTreeType& b, ExtendedCombineOp& op,
953  bool prune = false);
954 #ifndef _MSC_VER
955  template<typename ExtendedCombineOp, typename OtherTreeType /*= Tree*/>
956  void combine2Extended(const Tree& a, const OtherTreeType& b, const ExtendedCombineOp&,
957  bool prune = false);
958 #endif
959 
1000  template<typename BBoxOp> void visitActiveBBox(BBoxOp& op) const { mRoot.visitActiveBBox(op); }
1001 
1055  template<typename VisitorOp> void visit(VisitorOp& op);
1056  template<typename VisitorOp> void visit(const VisitorOp& op);
1057 
1062  template<typename VisitorOp> void visit(VisitorOp& op) const;
1063  template<typename VisitorOp> void visit(const VisitorOp& op) const;
1064 
1112  template<typename OtherTreeType, typename VisitorOp>
1113  void visit2(OtherTreeType& other, VisitorOp& op);
1114  template<typename OtherTreeType, typename VisitorOp>
1115  void visit2(OtherTreeType& other, const VisitorOp& op);
1116 
1127  template<typename OtherTreeType, typename VisitorOp>
1128  void visit2(OtherTreeType& other, VisitorOp& op) const;
1129  template<typename OtherTreeType, typename VisitorOp>
1130  void visit2(OtherTreeType& other, const VisitorOp& op) const;
1131 
1132 
1133  //
1134  // Iteration
1135  //
1137  typename RootNodeType::ChildOnCIter beginRootChildren() const { return mRoot.cbeginChildOn(); }
1139  typename RootNodeType::ChildOnCIter cbeginRootChildren() const { return mRoot.cbeginChildOn(); }
1140  typename RootNodeType::ChildOnIter beginRootChildren() { return mRoot.beginChildOn(); }
1142 
1144  typename RootNodeType::ChildOffCIter beginRootTiles() const { return mRoot.cbeginChildOff(); }
1146  typename RootNodeType::ChildOffCIter cbeginRootTiles() const { return mRoot.cbeginChildOff(); }
1147  typename RootNodeType::ChildOffIter beginRootTiles() { return mRoot.beginChildOff(); }
1149 
1151  typename RootNodeType::ChildAllCIter beginRootDense() const { return mRoot.cbeginChildAll(); }
1153  typename RootNodeType::ChildAllCIter cbeginRootDense() const { return mRoot.cbeginChildAll(); }
1154  typename RootNodeType::ChildAllIter beginRootDense() { return mRoot.beginChildAll(); }
1156 
1157 
1163 
1169 
1171  NodeIter beginNode() { return NodeIter(*this); }
1173  NodeCIter beginNode() const { return NodeCIter(*this); }
1174  NodeCIter cbeginNode() const { return NodeCIter(*this); }
1176 
1178  LeafIter beginLeaf() { return LeafIter(*this); }
1180  LeafCIter beginLeaf() const { return LeafCIter(*this); }
1181  LeafCIter cbeginLeaf() const { return LeafCIter(*this); }
1183 
1190 
1192  ValueAllIter beginValueAll() { return ValueAllIter(*this); }
1194  ValueAllCIter beginValueAll() const { return ValueAllCIter(*this); }
1195  ValueAllCIter cbeginValueAll() const { return ValueAllCIter(*this); }
1197 
1198  ValueOnIter beginValueOn() { return ValueOnIter(*this); }
1200  ValueOnCIter beginValueOn() const { return ValueOnCIter(*this); }
1201  ValueOnCIter cbeginValueOn() const { return ValueOnCIter(*this); }
1203 
1204  ValueOffIter beginValueOff() { return ValueOffIter(*this); }
1206  ValueOffCIter beginValueOff() const { return ValueOffCIter(*this); }
1207  ValueOffCIter cbeginValueOff() const { return ValueOffCIter(*this); }
1209 
1212  template<typename IterT> IterT begin();
1215  template<typename CIterT> CIterT cbegin() const;
1216 
1217 
1218 protected:
1219  using AccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<Tree, true>*, bool>;
1220  using ConstAccessorRegistry = tbb::concurrent_hash_map<ValueAccessorBase<const Tree, true>*, bool>;
1221 
1224  void releaseAllAccessors();
1225 
1226  // TBB body object used to deallocates nodes in parallel.
1227  template<typename NodeType>
1229  DeallocateNodes(std::vector<NodeType*>& nodes)
1230  : mNodes(nodes.empty() ? nullptr : &nodes.front()) { }
1231  void operator()(const tbb::blocked_range<size_t>& range) const {
1232  for (size_t n = range.begin(), N = range.end(); n < N; ++n) {
1233  delete mNodes[n]; mNodes[n] = nullptr;
1234  }
1235  }
1236  NodeType ** const mNodes;
1237  };
1238 
1239  //
1240  // Data members
1241  //
1242  RootNodeType mRoot; // root node of the tree
1245 
1246  static tbb::atomic<const Name*> sTreeTypeName;
1247 }; // end of Tree class
1248 
1249 template<typename _RootNodeType>
1250 tbb::atomic<const Name*> Tree<_RootNodeType>::sTreeTypeName;
1251 
1252 
1257 template<typename T, Index N1=4, Index N2=3>
1258 struct Tree3 {
1260 };
1261 
1262 
1267 template<typename T, Index N1=5, Index N2=4, Index N3=3>
1268 struct Tree4 {
1270 };
1271 
1276 template<typename T, Index N1=6, Index N2=5, Index N3=4, Index N4=3>
1277 struct Tree5 {
1278  using Type =
1280 };
1281 
1282 
1284 
1285 
1286 inline void
1287 TreeBase::readTopology(std::istream& is, bool /*saveFloatAsHalf*/)
1288 {
1289  int32_t bufferCount;
1290  is.read(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1291  if (bufferCount != 1) OPENVDB_LOG_WARN("multi-buffer trees are no longer supported");
1292 }
1293 
1294 
1295 inline void
1296 TreeBase::writeTopology(std::ostream& os, bool /*saveFloatAsHalf*/) const
1297 {
1298  int32_t bufferCount = 1;
1299  os.write(reinterpret_cast<char*>(&bufferCount), sizeof(int32_t));
1300 }
1301 
1302 
1303 inline void
1304 TreeBase::print(std::ostream& os, int /*verboseLevel*/) const
1305 {
1306  os << " Tree Type: " << type()
1307  << " Active Voxel Count: " << activeVoxelCount() << std::endl
1308 #if OPENVDB_ABI_VERSION_NUMBER >= 3
1309  << " Active tile Count: " << activeTileCount() << std::endl
1310 #endif
1311  << " Inactive Voxel Count: " << inactiveVoxelCount() << std::endl
1312  << " Leaf Node Count: " << leafCount() << std::endl
1313  << " Non-leaf Node Count: " << nonLeafCount() << std::endl;
1314 }
1315 
1316 
1318 
1319 
1320 //
1321 // Type traits for tree iterators
1322 //
1323 
1326 template<typename TreeT, typename IterT> struct TreeIterTraits;
1327 
1328 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnIter> {
1329  static typename TreeT::RootNodeType::ChildOnIter begin(TreeT& tree) {
1330  return tree.beginRootChildren();
1331  }
1332 };
1333 
1334 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOnCIter> {
1335  static typename TreeT::RootNodeType::ChildOnCIter begin(const TreeT& tree) {
1336  return tree.cbeginRootChildren();
1337  }
1338 };
1339 
1340 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffIter> {
1341  static typename TreeT::RootNodeType::ChildOffIter begin(TreeT& tree) {
1342  return tree.beginRootTiles();
1343  }
1344 };
1345 
1346 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildOffCIter> {
1347  static typename TreeT::RootNodeType::ChildOffCIter begin(const TreeT& tree) {
1348  return tree.cbeginRootTiles();
1349  }
1350 };
1351 
1352 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllIter> {
1353  static typename TreeT::RootNodeType::ChildAllIter begin(TreeT& tree) {
1354  return tree.beginRootDense();
1355  }
1356 };
1357 
1358 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::RootNodeType::ChildAllCIter> {
1359  static typename TreeT::RootNodeType::ChildAllCIter begin(const TreeT& tree) {
1360  return tree.cbeginRootDense();
1361  }
1362 };
1363 
1364 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeIter> {
1365  static typename TreeT::NodeIter begin(TreeT& tree) { return tree.beginNode(); }
1366 };
1367 
1368 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::NodeCIter> {
1369  static typename TreeT::NodeCIter begin(const TreeT& tree) { return tree.cbeginNode(); }
1370 };
1371 
1372 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafIter> {
1373  static typename TreeT::LeafIter begin(TreeT& tree) { return tree.beginLeaf(); }
1374 };
1375 
1376 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::LeafCIter> {
1377  static typename TreeT::LeafCIter begin(const TreeT& tree) { return tree.cbeginLeaf(); }
1378 };
1379 
1380 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnIter> {
1381  static typename TreeT::ValueOnIter begin(TreeT& tree) { return tree.beginValueOn(); }
1382 };
1383 
1384 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOnCIter> {
1385  static typename TreeT::ValueOnCIter begin(const TreeT& tree) { return tree.cbeginValueOn(); }
1386 };
1387 
1388 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffIter> {
1389  static typename TreeT::ValueOffIter begin(TreeT& tree) { return tree.beginValueOff(); }
1390 };
1391 
1392 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueOffCIter> {
1393  static typename TreeT::ValueOffCIter begin(const TreeT& tree) { return tree.cbeginValueOff(); }
1394 };
1395 
1396 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllIter> {
1397  static typename TreeT::ValueAllIter begin(TreeT& tree) { return tree.beginValueAll(); }
1398 };
1399 
1400 template<typename TreeT> struct TreeIterTraits<TreeT, typename TreeT::ValueAllCIter> {
1401  static typename TreeT::ValueAllCIter begin(const TreeT& tree) { return tree.cbeginValueAll(); }
1402 };
1403 
1404 
1405 template<typename RootNodeType>
1406 template<typename IterT>
1407 inline IterT
1409 {
1410  return TreeIterTraits<Tree, IterT>::begin(*this);
1411 }
1412 
1413 
1414 template<typename RootNodeType>
1415 template<typename IterT>
1416 inline IterT
1418 {
1419  return TreeIterTraits<Tree, IterT>::begin(*this);
1420 }
1421 
1422 
1424 
1425 
1426 template<typename RootNodeType>
1427 void
1428 Tree<RootNodeType>::readTopology(std::istream& is, bool saveFloatAsHalf)
1429 {
1430  this->clearAllAccessors();
1431  TreeBase::readTopology(is, saveFloatAsHalf);
1432  mRoot.readTopology(is, saveFloatAsHalf);
1433 }
1434 
1435 
1436 template<typename RootNodeType>
1437 void
1438 Tree<RootNodeType>::writeTopology(std::ostream& os, bool saveFloatAsHalf) const
1439 {
1440  TreeBase::writeTopology(os, saveFloatAsHalf);
1441  mRoot.writeTopology(os, saveFloatAsHalf);
1442 }
1443 
1444 
1445 template<typename RootNodeType>
1446 inline void
1447 Tree<RootNodeType>::readBuffers(std::istream &is, bool saveFloatAsHalf)
1448 {
1449  this->clearAllAccessors();
1450  mRoot.readBuffers(is, saveFloatAsHalf);
1451 }
1452 
1453 
1454 #if OPENVDB_ABI_VERSION_NUMBER >= 3
1455 
1456 template<typename RootNodeType>
1457 inline void
1458 Tree<RootNodeType>::readBuffers(std::istream &is, const CoordBBox& bbox, bool saveFloatAsHalf)
1459 {
1460  this->clearAllAccessors();
1461  mRoot.readBuffers(is, bbox, saveFloatAsHalf);
1462 }
1463 
1464 
1465 template<typename RootNodeType>
1466 inline void
1468 {
1469  for (LeafCIter it = this->cbeginLeaf(); it; ++it) {
1470  // Retrieving the value of a leaf voxel forces loading of the leaf node's voxel buffer.
1471  it->getValue(Index(0));
1472  }
1473 }
1474 
1475 #endif
1476 
1477 
1478 template<typename RootNodeType>
1479 inline void
1480 Tree<RootNodeType>::writeBuffers(std::ostream &os, bool saveFloatAsHalf) const
1481 {
1482  mRoot.writeBuffers(os, saveFloatAsHalf);
1483 }
1484 
1485 
1486 template<typename RootNodeType>
1487 inline void
1489 {
1490  std::vector<LeafNodeType*> leafnodes;
1491  this->stealNodes(leafnodes);
1492 
1493  tbb::parallel_for(tbb::blocked_range<size_t>(0, leafnodes.size()),
1494  DeallocateNodes<LeafNodeType>(leafnodes));
1495 
1496  std::vector<typename RootNodeType::ChildNodeType*> internalNodes;
1497  this->stealNodes(internalNodes);
1498 
1499  tbb::parallel_for(tbb::blocked_range<size_t>(0, internalNodes.size()),
1501 
1502  mRoot.clear();
1503 
1504  this->clearAllAccessors();
1505 }
1506 
1507 
1509 
1510 
1511 template<typename RootNodeType>
1512 inline void
1514 {
1515  typename AccessorRegistry::accessor a;
1516  mAccessorRegistry.insert(a, &accessor);
1517 }
1518 
1519 
1520 template<typename RootNodeType>
1521 inline void
1523 {
1524  typename ConstAccessorRegistry::accessor a;
1525  mConstAccessorRegistry.insert(a, &accessor);
1526 }
1527 
1528 
1529 template<typename RootNodeType>
1530 inline void
1532 {
1533  mAccessorRegistry.erase(&accessor);
1534 }
1535 
1536 
1537 template<typename RootNodeType>
1538 inline void
1540 {
1541  mConstAccessorRegistry.erase(&accessor);
1542 }
1543 
1544 
1545 template<typename RootNodeType>
1546 inline void
1548 {
1549  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1550  it != mAccessorRegistry.end(); ++it)
1551  {
1552  if (it->first) it->first->clear();
1553  }
1554 
1555  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1556  it != mConstAccessorRegistry.end(); ++it)
1557  {
1558  if (it->first) it->first->clear();
1559  }
1560 }
1561 
1562 
1563 template<typename RootNodeType>
1564 inline void
1566 {
1567  mAccessorRegistry.erase(nullptr);
1568  for (typename AccessorRegistry::iterator it = mAccessorRegistry.begin();
1569  it != mAccessorRegistry.end(); ++it)
1570  {
1571  it->first->release();
1572  }
1573  mAccessorRegistry.clear();
1574 
1575  mAccessorRegistry.erase(nullptr);
1576  for (typename ConstAccessorRegistry::iterator it = mConstAccessorRegistry.begin();
1577  it != mConstAccessorRegistry.end(); ++it)
1578  {
1579  it->first->release();
1580  }
1581  mConstAccessorRegistry.clear();
1582 }
1583 
1584 
1586 
1587 
1588 template<typename RootNodeType>
1589 inline const typename RootNodeType::ValueType&
1591 {
1592  return mRoot.getValue(xyz);
1593 }
1594 
1595 
1596 template<typename RootNodeType>
1597 template<typename AccessT>
1598 inline const typename RootNodeType::ValueType&
1599 Tree<RootNodeType>::getValue(const Coord& xyz, AccessT& accessor) const
1600 {
1601  return accessor.getValue(xyz);
1602 }
1603 
1604 
1605 template<typename RootNodeType>
1606 inline int
1608 {
1609  return mRoot.getValueDepth(xyz);
1610 }
1611 
1612 
1613 template<typename RootNodeType>
1614 inline void
1616 {
1617  mRoot.setValueOff(xyz);
1618 }
1619 
1620 
1621 template<typename RootNodeType>
1622 inline void
1624 {
1625  mRoot.setValueOff(xyz, value);
1626 }
1627 
1628 
1629 template<typename RootNodeType>
1630 inline void
1632 {
1633  mRoot.setActiveState(xyz, on);
1634 }
1635 
1636 
1637 template<typename RootNodeType>
1638 inline void
1640 {
1641  mRoot.setValueOn(xyz, value);
1642 }
1643 
1644 template<typename RootNodeType>
1645 inline void
1647 {
1648  mRoot.setValueOnly(xyz, value);
1649 }
1650 
1651 template<typename RootNodeType>
1652 template<typename AccessT>
1653 inline void
1654 Tree<RootNodeType>::setValue(const Coord& xyz, const ValueType& value, AccessT& accessor)
1655 {
1656  accessor.setValue(xyz, value);
1657 }
1658 
1659 
1660 template<typename RootNodeType>
1661 inline void
1663 {
1664  mRoot.setActiveState(xyz, true);
1665 }
1666 
1667 
1668 template<typename RootNodeType>
1669 inline void
1671 {
1672  mRoot.setValueOn(xyz, value);
1673 }
1674 
1675 
1676 template<typename RootNodeType>
1677 template<typename ModifyOp>
1678 inline void
1679 Tree<RootNodeType>::modifyValue(const Coord& xyz, const ModifyOp& op)
1680 {
1681  mRoot.modifyValue(xyz, op);
1682 }
1683 
1684 
1685 template<typename RootNodeType>
1686 template<typename ModifyOp>
1687 inline void
1689 {
1690  mRoot.modifyValueAndActiveState(xyz, op);
1691 }
1692 
1693 
1694 template<typename RootNodeType>
1695 inline bool
1697 {
1698  return mRoot.probeValue(xyz, value);
1699 }
1700 
1701 
1703 
1704 
1705 template<typename RootNodeType>
1706 inline void
1708  const ValueType& value, bool active)
1709 {
1710  mRoot.addTile(level, xyz, value, active);
1711 }
1712 
1713 
1714 template<typename RootNodeType>
1715 template<typename NodeT>
1716 inline NodeT*
1717 Tree<RootNodeType>::stealNode(const Coord& xyz, const ValueType& value, bool active)
1718 {
1719  this->clearAllAccessors();
1720  return mRoot.template stealNode<NodeT>(xyz, value, active);
1721 }
1722 
1723 
1724 template<typename RootNodeType>
1725 inline typename RootNodeType::LeafNodeType*
1727 {
1728  return mRoot.touchLeaf(xyz);
1729 }
1730 
1731 
1732 template<typename RootNodeType>
1733 inline typename RootNodeType::LeafNodeType*
1735 {
1736  return mRoot.probeLeaf(xyz);
1737 }
1738 
1739 
1740 template<typename RootNodeType>
1741 inline const typename RootNodeType::LeafNodeType*
1743 {
1744  return mRoot.probeConstLeaf(xyz);
1745 }
1746 
1747 
1748 template<typename RootNodeType>
1749 template<typename NodeType>
1750 inline NodeType*
1752 {
1753  return mRoot.template probeNode<NodeType>(xyz);
1754 }
1755 
1756 
1757 template<typename RootNodeType>
1758 template<typename NodeType>
1759 inline const NodeType*
1761 {
1762  return this->template probeConstNode<NodeType>(xyz);
1763 }
1764 
1765 
1766 template<typename RootNodeType>
1767 template<typename NodeType>
1768 inline const NodeType*
1770 {
1771  return mRoot.template probeConstNode<NodeType>(xyz);
1772 }
1773 
1774 
1776 
1777 
1778 template<typename RootNodeType>
1779 inline void
1781 {
1782  this->clearAllAccessors();
1783  return mRoot.clip(bbox);
1784 }
1785 
1786 
1787 #if OPENVDB_ABI_VERSION_NUMBER >= 3
1788 template<typename RootNodeType>
1789 inline void
1791 {
1792  this->clearAllAccessors();
1793  for (LeafIter it = this->beginLeaf(); it; ) {
1794  const LeafNodeType* leaf = it.getLeaf();
1795  ++it; // advance the iterator before deleting the leaf node
1796  if (!leaf->isAllocated()) {
1797  this->addTile(/*level=*/0, leaf->origin(), this->background(), /*active=*/false);
1798  }
1799  }
1800 }
1801 #endif
1802 
1803 #if OPENVDB_ABI_VERSION_NUMBER >= 4
1804 template<typename RootNodeType>
1805 inline Index32
1807 {
1808  Index32 sum = 0;
1809  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
1810  return sum;
1811 }
1812 #endif
1813 
1814 
1815 template<typename RootNodeType>
1816 inline void
1817 Tree<RootNodeType>::sparseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1818 {
1819  this->clearAllAccessors();
1820  return mRoot.sparseFill(bbox, value, active);
1821 }
1822 
1823 
1824 template<typename RootNodeType>
1825 inline void
1826 Tree<RootNodeType>::denseFill(const CoordBBox& bbox, const ValueType& value, bool active)
1827 {
1828  this->clearAllAccessors();
1829  return mRoot.denseFill(bbox, value, active);
1830 }
1831 
1832 
1833 template<typename RootNodeType>
1834 inline void
1836 {
1837  this->clearAllAccessors();
1838  mRoot.voxelizeActiveTiles(threaded);
1839 }
1840 
1841 
1842 template<typename RootNodeType>
1845 {
1846  Metadata::Ptr result;
1847  if (Metadata::isRegisteredType(valueType())) {
1848  using MetadataT = TypedMetadata<ValueType>;
1849  result = Metadata::createMetadata(valueType());
1850  if (result->typeName() == MetadataT::staticTypeName()) {
1851  MetadataT* m = static_cast<MetadataT*>(result.get());
1852  m->value() = mRoot.background();
1853  }
1854  }
1855  return result;
1856 }
1857 
1858 
1860 
1861 
1862 template<typename RootNodeType>
1863 inline void
1865 {
1866  this->clearAllAccessors();
1867  other.clearAllAccessors();
1868  switch (policy) {
1869  case MERGE_ACTIVE_STATES:
1870  mRoot.template merge<MERGE_ACTIVE_STATES>(other.mRoot); break;
1871  case MERGE_NODES:
1872  mRoot.template merge<MERGE_NODES>(other.mRoot); break;
1874  mRoot.template merge<MERGE_ACTIVE_STATES_AND_NODES>(other.mRoot); break;
1875  }
1876 }
1877 
1878 
1879 template<typename RootNodeType>
1880 template<typename OtherRootNodeType>
1881 inline void
1883 {
1884  this->clearAllAccessors();
1885  mRoot.topologyUnion(other.root());
1886 }
1887 
1888 template<typename RootNodeType>
1889 template<typename OtherRootNodeType>
1890 inline void
1892 {
1893  this->clearAllAccessors();
1894  mRoot.topologyIntersection(other.root());
1895 }
1896 
1897 template<typename RootNodeType>
1898 template<typename OtherRootNodeType>
1899 inline void
1901 {
1902  this->clearAllAccessors();
1903  mRoot.topologyDifference(other.root());
1904 }
1905 
1907 
1908 
1911 template<typename AValueT, typename CombineOp, typename BValueT = AValueT>
1913 {
1914  CombineOpAdapter(CombineOp& _op): op(_op) {}
1915 
1917  op(args.a(), args.b(), args.result());
1918  }
1919 
1920  CombineOp& op;
1921 };
1922 
1923 
1924 template<typename RootNodeType>
1925 template<typename CombineOp>
1926 inline void
1927 Tree<RootNodeType>::combine(Tree& other, CombineOp& op, bool prune)
1928 {
1930  this->combineExtended(other, extendedOp, prune);
1931 }
1932 
1933 
1936 #ifndef _MSC_VER
1937 template<typename RootNodeType>
1938 template<typename CombineOp>
1939 inline void
1940 Tree<RootNodeType>::combine(Tree& other, const CombineOp& op, bool prune)
1941 {
1943  this->combineExtended(other, extendedOp, prune);
1944 }
1945 #endif
1946 
1947 
1948 template<typename RootNodeType>
1949 template<typename ExtendedCombineOp>
1950 inline void
1951 Tree<RootNodeType>::combineExtended(Tree& other, ExtendedCombineOp& op, bool prune)
1952 {
1953  this->clearAllAccessors();
1954  mRoot.combine(other.root(), op, prune);
1955 }
1956 
1957 
1960 #ifndef _MSC_VER
1961 template<typename RootNodeType>
1962 template<typename ExtendedCombineOp>
1963 inline void
1964 Tree<RootNodeType>::combineExtended(Tree& other, const ExtendedCombineOp& op, bool prune)
1965 {
1966  this->clearAllAccessors();
1967  mRoot.template combine<const ExtendedCombineOp>(other.mRoot, op, prune);
1968 }
1969 #endif
1970 
1971 
1972 template<typename RootNodeType>
1973 template<typename CombineOp, typename OtherTreeType>
1974 inline void
1975 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, CombineOp& op, bool prune)
1976 {
1978  this->combine2Extended(a, b, extendedOp, prune);
1979 }
1980 
1981 
1984 #ifndef _MSC_VER
1985 template<typename RootNodeType>
1986 template<typename CombineOp, typename OtherTreeType>
1987 inline void
1988 Tree<RootNodeType>::combine2(const Tree& a, const OtherTreeType& b, const CombineOp& op, bool prune)
1989 {
1991  this->combine2Extended(a, b, extendedOp, prune);
1992 }
1993 #endif
1994 
1995 
1996 template<typename RootNodeType>
1997 template<typename ExtendedCombineOp, typename OtherTreeType>
1998 inline void
1999 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
2000  ExtendedCombineOp& op, bool prune)
2001 {
2002  this->clearAllAccessors();
2003  mRoot.combine2(a.root(), b.root(), op, prune);
2004 }
2005 
2006 
2010 #ifndef _MSC_VER
2011 template<typename RootNodeType>
2012 template<typename ExtendedCombineOp, typename OtherTreeType>
2013 inline void
2014 Tree<RootNodeType>::combine2Extended(const Tree& a, const OtherTreeType& b,
2015  const ExtendedCombineOp& op, bool prune)
2016 {
2017  this->clearAllAccessors();
2018  mRoot.template combine2<const ExtendedCombineOp>(a.root(), b.root(), op, prune);
2019 }
2020 #endif
2021 
2022 
2024 
2025 
2026 template<typename RootNodeType>
2027 template<typename VisitorOp>
2028 inline void
2030 {
2031  this->clearAllAccessors();
2032  mRoot.template visit<VisitorOp>(op);
2033 }
2034 
2035 
2036 template<typename RootNodeType>
2037 template<typename VisitorOp>
2038 inline void
2039 Tree<RootNodeType>::visit(VisitorOp& op) const
2040 {
2041  mRoot.template visit<VisitorOp>(op);
2042 }
2043 
2044 
2047 template<typename RootNodeType>
2048 template<typename VisitorOp>
2049 inline void
2050 Tree<RootNodeType>::visit(const VisitorOp& op)
2051 {
2052  this->clearAllAccessors();
2053  mRoot.template visit<const VisitorOp>(op);
2054 }
2055 
2056 
2059 template<typename RootNodeType>
2060 template<typename VisitorOp>
2061 inline void
2062 Tree<RootNodeType>::visit(const VisitorOp& op) const
2063 {
2064  mRoot.template visit<const VisitorOp>(op);
2065 }
2066 
2067 
2069 
2070 
2071 template<typename RootNodeType>
2072 template<typename OtherTreeType, typename VisitorOp>
2073 inline void
2074 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op)
2075 {
2076  this->clearAllAccessors();
2077  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2078  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
2079 }
2080 
2081 
2082 template<typename RootNodeType>
2083 template<typename OtherTreeType, typename VisitorOp>
2084 inline void
2085 Tree<RootNodeType>::visit2(OtherTreeType& other, VisitorOp& op) const
2086 {
2087  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2088  mRoot.template visit2<OtherRootNodeType, VisitorOp>(other.root(), op);
2089 }
2090 
2091 
2094 template<typename RootNodeType>
2095 template<typename OtherTreeType, typename VisitorOp>
2096 inline void
2097 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op)
2098 {
2099  this->clearAllAccessors();
2100  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2101  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2102 }
2103 
2104 
2107 template<typename RootNodeType>
2108 template<typename OtherTreeType, typename VisitorOp>
2109 inline void
2110 Tree<RootNodeType>::visit2(OtherTreeType& other, const VisitorOp& op) const
2111 {
2112  using OtherRootNodeType = typename OtherTreeType::RootNodeType;
2113  mRoot.template visit2<OtherRootNodeType, const VisitorOp>(other.root(), op);
2114 }
2115 
2116 
2118 
2119 
2120 template<typename RootNodeType>
2121 inline const Name&
2123 {
2124  if (sTreeTypeName == nullptr) {
2125  std::vector<Index> dims;
2126  Tree::getNodeLog2Dims(dims);
2127  std::ostringstream ostr;
2128  ostr << "Tree_" << typeNameAsString<BuildType>();
2129  for (size_t i = 1, N = dims.size(); i < N; ++i) { // start from 1 to skip the RootNode
2130  ostr << "_" << dims[i];
2131  }
2132  Name* s = new Name(ostr.str());
2133  if (sTreeTypeName.compare_and_swap(s, nullptr) != nullptr) delete s;
2134  }
2135  return *sTreeTypeName;
2136 }
2137 
2138 
2139 template<typename RootNodeType>
2140 template<typename OtherRootNodeType>
2141 inline bool
2143 {
2144  return mRoot.hasSameTopology(other.root());
2145 }
2146 
2147 
2148 template<typename RootNodeType>
2149 Index64
2151 {
2152  Coord dim(0, 0, 0);
2153  this->evalActiveVoxelDim(dim);
2154  const Index64
2155  totalVoxels = dim.x() * dim.y() * dim.z(),
2156  activeVoxels = this->activeVoxelCount();
2157  assert(totalVoxels >= activeVoxels);
2158  return totalVoxels - activeVoxels;
2159 }
2160 
2161 
2162 template<typename RootNodeType>
2163 inline bool
2165 {
2166  bbox.reset(); // default invalid bbox
2167 
2168  if (this->empty()) return false; // empty
2169 
2170  mRoot.evalActiveBoundingBox(bbox, false);
2171 
2172  return true;// not empty
2173 }
2174 
2175 template<typename RootNodeType>
2176 inline bool
2178 {
2179  bbox.reset(); // default invalid bbox
2180 
2181  if (this->empty()) return false; // empty
2182 
2183  mRoot.evalActiveBoundingBox(bbox, true);
2184 
2185  return true;// not empty
2186 }
2187 
2188 
2189 template<typename RootNodeType>
2190 inline bool
2192 {
2193  CoordBBox bbox;
2194  bool notEmpty = this->evalActiveVoxelBoundingBox(bbox);
2195  dim = bbox.extents();
2196  return notEmpty;
2197 }
2198 
2199 
2200 template<typename RootNodeType>
2201 inline bool
2203 {
2204  CoordBBox bbox;
2205  bool notEmpty = this->evalLeafBoundingBox(bbox);
2206  dim = bbox.extents();
2207  return notEmpty;
2208 }
2209 
2210 
2211 template<typename RootNodeType>
2212 inline void
2214 {
2216  minVal = maxVal = zeroVal<ValueType>();
2217  if (ValueOnCIter iter = this->cbeginValueOn()) {
2218  minVal = maxVal = *iter;
2219  for (++iter; iter; ++iter) {
2220  const ValueType& val = *iter;
2221  if (val < minVal) minVal = val;
2222  if (val > maxVal) maxVal = val;
2223  }
2224  }
2225 }
2226 
2227 
2228 template<typename RootNodeType>
2229 inline void
2230 Tree<RootNodeType>::getNodeLog2Dims(std::vector<Index>& dims)
2231 {
2232  dims.clear();
2233  RootNodeType::getNodeLog2Dims(dims);
2234 }
2235 
2236 
2237 template<typename RootNodeType>
2238 inline void
2239 Tree<RootNodeType>::print(std::ostream& os, int verboseLevel) const
2240 {
2241  if (verboseLevel <= 0) return;
2242 
2244  struct OnExit {
2245  std::ostream& os;
2246  std::streamsize savedPrecision;
2247  OnExit(std::ostream& _os): os(_os), savedPrecision(os.precision()) {}
2248  ~OnExit() { os.precision(savedPrecision); }
2249  };
2250  OnExit restorePrecision(os);
2251 
2252  std::vector<Index> dims;
2253  Tree::getNodeLog2Dims(dims);
2254 
2255  os << "Information about Tree:\n"
2256  << " Type: " << this->type() << "\n";
2257 
2258  os << " Configuration:\n";
2259 
2260  if (verboseLevel <= 1) {
2261  // Print node types and sizes.
2262  os << " Root(" << mRoot.getTableSize() << ")";
2263  if (dims.size() > 1) {
2264  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2265  os << ", Internal(" << (1 << dims[i]) << "^3)";
2266  }
2267  os << ", Leaf(" << (1 << *dims.rbegin()) << "^3)\n";
2268  }
2269  os << " Background value: " << mRoot.background() << "\n";
2270  return;
2271  }
2272 
2273  // The following is tree information that is expensive to extract.
2274 
2275  ValueType minVal = zeroVal<ValueType>(), maxVal = zeroVal<ValueType>();
2276  if (verboseLevel > 3) {
2277  // This forces loading of all non-resident nodes.
2278  this->evalMinMax(minVal, maxVal);
2279  }
2280 
2281  std::vector<Index64> nodeCount(dims.size());
2282  for (NodeCIter it = cbeginNode(); it; ++it) ++(nodeCount[it.getDepth()]);
2283 
2284  Index64 totalNodeCount = 0;
2285  for (size_t i = 0; i < nodeCount.size(); ++i) totalNodeCount += nodeCount[i];
2286 
2287  // Print node types, counts and sizes.
2288  os << " Root(1 x " << mRoot.getTableSize() << ")";
2289  if (dims.size() > 1) {
2290  for (size_t i = 1, N = dims.size() - 1; i < N; ++i) {
2291  os << ", Internal(" << util::formattedInt(nodeCount[i]);
2292  os << " x " << (1 << dims[i]) << "^3)";
2293  }
2294  os << ", Leaf(" << util::formattedInt(*nodeCount.rbegin());
2295  os << " x " << (1 << *dims.rbegin()) << "^3)\n";
2296  }
2297  os << " Background value: " << mRoot.background() << "\n";
2298 
2299  // Statistics of topology and values
2300 
2301  if (verboseLevel > 3) {
2302  os << " Min value: " << minVal << "\n";
2303  os << " Max value: " << maxVal << "\n";
2304  }
2305 
2306  const Index64
2307  leafCount = *nodeCount.rbegin(),
2308  numActiveVoxels = this->activeVoxelCount(),
2309  numActiveLeafVoxels = this->activeLeafVoxelCount(),
2310  numActiveTiles = this->activeTileCount();
2311 
2312  os << " Number of active voxels: " << util::formattedInt(numActiveVoxels) << "\n";
2313  os << " Number of active tiles: " << util::formattedInt(numActiveTiles) << "\n";
2314 
2315  Coord dim(0, 0, 0);
2316  Index64 totalVoxels = 0;
2317  if (numActiveVoxels) { // nonempty
2318  CoordBBox bbox;
2319  this->evalActiveVoxelBoundingBox(bbox);
2320  dim = bbox.extents();
2321  totalVoxels = dim.x() * uint64_t(dim.y()) * dim.z();
2322 
2323  os << " Bounding box of active voxels: " << bbox << "\n";
2324  os << " Dimensions of active voxels: "
2325  << dim[0] << " x " << dim[1] << " x " << dim[2] << "\n";
2326 
2327  const double activeRatio = (100.0 * double(numActiveVoxels)) / double(totalVoxels);
2328  os << " Percentage of active voxels: " << std::setprecision(3) << activeRatio << "%\n";
2329 
2330  if (leafCount > 0) {
2331  const double fillRatio = (100.0 * double(numActiveLeafVoxels))
2332  / (double(leafCount) * double(LeafNodeType::NUM_VOXELS));
2333  os << " Average leaf node fill ratio: " << fillRatio << "%\n";
2334  }
2335 
2336 #if OPENVDB_ABI_VERSION_NUMBER >= 3
2337  if (verboseLevel > 2) {
2338  Index64 sum = 0;// count the number of unallocated leaf nodes
2339  for (auto it = this->cbeginLeaf(); it; ++it) if (!it->isAllocated()) ++sum;
2340  os << " Number of unallocated nodes: "
2341  << util::formattedInt(sum) << " ("
2342  << (100.0 * double(sum) / double(totalNodeCount)) << "%)\n";
2343  }
2344 #endif
2345  } else {
2346  os << " Tree is empty!\n";
2347  }
2348  os << std::flush;
2349 
2350  if (verboseLevel == 2) return;
2351 
2352  // Memory footprint in bytes
2353  const Index64
2354  actualMem = this->memUsage(),
2355  denseMem = sizeof(ValueType) * totalVoxels,
2356  voxelsMem = sizeof(ValueType) * numActiveLeafVoxels;
2358 
2359  os << "Memory footprint:\n";
2360  util::printBytes(os, actualMem, " Actual: ");
2361  util::printBytes(os, voxelsMem, " Active leaf voxels: ");
2362 
2363  if (numActiveVoxels) {
2364  util::printBytes(os, denseMem, " Dense equivalent: ");
2365  os << " Actual footprint is " << (100.0 * double(actualMem) / double(denseMem))
2366  << "% of an equivalent dense volume\n";
2367  os << " Leaf voxel footprint is " << (100.0 * double(voxelsMem) / double(actualMem))
2368  << "% of actual footprint\n";
2369  }
2370 }
2371 
2372 } // namespace tree
2373 } // namespace OPENVDB_VERSION_NAME
2374 } // namespace openvdb
2375 
2376 #endif // OPENVDB_TREE_TREE_HAS_BEEN_INCLUDED
2377 
2378 // Copyright (c) DreamWorks Animation LLC
2379 // All rights reserved. This software is distributed under the
2380 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
ConstAccessorRegistry mConstAccessorRegistry
Definition: Tree.h:1244
void visitActiveBBox(BBoxOp &op) const
Use sparse traversal to call the given functor with bounding box information for all active tiles and...
Definition: Tree.h:1000
void modifyValueAndActiveState(const Coord &xyz, const ModifyOp &op)
Apply a functor to the voxel at the given coordinates.
Definition: Tree.h:1688
#define OPENVDB_API
Helper macros for defining library symbol visibility.
Definition: Platform.h:288
int getValueDepth(const Coord &xyz) const
Return the tree depth (0 = root) at which the value of voxel (x, y, z) resides.
Definition: Tree.h:1607
static bool isRegisteredType(const Name &typeName)
Return true if the given type is known by the metadata type registry.
bool empty() const
Return true if this tree contains no nodes other than the root node and no tiles other than backgroun...
Definition: Tree.h:646
static TreeT::NodeCIter begin(const TreeT &tree)
Definition: Tree.h:1369
static TreeT::ValueOffIter begin(TreeT &tree)
Definition: Tree.h:1389
bool operator==(const Tree &) const
Definition: Tree.h:302
Utility routines to output nicely-formatted numeric values.
static tbb::atomic< const Name * > sTreeTypeName
Definition: Tree.h:1246
bool isValueOff(const Coord &xyz) const
Return true if the value at the given coordinates is inactive.
Definition: Tree.h:474
Coord extents() const
Definition: Coord.h:409
const AValueType & a() const
Get the A input value.
Definition: Types.h:657
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
LeafNodeType * probeLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:1734
void setValueOnly(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates but don&#39;t change its active state.
Definition: Tree.h:1646
void setActiveState(const Coord &xyz, bool on)
Set the active state of the voxel at the given coordinates but don&#39;t change its value.
Definition: Tree.h:1631
Index64 memUsage() const override
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:389
Int32 z() const
Definition: Coord.h:160
ValueAllCIter cbeginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1195
Tree4<T, N1, N2, N3>::Type is the type of a four-level tree (Root, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2 and N3, respectively.
Definition: Tree.h:1268
RootNodeType::ChildOnCIter cbeginRootChildren() const
Return an iterator over children of the root node.
Definition: Tree.h:1139
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
static TreeT::RootNodeType::ChildAllIter begin(TreeT &tree)
Definition: Tree.h:1353
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
Index32 leafCount() const override
Return the number of leaf nodes.
Definition: Tree.h:368
void writeBuffers(std::ostream &, bool saveFloatAsHalf=false) const override
Write out all data buffers for this tree.
Definition: Tree.h:1480
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:52
RootNodeType::ChildOffIter beginRootTiles()
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:1147
Base class for tree-traversal iterators over tile and voxel values.
Definition: TreeIterator.h:648
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:361
Tree(const OtherTreeType &other, const ValueType &inactiveValue, const ValueType &activeValue, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:259
void fill(const CoordBBox &bbox, const ValueType &value, bool active=true)
Set all voxels within a given axis-aligned box to a constant value.
Definition: Tree.h:504
ValueConverter<T>::Type is the type of a tree having the same hierarchy as this tree but a different ...
Definition: Tree.h:223
typename RootNodeType::BuildType BuildType
Definition: Tree.h:211
DeallocateNodes(std::vector< NodeType *> &nodes)
Definition: Tree.h:1229
Tree(const Tree &other)
Deep copy constructor.
Definition: Tree.h:233
Index32 Index
Definition: Types.h:61
virtual Index64 memUsage() const
Return the total amount of memory in bytes occupied by this tree.
Definition: Tree.h:158
RootNodeType::ChildAllCIter cbeginRootDense() const
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:1153
std::shared_ptr< T > SharedPtr
Definition: Types.h:139
static TreeT::ValueOnCIter begin(const TreeT &tree)
Definition: Tree.h:1385
Index64 activeVoxelCount() const override
Return the total number of active voxels.
Definition: Tree.h:376
virtual Metadata::Ptr getBackgroundValue() const
Return this tree&#39;s background value wrapped as metadata.
Definition: Tree.h:87
void attachAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:664
Index32 nonLeafCount() const override
Return the number of non-leaf nodes.
Definition: Tree.h:370
void getNodes(ArrayT &array) const
Adds all nodes of a certain type to a container with the following API:
Definition: Tree.h:606
NodeCIter cbeginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1174
CombineOpAdapter(CombineOp &_op)
Definition: Tree.h:1914
static TreeT::ValueAllIter begin(TreeT &tree)
Definition: Tree.h:1397
bool hasActiveTiles() const
Return true if this tree has any active tiles.
Definition: Tree.h:476
const LeafNodeType * probeLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:579
const RootNodeType & root() const
Return this tree&#39;s root node.
Definition: Tree.h:308
LeafNodeType * touchLeaf(const Coord &xyz)
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, create one that preserves the values and active states of all voxels.
Definition: Tree.h:1726
NodeType **const mNodes
Definition: Tree.h:1236
bool isValueOn(const Coord &xyz) const
Return true if the value at the given coordinates is active.
Definition: Tree.h:472
Int32 x() const
Definition: Coord.h:158
void reset()
Definition: Coord.h:354
Tag dispatch class that distinguishes topology copy constructors from deep copy constructors.
Definition: Types.h:750
RootNodeType::ChildOnIter beginRootChildren()
Return an iterator over children of the root node.
Definition: Tree.h:1140
MergePolicy
Definition: Types.h:555
Tree(const OtherTreeType &other, const ValueType &background, TopologyCopy)
Topology copy constructor from a tree of a different type.
Definition: Tree.h:280
Definition: Types.h:556
static TreeT::ValueOnIter begin(TreeT &tree)
Definition: Tree.h:1381
void addTile(Index level, const Coord &xyz, const ValueType &value, bool active)
Add a tile containing voxel (x, y, z) at the specified tree level, creating a new branch if necessary...
Definition: Tree.h:1707
void operator()(CombineArgs< AValueT, BValueT > &args) const
Definition: Tree.h:1916
Internal table nodes for OpenVDB trees.
Name valueType() const override
Return the name of the type of a voxel&#39;s value (e.g., "float" or "vec3d")
Definition: Tree.h:295
static TreeT::RootNodeType::ChildOffIter begin(TreeT &tree)
Definition: Tree.h:1341
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
ValueAllCIter beginValueAll() const
Return an iterator over all values (tile and voxel) across all nodes.
Definition: Tree.h:1194
std::string Name
Definition: Name.h:44
void addLeaf(LeafNodeType *leaf)
Add the given leaf node to this tree, creating a new branch if necessary. If a leaf node with the sam...
Definition: Tree.h:544
bool probeValue(const Coord &xyz, ValueType &value) const
Get the value of the voxel at the given coordinates.
Definition: Tree.h:1696
#define OPENVDB_LOG_WARN(message)
Log a warning message of the form &#39;someVar << "some text" << ...&#39;.
Definition: logging.h:280
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:275
ValueOnCIter cbeginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1201
const ValueType & background() const
Return this tree&#39;s background value.
Definition: Tree.h:688
Index64 inactiveLeafVoxelCount() const override
Return the number of inactive voxels stored in leaf nodes.
Definition: Tree.h:374
TreeBase::Ptr copy() const override
Return a pointer to a deep copy of this tree.
Definition: Tree.h:292
RootNodeType::ChildOffCIter cbeginRootTiles() const
Return an iterator over non-child entries of the root node&#39;s table.
Definition: Tree.h:1146
Tree5<T, N1, N2, N3, N4>::Type is the type of a five-level tree (Root, Internal, Internal, Internal, Leaf) with value type T and internal and leaf node log dimensions N1, N2, N3 and N4, respectively.
Definition: Tree.h:1277
tree::TreeBase TreeBase
Definition: Grid.h:53
typename RootNodeType::ValueType ValueType
Definition: Tree.h:210
void stealNodes(ArrayT &array)
Steals all nodes of a certain type from the tree and adds them to a container with the following API:...
Definition: Tree.h:633
ValueOffCIter beginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1206
const LeafNodeType * probeConstLeaf(const Coord &xyz) const
Return a pointer to the leaf node that contains voxel (x, y, z). If no such node exists, return nullptr.
Definition: Tree.h:1742
CombineOp & op
Definition: Tree.h:1920
Definition: Tree.h:203
static TreeT::ValueOffCIter begin(const TreeT &tree)
Definition: Tree.h:1393
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: Tree.h:1231
Definition: Exceptions.h:40
This base class for ValueAccessors manages registration of an accessor with a tree so that the tree c...
Definition: ValueAccessor.h:122
Templated metadata class to hold specific types.
Definition: Metadata.h:171
void getIndexRange(CoordBBox &bbox) const override
Min and max are both inclusive.
Definition: Tree.h:691
tbb::concurrent_hash_map< ValueAccessorBase< const Tree, true > *, bool > ConstAccessorRegistry
Definition: Tree.h:1220
NodeCIter beginNode() const
Return an iterator over all nodes in this tree.
Definition: Tree.h:1173
void modifyValue(const Coord &xyz, const ModifyOp &op)
Apply a functor to the value of the voxel at the given coordinates and mark the voxel as active...
Definition: Tree.h:1679
void setValue(const Coord &xyz, const ValueType &value)
Set the value of the voxel at the given coordinates and mark the voxel as active. ...
Definition: Tree.h:1639
OPENVDB_API int printBytes(std::ostream &os, uint64_t bytes, const std::string &head="", const std::string &tail="\, bool exact=false, int width=8, int precision=3)
uint64_t Index64
Definition: Types.h:60
static TreeT::RootNodeType::ChildOnIter begin(TreeT &tree)
Definition: Tree.h:1329
virtual void readTopology(std::istream &, bool saveFloatAsHalf=false)
Read the tree topology from a stream.
Definition: Tree.h:1287
void clearAllAccessors()
Clear all registered accessors.
Definition: Tree.h:1547
const Name & type() const override
Return the name of this type of tree.
Definition: Tree.h:300
Base class for typed trees.
Definition: Tree.h:62
static TreeT::ValueAllCIter begin(const TreeT &tree)
Definition: Tree.h:1401
ValueOffCIter cbeginValueOff() const
Return an iterator over inactive values (tile and voxel) across all nodes.
Definition: Tree.h:1207
static TreeT::RootNodeType::ChildOffCIter begin(const TreeT &tree)
Definition: Tree.h:1347
This struct collects both input and output arguments to "grid combiner" functors used with the tree::...
Definition: Types.h:617
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
static Metadata::Ptr createMetadata(const Name &typeName)
Create new metadata of the given type.
RootNodeType & root()
Return this tree&#39;s root node.
Definition: Tree.h:307
Int32 y() const
Definition: Coord.h:159
Tree()
Definition: Tree.h:228
RootNodeType mRoot
Definition: Tree.h:1242
void releaseAccessor(ValueAccessorBase< const Tree, false > &) const
Dummy implementations.
Definition: Tree.h:676
void prune(const ValueType &tolerance=zeroVal< ValueType >())
Reduce the memory footprint of this tree by replacing with tiles any nodes whose values are all the s...
Definition: Tree.h:533
typename RootNodeType::LeafNodeType LeafNodeType
Definition: Tree.h:212
FormattedInt< IntT > formattedInt(IntT n)
Definition: Formats.h:145
GridType::Ptr clip(const GridType &grid, const BBoxd &bbox, bool keepInterior=true)
Clip the given grid against a world-space bounding box and return a new grid containing the result...
Definition: Clip.h:379
Helper class to adapt a three-argument (a, b, result) CombineOp functor into a single-argument functo...
Definition: Tree.h:1912
AccessorRegistry mAccessorRegistry
Definition: Tree.h:1243
The root node of an OpenVDB tree.
LeafCIter beginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1180
bool operator!=(const Tree &) const
Definition: Tree.h:303
~Tree() override
Definition: Tree.h:289
Definition: Types.h:557
tbb::concurrent_hash_map< ValueAccessorBase< Tree, true > *, bool > AccessorRegistry
Definition: Tree.h:1219
Index64 activeLeafVoxelCount() const override
Return the number of active voxels stored in leaf nodes.
Definition: Tree.h:372
Tree(const ValueType &background)
Empty tree constructor.
Definition: Tree.h:287
LeafCIter cbeginLeaf() const
Return an iterator over all leaf nodes in this tree.
Definition: Tree.h:1181
static TreeT::NodeIter begin(TreeT &tree)
Definition: Tree.h:1365
Base class for tree-traversal iterators over all nodes.
Definition: TreeIterator.h:967
Definition: Exceptions.h:88
SharedPtr< Metadata > Ptr
Definition: Metadata.h:53
void stealNodes(ArrayT &array, const ValueType &value, bool state)
Definition: Tree.h:635
SharedPtr< TreeBase > Ptr
Definition: Tree.h:65
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
virtual void print(std::ostream &os=std::cout, int verboseLevel=1) const
Print statistics, memory usage and other information about this tree.
Definition: Tree.h:1304
Tree(const Tree< OtherRootType > &other)
Value conversion deep copy constructor.
Definition: Tree.h:244
Index treeDepth() const override
Return the depth of this tree.
Definition: Tree.h:366
SharedPtr< const TreeBase > ConstPtr
Definition: Tree.h:66
_RootNodeType RootNodeType
Definition: Tree.h:209
static TreeT::RootNodeType::ChildOnCIter begin(const TreeT &tree)
Definition: Tree.h:1335
bool hasSameTopology(const Tree< OtherRootNodeType > &other) const
Return true if the given tree has the same node and active value topology as this tree...
Definition: Tree.h:2142
void setValueOn(const Coord &xyz)
Mark the voxel at the given coordinates as active but don&#39;t change its value.
Definition: Tree.h:1662
static TreeT::LeafCIter begin(const TreeT &tree)
Definition: Tree.h:1377
TreeIterTraits provides, for all tree iterators, a begin(tree) function that returns an iterator over...
Definition: Tree.h:1326
const ValueType & getValue(const Coord &xyz) const
Return the value of the voxel at the given coordinates.
Definition: Tree.h:1590
Base class for tree-traversal iterators over all leaf nodes (but not leaf voxels) ...
Definition: TreeIterator.h:1218
ValueOnCIter beginValueOn() const
Return an iterator over active values (tile and voxel) across all nodes.
Definition: Tree.h:1200
const BValueType & b() const
Get the B input value.
Definition: Types.h:659
uint32_t Index32
Definition: Types.h:59
const AValueType & result() const
Get the output value.
Definition: Types.h:662
static TreeT::LeafIter begin(TreeT &tree)
Definition: Tree.h:1373
Tree3<T, N1, N2>::Type is the type of a three-level tree (Root, Internal, Leaf) with value type T and...
Definition: Tree.h:1258
virtual void writeTopology(std::ostream &, bool saveFloatAsHalf=false) const
Write the tree topology to a stream.
Definition: Tree.h:1296
void clear()
Remove all tiles from this tree and all nodes other than the root node.
Definition: Tree.h:1488
RootNodeType::ChildAllIter beginRootDense()
Return an iterator over all entries of the root node&#39;s table.
Definition: Tree.h:1154
static TreeT::RootNodeType::ChildAllCIter begin(const TreeT &tree)
Definition: Tree.h:1359
void setValueOff(const Coord &xyz)
Mark the voxel at the given coordinates as inactive but don&#39;t change its value.
Definition: Tree.h:1615