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 
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 
101 /// Index filtering on active / inactive state of host voxel
102 template <bool On>
104 {
105 public:
106  static bool initialized() { return true; }
107  static index::State state() { return index::PARTIAL; }
108  template <typename LeafT>
109  static index::State state(const LeafT& leaf)
110  {
111  if (leaf.isDense()) return On ? index::ALL : index::NONE;
112  else if (leaf.isEmpty()) return On ? index::NONE : index::ALL;
113  return index::PARTIAL;
114  }
115 
116  template <typename LeafT>
117  void reset(const LeafT&) { }
118 
119  template <typename IterT>
120  bool valid(const IterT& iter) const
121  {
122  const bool valueOn = iter.isValueOn();
123  return On ? valueOn : !valueOn;
124  }
125 };
126 
127 
130 
131 
132 /// Index filtering on multiple group membership for inclusion and exclusion
133 ///
134 /// @note include filters are applied first, then exclude filters
136 {
137 public:
138  using NameVector = std::vector<Name>;
139  using IndexVector = std::vector<AttributeSet::Descriptor::GroupIndex>;
140  using HandleVector = std::vector<GroupHandle>;
141 
142 private:
143  static IndexVector namesToIndices(const AttributeSet& attributeSet, const NameVector& names) {
145  for (const auto& name : names) {
146  try {
147  indices.emplace_back(attributeSet.groupIndex(name));
148  } catch (LookupError&) {
149  // silently drop group names that don't exist
150  }
151  }
152  return indices;
153  }
154 
155 public:
156  MultiGroupFilter( const NameVector& include,
157  const NameVector& exclude,
158  const AttributeSet& attributeSet)
159  : mInclude(MultiGroupFilter::namesToIndices(attributeSet, include))
160  , mExclude(MultiGroupFilter::namesToIndices(attributeSet, exclude)) { }
161 
162  MultiGroupFilter( const IndexVector& include,
163  const IndexVector& exclude)
164  : mInclude(include)
165  , mExclude(exclude) { }
166 
168  : mInclude(filter.mInclude)
169  , mExclude(filter.mExclude)
170  , mIncludeHandles(filter.mIncludeHandles)
171  , mExcludeHandles(filter.mExcludeHandles)
172  , mInitialized(filter.mInitialized) { }
173 
174  inline bool initialized() const { return mInitialized; }
175 
176  inline index::State state() const
177  {
178  return (mInclude.empty() && mExclude.empty()) ? index::ALL : index::PARTIAL;
179  }
180 
181  template <typename LeafT>
182  static index::State state(const LeafT&) { return index::PARTIAL; }
183 
184  template <typename LeafT>
185  void reset(const LeafT& leaf) {
186  mIncludeHandles.clear();
187  mExcludeHandles.clear();
188  for (const auto& i : mInclude) {
189  mIncludeHandles.emplace_back(leaf.groupHandle(i));
190  }
191  for (const auto& i : mExclude) {
192  mExcludeHandles.emplace_back(leaf.groupHandle(i));
193  }
194  mInitialized = true;
195  }
196 
197  template <typename IterT>
198  bool valid(const IterT& iter) const {
199  assert(mInitialized);
200  // accept no include filters as valid
201  bool includeValid = mIncludeHandles.empty();
202  for (const GroupHandle& handle : mIncludeHandles) {
203  if (handle.getUnsafe(*iter)) {
204  includeValid = true;
205  break;
206  }
207  }
208  if (!includeValid) return false;
209  for (const GroupHandle& handle : mExcludeHandles) {
210  if (handle.getUnsafe(*iter)) return false;
211  }
212  return true;
213  }
214 
215 private:
216  IndexVector mInclude;
217  IndexVector mExclude;
218  HandleVector mIncludeHandles;
219  HandleVector mExcludeHandles;
220  bool mInitialized = false;
221 }; // class MultiGroupFilter
222 
223 
224 // Random index filtering per leaf
225 template <typename PointDataTreeT, typename RandGenT>
227 {
228 public:
229  using SeedCountPair = std::pair<Index, Index>;
230  using LeafMap = std::unordered_map<openvdb::Coord, SeedCountPair>;
231 
232  RandomLeafFilter( const PointDataTreeT& tree,
233  const Index64 targetPoints,
234  const unsigned int seed = 0) {
235  Index64 currentPoints = 0;
236  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
237  currentPoints += iter->pointCount();
238  }
239 
240  const float factor = targetPoints > currentPoints ? 1.0f : float(targetPoints) / float(currentPoints);
241 
242  std::mt19937 generator(seed);
243  std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max() - 1);
244 
245  Index32 leafCounter = 0;
246  float totalPointsFloat = 0.0f;
247  int totalPoints = 0;
248  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
249  // for the last leaf - use the remaining points to reach the target points
250  if (leafCounter + 1 == tree.leafCount()) {
251  const int leafPoints = static_cast<int>(targetPoints) - totalPoints;
252  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
253  break;
254  }
255  totalPointsFloat += factor * static_cast<float>(iter->pointCount());
256  const auto leafPoints = static_cast<int>(math::Floor(totalPointsFloat));
257  totalPointsFloat -= static_cast<float>(leafPoints);
258  totalPoints += leafPoints;
259 
260  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
261 
262  leafCounter++;
263  }
264  }
265 
266  inline bool initialized() const { return mNextIndex == -1; }
267 
268  static index::State state() { return index::PARTIAL; }
269  template <typename LeafT>
270  static index::State state(const LeafT&) { return index::PARTIAL; }
271 
272  template <typename LeafT>
273  void reset(const LeafT& leaf) {
275 
276  auto it = mLeafMap.find(leaf.origin());
277  if (it == mLeafMap.end()) {
278  OPENVDB_THROW(openvdb::KeyError,
279  "Cannot find leaf origin in map for random filter - " << leaf.origin());
280  }
281 
282  const SeedCountPair& value = it->second;
283  const unsigned int seed = static_cast<unsigned int>(value.first);
284  const auto total = static_cast<Index>(leaf.pointCount());
285  mCount = std::min(value.second, total);
286 
287  mIndices = generateRandomSubset<RandGenT, int>(seed, mCount, total);
288 
289  mSubsetOffset = -1;
290  mNextIndex = -1;
291  }
292 
293  inline void next() const {
294  mSubsetOffset++;
295  mNextIndex = mSubsetOffset >= mCount ?
297  mIndices[mSubsetOffset];
298  }
299 
300  template <typename IterT>
301  bool valid(const IterT& iter) const {
302  const int index = *iter;
303  while (mNextIndex < index) this->next();
304  return mNextIndex == index;
305  }
306 
307 protected:
308  friend class ::TestIndexFilter;
309 
310 private:
311  LeafMap mLeafMap;
312  std::vector<int> mIndices;
313  int mCount = 0;
314  mutable int mSubsetOffset = -1;
315  mutable int mNextIndex = -1;
316 }; // class RandomLeafFilter
317 
318 
319 // Hash attribute value for deterministic, but approximate filtering
320 template <typename RandGenT, typename IntType>
322 {
323 public:
325 
327  const double percentage,
328  const unsigned int seed = 0)
329  : mIndex(index)
330  , mFactor(percentage / 100.0)
331  , mSeed(seed) { }
332 
334  : mIndex(filter.mIndex)
335  , mFactor(filter.mFactor)
336  , mSeed(filter.mSeed)
337  {
338  if (filter.mIdHandle) mIdHandle.reset(new Handle(*filter.mIdHandle));
339  }
340 
341  inline bool initialized() const { return bool(mIdHandle); }
342 
343  static index::State state() { return index::PARTIAL; }
344  template <typename LeafT>
345  static index::State state(const LeafT&) { return index::PARTIAL; }
346 
347  template <typename LeafT>
348  void reset(const LeafT& leaf) {
349  assert(leaf.hasAttribute(mIndex));
350  mIdHandle.reset(new Handle(leaf.constAttributeArray(mIndex)));
351  }
352 
353  template <typename IterT>
354  bool valid(const IterT& iter) const {
355  assert(mIdHandle);
356  const IntType id = mIdHandle->get(*iter);
357  const unsigned int seed = mSeed + static_cast<unsigned int>(id);
358  RandGenT generator(seed);
359  std::uniform_real_distribution<double> dist(0.0, 1.0);
360  return dist(generator) < mFactor;
361  }
362 
363 private:
364  const size_t mIndex;
365  const double mFactor;
366  const unsigned int mSeed;
367  typename Handle::UniquePtr mIdHandle;
368 }; // class AttributeHashFilter
369 
370 
371 template <typename LevelSetGridT>
373 {
374 public:
375  using ValueT = typename LevelSetGridT::ValueType;
377 
378  LevelSetFilter( const LevelSetGridT& grid,
379  const math::Transform& transform,
380  const ValueT min,
381  const ValueT max)
382  : mAccessor(grid.getConstAccessor())
383  , mLevelSetTransform(grid.transform())
384  , mTransform(transform)
385  , mMin(min)
386  , mMax(max) { }
387 
389  : mAccessor(filter.mAccessor)
390  , mLevelSetTransform(filter.mLevelSetTransform)
391  , mTransform(filter.mTransform)
392  , mMin(filter.mMin)
393  , mMax(filter.mMax)
394  {
395  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
396  }
397 
398  inline bool initialized() const { return bool(mPositionHandle); }
399 
400  static index::State state() { return index::PARTIAL; }
401  template <typename LeafT>
402  static index::State state(const LeafT&) { return index::PARTIAL; }
403 
404  template <typename LeafT>
405  void reset(const LeafT& leaf) {
406  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
407  }
408 
409  template <typename IterT>
410  bool valid(const IterT& iter) const {
411  assert(mPositionHandle);
412  assert(iter);
413 
414  const openvdb::Coord ijk = iter.getCoord();
415  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
416 
417  // Retrieve point position in voxel space
418  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
419 
420  // Compute point position in index space
421  const openvdb::Vec3f pointWorldSpace = mTransform.indexToWorld(pointVoxelSpace + voxelIndexSpace);
422  const openvdb::Vec3f pointIndexSpace = mLevelSetTransform.worldToIndex(pointWorldSpace);
423 
424  // Perform level-set sampling
425  const typename LevelSetGridT::ValueType value = tools::BoxSampler::sample(mAccessor, pointIndexSpace);
426 
427  // if min is greater than max, we invert so that values are valid outside of the range (not inside)
428  const bool invert = mMin > mMax;
429 
430  return invert ? (value < mMax || value > mMin) : (value < mMax && value > mMin);
431  }
432 
433 private:
434  // not a reference to ensure const-accessor is unique per-thread
435  const typename LevelSetGridT::ConstAccessor mAccessor;
436  const math::Transform& mLevelSetTransform;
437  const math::Transform& mTransform;
438  const ValueT mMin;
439  const ValueT mMax;
440  Handle::UniquePtr mPositionHandle;
441 }; // class LevelSetFilter
442 
443 
444 // BBox index filtering
446 {
447 public:
449 
451  const openvdb::BBoxd& bboxWS)
452  : mTransform(transform)
453  , mBbox(transform.worldToIndex(bboxWS)) { }
454 
456  : mTransform(filter.mTransform)
457  , mBbox(filter.mBbox)
458  {
459  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
460  }
461 
462  inline bool initialized() const { return bool(mPositionHandle); }
463 
464  inline index::State state() const
465  {
466  return mBbox.empty() ? index::NONE : index::PARTIAL;
467  }
468  template <typename LeafT>
469  static index::State state(const LeafT&) { return index::PARTIAL; }
470 
471  template <typename LeafT>
472  void reset(const LeafT& leaf) {
473  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
474  }
475 
476  template <typename IterT>
477  bool valid(const IterT& iter) const {
478  assert(mPositionHandle);
479 
480  const openvdb::Coord ijk = iter.getCoord();
481  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
482 
483  // Retrieve point position in voxel space
484  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
485 
486  // Compute point position in index space
487  const openvdb::Vec3f pointIndexSpace = pointVoxelSpace + voxelIndexSpace;
488 
489  return mBbox.isInside(pointIndexSpace);
490  }
491 
492 private:
493  const openvdb::math::Transform& mTransform;
494  const openvdb::BBoxd mBbox;
495  Handle::UniquePtr mPositionHandle;
496 }; // class BBoxFilter
497 
498 
499 // Index filtering based on evaluating both sub-filters
500 template <typename T1, typename T2, bool And = true>
502 {
503 public:
504  BinaryFilter( const T1& filter1,
505  const T2& filter2)
506  : mFilter1(filter1)
507  , mFilter2(filter2) { }
508 
509  inline bool initialized() const { return mFilter1.initialized() && mFilter2.initialized(); }
510 
511  inline index::State state() const
512  {
513  return this->computeState(mFilter1.state(), mFilter2.state());
514  }
515  template <typename LeafT>
516  inline index::State state(const LeafT& leaf) const
517  {
518  return this->computeState(mFilter1.state(leaf), mFilter2.state(leaf));
519  }
520 
521  template <typename LeafT>
522  void reset(const LeafT& leaf) {
523  mFilter1.reset(leaf);
524  mFilter2.reset(leaf);
525  }
526 
527  template <typename IterT>
528  bool valid(const IterT& iter) const {
529  if (And) return mFilter1.valid(iter) && mFilter2.valid(iter);
530  return mFilter1.valid(iter) || mFilter2.valid(iter);
531  }
532 
533 private:
534  inline index::State computeState( index::State state1,
535  index::State state2) const
536  {
537  if (And) {
538  if (state1 == index::NONE || state2 == index::NONE) return index::NONE;
539  else if (state1 == index::ALL && state2 == index::ALL) return index::ALL;
540  } else {
541  if (state1 == index::NONE && state2 == index::NONE) return index::NONE;
542  else if (state1 == index::ALL && state2 == index::ALL) return index::ALL;
543  }
544  return index::PARTIAL;
545  }
546 
547  T1 mFilter1;
548  T2 mFilter2;
549 }; // class BinaryFilter
550 
551 
552 ////////////////////////////////////////
553 
554 
555 template<typename T>
556 struct FilterTraits {
557  static const bool RequiresCoord = false;
558 };
559 template<>
561  static const bool RequiresCoord = true;
562 };
563 template <typename T>
565  static const bool RequiresCoord = true;
566 };
567 template <typename T0, typename T1, bool And>
568 struct FilterTraits<BinaryFilter<T0, T1, And>> {
571 };
572 
573 
574 ////////////////////////////////////////
575 
576 
577 } // namespace points
578 } // namespace OPENVDB_VERSION_NAME
579 } // namespace openvdb
580 
581 #endif // OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
vint4 max(const vint4 &a, const vint4 &b)
Definition: simd.h:4703
GA_API const UT_StringHolder dist
GLboolean invert
Definition: glew.h:1422
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
GLuint id
Definition: glew.h:1679
Vec3d indexToWorld(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:108
GLuint const GLchar * name
Definition: glew.h:1814
GLuint GLenum GLenum transform
Definition: glew.h:14742
GLuint index
Definition: glew.h:1814
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:232
GLint GLsizei const GLuint64 * values
Definition: glew.h:3612
vbool4 shuffle(const vbool4 &a)
shuffle<i>(a) is the same as shuffle<i,i,i,i>(a)
Definition: simd.h:3313
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:167
const GLdouble * m
Definition: glew.h:9124
class OCIOEXPORT Transform
rst::
Index filtering on active / inactive state of host voxel.
Definition: IndexFilter.h:103
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:167
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:448
static index::State state(const LeafT &)
Definition: IndexFilter.h:402
GLint GLint GLint GLint GLint GLint GLint GLbitfield GLenum filter
Definition: glew.h:2981
static index::State state(const LeafT &)
Definition: IndexFilter.h:469
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:375
MultiGroupFilter(const NameVector &include, const NameVector &exclude, const AttributeSet &attributeSet)
Definition: IndexFilter.h:156
GLuint GLuint GLsizei GLenum const void * indices
Definition: glew.h:1253
GLuint const GLuint * names
Definition: glew.h:2690
GLsizei n
Definition: glew.h:4040
std::unordered_map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:230
Index Iterators.
static bool sample(const TreeT &inTree, const Vec3R &inCoord, typename TreeT::ValueType &result)
Trilinearly reconstruct inTree at inCoord and store the result in result.
static index::State state(const LeafT &leaf)
Definition: IndexFilter.h:109
Library and file format version numbers.
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:326
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:504
Set of Attribute Arrays which tracks metadata about each array.
Attribute Group access and filtering for iteration.
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:376
GLuint GLdouble GLdouble GLint GLint const GLdouble * points
Definition: glew.h:3446
math::BBox< Vec3d > BBoxd
Definition: Types.h:62
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:38
int Floor(float x)
Return the floor of x.
Definition: Math.h:841
std::vector< IntType > generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
Definition: IndexFilter.h:74
index::State state(const LeafT &leaf) const
Definition: IndexFilter.h:516
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:378
vint4 min(const vint4 &a, const vint4 &b)
Definition: simd.h:4694
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:450
Attribute Array storage templated on type and compression codec.
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:333
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:113
GLsizei const GLfloat * value
Definition: glew.h:1849
void sort(I begin, I end, const Pred &pred)
Definition: pugixml.cpp:7334
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
MultiGroupFilter(const IndexVector &include, const IndexVector &exclude)
Definition: IndexFilter.h:162
std::vector< AttributeSet::Descriptor::GroupIndex > IndexVector
Definition: IndexFilter.h:139
math::Vec3< float > Vec3f
Definition: Types.h:52