OpenVDB  5.1.0
IndexFilter.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2018 DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 
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 <boost/ptr_container/ptr_vector.hpp>
52 
53 #include <random> // std::mt19937
54 #include <numeric> // std::iota
55 
56 
57 class TestIndexFilter;
58 
59 namespace openvdb {
61 namespace OPENVDB_VERSION_NAME {
62 namespace points {
63 
64 
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 
105 {
106 public:
107  using NameVector = std::vector<Name>;
108  using IndexVector = std::vector<AttributeSet::Descriptor::GroupIndex>;
109  using HandleVector = std::vector<GroupHandle>;
110 
111 private:
112  static IndexVector namesToIndices(const AttributeSet& attributeSet, const NameVector& names) {
113  IndexVector indices;
114  for (const auto& name : names) {
115  try {
116  indices.emplace_back(attributeSet.groupIndex(name));
117  } catch (LookupError&) {
118  // silently drop group names that don't exist
119  }
120  }
121  return indices;
122  }
123 
124 public:
125  MultiGroupFilter( const NameVector& include,
126  const NameVector& exclude,
127  const AttributeSet& attributeSet)
128  : mInclude(MultiGroupFilter::namesToIndices(attributeSet, include))
129  , mExclude(MultiGroupFilter::namesToIndices(attributeSet, exclude)) { }
130 
131  MultiGroupFilter( const IndexVector& include,
132  const IndexVector& exclude)
133  : mInclude(include)
134  , mExclude(exclude) { }
135 
137  : mInclude(filter.mInclude)
138  , mExclude(filter.mExclude)
139  , mIncludeHandles(filter.mIncludeHandles)
140  , mExcludeHandles(filter.mExcludeHandles)
141  , mInitialized(filter.mInitialized) { }
142 
143  inline bool initialized() const { return mInitialized; }
144 
145  template <typename LeafT>
146  void reset(const LeafT& leaf) {
147  mIncludeHandles.clear();
148  mExcludeHandles.clear();
149  for (const AttributeSet::Descriptor::GroupIndex& index : mInclude) {
150  mIncludeHandles.emplace_back(leaf.groupHandle(index));
151  }
152  for (const AttributeSet::Descriptor::GroupIndex& index : mExclude) {
153  mExcludeHandles.emplace_back(leaf.groupHandle(index));
154  }
155  mInitialized = true;
156  }
157 
158  template <typename IterT>
159  bool valid(const IterT& iter) const {
160  assert(mInitialized);
161  // accept no include filters as valid
162  bool includeValid = mIncludeHandles.empty();
163  for (const GroupHandle& handle : mIncludeHandles) {
164  if (handle.getUnsafe(*iter)) {
165  includeValid = true;
166  break;
167  }
168  }
169  if (!includeValid) return false;
170  for (const GroupHandle& handle : mExcludeHandles) {
171  if (handle.getUnsafe(*iter)) return false;
172  }
173  return true;
174  }
175 
176 private:
177  IndexVector mInclude;
178  IndexVector mExclude;
179  HandleVector mIncludeHandles;
180  HandleVector mExcludeHandles;
181  bool mInitialized = false;
182 }; // class MultiGroupFilter
183 
184 
185 // Random index filtering per leaf
186 template <typename PointDataTreeT, typename RandGenT>
188 {
189 public:
190  using SeedCountPair = std::pair<Index, Index>;
191  using LeafMap = std::map<openvdb::Coord, SeedCountPair>;
192 
193  RandomLeafFilter( const PointDataTreeT& tree,
194  const Index64 targetPoints,
195  const unsigned int seed = 0) {
196  Index64 currentPoints = 0;
197  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
198  currentPoints += iter->pointCount();
199  }
200 
201  const float factor = targetPoints > currentPoints ? 1.0f : float(targetPoints) / float(currentPoints);
202 
203  std::mt19937 generator(seed);
204  std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max() - 1);
205 
206  Index32 leafCounter = 0;
207  float totalPointsFloat = 0.0f;
208  int totalPoints = 0;
209  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
210  // for the last leaf - use the remaining points to reach the target points
211  if (leafCounter + 1 == tree.leafCount()) {
212  const int leafPoints = static_cast<int>(targetPoints) - totalPoints;
213  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
214  break;
215  }
216  totalPointsFloat += factor * iter->pointCount();
217  const auto leafPoints = static_cast<int>(math::Floor(totalPointsFloat));
218  totalPointsFloat -= static_cast<float>(leafPoints);
219  totalPoints += leafPoints;
220 
221  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
222 
223  leafCounter++;
224  }
225  }
226 
227  inline bool initialized() const { return mNextIndex == -1; }
228 
229  template <typename LeafT>
230  void reset(const LeafT& leaf) {
232 
233  auto it = mLeafMap.find(leaf.origin());
234  if (it == mLeafMap.end()) {
236  "Cannot find leaf origin in map for random filter - " << leaf.origin());
237  }
238 
239  const SeedCountPair& value = it->second;
240  const unsigned int seed = static_cast<unsigned int>(value.first);
241  const auto total = static_cast<Index>(leaf.pointCount());
242  mCount = std::min(value.second, total);
243 
244  mIndices = generateRandomSubset<RandGenT, int>(seed, mCount, total);
245 
246  mSubsetOffset = -1;
247  mNextIndex = -1;
248  }
249 
250  inline void next() const {
251  mSubsetOffset++;
252  mNextIndex = mSubsetOffset >= mCount ?
254  mIndices[mSubsetOffset];
255  }
256 
257  template <typename IterT>
258  bool valid(const IterT& iter) const {
259  const int index = *iter;
260  while (mNextIndex < index) this->next();
261  return mNextIndex == index;
262  }
263 
264 protected:
265  friend class ::TestIndexFilter;
266 
267 private:
268  LeafMap mLeafMap;
269  std::vector<int> mIndices;
270  int mCount = 0;
271  mutable int mSubsetOffset = -1;
272  mutable int mNextIndex = -1;
273 }; // class RandomLeafFilter
274 
275 
276 // Hash attribute value for deterministic, but approximate filtering
277 template <typename RandGenT, typename IntType>
279 {
280 public:
282 
283  AttributeHashFilter(const size_t index,
284  const double percentage,
285  const unsigned int seed = 0)
286  : mIndex(index)
287  , mFactor(percentage / 100.0)
288  , mSeed(seed) { }
289 
291  : mIndex(filter.mIndex)
292  , mFactor(filter.mFactor)
293  , mSeed(filter.mSeed)
294  {
295  if (filter.mIdHandle) mIdHandle.reset(new Handle(*filter.mIdHandle));
296  }
297 
298  inline bool initialized() const { return bool(mIdHandle); }
299 
300  template <typename LeafT>
301  void reset(const LeafT& leaf) {
302  assert(leaf.hasAttribute(mIndex));
303  mIdHandle.reset(new Handle(leaf.constAttributeArray(mIndex)));
304  }
305 
306  template <typename IterT>
307  bool valid(const IterT& iter) const {
308  assert(mIdHandle);
309  const IntType id = mIdHandle->get(*iter);
310  const unsigned int seed = mSeed + static_cast<unsigned int>(id);
311  RandGenT generator(seed);
312  std::uniform_real_distribution<double> dist(0.0, 1.0);
313  return dist(generator) < mFactor;
314  }
315 
316 private:
317  const size_t mIndex;
318  const double mFactor;
319  const unsigned int mSeed;
320  typename Handle::UniquePtr mIdHandle;
321 }; // class AttributeHashFilter
322 
323 
324 template <typename LevelSetGridT>
326 {
327 public:
328  using ValueT = typename LevelSetGridT::ValueType;
330 
331  LevelSetFilter( const LevelSetGridT& grid,
332  const math::Transform& transform,
333  const ValueT min,
334  const ValueT max)
335  : mAccessor(grid.getConstAccessor())
336  , mLevelSetTransform(grid.transform())
337  , mTransform(transform)
338  , mMin(min)
339  , mMax(max) { }
340 
342  : mAccessor(filter.mAccessor)
343  , mLevelSetTransform(filter.mLevelSetTransform)
344  , mTransform(filter.mTransform)
345  , mMin(filter.mMin)
346  , mMax(filter.mMax)
347  {
348  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
349  }
350 
351  inline bool initialized() const { return bool(mPositionHandle); }
352 
353  template <typename LeafT>
354  void reset(const LeafT& leaf) {
355  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
356  }
357 
358  template <typename IterT>
359  bool valid(const IterT& iter) const {
360  assert(mPositionHandle);
361  assert(iter);
362 
363  const openvdb::Coord ijk = iter.getCoord();
364  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
365 
366  // Retrieve point position in voxel space
367  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
368 
369  // Compute point position in index space
370  const openvdb::Vec3f pointWorldSpace = mTransform.indexToWorld(pointVoxelSpace + voxelIndexSpace);
371  const openvdb::Vec3f pointIndexSpace = mLevelSetTransform.worldToIndex(pointWorldSpace);
372 
373  // Perform level-set sampling
374  const typename LevelSetGridT::ValueType value = tools::BoxSampler::sample(mAccessor, pointIndexSpace);
375 
376  // if min is greater than max, we invert so that values are valid outside of the range (not inside)
377  const bool invert = mMin > mMax;
378 
379  return invert ? (value < mMax || value > mMin) : (value < mMax && value > mMin);
380  }
381 
382 private:
383  // not a reference to ensure const-accessor is unique per-thread
384  const typename LevelSetGridT::ConstAccessor mAccessor;
385  const math::Transform& mLevelSetTransform;
386  const math::Transform& mTransform;
387  const ValueT mMin;
388  const ValueT mMax;
389  Handle::UniquePtr mPositionHandle;
390 }; // class LevelSetFilter
391 
392 
393 // BBox index filtering
395 {
396 public:
398 
399  BBoxFilter(const openvdb::math::Transform& transform,
400  const openvdb::BBoxd& bboxWS)
401  : mTransform(transform)
402  , mBbox(transform.worldToIndex(bboxWS)) { }
403 
404  BBoxFilter(const BBoxFilter& filter)
405  : mTransform(filter.mTransform)
406  , mBbox(filter.mBbox)
407  {
408  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
409  }
410 
411  inline bool initialized() const { return bool(mPositionHandle); }
412 
413  template <typename LeafT>
414  void reset(const LeafT& leaf) {
415  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
416  }
417 
418  template <typename IterT>
419  bool valid(const IterT& iter) const {
420  assert(mPositionHandle);
421 
422  const openvdb::Coord ijk = iter.getCoord();
423  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
424 
425  // Retrieve point position in voxel space
426  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
427 
428  // Compute point position in index space
429  const openvdb::Vec3f pointIndexSpace = pointVoxelSpace + voxelIndexSpace;
430 
431  return mBbox.isInside(pointIndexSpace);
432  }
433 
434 private:
435  const openvdb::math::Transform& mTransform;
436  const openvdb::BBoxd mBbox;
437  Handle::UniquePtr mPositionHandle;
438 }; // class BBoxFilter
439 
440 
441 // Index filtering based on evaluating both sub-filters
442 template <typename T1, typename T2, bool And = true>
444 {
445 public:
446  BinaryFilter( const T1& filter1,
447  const T2& filter2)
448  : mFilter1(filter1)
449  , mFilter2(filter2) { }
450 
451  inline bool initialized() const { return mFilter1.initialized() && mFilter2.initialized(); }
452 
453  template <typename LeafT>
454  void reset(const LeafT& leaf) {
455  mFilter1.reset(leaf);
456  mFilter2.reset(leaf);
457  }
458 
459  template <typename IterT>
460  bool valid(const IterT& iter) const {
461  if (And) return mFilter1.valid(iter) && mFilter2.valid(iter);
462  return mFilter1.valid(iter) || mFilter2.valid(iter);
463  }
464 
465 private:
466  T1 mFilter1;
467  T2 mFilter2;
468 }; // class BinaryFilter
469 
470 
472 
473 
474 template<typename T>
475 struct FilterTraits {
476  static const bool RequiresCoord = false;
477 };
478 template<>
480  static const bool RequiresCoord = true;
481 };
482 template <typename T>
484  static const bool RequiresCoord = true;
485 };
486 template <typename T0, typename T1, bool And>
487 struct FilterTraits<BinaryFilter<T0, T1, And>> {
488  static const bool RequiresCoord = FilterTraits<T0>::RequiresCoord ||
490 };
491 
492 
494 
495 
496 } // namespace points
497 } // namespace OPENVDB_VERSION_NAME
498 } // namespace openvdb
499 
500 #endif // OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
501 
502 // Copyright (c) 2012-2018 DreamWorks Animation LLC
503 // All rights reserved. This software is distributed under the
504 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
Definition: IndexFilter.h:394
uint32_t Index32
Definition: Types.h:59
Definition: Exceptions.h:86
Definition: IndexFilter.h:104
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:193
Attribute Group access and filtering for iteration.
int Floor(float x)
Return the floor of x.
Definition: Math.h:802
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:283
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:446
bool initialized() const
Definition: IndexFilter.h:143
std::pair< Index, Index > SeedCountPair
Definition: IndexFilter.h:190
bool initialized() const
Definition: IndexFilter.h:451
bool initialized() const
Definition: IndexFilter.h:351
std::vector< AttributeSet::Descriptor::GroupIndex > IndexVector
Definition: IndexFilter.h:108
bool valid(const IterT &iter) const
Definition: IndexFilter.h:258
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:109
MultiGroupFilter(const IndexVector &include, const IndexVector &exclude)
Definition: IndexFilter.h:131
Attribute Array storage templated on type and compression codec.
Definition: AttributeArray.h:644
Definition: IndexFilter.h:475
bool valid(const IterT &iter) const
Definition: IndexFilter.h:419
Definition: IndexFilter.h:443
Definition: Mat.h:197
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:290
bool initialized() const
Definition: IndexFilter.h:411
bool valid(const IterT &iter) const
Definition: IndexFilter.h:307
Definition: IndexFilter.h:278
std::vector< GroupHandle > HandleVector
Definition: IndexFilter.h:109
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
MultiGroupFilter(const NameVector &include, const NameVector &exclude, const AttributeSet &attributeSet)
Definition: IndexFilter.h:125
Definition: Transform.h:66
Definition: Exceptions.h:87
uint64_t Index64
Definition: Types.h:60
void reset(const LeafT &leaf)
Definition: IndexFilter.h:414
Definition: Exceptions.h:40
std::vector< IntType > generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
Definition: IndexFilter.h:74
void reset(const LeafT &leaf)
Definition: IndexFilter.h:230
bool valid(const IterT &iter) const
Definition: IndexFilter.h:359
bool initialized() const
Definition: IndexFilter.h:298
Definition: AttributeGroup.h:102
bool valid(const IterT &iter) const
Definition: IndexFilter.h:159
Index Iterators.
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:136
void reset(const LeafT &leaf)
Definition: IndexFilter.h:146
bool initialized() const
Definition: IndexFilter.h:227
LevelSetFilter(const LevelSetFilter &filter)
Definition: IndexFilter.h:341
Library and file format version numbers.
BBoxFilter(const openvdb::math::Transform &transform, const openvdb::BBoxd &bboxWS)
Definition: IndexFilter.h:399
Definition: IndexFilter.h:187
BBoxFilter(const BBoxFilter &filter)
Definition: IndexFilter.h:404
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:129
Definition: IndexFilter.h:325
Signed (x, y, z) 32-bit integer coordinates.
Definition: Coord.h:51
std::vector< Name > NameVector
Definition: IndexFilter.h:107
Util::GroupIndex groupIndex(const Name &groupName) const
Return the group index from the name of the group.
void reset(const LeafT &leaf)
Definition: IndexFilter.h:301
Index32 Index
Definition: Types.h:61
Ordered collection of uniquely-named attribute arrays.
Definition: AttributeSet.h:62
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
bool valid(const IterT &iter) const
Definition: IndexFilter.h:460
Vec3d asVec3d() const
Definition: Coord.h:170
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:331
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:328
std::unique_ptr< Handle > UniquePtr
Definition: AttributeArray.h:649
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:133
std::map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:191
Set of Attribute Arrays which tracks metadata about each array.
void reset(const LeafT &leaf)
Definition: IndexFilter.h:354
void reset(const LeafT &leaf)
Definition: IndexFilter.h:454
void next() const
Definition: IndexFilter.h:250