OpenVDB  7.0.0
IndexFilter.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
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 
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 
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 
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) {
144  IndexVector indices;
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()) {
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 
326  AttributeHashFilter(const size_t index,
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 
450  BBoxFilter(const openvdb::math::Transform& transform,
451  const openvdb::BBoxd& bboxWS)
452  : mTransform(transform)
453  , mBbox(transform.worldToIndex(bboxWS)) { }
454 
455  BBoxFilter(const BBoxFilter& filter)
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 
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>> {
569  static const bool RequiresCoord = FilterTraits<T0>::RequiresCoord ||
571 };
572 
573 
575 
576 
577 } // namespace points
578 } // namespace OPENVDB_VERSION_NAME
579 } // namespace openvdb
580 
581 #endif // OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
static index::State state(const LeafT &leaf)
Definition: IndexFilter.h:109
bool initialized() const
Definition: IndexFilter.h:174
bool valid(const IterT &iter) const
Definition: IndexFilter.h:477
void reset(const LeafT &leaf)
Definition: IndexFilter.h:472
BBoxFilter(const BBoxFilter &filter)
Definition: IndexFilter.h:455
Attribute Group access and filtering for iteration.
void reset(const LeafT &leaf)
Definition: IndexFilter.h:405
std::vector< Name > NameVector
Definition: IndexFilter.h:138
std::unordered_map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:230
bool valid(const IterT &iter) const
Definition: IndexFilter.h:120
bool valid(const IterT &iter) const
Definition: IndexFilter.h:354
std::vector< AttributeSet::Descriptor::GroupIndex > IndexVector
Definition: IndexFilter.h:139
uint32_t Index32
Definition: Types.h:29
Definition: IndexFilter.h:556
index::State state() const
Definition: IndexFilter.h:511
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:82
void next() const
Definition: IndexFilter.h:293
static bool initialized()
Definition: IndexFilter.h:106
Attribute Array storage templated on type and compression codec.
std::pair< Index, Index > SeedCountPair
Definition: IndexFilter.h:229
static index::State state()
Definition: IndexFilter.h:400
bool valid(const IterT &iter) const
Definition: IndexFilter.h:301
MultiGroupFilter(const IndexVector &include, const IndexVector &exclude)
Definition: IndexFilter.h:162
Definition: IndexIterator.h:41
bool valid(const IterT &iter) const
Definition: IndexFilter.h:528
Definition: Exceptions.h:59
Definition: IndexIterator.h:42
static index::State state(const LeafT &)
Definition: IndexFilter.h:402
Definition: IndexIterator.h:43
void reset(const LeafT &leaf)
Definition: IndexFilter.h:273
Definition: IndexFilter.h:501
static index::State state(const LeafT &)
Definition: IndexFilter.h:270
Definition: AttributeGroup.h:75
index::State state() const
Definition: IndexFilter.h:176
Definition: IndexFilter.h:372
std::unique_ptr< Handle > UniquePtr
Definition: AttributeArray.h:854
State
Definition: IndexIterator.h:39
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
std::vector< GroupHandle > HandleVector
Definition: IndexFilter.h:140
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:333
std::vector< IntType > generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
Definition: IndexFilter.h:74
bool initialized() const
Definition: IndexFilter.h:509
bool initialized() const
Definition: IndexFilter.h:398
static index::State state()
Definition: IndexFilter.h:107
Definition: IndexFilter.h:226
Definition: IndexFilter.h:135
Definition: Exceptions.h:13
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:167
void reset(const LeafT &leaf)
Definition: IndexFilter.h:348
int Floor(float x)
Return the floor of x.
Definition: Math.h:795
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:375
Index Iterators.
static index::State state()
Definition: IndexFilter.h:268
Index filtering on active / inactive state of host voxel.
Definition: IndexFilter.h:103
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:232
Library and file format version numbers.
void reset(const LeafT &leaf)
Definition: IndexFilter.h:522
bool valid(const IterT &iter) const
Definition: IndexFilter.h:410
Definition: Transform.h:39
static index::State state()
Definition: IndexFilter.h:343
Index32 Index
Definition: Types.h:31
Definition: Exceptions.h:60
static index::State state(const LeafT &)
Definition: IndexFilter.h:182
Definition: AttributeArray.h:849
Definition: IndexFilter.h:445
bool initialized() const
Definition: IndexFilter.h:462
Definition: Mat.h:170
LevelSetFilter(const LevelSetFilter &filter)
Definition: IndexFilter.h:388
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:102
index::State state() const
Definition: IndexFilter.h:464
Definition: IndexFilter.h:321
bool valid(const IterT &iter) const
Definition: IndexFilter.h:198
index::State state(const LeafT &leaf) const
Definition: IndexFilter.h:516
uint64_t Index64
Definition: Types.h:30
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:504
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
bool initialized() const
Definition: IndexFilter.h:266
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:326
static index::State state(const LeafT &)
Definition: IndexFilter.h:469
Set of Attribute Arrays which tracks metadata about each array.
void reset(const LeafT &leaf)
Definition: IndexFilter.h:185
static index::State state(const LeafT &)
Definition: IndexFilter.h:345
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:35
MultiGroupFilter(const NameVector &include, const NameVector &exclude, const AttributeSet &attributeSet)
Definition: IndexFilter.h:156
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:106
bool initialized() const
Definition: IndexFilter.h:341
BBoxFilter(const openvdb::math::Transform &transform, const openvdb::BBoxd &bboxWS)
Definition: IndexFilter.h:450
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:378
void reset(const LeafT &)
Definition: IndexFilter.h:117