OpenVDB  10.0.1
Count.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 //
4 /// @file Count.h
5 ///
6 /// @brief Functions to count tiles, nodes or voxels in a grid
7 ///
8 /// @author Dan Bailey
9 ///
10 
11 #ifndef OPENVDB_TOOLS_COUNT_HAS_BEEN_INCLUDED
12 #define OPENVDB_TOOLS_COUNT_HAS_BEEN_INCLUDED
13 
14 #include <openvdb/version.h>
15 #include <openvdb/math/Stats.h>
18 
19 namespace openvdb {
21 namespace OPENVDB_VERSION_NAME {
22 namespace tools {
23 
24 
25 /// @brief Return the total number of active voxels in the tree.
26 template <typename TreeT>
27 Index64 countActiveVoxels(const TreeT& tree, bool threaded = true);
28 
29 
30 /// @brief Return the total number of active voxels in the tree that intersects
31 /// a bounding box.
32 template <typename TreeT>
33 Index64 countActiveVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded = true);
34 
35 
36 /// @brief Return the total number of active voxels stored in leaf nodes.
37 template <typename TreeT>
38 Index64 countActiveLeafVoxels(const TreeT& tree, bool threaded = true);
39 
40 
41 /// @brief Return the total number of active voxels stored in leaf nodes that intersects
42 /// a bounding box.
43 template <typename TreeT>
44 Index64 countActiveLeafVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded = true);
45 
46 
47 /// @brief Return the total number of inactive voxels in the tree.
48 template <typename TreeT>
49 Index64 countInactiveVoxels(const TreeT& tree, bool threaded = true);
50 
51 
52 /// @brief Return the total number of inactive voxels stored in leaf nodes.
53 template <typename TreeT>
54 Index64 countInactiveLeafVoxels(const TreeT& tree, bool threaded = true);
55 
56 
57 /// @brief Return the total number of active tiles in the tree.
58 template <typename TreeT>
59 Index64 countActiveTiles(const TreeT& tree, bool threaded = true);
60 
61 
62 /// @brief Return the total amount of memory in bytes occupied by this tree.
63 /// @details This method returns the total in-core memory usage which can be
64 /// different to the maximum possible memory usage for trees which have not
65 /// been fully deserialized (via delay-loading). Thus, this is the current
66 /// true memory consumption.
67 template <typename TreeT>
68 Index64 memUsage(const TreeT& tree, bool threaded = true);
69 
70 
71 /// @brief Return the deserialized memory usage of this tree. This is not
72 /// necessarily equal to the current memory usage (returned by tools::memUsage)
73 /// if delay-loading is enabled. See File::open.
74 template <typename TreeT>
75 Index64 memUsageIfLoaded(const TreeT& tree, bool threaded = true);
76 
77 
78 /// @brief Return the minimum and maximum active values in this tree.
79 /// @note Returns zeroVal<ValueType> for empty trees.
80 template <typename TreeT>
81 math::MinMax<typename TreeT::ValueType> minMax(const TreeT& tree, bool threaded = true);
82 
83 
84 ////////////////////////////////////////
85 
86 /// @cond OPENVDB_DOCS_INTERNAL
87 
88 namespace count_internal {
89 
90 /// @brief A DynamicNodeManager operator to count active voxels in a tree
91 template<typename TreeType>
92 struct ActiveVoxelCountOp
93 {
94  using LeafT = typename TreeType::LeafNodeType;
95 
96  ActiveVoxelCountOp() = default;
97  ActiveVoxelCountOp(const ActiveVoxelCountOp&, tbb::split) { }
98 
99  // accumulate all voxels in active tile children
100  template<typename NodeT>
101  bool operator()(const NodeT& node, size_t)
102  {
103  for (auto iter = node.cbeginValueOn(); iter; ++iter) {
104  count += NodeT::ChildNodeType::NUM_VOXELS;
105  }
106  return true;
107  }
108 
109  // accumulate all active voxels in the leaf
110  bool operator()(const LeafT& leaf, size_t)
111  {
112  count += leaf.onVoxelCount();
113  return false;
114  }
115 
116  void join(const ActiveVoxelCountOp& other)
117  {
118  count += other.count;
119  }
120 
121  openvdb::Index64 count{0};
122 }; // struct ActiveVoxelCountOp
123 
124 /// @brief A DynamicNodeManager operator to count active voxels in a tree
125 /// that fall within a provided bounding box
126 template<typename TreeType>
127 struct ActiveVoxelCountBBoxOp
128 {
129  using LeafT = typename TreeType::LeafNodeType;
130 
131  explicit ActiveVoxelCountBBoxOp(const CoordBBox& bbox)
132  : mBBox(bbox) { }
133  ActiveVoxelCountBBoxOp(const ActiveVoxelCountBBoxOp& other, tbb::split)
134  : mBBox(other.mBBox) { }
135 
136  // accumulate all voxels in active tile children bounded by the bbox
137  template<typename NodeT>
138  bool operator()(const NodeT& node, size_t)
139  {
140  if (!mBBox.hasOverlap(node.getNodeBoundingBox())) return false;
141 
142  // count any overlapping regions in active tiles
143  for (auto iter = node.cbeginValueOn(); iter; ++iter) {
144  CoordBBox bbox(CoordBBox::createCube(iter.getCoord(), NodeT::ChildNodeType::DIM));
145 
146  if (!bbox.hasOverlap(mBBox)) {
147  // box is completely outside the active tile
148  continue;
149  } else if (bbox.isInside(mBBox)) {
150  // bbox is completely inside the active tile
151  count += mBBox.volume();
152  } else if (mBBox.isInside(bbox)) {
153  // active tile is completely inside bbox
154  count += bbox.volume();
155  } else {
156  // partial overlap between tile and bbox
157  bbox.intersect(mBBox);
158  count += bbox.volume();
159  }
160  }
161 
162  // return true if any child nodes overlap with the bounding box
163  for (auto iter = node.cbeginChildOn(); iter; ++iter) {
164  if (mBBox.hasOverlap(iter->getNodeBoundingBox())) return true;
165  }
166 
167  // otherwise return false to prevent recursion along this branch
168  return false;
169  }
170 
171  // accumulate all active voxels in the leaf bounded by the bbox
172  inline bool operator()(const LeafT& leaf, size_t)
173  {
174  // note: the true/false return value does nothing
175 
176  CoordBBox bbox = leaf.getNodeBoundingBox();
177 
178  if (mBBox.isInside(bbox)) {
179  // leaf node is completely inside bbox
180  count += leaf.onVoxelCount();
181  } else if (!bbox.hasOverlap(mBBox)) {
182  // bbox is completely outside the leaf node
183  return false;
184  } else if (leaf.isDense()) {
185  // partial overlap between dense leaf node and bbox
186  bbox.intersect(mBBox);
187  count += bbox.volume();
188  } else {
189  // partial overlap between sparse leaf node and bbox
190  for (auto i = leaf.cbeginValueOn(); i; ++i) {
191  if (mBBox.isInside(i.getCoord())) ++count;
192  }
193  }
194  return false;
195  }
196 
197  void join(const ActiveVoxelCountBBoxOp& other)
198  {
199  count += other.count;
200  }
201 
202  openvdb::Index64 count{0};
203 private:
204  CoordBBox mBBox;
205 }; // struct ActiveVoxelCountBBoxOp
206 
207 /// @brief A DynamicNodeManager operator to count inactive voxels in a tree
208 template<typename TreeType>
209 struct InactiveVoxelCountOp
210 {
211  using RootT = typename TreeType::RootNodeType;
212  using LeafT = typename TreeType::LeafNodeType;
213 
214  InactiveVoxelCountOp() = default;
215  InactiveVoxelCountOp(const InactiveVoxelCountOp&, tbb::split) { }
216 
217  // accumulate all inactive voxels in the root node
218  bool operator()(const RootT& root, size_t)
219  {
220  for (auto iter = root.cbeginValueOff(); iter; ++iter) {
221  // background tiles are not considered to contain inactive voxels
222  if (!math::isApproxEqual(*iter, root.background())) {
223  count += RootT::ChildNodeType::NUM_VOXELS;
224  }
225  }
226  return true;
227  }
228 
229  // accumulate all voxels in inactive tile children
230  template<typename NodeT>
231  bool operator()(const NodeT& node, size_t)
232  {
233  for (auto iter = node.cbeginValueOff(); iter; ++iter) {
234  if (node.isChildMaskOff(iter.pos())) {
235  count += NodeT::ChildNodeType::NUM_VOXELS;
236  }
237  }
238  return true;
239  }
240 
241  // accumulate all inactive voxels in the leaf
242  bool operator()(const LeafT& leaf, size_t)
243  {
244  count += leaf.offVoxelCount();
245  return false;
246  }
247 
248  void join(const InactiveVoxelCountOp& other)
249  {
250  count += other.count;
251  }
252 
253  openvdb::Index64 count{0};
254 }; // struct InactiveVoxelCountOp
255 
256 /// @brief A DynamicNodeManager operator to count active tiles in a tree
257 template<typename TreeType>
258 struct ActiveTileCountOp
259 {
260  using RootT = typename TreeType::RootNodeType;
261  using LeafT = typename TreeType::LeafNodeType;
262 
263  ActiveTileCountOp() = default;
264  ActiveTileCountOp(const ActiveTileCountOp&, tbb::split) { }
265 
266  // accumulate all active tiles in root node
267  bool operator()(const RootT& root, size_t)
268  {
269  for (auto iter = root.cbeginValueOn(); iter; ++iter) count++;
270  return true;
271  }
272 
273  // accumulate all active tiles in internal node
274  template<typename NodeT>
275  bool operator()(const NodeT& node, size_t)
276  {
277  count += node.getValueMask().countOn();
278  return true;
279  }
280 
281  // do nothing (leaf nodes cannot contain tiles)
282  bool operator()(const LeafT&, size_t)
283  {
284  return false;
285  }
286 
287  void join(const ActiveTileCountOp& other)
288  {
289  count += other.count;
290  }
291 
292  openvdb::Index64 count{0};
293 }; // struct ActiveTileCountOp
294 
295 /// @brief A DynamicNodeManager operator to sum the number of bytes of memory used
296 template<typename TreeType>
297 struct MemUsageOp
298 {
299  using RootT = typename TreeType::RootNodeType;
300  using LeafT = typename TreeType::LeafNodeType;
301 
302  MemUsageOp(const bool inCoreOnly) : mInCoreOnly(inCoreOnly) {}
303  MemUsageOp(const MemUsageOp& other) : mCount(0), mInCoreOnly(other.mInCoreOnly) {}
304  MemUsageOp(const MemUsageOp& other, tbb::split) : MemUsageOp(other) {}
305 
306  // accumulate size of the root node in bytes
307  bool operator()(const RootT& root, size_t)
308  {
309  mCount += sizeof(root);
310  return true;
311  }
312 
313  // accumulate size of all child nodes in bytes
314  template<typename NodeT>
315  bool operator()(const NodeT& node, size_t)
316  {
317  mCount += NodeT::NUM_VALUES * sizeof(typename NodeT::UnionType) +
318  node.getChildMask().memUsage() + node.getValueMask().memUsage() +
319  sizeof(Coord);
320  return true;
321  }
322 
323  // accumulate size of leaf node in bytes
324  bool operator()(const LeafT& leaf, size_t)
325  {
326  if (mInCoreOnly) mCount += leaf.memUsage();
327  else mCount += leaf.memUsageIfLoaded();
328  return false;
329  }
330 
331  void join(const MemUsageOp& other)
332  {
333  mCount += other.mCount;
334  }
335 
336  openvdb::Index64 mCount{0};
337  const bool mInCoreOnly;
338 }; // struct MemUsageOp
339 
340 /// @brief A DynamicNodeManager operator to find the minimum and maximum active values in this tree.
341 template<typename TreeType>
342 struct MinMaxValuesOp
343 {
344  using ValueT = typename TreeType::ValueType;
345 
346  explicit MinMaxValuesOp()
347  : min(zeroVal<ValueT>())
348  , max(zeroVal<ValueT>())
349  , seen_value(false) {}
350 
351  MinMaxValuesOp(const MinMaxValuesOp&, tbb::split)
352  : MinMaxValuesOp() {}
353 
354  template <typename NodeType>
355  bool operator()(NodeType& node, size_t)
356  {
357  if (auto iter = node.cbeginValueOn()) {
358  if (!seen_value) {
359  seen_value = true;
360  min = max = *iter;
361  ++iter;
362  }
363 
364  for (; iter; ++iter) {
365  const ValueT val = *iter;
366 
367  if (math::cwiseLessThan(val, min))
368  min = val;
369 
370  if (math::cwiseGreaterThan(val, max))
371  max = val;
372  }
373  }
374 
375  return true;
376  }
377 
378  bool join(const MinMaxValuesOp& other)
379  {
380  if (!other.seen_value) return true;
381 
382  if (!seen_value) {
383  min = other.min;
384  max = other.max;
385  }
386  else {
387  if (math::cwiseLessThan(other.min, min))
388  min = other.min;
389  if (math::cwiseGreaterThan(other.max, max))
390  max = other.max;
391  }
392 
393  seen_value = true;
394  return true;
395  }
396 
397  ValueT min, max;
398 
399 private:
400 
401  bool seen_value;
402 }; // struct MinMaxValuesOp
403 
404 } // namespace count_internal
405 
406 /// @endcond
407 
408 
409 ////////////////////////////////////////
410 
411 
412 template <typename TreeT>
413 Index64 countActiveVoxels(const TreeT& tree, bool threaded)
414 {
415  count_internal::ActiveVoxelCountOp<TreeT> op;
416  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
417  nodeManager.reduceTopDown(op, threaded);
418  return op.count;
419 }
420 
421 
422 template <typename TreeT>
423 Index64 countActiveVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded)
424 {
425  if (bbox.empty()) return Index64(0);
426  else if (bbox == CoordBBox::inf()) return countActiveVoxels(tree, threaded);
427 
428  count_internal::ActiveVoxelCountBBoxOp<TreeT> op(bbox);
429  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
430  nodeManager.reduceTopDown(op, threaded);
431  return op.count;
432 }
433 
434 
435 template <typename TreeT>
436 Index64 countActiveLeafVoxels(const TreeT& tree, bool threaded)
437 {
438  count_internal::ActiveVoxelCountOp<TreeT> op;
439  // use a leaf manager instead of a node manager
440  tree::LeafManager<const TreeT> leafManager(tree);
441  leafManager.reduce(op, threaded);
442  return op.count;
443 }
444 
445 
446 template <typename TreeT>
447 Index64 countActiveLeafVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded)
448 {
449  if (bbox.empty()) return Index64(0);
450  else if (bbox == CoordBBox::inf()) return countActiveLeafVoxels(tree, threaded);
451 
452  count_internal::ActiveVoxelCountBBoxOp<TreeT> op(bbox);
453  // use a leaf manager instead of a node manager
454  tree::LeafManager<const TreeT> leafManager(tree);
455  leafManager.reduce(op, threaded);
456  return op.count;
457 }
458 
459 
460 template <typename TreeT>
461 Index64 countInactiveVoxels(const TreeT& tree, bool threaded)
462 {
463  count_internal::InactiveVoxelCountOp<TreeT> op;
464  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
465  nodeManager.reduceTopDown(op, threaded);
466  return op.count;
467 }
468 
469 
470 template <typename TreeT>
471 Index64 countInactiveLeafVoxels(const TreeT& tree, bool threaded)
472 {
473  count_internal::InactiveVoxelCountOp<TreeT> op;
474  // use a leaf manager instead of a node manager
475  tree::LeafManager<const TreeT> leafManager(tree);
476  leafManager.reduce(op, threaded);
477  return op.count;
478 }
479 
480 
481 template <typename TreeT>
482 Index64 countActiveTiles(const TreeT& tree, bool threaded)
483 {
484  count_internal::ActiveTileCountOp<TreeT> op;
485  // exclude leaf nodes as they cannot contain tiles
486  tree::DynamicNodeManager<const TreeT, TreeT::DEPTH-2> nodeManager(tree);
487  nodeManager.reduceTopDown(op, threaded);
488  return op.count;
489 }
490 
491 
492 template <typename TreeT>
493 Index64 memUsage(const TreeT& tree, bool threaded)
494 {
495  count_internal::MemUsageOp<TreeT> op(true);
496  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
497  nodeManager.reduceTopDown(op, threaded);
498  return op.mCount + sizeof(tree);
499 }
500 
501 template <typename TreeT>
502 Index64 memUsageIfLoaded(const TreeT& tree, bool threaded)
503 {
504  /// @note For numeric (non-point) grids this really doesn't need to
505  /// traverse the tree and could instead be computed from the node counts.
506  /// We do so anyway as it ties this method into the tree data structure
507  /// which makes sure that changes to the tree/nodes are reflected/kept in
508  /// sync here.
509  count_internal::MemUsageOp<TreeT> op(false);
510  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
511  nodeManager.reduceTopDown(op, threaded);
512  return op.mCount + sizeof(tree);
513 }
514 
515 template <typename TreeT>
516 math::MinMax<typename TreeT::ValueType> minMax(const TreeT& tree, bool threaded)
517 {
518  using ValueT = typename TreeT::ValueType;
519 
520  count_internal::MinMaxValuesOp<TreeT> op;
521  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
522  nodeManager.reduceTopDown(op, threaded);
523 
524  return math::MinMax<ValueT>(op.min, op.max);
525 }
526 
527 
528 } // namespace tools
529 } // namespace OPENVDB_VERSION_NAME
530 } // namespace openvdb
531 
532 #endif // OPENVDB_TOOLS_COUNT_HAS_BEEN_INCLUDED
uint64_t Index64
Definition: Types.h:53
Index64 countInactiveLeafVoxels(const TreeT &tree, bool threaded=true)
Return the total number of inactive voxels stored in leaf nodes.
Definition: Count.h:471
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:106
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:110
bool cwiseLessThan(const Mat< SIZE, T > &m0, const Mat< SIZE, T > &m1)
Definition: Mat.h:1015
Templated class to compute the minimum and maximum values.
Definition: Stats.h:30
bool cwiseGreaterThan(const Mat< SIZE, T > &m0, const Mat< SIZE, T > &m1)
Definition: Mat.h:1029
Index64 memUsage(const TreeT &tree, bool threaded=true)
Return the total amount of memory in bytes occupied by this tree.
Definition: Count.h:493
void reduce(LeafOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to each leaf node in the LeafManager. Unlike foreach (defined above) this method performs a reduction on all the leaf nodes.
Definition: LeafManager.h:532
bool isApproxEqual(const Type &a, const Type &b, const Type &tolerance)
Return true if a is equal to b to within the given tolerance.
Definition: Math.h:406
Index64 countActiveVoxels(const TreeT &tree, const CoordBBox &bbox, bool threaded=true)
Return the total number of active voxels in the tree that intersects a bounding box.
Definition: Count.h:423
Classes to compute statistics and histograms.
BBox< Coord > CoordBBox
Definition: NanoVDB.h:1809
void reduceTopDown(NodeOp &op, bool threaded=true, size_t leafGrainSize=1, size_t nonLeafGrainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:1043
Definition: Exceptions.h:13
Index64 countActiveLeafVoxels(const TreeT &tree, const CoordBBox &bbox, bool threaded=true)
Return the total number of active voxels stored in leaf nodes that intersects a bounding box...
Definition: Count.h:447
Index64 countInactiveVoxels(const TreeT &tree, bool threaded=true)
Return the total number of inactive voxels in the tree.
Definition: Count.h:461
Index64 countActiveTiles(const TreeT &tree, bool threaded=true)
Return the total number of active tiles in the tree.
Definition: Count.h:482
This class manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional auxil...
Definition: LeafManager.h:84
A LeafManager manages a linear array of pointers to a given tree&#39;s leaf nodes, as well as optional au...
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
T zeroVal()
Return the value of type T that corresponds to zero.
Definition: Math.h:70
math::MinMax< typename TreeT::ValueType > minMax(const TreeT &tree, bool threaded=true)
Return the minimum and maximum active values in this tree.
Definition: Count.h:516
Index64 memUsageIfLoaded(const TreeT &tree, bool threaded=true)
Return the deserialized memory usage of this tree. This is not necessarily equal to the current memor...
Definition: Count.h:502
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
Definition: NodeManager.h:36