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
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