22 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
23 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
33 #include <tbb/blocked_range.h>
34 #include <tbb/parallel_for.h>
35 #include <tbb/parallel_reduce.h>
46 template<
typename ValueType>
58 template<
typename TreeT>
74 template<
typename TreeT>
87 template<
typename TreeT>
100 template<
typename TreeT>
113 template<
typename TreeT>
126 template<
typename TreeT>
127 std::vector<TileData<typename TreeT::ValueType>>
139 template<
typename TreeT>
153 void update(
const TreeT& tree);
188 void init(
const TreeT &tree);
190 template<
typename NodeT>
191 typename NodeT::NodeMaskType getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
const;
197 void activeTiles(
const typename TreeT::LeafNodeType*,
const CoordBBox&, std::vector<TileDataT>&)
const {;}
201 template<
typename NodeT>
203 template<
typename NodeT>
205 template<
typename NodeT>
207 template<
typename NodeT>
208 void activeTiles(
const NodeT* node,
const CoordBBox &bbox, std::vector<TileDataT> &tiles)
const;
209 template<
typename NodeT>
213 using RootChildType =
typename TreeT::RootNodeType::ChildNodeType;
218 std::vector<TileDataT> mRootTiles;
219 std::vector<RootChild> mRootNodes;
225 template<
typename TreeT>
231 template<
typename TreeT>
237 template<
typename TreeT>
245 template<
typename TreeT>
252 template<
typename TreeT>
253 void FindActiveValues<TreeT>::init(
const TreeT& tree)
255 const auto &root = tree.root();
256 for (
auto i = root.cbeginChildOn(); i; ++i) {
257 mRootNodes.emplace_back(i.getCoord(), &*i);
259 for (
auto i = root.cbeginValueOn(); i; ++i) {
260 mRootTiles.emplace_back(root, i.getCoord(), *i);
264 template<
typename TreeT>
269 if (mAcc.isValueOn( (bbox.min() + bbox.max())>>1 ))
return true;
271 if (mAcc.tree().isValueOn( (bbox.min() + bbox.max())>>1 ))
return true;
274 for (
auto& tile : mRootTiles) {
275 if (tile.bbox.hasOverlap(bbox))
return true;
277 for (
auto& node : mRootNodes) {
278 if (!node.bbox.hasOverlap(bbox)) {
280 }
else if (node.bbox.isInside(bbox)) {
289 template<
typename TreeT>
292 for (
auto& node : mRootNodes) {
293 if (!node.bbox.hasOverlap(bbox)) {
295 }
else if (node.bbox.isInside(bbox)) {
304 template<
typename TreeT>
307 for (
auto& tile : mRootTiles) {
308 if (tile.bbox.hasOverlap(bbox))
return true;
310 for (
auto& node : mRootNodes) {
311 if (!node.bbox.hasOverlap(bbox)) {
313 }
else if (node.bbox.isInside(bbox)) {
322 template<
typename TreeT>
326 for (
auto& tile : mRootTiles) {
327 if (!tile.bbox.hasOverlap(bbox)) {
329 }
else if (tile.bbox.isInside(bbox)) {
330 return bbox.volume();
331 }
else if (bbox.isInside(tile.bbox)) {
332 count += RootChildType::NUM_VOXELS;
334 auto tmp = tile.bbox;
336 count += tmp.volume();
339 for (
auto &node : mRootNodes) {
340 if ( !node.bbox.hasOverlap(bbox) ) {
342 }
else if ( node.bbox.isInside(bbox) ) {
343 return this->
count(node.child, bbox);
345 count += this->
count(node.child, bbox);
351 template<
typename TreeT>
352 std::vector<TileData<typename TreeT::ValueType> >
355 std::vector<TileDataT> tiles;
356 for (
auto& tile : mRootTiles) {
357 if (!tile.bbox.hasOverlap(bbox)) {
359 }
else if (tile.bbox.isInside(bbox)) {
360 tiles.emplace_back(bbox, tile.value, tile.level);
362 }
else if (bbox.isInside(tile.bbox)) {
363 tiles.push_back(tile);
365 auto tmp = tile.bbox;
367 tiles.emplace_back(tmp, tile.value, tile.level);
370 for (
auto &node : mRootNodes) {
371 if ( !node.bbox.hasOverlap(bbox) ) {
373 }
else if ( node.bbox.isInside(bbox) ) {
383 template<
typename TreeT>
384 template<
typename NodeT>
387 typename NodeT::NodeMaskType
mask;
388 auto b = node->getNodeBoundingBox();
389 assert( bbox.hasOverlap(
b) );
390 if ( bbox.isInside(
b) ) {
395 b.min() &= NodeT::DIM-1u;
396 b.min() >>= NodeT::ChildNodeType::TOTAL;
397 b.max() &= NodeT::DIM-1u;
398 b.max() >>= NodeT::ChildNodeType::TOTAL;
399 assert(
b.hasVolume() );
401 for (
const Coord& ijk = *it; it; ++it) {
402 mask.setOn(ijk[2] + (ijk[1] << NodeT::LOG2DIM) + (ijk[0] << 2*NodeT::LOG2DIM));
408 template<
typename TreeT>
409 template<
typename NodeT>
413 auto mask = this->getBBoxMask(bbox, node);
416 const auto tmp = mask & node->getValueMask();
417 if (!tmp.isOff())
return true;
420 mask &= node->getChildMask();
421 const auto*
table = node->getTable();
423 for (
auto i = mask.beginOn(); !active && i; ++i) {
429 template<
typename TreeT>
430 template<
typename NodeT>
434 auto mask = this->getBBoxMask(bbox, node);
437 mask &= node->getChildMask();
438 const auto*
table = node->getTable();
440 for (
auto i = mask.beginOn(); !active && i; ++i) {
446 template<
typename TreeT>
449 const auto &mask = leaf->getValueMask();
452 if (bbox.isInside(leaf->getNodeBoundingBox()))
return !mask.isOff();
453 if (mask.isOn())
return true;
456 for (
auto i = leaf->cbeginValueOn(); !active && i; ++i) {
457 active = bbox.isInside(i.getCoord());
462 template<
typename TreeT>
463 template<
typename NodeT>
467 auto mask = this->getBBoxMask(bbox, node);
470 const auto tmp = mask & node->getValueMask();
471 if (!tmp.isOff())
return true;
474 if (NodeT::LEVEL>1) {
475 mask &= node->getChildMask();
476 const auto*
table = node->getTable();
477 for (
auto i = mask.beginOn(); !active && i; ++i) {
484 template<
typename TreeT>
488 auto b = leaf->getNodeBoundingBox();
489 if (
b.isInside(bbox)) {
490 count = leaf->onVoxelCount();
491 }
else if (leaf->isDense()) {
494 }
else if (
b.hasOverlap(bbox)) {
495 for (
auto i = leaf->cbeginValueOn(); i; ++i) {
496 if (bbox.isInside(i.getCoord())) ++
count;
502 template<
typename TreeT>
503 template<
typename NodeT>
509 auto mask = this->getBBoxMask(bbox, node);
510 const auto childMask = mask & node->getChildMask();
511 mask &= node->getValueMask();
512 const auto*
table = node->getTable();
515 using ChildT =
typename NodeT::ChildNodeType;
516 using RangeT = tbb::blocked_range<typename std::vector<const ChildT*>::iterator>;
517 std::vector<const ChildT*> childNodes(childMask.countOn());
519 for (
auto i = childMask.beginOn(); i; ++i, ++
j) childNodes[j] =
table[i.pos()].getChild();
520 count += tbb::parallel_reduce( RangeT(childNodes.begin(), childNodes.end()), 0,
521 [&](
const RangeT&
r,
Index64 sum)->Index64 {
522 for (
auto i =
r.begin(); i !=
r.end(); ++i ) sum += this->
count(*i, bbox);
529 std::vector<Coord>
coords(mask.countOn());
530 using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
532 for (
auto i = mask.beginOn(); i; ++i, ++
j)
coords[j] = node->offsetToGlobalCoord(i.pos());
533 count += tbb::parallel_reduce( RangeT(
coords.begin(),
coords.end()), 0,
534 [&bbox](
const RangeT&
r,
Index64 sum)->Index64 {
535 for (
auto i =
r.begin(); i !=
r.end(); ++i ) {
536 auto b = CoordBBox::createCube(*i, NodeT::ChildNodeType::DIM);
549 template<
typename TreeT>
550 template<
typename NodeT>
554 auto mask = this->getBBoxMask(bbox, node);
555 const auto childMask = mask & node->getChildMask();
556 mask &= node->getValueMask();
558 if (NodeT::LEVEL > 1) {
559 const auto*
table = node->getTable();
560 for (
auto i = childMask.beginOn(); i; ++i) this->
activeTiles(
table[i.pos()].getChild(), bbox, tiles);
563 const size_t tileCount = mask.countOn();
565 for (
auto iter = mask.beginOn(); iter; ++iter) {
566 tiles.emplace_back(*node, iter.pos());
567 tiles.back().bbox.intersect(bbox);
570 std::vector<TileDataT> tmp( tileCount );
572 for (
auto iter = mask.beginOn(); iter; ++iter) tmp[n++].
level = iter.pos();
573 tbb::parallel_for(tbb::blocked_range<size_t>(0, tileCount, 8), [&](
const tbb::blocked_range<size_t>&
r) {
574 for (
size_t i = r.begin(); i != r.end(); ++i ) {
575 tmp[i] = TileDataT(*node, tmp[i].
level);
576 tmp[i].bbox.intersect(bbox);
579 tiles.insert(tiles.end(), tmp.begin(), tmp.end());
583 template<
typename TreeT>
588 RootChild(
const Coord& ijk = Coord(),
const RootChildType*
ptr =
nullptr)
589 : bbox(
CoordBBox::createCube(ijk, RootChildType::DIM)), child(
ptr)
596 template<
typename ValueType>
616 template <
typename ParentNodeT>
618 : bbox(
CoordBBox::createCube(parent.offsetToGlobalCoord(childIdx), parent.getChildDim()))
622 assert(childIdx < ParentNodeT::NUM_VALUES);
623 assert(parent.isChildMaskOff(childIdx));
624 assert(parent.isValueMaskOn(childIdx));
625 value = parent.getTable()[childIdx].getValue();
630 template <
typename ParentNodeT>
632 : bbox(
CoordBBox::createCube(ijk, parent.getChildDim()))
643 template<
typename TreeT>
652 template<
typename TreeT>
661 template<
typename TreeT>
670 template<
typename TreeT>
679 template<
typename TreeT>
687 template<
typename TreeT>
688 std::vector<TileData<typename TreeT::ValueType>>
701 #ifdef OPENVDB_USE_EXPLICIT_INSTANTIATION
703 #ifdef OPENVDB_INSTANTIATE_FINDACTIVEVALUES
707 #define _FUNCTION(TreeT) \
708 bool anyActiveValues(const TreeT&, const CoordBBox&)
712 #define _FUNCTION(TreeT) \
713 bool anyActiveVoxels(const TreeT&, const CoordBBox&)
717 #define _FUNCTION(TreeT) \
718 bool anyActiveTiles(const TreeT&, const CoordBBox&)
722 #define _FUNCTION(TreeT) \
723 bool noActiveValues(const TreeT&, const CoordBBox&)
727 #define _FUNCTION(TreeT) \
728 Index64 countActiveValues(const TreeT&, const CoordBBox&)
732 #define _FUNCTION(TreeT) \
733 std::vector<TileData<TreeT::ValueType>> activeTiles(const TreeT&, const CoordBBox&)
737 #endif // OPENVDB_USE_EXPLICIT_INSTANTIATION
744 #endif // OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
void parallel_for(int64_t start, int64_t end, std::function< void(int64_t index)> &&task, parallel_options opt=parallel_options(0, Split_Y, 1))
GLboolean GLboolean GLboolean GLboolean a
#define OPENVDB_USE_VERSION_NAMESPACE
The Value Accessor Implementation and API methods. The majoirty of the API matches the API of a compa...
ValueAccessors are designed to help accelerate accesses into the OpenVDB Tree structures by storing c...
Functions to count tiles, nodes or voxels in a grid.
#define OPENVDB_VOLUME_TREE_INSTANTIATE(Function)
GLboolean GLboolean GLboolean b
GLenum GLenum GLsizei void * table
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate active
Library and file format version numbers.
ValueAccessorImpl< TreeType, IsSafe, MutexType, openvdb::make_index_sequence< CacheLevels >> ValueAccessor
Default alias for a ValueAccessor. This is simply a helper alias for the generic definition but takes...
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.