HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
IndexFilter.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /// @file points/IndexFilter.h
5 ///
6 /// @author Dan Bailey
7 ///
8 /// @brief Index filters primarily designed to be used with a FilterIndexIter.
9 ///
10 /// Filters must adhere to the interface described in the example below:
11 /// @code
12 /// struct MyFilter
13 /// {
14 /// // Return true when the filter has been initialized for first use
15 /// bool initialized() { return true; }
16 ///
17 /// // Return index::ALL if all points are valid, index::NONE if no points are valid
18 /// // and index::PARTIAL if some points are valid
19 /// index::State state() { return index::PARTIAL; }
20 ///
21 /// // Return index::ALL if all points in this leaf are valid, index::NONE if no points
22 /// // in this leaf are valid and index::PARTIAL if some points in this leaf are valid
23 /// template <typename LeafT>
24 /// index::State state(const LeafT&) { return index::PARTIAL; }
25 ///
26 /// // Resets the filter to refer to the specified leaf, all subsequent valid() calls
27 /// // will be relative to this leaf until reset() is called with a different leaf.
28 /// // Although a required method, many filters will provide an empty implementation if
29 /// // there is no leaf-specific logic needed.
30 /// template <typename LeafT> void reset(const LeafT&) { }
31 ///
32 /// // Returns true if the filter is valid for the supplied iterator
33 /// template <typename IterT> bool valid(const IterT&) { return true; }
34 /// };
35 /// @endcode
36 
37 #ifndef OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
38 #define OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
39 
40 #include <openvdb/version.h>
41 #include <openvdb/Types.h>
42 
43 #include <openvdb/math/Transform.h>
45 
46 #include "IndexIterator.h"
47 #include "AttributeArray.h"
48 #include "AttributeGroup.h"
49 #include "AttributeSet.h"
50 
51 #include <random> // std::mt19937
52 #include <numeric> // std::iota
53 #include <unordered_map>
54 
55 
56 class TestIndexFilter;
57 
58 namespace openvdb {
60 namespace OPENVDB_VERSION_NAME {
61 namespace points {
62 
63 
64 ////////////////////////////////////////
65 
66 /// @cond OPENVDB_DOCS_INTERNAL
67 
68 namespace index_filter_internal {
69 
70 
71 // generate a random subset of n indices from the range [0:m]
72 template <typename RandGenT, typename IntType>
73 std::vector<IntType>
74 generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
75 {
76  if (n <= 0) return std::vector<IntType>();
77 
78  // fill vector with ascending indices
79  std::vector<IntType> values(m);
80  std::iota(values.begin(), values.end(), 0);
81  if (n >= m) return values;
82 
83  // shuffle indices using random generator
84 
85  RandGenT randGen(seed);
86  std::shuffle(values.begin(), values.end(), randGen);
87 
88  // resize the container to n elements
89  values.resize(n);
90 
91  // sort the subset of the indices vector that will be used
92  std::sort(values.begin(), values.end());
93 
94  return values;
95 }
96 
97 
98 } // namespace index_filter_internal
99 
100 /// @endcond
101 
102 
103 /// Index filtering on active / inactive state of host voxel
104 template <bool On>
106 {
107 public:
108  static bool initialized() { return true; }
109  static index::State state() { return index::PARTIAL; }
110  template <typename LeafT>
111  static index::State state(const LeafT& leaf)
112  {
113  if (leaf.isDense()) return On ? index::ALL : index::NONE;
114  else if (leaf.isEmpty()) return On ? index::NONE : index::ALL;
115  return index::PARTIAL;
116  }
117 
118  template <typename LeafT>
119  void reset(const LeafT&) { }
120 
121  template <typename IterT>
122  bool valid(const IterT& iter) const
123  {
124  const bool valueOn = iter.isValueOn();
125  return On ? valueOn : !valueOn;
126  }
127 };
128 
129 
132 
133 
134 /// Index filtering on multiple group membership for inclusion and exclusion
135 ///
136 /// @note include filters are applied first, then exclude filters
138 {
139 public:
140  using NameVector = std::vector<Name>;
141  using IndexVector = std::vector<AttributeSet::Descriptor::GroupIndex>;
142  using HandleVector = std::vector<GroupHandle>;
143 
144 private:
145  static IndexVector namesToIndices(const AttributeSet& attributeSet, const NameVector& names) {
147  for (const auto& name : names) {
148  try {
149  indices.emplace_back(attributeSet.groupIndex(name));
150  } catch (LookupError&) {
151  // silently drop group names that don't exist
152  }
153  }
154  return indices;
155  }
156 
157 public:
158  MultiGroupFilter( const NameVector& include,
159  const NameVector& exclude,
160  const AttributeSet& attributeSet)
161  : mInclude(MultiGroupFilter::namesToIndices(attributeSet, include))
162  , mExclude(MultiGroupFilter::namesToIndices(attributeSet, exclude)) { }
163 
164  MultiGroupFilter( const IndexVector& include,
165  const IndexVector& exclude)
166  : mInclude(include)
167  , mExclude(exclude) { }
168 
170  : mInclude(filter.mInclude)
171  , mExclude(filter.mExclude)
172  , mIncludeHandles(filter.mIncludeHandles)
173  , mExcludeHandles(filter.mExcludeHandles)
174  , mInitialized(filter.mInitialized) { }
175 
176  inline bool initialized() const { return mInitialized; }
177 
178  inline index::State state() const
179  {
180  return (mInclude.empty() && mExclude.empty()) ? index::ALL : index::PARTIAL;
181  }
182 
183  template <typename LeafT>
184  static index::State state(const LeafT&) { return index::PARTIAL; }
185 
186  template <typename LeafT>
187  void reset(const LeafT& leaf) {
188  mIncludeHandles.clear();
189  mExcludeHandles.clear();
190  for (const auto& i : mInclude) {
191  mIncludeHandles.emplace_back(leaf.groupHandle(i));
192  }
193  for (const auto& i : mExclude) {
194  mExcludeHandles.emplace_back(leaf.groupHandle(i));
195  }
196  mInitialized = true;
197  }
198 
199  template <typename IterT>
200  bool valid(const IterT& iter) const {
201  assert(mInitialized);
202  // accept no include filters as valid
203  bool includeValid = mIncludeHandles.empty();
204  for (const GroupHandle& handle : mIncludeHandles) {
205  if (handle.getUnsafe(*iter)) {
206  includeValid = true;
207  break;
208  }
209  }
210  if (!includeValid) return false;
211  for (const GroupHandle& handle : mExcludeHandles) {
212  if (handle.getUnsafe(*iter)) return false;
213  }
214  return true;
215  }
216 
217 private:
218  IndexVector mInclude;
219  IndexVector mExclude;
220  HandleVector mIncludeHandles;
221  HandleVector mExcludeHandles;
222  bool mInitialized = false;
223 }; // class MultiGroupFilter
224 
225 
226 // Random index filtering per leaf
227 template <typename PointDataTreeT, typename RandGenT>
229 {
230 public:
231  using SeedCountPair = std::pair<Index, Index>;
232  using LeafMap = std::unordered_map<openvdb::Coord, SeedCountPair>;
233 
234  RandomLeafFilter( const PointDataTreeT& tree,
235  const Index64 targetPoints,
236  const unsigned int seed = 0) {
237  Index64 currentPoints = 0;
238  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
239  currentPoints += iter->pointCount();
240  }
241 
242  const float factor = targetPoints > currentPoints ? 1.0f : float(targetPoints) / float(currentPoints);
243 
244  std::mt19937 generator(seed);
245  std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max() - 1);
246 
247  Index32 leafCounter = 0;
248  float totalPointsFloat = 0.0f;
249  int totalPoints = 0;
250  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
251  // for the last leaf - use the remaining points to reach the target points
252  if (leafCounter + 1 == tree.leafCount()) {
253  const int leafPoints = static_cast<int>(targetPoints) - totalPoints;
254  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
255  break;
256  }
257  totalPointsFloat += factor * static_cast<float>(iter->pointCount());
258  const auto leafPoints = static_cast<int>(math::Floor(totalPointsFloat));
259  totalPointsFloat -= static_cast<float>(leafPoints);
260  totalPoints += leafPoints;
261 
262  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
263 
264  leafCounter++;
265  }
266  }
267 
268  inline bool initialized() const { return mNextIndex == -1; }
269 
270  static index::State state() { return index::PARTIAL; }
271  template <typename LeafT>
272  static index::State state(const LeafT&) { return index::PARTIAL; }
273 
274  template <typename LeafT>
275  void reset(const LeafT& leaf) {
276  using index_filter_internal::generateRandomSubset;
277 
278  auto it = mLeafMap.find(leaf.origin());
279  if (it == mLeafMap.end()) {
280  OPENVDB_THROW(openvdb::KeyError,
281  "Cannot find leaf origin in map for random filter - " << leaf.origin());
282  }
283 
284  const SeedCountPair& value = it->second;
285  const unsigned int seed = static_cast<unsigned int>(value.first);
286  const auto total = static_cast<Index>(leaf.pointCount());
287  mCount = std::min(value.second, total);
288 
289  mIndices = generateRandomSubset<RandGenT, int>(seed, mCount, total);
290 
291  mSubsetOffset = -1;
292  mNextIndex = -1;
293  }
294 
295  inline void next() const {
296  mSubsetOffset++;
297  mNextIndex = mSubsetOffset >= mCount ?
299  mIndices[mSubsetOffset];
300  }
301 
302  template <typename IterT>
303  bool valid(const IterT& iter) const {
304  const int index = *iter;
305  while (mNextIndex < index) this->next();
306  return mNextIndex == index;
307  }
308 
309 protected:
310  friend class ::TestIndexFilter;
311 
312 private:
313  LeafMap mLeafMap;
314  std::vector<int> mIndices;
315  int mCount = 0;
316  mutable int mSubsetOffset = -1;
317  mutable int mNextIndex = -1;
318 }; // class RandomLeafFilter
319 
320 
321 // Hash attribute value for deterministic, but approximate filtering
322 template <typename RandGenT, typename IntType>
324 {
325 public:
327 
329  const double percentage,
330  const unsigned int seed = 0)
331  : mIndex(index)
332  , mFactor(percentage / 100.0)
333  , mSeed(seed) { }
334 
336  : mIndex(filter.mIndex)
337  , mFactor(filter.mFactor)
338  , mSeed(filter.mSeed)
339  {
340  if (filter.mIdHandle) mIdHandle.reset(new Handle(*filter.mIdHandle));
341  }
342 
343  inline bool initialized() const { return bool(mIdHandle); }
344 
345  static index::State state() { return index::PARTIAL; }
346  template <typename LeafT>
347  static index::State state(const LeafT&) { return index::PARTIAL; }
348 
349  template <typename LeafT>
350  void reset(const LeafT& leaf) {
351  assert(leaf.hasAttribute(mIndex));
352  mIdHandle.reset(new Handle(leaf.constAttributeArray(mIndex)));
353  }
354 
355  template <typename IterT>
356  bool valid(const IterT& iter) const {
357  assert(mIdHandle);
358  const IntType id = mIdHandle->get(*iter);
359  const unsigned int seed = mSeed + static_cast<unsigned int>(id);
360  RandGenT generator(seed);
361  std::uniform_real_distribution<double> dist(0.0, 1.0);
362  return dist(generator) < mFactor;
363  }
364 
365 private:
366  const size_t mIndex;
367  const double mFactor;
368  const unsigned int mSeed;
369  typename Handle::UniquePtr mIdHandle;
370 }; // class AttributeHashFilter
371 
372 
373 template <typename LevelSetGridT>
375 {
376 public:
377  using ValueT = typename LevelSetGridT::ValueType;
379 
380  LevelSetFilter( const LevelSetGridT& grid,
381  const math::Transform& transform,
382  const ValueT min,
383  const ValueT max)
384  : mAccessor(grid.getConstAccessor())
385  , mLevelSetTransform(grid.transform())
386  , mTransform(transform)
387  , mMin(min)
388  , mMax(max) { }
389 
391  : mAccessor(filter.mAccessor)
392  , mLevelSetTransform(filter.mLevelSetTransform)
393  , mTransform(filter.mTransform)
394  , mMin(filter.mMin)
395  , mMax(filter.mMax)
396  {
397  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
398  }
399 
400  inline bool initialized() const { return bool(mPositionHandle); }
401 
402  static index::State state() { return index::PARTIAL; }
403  template <typename LeafT>
404  static index::State state(const LeafT&) { return index::PARTIAL; }
405 
406  template <typename LeafT>
407  void reset(const LeafT& leaf) {
408  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
409  }
410 
411  template <typename IterT>
412  bool valid(const IterT& iter) const {
413  assert(mPositionHandle);
414  assert(iter);
415 
416  const openvdb::Coord ijk = iter.getCoord();
417  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
418 
419  // Retrieve point position in voxel space
420  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
421 
422  // Compute point position in index space
423  const openvdb::Vec3f pointWorldSpace = mTransform.indexToWorld(pointVoxelSpace + voxelIndexSpace);
424  const openvdb::Vec3f pointIndexSpace = mLevelSetTransform.worldToIndex(pointWorldSpace);
425 
426  // Perform level-set sampling
427  const typename LevelSetGridT::ValueType value = tools::BoxSampler::sample(mAccessor, pointIndexSpace);
428 
429  // if min is greater than max, we invert so that values are valid outside of the range (not inside)
430  const bool invert = mMin > mMax;
431 
432  return invert ? (value < mMax || value > mMin) : (value < mMax && value > mMin);
433  }
434 
435 private:
436  // not a reference to ensure const-accessor is unique per-thread
437  const typename LevelSetGridT::ConstAccessor mAccessor;
438  const math::Transform& mLevelSetTransform;
439  const math::Transform& mTransform;
440  const ValueT mMin;
441  const ValueT mMax;
442  Handle::UniquePtr mPositionHandle;
443 }; // class LevelSetFilter
444 
445 
446 // BBox index filtering
448 {
449 public:
451 
452  BBoxFilter(const openvdb::math::Transform& transform,
453  const openvdb::BBoxd& bboxWS)
454  : mTransform(transform)
455  , mBbox(transform.worldToIndex(bboxWS)) { }
456 
458  : mTransform(filter.mTransform)
459  , mBbox(filter.mBbox)
460  {
461  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
462  }
463 
464  inline bool initialized() const { return bool(mPositionHandle); }
465 
466  inline index::State state() const
467  {
468  return mBbox.empty() ? index::NONE : index::PARTIAL;
469  }
470  template <typename LeafT>
471  static index::State state(const LeafT&) { return index::PARTIAL; }
472 
473  template <typename LeafT>
474  void reset(const LeafT& leaf) {
475  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
476  }
477 
478  template <typename IterT>
479  bool valid(const IterT& iter) const {
480  assert(mPositionHandle);
481 
482  const openvdb::Coord ijk = iter.getCoord();
483  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
484 
485  // Retrieve point position in voxel space
486  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
487 
488  // Compute point position in index space
489  const openvdb::Vec3f pointIndexSpace = pointVoxelSpace + voxelIndexSpace;
490 
491  return mBbox.isInside(pointIndexSpace);
492  }
493 
494 private:
495  const openvdb::math::Transform& mTransform;
496  const openvdb::BBoxd mBbox;
497  Handle::UniquePtr mPositionHandle;
498 }; // class BBoxFilter
499 
500 
501 // Index filtering based on evaluating both sub-filters
502 template <typename T1, typename T2, bool And = true>
504 {
505 public:
506  BinaryFilter( const T1& filter1,
507  const T2& filter2)
508  : mFilter1(filter1)
509  , mFilter2(filter2) { }
510 
511  inline bool initialized() const { return mFilter1.initialized() && mFilter2.initialized(); }
512 
513  inline index::State state() const
514  {
515  return this->computeState(mFilter1.state(), mFilter2.state());
516  }
517  template <typename LeafT>
518  inline index::State state(const LeafT& leaf) const
519  {
520  return this->computeState(mFilter1.state(leaf), mFilter2.state(leaf));
521  }
522 
523  template <typename LeafT>
524  void reset(const LeafT& leaf) {
525  mFilter1.reset(leaf);
526  mFilter2.reset(leaf);
527  }
528 
529  template <typename IterT>
530  bool valid(const IterT& iter) const {
531  if (And) return mFilter1.valid(iter) && mFilter2.valid(iter);
532  return mFilter1.valid(iter) || mFilter2.valid(iter);
533  }
534 
535 private:
536  inline index::State computeState( index::State state1,
537  index::State state2) const
538  {
539  if (And) {
540  if (state1 == index::NONE || state2 == index::NONE) return index::NONE;
541  else if (state1 == index::ALL && state2 == index::ALL) return index::ALL;
542  } else {
543  if (state1 == index::NONE && state2 == index::NONE) return index::NONE;
544  else if (state1 == index::ALL && state2 == index::ALL) return index::ALL;
545  }
546  return index::PARTIAL;
547  }
548 
549  T1 mFilter1;
550  T2 mFilter2;
551 }; // class BinaryFilter
552 
553 
554 ////////////////////////////////////////
555 
556 
557 template<typename T>
558 struct FilterTraits {
559  static const bool RequiresCoord = false;
560 };
561 template<>
563  static const bool RequiresCoord = true;
564 };
565 template <typename T>
567  static const bool RequiresCoord = true;
568 };
569 template <typename T0, typename T1, bool And>
570 struct FilterTraits<BinaryFilter<T0, T1, And>> {
573 };
574 
575 
576 ////////////////////////////////////////
577 
578 
579 } // namespace points
580 } // namespace OPENVDB_VERSION_NAME
581 } // namespace openvdb
582 
583 #endif // OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
GA_API const UT_StringHolder dist
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
OIIO_FORCEINLINE vbool4 shuffle(const vbool4 &a)
Definition: simd.h:3409
Vec3d indexToWorld(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:108
GLboolean invert
Definition: glcorearb.h:549
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:234
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:207
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
GLuint const GLchar * name
Definition: glcorearb.h:786
Index filtering on active / inactive state of host voxel.
Definition: IndexFilter.h:105
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:169
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1602
GLuint GLenum GLenum transform
Definition: glew.h:15055
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:450
static index::State state(const LeafT &)
Definition: IndexFilter.h:404
static index::State state(const LeafT &)
Definition: IndexFilter.h:471
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:377
MultiGroupFilter(const NameVector &include, const NameVector &exclude, const AttributeSet &attributeSet)
Definition: IndexFilter.h:158
GLsizei GLenum const void * indices
Definition: glcorearb.h:406
std::unordered_map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:232
Index Iterators.
GLuint id
Definition: glcorearb.h:655
GLint GLint GLint GLint GLint GLint GLint GLbitfield GLenum filter
Definition: glcorearb.h:1297
GLuint const GLuint * names
Definition: glew.h:2695
static bool sample(const TreeT &inTree, const Vec3R &inCoord, typename TreeT::ValueType &result)
Trilinearly reconstruct inTree at inCoord and store the result in result.
GLuint GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glew.h:3460
GLdouble n
Definition: glcorearb.h:2008
static index::State state(const LeafT &leaf)
Definition: IndexFilter.h:111
Library and file format version numbers.
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:328
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:506
Set of Attribute Arrays which tracks metadata about each array.
Attribute Group access and filtering for iteration.
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:378
GLuint index
Definition: glcorearb.h:786
math::BBox< Vec3d > BBoxd
Definition: Types.h:84
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:38
const GLdouble * m
Definition: glew.h:9166
int Floor(float x)
Return the floor of x.
Definition: Math.h:851
Definition: core.h:1131
index::State state(const LeafT &leaf) const
Definition: IndexFilter.h:518
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:380
Vec3d worldToIndex(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:110
BBoxFilter(const openvdb::math::Transform &transform, const openvdb::BBoxd &bboxWS)
Definition: IndexFilter.h:452
Attribute Array storage templated on type and compression codec.
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:335
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:119
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
MultiGroupFilter(const IndexVector &include, const IndexVector &exclude)
Definition: IndexFilter.h:164
std::vector< AttributeSet::Descriptor::GroupIndex > IndexVector
Definition: IndexFilter.h:141
math::Vec3< float > Vec3f
Definition: Types.h:74