40 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED 41 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED 48 #include <tbb/blocked_range.h> 49 #include <tbb/parallel_reduce.h> 65 template<
typename TreeT>
78 template<
typename TreeT>
91 template<
typename TreeT>
104 template<
typename TreeT>
116 void update(
const TreeT& tree);
123 bool any(
const CoordBBox &bbox,
bool useAccessor =
false)
const;
130 bool none(
const CoordBBox &bbox,
bool useAccessor =
false)
const {
return !this->any(bbox, useAccessor); }
141 void init(
const TreeT &tree);
143 template<
typename NodeT>
144 typename NodeT::NodeMaskType getBBoxMask(
const CoordBBox &bbox,
const NodeT* node)
const;
147 inline bool any(
const typename TreeT::LeafNodeType* leaf,
const CoordBBox &bbox )
const;
150 inline Index64 count(
const typename TreeT::LeafNodeType* leaf,
const CoordBBox &bbox )
const;
153 template<
typename NodeT>
154 bool any(
const NodeT* node,
const CoordBBox &bbox)
const;
157 template<
typename NodeT>
161 using RootChildT =
typename TreeT::RootNodeType::ChildNodeType;
166 std::vector<CoordBBox> mRootTiles;
167 std::vector<NodePairT> mRootNodes;
173 template<
typename TreeT>
179 template<
typename TreeT>
185 template<
typename TreeT>
193 template<
typename TreeT>
200 template<
typename TreeT>
203 for (
auto i = tree.root().cbeginChildOn(); i; ++i) {
204 mRootNodes.emplace_back(i.getCoord(), &*i);
206 for (
auto i = tree.root().cbeginValueOn(); i; ++i) {
211 template<
typename TreeT>
217 if (mAcc.
tree().isValueOn( (bbox.
min() + bbox.
max())>>1 ))
return true;
220 for (
auto& tile : mRootTiles) {
221 if (tile.hasOverlap(bbox))
return true;
223 for (
auto& node : mRootNodes) {
224 if (!node.bbox.hasOverlap(bbox)) {
226 }
else if (node.bbox.isInside(bbox)) {
227 return this->
any(node.child, bbox);
228 }
else if (this->
any(node.child, bbox)) {
235 template<
typename TreeT>
239 for (
auto& tile : mRootTiles) {
240 if (!tile.hasOverlap(bbox)) {
242 }
else if (tile.isInside(bbox)) {
245 count += RootChildT::NUM_VOXELS;
249 count += tmp.volume();
252 for (
auto &node : mRootNodes) {
253 if ( !node.bbox.hasOverlap(bbox) ) {
255 }
else if ( node.bbox.isInside(bbox) ) {
256 return this->
count(node.child, bbox);
258 count += this->
count(node.child, bbox);
264 template<
typename TreeT>
265 template<
typename NodeT>
268 typename NodeT::NodeMaskType mask;
269 auto b = node->getNodeBoundingBox();
275 b.min() &= NodeT::DIM-1u;
276 b.min() >>= NodeT::ChildNodeType::TOTAL;
277 b.max() &= NodeT::DIM-1u;
278 b.max() >>= NodeT::ChildNodeType::TOTAL;
279 assert( b.hasVolume() );
281 for (
const Coord& x = *it; it; ++it) {
282 mask.setOn(x[2] + (x[1] << NodeT::LOG2DIM) + (x[0] << 2*NodeT::LOG2DIM));
288 template<
typename TreeT>
289 template<
typename NodeT>
293 auto mask = this->getBBoxMask(bbox, node);
296 const auto tmp = mask & node->getValueMask();
297 if (!tmp.isOff())
return true;
300 mask &= node->getChildMask();
301 const auto* table = node->getTable();
303 for (
auto i = mask.beginOn(); !test && i; ++i) {
304 test = this->
any(table[i.pos()].getChild(), bbox);
309 template<
typename TreeT>
312 bool test = leaf->getValueMask().isOn();
314 for (
auto i = leaf->cbeginValueOn(); !test && i; ++i) {
320 template<
typename TreeT>
324 if (leaf->getValueMask().isOn()) {
325 auto b = leaf->getNodeBoundingBox();
329 for (
auto i = leaf->cbeginValueOn(); i; ++i) {
336 template<
typename TreeT>
337 template<
typename NodeT>
343 auto mask = this->getBBoxMask(bbox, node);
344 const auto childMask = mask & node->getChildMask();
345 mask &= node->getValueMask();
346 const auto* table = node->getTable();
349 using ChildT =
typename NodeT::ChildNodeType;
350 using RangeT = tbb::blocked_range<typename std::vector<const ChildT*>::iterator>;
351 std::vector<const ChildT*> childNodes(childMask.countOn());
353 for (
auto i = childMask.beginOn(); i; ++i, ++j) childNodes[j] = table[i.pos()].getChild();
354 count += tbb::parallel_reduce( RangeT(childNodes.begin(), childNodes.end()), 0,
355 [&](
const RangeT& r,
Index64 sum)->Index64 {
356 for (
auto i = r.begin(); i != r.end(); ++i ) sum += this->
count(*i, bbox);
363 std::vector<Coord> coords(mask.countOn());
364 using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
366 for (
auto i = mask.beginOn(); i; ++i, ++j) coords[j] = node->offsetToGlobalCoord(i.pos());
367 count += tbb::parallel_reduce( RangeT(coords.begin(), coords.end()), 0,
368 [&bbox](
const RangeT& r,
Index64 sum)->Index64 {
369 for (
auto i = r.begin(); i != r.end(); ++i ) {
382 template<
typename TreeT>
388 : child(p), bbox(
CoordBBox::createCube(c, RootChildT::DIM))
396 template<
typename TreeT>
405 template<
typename TreeT>
410 return op.
none(bbox);
414 template<
typename TreeT>
419 return op.
count(bbox);
426 #endif // OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
const Coord & max() const
Definition: Coord.h:349
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:52
bool isInside(const Coord &xyz) const
Return true if point (x, y, z) is inside this bounding box.
Definition: Coord.h:427
const Coord & min() const
Definition: Coord.h:348
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
bool isValueOn(const Coord &xyz) const
Return the active state of the voxel at the given coordinates.
Definition: ValueAccessor.h:264
Axis-aligned bounding box of signed integer coordinates.
Definition: Coord.h:275
Definition: Exceptions.h:40
bool hasOverlap(const CoordBBox &b) const
Return true if the given bounding box overlaps with this bounding box.
Definition: Coord.h:439
uint64_t Index64
Definition: Types.h:60
Library and file format version numbers.
TreeType & tree() const
Return a reference to the tree associated with this accessor.
Definition: ValueAccessor.h:148
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
Index64 volume() const
Return the integer volume of coordinates spanned by this bounding box.
Definition: Coord.h:412
static CoordBBox createCube(const Coord &min, ValueType dim)
Definition: Coord.h:340