22 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
23 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
30 #include <tbb/blocked_range.h>
31 #include <tbb/parallel_reduce.h>
42 template<
typename ValueType>
54 template<
typename TreeT>
70 template<
typename TreeT>
83 template<
typename TreeT>
96 template<
typename TreeT>
109 template<
typename TreeT>
122 template<
typename TreeT>
123 inline std::vector<TileData<typename TreeT::ValueType>>
124 activeTiles(
const TreeT& tree,
const CoordBBox &bbox);
135 template<
typename TreeT>
149 void update(
const TreeT& tree);
178 [[deprecated(
"Use anyActiveValues() instead")]]
inline bool any(
const CoordBBox &bbox,
bool useAccessor =
false)
const
182 [[deprecated(
"Use noActiveValues() instead")]]
inline bool none(
const CoordBBox &bbox,
bool useAccessor =
false)
const
193 void init(
const TreeT &tree);
195 template<
typename NodeT>
196 typename NodeT::NodeMaskType getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
const;
202 void activeTiles(
const typename TreeT::LeafNodeType*,
const CoordBBox&, std::vector<TileDataT>&)
const {;}
203 inline Index64 count(
const typename TreeT::LeafNodeType* leaf,
const CoordBBox &bbox )
const;
206 template<
typename NodeT>
208 template<
typename NodeT>
210 template<
typename NodeT>
211 bool anyActiveTiles(
const NodeT* node,
const CoordBBox &bbox)
const;
212 template<
typename NodeT>
213 void activeTiles(
const NodeT* node,
const CoordBBox &bbox, std::vector<TileDataT> &tiles)
const;
214 template<
typename NodeT>
215 Index64 count(
const NodeT* node,
const CoordBBox &bbox)
const;
217 using AccT = tree::ValueAccessor<
const TreeT,
false>;
218 using RootChildType =
typename TreeT::RootNodeType::ChildNodeType;
223 std::vector<TileDataT> mRootTiles;
224 std::vector<RootChild> mRootNodes;
230 template<
typename TreeT>
236 template<
typename TreeT>
242 template<
typename TreeT>
250 template<
typename TreeT>
257 template<
typename TreeT>
258 void FindActiveValues<TreeT>::init(
const TreeT& tree)
260 const auto &root = tree.root();
261 for (
auto i = root.cbeginChildOn(); i; ++i) {
262 mRootNodes.emplace_back(i.getCoord(), &*i);
264 for (
auto i = root.cbeginValueOn(); i; ++i) {
265 mRootTiles.emplace_back(root, i.getCoord(), *i);
269 template<
typename TreeT>
274 if (mAcc.isValueOn( (bbox.
min() + bbox.
max())>>1 ))
return true;
276 if (mAcc.tree().isValueOn( (bbox.
min() + bbox.
max())>>1 ))
return true;
279 for (
auto& tile : mRootTiles) {
280 if (tile.bbox.hasOverlap(bbox))
return true;
282 for (
auto& node : mRootNodes) {
283 if (!node.bbox.hasOverlap(bbox)) {
285 }
else if (node.bbox.isInside(bbox)) {
294 template<
typename TreeT>
297 for (
auto& node : mRootNodes) {
298 if (!node.bbox.hasOverlap(bbox)) {
300 }
else if (node.bbox.isInside(bbox)) {
309 template<
typename TreeT>
312 for (
auto& tile : mRootTiles) {
313 if (tile.bbox.hasOverlap(bbox))
return true;
315 for (
auto& node : mRootNodes) {
316 if (!node.bbox.hasOverlap(bbox)) {
318 }
else if (node.bbox.isInside(bbox)) {
327 template<
typename TreeT>
331 for (
auto& tile : mRootTiles) {
332 if (!tile.bbox.hasOverlap(bbox)) {
334 }
else if (tile.bbox.isInside(bbox)) {
336 }
else if (bbox.
isInside(tile.bbox)) {
337 count += RootChildType::NUM_VOXELS;
339 auto tmp = tile.bbox;
341 count += tmp.volume();
344 for (
auto &node : mRootNodes) {
345 if ( !node.bbox.hasOverlap(bbox) ) {
347 }
else if ( node.bbox.isInside(bbox) ) {
348 return this->count(node.child, bbox);
350 count += this->count(node.child, bbox);
356 template<
typename TreeT>
357 std::vector<TileData<typename TreeT::ValueType> >
360 std::vector<TileDataT> tiles;
361 for (
auto& tile : mRootTiles) {
362 if (!tile.bbox.hasOverlap(bbox)) {
364 }
else if (tile.bbox.isInside(bbox)) {
365 tiles.emplace_back(bbox, tile.value, tile.level);
367 }
else if (bbox.
isInside(tile.bbox)) {
368 tiles.push_back(tile);
370 auto tmp = tile.bbox;
372 tiles.emplace_back(tmp, tile.value, tile.level);
375 for (
auto &node : mRootNodes) {
376 if ( !node.bbox.hasOverlap(bbox) ) {
378 }
else if ( node.bbox.isInside(bbox) ) {
388 template<
typename TreeT>
389 template<
typename NodeT>
392 typename NodeT::NodeMaskType mask;
393 auto b = node->getNodeBoundingBox();
400 b.min() &= NodeT::DIM-1u;
401 b.min() >>= NodeT::ChildNodeType::TOTAL;
402 b.max() &= NodeT::DIM-1u;
403 b.max() >>= NodeT::ChildNodeType::TOTAL;
404 assert( b.hasVolume() );
406 for (
const Coord& ijk = *it; it; ++it) {
407 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
413 template<
typename TreeT>
414 template<
typename NodeT>
418 auto mask = this->getBBoxMask(bbox, node);
421 const auto tmp = mask & node->getValueMask();
422 if (!tmp.isOff())
return true;
425 mask &= node->getChildMask();
426 const auto* table = node->getTable();
428 for (
auto i = mask.beginOn(); !active && i; ++i) {
434 template<
typename TreeT>
435 template<
typename NodeT>
439 auto mask = this->getBBoxMask(bbox, node);
442 mask &= node->getChildMask();
443 const auto* table = node->getTable();
445 for (
auto i = mask.beginOn(); !active && i; ++i) {
451 template<
typename TreeT>
454 const auto &mask = leaf->getValueMask();
457 if (bbox.isInside(leaf->getNodeBoundingBox()))
return !mask.isOff();
458 if (mask.isOn())
return true;
461 for (
auto i = leaf->cbeginValueOn(); !active && i; ++i) {
462 active = bbox.isInside(i.getCoord());
467 template<
typename TreeT>
468 template<
typename NodeT>
472 auto mask = this->getBBoxMask(bbox, node);
475 const auto tmp = mask & node->getValueMask();
476 if (!tmp.isOff())
return true;
479 if (NodeT::LEVEL>1) {
480 mask &= node->getChildMask();
481 const auto* table = node->getTable();
482 for (
auto i = mask.beginOn(); !active && i; ++i) {
489 template<
typename TreeT>
493 if (leaf->getValueMask().isOn()) {
494 auto b = leaf->getNodeBoundingBox();
498 for (
auto i = leaf->cbeginValueOn(); i; ++i) {
499 if (bbox.isInside(i.getCoord())) ++count;
505 template<
typename TreeT>
506 template<
typename NodeT>
512 auto mask = this->getBBoxMask(bbox, node);
513 const auto childMask = mask & node->getChildMask();
514 mask &= node->getValueMask();
515 const auto* table = node->getTable();
518 using ChildT =
typename NodeT::ChildNodeType;
519 using RangeT = tbb::blocked_range<typename std::vector<const ChildT*>::iterator>;
520 std::vector<const ChildT*> childNodes(childMask.countOn());
522 for (
auto i = childMask.beginOn(); i; ++i, ++j) childNodes[j] = table[i.pos()].getChild();
523 count += tbb::parallel_reduce( RangeT(childNodes.begin(), childNodes.end()), 0,
524 [&](
const RangeT& r,
Index64 sum)->Index64 {
525 for ( auto i = r.begin(); i != r.end(); ++i ) sum += this->count(*i, bbox);
532 std::vector<Coord> coords(mask.countOn());
533 using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
535 for (
auto i = mask.beginOn(); i; ++i, ++j) coords[j] = node->offsetToGlobalCoord(i.pos());
536 count += tbb::parallel_reduce( RangeT(coords.begin(), coords.end()), 0,
537 [&bbox](
const RangeT& r,
Index64 sum)->Index64 {
538 for ( auto i = r.begin(); i != r.end(); ++i ) {
539 auto b = CoordBBox::createCube(*i, NodeT::ChildNodeType::DIM);
552 template<
typename TreeT>
553 template<
typename NodeT>
557 auto mask = this->getBBoxMask(bbox, node);
558 const auto childMask = mask & node->getChildMask();
559 mask &= node->getValueMask();
561 if (NodeT::LEVEL > 1) {
562 const auto* table = node->getTable();
563 for (
auto i = childMask.beginOn(); i; ++i) this->
activeTiles(table[i.pos()].getChild(), bbox, tiles);
566 const size_t tileCount = mask.countOn();
568 for (
auto iter = mask.beginOn(); iter; ++iter) {
569 tiles.emplace_back(*node, iter.pos());
570 tiles.back().bbox.intersect(bbox);
573 std::vector<TileDataT> tmp( tileCount );
575 for (
auto iter = mask.beginOn(); iter; ++iter) tmp[n++].level = iter.pos();
576 tbb::parallel_for(tbb::blocked_range<size_t>(0, tileCount, 8), [&](
const tbb::blocked_range<size_t>& r) {
577 for (
size_t i = r.begin(); i != r.end(); ++i ) {
578 tmp[i] = TileDataT(*node, tmp[i].level);
579 tmp[i].bbox.intersect(bbox);
582 tiles.insert(tiles.end(), tmp.begin(), tmp.end());
586 template<
typename TreeT>
592 : bbox(
CoordBBox::createCube(ijk, RootChildType::DIM)), child(ptr)
599 template<
typename ValueType>
612 : bbox(b), value(v), level(l), state(active) {}
619 template <
typename ParentNodeT>
621 : bbox(
CoordBBox::createCube(parent.offsetToGlobalCoord(childIdx), parent.getChildDim()))
625 assert(childIdx < ParentNodeT::NUM_VALUES);
626 assert(parent.isChildMaskOff(childIdx));
627 assert(parent.isValueMaskOn(childIdx));
628 value = parent.getTable()[childIdx].getValue();
633 template <
typename ParentNodeT>
635 : bbox(
CoordBBox::createCube(ijk, parent.getChildDim()))
646 template<
typename TreeT>
655 template<
typename TreeT>
664 template<
typename TreeT>
673 template<
typename TreeT>
682 template<
typename TreeT>
687 return op.
count(bbox);
691 template<
typename TreeT>
692 inline std::vector<TileData<typename TreeT::ValueType>>
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:249
const Coord & min() const
Definition: Coord.h:321
const Coord & max() const
Definition: Coord.h:322
bool hasOverlap(const CoordBBox &b) const
Return true if the given bounding box overlaps with this bounding box.
Definition: Coord.h:412
Index64 volume() const
Return the integer volume of coordinates spanned by this bounding box.
Definition: Coord.h:385
bool isInside(const Coord &xyz) const
Return true if point (x, y, z) is inside this bounding box.
Definition: Coord.h:400
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:26
Level getLevel()
Return the current logging level.
Definition: logging.h:138
Index32 Index
Definition: openvdb/Types.h:32
uint64_t Index64
Definition: openvdb/Types.h:31
Definition: openvdb/Exceptions.h:13
Library and file format version numbers.
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:101
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:153