22 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
23 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
26 #include <openvdb/version.h>
32 #include <tbb/blocked_range.h>
33 #include <tbb/parallel_for.h>
34 #include <tbb/parallel_reduce.h>
45 template<
typename ValueType>
57 template<
typename TreeT>
73 template<
typename TreeT>
86 template<
typename TreeT>
99 template<
typename TreeT>
112 template<
typename TreeT>
125 template<
typename TreeT>
126 inline std::vector<TileData<typename TreeT::ValueType>>
127 activeTiles(
const TreeT& tree,
const CoordBBox &bbox);
138 template<
typename TreeT>
152 void update(
const TreeT& tree);
196 void init(
const TreeT &tree);
198 template<
typename NodeT>
199 typename NodeT::NodeMaskType getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
const;
205 void activeTiles(
const typename TreeT::LeafNodeType*,
const CoordBBox&, std::vector<TileDataT>&)
const {;}
206 inline Index64 count(
const typename TreeT::LeafNodeType* leaf,
const CoordBBox &bbox )
const;
209 template<
typename NodeT>
211 template<
typename NodeT>
213 template<
typename NodeT>
214 bool anyActiveTiles(
const NodeT* node,
const CoordBBox &bbox)
const;
215 template<
typename NodeT>
216 void activeTiles(
const NodeT* node,
const CoordBBox &bbox, std::vector<TileDataT> &tiles)
const;
217 template<
typename NodeT>
218 Index64 count(
const NodeT* node,
const CoordBBox &bbox)
const;
220 using AccT = tree::ValueAccessor<
const TreeT,
false>;
221 using RootChildType =
typename TreeT::RootNodeType::ChildNodeType;
226 std::vector<TileDataT> mRootTiles;
227 std::vector<RootChild> mRootNodes;
233 template<
typename TreeT>
239 template<
typename TreeT>
245 template<
typename TreeT>
253 template<
typename TreeT>
260 template<
typename TreeT>
261 void FindActiveValues<TreeT>::init(
const TreeT& tree)
263 const auto &root = tree.root();
264 for (
auto i = root.cbeginChildOn(); i; ++i) {
265 mRootNodes.emplace_back(i.getCoord(), &*i);
267 for (
auto i = root.cbeginValueOn(); i; ++i) {
268 mRootTiles.emplace_back(root, i.getCoord(), *i);
272 template<
typename TreeT>
277 if (mAcc.isValueOn( (bbox.
min() + bbox.
max())>>1 ))
return true;
279 if (mAcc.tree().isValueOn( (bbox.
min() + bbox.
max())>>1 ))
return true;
282 for (
auto& tile : mRootTiles) {
283 if (tile.bbox.hasOverlap(bbox))
return true;
285 for (
auto& node : mRootNodes) {
286 if (!node.bbox.hasOverlap(bbox)) {
288 }
else if (node.bbox.isInside(bbox)) {
297 template<
typename TreeT>
300 for (
auto& node : mRootNodes) {
301 if (!node.bbox.hasOverlap(bbox)) {
303 }
else if (node.bbox.isInside(bbox)) {
312 template<
typename TreeT>
315 for (
auto& tile : mRootTiles) {
316 if (tile.bbox.hasOverlap(bbox))
return true;
318 for (
auto& node : mRootNodes) {
319 if (!node.bbox.hasOverlap(bbox)) {
321 }
else if (node.bbox.isInside(bbox)) {
330 template<
typename TreeT>
334 for (
auto& tile : mRootTiles) {
335 if (!tile.bbox.hasOverlap(bbox)) {
337 }
else if (tile.bbox.isInside(bbox)) {
339 }
else if (bbox.
isInside(tile.bbox)) {
340 count += RootChildType::NUM_VOXELS;
342 auto tmp = tile.bbox;
344 count += tmp.volume();
347 for (
auto &node : mRootNodes) {
348 if ( !node.bbox.hasOverlap(bbox) ) {
350 }
else if ( node.bbox.isInside(bbox) ) {
351 return this->count(node.child, bbox);
353 count += this->count(node.child, bbox);
359 template<
typename TreeT>
360 std::vector<TileData<typename TreeT::ValueType> >
363 std::vector<TileDataT> tiles;
364 for (
auto& tile : mRootTiles) {
365 if (!tile.bbox.hasOverlap(bbox)) {
367 }
else if (tile.bbox.isInside(bbox)) {
368 tiles.emplace_back(bbox, tile.value, tile.level);
370 }
else if (bbox.
isInside(tile.bbox)) {
371 tiles.push_back(tile);
373 auto tmp = tile.bbox;
375 tiles.emplace_back(tmp, tile.value, tile.level);
378 for (
auto &node : mRootNodes) {
379 if ( !node.bbox.hasOverlap(bbox) ) {
381 }
else if ( node.bbox.isInside(bbox) ) {
391 template<
typename TreeT>
392 template<
typename NodeT>
395 typename NodeT::NodeMaskType mask;
396 auto b = node->getNodeBoundingBox();
403 b.min() &= NodeT::DIM-1u;
404 b.min() >>= NodeT::ChildNodeType::TOTAL;
405 b.max() &= NodeT::DIM-1u;
406 b.max() >>= NodeT::ChildNodeType::TOTAL;
407 assert( b.hasVolume() );
409 for (
const Coord& ijk = *it; it; ++it) {
410 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
416 template<
typename TreeT>
417 template<
typename NodeT>
421 auto mask = this->getBBoxMask(bbox, node);
424 const auto tmp = mask & node->getValueMask();
425 if (!tmp.isOff())
return true;
428 mask &= node->getChildMask();
429 const auto* table = node->getTable();
431 for (
auto i = mask.beginOn(); !active && i; ++i) {
437 template<
typename TreeT>
438 template<
typename NodeT>
442 auto mask = this->getBBoxMask(bbox, node);
445 mask &= node->getChildMask();
446 const auto* table = node->getTable();
448 for (
auto i = mask.beginOn(); !active && i; ++i) {
454 template<
typename TreeT>
457 const auto &mask = leaf->getValueMask();
460 if (bbox.isInside(leaf->getNodeBoundingBox()))
return !mask.isOff();
461 if (mask.isOn())
return true;
464 for (
auto i = leaf->cbeginValueOn(); !active && i; ++i) {
465 active = bbox.isInside(i.getCoord());
470 template<
typename TreeT>
471 template<
typename NodeT>
475 auto mask = this->getBBoxMask(bbox, node);
478 const auto tmp = mask & node->getValueMask();
479 if (!tmp.isOff())
return true;
482 if (NodeT::LEVEL>1) {
483 mask &= node->getChildMask();
484 const auto* table = node->getTable();
485 for (
auto i = mask.beginOn(); !active && i; ++i) {
492 template<
typename TreeT>
496 auto b = leaf->getNodeBoundingBox();
497 if (b.isInside(bbox)) {
498 count = leaf->onVoxelCount();
499 }
else if (leaf->isDense()) {
502 }
else if (b.hasOverlap(bbox)) {
503 for (
auto i = leaf->cbeginValueOn(); i; ++i) {
504 if (bbox.isInside(i.getCoord())) ++count;
510 template<
typename TreeT>
511 template<
typename NodeT>
517 auto mask = this->getBBoxMask(bbox, node);
518 const auto childMask = mask & node->getChildMask();
519 mask &= node->getValueMask();
520 const auto* table = node->getTable();
523 using ChildT =
typename NodeT::ChildNodeType;
524 using RangeT = tbb::blocked_range<typename std::vector<const ChildT*>::iterator>;
525 std::vector<const ChildT*> childNodes(childMask.countOn());
527 for (
auto i = childMask.beginOn(); i; ++i, ++j) childNodes[j] = table[i.pos()].getChild();
528 count += tbb::parallel_reduce( RangeT(childNodes.begin(), childNodes.end()), 0,
529 [&](
const RangeT& r,
Index64 sum)->Index64 {
530 for ( auto i = r.begin(); i != r.end(); ++i ) sum += this->count(*i, bbox);
537 std::vector<Coord> coords(mask.countOn());
538 using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
540 for (
auto i = mask.beginOn(); i; ++i, ++j) coords[j] = node->offsetToGlobalCoord(i.pos());
541 count += tbb::parallel_reduce( RangeT(coords.begin(), coords.end()), 0,
542 [&bbox](
const RangeT& r,
Index64 sum)->Index64 {
543 for ( auto i = r.begin(); i != r.end(); ++i ) {
544 auto b = CoordBBox::createCube(*i, NodeT::ChildNodeType::DIM);
557 template<
typename TreeT>
558 template<
typename NodeT>
562 auto mask = this->getBBoxMask(bbox, node);
563 const auto childMask = mask & node->getChildMask();
564 mask &= node->getValueMask();
566 if (NodeT::LEVEL > 1) {
567 const auto* table = node->getTable();
568 for (
auto i = childMask.beginOn(); i; ++i) this->
activeTiles(table[i.pos()].getChild(), bbox, tiles);
571 const size_t tileCount = mask.countOn();
573 for (
auto iter = mask.beginOn(); iter; ++iter) {
574 tiles.emplace_back(*node, iter.pos());
575 tiles.back().bbox.intersect(bbox);
578 std::vector<TileDataT> tmp( tileCount );
580 for (
auto iter = mask.beginOn(); iter; ++iter) tmp[n++].level = iter.pos();
581 tbb::parallel_for(tbb::blocked_range<size_t>(0, tileCount, 8), [&](
const tbb::blocked_range<size_t>& r) {
582 for (
size_t i = r.begin(); i != r.end(); ++i ) {
583 tmp[i] = TileDataT(*node, tmp[i].level);
584 tmp[i].bbox.intersect(bbox);
587 tiles.insert(tiles.end(), tmp.begin(), tmp.end());
591 template<
typename TreeT>
597 : bbox(
CoordBBox::createCube(ijk, RootChildType::DIM)), child(ptr)
604 template<
typename ValueType>
617 : bbox(b), value(v), level(l), state(active) {}
624 template <
typename ParentNodeT>
626 : bbox(
CoordBBox::createCube(parent.offsetToGlobalCoord(childIdx), parent.getChildDim()))
630 assert(childIdx < ParentNodeT::NUM_VALUES);
631 assert(parent.isChildMaskOff(childIdx));
632 assert(parent.isValueMaskOn(childIdx));
633 value = parent.getTable()[childIdx].getValue();
638 template <
typename ParentNodeT>
640 : bbox(
CoordBBox::createCube(ijk, parent.getChildDim()))
651 template<
typename TreeT>
660 template<
typename TreeT>
669 template<
typename TreeT>
678 template<
typename TreeT>
687 template<
typename TreeT>
695 template<
typename TreeT>
696 inline std::vector<TileData<typename TreeT::ValueType>>
Functions to count tiles, nodes or voxels in a grid.
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:248
const Coord & min() const
Definition: Coord.h:320
const Coord & max() const
Definition: Coord.h:321
bool hasOverlap(const CoordBBox &b) const
Return true if the given bounding box overlaps with this bounding box.
Definition: Coord.h:411
Index64 volume() const
Return the integer volume of coordinates spanned by this bounding box.
Definition: Coord.h:384
bool isInside(const Coord &xyz) const
Return true if point (x, y, z) is inside this bounding box.
Definition: Coord.h:399
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:25
Level getLevel()
Return the current logging level.
Definition: logging.h:141
Index32 Index
Definition: Types.h:54
uint64_t Index64
Definition: Types.h:53
Definition: Exceptions.h:13
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:180