GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/FindActiveValues.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 150 187 80.2%
Functions: 31 221 14.0%
Branches: 100 180 55.6%
Line Branch Exec Source
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3
4 ///////////////////////////////////////////////////////////////////////////
5 //
6 /// @file FindActiveValues.h
7 ///
8 /// @author Ken Museth
9 ///
10 /// @brief Finds the active values and tiles in a tree that intersects a bounding box.
11 /// Methods are provided that count the number of active values and tiles,
12 /// test for the existence of active values and tiles, and return a list of
13 /// the active tiles that intersect a bbox.
14 ///
15 /// @warning For repeated calls to the free-standing functions defined below
16 /// consider instead creating an instance of FindActiveValues
17 /// and then repeatedly call its member methods. This assumes the tree
18 /// to be constant between calls but is sightly faster.
19 ///
20 ///////////////////////////////////////////////////////////////////////////
21
22 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
23 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
24
25 #include <vector>
26 #include <openvdb/version.h> // for OPENVDB_VERSION_NAME
27 #include <openvdb/Types.h>
28 #include <openvdb/tree/ValueAccessor.h>
29 #include <openvdb/openvdb.h>
30
31 #include "Count.h" // tools::countActiveVoxels()
32
33 #include <tbb/blocked_range.h>
34 #include <tbb/parallel_for.h>
35 #include <tbb/parallel_reduce.h>
36
37 namespace openvdb {
38 OPENVDB_USE_VERSION_NAMESPACE
39 namespace OPENVDB_VERSION_NAME {
40 namespace tools {
41
42 /// @brief Struct that encodes a bounding box, value and level of a tile
43 ///
44 /// @details The bbox of a tiles is trimmed to the bounding box that probed it.
45 /// The level is typically defined as: 1 is 8^3, 2 is 128^3, and 3 is 4096^3.
46 template<typename ValueType>
47 struct TileData;
48
49 /// @brief Returns true if the bounding box intersects any of the active
50 /// values in a tree, i.e. either active voxels or active tiles.
51 ///
52 /// @warning For repeated calls to this method consider instead creating an instance of
53 /// FindActiveValues and then repeatedly call anyActiveValues(). This assumes the tree
54 /// to be constant between calls but is slightly faster.
55 ///
56 /// @param tree const tree to be tested for active values.
57 /// @param bbox index bounding box which is intersected against the active values.
58 template<typename TreeT>
59 bool
60 anyActiveValues(const TreeT& tree, const CoordBBox &bbox);
61
62 /// @brief Returns true if the bounding box intersects any of the active
63 /// voxels in a tree, i.e. ignores active tile values.
64 ///
65 /// @note In VDB voxels by definition reside in the leaf nodes ONLY. So this method
66 /// ignores active tile values that reside higher up in the VDB tree structure.
67 ///
68 /// @warning For repeated calls to this method consider instead creating an instance of
69 /// FindActiveValues and then repeatedly call anyActiveVoxels(). This assumes the tree
70 /// to be constant between calls but is slightly faster.
71 ///
72 /// @param tree const tree to be tested for active voxels.
73 /// @param bbox index bounding box which is intersected against the active voxels.
74 template<typename TreeT>
75 bool
76 anyActiveVoxels(const TreeT& tree, const CoordBBox &bbox);
77
78 /// @brief Returns true if the bounding box intersects any of the active
79 /// tiles in a tree, i.e. ignores active leaf values.
80 ///
81 /// @warning For repeated calls to this method consider instead creating an instance of
82 /// FindActiveValues and then repeatedly call anyActiveTiles(). This assumes the tree
83 /// to be constant between calls but is slightly faster.
84 ///
85 /// @param tree const tree to be tested for active tiles.
86 /// @param bbox index bounding box which is intersected against the active tiles.
87 template<typename TreeT>
88 bool
89 anyActiveTiles(const TreeT& tree, const CoordBBox &bbox);
90
91 /// @brief Returns true if the bounding box intersects none of the active
92 /// values in a tree, i.e. neither active voxels or active tiles.
93 ///
94 /// @warning For repeated calls to this method consider instead creating an instance of
95 /// FindActiveValues and then repeatedly call noActiveValues(). This assumes the tree
96 /// to be constant between calls but is slightly faster.
97 ///
98 /// @param tree const tree to be tested for active values.
99 /// @param bbox index bounding box which is intersected against the active values.
100 template<typename TreeT>
101 bool
102 noActiveValues(const TreeT& tree, const CoordBBox &bbox);
103
104 /// @brief Returns the number of active values that intersects a bounding box intersects,
105 /// i.e. the count includes both active voxels and virtual voxels in active tiles.
106 ///
107 /// @warning For repeated calls to this method consider instead creating an instance of
108 /// FindActiveValues and then repeatedly call count(). This assumes the tree
109 /// to be constant between calls but is slightly faster.
110 ///
111 /// @param tree const tree to be tested for active values.
112 /// @param bbox index bounding box which is intersected against the active values.
113 template<typename TreeT>
114 Index64
115 countActiveValues(const TreeT& tree, const CoordBBox &bbox);
116
117 /// @brief Return a vector with bounding boxes that represents all the intersections
118 /// between active tiles in the tree and the specified bounding box.
119 ///
120 /// @warning For repeated calls to this method consider instead creating an instance of
121 /// FindActiveValues and then repeatedly call count(). This assumes the tree
122 /// to be constant between calls but is slightly faster.
123 ///
124 /// @param tree const tree to be tested for active tiles.
125 /// @param bbox index bounding box which is intersected against the active tiles.
126 template<typename TreeT>
127 std::vector<TileData<typename TreeT::ValueType>>
128 activeTiles(const TreeT& tree, const CoordBBox &bbox);
129
130 //////////////////////////////////////////////////////////////////////////////////////////
131
132 /// @brief Finds the active values in a tree which intersects a bounding box.
133 ///
134 /// @details Two methods are provided, one that count the number of active values
135 /// and one that simply tests if any active values intersect the bbox.
136 ///
137 /// @warning Tree nodes are cached by this class so it's important that the tree is not
138 /// modified after this class is instantiated and before its methods are called.
139 template<typename TreeT>
140 class FindActiveValues
141 {
142 public:
143
144 using TileDataT = TileData<typename TreeT::ValueType>;
145
146 /// @brief Constructor from a const tree, which is assumed not to be modified after construction.
147 FindActiveValues(const TreeT& tree);
148
149 /// @brief Default destructor
150 ~FindActiveValues();
151
152 /// @brief Initiate this class with a new (or modified) tree.
153 void update(const TreeT& tree);
154
155 /// @brief Returns true if the specified bounding box intersects any active values.
156 ///
157 /// @warning Using a ValueAccessor (i.e. useAccessor = true) can improve performance for especially
158 /// small bounding boxes, but at the cost of no thread-safety. So if multiple threads are
159 /// calling this method concurrently use the default setting, useAccessor = false.
160 bool anyActiveValues(const CoordBBox &bbox, bool useAccessor = false) const;
161
162 /// @brief Returns true if the specified bounding box intersects any active tiles only.
163 bool anyActiveVoxels(const CoordBBox &bbox) const;
164
165 /// @brief Returns true if the specified bounding box intersects any active tiles only.
166 bool anyActiveTiles(const CoordBBox &bbox) const;
167
168 /// @brief Returns true if the specified bounding box does not intersect any active values.
169 ///
170 /// @warning Using a ValueAccessor (i.e. useAccessor = true) can improve performance for especially
171 /// small bounding boxes, but at the cost of no thread-safety. So if multiple threads are
172 /// calling this method concurrently use the default setting, useAccessor = false.
173
4/18
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 58 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 13 taken 3 times.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 62 bool noActiveValues(const CoordBBox &bbox, bool useAccessor = false) const { return !this->anyActiveValues(bbox, useAccessor); }
174
175 /// @brief Returns the number of active voxels intersected by the specified bounding box.
176 Index64 count(const CoordBBox &bbox) const;
177
178 /// @brief Return a vector with bounding boxes that represents all the intersections
179 /// between active tiles in the tree and the specified bounding box.
180 std::vector<TileDataT> activeTiles(const CoordBBox &bbox) const;
181
182 OPENVDB_DEPRECATED_MESSAGE("Use anyActiveValues() instead") inline bool any(const CoordBBox &bbox, bool useAccessor = false) const
183 {
184 return this->anyActiveValues(bbox, useAccessor);
185 }
186 OPENVDB_DEPRECATED_MESSAGE("Use noActiveValues() instead") inline bool none(const CoordBBox &bbox, bool useAccessor = false) const
187 {
188 return this->noActiveValues(bbox, useAccessor);
189 }
190
191 private:
192
193 // Cleans up internal data structures
194 void clear();
195
196 // builds internal data structures
197 void init(const TreeT &tree);
198
199 template<typename NodeT>
200 typename NodeT::NodeMaskType getBBoxMask(const CoordBBox &bbox, const NodeT* node) const;
201
202 // process leaf nodes
203 76 inline bool anyActiveValues(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const { return this->anyActiveVoxels(leaf, bbox); }
204 inline bool anyActiveVoxels(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const;
205 static bool anyActiveTiles( const typename TreeT::LeafNodeType*, const CoordBBox& ) {return false;}
206 void activeTiles(const typename TreeT::LeafNodeType*, const CoordBBox&, std::vector<TileDataT>&) const {;}// no-op
207 inline Index64 count(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const;
208
209 // process internal nodes
210 template<typename NodeT>
211 bool anyActiveValues(const NodeT* node, const CoordBBox &bbox) const;
212 template<typename NodeT>
213 bool anyActiveVoxels(const NodeT* node, const CoordBBox &bbox) const;
214 template<typename NodeT>
215 bool anyActiveTiles(const NodeT* node, const CoordBBox &bbox) const;
216 template<typename NodeT>
217 void activeTiles(const NodeT* node, const CoordBBox &bbox, std::vector<TileDataT> &tiles) const;
218 template<typename NodeT>
219 Index64 count(const NodeT* node, const CoordBBox &bbox) const;
220
221 using AccT = tree::ValueAccessor<const TreeT, false/* IsSafe */>;
222 using RootChildType = typename TreeT::RootNodeType::ChildNodeType;
223
224 struct RootChild;
225
226 AccT mAcc;
227 std::vector<TileDataT> mRootTiles;// cache bbox of child nodes (faster to cache than access RootNode)
228 std::vector<RootChild> mRootNodes;// cache bbox of active tiles (faster to cache than access RootNode)
229
230 };// FindActiveValues class
231
232 //////////////////////////////////////////////////////////////////////////////////////////
233
234 template<typename TreeT>
235 100 FindActiveValues<TreeT>::FindActiveValues(const TreeT& tree) : mAcc(tree), mRootTiles(), mRootNodes()
236 {
237
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 this->init(tree);
238 100 }
239
240 template<typename TreeT>
241 100 FindActiveValues<TreeT>::~FindActiveValues()
242 {
243 100 this->clear();
244 100 }
245
246 template<typename TreeT>
247 1 void FindActiveValues<TreeT>::update(const TreeT& tree)
248 {
249 1 this->clear();
250
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 mAcc = AccT(tree);
251 1 this->init(tree);
252 1 }
253
254 template<typename TreeT>
255
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 4 times.
 101 void FindActiveValues<TreeT>::clear()
256 {
257 mRootNodes.clear();
258 mRootTiles.clear();
259 101 }
260
261 template<typename TreeT>
262 101 void FindActiveValues<TreeT>::init(const TreeT& tree)
263 {
264 const auto &root = tree.root();
265
2/2
✓ Branch 1 taken 621 times.
✓ Branch 2 taken 101 times.
 823 for (auto i = root.cbeginChildOn(); i; ++i) {
266 621 mRootNodes.emplace_back(i.getCoord(), &*i);
267 }
268
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 101 times.
 202 for (auto i = root.cbeginValueOn(); i; ++i) {
269 ✗ mRootTiles.emplace_back(root, i.getCoord(), *i);
270 }
271 101 }
272
273 template<typename TreeT>
274 3210 bool FindActiveValues<TreeT>::anyActiveValues(const CoordBBox &bbox, bool useAccessor) const
275 {
276 // test early-out: the center of the bbox is active
277
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3210 times.
 3210 if (useAccessor) {
278 ✗ if (mAcc.isValueOn( (bbox.min() + bbox.max())>>1 )) return true;
279 } else {
280
2/2
✓ Branch 1 taken 135 times.
✓ Branch 2 taken 3075 times.
 3210 if (mAcc.tree().isValueOn( (bbox.min() + bbox.max())>>1 )) return true;
281 }
282
283
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 135 times.
 135 for (auto& tile : mRootTiles) {
284 ✗ if (tile.bbox.hasOverlap(bbox)) return true;
285 }
286
2/2
✓ Branch 0 taken 982 times.
✓ Branch 1 taken 118 times.
 1100 for (auto& node : mRootNodes) {
287 63 if (!node.bbox.hasOverlap(bbox)) {// no overlap
288 63 continue;
289 } else if (node.bbox.isInside(bbox)) {// bbox is inside the child node
290 17 return this->anyActiveValues(node.child, bbox);
291
2/2
✓ Branch 1 taken 902 times.
✓ Branch 2 taken 5 times.
 907 } else if (this->anyActiveValues(node.child, bbox)) {// bbox overlaps the child node
292 return true;
293 }
294 }
295 118 return false;
296 }
297
298 template<typename TreeT>
299 517 bool FindActiveValues<TreeT>::anyActiveVoxels(const CoordBBox &bbox) const
300 {
301
2/2
✓ Branch 0 taken 2302 times.
✓ Branch 1 taken 3 times.
 2305 for (auto& node : mRootNodes) {
302 1785 if (!node.bbox.hasOverlap(bbox)) {// no overlap
303 1785 continue;
304 } else if (node.bbox.isInside(bbox)) {// bbox is inside the child node
305 514 return this->anyActiveVoxels(node.child, bbox);
306
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 4 times.
 7 } else if (this->anyActiveVoxels(node.child, bbox)) {// bbox overlaps the child node
307 return true;
308 }
309 }
310 3 return false;
311 }
312
313 template<typename TreeT>
314 12 bool FindActiveValues<TreeT>::anyActiveTiles(const CoordBBox &bbox) const
315 {
316
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 12 for (auto& tile : mRootTiles) {
317 ✗ if (tile.bbox.hasOverlap(bbox)) return true;
318 }
319
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 3 times.
 34 for (auto& node : mRootNodes) {
320 ✗ if (!node.bbox.hasOverlap(bbox)) {// no overlap
321 ✗ continue;
322 } else if (node.bbox.isInside(bbox)) {// bbox is inside the child node
323 6 return this->anyActiveTiles(node.child, bbox);
324
2/2
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 2 times.
 26 } else if (this->anyActiveTiles(node.child, bbox)) {// bbox overlaps the child node
325 return true;
326 }
327 }
328 6 return false;
329 }
330
331 template<typename TreeT>
332 5 Index64 FindActiveValues<TreeT>::count(const CoordBBox &bbox) const
333 {
334 Index64 count = 0;
335
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 for (auto& tile : mRootTiles) {//loop over active tiles only
336 ✗ if (!tile.bbox.hasOverlap(bbox)) {
337 ✗ continue;//ignore non-overlapping tiles
338 } else if (tile.bbox.isInside(bbox)) {
339 ✗ return bbox.volume();// bbox is completely inside the active tile
340 } else if (bbox.isInside(tile.bbox)) {
341 ✗ count += RootChildType::NUM_VOXELS;
342 } else {// partial overlap between tile and bbox
343 ✗ auto tmp = tile.bbox;
344 ✗ tmp.intersect(bbox);
345 ✗ count += tmp.volume();
346 }
347 }
348
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 5 times.
 45 for (auto &node : mRootNodes) {//loop over child nodes of the root node only
349 ✗ if ( !node.bbox.hasOverlap(bbox) ) {
350 ✗ continue;//ignore non-overlapping child nodes
351 } else if ( node.bbox.isInside(bbox) ) {
352 ✗ return this->count(node.child, bbox);// bbox is completely inside the child node
353 } else {
354 40 count += this->count(node.child, bbox);
355 }
356 }
357 5 return count;
358 }
359
360 template<typename TreeT>
361 std::vector<TileData<typename TreeT::ValueType> >
362 12 FindActiveValues<TreeT>::activeTiles(const CoordBBox &bbox) const
363 {
364 std::vector<TileDataT> tiles;
365
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 12 for (auto& tile : mRootTiles) {//loop over active tiles only
366 ✗ if (!tile.bbox.hasOverlap(bbox)) {
367 ✗ continue;//ignore non-overlapping tiles
368 } else if (tile.bbox.isInside(bbox)) {// bbox is completely inside the active tile
369 ✗ tiles.emplace_back(bbox, tile.value, tile.level);
370 ✗ return tiles;
371 } else if (bbox.isInside(tile.bbox)) {// active tile is completely inside the bbox
372 ✗ tiles.push_back(tile);
373 } else {// partial overlap between tile and bbox
374 ✗ auto tmp = tile.bbox;
375 ✗ tmp.intersect(bbox);
376 ✗ tiles.emplace_back(tmp, tile.value, tile.level);
377 }
378 }
379
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 5 times.
 64 for (auto &node : mRootNodes) {//loop over child nodes of the root node only
380 ✗ if ( !node.bbox.hasOverlap(bbox) ) {
381 ✗ continue;//ignore non-overlapping child nodes
382 } else if ( node.bbox.isInside(bbox) ) {// bbox is completely inside the child node
383
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 2 this->activeTiles(node.child, bbox, tiles);
384 2 return tiles;
385 } else {// partial overlap between tile and child node
386
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 52 this->activeTiles(node.child, bbox, tiles);
387 }
388 }
389 10 return tiles;
390 }
391
392 template<typename TreeT>
393 template<typename NodeT>
394 6638 typename NodeT::NodeMaskType FindActiveValues<TreeT>::getBBoxMask(const CoordBBox &bbox, const NodeT* node) const
395 {
396 typename NodeT::NodeMaskType mask;// typically 32^3 or 16^3 bit mask
397 6638 auto b = node->getNodeBoundingBox();
398 ✗ assert( bbox.hasOverlap(b) );
399 if ( bbox.isInside(b) ) {
400 mask.setOn();//node is completely inside the bbox so early out
401 } else {
402 5980 b.intersect(bbox);// trim bounding box
403 // transform bounding box from global to local coordinates
404 b.min() &= NodeT::DIM-1u;
405 b.min() >>= NodeT::ChildNodeType::TOTAL;
406 b.max() &= NodeT::DIM-1u;
407 b.max() >>= NodeT::ChildNodeType::TOTAL;
408 ✗ assert( b.hasVolume() );
409 auto it = b.begin();// iterates over all the child nodes or tiles that intersects bbox
410
2/2
✓ Branch 0 taken 642615 times.
✓ Branch 1 taken 2990 times.
 1291210 for (const Coord& ijk = *it; it; ++it) {
411 1285230 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
412 }
413 }
414 6638 return mask;
415 }
416
417 template<typename TreeT>
418 template<typename NodeT>
419 3670 bool FindActiveValues<TreeT>::anyActiveValues(const NodeT* node, const CoordBBox &bbox) const
420 {
421 // Generate a bit mask of the bbox coverage
422 3670 auto mask = this->getBBoxMask(bbox, node);
423
424 // Check active tiles
425 const auto tmp = mask & node->getValueMask();// prune active the tile mask with the bbox mask
426
2/2
✓ Branch 0 taken 1834 times.
✓ Branch 1 taken 1 times.
 3670 if (!tmp.isOff()) return true;
427
428 // Check child nodes
429 mask &= node->getChildMask();// prune the child mask with the bbox mask
430 const auto* table = node->getTable();
431 bool active = false;
432
4/4
✓ Branch 1 taken 2812 times.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 992 times.
✓ Branch 4 taken 1820 times.
 11276 for (auto i = mask.beginOn(); !active && i; ++i) {
433 1984 active = this->anyActiveValues(table[i.pos()].getChild(), bbox);
434 }
435 3668 return active;
436 }
437
438 template<typename TreeT>
439 template<typename NodeT>
440 1558 bool FindActiveValues<TreeT>::anyActiveVoxels(const NodeT* node, const CoordBBox &bbox) const
441 {
442 // Generate a bit mask of the bbox coverage
443 1558 auto mask = this->getBBoxMask(bbox, node);
444
445 // Check child nodes
446 mask &= node->getChildMask();// prune the child mask with the bbox mask
447 const auto* table = node->getTable();
448 bool active = false;
449
4/4
✓ Branch 1 taken 784 times.
✓ Branch 2 taken 518 times.
✓ Branch 3 taken 523 times.
✓ Branch 4 taken 261 times.
 4172 for (auto i = mask.beginOn(); !active && i; ++i) {
450 1046 active = this->anyActiveVoxels(table[i.pos()].getChild(), bbox);
451 }
452 1558 return active;
453 }
454
455 template<typename TreeT>
456 337 inline bool FindActiveValues<TreeT>::anyActiveVoxels(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const
457 {
458 const auto &mask = leaf->getValueMask();
459
460 // check for two common cases that leads to early-out
461 924 if (bbox.isInside(leaf->getNodeBoundingBox())) return !mask.isOff();// leaf in inside the bbox
462
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 7 times.
 87 if (mask.isOn()) return true;// all values are active
463
464 bool active = false;
465
4/4
✓ Branch 0 taken 8919 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 71 times.
✓ Branch 3 taken 8848 times.
 17847 for (auto i = leaf->cbeginValueOn(); !active && i; ++i) {
466 17696 active = bbox.isInside(i.getCoord());
467 }
468 80 return active;
469 }
470
471 template<typename TreeT>
472 template<typename NodeT>
473 54 bool FindActiveValues<TreeT>::anyActiveTiles(const NodeT* node, const CoordBBox &bbox) const
474 {
475 // Generate a bit mask of the bbox coverage
476 54 auto mask = this->getBBoxMask(bbox, node);
477
478 // Check active tiles
479 const auto tmp = mask & node->getValueMask();// prune active the tile mask with the bbox mask
480
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 13 times.
 54 if (!tmp.isOff()) return true;
481
482 bool active = false;
483 if (NodeT::LEVEL>1) {// Only check child nodes if they are NOT leaf nodes
484 mask &= node->getChildMask();// prune the child mask with the bbox mask
485 const auto* table = node->getTable();
486
4/4
✓ Branch 1 taken 25 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 12 times.
 102 for (auto i = mask.beginOn(); !active && i; ++i) {
487 26 active = this->anyActiveTiles(table[i.pos()].getChild(), bbox);
488 }
489 }
490 26 return active;
491 }
492
493 template<typename TreeT>
494 602812 inline Index64 FindActiveValues<TreeT>::count(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const
495 {
496 Index64 count = 0;
497 602812 auto b = leaf->getNodeBoundingBox();
498 if (b.isInside(bbox)) { // leaf node is completely inside bbox
499 count = leaf->onVoxelCount();
500
2/2
✓ Branch 0 taken 524288 times.
✓ Branch 1 taken 78524 times.
 602812 } else if (leaf->isDense()) {
501 524288 b.intersect(bbox);
502 count = b.volume();
503 } else if (b.hasOverlap(bbox)) {
504
2/2
✓ Branch 0 taken 5478729 times.
✓ Branch 1 taken 78524 times.
 5557253 for (auto i = leaf->cbeginValueOn(); i; ++i) {
505 10957458 if (bbox.isInside(i.getCoord())) ++count;
506 }
507 }
508 602812 return count;
509 }
510
511 template<typename TreeT>
512 template<typename NodeT>
513 1030 Index64 FindActiveValues<TreeT>::count(const NodeT* node, const CoordBBox &bbox) const
514 {
515 Index64 count = 0;
516
517 // Generate a bit masks
518 1030 auto mask = this->getBBoxMask(bbox, node);
519 const auto childMask = mask & node->getChildMask();// prune the child mask with the bbox mask
520 mask &= node->getValueMask();// prune active tile mask with the bbox mask
521 const auto* table = node->getTable();
522
523 {// Check child nodes
524 using ChildT = typename NodeT::ChildNodeType;
525 using RangeT = tbb::blocked_range<typename std::vector<const ChildT*>::iterator>;
526 1030 std::vector<const ChildT*> childNodes(childMask.countOn());
527 int j=0;
528
2/2
✓ Branch 1 taken 603287 times.
✓ Branch 2 taken 515 times.
 1208634 for (auto i = childMask.beginOn(); i; ++i, ++j) childNodes[j] = table[i.pos()].getChild();
529
3/6
✓ Branch 1 taken 515 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 506 times.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 1030 count += tbb::parallel_reduce( RangeT(childNodes.begin(), childNodes.end()), 0,
530 56026 [&](const RangeT& r, Index64 sum)->Index64 {
531
4/4
✓ Branch 0 taken 602812 times.
✓ Branch 1 taken 55551 times.
✓ Branch 3 taken 475 times.
✓ Branch 4 taken 475 times.
 659313 for ( auto i = r.begin(); i != r.end(); ++i ) sum += this->count(*i, bbox);
532 56026 return sum;
533 }, []( Index64 a, Index64 b )->Index64 { return a+b; }
534 );
535 }
536
537 {// Check active tiles
538 1030 std::vector<Coord> coords(mask.countOn());
539 using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
540 int j=0;
541
2/2
✓ Branch 1 taken 576 times.
✓ Branch 2 taken 515 times.
 4364 for (auto i = mask.beginOn(); i; ++i, ++j) coords[j] = node->offsetToGlobalCoord(i.pos());
542
3/6
✓ Branch 1 taken 515 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 499 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 1030 count += tbb::parallel_reduce( RangeT(coords.begin(), coords.end()), 0,
543 576 [&bbox](const RangeT& r, Index64 sum)->Index64 {
544
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 576 times.
✓ Branch 3 taken 576 times.
 1152 for ( auto i = r.begin(); i != r.end(); ++i ) {
545 auto b = CoordBBox::createCube(*i, NodeT::ChildNodeType::DIM);
546 576 b.intersect(bbox);
547 576 sum += b.volume();
548 }
549 576 return sum;
550 }, []( Index64 a, Index64 b )->Index64 { return a+b; }
551 );
552 }
553
554 1030 return count;
555 }
556
557 // process internal node
558 template<typename TreeT>
559 template<typename NodeT>
560 326 void FindActiveValues<TreeT>::activeTiles(const NodeT* node, const CoordBBox &bbox, std::vector<TileDataT> &tiles) const
561 {
562 // Generate a bit masks
563 326 auto mask = this->getBBoxMask(bbox, node);
564 326 const auto childMask = mask & node->getChildMask();// prune the child mask with the bbox mask
565 326 mask &= node->getValueMask();// prune active tile mask with the bbox mask
566
567 if (NodeT::LEVEL > 1) {// Only check child nodes if they are NOT leaf nodes
568 54 const auto* table = node->getTable();
569
2/2
✓ Branch 1 taken 136 times.
✓ Branch 2 taken 27 times.
 380 for (auto i = childMask.beginOn(); i; ++i) this->activeTiles(table[i.pos()].getChild(), bbox, tiles);
570 }
571
572 326 const size_t tileCount = mask.countOn();
573
2/2
✓ Branch 0 taken 154 times.
✓ Branch 1 taken 9 times.
 326 if (tileCount < 8) {// Serial processing of active tiles
574
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 154 times.
 616 for (auto iter = mask.beginOn(); iter; ++iter) {
575 ✗ tiles.emplace_back(*node, iter.pos());
576 ✗ tiles.back().bbox.intersect(bbox);
577 }
578 } else {// Parallel processing of active tiles
579 18 std::vector<TileDataT> tmp( tileCount );// for temporary thread-safe processing
580 int n = 0;
581
2/2
✓ Branch 1 taken 82 times.
✓ Branch 2 taken 9 times.
 200 for (auto iter = mask.beginOn(); iter; ++iter) tmp[n++].level = iter.pos();// placeholder to support multi-threading
582
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 112 tbb::parallel_for(tbb::blocked_range<size_t>(0, tileCount, 8), [&](const tbb::blocked_range<size_t>& r) {
583
4/32
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 18 times.
✓ Branch 9 taken 4 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✓ Branch 24 taken 64 times.
✓ Branch 25 taken 8 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
 94 for ( size_t i = r.begin(); i != r.end(); ++i ) {
584 82 tmp[i] = TileDataT(*node, tmp[i].level);
585 82 tmp[i].bbox.intersect(bbox);
586 }
587 });
588
2/6
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 18 tiles.insert(tiles.end(), tmp.begin(), tmp.end());
589 }
590 }
591
592 template<typename TreeT>
593 struct FindActiveValues<TreeT>::RootChild
594 {
595 const CoordBBox bbox;
596 const RootChildType* child;
597 621 RootChild(const Coord& ijk = Coord(), const RootChildType* ptr = nullptr)
598 621 : bbox(CoordBBox::createCube(ijk, RootChildType::DIM)), child(ptr)
599 {
600 621 }
601 };// RootChild struct
602
603 //////////////////////////////////////////////////////////////////////////////////////////
604
605 template<typename ValueType>
606 struct TileData
607 {
608 CoordBBox bbox;
609 ValueType value;
610 Index level;
611 bool state;
612
613 /// @brief Default constructor
614 82 TileData() = default;
615
616 /// @brief Member data constructor
617 ✗ TileData(const CoordBBox &b, const ValueType &v, Index l, bool active = true)
618 ✗ : bbox(b), value(v), level(l), state(active) {}
619
620 /// @brief Constructor from a parent node and the linear offset to one of its tiles
621 ///
622 /// @warning This is an expert-only method since it assumes the linear offset to be valid,
623 /// i.e. within the rand of the dimension of the parent node and NOT corresponding
624 /// to a child node.
625 template <typename ParentNodeT>
626 164 TileData(const ParentNodeT &parent, Index childIdx)
627 164 : bbox(CoordBBox::createCube(parent.offsetToGlobalCoord(childIdx), parent.getChildDim()))
628 , level(parent.getLevel())
629 164 , state(true)
630 {
631
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82 times.
 164 assert(childIdx < ParentNodeT::NUM_VALUES);
632
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82 times.
 164 assert(parent.isChildMaskOff(childIdx));
633
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 82 times.
 164 assert(parent.isValueMaskOn(childIdx));
634 164 value = parent.getTable()[childIdx].getValue();
635 }
636
637 /// @brief Constructor form a parent node, the coordinate of the origin of one of its tiles,
638 /// and said tiles value.
639 template <typename ParentNodeT>
640 ✗ TileData(const ParentNodeT &parent, const Coord &ijk, const ValueType &v)
641 ✗ : bbox(CoordBBox::createCube(ijk, parent.getChildDim()))
642 , value(v)
643 , level(parent.getLevel())
644 ✗ , state(true)
645 {
646 }
647 };// TileData struct
648
649 //////////////////////////////////////////////////////////////////////////////////////////
650
651 // Implementation of stand-alone function
652 template<typename TreeT>
653 bool
654 142 anyActiveValues(const TreeT& tree, const CoordBBox &bbox)
655 {
656 284 FindActiveValues<TreeT> op(tree);
657
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 284 return op.anyActiveValues(bbox);
658 }
659
660 // Implementation of stand-alone function
661 template<typename TreeT>
662 bool
663 14 anyActiveVoxels(const TreeT& tree, const CoordBBox &bbox)
664 {
665 28 FindActiveValues<TreeT> op(tree);
666
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 28 return op.anyActiveVoxels(bbox);
667 }
668
669 // Implementation of stand-alone function
670 template<typename TreeT>
671 bool
672 12 anyActiveTiles(const TreeT& tree, const CoordBBox &bbox)
673 {
674 24 FindActiveValues<TreeT> op(tree);
675 12 return op.anyActiveTiles(bbox);
676 }
677
678 // Implementation of stand-alone function
679 template<typename TreeT>
680 bool
681 6 noActiveValues(const TreeT& tree, const CoordBBox &bbox)
682 {
683 12 FindActiveValues<TreeT> op(tree);
684 6 return op.noActiveValues(bbox);
685 }
686
687 // Implementation of stand-alone function
688 template<typename TreeT>
689 Index64
690 ✗ countActiveValues(const TreeT& tree, const CoordBBox &bbox)
691 {
692 ✗ return tools::countActiveVoxels(tree, bbox);
693 }
694
695 // Implementation of stand-alone function
696 template<typename TreeT>
697 std::vector<TileData<typename TreeT::ValueType>>
698 6 activeTiles(const TreeT& tree, const CoordBBox &bbox)
699 {
700 12 FindActiveValues<TreeT> op(tree);
701 12 return op.activeTiles(bbox);
702 }
703
704
705 ////////////////////////////////////////
706
707
708 // Explicit Template Instantiation
709
710 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
711
712 #ifdef OPENVDB_INSTANTIATE_FINDACTIVEVALUES
713 #include <openvdb/util/ExplicitInstantiation.h>
714 #endif
715
716 #define _FUNCTION(TreeT) \
717 bool anyActiveValues(const TreeT&, const CoordBBox&)
718 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
719 #undef _FUNCTION
720
721 #define _FUNCTION(TreeT) \
722 bool anyActiveVoxels(const TreeT&, const CoordBBox&)
723 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
724 #undef _FUNCTION
725
726 #define _FUNCTION(TreeT) \
727 bool anyActiveTiles(const TreeT&, const CoordBBox&)
728 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
729 #undef _FUNCTION
730
731 #define _FUNCTION(TreeT) \
732 bool noActiveValues(const TreeT&, const CoordBBox&)
733 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
734 #undef _FUNCTION
735
736 #define _FUNCTION(TreeT) \
737 Index64 countActiveValues(const TreeT&, const CoordBBox&)
738 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
739 #undef _FUNCTION
740
741 #define _FUNCTION(TreeT) \
742 std::vector<TileData<TreeT::ValueType>> activeTiles(const TreeT&, const CoordBBox&)
743 OPENVDB_VOLUME_TREE_INSTANTIATE(_FUNCTION)
744 #undef _FUNCTION
745
746 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
747
748
749 } // namespace tools
750 } // namespace OPENVDB_VERSION_NAME
751 } // namespace openvdb
752
753 #endif // OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
754