HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
IndexFilter.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2017 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 //
29 ///////////////////////////////////////////////////////////////////////////
30 
31 /// @file points/IndexFilter.h
32 ///
33 /// @author Dan Bailey
34 ///
35 /// @brief Index filters primarily designed to be used with a FilterIndexIter.
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 
50 #include <hboost/ptr_container/ptr_vector.hpp>
51 
52 #include <random> // std::mt19937
53 #include <numeric> // std::iota
54 
55 
56 class TestIndexFilter;
57 
58 namespace openvdb {
60 namespace OPENVDB_VERSION_NAME {
61 namespace points {
62 
63 
64 ////////////////////////////////////////
65 
66 
67 namespace index_filter_internal {
68 
69 
70 // generate a random subset of n indices from the range [0:m]
71 template <typename RandGenT, typename IntType>
72 std::vector<IntType>
73 generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
74 {
75  if (n <= 0) return std::vector<IntType>();
76 
77  // fill vector with ascending indices
78  std::vector<IntType> values(m);
79  std::iota(values.begin(), values.end(), 0);
80  if (n >= m) return values;
81 
82  // shuffle indices using random generator
83 
84  RandGenT randGen(seed);
85  std::shuffle(values.begin(), values.end(), randGen);
86 
87  // resize the container to n elements
88  values.resize(n);
89 
90  // sort the subset of the indices vector that will be used
91  std::sort(values.begin(), values.end());
92 
93  return values;
94 }
95 
96 
97 } // namespace index_filter_internal
98 
99 
100 /// Index filtering on multiple group membership for inclusion and exclusion
101 ///
102 /// @note include filters are applied first, then exclude filters
104 {
105 public:
106  using NameVector = std::vector<Name>;
107  using HandleVector = hboost::ptr_vector<GroupHandle>;
108 
109  MultiGroupFilter( const NameVector& include,
110  const NameVector& exclude)
111  : mInclude(include)
112  , mExclude(exclude) { }
113 
115  : mInclude(filter.mInclude)
116  , mExclude(filter.mExclude)
117  , mIncludeHandles(filter.mIncludeHandles)
118  , mExcludeHandles(filter.mExcludeHandles)
119  , mInitialized(filter.mInitialized) { }
120 
121  inline bool initialized() const { return mInitialized; }
122 
123  template <typename LeafT>
124  void reset(const LeafT& leaf) {
125  mIncludeHandles.clear();
126  mExcludeHandles.clear();
127  for (const Name& name : mInclude) {
128  if (leaf.attributeSet().descriptor().hasGroup(name)) {
129  mIncludeHandles.push_back(new GroupHandle(leaf.groupHandle(name)));
130  }
131  }
132  for (const Name& name : mExclude) {
133  if (leaf.attributeSet().descriptor().hasGroup(name)) {
134  mExcludeHandles.push_back(new GroupHandle(leaf.groupHandle(name)));
135  }
136  }
137  mInitialized = true;
138  }
139 
140  template <typename IterT>
141  bool valid(const IterT& iter) const {
142  assert(mInitialized);
143  // accept no include filters as valid
144  bool includeValid = mIncludeHandles.empty();
145  for (const GroupHandle& handle : mIncludeHandles) {
146  if (handle.get(*iter)) {
147  includeValid = true;
148  break;
149  }
150  }
151  if (!includeValid) return false;
152  for (const GroupHandle& handle : mExcludeHandles) {
153  if (handle.get(*iter)) return false;
154  }
155  return true;
156  }
157 
158 private:
159  const NameVector mInclude;
160  const NameVector mExclude;
161  HandleVector mIncludeHandles;
162  HandleVector mExcludeHandles;
163  bool mInitialized = false;
164 }; // class MultiGroupFilter
165 
166 
167 // Random index filtering per leaf
168 template <typename PointDataTreeT, typename RandGenT>
170 {
171 public:
172  using SeedCountPair = std::pair<Index, Index>;
173  using LeafMap = std::map<openvdb::Coord, SeedCountPair>;
174 
175  RandomLeafFilter( const PointDataTreeT& tree,
176  const Index64 targetPoints,
177  const unsigned int seed = 0) {
178  Index64 currentPoints = 0;
179  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
180  currentPoints += iter->pointCount();
181  }
182 
183  const float factor = targetPoints > currentPoints ? 1.0f : float(targetPoints) / float(currentPoints);
184 
185  std::mt19937 generator(seed);
186  std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max() - 1);
187 
188  Index32 leafCounter = 0;
189  float totalPointsFloat = 0.0f;
190  int totalPoints = 0;
191  for (auto iter = tree.cbeginLeaf(); iter; ++iter) {
192  // for the last leaf - use the remaining points to reach the target points
193  if (leafCounter + 1 == tree.leafCount()) {
194  const int leafPoints = static_cast<int>(targetPoints) - totalPoints;
195  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
196  break;
197  }
198  totalPointsFloat += factor * iter->pointCount();
199  const auto leafPoints = static_cast<int>(math::Floor(totalPointsFloat));
200  totalPointsFloat -= static_cast<float>(leafPoints);
201  totalPoints += leafPoints;
202 
203  mLeafMap[iter->origin()] = SeedCountPair(dist(generator), leafPoints);
204 
205  leafCounter++;
206  }
207  }
208 
209  inline bool initialized() const { return mNextIndex == -1; }
210 
211  template <typename LeafT>
212  void reset(const LeafT& leaf) {
214 
215  auto it = mLeafMap.find(leaf.origin());
216  if (it == mLeafMap.end()) {
217  OPENVDB_THROW(openvdb::KeyError,
218  "Cannot find leaf origin in map for random filter - " << leaf.origin());
219  }
220 
221  const SeedCountPair& value = it->second;
222  const unsigned int seed = static_cast<unsigned int>(value.first);
223  const auto total = static_cast<Index>(leaf.pointCount());
224  mCount = std::min(value.second, total);
225 
226  mIndices = generateRandomSubset<RandGenT, int>(seed, mCount, total);
227 
228  mSubsetOffset = -1;
229  mNextIndex = -1;
230  }
231 
232  inline void next() const {
233  mSubsetOffset++;
234  mNextIndex = mSubsetOffset >= mCount ?
236  mIndices[mSubsetOffset];
237  }
238 
239  template <typename IterT>
240  bool valid(const IterT& iter) const {
241  const int index = *iter;
242  while (mNextIndex < index) this->next();
243  return mNextIndex == index;
244  }
245 
246 protected:
247  friend class ::TestIndexFilter;
248 
249 private:
250  LeafMap mLeafMap;
251  std::vector<int> mIndices;
252  int mCount = 0;
253  mutable int mSubsetOffset = -1;
254  mutable int mNextIndex = -1;
255 }; // class RandomLeafFilter
256 
257 
258 // Hash attribute value for deterministic, but approximate filtering
259 template <typename RandGenT, typename IntType>
261 {
262 public:
264 
266  const double percentage,
267  const unsigned int seed = 0)
268  : mIndex(index)
269  , mFactor(percentage / 100.0)
270  , mSeed(seed) { }
271 
273  : mIndex(filter.mIndex)
274  , mFactor(filter.mFactor)
275  , mSeed(filter.mSeed)
276  {
277  if (filter.mIdHandle) mIdHandle.reset(new Handle(*filter.mIdHandle));
278  }
279 
280  inline bool initialized() const { return bool(mIdHandle); }
281 
282  template <typename LeafT>
283  void reset(const LeafT& leaf) {
284  assert(leaf.hasAttribute(mIndex));
285  mIdHandle.reset(new Handle(leaf.constAttributeArray(mIndex)));
286  }
287 
288  template <typename IterT>
289  bool valid(const IterT& iter) const {
290  assert(mIdHandle);
291  const IntType id = mIdHandle->get(*iter);
292  const unsigned int seed = mSeed + static_cast<unsigned int>(id);
293  RandGenT generator(seed);
294  std::uniform_real_distribution<double> dist(0.0, 1.0);
295  return dist(generator) < mFactor;
296  }
297 
298 private:
299  const size_t mIndex;
300  const double mFactor;
301  const unsigned int mSeed;
302  typename Handle::UniquePtr mIdHandle;
303 }; // class AttributeHashFilter
304 
305 
306 template <typename LevelSetGridT>
308 {
309 public:
310  using ValueT = typename LevelSetGridT::ValueType;
312 
313  LevelSetFilter( const LevelSetGridT& grid,
314  const math::Transform& transform,
315  const ValueT min,
316  const ValueT max)
317  : mAccessor(grid.getConstAccessor())
318  , mLevelSetTransform(grid.transform())
319  , mTransform(transform)
320  , mMin(min)
321  , mMax(max) { }
322 
324  : mAccessor(filter.mAccessor)
325  , mLevelSetTransform(filter.mLevelSetTransform)
326  , mTransform(filter.mTransform)
327  , mMin(filter.mMin)
328  , mMax(filter.mMax)
329  {
330  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
331  }
332 
333  inline bool initialized() const { return bool(mPositionHandle); }
334 
335  template <typename LeafT>
336  void reset(const LeafT& leaf) {
337  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
338  }
339 
340  template <typename IterT>
341  bool valid(const IterT& iter) const {
342  assert(mPositionHandle);
343  assert(iter);
344 
345  const openvdb::Coord ijk = iter.getCoord();
346  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
347 
348  // Retrieve point position in voxel space
349  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
350 
351  // Compute point position in index space
352  const openvdb::Vec3f pointWorldSpace = mTransform.indexToWorld(pointVoxelSpace + voxelIndexSpace);
353  const openvdb::Vec3f pointIndexSpace = mLevelSetTransform.worldToIndex(pointWorldSpace);
354 
355  // Perform level-set sampling
356  const typename LevelSetGridT::ValueType value = tools::BoxSampler::sample(mAccessor, pointIndexSpace);
357 
358  // if min is greater than max, we invert so that values are valid outside of the range (not inside)
359  const bool invert = mMin > mMax;
360 
361  return invert ? (value < mMax || value > mMin) : (value < mMax && value > mMin);
362  }
363 
364 private:
365  // not a reference to ensure const-accessor is unique per-thread
366  const typename LevelSetGridT::ConstAccessor mAccessor;
367  const math::Transform& mLevelSetTransform;
368  const math::Transform& mTransform;
369  const ValueT mMin;
370  const ValueT mMax;
371  Handle::UniquePtr mPositionHandle;
372 }; // class LevelSetFilter
373 
374 
375 // BBox index filtering
377 {
378 public:
380 
381  BBoxFilter(const openvdb::math::Transform& transform,
382  const openvdb::BBoxd& bboxWS)
383  : mTransform(transform)
384  , mBbox(transform.worldToIndex(bboxWS)) { }
385 
387  : mTransform(filter.mTransform)
388  , mBbox(filter.mBbox)
389  {
390  if (filter.mPositionHandle) mPositionHandle.reset(new Handle(*filter.mPositionHandle));
391  }
392 
393  inline bool initialized() const { return bool(mPositionHandle); }
394 
395  template <typename LeafT>
396  void reset(const LeafT& leaf) {
397  mPositionHandle.reset(new Handle(leaf.constAttributeArray("P")));
398  }
399 
400  template <typename IterT>
401  bool valid(const IterT& iter) const {
402  assert(mPositionHandle);
403 
404  const openvdb::Coord ijk = iter.getCoord();
405  const openvdb::Vec3f voxelIndexSpace = ijk.asVec3d();
406 
407  // Retrieve point position in voxel space
408  const openvdb::Vec3f& pointVoxelSpace = mPositionHandle->get(*iter);
409 
410  // Compute point position in index space
411  const openvdb::Vec3f pointIndexSpace = pointVoxelSpace + voxelIndexSpace;
412 
413  return mBbox.isInside(pointIndexSpace);
414  }
415 
416 private:
417  const openvdb::math::Transform& mTransform;
418  const openvdb::BBoxd mBbox;
419  Handle::UniquePtr mPositionHandle;
420 }; // class BBoxFilter
421 
422 
423 // Index filtering based on evaluating both sub-filters
424 template <typename T1, typename T2, bool And = true>
426 {
427 public:
428  BinaryFilter( const T1& filter1,
429  const T2& filter2)
430  : mFilter1(filter1)
431  , mFilter2(filter2) { }
432 
433  inline bool initialized() const { return mFilter1.initialized() && mFilter2.initialized(); }
434 
435  template <typename LeafT>
436  void reset(const LeafT& leaf) {
437  mFilter1.reset(leaf);
438  mFilter2.reset(leaf);
439  }
440 
441  template <typename IterT>
442  bool valid(const IterT& iter) const {
443  if (And) return mFilter1.valid(iter) && mFilter2.valid(iter);
444  return mFilter1.valid(iter) || mFilter2.valid(iter);
445  }
446 
447 private:
448  T1 mFilter1;
449  T2 mFilter2;
450 }; // class BinaryFilter
451 
452 
453 ////////////////////////////////////////
454 
455 
456 template<typename T>
457 struct FilterTraits {
458  static const bool RequiresCoord = false;
459 };
460 template<>
462  static const bool RequiresCoord = true;
463 };
464 template <typename T>
466  static const bool RequiresCoord = true;
467 };
468 template <typename T0, typename T1, bool And>
469 struct FilterTraits<BinaryFilter<T0, T1, And>> {
472 };
473 
474 
475 ////////////////////////////////////////
476 
477 
478 } // namespace points
479 } // namespace OPENVDB_VERSION_NAME
480 } // namespace openvdb
481 
482 #endif // OPENVDB_POINTS_INDEX_FILTER_HAS_BEEN_INCLUDED
483 
484 // Copyright (c) 2012-2017 DreamWorks Animation LLC
485 // All rights reserved. This software is distributed under the
486 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
GA_API const UT_StringHolder dist
Definition: ImfName.h:53
Vec3d indexToWorld(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:135
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:128
GLboolean invert
Definition: glcorearb.h:548
RandomLeafFilter(const PointDataTreeT &tree, const Index64 targetPoints, const unsigned int seed=0)
Definition: IndexFilter.h:175
MultiGroupFilter(const MultiGroupFilter &filter)
Definition: IndexFilter.h:114
const hboost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:132
GLuint id
Definition: glcorearb.h:654
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:379
GLdouble n
Definition: glcorearb.h:2007
Calculate an axis-aligned bounding box in index space from a bounding sphere in world space...
Definition: Transform.h:66
typename LevelSetGridT::ValueType ValueT
Definition: IndexFilter.h:310
#define OPENVDB_VERSION_NAME
Definition: version.h:43
Index Iterators.
GLenum GLsizei GLsizei GLint * values
Definition: glcorearb.h:1601
hboost::ptr_vector< GroupHandle > HandleVector
Definition: IndexFilter.h:107
GLuint const GLchar * name
Definition: glcorearb.h:785
GA_API const UT_StringHolder transform
static bool sample(const TreeT &inTree, const Vec3R &inCoord, typename TreeT::ValueType &result)
Trilinearly reconstruct inTree at inCoord and store the result in result.
GLsizei const GLfloat * value
Definition: glcorearb.h:823
AttributeHashFilter(const size_t index, const double percentage, const unsigned int seed=0)
Definition: IndexFilter.h:265
BinaryFilter(const T1 &filter1, const T2 &filter2)
Definition: IndexFilter.h:428
Attribute Group access and filtering for iteration.
AttributeHandle< openvdb::Vec3f > Handle
Definition: IndexFilter.h:311
GLuint index
Definition: glcorearb.h:785
std::map< openvdb::Coord, SeedCountPair > LeafMap
Definition: IndexFilter.h:173
math::BBox< Vec3d > BBoxd
Definition: Types.h:87
int Floor(float x)
Return the floor of x.
Definition: Math.h:814
std::vector< IntType > generateRandomSubset(const unsigned int seed, const IntType n, const IntType m)
Definition: IndexFilter.h:73
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
LevelSetFilter(const LevelSetGridT &grid, const math::Transform &transform, const ValueT min, const ValueT max)
Definition: IndexFilter.h:313
Vec3d worldToIndex(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:137
BBoxFilter(const openvdb::math::Transform &transform, const openvdb::BBoxd &bboxWS)
Definition: IndexFilter.h:381
Attribute Array storage templated on type and compression codec.
AttributeHashFilter(const AttributeHashFilter &filter)
Definition: IndexFilter.h:272
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:101
MultiGroupFilter(const NameVector &include, const NameVector &exclude)
Definition: IndexFilter.h:109
GLint GLint GLint GLint GLint GLint GLint GLbitfield GLenum filter
Definition: glcorearb.h:1296
math::Vec3< float > Vec3f
Definition: Types.h:77