HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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>
17 
18 namespace openvdb {
20 namespace OPENVDB_VERSION_NAME {
21 namespace tools {
22 
23 
24 /// @brief Return the total number of active voxels in the tree.
25 template <typename TreeT>
26 Index64 countActiveVoxels(const TreeT& tree, bool threaded = true);
27 
28 
29 /// @brief Return the total number of active voxels in the tree that intersects
30 /// a bounding box.
31 template <typename TreeT>
32 Index64 countActiveVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded = true);
33 
34 
35 /// @brief Return the total number of active voxels stored in leaf nodes.
36 template <typename TreeT>
37 Index64 countActiveLeafVoxels(const TreeT& tree, bool threaded = true);
38 
39 
40 /// @brief Return the total number of active voxels stored in leaf nodes that intersects
41 /// a bounding box.
42 template <typename TreeT>
43 Index64 countActiveLeafVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded = true);
44 
45 
46 /// @brief Return the total number of inactive voxels in the tree.
47 template <typename TreeT>
48 Index64 countInactiveVoxels(const TreeT& tree, bool threaded = true);
49 
50 
51 /// @brief Return the total number of inactive voxels stored in leaf nodes.
52 template <typename TreeT>
53 Index64 countInactiveLeafVoxels(const TreeT& tree, bool threaded = true);
54 
55 
56 /// @brief Return the total number of active tiles in the tree.
57 template <typename TreeT>
58 Index64 countActiveTiles(const TreeT& tree, bool threaded = true);
59 
60 
61 /// @brief Return the total amount of memory in bytes occupied by this tree.
62 template <typename TreeT>
63 Index64 memUsage(const TreeT& tree, bool threaded = true);
64 
65 
66 ////////////////////////////////////////
67 
68 /// @cond OPENVDB_DOCS_INTERNAL
69 
70 namespace count_internal {
71 
72 /// @brief A DynamicNodeManager operator to count active voxels in a tree
73 template<typename TreeType>
74 struct ActiveVoxelCountOp
75 {
76  using LeafT = typename TreeType::LeafNodeType;
77 
78  ActiveVoxelCountOp() = default;
79  ActiveVoxelCountOp(const ActiveVoxelCountOp&, tbb::split) { }
80 
81  // accumulate all voxels in active tile children
82  template<typename NodeT>
83  bool operator()(const NodeT& node, size_t)
84  {
85  for (auto iter = node.cbeginValueOn(); iter; ++iter) {
86  count += NodeT::ChildNodeType::NUM_VOXELS;
87  }
88  return true;
89  }
90 
91  // accumulate all active voxels in the leaf
92  bool operator()(const LeafT& leaf, size_t)
93  {
94  count += leaf.onVoxelCount();
95  return false;
96  }
97 
98  void join(const ActiveVoxelCountOp& other)
99  {
100  count += other.count;
101  }
102 
104 }; // struct ActiveVoxelCountOp
105 
106 /// @brief A DynamicNodeManager operator to count active voxels in a tree
107 /// that fall within a provided bounding box
108 template<typename TreeType>
109 struct ActiveVoxelCountBBoxOp
110 {
111  using LeafT = typename TreeType::LeafNodeType;
112 
113  explicit ActiveVoxelCountBBoxOp(const CoordBBox& bbox)
114  : mBBox(bbox) { }
115  ActiveVoxelCountBBoxOp(const ActiveVoxelCountBBoxOp& other, tbb::split)
116  : mBBox(other.mBBox) { }
117 
118  // accumulate all voxels in active tile children bounded by the bbox
119  template<typename NodeT>
120  bool operator()(const NodeT& node, size_t)
121  {
122  if (!mBBox.hasOverlap(node.getNodeBoundingBox())) return false;
123 
124  // count any overlapping regions in active tiles
125  for (auto iter = node.cbeginValueOn(); iter; ++iter) {
126  CoordBBox bbox(CoordBBox::createCube(iter.getCoord(), NodeT::ChildNodeType::DIM));
127 
128  if (!bbox.hasOverlap(mBBox)) {
129  // box is completely outside the active tile
130  continue;
131  } else if (bbox.isInside(mBBox)) {
132  // bbox is completely inside the active tile
133  count += mBBox.volume();
134  } else if (mBBox.isInside(bbox)) {
135  // active tile is completely inside bbox
136  count += bbox.volume();
137  } else {
138  // partial overlap between tile and bbox
139  bbox.intersect(mBBox);
140  count += bbox.volume();
141  }
142  }
143 
144  // return true if any child nodes overlap with the bounding box
145  for (auto iter = node.cbeginChildOn(); iter; ++iter) {
146  if (mBBox.hasOverlap(iter->getNodeBoundingBox())) return true;
147  }
148 
149  // otherwise return false to prevent recursion along this branch
150  return false;
151  }
152 
153  // accumulate all active voxels in the leaf bounded by the bbox
154  inline bool operator()(const LeafT& leaf, size_t)
155  {
156  // note: the true/false return value does nothing
157 
158  CoordBBox bbox = leaf.getNodeBoundingBox();
159 
160  if (mBBox.isInside(bbox)) {
161  // leaf node is completely inside bbox
162  count += leaf.onVoxelCount();
163  } else if (!bbox.hasOverlap(mBBox)) {
164  // bbox is completely outside the leaf node
165  return false;
166  } else if (leaf.isDense()) {
167  // partial overlap between dense leaf node and bbox
168  bbox.intersect(mBBox);
169  count += bbox.volume();
170  } else {
171  // partial overlap between sparse leaf node and bbox
172  for (auto i = leaf.cbeginValueOn(); i; ++i) {
173  if (mBBox.isInside(i.getCoord())) ++count;
174  }
175  }
176  return false;
177  }
178 
179  void join(const ActiveVoxelCountBBoxOp& other)
180  {
181  count += other.count;
182  }
183 
185 private:
186  CoordBBox mBBox;
187 }; // struct ActiveVoxelCountBBoxOp
188 
189 /// @brief A DynamicNodeManager operator to count inactive voxels in a tree
190 template<typename TreeType>
191 struct InactiveVoxelCountOp
192 {
193  using RootT = typename TreeType::RootNodeType;
194  using LeafT = typename TreeType::LeafNodeType;
195 
196  InactiveVoxelCountOp() = default;
197  InactiveVoxelCountOp(const InactiveVoxelCountOp&, tbb::split) { }
198 
199  // accumulate all inactive voxels in the root node
200  bool operator()(const RootT& root, size_t)
201  {
202  for (auto iter = root.cbeginValueOff(); iter; ++iter) {
203  // background tiles are not considered to contain inactive voxels
204  if (!math::isApproxEqual(*iter, root.background())) {
205  count += RootT::ChildNodeType::NUM_VOXELS;
206  }
207  }
208  return true;
209  }
210 
211  // accumulate all voxels in inactive tile children
212  template<typename NodeT>
213  bool operator()(const NodeT& node, size_t)
214  {
215  for (auto iter = node.cbeginValueOff(); iter; ++iter) {
216  if (node.isChildMaskOff(iter.pos())) {
217  count += NodeT::ChildNodeType::NUM_VOXELS;
218  }
219  }
220  return true;
221  }
222 
223  // accumulate all inactive voxels in the leaf
224  bool operator()(const LeafT& leaf, size_t)
225  {
226  count += leaf.offVoxelCount();
227  return false;
228  }
229 
230  void join(const InactiveVoxelCountOp& other)
231  {
232  count += other.count;
233  }
234 
236 }; // struct InactiveVoxelCountOp
237 
238 /// @brief A DynamicNodeManager operator to count active tiles in a tree
239 template<typename TreeType>
240 struct ActiveTileCountOp
241 {
242  using RootT = typename TreeType::RootNodeType;
243  using LeafT = typename TreeType::LeafNodeType;
244 
245  ActiveTileCountOp() = default;
246  ActiveTileCountOp(const ActiveTileCountOp&, tbb::split) { }
247 
248  // accumulate all active tiles in root node
249  bool operator()(const RootT& root, size_t)
250  {
251  for (auto iter = root.cbeginValueOn(); iter; ++iter) count++;
252  return true;
253  }
254 
255  // accumulate all active tiles in internal node
256  template<typename NodeT>
257  bool operator()(const NodeT& node, size_t)
258  {
259  count += node.getValueMask().countOn();
260  return true;
261  }
262 
263  // do nothing (leaf nodes cannot contain tiles)
264  bool operator()(const LeafT&, size_t)
265  {
266  return false;
267  }
268 
269  void join(const ActiveTileCountOp& other)
270  {
271  count += other.count;
272  }
273 
275 }; // struct ActiveTileCountOp
276 
277 /// @brief A DynamicNodeManager operator to sum the number of bytes of memory used
278 template<typename TreeType>
279 struct MemUsageOp
280 {
281  using RootT = typename TreeType::RootNodeType;
282  using LeafT = typename TreeType::LeafNodeType;
283 
284  MemUsageOp() = default;
285  MemUsageOp(const MemUsageOp&, tbb::split) { }
286 
287  // accumulate size of the root node in bytes
288  bool operator()(const RootT& root, size_t)
289  {
290  count += sizeof(root);
291  return true;
292  }
293 
294  // accumulate size of all child nodes in bytes
295  template<typename NodeT>
296  bool operator()(const NodeT& node, size_t)
297  {
298  count += NodeT::NUM_VALUES * sizeof(typename NodeT::UnionType) +
299  node.getChildMask().memUsage() + node.getValueMask().memUsage() +
300  sizeof(Coord);
301  return true;
302  }
303 
304  // accumulate size of leaf node in bytes
305  bool operator()(const LeafT& leaf, size_t)
306  {
307  count += leaf.memUsage();
308  return false;
309  }
310 
311  void join(const MemUsageOp& other)
312  {
313  count += other.count;
314  }
315 
317 }; // struct MemUsageOp
318 
319 } // namespace count_internal
320 
321 /// @endcond
322 
323 
324 ////////////////////////////////////////
325 
326 
327 template <typename TreeT>
328 Index64 countActiveVoxels(const TreeT& tree, bool threaded)
329 {
330  count_internal::ActiveVoxelCountOp<TreeT> op;
331  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
332  nodeManager.reduceTopDown(op, threaded);
333  return op.count;
334 }
335 
336 
337 template <typename TreeT>
338 Index64 countActiveVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded)
339 {
340  if (bbox.empty()) return Index64(0);
341  else if (bbox == CoordBBox::inf()) return countActiveVoxels(tree, threaded);
342 
343  count_internal::ActiveVoxelCountBBoxOp<TreeT> op(bbox);
344  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
345  nodeManager.reduceTopDown(op, threaded);
346  return op.count;
347 }
348 
349 
350 template <typename TreeT>
351 Index64 countActiveLeafVoxels(const TreeT& tree, bool threaded)
352 {
353  count_internal::ActiveVoxelCountOp<TreeT> op;
354  // use a leaf manager instead of a node manager
355  tree::LeafManager<const TreeT> leafManager(tree);
356  leafManager.reduce(op, threaded);
357  return op.count;
358 }
359 
360 
361 template <typename TreeT>
362 Index64 countActiveLeafVoxels(const TreeT& tree, const CoordBBox& bbox, bool threaded)
363 {
364  if (bbox.empty()) return Index64(0);
365  else if (bbox == CoordBBox::inf()) return countActiveLeafVoxels(tree, threaded);
366 
367  count_internal::ActiveVoxelCountBBoxOp<TreeT> op(bbox);
368  // use a leaf manager instead of a node manager
369  tree::LeafManager<const TreeT> leafManager(tree);
370  leafManager.reduce(op, threaded);
371  return op.count;
372 }
373 
374 
375 template <typename TreeT>
376 Index64 countInactiveVoxels(const TreeT& tree, bool threaded)
377 {
378  count_internal::InactiveVoxelCountOp<TreeT> op;
379  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
380  nodeManager.reduceTopDown(op, threaded);
381  return op.count;
382 }
383 
384 
385 template <typename TreeT>
386 Index64 countInactiveLeafVoxels(const TreeT& tree, bool threaded)
387 {
388  count_internal::InactiveVoxelCountOp<TreeT> op;
389  // use a leaf manager instead of a node manager
390  tree::LeafManager<const TreeT> leafManager(tree);
391  leafManager.reduce(op, threaded);
392  return op.count;
393 }
394 
395 
396 template <typename TreeT>
397 Index64 countActiveTiles(const TreeT& tree, bool threaded)
398 {
399  count_internal::ActiveTileCountOp<TreeT> op;
400  // exclude leaf nodes as they cannot contain tiles
401  tree::DynamicNodeManager<const TreeT, TreeT::DEPTH-2> nodeManager(tree);
402  nodeManager.reduceTopDown(op, threaded);
403  return op.count;
404 }
405 
406 
407 template <typename TreeT>
408 Index64 memUsage(const TreeT& tree, bool threaded)
409 {
410  count_internal::MemUsageOp<TreeT> op;
411  tree::DynamicNodeManager<const TreeT> nodeManager(tree);
412  nodeManager.reduceTopDown(op, threaded);
413  return op.count + sizeof(tree);
414 }
415 
416 
417 } // namespace tools
418 } // namespace OPENVDB_VERSION_NAME
419 } // namespace openvdb
420 
421 #endif // OPENVDB_TOOLS_COUNT_HAS_BEEN_INCLUDED
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
Index64 countActiveLeafVoxels(const TreeT &tree, bool threaded=true)
Return the total number of active voxels stored in leaf nodes.
Definition: Count.h:351
Index64 memUsage(const TreeT &tree, bool threaded=true)
Return the total amount of memory in bytes occupied by this tree.
Definition: Count.h:408
Index64 countInactiveVoxels(const TreeT &tree, bool threaded=true)
Return the total number of inactive voxels in the tree.
Definition: Count.h:376
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:178
Index64 countActiveTiles(const TreeT &tree, bool threaded=true)
Return the total number of active tiles in the tree.
Definition: Count.h:397
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
void OIIO_API split(string_view str, std::vector< string_view > &result, string_view sep=string_view(), int maxsplit=-1)
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:407
Index64 countInactiveLeafVoxels(const TreeT &tree, bool threaded=true)
Return the total number of inactive voxels stored in leaf nodes.
Definition: Count.h:386
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:84
GLint GLsizei count
Definition: glcorearb.h:404
Library and file format version numbers.
Index64 countActiveVoxels(const TreeT &tree, bool threaded=true)
Return the total number of active voxels in the tree.
Definition: Count.h:328
NodeManager produces linear arrays of all tree nodes allowing for efficient threading and bottom-up p...
A LeafManager manages a linear array of pointers to a given tree's leaf nodes, as well as optional au...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:114
arg_join< It, Sentinel, char > join(It begin, Sentinel end, string_view sep)
Definition: format.h:3681