HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PointScatter.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 /// @author Ken Museth
32 ///
33 /// @file PointScatter.h
34 ///
35 /// @brief We offer three different algorithms (each in its own class)
36 /// for scattering of points in active voxels:
37 ///
38 /// 1) UniformPointScatter. Has two modes: Either randomly distributes
39 /// a fixed number of points into the active voxels, or the user can
40 /// specify a fixed probability of having a points per unit of volume.
41 ///
42 /// 2) DenseUniformPointScatter. Randomly distributes points into active
43 /// voxels using a fixed number of points per voxel.
44 ///
45 /// 3) NonIniformPointScatter. Define the local probability of having
46 /// a point in a voxel as the product of a global density and the
47 /// value of the voxel itself.
48 
49 #ifndef OPENVDB_TOOLS_POINT_SCATTER_HAS_BEEN_INCLUDED
50 #define OPENVDB_TOOLS_POINT_SCATTER_HAS_BEEN_INCLUDED
51 
52 #include <openvdb/Types.h>
53 #include <openvdb/Grid.h>
54 #include <openvdb/math/Math.h>
56 #include <tbb/parallel_sort.h>
57 #include <tbb/parallel_for.h>
58 #include <hboost/scoped_array.hpp>
59 
60 namespace openvdb {
62 namespace OPENVDB_VERSION_NAME {
63 namespace tools {
64 
65 /// Forward declaration of base class
66 template<typename PointAccessorType,
67  typename RandomGenerator,
68  typename InterruptType = util::NullInterrupter>
70 
71 /// @brief The two point scatters UniformPointScatter and
72 /// NonUniformPointScatter depend on the following two classes:
73 ///
74 /// The @c PointAccessorType template argument below refers to any class
75 /// with the following interface:
76 /// @code
77 /// class PointAccessor {
78 /// ...
79 /// public:
80 /// void add(const openvdb::Vec3R &pos);// appends point with world positions pos
81 /// };
82 /// @endcode
83 ///
84 ///
85 /// The @c InterruptType template argument below refers to any class
86 /// with the following interface:
87 /// @code
88 /// class Interrupter {
89 /// ...
90 /// public:
91 /// void start(const char* name = NULL)// called when computations begin
92 /// void end() // called when computations end
93 /// bool wasInterrupted(int percent=-1)// return true to break computation
94 ///};
95 /// @endcode
96 ///
97 /// @note If no template argument is provided for this InterruptType
98 /// the util::NullInterrupter is used which implies that all
99 /// interrupter calls are no-ops (i.e. incurs no computational overhead).
100 
101 
102 /// @brief Uniformly scatters points in the active voxels.
103 /// The point count is either explicitly defined or implicitly
104 /// through the specification of a global density (=points-per-volume)
105 ///
106 /// @note This uniform scattering technique assumes that the number of
107 /// points is generally smaller than the number of active voxels
108 /// (including virtual active voxels in active tiles).
109 template<typename PointAccessorType,
110  typename RandomGenerator,
111  typename InterruptType = util::NullInterrupter>
112 class UniformPointScatter : public BasePointScatter<PointAccessorType,
113  RandomGenerator,
114  InterruptType>
115 {
116 public:
118 
119  UniformPointScatter(PointAccessorType& points,
121  RandomGenerator& randGen,
122  double spread = 1.0,
123  InterruptType* interrupt = NULL)
124  : BaseT(points, randGen, spread, interrupt)
125  , mTargetPointCount(pointCount)
126  , mPointsPerVolume(0.0f)
127  {
128  }
129  UniformPointScatter(PointAccessorType& points,
130  float pointsPerVolume,
131  RandomGenerator& randGen,
132  double spread = 1.0,
133  InterruptType* interrupt = NULL)
134  : BaseT(points, randGen, spread, interrupt)
135  , mTargetPointCount(0)
136  , mPointsPerVolume(pointsPerVolume)
137  {
138  }
139 
140  /// @brief This is the main functor method implementing the actual
141  /// scattering of points.
142  template<typename GridT>
143  bool operator()(const GridT& grid)
144  {
145  mVoxelCount = grid.activeVoxelCount();
146  if (mVoxelCount == 0) return false;
147  const Vec3d dim = grid.voxelSize();
148  if (mPointsPerVolume>0) {
149  BaseT::start("Uniform scattering with fixed point density");
150  mTargetPointCount = Index64(mPointsPerVolume*dim[0]*dim[1]*dim[2])*mVoxelCount;
151  } else if (mTargetPointCount>0) {
152  BaseT::start("Uniform scattering with fixed point count");
153  mPointsPerVolume = mTargetPointCount/float(dim[0]*dim[1]*dim[2] * mVoxelCount);
154  } else {
155  return false;
156  }
157 
158  hboost::scoped_array<Index64> list(new Index64[mTargetPointCount]);
160  for (Index64 i=0; i<mTargetPointCount; ++i) list[i] = rand();
161  tbb::parallel_sort(list.get(), list.get() + mTargetPointCount);
162 
163  CoordBBox bbox;
164  const Vec3R offset(0.5, 0.5, 0.5);
165  typename GridT::ValueOnCIter valueIter = grid.cbeginValueOn();
166 
167  for (Index64 i=0, n=valueIter.getVoxelCount() ; i != mTargetPointCount; ++i) {
168  if (BaseT::interrupt()) return false;
169  const Index64 voxelId = list[i];
170  while ( n <= voxelId ) {
171  ++valueIter;
172  n += valueIter.getVoxelCount();
173  }
174  if (valueIter.isVoxelValue()) {// a majority is expected to be voxels
175  BaseT::addPoint(grid, valueIter.getCoord() - offset);
176  } else {// tiles contain multiple (virtual) voxels
177  valueIter.getBoundingBox(bbox);
178  BaseT::addPoint(grid, bbox.min() - offset, bbox.extents());
179  }
180  }//loop over all the active voxels and tiles
181  //}
182 
183  BaseT::end();
184  return true;
185  }
186 
187  // The following methods should only be called after the
188  // the operator() method was called
189  void print(const std::string &name, std::ostream& os = std::cout) const
190  {
191  os << "Uniformely scattered " << mPointCount << " points into " << mVoxelCount
192  << " active voxels in \"" << name << "\" corresponding to "
193  << mPointsPerVolume << " points per volume." << std::endl;
194  }
195 
196  float getPointsPerVolume() const { return mPointsPerVolume; }
197  Index64 getTargetPointCount() const { return mTargetPointCount; }
198 
199 private:
200 
201  using BaseT::mPointCount;
202  using BaseT::mVoxelCount;
203  Index64 mTargetPointCount;
204  float mPointsPerVolume;
205 
206 }; // class UniformPointScatter
207 
208 /// @brief Scatters a fixed (and integer) number of points in all
209 /// active voxels and tiles.
210 template<typename PointAccessorType,
211  typename RandomGenerator,
212  typename InterruptType = util::NullInterrupter>
213 class DenseUniformPointScatter : public BasePointScatter<PointAccessorType,
214  RandomGenerator,
215  InterruptType>
216 {
217 public:
219 
220  DenseUniformPointScatter(PointAccessorType& points,
221  float pointsPerVoxel,
222  RandomGenerator& randGen,
223  double spread = 1.0,
224  InterruptType* interrupt = NULL)
225  : BaseT(points, randGen, spread, interrupt)
226  , mPointsPerVoxel(pointsPerVoxel)
227  {
228  }
229 
230  /// This is the main functor method implementing the actual scattering of points.
231  template<typename GridT>
232  bool operator()(const GridT& grid)
233  {
234  typedef typename GridT::ValueOnCIter ValueIter;
235  if (mPointsPerVoxel < 1.0e-6) return false;
236  mVoxelCount = grid.activeVoxelCount();
237  if (mVoxelCount == 0) return false;
238  BaseT::start("Dense uniform scattering with fixed point count");
239  CoordBBox bbox;
240  const Vec3R offset(0.5, 0.5, 0.5);
241 
242  const int ppv = math::Floor(mPointsPerVoxel);
243  const double delta = mPointsPerVoxel - ppv;
244  const bool fractional = !math::isApproxZero(delta, 1.0e-6);
245 
246  for (ValueIter iter = grid.cbeginValueOn(); iter; ++iter) {
247  if (BaseT::interrupt()) return false;
248  if (iter.isVoxelValue()) {// a majority is expected to be voxels
249  const Vec3R dmin = iter.getCoord() - offset;
250  for (int n = 0; n != ppv; ++n) BaseT::addPoint(grid, dmin);
251  if (fractional && BaseT::getRand01() < delta) BaseT::addPoint(grid, dmin);
252  } else {// tiles contain multiple (virtual) voxels
253  iter.getBoundingBox(bbox);
254  const Coord size(bbox.extents());
255  const Vec3R dmin = bbox.min() - offset;
256  const double d = mPointsPerVoxel * iter.getVoxelCount();
257  const int m = math::Floor(d);
258  for (int n = 0; n != m; ++n) BaseT::addPoint(grid, dmin, size);
259  if (BaseT::getRand01() < d - m) BaseT::addPoint(grid, dmin, size);
260  }
261  }//loop over all the active voxels and tiles
262  //}
263  BaseT::end();
264  return true;
265  }
266 
267  // The following methods should only be called after the
268  // the operator() method was called
269  void print(const std::string &name, std::ostream& os = std::cout) const
270  {
271  os << "Dense uniformly scattered " << mPointCount << " points into " << mVoxelCount
272  << " active voxels in \"" << name << "\" corresponding to "
273  << mPointsPerVoxel << " points per voxel." << std::endl;
274  }
275 
276  float getPointsPerVoxel() const { return mPointsPerVoxel; }
277 
278 private:
279  using BaseT::mPointCount;
280  using BaseT::mVoxelCount;
281  float mPointsPerVoxel;
282 }; // class DenseUniformPointScatter
283 
284 /// @brief Non-uniform scatters of point in the active voxels.
285 /// The local point count is implicitly defined as a product of
286 /// of a global density (called pointsPerVolume) and the local voxel
287 /// (or tile) value.
288 ///
289 /// @note This scattering technique can be significantly slower
290 /// than a uniform scattering since its computational complexity
291 /// is proportional to the active voxel (and tile) count.
292 template<typename PointAccessorType,
293  typename RandomGenerator,
294  typename InterruptType = util::NullInterrupter>
295 class NonUniformPointScatter : public BasePointScatter<PointAccessorType,
296  RandomGenerator,
297  InterruptType>
298 {
299 public:
301 
302  NonUniformPointScatter(PointAccessorType& points,
303  float pointsPerVolume,
304  RandomGenerator& randGen,
305  double spread = 1.0,
306  InterruptType* interrupt = NULL)
307  : BaseT(points, randGen, spread, interrupt)
308  , mPointsPerVolume(pointsPerVolume)//note this is merely a
309  //multiplier for the local point density
310  {
311  }
312 
313  /// This is the main functor method implementing the actual scattering of points.
314  template<typename GridT>
315  bool operator()(const GridT& grid)
316  {
317  if (mPointsPerVolume <= 0.0f) return false;
318  mVoxelCount = grid.activeVoxelCount();
319  if (mVoxelCount == 0) return false;
320  BaseT::start("Non-uniform scattering with local point density");
321  const Vec3d dim = grid.voxelSize();
322  const double volumePerVoxel = dim[0]*dim[1]*dim[2],
323  pointsPerVoxel = mPointsPerVolume * volumePerVoxel;
324  CoordBBox bbox;
325  const Vec3R offset(0.5, 0.5, 0.5);
326  for (typename GridT::ValueOnCIter iter = grid.cbeginValueOn(); iter; ++iter) {
327  if (BaseT::interrupt()) return false;
328  const double d = (*iter) * pointsPerVoxel * iter.getVoxelCount();
329  const int n = int(d);
330  if (iter.isVoxelValue()) { // a majority is expected to be voxels
331  const Vec3R dmin =iter.getCoord() - offset;
332  for (int i = 0; i < n; ++i) BaseT::addPoint(grid, dmin);
333  if (BaseT::getRand01() < (d - n)) BaseT::addPoint(grid, dmin);
334  } else { // tiles contain multiple (virtual) voxels
335  iter.getBoundingBox(bbox);
336  const Coord size(bbox.extents());
337  const Vec3R dmin = bbox.min() - offset;
338  for (int i = 0; i < n; ++i) BaseT::addPoint(grid, dmin, size);
339  if (BaseT::getRand01() < (d - n)) BaseT::addPoint(grid, dmin, size);
340  }
341  }//loop over all the active voxels and tiles
342  BaseT::end();
343  return true;
344  }
345 
346  // The following methods should only be called after the
347  // the operator() method was called
348  void print(const std::string &name, std::ostream& os = std::cout) const
349  {
350  os << "Non-uniformly scattered " << mPointCount << " points into " << mVoxelCount
351  << " active voxels in \"" << name << "\"." << std::endl;
352  }
353 
354  float getPointPerVolume() const { return mPointsPerVolume; }
355 
356 private:
357  using BaseT::mPointCount;
358  using BaseT::mVoxelCount;
359  float mPointsPerVolume;
360 
361 }; // class NonUniformPointScatter
362 
363 /// Base class of all the point scattering classes defined above
364 template<typename PointAccessorType,
365  typename RandomGenerator,
366  typename InterruptType>
367 class BasePointScatter
368 {
369 public:
370 
371  Index64 getPointCount() const { return mPointCount; }
372  Index64 getVoxelCount() const { return mVoxelCount; }
373 
374 protected:
375 
376  PointAccessorType& mPoints;
377  InterruptType* mInterrupter;
381  const double mSpread;
383 
384  /// This is a base class so the constructor is protected
385  BasePointScatter(PointAccessorType& points,
386  RandomGenerator& randGen,
387  double spread,
388  InterruptType* interrupt = NULL)
389  : mPoints(points)
391  , mPointCount(0)
392  , mVoxelCount(0)
393  , mInterruptCount(0)
394  , mSpread(math::Clamp01(spread))
395  , mRand01(randGen)
396  {
397  }
398 
399  inline void start(const char* name)
400  {
401  if (mInterrupter) mInterrupter->start(name);
402  }
403 
404  inline void end()
405  {
406  if (mInterrupter) mInterrupter->end();
407  }
408 
409  inline bool interrupt()
410  {
411  //only check interrupter for every 32'th call
412  return !(mInterruptCount++ & ((1<<5)-1)) && util::wasInterrupted(mInterrupter);
413  }
414 
415  /// @brief Return a random floating point number between zero and one
416  inline double getRand01() { return mRand01(); }
417 
418  /// @brief Return a random floating point number between 0.5 -+ mSpread/2
419  inline double getRand() { return 0.5 + mSpread * (mRand01() - 0.5); }
420 
421  template <typename GridT>
422  inline void addPoint(const GridT &grid, const Vec3R &dmin)
423  {
424  const Vec3R pos(dmin[0] + this->getRand(),
425  dmin[1] + this->getRand(),
426  dmin[2] + this->getRand());
427  mPoints.add(grid.indexToWorld(pos));
428  ++mPointCount;
429  }
430 
431  template <typename GridT>
432  inline void addPoint(const GridT &grid, const Vec3R &dmin, const Coord &size)
433  {
434  const Vec3R pos(dmin[0] + size[0]*this->getRand(),
435  dmin[1] + size[1]*this->getRand(),
436  dmin[2] + size[2]*this->getRand());
437  mPoints.add(grid.indexToWorld(pos));
438  ++mPointCount;
439  }
440 };// class BasePointScatter
441 
442 } // namespace tools
443 } // namespace OPENVDB_VERSION_NAME
444 } // namespace openvdb
445 
446 #endif // OPENVDB_TOOLS_POINT_SCATTER_HAS_BEEN_INCLUDED
447 
448 // Copyright (c) 2012-2017 DreamWorks Animation LLC
449 // All rights reserved. This software is distributed under the
450 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool operator()(const GridT &grid)
This is the main functor method implementing the actual scattering of points.
Definition: PointScatter.h:232
void addPoint(const GridT &grid, const Vec3R &dmin, const Coord &size)
Definition: PointScatter.h:432
double getRand01()
Return a random floating point number between zero and one.
Definition: PointScatter.h:416
void print(const std::string &name, std::ostream &os=std::cout) const
Definition: PointScatter.h:269
DenseUniformPointScatter(PointAccessorType &points, float pointsPerVoxel, RandomGenerator &randGen, double spread=1.0, InterruptType *interrupt=NULL)
Definition: PointScatter.h:220
GLsizei const GLchar *const * string
Definition: glcorearb.h:813
bool operator()(const GridT &grid)
This is the main functor method implementing the actual scattering of points.
Definition: PointScatter.h:143
Dummy NOOP interrupter class defining interface.
png_uint_32 i
Definition: png.h:2877
Index64 pointCount(const PointDataTreeT &tree, const bool inCoreOnly=false)
Total points in the PointDataTree.
Definition: PointCount.h:198
Simple random integer generator.
Definition: Math.h:179
GLsizeiptr size
Definition: glcorearb.h:663
GLdouble n
Definition: glcorearb.h:2007
GLfloat f
Definition: glcorearb.h:1925
double getRand()
Return a random floating point number between 0.5 -+ mSpread/2.
Definition: PointScatter.h:419
The two point scatters UniformPointScatter and NonUniformPointScatter depend on the following two cla...
Definition: PointScatter.h:112
#define OPENVDB_VERSION_NAME
Definition: version.h:43
math::Rand01< double, RandomGenerator > mRand01
Definition: PointScatter.h:382
General-purpose arithmetic and comparison routines, most of which accept arbitrary value types (or at...
UniformPointScatter(PointAccessorType &points, float pointsPerVolume, RandomGenerator &randGen, double spread=1.0, InterruptType *interrupt=NULL)
Definition: PointScatter.h:129
GLintptr offset
Definition: glcorearb.h:664
void addPoint(const GridT &grid, const Vec3R &dmin)
Definition: PointScatter.h:422
GLuint const GLchar * name
Definition: glcorearb.h:785
bool isApproxZero(const Type &x)
Return true if x is equal to zero to within the default floating-point comparison tolerance...
Definition: Math.h:336
Non-uniform scatters of point in the active voxels. The local point count is implicitly defined as a ...
Definition: PointScatter.h:295
NonUniformPointScatter(PointAccessorType &points, float pointsPerVolume, RandomGenerator &randGen, double spread=1.0, InterruptType *interrupt=NULL)
Definition: PointScatter.h:302
BasePointScatter< PointAccessorType, RandomGenerator, InterruptType > BaseT
Definition: PointScatter.h:300
BasePointScatter< PointAccessorType, RandomGenerator, InterruptType > BaseT
Definition: PointScatter.h:218
typedef int
Definition: png.h:1175
void print(const std::string &name, std::ostream &os=std::cout) const
Definition: PointScatter.h:189
void print(const std::string &name, std::ostream &os=std::cout) const
Definition: PointScatter.h:348
BasePointScatter(PointAccessorType &points, RandomGenerator &randGen, double spread, InterruptType *interrupt=NULL)
This is a base class so the constructor is protected.
Definition: PointScatter.h:385
int Floor(float x)
Return the floor of x.
Definition: Math.h:814
UniformPointScatter(PointAccessorType &points, Index64 pointCount, RandomGenerator &randGen, double spread=1.0, InterruptType *interrupt=NULL)
Definition: PointScatter.h:119
Scatters a fixed (and integer) number of points in all active voxels and tiles.
Definition: PointScatter.h:213
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
BasePointScatter< PointAccessorType, RandomGenerator, InterruptType > BaseT
Definition: PointScatter.h:117
bool wasInterrupted(T *i, int percent=-1)
bool operator()(const GridT &grid)
This is the main functor method implementing the actual scattering of points.
Definition: PointScatter.h:315
Type Clamp01(Type x)
Return x clamped to [0, 1].
Definition: Math.h:256