OpenVDB 10.0.1
Loading...
Searching...
No Matches
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
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
56class TestIndexFilter;
57
58namespace openvdb {
60namespace OPENVDB_VERSION_NAME {
61namespace points {
62
63
64////////////////////////////////////////
65
66/// @cond OPENVDB_DOCS_INTERNAL
67
68namespace index_filter_internal {
69
70
71// generate a random subset of n indices from the range [0:m]
72template <typename RandGenT, typename IntType>
73std::vector<IntType>
74generateRandomSubset(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
104template <bool On>
106{
107public:
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{
139public:
140 using NameVector = std::vector<Name>;
141 using IndexVector = std::vector<AttributeSet::Descriptor::GroupIndex>;
142 using HandleVector = std::vector<GroupHandle>;
143
144private:
145 static IndexVector namesToIndices(const AttributeSet& attributeSet, const NameVector& names) {
146 IndexVector indices;
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
157public:
159 const NameVector& exclude,
160 const AttributeSet& attributeSet)
161 : mInclude(MultiGroupFilter::namesToIndices(attributeSet, include))
162 , mExclude(MultiGroupFilter::namesToIndices(attributeSet, exclude)) { }
163
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
217private:
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
227template <typename PointDataTreeT, typename RandGenT>
229{
230public:
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()) {
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 ?
298 std::numeric_limits<int>::max() :
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
309protected:
310 friend class ::TestIndexFilter;
311
312private:
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
322template <typename RandGenT, typename IntType>
324{
325public:
327
328 AttributeHashFilter(const size_t index,
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
365private:
366 const size_t mIndex;
367 const double mFactor;
368 const unsigned int mSeed;
369 typename Handle::UniquePtr mIdHandle;
370}; // class AttributeHashFilter
371
372
373template <typename LevelSetGridT>
375{
376public:
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
435private:
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{
449public:
451
452 BBoxFilter(const openvdb::math::Transform& transform,
453 const openvdb::BBoxd& bboxWS)
454 : mTransform(transform)
455 , mBbox(transform.worldToIndex(bboxWS)) { }
456
457 BBoxFilter(const BBoxFilter& filter)
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
494private:
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
502template <typename T1, typename T2, bool And = true>
504{
505public:
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
535private:
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
557template<typename T>
559 static const bool RequiresCoord = false;
560};
561template<>
563 static const bool RequiresCoord = true;
564};
565template <typename T>
567 static const bool RequiresCoord = true;
568};
569template <typename T0, typename T1, bool And>
570struct FilterTraits<BinaryFilter<T0, T1, And>> {
571 static const bool RequiresCoord = FilterTraits<T0>::RequiresCoord ||
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
Attribute Array storage templated on type and compression codec.
Attribute Group access and filtering for iteration.
Set of Attribute Arrays which tracks metadata about each array.
ValueT value
Definition: GridBuilder.h:1290
Index Iterators.
Definition: Exceptions.h:59
Definition: Exceptions.h:60
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:25
Vec3d asVec3d() const
Definition: Coord.h:143
Definition: Transform.h:40
Definition: Vec3.h:24
Definition: AttributeArray.h:836
Definition: IndexFilter.h:324
void reset(const LeafT &leaf)
Definition: IndexFilter.h:350
static index::State state()
Definition: IndexFilter.h:345
static index::State state(const LeafT &)
Definition: IndexFilter.h:347
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:335
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:328
bool valid(const IterT &iter) const
Definition: IndexFilter.h:356
bool initialized() const
Definition: IndexFilter.h:343
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:39
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
Definition: IndexFilter.h:448
void reset(const LeafT &leaf)
Definition: IndexFilter.h:474
index::State state() const
Definition: IndexFilter.h:466
static index::State state(const LeafT &)
Definition: IndexFilter.h:471
BBoxFilter(const BBoxFilter &filter)
Definition: IndexFilter.h:457
BBoxFilter(const openvdb::math::Transform &transform, const openvdb::BBoxd &bboxWS)
Definition: IndexFilter.h:452
bool valid(const IterT &iter) const
Definition: IndexFilter.h:479
bool initialized() const
Definition: IndexFilter.h:464
Definition: IndexFilter.h:504
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:506
void reset(const LeafT &leaf)
Definition: IndexFilter.h:524
index::State state() const
Definition: IndexFilter.h:513
index::State state(const LeafT &leaf) const
Definition: IndexFilter.h:518
bool valid(const IterT &iter) const
Definition: IndexFilter.h:530
bool initialized() const
Definition: IndexFilter.h:511
Definition: AttributeGroup.h:73
Definition: IndexFilter.h:375
void reset(const LeafT &leaf)
Definition: IndexFilter.h:407
static index::State state()
Definition: IndexFilter.h:402
static index::State state(const LeafT &)
Definition: IndexFilter.h:404
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:377
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:380
LevelSetFilter(const LevelSetFilter &filter)
Definition: IndexFilter.h:390
bool valid(const IterT &iter) const
Definition: IndexFilter.h:412
bool initialized() const
Definition: IndexFilter.h:400
Definition: IndexFilter.h:138
std::vector< GroupHandle > HandleVector
Definition: IndexFilter.h:142
MultiGroupFilter(const IndexVector &include, const IndexVector &exclude)
Definition: IndexFilter.h:164
std::vector< AttributeSet::Descriptor::GroupIndex > IndexVector
Definition: IndexFilter.h:141
void reset(const LeafT &leaf)
Definition: IndexFilter.h:187
index::State state() const
Definition: IndexFilter.h:178
static index::State state(const LeafT &)
Definition: IndexFilter.h:184
MultiGroupFilter(const NameVector &include, const NameVector &exclude, const AttributeSet &attributeSet)
Definition: IndexFilter.h:158
std::vector< Name > NameVector
Definition: IndexFilter.h:140
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:169
bool valid(const IterT &iter) const
Definition: IndexFilter.h:200
bool initialized() const
Definition: IndexFilter.h:176
Definition: IndexFilter.h:229
void reset(const LeafT &leaf)
Definition: IndexFilter.h:275
void next() const
Definition: IndexFilter.h:295
std::pair< Index, Index > SeedCountPair
Definition: IndexFilter.h:231
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:234
static index::State state()
Definition: IndexFilter.h:270
static index::State state(const LeafT &)
Definition: IndexFilter.h:272
std::unordered_map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:232
bool valid(const IterT &iter) const
Definition: IndexFilter.h:303
bool initialized() const
Definition: IndexFilter.h:268
Index filtering on active / inactive state of host voxel.
Definition: IndexFilter.h:106
static index::State state()
Definition: IndexFilter.h:109
static bool initialized()
Definition: IndexFilter.h:108
void reset(const LeafT &)
Definition: IndexFilter.h:119
static index::State state(const LeafT &leaf)
Definition: IndexFilter.h:111
bool valid(const IterT &iter) const
Definition: IndexFilter.h:122
State
Definition: IndexIterator.h:40
Index32 Index
Definition: Types.h:54
uint32_t Index32
Definition: Types.h:52
uint64_t Index64
Definition: Types.h:53
Definition: Exceptions.h:13
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:74
Definition: IndexFilter.h:558
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212