HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
FindActiveValues.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) Ken Museth
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
12 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
13 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
14 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
15 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
16 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
17 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
18 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
19 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
20 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
21 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
23 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
24 //
25 ///////////////////////////////////////////////////////////////////////////
26 //
27 /// @file FindActiveValues.h
28 ///
29 /// @brief Finds the active values in a tree which intersects a bounding box.
30 /// Two methods are provided, one that counts the number of active values
31 /// and one that simply tests if any active values intersect the bbox.
32 ///
33 /// @warning For repeated calls to the free-standing functions defined below
34 /// consider instead creating an instance of FindActiveValues
35 /// and then repeatedly call its member methods. This assumes the tree
36 /// to be constant between calls but is sightly faster.
37 ///
38 /// @author Ken Museth
39 
40 #ifndef OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
41 #define OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
42 
43 #include <vector>
44 #include <openvdb/version.h> // for OPENVDB_VERSION_NAME
45 #include <openvdb/Types.h>
47 
48 #include <tbb/blocked_range.h>
49 #include <tbb/parallel_reduce.h>
50 
51 namespace openvdb {
53 namespace OPENVDB_VERSION_NAME {
54 namespace tools {
55 
56 /// @brief Returns true if the bounding box intersects any of the active
57 /// values in a tree, i.e. either active voxels or active tiles.
58 ///
59 /// @warning For repeated calls to this method consider instead creating an instance of
60 /// FindActiveValues and then repeatedly call any(). This assumes the tree
61 /// to be constant between calls but is slightly faster.
62 ///
63 /// @param tree const tree to be tested for active values.
64 /// @param bbox index bounding box which is intersected against the active values.
65 template<typename TreeT>
66 inline bool
67 anyActiveValues(const TreeT& tree, const CoordBBox &bbox);
68 
69 /// @brief Returns true if the bounding box intersects none of the active
70 /// values in a tree, i.e. neither active voxels or active tiles.
71 ///
72 /// @warning For repeated calls to this method consider instead creating an instance of
73 /// FindActiveValues and then repeatedly call none(). This assumes the tree
74 /// to be constant between calls but is slightly faster.
75 ///
76 /// @param tree const tree to be tested for active values.
77 /// @param bbox index bounding box which is intersected against the active values.
78 template<typename TreeT>
79 inline bool
80 noActiveValues(const TreeT& tree, const CoordBBox &bbox);
81 
82 /// @brief Returns the number of active values that intersects a bounding box intersects,
83 /// i.e. the count includes both active voxels and virtual voxels in active tiles.
84 ///
85 /// @warning For repeated calls to this method consider instead creating an instance of
86 /// FindActiveValues and then repeatedly call count(). This assumes the tree
87 /// to be constant between calls but is slightly faster.
88 ///
89 /// @param tree const tree to be tested for active values.
90 /// @param bbox index bounding box which is intersected against the active values.
91 template<typename TreeT>
92 inline Index64
93 countActiveValues(const TreeT& tree, const CoordBBox &bbox);
94 
95 //////////////////////////////////////////////////////////////////////////////////////////
96 
97 /// @brief Finds the active values in a tree which intersects a bounding box.
98 ///
99 /// @details Two methods are provided, one that count the number of active values
100 /// and one that simply tests if any active values intersect the bbox.
101 ///
102 /// @warning Tree nodes are cached by this class so it's important that the tree is not
103 /// modified after this class is instantiated and before its methods are called.
104 template<typename TreeT>
106 {
107 public:
108 
109  /// @brief Constructor from a const tree, which is assumed not to be modified after construction.
110  FindActiveValues(const TreeT& tree);
111 
112  /// @brief Default destructor
114 
115  /// @brief Initiate this class with a new (or modified) tree.
116  void update(const TreeT& tree);
117 
118  /// @brief Returns true if the specified bounding box intersects any active values.
119  ///
120  /// @warning Using a ValueAccessor (i.e. useAccessor = true) can improve performance for especially
121  /// small bounding boxes, but at the cost of no thread-safety. So if multiple threads are
122  /// calling this method concurrently use the default setting, useAccessor = false.
123  bool any(const CoordBBox &bbox, bool useAccessor = false) const;
124 
125  /// @brief Returns true if the specified bounding box does not intersect any active values.
126  ///
127  /// @warning Using a ValueAccessor (i.e. useAccessor = true) can improve performance for especially
128  /// small bounding boxes, but at the cost of no thread-safety. So if multiple threads are
129  /// calling this method concurrently use the default setting, useAccessor = false.
130  bool none(const CoordBBox &bbox, bool useAccessor = false) const { return !this->any(bbox, useAccessor); }
131 
132  /// @brief Returns the number of active voxels intersected by the specified bounding box.
133  Index64 count(const CoordBBox &bbox) const;
134 
135 private:
136 
137  // Cleans up internal data structures
138  void clear();
139 
140  // builds internal data structures
141  void init(const TreeT &tree);
142 
143  template<typename NodeT>
144  typename NodeT::NodeMaskType getBBoxMask(const CoordBBox &bbox, const NodeT* node) const;
145 
146  // process leaf node
147  inline bool any(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const;
148 
149  // process leaf node
150  inline Index64 count(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const;
151 
152  // process internal node
153  template<typename NodeT>
154  bool any(const NodeT* node, const CoordBBox &bbox) const;
155 
156  // process internal node
157  template<typename NodeT>
158  Index64 count(const NodeT* node, const CoordBBox &bbox) const;
159 
160  using AccT = tree::ValueAccessor<const TreeT, false/* IsSafe */>;
161  using RootChildT = typename TreeT::RootNodeType::ChildNodeType;
162 
163  struct NodePairT;
164 
165  AccT mAcc;
166  std::vector<CoordBBox> mRootTiles;// cache bbox of child nodes (faster to cache than access RootNode)
167  std::vector<NodePairT> mRootNodes;// cache bbox of acive tiles (faster to cache than access RootNode)
168 
169 };// FindActiveValues class
170 
171 //////////////////////////////////////////////////////////////////////////////////////////
172 
173 template<typename TreeT>
174 FindActiveValues<TreeT>::FindActiveValues(const TreeT& tree) : mAcc(tree), mRootTiles(), mRootNodes()
175 {
176  this->init(tree);
177 }
178 
179 template<typename TreeT>
181 {
182  this->clear();
183 }
184 
185 template<typename TreeT>
186 void FindActiveValues<TreeT>::update(const TreeT& tree)
187 {
188  this->clear();
189  mAcc = AccT(tree);
190  this->init(tree);
191 }
192 
193 template<typename TreeT>
195 {
196  mRootNodes.clear();
197  mRootTiles.clear();
198 }
199 
200 template<typename TreeT>
201 void FindActiveValues<TreeT>::init(const TreeT& tree)
202 {
203  for (auto i = tree.root().cbeginChildOn(); i; ++i) {
204  mRootNodes.emplace_back(i.getCoord(), &*i);
205  }
206  for (auto i = tree.root().cbeginValueOn(); i; ++i) {
207  mRootTiles.emplace_back(CoordBBox::createCube(i.getCoord(), RootChildT::DIM));
208  }
209 }
210 
211 template<typename TreeT>
212 bool FindActiveValues<TreeT>::any(const CoordBBox &bbox, bool useAccessor) const
213 {
214  if (useAccessor) {
215  if (mAcc.isValueOn( (bbox.min() + bbox.max())>>1 )) return true;
216  } else {
217  if (mAcc.tree().isValueOn( (bbox.min() + bbox.max())>>1 )) return true;
218  }
219 
220  for (auto& tile : mRootTiles) {
221  if (tile.hasOverlap(bbox)) return true;
222  }
223  for (auto& node : mRootNodes) {
224  if (!node.bbox.hasOverlap(bbox)) {
225  continue;
226  } else if (node.bbox.isInside(bbox)) {
227  return this->any(node.child, bbox);
228  } else if (this->any(node.child, bbox)) {
229  return true;
230  }
231  }
232  return false;
233 }
234 
235 template<typename TreeT>
236 Index64 FindActiveValues<TreeT>::count(const CoordBBox &bbox) const
237 {
238  Index64 count = 0;
239  for (auto& tile : mRootTiles) {//loop over active tiles only
240  if (!tile.hasOverlap(bbox)) {
241  continue;//ignore non-overlapping tiles
242  } else if (tile.isInside(bbox)) {
243  return bbox.volume();// bbox is completely inside the active tile
244  } else if (bbox.isInside(tile)) {
245  count += RootChildT::NUM_VOXELS;
246  } else {
247  auto tmp = tile;
248  tmp.intersect(bbox);
249  count += tmp.volume();
250  }
251  }
252  for (auto &node : mRootNodes) {//loop over child nodes of the root node only
253  if ( !node.bbox.hasOverlap(bbox) ) {
254  continue;//ignore non-overlapping child nodes
255  } else if ( node.bbox.isInside(bbox) ) {
256  return this->count(node.child, bbox);// bbox is completely inside the child node
257  } else {
258  count += this->count(node.child, bbox);
259  }
260  }
261  return count;
262 }
263 
264 template<typename TreeT>
265 template<typename NodeT>
266 typename NodeT::NodeMaskType FindActiveValues<TreeT>::getBBoxMask(const CoordBBox &bbox, const NodeT* node) const
267 {
268  typename NodeT::NodeMaskType mask;
269  auto b = node->getNodeBoundingBox();
270  assert( bbox.hasOverlap(b) );
271  if ( bbox.isInside(b) ) {
272  mask.setOn();//node is completely inside the bbox so early out
273  } else {
274  b.intersect(bbox);
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() );
280  auto it = b.begin();
281  for (const Coord& x = *it; it; ++it) {
282  mask.setOn(x[2] + (x[1] << NodeT::LOG2DIM) + (x[0] << 2*NodeT::LOG2DIM));
283  }
284  }
285  return mask;
286 }
287 
288 template<typename TreeT>
289 template<typename NodeT>
290 bool FindActiveValues<TreeT>::any(const NodeT* node, const CoordBBox &bbox) const
291 {
292  // Generate a bit mask of the bbox coverage
293  auto mask = this->getBBoxMask(bbox, node);
294 
295  // Check active tiles
296  const auto tmp = mask & node->getValueMask();// prune active the tile mask with the bbox mask
297  if (!tmp.isOff()) return true;
298 
299  // Check child nodes
300  mask &= node->getChildMask();// prune the child mask with the bbox mask
301  const auto* table = node->getTable();
302  bool test = false;
303  for (auto i = mask.beginOn(); !test && i; ++i) {
304  test = this->any(table[i.pos()].getChild(), bbox);
305  }
306  return test;
307 }
308 
309 template<typename TreeT>
310 inline bool FindActiveValues<TreeT>::any(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const
311 {
312  bool test = leaf->getValueMask().isOn();
313 
314  for (auto i = leaf->cbeginValueOn(); !test && i; ++i) {
315  test = bbox.isInside(i.getCoord());
316  }
317  return test;
318 }
319 
320 template<typename TreeT>
321 inline Index64 FindActiveValues<TreeT>::count(const typename TreeT::LeafNodeType* leaf, const CoordBBox &bbox ) const
322 {
323  Index64 count = 0;
324  if (leaf->getValueMask().isOn()) {
325  auto b = leaf->getNodeBoundingBox();
326  b.intersect(bbox);
327  count = b.volume();
328  } else {
329  for (auto i = leaf->cbeginValueOn(); i; ++i) {
330  if (bbox.isInside(i.getCoord())) ++count;
331  }
332  }
333  return count;
334 }
335 
336 template<typename TreeT>
337 template<typename NodeT>
338 Index64 FindActiveValues<TreeT>::count(const NodeT* node, const CoordBBox &bbox) const
339 {
340  Index64 count = 0;
341 
342  // Generate a bit masks
343  auto mask = this->getBBoxMask(bbox, node);
344  const auto childMask = mask & node->getChildMask();// prune the child mask with the bbox mask
345  mask &= node->getValueMask();// prune active tile mask with the bbox mask
346  const auto* table = node->getTable();
347 
348  {// Check child nodes
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());
352  int j=0;
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);
357  return sum;
358  }, []( Index64 a, Index64 b )->Index64 { return a+b; }
359  );
360  }
361 
362  {// Check active tiles
363  std::vector<Coord> coords(mask.countOn());
364  using RangeT = tbb::blocked_range<typename std::vector<Coord>::iterator>;
365  int j=0;
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 ) {
370  auto b = CoordBBox::createCube(*i, NodeT::ChildNodeType::DIM);
371  b.intersect(bbox);
372  sum += b.volume();
373  }
374  return sum;
375  }, []( Index64 a, Index64 b )->Index64 { return a+b; }
376  );
377  }
378 
379  return count;
380 }
381 
382 template<typename TreeT>
384 {
385  const RootChildT* child;
386  const CoordBBox bbox;
387  NodePairT(const Coord& c = Coord(), const RootChildT* p = nullptr)
388  : child(p), bbox(CoordBBox::createCube(c, RootChildT::DIM))
389  {
390  }
391 };// NodePairT struct
392 
393 //////////////////////////////////////////////////////////////////////////////////////////
394 
395 // Implementation of stand-alone function
396 template<typename TreeT>
397 inline bool
398 anyActiveValues(const TreeT& tree, const CoordBBox &bbox)
399 {
400  FindActiveValues<TreeT> op(tree);
401  return op.any(bbox);
402 }
403 
404 // Implementation of stand-alone function
405 template<typename TreeT>
406 inline bool
407 noActiveValues(const TreeT& tree, const CoordBBox &bbox)
408 {
409  FindActiveValues<TreeT> op(tree);
410  return op.none(bbox);
411 }
412 
413 // Implementation of stand-alone function
414 template<typename TreeT>
415 inline bool
416 countActiveValues(const TreeT& tree, const CoordBBox &bbox)
417 {
418  FindActiveValues<TreeT> op(tree);
419  return op.count(bbox);
420 }
421 
422 } // namespace tools
423 } // namespace OPENVDB_VERSION_NAME
424 } // namespace openvdb
425 
426 #endif // OPENVDB_TOOLS_FINDACTIVEVALUES_HAS_BEEN_INCLUDED
427 
428 // Copyright (c) Ken Museth
429 // All rights reserved. This software is distributed under the
430 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
cvex test(vector P=0;int unbound=3;export float s=0;export vector Cf=0;)
Definition: test.vfl:11
GLboolean GLboolean GLboolean GLboolean a
Definition: glew.h:9477
GLenum GLsizei GLenum GLenum const void * table
Definition: glew.h:4940
GLenum GLuint coords
Definition: glew.h:7906
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:200
NodePairT(const Coord &c=Coord(), const RootChildT *p=nullptr)
GLenum GLint GLuint mask
Definition: glew.h:1845
bool anyActiveValues(const TreeT &tree, const CoordBBox &bbox)
Returns true if the bounding box intersects any of the active values in a tree, i.e. either active voxels or active tiles.
bool noActiveValues(const TreeT &tree, const CoordBBox &bbox)
Returns true if the bounding box intersects none of the active values in a tree, i.e. neither active voxels or active tiles.
bool any(const vbool4 &v)
Definition: simd.h:3372
GLint GLint GLint GLint GLint x
Definition: glew.h:1252
void update(const TreeT &tree)
Initiate this class with a new (or modified) tree.
const GLfloat * c
Definition: glew.h:16296
Index64 count(const CoordBBox &bbox) const
Returns the number of active voxels intersected by the specified bounding box.
Finds the active values in a tree which intersects a bounding box.
bool any(const CoordBBox &bbox, bool useAccessor=false) const
Returns true if the specified bounding box intersects any active values.
GLdouble GLdouble GLdouble b
Definition: glew.h:9122
GLfloat GLfloat p
Definition: glew.h:16321
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
GLuint GLuint GLsizei count
Definition: glew.h:1253
bool none(const CoordBBox &bbox, bool useAccessor=false) const
Returns true if the specified bounding box does not intersect any active values.
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:146
FindActiveValues(const TreeT &tree)
Constructor from a const tree, which is assumed not to be modified after construction.
Index64 countActiveValues(const TreeT &tree, const CoordBBox &bbox)
Returns the number of active values that intersects a bounding box intersects, i.e. the count includes both active voxels and virtual voxels in active tiles.