OpenVDB  3.1.0
PointPartitioner.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2015 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 //
44 
45 #ifndef OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
46 #define OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
47 
48 
49 #include <openvdb/Types.h>
50 #include <openvdb/math/Transform.h>
51 
52 #include <deque>
53 #include <map>
54 #include <set>
55 #include <utility> // std::pair
56 #include <vector>
57 
58 #include <boost/integer.hpp> // boost::int_t<N>::least
59 #include <boost/scoped_array.hpp>
60 #include <boost/shared_ptr.hpp>
61 #include <boost/math/special_functions/fpclassify.hpp> // boost::math::isfinite
62 
63 #include <tbb/blocked_range.h>
64 #include <tbb/parallel_for.h>
65 #include <tbb/task_scheduler_init.h>
66 
67 
68 namespace openvdb {
70 namespace OPENVDB_VERSION_NAME {
71 namespace tools {
72 
73 
75 
76 
100 template<typename PointIndexType = uint32_t, Index BucketLog2Dim = 3>
102 {
103 public:
104  enum { LOG2DIM = BucketLog2Dim };
105 
106  typedef boost::shared_ptr<PointPartitioner> Ptr;
107  typedef boost::shared_ptr<const PointPartitioner> ConstPtr;
108 
109  typedef PointIndexType IndexType;
110  typedef typename boost::int_t<1 + (3 * BucketLog2Dim)>::least VoxelOffsetType;
111  typedef boost::scoped_array<VoxelOffsetType> VoxelOffsetArray;
112 
113  class IndexIterator;
114 
116 
118 
125  template<typename PointArray>
126  void construct(const PointArray& points, const math::Transform& xform,
127  bool voxelOrder = false, bool recordVoxelOffsets = false);
128 
129 
136  template<typename PointArray>
137  static Ptr create(const PointArray& points, const math::Transform& xform,
138  bool voxelOrder = false, bool recordVoxelOffsets = false);
139 
140 
142  size_t size() const { return mPageCount; }
143 
145  bool empty() const { return mPageCount == 0; }
146 
148  void clear();
149 
151  void swap(PointPartitioner&);
152 
154  IndexIterator indices(size_t n) const;
155 
157  CoordBBox getBBox(size_t n) const {
158  return CoordBBox::createCube(mPageCoordinates[n], (1u << BucketLog2Dim));
159  }
160 
162  const Coord& origin(size_t n) const { return mPageCoordinates[n]; }
163 
166  const VoxelOffsetArray& voxelOffsets() const { return mVoxelOffsets; }
167 
168 private:
169  // Disallow copying
171  PointPartitioner& operator=(const PointPartitioner&);
172 
173  boost::scoped_array<IndexType> mPointIndices;
174  VoxelOffsetArray mVoxelOffsets;
175 
176  boost::scoped_array<IndexType> mPageOffsets;
177  boost::scoped_array<Coord> mPageCoordinates;
178  IndexType mPageCount;
179 }; // class PointPartitioner
180 
181 
183 
184 
185 template<typename PointIndexType, Index BucketLog2Dim>
186 class PointPartitioner<PointIndexType, BucketLog2Dim>::IndexIterator
187 {
188 public:
189  typedef PointIndexType IndexType;
190 
191  IndexIterator(IndexType* begin = NULL, IndexType* end = NULL)
192  : mBegin(begin), mEnd(end), mItem(begin) {}
193 
195  void reset() { mItem = mBegin; }
196 
198  size_t size() const { return mEnd - mBegin; }
199 
201  IndexType& operator*() { assert(mItem != NULL); return *mItem; }
202  const IndexType& operator*() const { assert(mItem != NULL); return *mItem; }
203 
205  operator bool() const { return mItem < mEnd; }
206  bool test() const { return mItem < mEnd; }
207 
209  IndexIterator& operator++() { assert(this->test()); ++mItem; return *this; }
210 
212  bool next() { this->operator++(); return this->test(); }
213  bool increment() { this->next(); return this->test(); }
214 
216  bool operator==(const IndexIterator& other) const { return mItem == other.mItem; }
217  bool operator!=(const IndexIterator& other) const { return !this->operator==(other); }
218 
219 private:
220  IndexType * const mBegin, * const mEnd;
221  IndexType * mItem;
222 }; // class PointPartitioner::IndexIterator
223 
224 
227 
228 // Implementation details
229 
230 
231 namespace point_partitioner_internal {
232 
233 
234 template<typename PointIndexType>
236 {
237  ComputePointOrderOp(PointIndexType* pointOrder,
238  const PointIndexType* bucketCounters, const PointIndexType* bucketOffsets)
239  : mPointOrder(pointOrder)
240  , mBucketCounters(bucketCounters)
241  , mBucketOffsets(bucketOffsets)
242  {
243  }
244 
245  void operator()(const tbb::blocked_range<size_t>& range) const {
246  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
247  mPointOrder[n] += mBucketCounters[mBucketOffsets[n]];
248  }
249  }
250 
251  PointIndexType * const mPointOrder;
252  PointIndexType const * const mBucketCounters;
253  PointIndexType const * const mBucketOffsets;
254 }; // struct ComputePointOrderOp
255 
256 
257 template<typename PointIndexType>
259 {
260  CreateOrderedPointIndexArrayOp(PointIndexType* orderedIndexArray,
261  const PointIndexType* pointOrder, const PointIndexType* indices)
262  : mOrderedIndexArray(orderedIndexArray)
263  , mPointOrder(pointOrder)
264  , mIndices(indices)
265  {
266  }
267 
268  void operator()(const tbb::blocked_range<size_t>& range) const {
269  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
270  mOrderedIndexArray[mPointOrder[n]] = mIndices[n];
271  }
272  }
273 
274  PointIndexType * const mOrderedIndexArray;
275  PointIndexType const * const mPointOrder;
276  PointIndexType const * const mIndices;
277 }; // struct CreateOrderedPointIndexArrayOp
278 
279 
280 template<typename PointIndexType, Index BucketLog2Dim>
282 {
283  typedef typename boost::int_t<1 + (3 * BucketLog2Dim)>::least VoxelOffsetType;
284  typedef boost::scoped_array<VoxelOffsetType> VoxelOffsetArray;
285  typedef boost::scoped_array<PointIndexType> IndexArray;
286 
287  VoxelOrderOp(IndexArray& indices, const IndexArray& pages,const VoxelOffsetArray& offsets)
288  : mIndices(indices.get())
289  , mPages(pages.get())
290  , mVoxelOffsets(offsets.get())
291  {
292  }
293 
294  void operator()(const tbb::blocked_range<size_t>& range) const {
295 
296  PointIndexType pointCount = 0;
297  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
298  pointCount = std::max(pointCount, (mPages[n + 1] - mPages[n]));
299  }
300 
301  const PointIndexType voxelCount = 1 << (3 * BucketLog2Dim);
302 
303  // allocate histogram buffers
304  boost::scoped_array<VoxelOffsetType> offsets(new VoxelOffsetType[pointCount]);
305  boost::scoped_array<PointIndexType> sortedIndices(new PointIndexType[pointCount]);
306  boost::scoped_array<PointIndexType> histogram(new PointIndexType[voxelCount]);
307 
308  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
309 
310  PointIndexType * const indices = mIndices + mPages[n];
311  pointCount = mPages[n + 1] - mPages[n];
312 
313  // local copy of voxel offsets.
314  for (PointIndexType i = 0; i < pointCount; ++i) {
315  offsets[i] = mVoxelOffsets[ indices[i] ];
316  }
317 
318  // reset histogram
319  memset(&histogram[0], 0, voxelCount * sizeof(PointIndexType));
320 
321  // compute histogram
322  for (PointIndexType i = 0; i < pointCount; ++i) {
323  ++histogram[ offsets[i] ];
324  }
325 
326  PointIndexType count = 0, startOffset;
327  for (int i = 0; i < int(voxelCount); ++i) {
328  if (histogram[i] > 0) {
329  startOffset = count;
330  count += histogram[i];
331  histogram[i] = startOffset;
332  }
333  }
334 
335  // sort indices based on voxel offset
336  for (PointIndexType i = 0; i < pointCount; ++i) {
337  sortedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
338  }
339 
340  memcpy(&indices[0], &sortedIndices[0], sizeof(PointIndexType) * pointCount);
341  }
342  }
343 
344  PointIndexType * const mIndices;
345  PointIndexType const * const mPages;
346  VoxelOffsetType const * const mVoxelOffsets;
347 }; // struct VoxelOrderOp
348 
349 
350 template<typename PointArray, typename PointIndexType>
352 {
353  typedef boost::scoped_array<PointIndexType> IndexArray;
354  typedef boost::scoped_array<Coord> CoordArray;
355 
356  LeafNodeOriginOp(CoordArray& coordinates,
357  const IndexArray& indices, const IndexArray& pages,
358  const PointArray& points, const math::Transform& m, int log2dim)
359  : mCoordinates(coordinates.get())
360  , mIndices(indices.get())
361  , mPages(pages.get())
362  , mPoints(&points)
363  , mXForm(m)
364  , mLog2Dim(log2dim)
365  {
366  }
367 
368  void operator()(const tbb::blocked_range<size_t>& range) const {
369 
370  typedef typename PointArray::value_type PointType;
371 
372  const int mask = ~((1 << mLog2Dim) - 1);
373  Coord ijk;
374  PointType pos;
375 
376  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
377 
378  mPoints->getPos(mIndices[mPages[n]], pos);
379 
380  if (boost::math::isfinite(pos[0]) &&
381  boost::math::isfinite(pos[1]) &&
382  boost::math::isfinite(pos[2])) {
383 
384  ijk = mXForm.worldToIndexCellCentered(pos);
385 
386  ijk[0] &= mask;
387  ijk[1] &= mask;
388  ijk[2] &= mask;
389 
390  mCoordinates[n] = ijk;
391  }
392  }
393  }
394 
395  Coord * const mCoordinates;
396  PointIndexType const * const mIndices;
397  PointIndexType const * const mPages;
398  PointArray const * const mPoints;
400  int const mLog2Dim;
401 }; // struct LeafNodeOriginOp
402 
403 
405 
406 
407 template<typename T>
408 struct Array
409 {
410  typedef boost::shared_ptr<Array> Ptr;
411 
412  Array(size_t size) : mSize(size), mData(new T[size]) { }
413 
414  size_t size() const { return mSize; }
415 
416  T* data() { return mData.get(); }
417  const T* data() const { return mData.get(); }
418 
419  void clear() { mSize = 0; mData.reset(); }
420 
421 private:
422  size_t mSize;
423  boost::scoped_array<T> mData;
424 }; // struct Array
425 
426 
427 template<typename PointIndexType>
429 {
431  typedef typename Segment::Ptr SegmentPtr;
432 
433  MoveSegmentDataOp(std::vector<PointIndexType*>& indexLists, SegmentPtr* segments)
434  : mIndexLists(&indexLists[0]), mSegments(segments)
435  {
436  }
437 
438  void operator()(const tbb::blocked_range<size_t>& range) const {
439  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
440  PointIndexType* indices = mIndexLists[n];
441  SegmentPtr& segment = mSegments[n];
442 
443  tbb::parallel_for(tbb::blocked_range<size_t>(0, segment->size()),
444  CopyData(indices, segment->data()));
445 
446  segment.reset(); // clear data
447  }
448  }
449 
450 private:
451 
452  struct CopyData
453  {
454  CopyData(PointIndexType* lhs, const PointIndexType* rhs) : mLhs(lhs), mRhs(rhs) { }
455 
456  void operator()(const tbb::blocked_range<size_t>& range) const {
457  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
458  mLhs[n] = mRhs[n];
459  }
460  }
461 
462  PointIndexType * const mLhs;
463  PointIndexType const * const mRhs;
464  };
465 
466  PointIndexType * const * const mIndexLists;
467  SegmentPtr * const mSegments;
468 }; // struct MoveSegmentDataOp
469 
470 
471 template<typename PointIndexType>
473 {
475  typedef typename Segment::Ptr SegmentPtr;
476 
477  typedef std::pair<PointIndexType, PointIndexType> IndexPair;
478  typedef std::deque<IndexPair> IndexPairList;
479  typedef boost::shared_ptr<IndexPairList> IndexPairListPtr;
480  typedef std::map<Coord, IndexPairListPtr> IndexPairListMap;
481  typedef boost::shared_ptr<IndexPairListMap> IndexPairListMapPtr;
482 
483  MergeBinsOp(IndexPairListMapPtr* bins,
484  SegmentPtr* indexSegments,
485  SegmentPtr* offsetSegments,
486  Coord* coords,
487  size_t numSegments)
488  : mBins(bins)
489  , mIndexSegments(indexSegments)
490  , mOffsetSegments(offsetSegments)
491  , mCoords(coords)
492  , mNumSegments(numSegments)
493  {
494  }
495 
496  void operator()(const tbb::blocked_range<size_t>& range) const {
497 
498  std::vector<IndexPairListPtr*> data;
499  std::vector<PointIndexType> arrayOffsets;
500 
501  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
502 
503  const Coord& ijk = mCoords[n];
504  size_t numIndices = 0;
505 
506  data.clear();
507 
508  for (size_t i = 0, I = mNumSegments; i < I; ++i) {
509 
510  IndexPairListMap& idxMap = *mBins[i];
511  typename IndexPairListMap::iterator iter = idxMap.find(ijk);
512 
513  if (iter != idxMap.end() && iter->second) {
514  IndexPairListPtr& idxListPtr = iter->second;
515 
516  data.push_back(&idxListPtr);
517  numIndices += idxListPtr->size();
518  }
519  }
520 
521  if (data.empty() || numIndices == 0) continue;
522 
523  SegmentPtr& indexSegment = mIndexSegments[n];
524  SegmentPtr& offsetSegment = mOffsetSegments[n];
525 
526  indexSegment.reset(new Segment(numIndices));
527  offsetSegment.reset(new Segment(numIndices));
528 
529  arrayOffsets.clear();
530  arrayOffsets.reserve(data.size());
531 
532  for (size_t i = 0, count = 0, I = data.size(); i < I; ++i) {
533  arrayOffsets.push_back(PointIndexType(count));
534  count += (*data[i])->size();
535  }
536 
537  tbb::parallel_for(tbb::blocked_range<size_t>(0, data.size()),
538  CopyData(&data[0], &arrayOffsets[0], indexSegment->data(), offsetSegment->data()));
539  }
540  }
541 
542 private:
543 
544  struct CopyData
545  {
546  CopyData(IndexPairListPtr** indexLists,
547  const PointIndexType* arrayOffsets,
548  PointIndexType* indices,
549  PointIndexType* offsets)
550  : mIndexLists(indexLists)
551  , mArrayOffsets(arrayOffsets)
552  , mIndices(indices)
553  , mOffsets(offsets)
554  {
555  }
556 
557  void operator()(const tbb::blocked_range<size_t>& range) const {
558 
559  typedef typename IndexPairList::const_iterator CIter;
560 
561  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
562 
563  const PointIndexType arrayOffset = mArrayOffsets[n];
564  PointIndexType* indexPtr = &mIndices[arrayOffset];
565  PointIndexType* offsetPtr = &mOffsets[arrayOffset];
566 
567  IndexPairListPtr& list = *mIndexLists[n];
568 
569  for (CIter it = list->begin(), end = list->end(); it != end; ++it) {
570  const IndexPair& data = *it;
571  *indexPtr++ = data.first;
572  *offsetPtr++ = data.second;
573  }
574 
575  list.reset(); // clear data
576  }
577  }
578 
579  IndexPairListPtr * const * const mIndexLists;
580  PointIndexType const * const mArrayOffsets;
581  PointIndexType * const mIndices;
582  PointIndexType * const mOffsets;
583  }; // struct CopyData
584 
585  IndexPairListMapPtr * const mBins;
586  SegmentPtr * const mIndexSegments;
587  SegmentPtr * const mOffsetSegments;
588  Coord const * const mCoords;
589  size_t const mNumSegments;
590 }; // struct MergeBinsOp
591 
592 
593 template<typename PointArray, typename PointIndexType, typename VoxelOffsetType>
595 {
596  typedef typename PointArray::value_type PointType;
597  typedef typename PointType::value_type PointElementType;
598 
599  typedef std::pair<PointIndexType, PointIndexType> IndexPair;
600  typedef std::deque<IndexPair> IndexPairList;
601  typedef boost::shared_ptr<IndexPairList> IndexPairListPtr;
602  typedef std::map<Coord, IndexPairListPtr> IndexPairListMap;
603  typedef boost::shared_ptr<IndexPairListMap> IndexPairListMapPtr;
604 
605  BinPointIndicesOp(IndexPairListMapPtr* data,
606  const PointArray& points,
607  VoxelOffsetType* voxelOffsets,
608  const math::Transform& m,
609  Index binLog2Dim,
610  Index bucketLog2Dim,
611  size_t numSegments)
612  : mData(data)
613  , mPoints(&points)
614  , mVoxelOffsets(voxelOffsets)
615  , mXForm(m)
616  , mBinLog2Dim(binLog2Dim)
617  , mBucketLog2Dim(bucketLog2Dim)
618  , mNumSegments(numSegments)
619  {
620  }
621 
622  void operator()(const tbb::blocked_range<size_t>& range) const {
623 
624  const Index log2dim = mBucketLog2Dim;
625  const Index log2dim2 = 2 * log2dim;
626  const Index bucketMask = (1u << log2dim) - 1u;
627 
628  const Index binLog2dim = mBinLog2Dim;
629  const Index binLog2dim2 = 2 * binLog2dim;
630 
631  const Index binMask = (1u << (log2dim + binLog2dim)) - 1u;
632  const Index invBinMask = ~binMask;
633 
634  IndexPairList * idxList = NULL;
635  Coord ijk(0, 0, 0), loc(0, 0, 0), binCoord(0, 0, 0), lastBinCoord(1, 2, 3);
636  PointType pos;
637 
638  PointIndexType bucketOffset = 0;
639  VoxelOffsetType voxelOffset = 0;
640 
641  const size_t numPoints = mPoints->size();
642  const size_t segmentSize = numPoints / mNumSegments;
643 
644  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
645 
646  IndexPairListMapPtr& dataPtr = mData[n];
647  if (!dataPtr) dataPtr.reset(new IndexPairListMap());
648  IndexPairListMap& idxMap = *dataPtr;
649 
650  const bool isLastSegment = (n + 1) >= mNumSegments;
651 
652  const size_t start = n * segmentSize;
653  const size_t end = isLastSegment ? numPoints : (start + segmentSize);
654 
655  for (size_t i = start; i != end; ++i) {
656 
657  mPoints->getPos(i, pos);
658 
659  if (boost::math::isfinite(pos[0]) &&
660  boost::math::isfinite(pos[1]) &&
661  boost::math::isfinite(pos[2])) {
662 
663  ijk = mXForm.worldToIndexCellCentered(pos);
664 
665  if (mVoxelOffsets) {
666  loc[0] = ijk[0] & bucketMask;
667  loc[1] = ijk[1] & bucketMask;
668  loc[2] = ijk[2] & bucketMask;
669  voxelOffset = VoxelOffsetType((loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
670  }
671 
672  binCoord[0] = ijk[0] & invBinMask;
673  binCoord[1] = ijk[1] & invBinMask;
674  binCoord[2] = ijk[2] & invBinMask;
675 
676  ijk[0] &= binMask;
677  ijk[1] &= binMask;
678  ijk[2] &= binMask;
679 
680  ijk[0] >>= log2dim;
681  ijk[1] >>= log2dim;
682  ijk[2] >>= log2dim;
683 
684  bucketOffset = PointIndexType((ijk[0] << binLog2dim2) + (ijk[1] << binLog2dim) + ijk[2]);
685 
686  if (lastBinCoord != binCoord) {
687  lastBinCoord = binCoord;
688  IndexPairListPtr& idxListPtr = idxMap[lastBinCoord];
689  if (!idxListPtr) idxListPtr.reset(new IndexPairList());
690  idxList = idxListPtr.get();
691  }
692 
693  idxList->push_back(IndexPair(PointIndexType(i), bucketOffset));
694  if (mVoxelOffsets) mVoxelOffsets[i] = voxelOffset;
695  }
696  }
697  }
698  }
699 
700  IndexPairListMapPtr * const mData;
701  PointArray const * const mPoints;
702  VoxelOffsetType * const mVoxelOffsets;
706  size_t const mNumSegments;
707 }; // struct BinPointIndicesOp
708 
709 
710 template<typename PointIndexType>
712 {
713  typedef boost::scoped_array<PointIndexType> IndexArray;
715 
716  OrderSegmentsOp(SegmentPtr* indexSegments, SegmentPtr* offestSegments,
717  IndexArray* pageOffsetArrays, Index binVolume)
718  : mIndexSegments(indexSegments)
719  , mOffsetSegments(offestSegments)
720  , mPageOffsetArrays(pageOffsetArrays)
721  , mBinVolume(binVolume)
722  {
723  }
724 
725  void operator()(const tbb::blocked_range<size_t>& range) const {
726 
727  const size_t bucketCountersSize = size_t(mBinVolume);
728  IndexArray bucketCounters(new PointIndexType[bucketCountersSize]);
729 
730  size_t maxSegmentSize = 0;
731  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
732  maxSegmentSize = std::max(maxSegmentSize, mIndexSegments[n]->size());
733  }
734 
735  IndexArray bucketIndices(new PointIndexType[maxSegmentSize]);
736 
737 
738  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
739 
740  memset(bucketCounters.get(), 0, sizeof(PointIndexType) * bucketCountersSize);
741 
742  const size_t segmentSize = mOffsetSegments[n]->size();
743  PointIndexType* offsets = mOffsetSegments[n]->data();
744 
745  // Count the number of points per bucket and assign a local bucket index
746  // to each point.
747  for (size_t i = 0; i < segmentSize; ++i) {
748  bucketIndices[i] = bucketCounters[offsets[i]]++;
749  }
750 
751  PointIndexType nonemptyBucketCount = 0;
752  for (size_t i = 0; i < bucketCountersSize; ++i) {
753  nonemptyBucketCount += static_cast<PointIndexType>(bucketCounters[i] != 0);
754  }
755 
756 
757  IndexArray& pageOffsets = mPageOffsetArrays[n];
758  pageOffsets.reset(new PointIndexType[nonemptyBucketCount + 1]);
759  pageOffsets[0] = nonemptyBucketCount + 1; // stores array size in first element
760 
761  // Compute bucket counter prefix sum
762  PointIndexType count = 0, idx = 1;
763  for (size_t i = 0; i < bucketCountersSize; ++i) {
764  if (bucketCounters[i] != 0) {
765  pageOffsets[idx] = bucketCounters[i];
766  bucketCounters[i] = count;
767  count += pageOffsets[idx];
768  ++idx;
769  }
770  }
771 
772  PointIndexType* indices = mIndexSegments[n]->data();
773  const tbb::blocked_range<size_t> segmentRange(0, segmentSize);
774 
775  // Compute final point order by incrementing the local bucket point index
776  // with the prefix sum offset.
777  tbb::parallel_for(segmentRange, ComputePointOrderOp<PointIndexType>(
778  bucketIndices.get(), bucketCounters.get(), offsets));
779 
780  tbb::parallel_for(segmentRange, CreateOrderedPointIndexArrayOp<PointIndexType>(
781  offsets, bucketIndices.get(), indices));
782 
783  mIndexSegments[n]->clear(); // clear data
784  }
785  }
786 
787  SegmentPtr * const mIndexSegments;
788  SegmentPtr * const mOffsetSegments;
789  IndexArray * const mPageOffsetArrays;
791 }; // struct OrderSegmentsOp
792 
793 
795 
796 
798 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
799 inline void binAndSegment(
800  const PointArray& points,
801  const math::Transform& xform,
802  boost::scoped_array<typename Array<PointIndexType>::Ptr>& indexSegments,
803  boost::scoped_array<typename Array<PointIndexType>::Ptr>& offsetSegments,
804  size_t& segmentCount,
805  const Index binLog2Dim,
806  const Index bucketLog2Dim,
807  VoxelOffsetType* voxelOffsets = NULL)
808 {
809  typedef std::pair<PointIndexType, PointIndexType> IndexPair;
810  typedef std::deque<IndexPair> IndexPairList;
811  typedef boost::shared_ptr<IndexPairList> IndexPairListPtr;
812  typedef std::map<Coord, IndexPairListPtr> IndexPairListMap;
813  typedef boost::shared_ptr<IndexPairListMap> IndexPairListMapPtr;
814 
815  size_t numTasks = 1, numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
816  if (points.size() > (numThreads * 2)) numTasks = numThreads * 2;
817  else if (points.size() > numThreads) numTasks = numThreads;
818 
819  boost::scoped_array<IndexPairListMapPtr> bins(new IndexPairListMapPtr[numTasks]);
820 
822 
823  tbb::parallel_for(tbb::blocked_range<size_t>(0, numTasks),
824  BinOp(bins.get(), points, voxelOffsets, xform, binLog2Dim, bucketLog2Dim, numTasks));
825 
826  std::set<Coord> uniqueCoords;
827 
828  for (size_t i = 0; i < numTasks; ++i) {
829  IndexPairListMap& idxMap = *bins[i];
830  for (typename IndexPairListMap::iterator it = idxMap.begin(); it != idxMap.end(); ++it) {
831  uniqueCoords.insert(it->first);
832  }
833  }
834 
835  std::vector<Coord> coords(uniqueCoords.begin(), uniqueCoords.end());
836  uniqueCoords.clear();
837 
838  segmentCount = coords.size();
839 
840  typedef typename Array<PointIndexType>::Ptr SegmentPtr;
841 
842  indexSegments.reset(new SegmentPtr[segmentCount]);
843  offsetSegments.reset(new SegmentPtr[segmentCount]);
844 
845  typedef MergeBinsOp<PointIndexType> MergeOp;
846 
847  tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
848  MergeOp(bins.get(), indexSegments.get(), offsetSegments.get(), &coords[0], numTasks));
849 }
850 
851 
852 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
853 inline void partition(
854  const PointArray& points,
855  const math::Transform& xform,
856  const Index bucketLog2Dim,
857  boost::scoped_array<PointIndexType>& pointIndices,
858  boost::scoped_array<PointIndexType>& pageOffsets,
859  PointIndexType& pageCount,
860  boost::scoped_array<VoxelOffsetType>& voxelOffsets,
861  bool recordVoxelOffsets)
862 {
863  if (recordVoxelOffsets) voxelOffsets.reset(new VoxelOffsetType[points.size()]);
864  else voxelOffsets.reset();
865 
866  const Index binLog2Dim = 5u;
867  // note: Bins span a (2^(binLog2Dim + bucketLog2Dim))^3 voxel region,
868  // i.e. bucketLog2Dim = 3 and binLog2Dim = 5 corresponds to a
869  // (2^8)^3 = 256^3 voxel region.
870 
871 
872  size_t numSegments = 0;
873 
874  boost::scoped_array<typename Array<PointIndexType>::Ptr> indexSegments;
875  boost::scoped_array<typename Array<PointIndexType>::Ptr> offestSegments;
876 
877  binAndSegment<PointIndexType, VoxelOffsetType, PointArray>(points, xform,
878  indexSegments, offestSegments, numSegments, binLog2Dim, bucketLog2Dim, voxelOffsets.get());
879 
880  const tbb::blocked_range<size_t> segmentRange(0, numSegments);
881 
882  typedef boost::scoped_array<PointIndexType> IndexArray;
883  boost::scoped_array<IndexArray> pageOffsetArrays(new IndexArray[numSegments]);
884 
885  const Index binVolume = 1u << (3u * binLog2Dim);
886 
887  tbb::parallel_for(segmentRange, OrderSegmentsOp<PointIndexType>
888  (indexSegments.get(), offestSegments.get(), pageOffsetArrays.get(), binVolume));
889 
890  indexSegments.reset();
891 
892  pageCount = 0;
893  for (size_t n = 0; n < numSegments; ++n) {
894  pageCount += pageOffsetArrays[n][0] - 1;
895  }
896 
897  pageOffsets.reset(new PointIndexType[pageCount + 1]);
898 
899  PointIndexType count = 0;
900  for (size_t n = 0, idx = 0; n < numSegments; ++n) {
901 
902  PointIndexType* offsets = pageOffsetArrays[n].get();
903  size_t size = size_t(offsets[0]);
904 
905  for (size_t i = 1; i < size; ++i) {
906  pageOffsets[idx++] = count;
907  count += offsets[i];
908  }
909  }
910 
911  pageOffsets[pageCount] = count;
912 
913  pointIndices.reset(new PointIndexType[points.size()]);
914 
915  std::vector<PointIndexType*> indexArray;
916  indexArray.reserve(numSegments);
917 
918  PointIndexType* index = pointIndices.get();
919  for (size_t n = 0; n < numSegments; ++n) {
920  indexArray.push_back(index);
921  index += offestSegments[n]->size();
922  }
923 
924  tbb::parallel_for(segmentRange, MoveSegmentDataOp<PointIndexType>(indexArray, offestSegments.get()));
925 }
926 
927 
928 } // namespace point_partitioner_internal
929 
930 
932 
933 
934 template<typename PointIndexType, Index BucketLog2Dim>
936  : mPointIndices(NULL)
937  , mVoxelOffsets(NULL)
938  , mPageOffsets(NULL)
939  , mPageCoordinates(NULL)
940  , mPageCount(0)
941 {
942 }
943 
944 
945 template<typename PointIndexType, Index BucketLog2Dim>
946 inline void
948 {
949  mPageCount = 0;
950  mPointIndices.reset();
951  mVoxelOffsets.reset();
952  mPageOffsets.reset();
953  mPageCoordinates.reset();
954 }
955 
956 
957 template<typename PointIndexType, Index BucketLog2Dim>
958 inline void
960 {
961  const IndexType tmpLhsPageCount = mPageCount;
962  mPageCount = rhs.mPageCount;
963  rhs.mPageCount = tmpLhsPageCount;
964 
965  mPointIndices.swap(rhs.mPointIndices);
966  mVoxelOffsets.swap(rhs.mVoxelOffsets);
967  mPageOffsets.swap(rhs.mPageOffsets);
968  mPageCoordinates.swap(rhs.mPageCoordinates);
969 }
970 
971 
972 template<typename PointIndexType, Index BucketLog2Dim>
975 {
976  assert(bool(mPointIndices) && bool(mPageCount));
977  return IndexIterator(
978  mPointIndices.get() + mPageOffsets[n],
979  mPointIndices.get() + mPageOffsets[n + 1]);
980 }
981 
982 
983 template<typename PointIndexType, Index BucketLog2Dim>
984 template<typename PointArray>
985 inline void
987  const math::Transform& xform, bool voxelOrder, bool recordVoxelOffsets)
988 {
989  point_partitioner_internal::partition(points, xform, BucketLog2Dim,
990  mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets, (voxelOrder || recordVoxelOffsets));
991 
992  const tbb::blocked_range<size_t> pageRange(0, mPageCount);
993  mPageCoordinates.reset(new Coord[mPageCount]);
994 
995  tbb::parallel_for(pageRange,
997  (mPageCoordinates, mPointIndices, mPageOffsets, points, xform, BucketLog2Dim));
998 
999  if (mVoxelOffsets && voxelOrder) {
1000  tbb::parallel_for(pageRange, point_partitioner_internal::VoxelOrderOp<
1001  IndexType, BucketLog2Dim>(mPointIndices, mPageOffsets, mVoxelOffsets));
1002  }
1003 
1004  if (mVoxelOffsets && !recordVoxelOffsets) {
1005  mVoxelOffsets.reset();
1006  }
1007 }
1008 
1009 
1010 template<typename PointIndexType, Index BucketLog2Dim>
1011 template<typename PointArray>
1014  bool voxelOrder, bool recordVoxelOffsets)
1015 {
1016  Ptr ret(new PointPartitioner());
1017  ret->construct(points, xform, voxelOrder, recordVoxelOffsets);
1018  return ret;
1019 }
1020 
1021 
1023 
1024 
1025 } // namespace tools
1026 } // namespace OPENVDB_VERSION_NAME
1027 } // namespace openvdb
1028 
1029 
1030 #endif // OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
1031 
1032 // Copyright (c) 2012-2015 DreamWorks Animation LLC
1033 // All rights reserved. This software is distributed under the
1034 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
void swap(PointPartitioner &)
Exchanges the content of the container by another.
Definition: PointPartitioner.h:959
bool operator==(const IndexIterator &other) const
Equality operators.
Definition: PointPartitioner.h:216
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:268
Index32 Index
Definition: Types.h:58
OrderSegmentsOp(SegmentPtr *indexSegments, SegmentPtr *offestSegments, IndexArray *pageOffsetArrays, Index binVolume)
Definition: PointPartitioner.h:716
IndexPairListMapPtr *const mData
Definition: PointPartitioner.h:700
PointIndexType *const mIndices
Definition: PointPartitioner.h:344
boost::int_t< 1+(3 *BucketLog2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:283
Index const mBucketLog2Dim
Definition: PointPartitioner.h:705
PointType::value_type PointElementType
Definition: PointPartitioner.h:597
IndexArray *const mPageOffsetArrays
Definition: PointPartitioner.h:789
Array< PointIndexType > Segment
Definition: PointPartitioner.h:474
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:438
size_t size() const
Returns the number of buckets.
Definition: PointPartitioner.h:142
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
PointArray::value_type PointType
Definition: PointPartitioner.h:596
boost::int_t< 1+(3 *BucketLog2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:110
void clear()
Removes all data and frees up memory.
Definition: PointPartitioner.h:947
Index const mBinLog2Dim
Definition: PointPartitioner.h:704
IndexIterator(IndexType *begin=NULL, IndexType *end=NULL)
Definition: PointPartitioner.h:191
bool empty() const
true if the container size is 0, false otherwise.
Definition: PointPartitioner.h:145
void clear()
Definition: PointPartitioner.h:419
Segment::Ptr SegmentPtr
Definition: PointPartitioner.h:431
Array(size_t size)
Definition: PointPartitioner.h:412
std::pair< PointIndexType, PointIndexType > IndexPair
Definition: PointPartitioner.h:599
const T * data() const
Definition: PointPartitioner.h:417
CreateOrderedPointIndexArrayOp(PointIndexType *orderedIndexArray, const PointIndexType *pointOrder, const PointIndexType *indices)
Definition: PointPartitioner.h:260
Array< PointIndexType >::Ptr SegmentPtr
Definition: PointPartitioner.h:714
BinPointIndicesOp(IndexPairListMapPtr *data, const PointArray &points, VoxelOffsetType *voxelOffsets, const math::Transform &m, Index binLog2Dim, Index bucketLog2Dim, size_t numSegments)
Definition: PointPartitioner.h:605
const IndexType & operator*() const
Definition: PointPartitioner.h:202
T * data()
Definition: PointPartitioner.h:416
CoordBBox getBBox(size_t n) const
Returns the coordinate-aligned bounding box for bucket n.
Definition: PointPartitioner.h:157
bool increment()
Definition: PointPartitioner.h:213
void construct(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false)
Partitions point indices into BucketLog2Dim aligned buckets.
Definition: PointPartitioner.h:986
Segment::Ptr SegmentPtr
Definition: PointPartitioner.h:475
PointIndexType const *const mPages
Definition: PointPartitioner.h:345
VoxelOffsetType const *const mVoxelOffsets
Definition: PointPartitioner.h:346
Definition: PointPartitioner.h:101
boost::shared_ptr< PointPartitioner > Ptr
Definition: PointPartitioner.h:106
boost::shared_ptr< IndexPairListMap > IndexPairListMapPtr
Definition: PointPartitioner.h:481
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:496
PointIndexType IndexType
Definition: PointPartitioner.h:109
Coord *const mCoordinates
Definition: PointPartitioner.h:395
Index const mBinVolume
Definition: PointPartitioner.h:790
std::map< Coord, IndexPairListPtr > IndexPairListMap
Definition: PointPartitioner.h:602
boost::scoped_array< Coord > CoordArray
Definition: PointPartitioner.h:354
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:285
IndexIterator indices(size_t n) const
Returns the point indices for bucket n.
Definition: PointPartitioner.h:974
boost::shared_ptr< IndexPairListMap > IndexPairListMapPtr
Definition: PointPartitioner.h:603
VoxelOffsetType *const mVoxelOffsets
Definition: PointPartitioner.h:702
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:368
VoxelOrderOp(IndexArray &indices, const IndexArray &pages, const VoxelOffsetArray &offsets)
Definition: PointPartitioner.h:287
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:245
ComputePointOrderOp(PointIndexType *pointOrder, const PointIndexType *bucketCounters, const PointIndexType *bucketOffsets)
Definition: PointPartitioner.h:237
PointPartitioner< uint32_t, 3 > UInt32PointPartitioner
Definition: PointPartitioner.h:182
void partition(const PointArray &points, const math::Transform &xform, const Index bucketLog2Dim, boost::scoped_array< PointIndexType > &pointIndices, boost::scoped_array< PointIndexType > &pageOffsets, PointIndexType &pageCount, boost::scoped_array< VoxelOffsetType > &voxelOffsets, bool recordVoxelOffsets)
Definition: PointPartitioner.h:853
#define OPENVDB_VERSION_NAME
Definition: version.h:43
size_t size() const
Number of point indices in the iterator range.
Definition: PointPartitioner.h:198
PointIndexType const *const mIndices
Definition: PointPartitioner.h:276
std::pair< PointIndexType, PointIndexType > IndexPair
Definition: PointPartitioner.h:477
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:353
bool next()
Advance to the next item.
Definition: PointPartitioner.h:212
boost::shared_ptr< IndexPairList > IndexPairListPtr
Definition: PointPartitioner.h:479
LeafNodeOriginOp(CoordArray &coordinates, const IndexArray &indices, const IndexArray &pages, const PointArray &points, const math::Transform &m, int log2dim)
Definition: PointPartitioner.h:356
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:622
boost::shared_ptr< Array > Ptr
Definition: PointPartitioner.h:410
math::Transform const mXForm
Definition: PointPartitioner.h:703
void binAndSegment(const PointArray &points, const math::Transform &xform, boost::scoped_array< typename Array< PointIndexType >::Ptr > &indexSegments, boost::scoped_array< typename Array< PointIndexType >::Ptr > &offsetSegments, size_t &segmentCount, const Index binLog2Dim, const Index bucketLog2Dim, VoxelOffsetType *voxelOffsets=NULL)
Segment points using one level of least significant digit radix bins.
Definition: PointPartitioner.h:799
PointIndexType *const mOrderedIndexArray
Definition: PointPartitioner.h:274
Definition: Exceptions.h:39
std::deque< IndexPair > IndexPairList
Definition: PointPartitioner.h:600
PointArray const *const mPoints
Definition: PointPartitioner.h:701
bool operator!=(const IndexIterator &other) const
Definition: PointPartitioner.h:217
PointIndexType const *const mPages
Definition: PointPartitioner.h:397
SegmentPtr *const mOffsetSegments
Definition: PointPartitioner.h:788
math::Transform const mXForm
Definition: PointPartitioner.h:399
int const mLog2Dim
Definition: PointPartitioner.h:400
static Ptr create(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false)
Partitions point indices into BucketLog2Dim aligned buckets.
Definition: PointPartitioner.h:1013
MoveSegmentDataOp(std::vector< PointIndexType * > &indexLists, SegmentPtr *segments)
Definition: PointPartitioner.h:433
boost::scoped_array< VoxelOffsetType > VoxelOffsetArray
Definition: PointPartitioner.h:111
MergeBinsOp(IndexPairListMapPtr *bins, SegmentPtr *indexSegments, SegmentPtr *offsetSegments, Coord *coords, size_t numSegments)
Definition: PointPartitioner.h:483
PointArray const *const mPoints
Definition: PointPartitioner.h:398
size_t size() const
Definition: PointPartitioner.h:414
SegmentPtr *const mIndexSegments
Definition: PointPartitioner.h:787
std::map< Coord, IndexPairListPtr > IndexPairListMap
Definition: PointPartitioner.h:480
Calculate an axis-aligned bounding box in index space from a bounding sphere in world space...
Definition: Transform.h:66
size_t const mNumSegments
Definition: PointPartitioner.h:706
const boost::disable_if_c< VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:109
bool test() const
Definition: PointPartitioner.h:206
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
PointIndexType IndexType
Definition: PointPartitioner.h:189
PointIndexType const *const mIndices
Definition: PointPartitioner.h:396
PointIndexType const *const mBucketCounters
Definition: PointPartitioner.h:252
boost::shared_ptr< const PointPartitioner > ConstPtr
Definition: PointPartitioner.h:107
PointIndexType const *const mBucketOffsets
Definition: PointPartitioner.h:253
Array< PointIndexType > Segment
Definition: PointPartitioner.h:430
PointIndexType *const mPointOrder
Definition: PointPartitioner.h:251
IndexType & operator*()
Returns the item to which this iterator is currently pointing.
Definition: PointPartitioner.h:201
const Coord & origin(size_t n) const
Returns the origin coordinate for bucket n.
Definition: PointPartitioner.h:162
std::vector< typename GridType::Ptr > segment(GridType &grid, InterruptType *interrupter=NULL)
Segmentation scheme, splits disjoint fragments into separate grids.
Definition: LevelSetFracture.h:131
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:713
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
IndexIterator & operator++()
Advance to the next item.
Definition: PointPartitioner.h:209
boost::shared_ptr< IndexPairList > IndexPairListPtr
Definition: PointPartitioner.h:601
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:725
void reset()
Rewind to first item.
Definition: PointPartitioner.h:195
PointIndexType const *const mPointOrder
Definition: PointPartitioner.h:275
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:294
boost::scoped_array< VoxelOffsetType > VoxelOffsetArray
Definition: PointPartitioner.h:284
std::deque< IndexPair > IndexPairList
Definition: PointPartitioner.h:478
const VoxelOffsetArray & voxelOffsets() const
Returns a list of LeafNode voxel offsets for the points.
Definition: PointPartitioner.h:166