OpenVDB  7.0.0
PointPartitioner.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
17 
18 #ifndef OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
19 #define OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
20 
21 #include <openvdb/Types.h>
22 #include <openvdb/math/Transform.h>
23 
24 #include <boost/integer.hpp> // boost::int_t<N>::least
25 #include <boost/scoped_array.hpp>
26 
27 #include <tbb/blocked_range.h>
28 #include <tbb/parallel_for.h>
29 #include <tbb/task_scheduler_init.h>
30 
31 #include <algorithm>
32 #include <cmath> // for std::isfinite()
33 #include <deque>
34 #include <map>
35 #include <set>
36 #include <utility> // std::pair
37 #include <vector>
38 
39 
40 namespace openvdb {
42 namespace OPENVDB_VERSION_NAME {
43 namespace tools {
44 
45 
47 
48 
78 template<typename PointIndexType = uint32_t, Index BucketLog2Dim = 3>
80 {
81 public:
82  enum { LOG2DIM = BucketLog2Dim };
83 
86 
87  using IndexType = PointIndexType;
88  using VoxelOffsetType = typename boost::int_t<1 + (3 * BucketLog2Dim)>::least;
89  using VoxelOffsetArray = boost::scoped_array<VoxelOffsetType>;
90 
91  class IndexIterator;
92 
94 
96 
106  template<typename PointArray>
107  void construct(const PointArray& points, const math::Transform& xform,
108  bool voxelOrder = false, bool recordVoxelOffsets = false,
109  bool cellCenteredTransform = true);
110 
111 
121  template<typename PointArray>
122  static Ptr create(const PointArray& points, const math::Transform& xform,
123  bool voxelOrder = false, bool recordVoxelOffsets = false,
124  bool cellCenteredTransform = true);
125 
126 
128  size_t size() const { return mPageCount; }
129 
131  bool empty() const { return mPageCount == 0; }
132 
134  void clear();
135 
137  void swap(PointPartitioner&);
138 
140  IndexIterator indices(size_t n) const;
141 
143  CoordBBox getBBox(size_t n) const {
144  return CoordBBox::createCube(mPageCoordinates[n], (1u << BucketLog2Dim));
145  }
146 
148  const Coord& origin(size_t n) const { return mPageCoordinates[n]; }
149 
152  const VoxelOffsetArray& voxelOffsets() const { return mVoxelOffsets; }
153 
157  bool usingCellCenteredTransform() const { return mUsingCellCenteredTransform; }
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  bool mUsingCellCenteredTransform;
171 }; // class PointPartitioner
172 
173 
175 
176 
177 template<typename PointIndexType, Index BucketLog2Dim>
178 class PointPartitioner<PointIndexType, BucketLog2Dim>::IndexIterator
179 {
180 public:
181  using IndexType = PointIndexType;
182 
183  IndexIterator(IndexType* begin = nullptr, IndexType* end = nullptr)
184  : mBegin(begin), mEnd(end), mItem(begin) {}
185 
187  void reset() { mItem = mBegin; }
188 
190  size_t size() const { return mEnd - mBegin; }
191 
193  IndexType& operator*() { assert(mItem != nullptr); return *mItem; }
194  const IndexType& operator*() const { assert(mItem != nullptr); return *mItem; }
195 
197  operator bool() const { return mItem < mEnd; }
198  bool test() const { return mItem < mEnd; }
199 
201  IndexIterator& operator++() { assert(this->test()); ++mItem; return *this; }
202 
204  bool next() { this->operator++(); return this->test(); }
205  bool increment() { this->next(); return this->test(); }
206 
208  bool operator==(const IndexIterator& other) const { return mItem == other.mItem; }
209  bool operator!=(const IndexIterator& other) const { return !this->operator==(other); }
210 
211 private:
212  IndexType * const mBegin, * const mEnd;
213  IndexType * mItem;
214 }; // class PointPartitioner::IndexIterator
215 
216 
219 
220 // Implementation details
221 
222 
223 namespace point_partitioner_internal {
224 
225 
226 template<typename PointIndexType>
228 {
229  ComputePointOrderOp(PointIndexType* pointOrder,
230  const PointIndexType* bucketCounters, const PointIndexType* bucketOffsets)
231  : mPointOrder(pointOrder)
232  , mBucketCounters(bucketCounters)
233  , mBucketOffsets(bucketOffsets)
234  {
235  }
236 
237  void operator()(const tbb::blocked_range<size_t>& range) const {
238  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
239  mPointOrder[n] += mBucketCounters[mBucketOffsets[n]];
240  }
241  }
242 
243  PointIndexType * const mPointOrder;
244  PointIndexType const * const mBucketCounters;
245  PointIndexType const * const mBucketOffsets;
246 }; // struct ComputePointOrderOp
247 
248 
249 template<typename PointIndexType>
251 {
252  CreateOrderedPointIndexArrayOp(PointIndexType* orderedIndexArray,
253  const PointIndexType* pointOrder, const PointIndexType* indices)
254  : mOrderedIndexArray(orderedIndexArray)
255  , mPointOrder(pointOrder)
256  , mIndices(indices)
257  {
258  }
259 
260  void operator()(const tbb::blocked_range<size_t>& range) const {
261  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
262  mOrderedIndexArray[mPointOrder[n]] = mIndices[n];
263  }
264  }
265 
266  PointIndexType * const mOrderedIndexArray;
267  PointIndexType const * const mPointOrder;
268  PointIndexType const * const mIndices;
269 }; // struct CreateOrderedPointIndexArrayOp
270 
271 
272 template<typename PointIndexType, Index BucketLog2Dim>
274 {
275  using VoxelOffsetType = typename boost::int_t<1 + (3 * BucketLog2Dim)>::least;
276  using VoxelOffsetArray = boost::scoped_array<VoxelOffsetType>;
277  using IndexArray = boost::scoped_array<PointIndexType>;
278 
279  VoxelOrderOp(IndexArray& indices, const IndexArray& pages,const VoxelOffsetArray& offsets)
280  : mIndices(indices.get())
281  , mPages(pages.get())
282  , mVoxelOffsets(offsets.get())
283  {
284  }
285 
286  void operator()(const tbb::blocked_range<size_t>& range) const {
287 
288  PointIndexType pointCount = 0;
289  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
290  pointCount = std::max(pointCount, (mPages[n + 1] - mPages[n]));
291  }
292 
293  const PointIndexType voxelCount = 1 << (3 * BucketLog2Dim);
294 
295  // allocate histogram buffers
296  boost::scoped_array<VoxelOffsetType> offsets(new VoxelOffsetType[pointCount]);
297  boost::scoped_array<PointIndexType> sortedIndices(new PointIndexType[pointCount]);
298  boost::scoped_array<PointIndexType> histogram(new PointIndexType[voxelCount]);
299 
300  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
301 
302  PointIndexType * const indices = mIndices + mPages[n];
303  pointCount = mPages[n + 1] - mPages[n];
304 
305  // local copy of voxel offsets.
306  for (PointIndexType i = 0; i < pointCount; ++i) {
307  offsets[i] = mVoxelOffsets[ indices[i] ];
308  }
309 
310  // reset histogram
311  memset(&histogram[0], 0, voxelCount * sizeof(PointIndexType));
312 
313  // compute histogram
314  for (PointIndexType i = 0; i < pointCount; ++i) {
315  ++histogram[ offsets[i] ];
316  }
317 
318  PointIndexType count = 0, startOffset;
319  for (int i = 0; i < int(voxelCount); ++i) {
320  if (histogram[i] > 0) {
321  startOffset = count;
322  count += histogram[i];
323  histogram[i] = startOffset;
324  }
325  }
326 
327  // sort indices based on voxel offset
328  for (PointIndexType i = 0; i < pointCount; ++i) {
329  sortedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
330  }
331 
332  memcpy(&indices[0], &sortedIndices[0], sizeof(PointIndexType) * pointCount);
333  }
334  }
335 
336  PointIndexType * const mIndices;
337  PointIndexType const * const mPages;
339 }; // struct VoxelOrderOp
340 
341 
342 template<typename PointArray, typename PointIndexType>
344 {
345  using IndexArray = boost::scoped_array<PointIndexType>;
346  using CoordArray = boost::scoped_array<Coord>;
347 
349  const IndexArray& indices, const IndexArray& pages,
350  const PointArray& points, const math::Transform& m, int log2dim, bool cellCenteredTransform)
351  : mCoordinates(coordinates.get())
352  , mIndices(indices.get())
353  , mPages(pages.get())
354  , mPoints(&points)
355  , mXForm(m)
356  , mLog2Dim(log2dim)
357  , mCellCenteredTransform(cellCenteredTransform)
358  {
359  }
360 
361  void operator()(const tbb::blocked_range<size_t>& range) const {
362 
363  using PosType = typename PointArray::PosType;
364 
365  const bool cellCentered = mCellCenteredTransform;
366  const int mask = ~((1 << mLog2Dim) - 1);
367  Coord ijk;
368  PosType pos;
369 
370  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
371 
372  mPoints->getPos(mIndices[mPages[n]], pos);
373 
374  if (std::isfinite(pos[0]) && std::isfinite(pos[1]) && std::isfinite(pos[2])) {
375  ijk = cellCentered ? mXForm.worldToIndexCellCentered(pos) :
376  mXForm.worldToIndexNodeCentered(pos);
377 
378  ijk[0] &= mask;
379  ijk[1] &= mask;
380  ijk[2] &= mask;
381 
382  mCoordinates[n] = ijk;
383  }
384  }
385  }
386 
387  Coord * const mCoordinates;
388  PointIndexType const * const mIndices;
389  PointIndexType const * const mPages;
390  PointArray const * const mPoints;
392  int const mLog2Dim;
394 }; // struct LeafNodeOriginOp
395 
396 
398 
399 
400 template<typename T>
401 struct Array
402 {
404 
405  Array(size_t size) : mSize(size), mData(new T[size]) { }
406 
407  size_t size() const { return mSize; }
408 
409  T* data() { return mData.get(); }
410  const T* data() const { return mData.get(); }
411 
412  void clear() { mSize = 0; mData.reset(); }
413 
414 private:
415  size_t mSize;
416  boost::scoped_array<T> mData;
417 }; // struct Array
418 
419 
420 template<typename PointIndexType>
422 {
424  using SegmentPtr = typename Segment::Ptr;
425 
426  MoveSegmentDataOp(std::vector<PointIndexType*>& indexLists, SegmentPtr* segments)
427  : mIndexLists(&indexLists[0]), mSegments(segments)
428  {
429  }
430 
431  void operator()(const tbb::blocked_range<size_t>& range) const {
432  for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
433  PointIndexType* indices = mIndexLists[n];
434  SegmentPtr& segment = mSegments[n];
435 
436  tbb::parallel_for(tbb::blocked_range<size_t>(0, segment->size()),
437  CopyData(indices, segment->data()));
438 
439  segment.reset(); // clear data
440  }
441  }
442 
443 private:
444 
445  struct CopyData
446  {
447  CopyData(PointIndexType* lhs, const PointIndexType* rhs) : mLhs(lhs), mRhs(rhs) { }
448 
449  void operator()(const tbb::blocked_range<size_t>& range) const {
450  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
451  mLhs[n] = mRhs[n];
452  }
453  }
454 
455  PointIndexType * const mLhs;
456  PointIndexType const * const mRhs;
457  };
458 
459  PointIndexType * const * const mIndexLists;
460  SegmentPtr * const mSegments;
461 }; // struct MoveSegmentDataOp
462 
463 
464 template<typename PointIndexType>
466 {
468  using SegmentPtr = typename Segment::Ptr;
469 
470  using IndexPair = std::pair<PointIndexType, PointIndexType>;
471  using IndexPairList = std::deque<IndexPair>;
473  using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
475 
477  SegmentPtr* indexSegments,
478  SegmentPtr* offsetSegments,
479  Coord* coords,
480  size_t numSegments)
481  : mBins(bins)
482  , mIndexSegments(indexSegments)
483  , mOffsetSegments(offsetSegments)
484  , mCoords(coords)
485  , mNumSegments(numSegments)
486  {
487  }
488 
489  void operator()(const tbb::blocked_range<size_t>& range) const {
490 
491  std::vector<IndexPairListPtr*> data;
492  std::vector<PointIndexType> arrayOffsets;
493 
494  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
495 
496  const Coord& ijk = mCoords[n];
497  size_t numIndices = 0;
498 
499  data.clear();
500 
501  for (size_t i = 0, I = mNumSegments; i < I; ++i) {
502 
503  IndexPairListMap& idxMap = *mBins[i];
504  typename IndexPairListMap::iterator iter = idxMap.find(ijk);
505 
506  if (iter != idxMap.end() && iter->second) {
507  IndexPairListPtr& idxListPtr = iter->second;
508 
509  data.push_back(&idxListPtr);
510  numIndices += idxListPtr->size();
511  }
512  }
513 
514  if (data.empty() || numIndices == 0) continue;
515 
516  SegmentPtr& indexSegment = mIndexSegments[n];
517  SegmentPtr& offsetSegment = mOffsetSegments[n];
518 
519  indexSegment.reset(new Segment(numIndices));
520  offsetSegment.reset(new Segment(numIndices));
521 
522  arrayOffsets.clear();
523  arrayOffsets.reserve(data.size());
524 
525  for (size_t i = 0, count = 0, I = data.size(); i < I; ++i) {
526  arrayOffsets.push_back(PointIndexType(count));
527  count += (*data[i])->size();
528  }
529 
530  tbb::parallel_for(tbb::blocked_range<size_t>(0, data.size()),
531  CopyData(&data[0], &arrayOffsets[0], indexSegment->data(), offsetSegment->data()));
532  }
533  }
534 
535 private:
536 
537  struct CopyData
538  {
539  CopyData(IndexPairListPtr** indexLists,
540  const PointIndexType* arrayOffsets,
541  PointIndexType* indices,
542  PointIndexType* offsets)
543  : mIndexLists(indexLists)
544  , mArrayOffsets(arrayOffsets)
545  , mIndices(indices)
546  , mOffsets(offsets)
547  {
548  }
549 
550  void operator()(const tbb::blocked_range<size_t>& range) const {
551 
552  using CIter = typename IndexPairList::const_iterator;
553 
554  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
555 
556  const PointIndexType arrayOffset = mArrayOffsets[n];
557  PointIndexType* indexPtr = &mIndices[arrayOffset];
558  PointIndexType* offsetPtr = &mOffsets[arrayOffset];
559 
560  IndexPairListPtr& list = *mIndexLists[n];
561 
562  for (CIter it = list->begin(), end = list->end(); it != end; ++it) {
563  const IndexPair& data = *it;
564  *indexPtr++ = data.first;
565  *offsetPtr++ = data.second;
566  }
567 
568  list.reset(); // clear data
569  }
570  }
571 
572  IndexPairListPtr * const * const mIndexLists;
573  PointIndexType const * const mArrayOffsets;
574  PointIndexType * const mIndices;
575  PointIndexType * const mOffsets;
576  }; // struct CopyData
577 
578  IndexPairListMapPtr * const mBins;
579  SegmentPtr * const mIndexSegments;
580  SegmentPtr * const mOffsetSegments;
581  Coord const * const mCoords;
582  size_t const mNumSegments;
583 }; // struct MergeBinsOp
584 
585 
586 template<typename PointArray, typename PointIndexType, typename VoxelOffsetType>
588 {
589  using PosType = typename PointArray::PosType;
590  using IndexPair = std::pair<PointIndexType, PointIndexType>;
591  using IndexPairList = std::deque<IndexPair>;
593  using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
595 
597  const PointArray& points,
598  VoxelOffsetType* voxelOffsets,
599  const math::Transform& m,
600  Index binLog2Dim,
601  Index bucketLog2Dim,
602  size_t numSegments,
603  bool cellCenteredTransform)
604  : mData(data)
605  , mPoints(&points)
606  , mVoxelOffsets(voxelOffsets)
607  , mXForm(m)
608  , mBinLog2Dim(binLog2Dim)
609  , mBucketLog2Dim(bucketLog2Dim)
610  , mNumSegments(numSegments)
611  , mCellCenteredTransform(cellCenteredTransform)
612  {
613  }
614 
615  void operator()(const tbb::blocked_range<size_t>& range) const {
616 
617  const Index log2dim = mBucketLog2Dim;
618  const Index log2dim2 = 2 * log2dim;
619  const Index bucketMask = (1u << log2dim) - 1u;
620 
621  const Index binLog2dim = mBinLog2Dim;
622  const Index binLog2dim2 = 2 * binLog2dim;
623 
624  const Index binMask = (1u << (log2dim + binLog2dim)) - 1u;
625  const Index invBinMask = ~binMask;
626 
627  IndexPairList * idxList = nullptr;
628  Coord ijk(0, 0, 0), loc(0, 0, 0), binCoord(0, 0, 0), lastBinCoord(1, 2, 3);
629  PosType pos;
630 
631  PointIndexType bucketOffset = 0;
632  VoxelOffsetType voxelOffset = 0;
633 
634  const bool cellCentered = mCellCenteredTransform;
635 
636  const size_t numPoints = mPoints->size();
637  const size_t segmentSize = numPoints / mNumSegments;
638 
639  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
640 
641  IndexPairListMapPtr& dataPtr = mData[n];
642  if (!dataPtr) dataPtr.reset(new IndexPairListMap());
643  IndexPairListMap& idxMap = *dataPtr;
644 
645  const bool isLastSegment = (n + 1) >= mNumSegments;
646 
647  const size_t start = n * segmentSize;
648  const size_t end = isLastSegment ? numPoints : (start + segmentSize);
649 
650  for (size_t i = start; i != end; ++i) {
651 
652  mPoints->getPos(i, pos);
653 
654  if (std::isfinite(pos[0]) && std::isfinite(pos[1]) && std::isfinite(pos[2])) {
655  ijk = cellCentered ? mXForm.worldToIndexCellCentered(pos) :
656  mXForm.worldToIndexNodeCentered(pos);
657 
658  if (mVoxelOffsets) {
659  loc[0] = ijk[0] & bucketMask;
660  loc[1] = ijk[1] & bucketMask;
661  loc[2] = ijk[2] & bucketMask;
662  voxelOffset = VoxelOffsetType(
663  (loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
664  }
665 
666  binCoord[0] = ijk[0] & invBinMask;
667  binCoord[1] = ijk[1] & invBinMask;
668  binCoord[2] = ijk[2] & invBinMask;
669 
670  ijk[0] &= binMask;
671  ijk[1] &= binMask;
672  ijk[2] &= binMask;
673 
674  ijk[0] >>= log2dim;
675  ijk[1] >>= log2dim;
676  ijk[2] >>= log2dim;
677 
678  bucketOffset = PointIndexType(
679  (ijk[0] << binLog2dim2) + (ijk[1] << binLog2dim) + ijk[2]);
680 
681  if (lastBinCoord != binCoord) {
682  lastBinCoord = binCoord;
683  IndexPairListPtr& idxListPtr = idxMap[lastBinCoord];
684  if (!idxListPtr) idxListPtr.reset(new IndexPairList());
685  idxList = idxListPtr.get();
686  }
687 
688  idxList->push_back(IndexPair(PointIndexType(i), bucketOffset));
689  if (mVoxelOffsets) mVoxelOffsets[i] = voxelOffset;
690  }
691  }
692  }
693  }
694 
696  PointArray const * const mPoints;
697  VoxelOffsetType * const mVoxelOffsets;
701  size_t const mNumSegments;
703 }; // struct BinPointIndicesOp
704 
705 
706 template<typename PointIndexType>
708 {
709  using IndexArray = boost::scoped_array<PointIndexType>;
711 
712  OrderSegmentsOp(SegmentPtr* indexSegments, SegmentPtr* offestSegments,
713  IndexArray* pageOffsetArrays, Index binVolume)
714  : mIndexSegments(indexSegments)
715  , mOffsetSegments(offestSegments)
716  , mPageOffsetArrays(pageOffsetArrays)
717  , mBinVolume(binVolume)
718  {
719  }
720 
721  void operator()(const tbb::blocked_range<size_t>& range) const {
722 
723  const size_t bucketCountersSize = size_t(mBinVolume);
724  IndexArray bucketCounters(new PointIndexType[bucketCountersSize]);
725 
726  size_t maxSegmentSize = 0;
727  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
728  maxSegmentSize = std::max(maxSegmentSize, mIndexSegments[n]->size());
729  }
730 
731  IndexArray bucketIndices(new PointIndexType[maxSegmentSize]);
732 
733 
734  for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
735 
736  memset(bucketCounters.get(), 0, sizeof(PointIndexType) * bucketCountersSize);
737 
738  const size_t segmentSize = mOffsetSegments[n]->size();
739  PointIndexType* offsets = mOffsetSegments[n]->data();
740 
741  // Count the number of points per bucket and assign a local bucket index
742  // to each point.
743  for (size_t i = 0; i < segmentSize; ++i) {
744  bucketIndices[i] = bucketCounters[offsets[i]]++;
745  }
746 
747  PointIndexType nonemptyBucketCount = 0;
748  for (size_t i = 0; i < bucketCountersSize; ++i) {
749  nonemptyBucketCount += static_cast<PointIndexType>(bucketCounters[i] != 0);
750  }
751 
752 
753  IndexArray& pageOffsets = mPageOffsetArrays[n];
754  pageOffsets.reset(new PointIndexType[nonemptyBucketCount + 1]);
755  pageOffsets[0] = nonemptyBucketCount + 1; // stores array size in first element
756 
757  // Compute bucket counter prefix sum
758  PointIndexType count = 0, idx = 1;
759  for (size_t i = 0; i < bucketCountersSize; ++i) {
760  if (bucketCounters[i] != 0) {
761  pageOffsets[idx] = bucketCounters[i];
762  bucketCounters[i] = count;
763  count += pageOffsets[idx];
764  ++idx;
765  }
766  }
767 
768  PointIndexType* indices = mIndexSegments[n]->data();
769  const tbb::blocked_range<size_t> segmentRange(0, segmentSize);
770 
771  // Compute final point order by incrementing the local bucket point index
772  // with the prefix sum offset.
773  tbb::parallel_for(segmentRange, ComputePointOrderOp<PointIndexType>(
774  bucketIndices.get(), bucketCounters.get(), offsets));
775 
776  tbb::parallel_for(segmentRange, CreateOrderedPointIndexArrayOp<PointIndexType>(
777  offsets, bucketIndices.get(), indices));
778 
779  mIndexSegments[n]->clear(); // clear data
780  }
781  }
782 
787 }; // struct OrderSegmentsOp
788 
789 
791 
792 
794 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
795 inline void binAndSegment(
796  const PointArray& points,
797  const math::Transform& xform,
798  boost::scoped_array<typename Array<PointIndexType>::Ptr>& indexSegments,
799  boost::scoped_array<typename Array<PointIndexType>::Ptr>& offsetSegments,
800  size_t& segmentCount,
801  const Index binLog2Dim,
802  const Index bucketLog2Dim,
803  VoxelOffsetType* voxelOffsets = nullptr,
804  bool cellCenteredTransform = true)
805 {
806  using IndexPair = std::pair<PointIndexType, PointIndexType>;
807  using IndexPairList = std::deque<IndexPair>;
808  using IndexPairListPtr = SharedPtr<IndexPairList>;
809  using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
810  using IndexPairListMapPtr = SharedPtr<IndexPairListMap>;
811 
812  size_t numTasks = 1, numThreads = size_t(tbb::task_scheduler_init::default_num_threads());
813  if (points.size() > (numThreads * 2)) numTasks = numThreads * 2;
814  else if (points.size() > numThreads) numTasks = numThreads;
815 
816  boost::scoped_array<IndexPairListMapPtr> bins(new IndexPairListMapPtr[numTasks]);
817 
819 
820  tbb::parallel_for(tbb::blocked_range<size_t>(0, numTasks),
821  BinOp(bins.get(), points, voxelOffsets, xform, binLog2Dim, bucketLog2Dim,
822  numTasks, cellCenteredTransform));
823 
824  std::set<Coord> uniqueCoords;
825 
826  for (size_t i = 0; i < numTasks; ++i) {
827  IndexPairListMap& idxMap = *bins[i];
828  for (typename IndexPairListMap::iterator it = idxMap.begin(); it != idxMap.end(); ++it) {
829  uniqueCoords.insert(it->first);
830  }
831  }
832 
833  std::vector<Coord> coords(uniqueCoords.begin(), uniqueCoords.end());
834  uniqueCoords.clear();
835 
836  segmentCount = coords.size();
837 
838  using SegmentPtr = typename Array<PointIndexType>::Ptr;
839 
840  indexSegments.reset(new SegmentPtr[segmentCount]);
841  offsetSegments.reset(new SegmentPtr[segmentCount]);
842 
843  using MergeOp = MergeBinsOp<PointIndexType>;
844 
845  tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
846  MergeOp(bins.get(), indexSegments.get(), offsetSegments.get(), &coords[0], numTasks));
847 }
848 
849 
850 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
851 inline void partition(
852  const PointArray& points,
853  const math::Transform& xform,
854  const Index bucketLog2Dim,
855  boost::scoped_array<PointIndexType>& pointIndices,
856  boost::scoped_array<PointIndexType>& pageOffsets,
857  PointIndexType& pageCount,
858  boost::scoped_array<VoxelOffsetType>& voxelOffsets,
859  bool recordVoxelOffsets,
860  bool cellCenteredTransform)
861 {
862  if (recordVoxelOffsets) voxelOffsets.reset(new VoxelOffsetType[points.size()]);
863  else voxelOffsets.reset();
864 
865  const Index binLog2Dim = 5u;
866  // note: Bins span a (2^(binLog2Dim + bucketLog2Dim))^3 voxel region,
867  // i.e. bucketLog2Dim = 3 and binLog2Dim = 5 corresponds to a
868  // (2^8)^3 = 256^3 voxel region.
869 
870 
871  size_t numSegments = 0;
872 
873  boost::scoped_array<typename Array<PointIndexType>::Ptr> indexSegments;
874  boost::scoped_array<typename Array<PointIndexType>::Ptr> offestSegments;
875 
876  binAndSegment<PointIndexType, VoxelOffsetType, PointArray>(points, xform,
877  indexSegments, offestSegments, numSegments, binLog2Dim, bucketLog2Dim,
878  voxelOffsets.get(), cellCenteredTransform);
879 
880  const tbb::blocked_range<size_t> segmentRange(0, numSegments);
881 
882  using IndexArray = boost::scoped_array<PointIndexType>;
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,
925  MoveSegmentDataOp<PointIndexType>(indexArray, offestSegments.get()));
926 }
927 
928 
929 } // namespace point_partitioner_internal
930 
931 
933 
934 
935 template<typename PointIndexType, Index BucketLog2Dim>
937  : mPointIndices(nullptr)
938  , mVoxelOffsets(nullptr)
939  , mPageOffsets(nullptr)
940  , mPageCoordinates(nullptr)
941  , mPageCount(0)
942  , mUsingCellCenteredTransform(true)
943 {
944 }
945 
946 
947 template<typename PointIndexType, Index BucketLog2Dim>
948 inline void
950 {
951  mPageCount = 0;
952  mUsingCellCenteredTransform = true;
953  mPointIndices.reset();
954  mVoxelOffsets.reset();
955  mPageOffsets.reset();
956  mPageCoordinates.reset();
957 }
958 
959 
960 template<typename PointIndexType, Index BucketLog2Dim>
961 inline void
963 {
964  const IndexType tmpLhsPageCount = mPageCount;
965  mPageCount = rhs.mPageCount;
966  rhs.mPageCount = tmpLhsPageCount;
967 
968  mPointIndices.swap(rhs.mPointIndices);
969  mVoxelOffsets.swap(rhs.mVoxelOffsets);
970  mPageOffsets.swap(rhs.mPageOffsets);
971  mPageCoordinates.swap(rhs.mPageCoordinates);
972 
973  bool lhsCellCenteredTransform = mUsingCellCenteredTransform;
974  mUsingCellCenteredTransform = rhs.mUsingCellCenteredTransform;
975  rhs.mUsingCellCenteredTransform = lhsCellCenteredTransform;
976 }
977 
978 
979 template<typename PointIndexType, Index BucketLog2Dim>
982 {
983  assert(bool(mPointIndices) && bool(mPageCount));
984  return IndexIterator(
985  mPointIndices.get() + mPageOffsets[n],
986  mPointIndices.get() + mPageOffsets[n + 1]);
987 }
988 
989 
990 template<typename PointIndexType, Index BucketLog2Dim>
991 template<typename PointArray>
992 inline void
994  const PointArray& points,
995  const math::Transform& xform,
996  bool voxelOrder,
997  bool recordVoxelOffsets,
998  bool cellCenteredTransform)
999 {
1000  mUsingCellCenteredTransform = cellCenteredTransform;
1001 
1002  point_partitioner_internal::partition(points, xform, BucketLog2Dim,
1003  mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets,
1004  (voxelOrder || recordVoxelOffsets), cellCenteredTransform);
1005 
1006  const tbb::blocked_range<size_t> pageRange(0, mPageCount);
1007  mPageCoordinates.reset(new Coord[mPageCount]);
1008 
1009  tbb::parallel_for(pageRange,
1011  (mPageCoordinates, mPointIndices, mPageOffsets, points, xform,
1012  BucketLog2Dim, cellCenteredTransform));
1013 
1014  if (mVoxelOffsets && voxelOrder) {
1015  tbb::parallel_for(pageRange, point_partitioner_internal::VoxelOrderOp<
1016  IndexType, BucketLog2Dim>(mPointIndices, mPageOffsets, mVoxelOffsets));
1017  }
1018 
1019  if (mVoxelOffsets && !recordVoxelOffsets) {
1020  mVoxelOffsets.reset();
1021  }
1022 }
1023 
1024 
1025 template<typename PointIndexType, Index BucketLog2Dim>
1026 template<typename PointArray>
1029  const PointArray& points,
1030  const math::Transform& xform,
1031  bool voxelOrder,
1032  bool recordVoxelOffsets,
1033  bool cellCenteredTransform)
1034 {
1035  Ptr ret(new PointPartitioner());
1036  ret->construct(points, xform, voxelOrder, recordVoxelOffsets, cellCenteredTransform);
1037  return ret;
1038 }
1039 
1040 
1042 
1043 
1044 } // namespace tools
1045 } // namespace OPENVDB_VERSION_NAME
1046 } // namespace openvdb
1047 
1048 
1049 #endif // OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:277
void construct(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false, bool cellCenteredTransform=true)
Partitions point indices into BucketLog2Dim aligned buckets.
Definition: PointPartitioner.h:993
void swap(PointPartitioner &)
Exchanges the content of the container by another.
Definition: PointPartitioner.h:962
bool next()
Advance to the next item.
Definition: PointPartitioner.h:204
PointArray const *const mPoints
Definition: PointPartitioner.h:696
static Ptr create(const PointArray &points, const math::Transform &xform, bool voxelOrder=false, bool recordVoxelOffsets=false, bool cellCenteredTransform=true)
Partitions point indices into BucketLog2Dim aligned buckets.
Definition: PointPartitioner.h:1028
Definition: PointPartitioner.h:79
SharedPtr< IndexPairListMap > IndexPairListMapPtr
Definition: PointPartitioner.h:594
size_t const mNumSegments
Definition: PointPartitioner.h:701
typename PointArray::PosType PosType
Definition: PointPartitioner.h:589
bool empty() const
true if the container size is 0, false otherwise.
Definition: PointPartitioner.h:131
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:260
Index64 pointCount(const PointDataTreeT &tree, const FilterT &filter=NullFilter(), const bool inCoreOnly=false, const bool threaded=true)
Count the total number of points in a PointDataTree.
Definition: PointCount.h:88
bool usingCellCenteredTransform() const
Returns true if this point partitioning was constructed using a cell-centered transform.
Definition: PointPartitioner.h:157
Coord *const mCoordinates
Definition: PointPartitioner.h:387
std::shared_ptr< T > SharedPtr
Definition: Types.h:91
bool increment()
Definition: PointPartitioner.h:205
VoxelOffsetType *const mVoxelOffsets
Definition: PointPartitioner.h:697
CoordBBox getBBox(size_t n) const
Returns the coordinate-aligned bounding box for bucket n.
Definition: PointPartitioner.h:143
std::map< Coord, IndexPairListPtr > IndexPairListMap
Definition: PointPartitioner.h:473
OrderSegmentsOp(SegmentPtr *indexSegments, SegmentPtr *offestSegments, IndexArray *pageOffsetArrays, Index binVolume)
Definition: PointPartitioner.h:712
void reset()
Rewind to first item.
Definition: PointPartitioner.h:187
bool operator!=(const IndexIterator &other) const
Definition: PointPartitioner.h:209
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:615
size_t size() const
Number of point indices in the iterator range.
Definition: PointPartitioner.h:190
bool operator==(const IndexIterator &other) const
Equality operators.
Definition: PointPartitioner.h:208
MergeBinsOp(IndexPairListMapPtr *bins, SegmentPtr *indexSegments, SegmentPtr *offsetSegments, Coord *coords, size_t numSegments)
Definition: PointPartitioner.h:476
T * data()
Definition: PointPartitioner.h:409
size_t size() const
Definition: PointPartitioner.h:407
boost::scoped_array< VoxelOffsetType > VoxelOffsetArray
Definition: PointPartitioner.h:89
SharedPtr< const PointPartitioner > ConstPtr
Definition: PointPartitioner.h:85
IndexIterator(IndexType *begin=nullptr, IndexType *end=nullptr)
Definition: PointPartitioner.h:183
BinPointIndicesOp(IndexPairListMapPtr *data, const PointArray &points, VoxelOffsetType *voxelOffsets, const math::Transform &m, Index binLog2Dim, Index bucketLog2Dim, size_t numSegments, bool cellCenteredTransform)
Definition: PointPartitioner.h:596
SharedPtr< IndexPairList > IndexPairListPtr
Definition: PointPartitioner.h:472
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:431
IndexArray *const mPageOffsetArrays
Definition: PointPartitioner.h:785
SharedPtr< IndexPairList > IndexPairListPtr
Definition: PointPartitioner.h:592
PointIndexType const *const mBucketCounters
Definition: PointPartitioner.h:244
bool test() const
Definition: PointPartitioner.h:198
const VoxelOffsetArray & voxelOffsets() const
Returns a list of LeafNode voxel offsets for the points.
Definition: PointPartitioner.h:152
math::Transform const mXForm
Definition: PointPartitioner.h:698
boost::scoped_array< VoxelOffsetType > VoxelOffsetArray
Definition: PointPartitioner.h:276
std::pair< PointIndexType, PointIndexType > IndexPair
Definition: PointPartitioner.h:590
Index const mBinLog2Dim
Definition: PointPartitioner.h:699
SegmentPtr *const mIndexSegments
Definition: PointPartitioner.h:783
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:489
PointIndexType const *const mIndices
Definition: PointPartitioner.h:388
PointIndexType const *const mBucketOffsets
Definition: PointPartitioner.h:245
SharedPtr< Array > Ptr
Definition: PointPartitioner.h:403
SharedPtr< IndexPairListMap > IndexPairListMapPtr
Definition: PointPartitioner.h:474
std::pair< Index, Index > IndexPair
Definition: PointMove.h:168
IndexPairListMapPtr *const mData
Definition: PointPartitioner.h:695
const T * data() const
Definition: PointPartitioner.h:410
Definition: Exceptions.h:13
CreateOrderedPointIndexArrayOp(PointIndexType *orderedIndexArray, const PointIndexType *pointOrder, const PointIndexType *indices)
Definition: PointPartitioner.h:252
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:345
PointIndexType *const mIndices
Definition: PointPartitioner.h:336
std::vector< Index > IndexArray
Definition: PointMove.h:161
PointIndexType IndexType
Definition: PointPartitioner.h:181
SharedPtr< PointPartitioner > Ptr
Definition: PointPartitioner.h:84
int const mLog2Dim
Definition: PointPartitioner.h:392
std::deque< IndexPair > IndexPairList
Definition: PointPartitioner.h:591
Array(size_t size)
Definition: PointPartitioner.h:405
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:286
typename Array< PointIndexType >::Ptr SegmentPtr
Definition: PointPartitioner.h:710
boost::scoped_array< PointIndexType > IndexArray
Definition: PointPartitioner.h:709
LeafNodeOriginOp(CoordArray &coordinates, const IndexArray &indices, const IndexArray &pages, const PointArray &points, const math::Transform &m, int log2dim, bool cellCenteredTransform)
Definition: PointPartitioner.h:348
PointPartitioner()
Definition: PointPartitioner.h:936
math::Transform const mXForm
Definition: PointPartitioner.h:391
VoxelOrderOp(IndexArray &indices, const IndexArray &pages, const VoxelOffsetArray &offsets)
Definition: PointPartitioner.h:279
void clear()
Definition: PointPartitioner.h:412
SegmentPtr *const mOffsetSegments
Definition: PointPartitioner.h:784
IndexIterator & operator++()
Advance to the next item.
Definition: PointPartitioner.h:201
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:471
Definition: Transform.h:39
typename boost::int_t< 1+(3 *BucketLog2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:88
PointIndexType const *const mIndices
Definition: PointPartitioner.h:268
std::pair< PointIndexType, PointIndexType > IndexPair
Definition: PointPartitioner.h:470
Index32 Index
Definition: Types.h:31
const Coord & origin(size_t n) const
Returns the origin coordinate for bucket n.
Definition: PointPartitioner.h:148
bool const mCellCenteredTransform
Definition: PointPartitioner.h:702
IndexIterator indices(size_t n) const
Returns the point indices for bucket n.
Definition: PointPartitioner.h:981
VoxelOffsetType const *const mVoxelOffsets
Definition: PointPartitioner.h:338
PointIndexType const *const mPages
Definition: PointPartitioner.h:389
typename Segment::Ptr SegmentPtr
Definition: PointPartitioner.h:468
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:361
void clear()
Removes all data and frees up memory.
Definition: PointPartitioner.h:949
std::deque< IndexPair > IndexPairList
Definition: PointPartitioner.h:471
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, bool cellCenteredTransform)
Definition: PointPartitioner.h:851
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=nullptr, bool cellCenteredTransform=true)
Segment points using one level of least significant digit radix bins.
Definition: PointPartitioner.h:795
PointIndexType *const mPointOrder
Definition: PointPartitioner.h:243
Index const mBinVolume
Definition: PointPartitioner.h:786
PointIndexType const *const mPointOrder
Definition: PointPartitioner.h:267
PointIndexType IndexType
Definition: PointPartitioner.h:87
typename boost::int_t< 1+(3 *BucketLog2Dim)>::least VoxelOffsetType
Definition: PointPartitioner.h:275
PointIndexType *const mOrderedIndexArray
Definition: PointPartitioner.h:266
PointArray const *const mPoints
Definition: PointPartitioner.h:390
MoveSegmentDataOp(std::vector< PointIndexType * > &indexLists, SegmentPtr *segments)
Definition: PointPartitioner.h:426
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
IndexType & operator*()
Returns the item to which this iterator is currently pointing.
Definition: PointPartitioner.h:193
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:341
const IndexType & operator*() const
Definition: PointPartitioner.h:194
std::map< Coord, IndexPairListPtr > IndexPairListMap
Definition: PointPartitioner.h:593
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:237
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:721
bool const mCellCenteredTransform
Definition: PointPartitioner.h:393
ComputePointOrderOp(PointIndexType *pointOrder, const PointIndexType *bucketCounters, const PointIndexType *bucketOffsets)
Definition: PointPartitioner.h:229
size_t size() const
Returns the number of buckets.
Definition: PointPartitioner.h:128
PointIndexType const *const mPages
Definition: PointPartitioner.h:337
const std::enable_if<!VecTraits< T >::IsVec, T >::type & max(const T &a, const T &b)
Definition: Composite.h:106
Index const mBucketLog2Dim
Definition: PointPartitioner.h:700
boost::scoped_array< Coord > CoordArray
Definition: PointPartitioner.h:346
typename Segment::Ptr SegmentPtr
Definition: PointPartitioner.h:424