OpenVDB  3.0.0
PointPartitioner.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2014 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 //
41 
42 #ifndef OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
43 #define OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
44 
45 
46 #include <openvdb/Types.h>
47 #include <openvdb/math/Transform.h>
48 
49 #include <vector>
50 #include <deque>
51 #include <algorithm> // std::swap
52 
53 #include <boost/scoped_array.hpp>
54 #include <boost/integer.hpp> // boost::int_t<N>::least
55 #include <boost/math/special_functions/fpclassify.hpp>//for boost::math::isfinite
56 
57 #include <tbb/atomic.h>
58 #include <tbb/blocked_range.h>
59 #include <tbb/parallel_for.h>
60 #include <tbb/parallel_reduce.h>
61 #include <tbb/parallel_sort.h>
62 #include <tbb/task_group.h>
63 #include <tbb/task_scheduler_init.h>
64 
65 namespace openvdb {
67 namespace OPENVDB_VERSION_NAME {
68 namespace tools {
69 
70 
72 
73 
74 // Expected interface for the PointArray container:
75 //
76 // template<typename VectorType>
77 // struct PointList {
78 // typedef VectorType position_type;
79 // size_t size() const;
80 // void getPos(size_t n, VectorType& xyz) const;
81 // };
82 
83 
91 template<typename PointIndexT = uint32_t, Index Log2Dim = 3>
93 {
94 public:
95  enum { LOG2DIM = Log2Dim };
96 
97  typedef boost::shared_ptr<PointPartitioner> Ptr;
98  typedef boost::shared_ptr<const PointPartitioner> ConstPtr;
99 
100  typedef PointIndexT IndexType;
101  typedef typename boost::int_t<1 + (3 * Log2Dim)>::least VoxelOffsetType;
102  typedef boost::scoped_array<VoxelOffsetType> VoxelOffsetArray;
103 
104  class IndexIterator;
105 
107 
109 
116  template<typename PointArray>
117  void construct(const PointArray& points, const math::Transform& xform,
118  bool voxelOrder = false, bool recordVoxelOffsets = false);
119 
120 
127  template<typename PointArray>
128  static Ptr create(const PointArray& points, const math::Transform& xform,
129  bool voxelOrder = false, bool recordVoxelOffsets = false);
130 
131 
133  size_t size() const { return mPageCount; }
134 
136  bool empty() const { return mPageCount == 0; }
137 
139  void clear();
140 
142  void swap(PointPartitioner&);
143 
145  IndexIterator indices(size_t n) const;
146 
148  CoordBBox getBBox(size_t n) const {
149  return CoordBBox::createCube(mPageCoordinates[n], (1u << Log2Dim));
150  }
151 
153  const Coord& origin(size_t n) const { return mPageCoordinates[n]; }
154 
157  const VoxelOffsetArray& voxelOffsets() const { return mVoxelOffsets; }
158 
159 private:
160  // Disallow copying
162  PointPartitioner& operator=(const PointPartitioner&);
163 
164  boost::scoped_array<IndexType> mPointIndices;
165  VoxelOffsetArray mVoxelOffsets;
166 
167  boost::scoped_array<IndexType> mPageOffsets;
168  boost::scoped_array<Coord> mPageCoordinates;
169  IndexType mPageCount;
170 }; // class PointPartitioner
171 
172 
174 
175 
176 template<typename PointIndexT, Index Log2Dim>
177 class PointPartitioner<PointIndexT, Log2Dim>::IndexIterator
178 {
179 public:
180  typedef PointIndexT IndexType;
181 
182  IndexIterator(IndexType* begin = NULL, IndexType* end = NULL)
183  : mBegin(begin), mEnd(end), mItem(begin) {}
184 
186  void reset() { mItem = mBegin; }
187 
189  size_t size() const { return mEnd - mBegin; }
190 
192  IndexType& operator*() { assert(mItem != NULL); return *mItem; }
193  const IndexType& operator*() const { assert(mItem != NULL); return *mItem; }
194 
196  operator bool() const { return mItem < mEnd; }
197  bool test() const { return mItem < mEnd; }
198 
200  IndexIterator& operator++() { assert(this->test()); ++mItem; return *this; }
201 
203  bool next() { this->operator++(); return this->test(); }
204  bool increment() { this->next(); return this->test(); }
205 
207  bool operator==(const IndexIterator& other) const { return mItem == other.mItem; }
208  bool operator!=(const IndexIterator& other) const { return !this->operator==(other); }
209 
210 private:
211  IndexType * const mBegin, * const mEnd;
212  IndexType * mItem;
213 }; // class PointPartitioner::IndexIterator
214 
215 
217 
218 // Implementation details
219 
220 
221 namespace point_partitioner_internal {
222 
223 enum { LEAF_NODE_LIMIT = 1000000000 };
224 
226 
227 
228 template<typename PointArray>
230  typedef typename PointArray::value_type PointType;
231  typedef typename PointType::value_type ElementType;
232 
233  ComputeBBoxOp(const PointArray& points)
234  : mPoints(&points)
235  , mMin(std::numeric_limits<ElementType>::max())
236  , mMax(-std::numeric_limits<ElementType>::max())
237  {
238  }
239 
240  ComputeBBoxOp(const ComputeBBoxOp& other, tbb::split)
241  : mPoints(other.mPoints)
242  , mMin(std::numeric_limits<ElementType>::max())
243  , mMax(-std::numeric_limits<ElementType>::max())
244  {
245  }
246 
247  void operator()(const tbb::blocked_range<size_t>& range) {
248 
249  PointType pos, tmpMin(mMin), tmpMax(mMax);
250 
251  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
252  mPoints->getPos(n, pos);
253 
254  if (boost::math::isfinite(pos[0]) &&
255  boost::math::isfinite(pos[1]) &&
256  boost::math::isfinite(pos[2])) {
257  tmpMin[0] = std::min(tmpMin[0], pos[0]);
258  tmpMin[1] = std::min(tmpMin[1], pos[1]);
259  tmpMin[2] = std::min(tmpMin[2], pos[2]);
260  tmpMax[0] = std::max(tmpMax[0], pos[0]);
261  tmpMax[1] = std::max(tmpMax[1], pos[1]);
262  tmpMax[2] = std::max(tmpMax[2], pos[2]);
263  }
264  }
265 
266  mMin[0] = std::min(tmpMin[0], mMin[0]);
267  mMin[1] = std::min(tmpMin[1], mMin[1]);
268  mMin[2] = std::min(tmpMin[2], mMin[2]);
269  mMax[0] = std::max(tmpMax[0], mMax[0]);
270  mMax[1] = std::max(tmpMax[1], mMax[1]);
271  mMax[2] = std::max(tmpMax[2], mMax[2]);
272  }
273 
274  void join(ComputeBBoxOp& other) {
275  mMin[0] = std::min(mMin[0], other.mMin[0]);
276  mMin[1] = std::min(mMin[1], other.mMin[1]);
277  mMin[2] = std::min(mMin[2], other.mMin[2]);
278  mMax[0] = std::max(mMax[0], other.mMax[0]);
279  mMax[1] = std::max(mMax[1], other.mMax[1]);
280  mMax[2] = std::max(mMax[2], other.mMax[2]);
281  }
282 
284 
285  PointArray const * const mPoints;
286  PointType mMin, mMax;
287 };
288 
289 
291 
292 
293 template<typename IndexT>
294 struct IndexPair {
295  IndexT first, second;
296 
297  bool operator<(const IndexPair& rhs) const {
298  return first < rhs.first;
299  }
300 };
301 
302 
303 template<typename PointArray, typename IndexT, typename VoxelOffsetT>
305 {
306  typedef typename PointArray::value_type PointType;
307  typedef boost::scoped_array<IndexT> IndexArray;
308  typedef boost::scoped_array<VoxelOffsetT> VoxelOffsetArray;
309 
311  VoxelOffsetArray& voxelOffsets, IndexArray& bucketOffsets,
312  const PointArray& points, const math::Transform& m,
313  const CoordBBox& bbox, int log2dim)
314  : mVoxelOffsets(voxelOffsets.get())
315  , mBucketOffsets(bucketOffsets.get())
316  , mPoints(&points)
317  , mXForm(m)
318  , mBBox(bbox)
319  , mDim(bbox.dim())
320  , mBlockLog2Dim(log2dim)
321  {
322  }
323 
324 
325  void operator()(const tbb::blocked_range<size_t>& range) const {
326  PointType pos;
327  Coord ijk(0, 0, 0), loc(0, 0, 0);
328 
329  const int xMin = mBBox.min()[0], yMin = mBBox.min()[1], zMin = mBBox.min()[2];
330  const int yzDim = mDim[1] * mDim[2], zDim = mDim[2];
331 
332  const int log2dim = mBlockLog2Dim, log2dim2 = 2 * mBlockLog2Dim,
333  mask = unsigned(1u << mBlockLog2Dim) - 1u;
334 
335  IndexT bucketOffset = 0;
336  VoxelOffsetT voxelOffset = 0;
337 
338  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
339 
340  mPoints->getPos(n, pos);
341 
342  if (boost::math::isfinite(pos[0]) &&
343  boost::math::isfinite(pos[1]) &&
344  boost::math::isfinite(pos[2])) {
345 
346  ijk = mXForm.worldToIndexCellCentered(pos);
347 
348  // coord to offset
349  if (mVoxelOffsets) {
350  loc[0] = ijk[0] & mask;
351  loc[1] = ijk[1] & mask;
352  loc[2] = ijk[2] & mask;
353 
354  voxelOffset = VoxelOffsetT((loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
355  }
356 
357  ijk[0] >>= log2dim;
358  ijk[1] >>= log2dim;
359  ijk[2] >>= log2dim;
360 
361  ijk[0] -= xMin;
362  ijk[1] -= yMin;
363  ijk[2] -= zMin;
364 
365  bucketOffset = IndexT(ijk[0] * yzDim + ijk[1] * zDim + ijk[2]);
366  mBucketOffsets[n] = bucketOffset;
367 
368  if (mVoxelOffsets) mVoxelOffsets[n] = voxelOffset;
369  }
370  }
371  }
372 
374 
375  VoxelOffsetT * const mVoxelOffsets;
376  IndexT * const mBucketOffsets;
377  PointArray const * const mPoints;
378 
380  const CoordBBox mBBox;
381  const Coord mDim;
382  const int mBlockLog2Dim;
383 };
384 
385 
386 template<typename PointArray, typename IndexT, typename VoxelOffsetT>
388 {
389  typedef typename PointArray::value_type PointType;
391  typedef boost::scoped_array<IndexPairT> IndexPairArray;
392  typedef boost::scoped_array<VoxelOffsetT> VoxelOffsetArray;
393 
395  VoxelOffsetArray& voxelOffsets, IndexPairArray& bucketOffsets,
396  const PointArray& points, const math::Transform& m,
397  const CoordBBox& bbox, int log2dim)
398  : mVoxelOffsets(voxelOffsets.get())
399  , mBucketOffsets(bucketOffsets.get())
400  , mPoints(&points)
401  , mXForm(m)
402  , mBBox(bbox)
403  , mDim(bbox.dim())
404  , mBlockLog2Dim(log2dim)
405  {
406  }
407 
408 
409  void operator()(const tbb::blocked_range<size_t>& range) const {
410  PointType pos;
411  Coord ijk(0, 0, 0), loc(0, 0, 0);
412 
413  const int xMin = mBBox.min()[0], yMin = mBBox.min()[1], zMin = mBBox.min()[2];
414  const int yzDim = mDim[1] * mDim[2], zDim = mDim[2];
415 
416  const int log2dim = mBlockLog2Dim, log2dim2 = 2 * mBlockLog2Dim,
417  mask = unsigned(1u << mBlockLog2Dim) - 1u;
418 
419  IndexT bucketOffset = 0;
420  VoxelOffsetT voxelOffset = 0;
421 
422  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
423 
424  mPoints->getPos(n, pos);
425 
426  if (boost::math::isfinite(pos[0]) &&
427  boost::math::isfinite(pos[1]) &&
428  boost::math::isfinite(pos[2])) {
429  ijk = mXForm.worldToIndexCellCentered(pos);
430 
431  // coord to offset
432  if (mVoxelOffsets) {
433  loc[0] = ijk[0] & mask;
434  loc[1] = ijk[1] & mask;
435  loc[2] = ijk[2] & mask;
436 
437  voxelOffset = VoxelOffsetT((loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
438  }
439 
440  ijk[0] >>= log2dim;
441  ijk[1] >>= log2dim;
442  ijk[2] >>= log2dim;
443 
444  ijk[0] -= xMin;
445  ijk[1] -= yMin;
446  ijk[2] -= zMin;
447 
448  bucketOffset = IndexT(ijk[0] * yzDim + ijk[1] * zDim + ijk[2]);
449 
450  IndexPairT& item = mBucketOffsets[n];
451 
452  item.first = bucketOffset;
453  item.second = IndexT(n);
454 
455  if (mVoxelOffsets) mVoxelOffsets[n] = voxelOffset;
456  }
457  }
458  }
459 
461 
462  VoxelOffsetT * const mVoxelOffsets;
463  IndexPairT * const mBucketOffsets;
464  PointArray const * const mPoints;
465 
467  const CoordBBox mBBox;
468  const Coord mDim;
469  const int mBlockLog2Dim;
470 };
471 
472 
473 
474 template<typename IndexT>
476 {
477  typedef tbb::atomic<IndexT> AtomicIndex;
478  typedef boost::scoped_array<AtomicIndex> AtomicIndexArray;
479  typedef boost::scoped_array<IndexT> IndexArray;
480 
481  BucketMapOp(IndexArray& bucketIndices,
482  AtomicIndexArray& bucketMap, const IndexArray& bucketOffsets)
483  : mBucketIndices(bucketIndices.get())
484  , mBucketMap(bucketMap.get())
485  , mBucketOffsets(bucketOffsets.get())
486  {
487  }
488 
489  void operator()(const tbb::blocked_range<size_t>& range) const {
490  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
491  mBucketIndices[n] = mBucketMap[mBucketOffsets[n]].fetch_and_increment();
492  }
493  }
494 
495  IndexT * const mBucketIndices;
496  AtomicIndex * const mBucketMap;
497  IndexT const * const mBucketOffsets;
498 };
499 
500 
501 template<typename IndexT>
503 {
504  typedef tbb::atomic<IndexT> AtomicIndex;
505  typedef boost::scoped_array<AtomicIndex> AtomicIndexArray;
506  typedef boost::scoped_array<IndexT> IndexArray;
507 
508  MergeOffsetsOp(IndexArray& pointIndices,
509  const AtomicIndexArray& bucketMap, const IndexArray& bucketOffsets)
510  : mPointIndices(pointIndices.get())
511  , mBucketMap(bucketMap.get())
512  , mBucketOffsets(bucketOffsets.get())
513  {
514  }
515 
516  void operator()(const tbb::blocked_range<size_t>& range) const {
517  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
518  mPointIndices[n] += mBucketMap[mBucketOffsets[n]];
519  }
520  }
521 
522  IndexT * const mPointIndices;
523  AtomicIndex const * const mBucketMap;
524  IndexT const * const mBucketOffsets;
525 };
526 
527 
528 template<typename IndexT>
530 {
531  typedef boost::scoped_array<IndexT> IndexArray;
532 
533  BucketOrderOp(IndexArray& pointIndices, IndexArray& bucketOffsets)
534  : mPointIndices(pointIndices.get())
535  , mBucketOffsets(bucketOffsets.get())
536  {
537  }
538 
539  void operator()(const tbb::blocked_range<size_t>& range) const {
540  for (IndexT n = static_cast<IndexT>(range.begin()), N = static_cast<IndexT>(range.end());
541  n != N; ++n)
542  {
543  mBucketOffsets[mPointIndices[n]] = n;
544  }
545  }
546 
547  IndexT const * const mPointIndices;
548  IndexT * const mBucketOffsets;
549 };
550 
551 template<typename IndexT>
553 {
554  typedef boost::scoped_array<IndexT> IndexArray;
555  typedef boost::scoped_array<IndexPair<IndexT> > IndexPairArray;
556 
557  PageOrderOp(IndexArray& pointIndices, const IndexPairArray& pairs)
558  : mPointIndices(pointIndices.get())
559  , mPairs(pairs.get())
560  {
561  }
562 
563  void operator()(const tbb::blocked_range<size_t>& range) const {
564  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
565  mPointIndices[n] = mPairs[n].second;
566  }
567  }
568 
569  IndexT * const mPointIndices;
570  IndexPair<IndexT> const * const mPairs;
571 };
572 
573 template<typename IndexT>
575 {
576  typedef std::pair<IndexT, IndexT> Range;
577  typedef boost::scoped_array<IndexT> IndexArray;
578  typedef boost::scoped_array<IndexPair<IndexT> > IndexPairArray;
579 
580  PageBreakOp(const Range& range, const IndexPairArray& pairs,
581  IndexArray& segment, IndexT& size)
582  : mRange(range)
583  , mPairs(pairs.get())
584  , mSegment(&segment)
585  , mSize(&size)
586  {
587  }
588 
589  void operator()() const {
590 
591  const IndexT start = mRange.first;
592  const IndexT end = mRange.second;
593 
594  std::deque<IndexT> pageBreaks;
595 
596  IndexT last = mPairs[start].first;
597  for (IndexT n = start + 1; n != end; ++n) {
598  const IndexPair<IndexT>& pair = mPairs[n];
599  if (last != pair.first) {
600  last = pair.first;
601  pageBreaks.push_back(n);
602  }
603  }
604 
605  if (!pageBreaks.empty()) {
606 
607  IndexArray segment(new IndexT[pageBreaks.size()]);
608  IndexT* item = segment.get();
609 
610  typename std::deque<IndexT>::iterator it = pageBreaks.begin();
611  while (it != pageBreaks.end()) {
612  *item++ = *it++;
613  }
614 
615  mSegment->swap(segment);
616  *mSize = static_cast<IndexT>(pageBreaks.size());
617  }
618  }
619 
620  Range mRange;
621  IndexPair<IndexT> const * const mPairs;
622  IndexArray * const mSegment;
623  IndexT * const mSize;
624 };
625 
626 
627 
628 template<typename IndexT, Index Log2Dim>
630 {
631  typedef typename boost::int_t<1 + (3 * Log2Dim)>::least VoxelOffsetT;
632  typedef boost::scoped_array<VoxelOffsetT> VoxelOffsetArray;
633  typedef boost::scoped_array<IndexT> IndexArray;
634 
635  VoxelOrderOp(IndexArray& indices, const IndexArray& pages,const VoxelOffsetArray& offsets)
636  : mIndices(indices.get())
637  , mPages(pages.get())
638  , mVoxelOffsets(offsets.get())
639  {
640  }
641 
642 
643  void operator()(const tbb::blocked_range<size_t>& range) const {
644 
645  IndexT pointCount = 0;
646  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
647  pointCount = std::max(pointCount, (mPages[n + 1] - mPages[n]));
648  }
649 
650  const IndexT voxelCount = 1 << (3 * Log2Dim);
651 
652  // allocate histogram buffers
653  boost::scoped_array<VoxelOffsetT> offsets(new VoxelOffsetT[pointCount]);
654  boost::scoped_array<IndexT> sortedIndices(new IndexT[pointCount]);
655  boost::scoped_array<IndexT> histogram(new IndexT[voxelCount]);
656 
657  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
658 
659  IndexT * const indices = mIndices + mPages[n];
660  pointCount = mPages[n + 1] - mPages[n];
661 
662  // local copy of voxel offsets.
663  for (IndexT i = 0; i < pointCount; ++i) {
664  offsets[i] = mVoxelOffsets[ indices[i] ];
665  }
666 
667  // reset histogram
668  memset(&histogram[0], 0, voxelCount * sizeof(IndexT));
669 
670  // compute histogram
671  for (IndexT i = 0; i < pointCount; ++i) {
672  ++histogram[ offsets[i] ];
673  }
674 
675  IndexT count = 0, startOffset;
676  for (int i = 0; i < int(voxelCount); ++i) {
677  if (histogram[i] > 0) {
678  startOffset = count;
679  count += histogram[i];
680  histogram[i] = startOffset;
681  }
682  }
683 
684  // sort indices based on voxel offset
685  for (IndexT i = 0; i < pointCount; ++i) {
686  sortedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
687  }
688 
689  memcpy(&indices[0], &sortedIndices[0], sizeof(IndexT) * pointCount);
690  }
691  }
692 
693 
694  IndexT * const mIndices;
695  IndexT const * const mPages;
696  VoxelOffsetT const * const mVoxelOffsets;
697 };
698 
699 
700 template<typename IndexT>
702 {
703  typedef boost::scoped_array<IndexT> IndexArray;
704 
705  IndexOrderOp(IndexArray& indices, const IndexArray& pages)
706  : mIndices(indices.get()) , mPages(pages.get()) { }
707 
708  void operator()(const tbb::blocked_range<size_t>& range) const {
709  for (size_t n(range.begin()), N(range.end()); n != N; ++n)
710  std::sort(mIndices + mPages[n], mIndices + mPages[n+1]);
711  }
712 
713  IndexT * const mIndices;
714  IndexT const * const mPages;
715 };
716 
717 
718 template<typename PointArray, typename IndexT>
720 {
721  typedef boost::scoped_array<IndexT> IndexArray;
722  typedef boost::scoped_array<Coord> CoordArray;
723 
724  LeafNodeOriginOp(CoordArray& coordinates,
725  const IndexArray& indices, const IndexArray& pages,
726  const PointArray& points, const math::Transform& m, int log2dim)
727  : mCoordinates(coordinates.get())
728  , mIndices(indices.get())
729  , mPages(pages.get())
730  , mPoints(&points)
731  , mXForm(m)
732  , mLog2Dim(log2dim)
733  {
734  }
735 
736  void operator()(const tbb::blocked_range<size_t>& range) const {
737 
738  const int mask = ~((1 << mLog2Dim) - 1);
739  Coord ijk;
740  typename PointArray::value_type pos;
741  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
742 
743  mPoints->getPos(mIndices[mPages[n]], pos);
744 
745  if (boost::math::isfinite(pos[0]) &&
746  boost::math::isfinite(pos[1]) &&
747  boost::math::isfinite(pos[2])) {
748 
749  ijk = mXForm.worldToIndexCellCentered(pos);
750 
751  ijk[0] &= mask;
752  ijk[1] &= mask;
753  ijk[2] &= mask;
754 
755  mCoordinates[n] = ijk;
756  }
757  }
758  }
759 
761 
762  Coord * const mCoordinates;
763  IndexT const * const mIndices;
764  IndexT const * const mPages;
765  PointArray const * const mPoints;
766 
768  const int mLog2Dim;
769 };
770 
771 
773 
774 
775 // Tests whether the given bbox volume can be computed without
776 // overflowing the given IntType
777 template<typename IntType>
778 inline bool
779 isVolumeCalculationOverflowSafe(const CoordBBox& bbox)
780 {
781  const uint64_t xdim = uint64_t(bbox.max()[0] - bbox.min()[0]);
782  const uint64_t ydim = uint64_t(bbox.max()[1] - bbox.min()[1]);
783  const uint64_t zdim = uint64_t(bbox.max()[2] - bbox.min()[2]);
784 
785  uint64_t product = xdim * ydim;
786  if (product > std::numeric_limits<IntType>::max()) return false;
787 
788  product *= zdim;
789  if (product > std::numeric_limits<IntType>::max()) return false;
790  return true;
791 }
792 
793 
795 
796 template<typename PointArray>
797 inline CoordBBox
798 computeLeafBounds(const PointArray& points, const math::Transform& m, unsigned log2dim)
799 {
800  ComputeBBoxOp<PointArray> bboxOp(points);
801  tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), bboxOp);
802 
803  CoordBBox box;
804 
805  if (m.isLinear()) {
806  box.min() = m.worldToIndexCellCentered(bboxOp.mMin);
807  box.max() = m.worldToIndexCellCentered(bboxOp.mMax);
808  } else {
809  Vec3d minIS, maxIS;
810  math::calculateBounds(m, bboxOp.mMin, bboxOp.mMax, minIS, maxIS);
811  box.min() = math::Coord::round(minIS);
812  box.max() = math::Coord::round(maxIS);
813  }
814 
815  box.min() >>= log2dim;
816  box.max() >>= log2dim;
817  return box;
818 }
819 
820 
821 template<Index Log2Dim, typename IndexT, typename VoxelOffsetT, typename PointArray>
822 inline void partition(
823  const PointArray& points,
824  const math::Transform& xform,
825  const CoordBBox& bbox,
826  boost::scoped_array<IndexT>& pointIndices,
827  boost::scoped_array<IndexT>& pageOffsets,
828  IndexT& pageCount,
829  boost::scoped_array<VoxelOffsetT>& voxelOffsets,
830  bool recordVoxelOffsets)
831 {
832  typedef tbb::atomic<IndexT> AtomicIndexT;
833  typedef boost::scoped_array<AtomicIndexT> AtomicIndexArray;
834  typedef boost::scoped_array<IndexT> IndexArray;
835 
837 
838  // Compute voxel and bucket offsets
839 
840  const size_t pointCount = points.size();
841  const tbb::blocked_range<size_t> pointRange(0, pointCount);
842 
843  if (recordVoxelOffsets) {
844  voxelOffsets.reset(new VoxelOffsetT[pointCount]);
845  } else {
846  voxelOffsets.reset();
847  }
848 
849  IndexArray bucketOffsets(new IndexT[pointCount]);
850 
851  tbb::parallel_for(pointRange, BucketAndVoxelOffsetOp<
852  PointArray, IndexT, VoxelOffsetT>(
853  voxelOffsets, bucketOffsets, points, xform, bbox, int(Log2Dim)));
854 
855  // Compute bucket indices and bucket point counts
856 
857  const Index64 volume = bbox.volume();
858 
859  pointIndices.reset(new IndexT[pointCount]);
860  AtomicIndexArray bucketMap(new AtomicIndexT[volume]);
861  memset(&bucketMap[0], 0, sizeof(AtomicIndexT) * volume);
862 
863  tbb::parallel_for(pointRange,
864  BucketMapOp<IndexT>(pointIndices, bucketMap, bucketOffsets));
865 
866  // Initialize page offsets and update bucket map with global start index.
867  {
868  pageCount = 0;
869  for (size_t n(0), N(volume); n < N; ++n) {
870  pageCount += static_cast<IndexT>(bucketMap[n] != 0);
871  }
872 
873  pageOffsets.reset(new IndexT[pageCount + 1]);
874  IndexT count = 0;
875  for (size_t n = 0, idx = 0; n < volume; ++n) {
876  if (bucketMap[n] != 0) {
877  pageOffsets[idx] = count;
878  count += bucketMap[n];
879  bucketMap[n] = pageOffsets[idx];
880  ++idx;
881  }
882  }
883 
884  pageOffsets[pageCount] = count;
885  }
886 
887 
888  // Merge bucket offsets with bucket indices
889  tbb::parallel_for(pointRange,
890  MergeOffsetsOp<IndexT>(pointIndices, bucketMap, bucketOffsets));
891 
892  bucketMap.reset();
893 
894  // Bucket order indices
895  tbb::parallel_for(pointRange, BucketOrderOp<IndexT>(pointIndices, bucketOffsets));
896 
897  pointIndices.swap(bucketOffsets);
898  bucketOffsets.reset();
899 }
900 
901 
902 template<Index Log2Dim, typename IndexT, typename VoxelOffsetT, typename PointArray>
903 inline void sortPartition(
904  const PointArray& points,
905  const math::Transform& xform,
906  const CoordBBox& bbox,
907  boost::scoped_array<IndexT>& pointIndices,
908  boost::scoped_array<IndexT>& pageOffsets,
909  IndexT& pageCount,
910  boost::scoped_array<VoxelOffsetT>& voxelOffsets,
911  bool recordVoxelOffsets)
912 {
913  typedef boost::scoped_array<IndexT> IndexArray;
914  typedef IndexPair<IndexT> IndexPairT;
915  typedef boost::scoped_array<IndexPairT> IndexPairArray;
916 
918 
919  const size_t pointCount = points.size();
920  const tbb::blocked_range<size_t> pointRange(0, pointCount);
921 
922  if (recordVoxelOffsets) {
923  voxelOffsets.reset(new VoxelOffsetT[pointCount]);
924  } else {
925  voxelOffsets.reset();
926  }
927 
928  IndexPairArray bucketOffsets(new IndexPairT[pointCount]);
929  tbb::parallel_for(pointRange, ComputeOffsetOp<
930  PointArray, IndexT, VoxelOffsetT>(
931  voxelOffsets, bucketOffsets, points, xform, bbox, int(Log2Dim)));
932 
933  tbb::parallel_sort(bucketOffsets.get(), bucketOffsets.get() + pointCount);
934 
935  { // Compute page offsets
936  const size_t nthreads = tbb::task_scheduler_init::default_num_threads();
937  const size_t ntasks = nthreads > 1 ? 2 * nthreads : 1;
938 
939  if (ntasks > 1) {
940 
941  IndexArray segmentSizes(new IndexT[ntasks]);
942  memset(segmentSizes.get(), 0, ntasks * sizeof(IndexT));
943  boost::scoped_array<IndexArray> segments(new IndexArray[ntasks]);
944 
945  const IndexT grainSize = static_cast<IndexT>(pointCount / ntasks);
946  const IndexT end = static_cast<IndexT>(grainSize * (ntasks - 1));
947 
948  tbb::task_group tasks;
949 
950  IndexT idx = 0;
951  std::pair<IndexT, IndexT> range;
952 
953  // create tasks
954  range.first = 0;
955  range.second = grainSize;
956  tasks.run(PageBreakOp<IndexT>(range, bucketOffsets, segments[idx], segmentSizes[idx]));
957  ++idx;
958 
959  for (IndexT n = grainSize; n < end; n += grainSize) {
960  range.first = n-1;
961  range.second = n+grainSize;
962  tasks.run(PageBreakOp<IndexT>(range, bucketOffsets, segments[idx], segmentSizes[idx]));
963  ++idx;
964  }
965 
966  range.first = end-1;
967  range.second = static_cast<IndexT>(pointCount);
968  tasks.run(PageBreakOp<IndexT>(range, bucketOffsets, segments[idx], segmentSizes[idx]));
969 
970  tasks.wait();
971 
972  // collect data
973  size_t pcount = 1;
974  for (size_t n = 0; n < ntasks; ++n) {
975  pcount += segmentSizes[n];
976  }
977 
978  pageCount = static_cast<IndexT>(pcount);
979  pageOffsets.reset(new IndexT[pageCount + 1]);
980 
981  pcount = 1;
982  for (size_t n = 0; n < ntasks; ++n) {
983  const IndexT size = segmentSizes[n];
984  if(size != 0) {
985  memcpy(pageOffsets.get() + pcount, segments[n].get(), size * sizeof(IndexT));
986  pcount += size;
987  }
988  }
989 
990  pageOffsets[0] = 0;
991  pageOffsets[pageCount] = static_cast<IndexT>(pointCount);
992 
993  } else {
994 
995  std::deque<IndexT> pageBreaks;
996  IndexT last = bucketOffsets[0].first;
997 
998  for (IndexT n = 1; n != pointCount; ++n) {
999  if (last != bucketOffsets[n].first) {
1000  last = bucketOffsets[n].first;
1001  pageBreaks.push_back(n);
1002  }
1003  }
1004 
1005  pageCount = static_cast<IndexT>(pageBreaks.size() + 1);
1006  pageOffsets.reset(new IndexT[pageCount + 1]);
1007 
1008  if (!pageBreaks.empty()) {
1009 
1010  IndexT* item = pageOffsets.get() + 1;
1011 
1012  typename std::deque<IndexT>::iterator it = pageBreaks.begin();
1013  while (it != pageBreaks.end()) {
1014  *item++ = *it++;
1015  }
1016  }
1017 
1018  pageOffsets[0] = 0;
1019  pageOffsets[pageCount] = static_cast<IndexT>(pointCount);
1020  }
1021  }
1022 
1023  pointIndices.reset(new IndexT[pointCount]);
1024  tbb::parallel_for(pointRange, PageOrderOp<IndexT>(pointIndices, bucketOffsets));
1025 }
1026 
1027 } // namespace point_partitioner_internal
1028 
1029 
1031 
1032 
1033 template<typename PointIndexT, Index Log2Dim>
1035  : mPointIndices(NULL)
1036  , mVoxelOffsets(NULL)
1037  , mPageOffsets(NULL)
1038  , mPageCoordinates(NULL)
1039  , mPageCount(0)
1040 {
1041 }
1042 
1043 
1044 template<typename PointIndexT, Index Log2Dim>
1045 inline void
1047 {
1048  mPageCount = 0;
1049  mPointIndices.reset();
1050  mVoxelOffsets.reset();
1051  mPageOffsets.reset();
1052  mPageCoordinates.reset();
1053 }
1054 
1055 
1056 template<typename PointIndexT, Index Log2Dim>
1057 inline void
1059 {
1060  std::swap(mPageCount, rhs.mPageCount);
1061  mPointIndices.swap(rhs.mPointIndices);
1062  mVoxelOffsets.swap(rhs.mVoxelOffsets);
1063  mPageOffsets.swap(rhs.mPageOffsets);
1064  mPageCoordinates.swap(rhs.mPageCoordinates);
1065 }
1066 
1067 
1068 template<typename PointIndexT, Index Log2Dim>
1071 {
1072  assert(bool(mPointIndices) && bool(mPageCount));
1073  return IndexIterator(
1074  mPointIndices.get() + mPageOffsets[n],
1075  mPointIndices.get() + mPageOffsets[n + 1]);
1076 }
1077 
1078 
1079 template<typename PointIndexT, Index Log2Dim>
1080 template<typename PointArray>
1081 inline void
1083  const math::Transform& xform, bool voxelOrder, bool recordVoxelOffsets)
1084 {
1085  const CoordBBox bbox =
1086  point_partitioner_internal::computeLeafBounds(points, xform, int(Log2Dim));
1087 
1088  if(!point_partitioner_internal::isVolumeCalculationOverflowSafe<PointIndexT>(bbox)) {
1089  // the bbox is computed in leafnode space (the lattice composing of only
1090  // leafnode origins) and should rarely overflow the volume calc. in practice.
1091  OPENVDB_THROW(ArithmeticError, "Detected overflow in bbox volume computation, "
1092  "use uint64 for the PointIndexT type in the PointPartitioner.");
1093 
1097  }
1098 
1100  point_partitioner_internal::sortPartition<Log2Dim>(points, xform, bbox,
1101  mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets, (voxelOrder || recordVoxelOffsets));
1102  } else {
1103  point_partitioner_internal::partition<Log2Dim>(points, xform, bbox,
1104  mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets, (voxelOrder || recordVoxelOffsets));
1105  }
1106 
1107  const tbb::blocked_range<size_t> pageRange(0, mPageCount);
1108 
1109  tbb::parallel_for(pageRange,
1110  point_partitioner_internal::IndexOrderOp<IndexType>(mPointIndices, mPageOffsets));
1111 
1112  mPageCoordinates.reset(new Coord[mPageCount]);
1113 
1114  tbb::parallel_for(pageRange,
1116  (mPageCoordinates, mPointIndices, mPageOffsets, points, xform, Log2Dim));
1117 
1118  if (mVoxelOffsets && voxelOrder) {
1119  tbb::parallel_for(pageRange, point_partitioner_internal::VoxelOrderOp<
1120  IndexType, Log2Dim>(mPointIndices, mPageOffsets, mVoxelOffsets));
1121  }
1122 
1123  if (mVoxelOffsets && !recordVoxelOffsets) {
1124  mVoxelOffsets.reset();
1125  }
1126 }
1127 
1128 
1129 template<typename PointIndexT, Index Log2Dim>
1130 template<typename PointArray>
1133  bool voxelOrder, bool recordVoxelOffsets)
1134 {
1135  Ptr ret(new PointPartitioner());
1136  ret->construct(points, xform, voxelOrder, recordVoxelOffsets);
1137  return ret;
1138 }
1139 
1140 
1142 
1143 
1144 } // namespace tools
1145 } // namespace OPENVDB_VERSION_NAME
1146 } // namespace openvdb
1147 
1148 
1149 #endif // OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
1150 
1151 // Copyright (c) 2012-2014 DreamWorks Animation LLC
1152 // All rights reserved. This software is distributed under the
1153 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
static Ptr create(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false)
Partitions point indices into Log2Dim aligned buckets.
Definition: PointPartitioner.h:1132
math::Histogram histogram(const IterT &iter, double minVal, double maxVal, size_t numBins=10, bool threaded=true)
Iterate over a scalar grid and compute a histogram of the values of the voxels that are visited...
Definition: Statistics.h:368
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:643
boost::shared_ptr< const PointPartitioner > ConstPtr
Definition: PointPartitioner.h:98
IndexPair< IndexT > const *const mPairs
Definition: PointPartitioner.h:621
boost::scoped_array< AtomicIndex > AtomicIndexArray
Definition: PointPartitioner.h:478
const Coord & origin(size_t n) const
Returns the origin coordinate for bucket n.
Definition: PointPartitioner.h:153
IndexT *const mBucketOffsets
Definition: PointPartitioner.h:548
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:409
IndexT const *const mPages
Definition: PointPartitioner.h:695
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:554
Calculate an axis-aligned bounding box in index space from a bounding sphere in world space...
Definition: Transform.h:66
CoordBBox getBBox(size_t n) const
Returns the coordinate-aligned bounding box for bucket n.
Definition: PointPartitioner.h:148
tbb::atomic< IndexT > AtomicIndex
Definition: PointPartitioner.h:504
void operator()(const tbb::blocked_range< size_t > &range)
Definition: PointPartitioner.h:247
boost::shared_ptr< PointPartitioner > Ptr
Definition: PointPartitioner.h:97
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:479
boost::scoped_array< VoxelOffsetT > VoxelOffsetArray
Definition: PointPartitioner.h:632
bool isVolumeCalculationOverflowSafe(const CoordBBox &bbox)
Definition: PointPartitioner.h:779
uint64_t Index64
Definition: Types.h:58
PointType mMin
Definition: PointPartitioner.h:286
const CoordBBox mBBox
Definition: PointPartitioner.h:380
Coord worldToIndexCellCentered(const Vec3d &xyz) const
Apply this transformation to the given coordinates.
Definition: Transform.h:138
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
VoxelOffsetT *const mVoxelOffsets
Definition: PointPartitioner.h:462
const math::Transform mXForm
Definition: PointPartitioner.h:767
boost::scoped_array< IndexPair< IndexT > > IndexPairArray
Definition: PointPartitioner.h:578
void swap(PointPartitioner &)
Exchanges the content of the container by another.
Definition: PointPartitioner.h:1058
BucketOrderOp(IndexArray &pointIndices, IndexArray &bucketOffsets)
Definition: PointPartitioner.h:533
tbb::atomic< IndexT > AtomicIndex
Definition: PointPartitioner.h:477
const int mBlockLog2Dim
Definition: PointPartitioner.h:469
PageOrderOp(IndexArray &pointIndices, const IndexPairArray &pairs)
Definition: PointPartitioner.h:557
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:506
bool next()
Advance to the next item.
Definition: PointPartitioner.h:203
void operator()() const
Definition: PointPartitioner.h:589
bool operator<(const IndexPair &rhs) const
Definition: PointPartitioner.h:297
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:516
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:577
PointType::value_type ElementType
Definition: PointPartitioner.h:231
bool operator==(const IndexIterator &other) const
Equality operators.
Definition: PointPartitioner.h:207
PointArray::value_type PointType
Definition: PointPartitioner.h:389
BucketAndVoxelOffsetOp(VoxelOffsetArray &voxelOffsets, IndexArray &bucketOffsets, const PointArray &points, const math::Transform &m, const CoordBBox &bbox, int log2dim)
Definition: PointPartitioner.h:310
BucketMapOp(IndexArray &bucketIndices, AtomicIndexArray &bucketMap, const IndexArray &bucketOffsets)
Definition: PointPartitioner.h:481
Partitions points into Log2Dim aligned buckets.
Definition: PointPartitioner.h:92
VoxelOffsetT const *const mVoxelOffsets
Definition: PointPartitioner.h:696
void clear()
Removes all data and frees up memory.
Definition: PointPartitioner.h:1046
Coord *const mCoordinates
Definition: PointPartitioner.h:762
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:633
bool empty() const
true if the container size is 0, false otherwise.
Definition: PointPartitioner.h:136
IndexT const *const mPages
Definition: PointPartitioner.h:714
PointArray const *const mPoints
Definition: PointPartitioner.h:464
boost::scoped_array< Coord > CoordArray
Definition: PointPartitioner.h:722
VoxelOffsetT *const mVoxelOffsets
Definition: PointPartitioner.h:375
boost::scoped_array< IndexPair< IndexT > > IndexPairArray
Definition: PointPartitioner.h:555
MergeOffsetsOp(IndexArray &pointIndices, const AtomicIndexArray &bucketMap, const IndexArray &bucketOffsets)
Definition: PointPartitioner.h:508
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:736
PointArray const *const mPoints
Definition: PointPartitioner.h:377
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:721
boost::scoped_array< AtomicIndex > AtomicIndexArray
Definition: PointPartitioner.h:505
#define OPENVDB_VERSION_NAME
Definition: version.h:43
boost::scoped_array< VoxelOffsetT > VoxelOffsetArray
Definition: PointPartitioner.h:392
OPENVDB_API void calculateBounds(const Transform &t, const Vec3d &minWS, const Vec3d &maxWS, Vec3d &minIS, Vec3d &maxIS)
Calculate an axis-aligned bounding box in index space from an axis-aligned bounding box in world spac...
IndexT *const mIndices
Definition: PointPartitioner.h:713
boost::scoped_array< VoxelOffsetType > VoxelOffsetArray
Definition: PointPartitioner.h:102
const math::Transform mXForm
Definition: PointPartitioner.h:466
const Coord mDim
Definition: PointPartitioner.h:468
IndexT const *const mBucketOffsets
Definition: PointPartitioner.h:497
IndexType & operator*()
Returns the item to which this iterator is currently pointing.
Definition: PointPartitioner.h:192
IndexOrderOp(IndexArray &indices, const IndexArray &pages)
Definition: PointPartitioner.h:705
void sortPartition(const PointArray &points, const math::Transform &xform, const CoordBBox &bbox, boost::scoped_array< IndexT > &pointIndices, boost::scoped_array< IndexT > &pageOffsets, IndexT &pageCount, boost::scoped_array< VoxelOffsetT > &voxelOffsets, bool recordVoxelOffsets)
Definition: PointPartitioner.h:903
LeafNodeOriginOp(CoordArray &coordinates, const IndexArray &indices, const IndexArray &pages, const PointArray &points, const math::Transform &m, int log2dim)
Definition: PointPartitioner.h:724
IndexT *const mPointIndices
Definition: PointPartitioner.h:522
bool test() const
Definition: PointPartitioner.h:197
IndexT *const mBucketOffsets
Definition: PointPartitioner.h:376
IndexIterator & operator++()
Advance to the next item.
Definition: PointPartitioner.h:200
void construct(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false)
Partitions point indices into Log2Dim aligned buckets.
Definition: PointPartitioner.h:1082
ComputeOffsetOp(VoxelOffsetArray &voxelOffsets, IndexPairArray &bucketOffsets, const PointArray &points, const math::Transform &m, const CoordBBox &bbox, int log2dim)
Definition: PointPartitioner.h:394
AtomicIndex const *const mBucketMap
Definition: PointPartitioner.h:523
boost::scoped_array< IndexPairT > IndexPairArray
Definition: PointPartitioner.h:391
Definition: Exceptions.h:39
void reset()
Rewind to first item.
Definition: PointPartitioner.h:186
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:489
IndexPairT *const mBucketOffsets
Definition: PointPartitioner.h:463
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
PointArray const *const mPoints
Definition: PointPartitioner.h:285
PageBreakOp(const Range &range, const IndexPairArray &pairs, IndexArray &segment, IndexT &size)
Definition: PointPartitioner.h:580
Vec3< double > Vec3d
Definition: Vec3.h:629
static Coord max()
Return the largest possible coordinate.
Definition: Coord.h:75
const IndexType & operator*() const
Definition: PointPartitioner.h:193
const CoordBBox mBBox
Definition: PointPartitioner.h:467
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:703
IndexArray *const mSegment
Definition: PointPartitioner.h:622
PointArray::value_type PointType
Definition: PointPartitioner.h:306
VoxelOrderOp(IndexArray &indices, const IndexArray &pages, const VoxelOffsetArray &offsets)
Definition: PointPartitioner.h:635
PointType mMax
Definition: PointPartitioner.h:286
Definition: Exceptions.h:78
PointPartitioner< uint32_t, 3 > UInt32PointPartitioner
Definition: PointPartitioner.h:173
IndexPair< IndexT > IndexPairT
Definition: PointPartitioner.h:390
bool isLinear() const
Return true if the transformation map is exclusively linear/affine.
Definition: Transform.h:88
boost::int_t< 1+(3 *Log2Dim)>::least VoxelOffsetT
Definition: PointPartitioner.h:631
std::vector< typename GridType::Ptr > segment(GridType &grid, InterruptType *interrupter=NULL)
Segmentation scheme, splits disjoint fragments into separate grids.
Definition: LevelSetFracture.h:130
PointArray const *const mPoints
Definition: PointPartitioner.h:765
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
PointIndexT IndexType
Definition: PointPartitioner.h:100
std::pair< IndexT, IndexT > Range
Definition: PointPartitioner.h:576
IndexT *const mSize
Definition: PointPartitioner.h:623
CoordBBox computeLeafBounds(const PointArray &points, const math::Transform &m, unsigned log2dim)
Definition: PointPartitioner.h:798
PointArray::value_type PointType
Definition: PointPartitioner.h:230
const VoxelOffsetArray & voxelOffsets() const
Returns a list of LeafNode voxel offsets for the points.
Definition: PointPartitioner.h:157
ComputeBBoxOp(const ComputeBBoxOp &other, tbb::split)
Definition: PointPartitioner.h:240
IndexT const *const mBucketOffsets
Definition: PointPartitioner.h:524
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:307
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
IndexT const *const mPointIndices
Definition: PointPartitioner.h:547
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:563
size_t size() const
Number of point indices in the iterator range.
Definition: PointPartitioner.h:189
IndexT const *const mPages
Definition: PointPartitioner.h:764
void partition(const PointArray &points, const math::Transform &xform, const CoordBBox &bbox, boost::scoped_array< IndexT > &pointIndices, boost::scoped_array< IndexT > &pageOffsets, IndexT &pageCount, boost::scoped_array< VoxelOffsetT > &voxelOffsets, bool recordVoxelOffsets)
Definition: PointPartitioner.h:822
IndexT second
Definition: PointPartitioner.h:295
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:539
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:325
const math::Transform mXForm
Definition: PointPartitioner.h:379
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
IndexPair< IndexT > const *const mPairs
Definition: PointPartitioner.h:570
AtomicIndex *const mBucketMap
Definition: PointPartitioner.h:496
size_t size() const
Returns the number of buckets.
Definition: PointPartitioner.h:133
IndexIterator(IndexType *begin=NULL, IndexType *end=NULL)
Definition: PointPartitioner.h:182
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:708
IndexT first
Definition: PointPartitioner.h:295
IndexIterator indices(size_t n) const
Returns the point indices for bucket n.
Definition: PointPartitioner.h:1070
boost::scoped_array< VoxelOffsetT > VoxelOffsetArray
Definition: PointPartitioner.h:308
IndexT *const mBucketIndices
Definition: PointPartitioner.h:495
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:531
IndexT *const mIndices
Definition: PointPartitioner.h:694
const int mLog2Dim
Definition: PointPartitioner.h:768
void join(ComputeBBoxOp &other)
Definition: PointPartitioner.h:274
IndexT const *const mIndices
Definition: PointPartitioner.h:763
bool increment()
Definition: PointPartitioner.h:204
bool operator!=(const IndexIterator &other) const
Definition: PointPartitioner.h:208
IndexT *const mPointIndices
Definition: PointPartitioner.h:569
PointIndexT IndexType
Definition: PointPartitioner.h:180
ComputeBBoxOp(const PointArray &points)
Definition: PointPartitioner.h:233
boost::int_t< 1+(3 *Log2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:101