42 #ifndef OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
43 #define OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
46 #include <openvdb/Types.h>
47 #include <openvdb/math/Transform.h>
53 #include <boost/scoped_array.hpp>
54 #include <boost/integer.hpp>
55 #include <boost/math/special_functions/fpclassify.hpp>
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>
91 template<
typename Po
intIndexT = u
int32_t, Index Log2Dim = 3>
95 enum { LOG2DIM = Log2Dim };
97 typedef boost::shared_ptr<PointPartitioner>
Ptr;
98 typedef boost::shared_ptr<const PointPartitioner>
ConstPtr;
116 template<
typename Po
intArray>
118 bool voxelOrder =
false,
bool recordVoxelOffsets =
false);
127 template<
typename Po
intArray>
129 bool voxelOrder =
false,
bool recordVoxelOffsets =
false);
133 size_t size()
const {
return mPageCount; }
136 bool empty()
const {
return mPageCount == 0; }
145 IndexIterator indices(
size_t n)
const;
149 return CoordBBox::createCube(mPageCoordinates[n], (1u << Log2Dim));
153 const Coord&
origin(
size_t n)
const {
return mPageCoordinates[n]; }
164 boost::scoped_array<IndexType> mPointIndices;
165 VoxelOffsetArray mVoxelOffsets;
167 boost::scoped_array<IndexType> mPageOffsets;
168 boost::scoped_array<Coord> mPageCoordinates;
169 IndexType mPageCount;
176 template<
typename Po
intIndexT, Index Log2Dim>
183 : mBegin(begin), mEnd(end), mItem(begin) {}
189 size_t size()
const {
return mEnd - mBegin; }
192 IndexType&
operator*() { assert(mItem != NULL);
return *mItem; }
193 const IndexType&
operator*()
const { assert(mItem != NULL);
return *mItem; }
196 operator bool()
const {
return mItem < mEnd; }
197 bool test()
const {
return mItem < mEnd; }
203 bool next() { this->operator++();
return this->test(); }
211 IndexType *
const mBegin, *
const mEnd;
221 namespace point_partitioner_internal {
228 template<
typename Po
intArray>
235 , mMin(std::numeric_limits<ElementType>::
max())
236 , mMax(-std::numeric_limits<ElementType>::
max())
241 : mPoints(other.mPoints)
242 , mMin(std::numeric_limits<ElementType>::
max())
243 , mMax(-std::numeric_limits<ElementType>::
max())
249 PointType pos, tmpMin(mMin), tmpMax(mMax);
251 for (
size_t n = range.begin(), N = range.end(); n != N; ++n) {
252 mPoints->getPos(n, pos);
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]);
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]);
293 template<
typename IndexT>
298 return first < rhs.
first;
303 template<
typename Po
intArray,
typename IndexT,
typename VoxelOffsetT>
311 VoxelOffsetArray& voxelOffsets, IndexArray& bucketOffsets,
313 const CoordBBox& bbox,
int log2dim)
314 : mVoxelOffsets(voxelOffsets.get())
315 , mBucketOffsets(bucketOffsets.get())
320 , mBlockLog2Dim(log2dim)
325 void operator()(
const tbb::blocked_range<size_t>& range)
const {
327 Coord ijk(0, 0, 0), loc(0, 0, 0);
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];
332 const int log2dim = mBlockLog2Dim, log2dim2 = 2 * mBlockLog2Dim,
333 mask = unsigned(1u << mBlockLog2Dim) - 1u;
335 IndexT bucketOffset = 0;
336 VoxelOffsetT voxelOffset = 0;
338 for (
size_t n = range.begin(), N = range.end(); n != N; ++n) {
340 mPoints->getPos(n, pos);
342 if (boost::math::isfinite(pos[0]) &&
343 boost::math::isfinite(pos[1]) &&
344 boost::math::isfinite(pos[2])) {
346 ijk = mXForm.worldToIndexCellCentered(pos);
350 loc[0] = ijk[0] & mask;
351 loc[1] = ijk[1] & mask;
352 loc[2] = ijk[2] & mask;
354 voxelOffset = VoxelOffsetT((loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
365 bucketOffset = IndexT(ijk[0] * yzDim + ijk[1] * zDim + ijk[2]);
366 mBucketOffsets[n] = bucketOffset;
368 if (mVoxelOffsets) mVoxelOffsets[n] = voxelOffset;
386 template<
typename Po
intArray,
typename IndexT,
typename VoxelOffsetT>
395 VoxelOffsetArray& voxelOffsets, IndexPairArray& bucketOffsets,
397 const CoordBBox& bbox,
int log2dim)
398 : mVoxelOffsets(voxelOffsets.get())
399 , mBucketOffsets(bucketOffsets.get())
404 , mBlockLog2Dim(log2dim)
409 void operator()(
const tbb::blocked_range<size_t>& range)
const {
411 Coord ijk(0, 0, 0), loc(0, 0, 0);
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];
416 const int log2dim = mBlockLog2Dim, log2dim2 = 2 * mBlockLog2Dim,
417 mask = unsigned(1u << mBlockLog2Dim) - 1u;
419 IndexT bucketOffset = 0;
420 VoxelOffsetT voxelOffset = 0;
422 for (
size_t n = range.begin(), N = range.end(); n != N; ++n) {
424 mPoints->getPos(n, pos);
426 if (boost::math::isfinite(pos[0]) &&
427 boost::math::isfinite(pos[1]) &&
428 boost::math::isfinite(pos[2])) {
429 ijk = mXForm.worldToIndexCellCentered(pos);
433 loc[0] = ijk[0] & mask;
434 loc[1] = ijk[1] & mask;
435 loc[2] = ijk[2] & mask;
437 voxelOffset = VoxelOffsetT((loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
448 bucketOffset = IndexT(ijk[0] * yzDim + ijk[1] * zDim + ijk[2]);
450 IndexPairT& item = mBucketOffsets[n];
452 item.
first = bucketOffset;
455 if (mVoxelOffsets) mVoxelOffsets[n] = voxelOffset;
474 template<
typename IndexT>
482 AtomicIndexArray& bucketMap,
const IndexArray& bucketOffsets)
483 : mBucketIndices(bucketIndices.get())
484 , mBucketMap(bucketMap.get())
485 , mBucketOffsets(bucketOffsets.get())
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();
501 template<
typename IndexT>
509 const AtomicIndexArray& bucketMap,
const IndexArray& bucketOffsets)
510 : mPointIndices(pointIndices.get())
511 , mBucketMap(bucketMap.get())
512 , mBucketOffsets(bucketOffsets.get())
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]];
528 template<
typename IndexT>
534 : mPointIndices(pointIndices.get())
535 , mBucketOffsets(bucketOffsets.get())
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());
543 mBucketOffsets[mPointIndices[n]] = n;
551 template<
typename IndexT>
557 PageOrderOp(IndexArray& pointIndices,
const IndexPairArray& pairs)
558 : mPointIndices(pointIndices.get())
559 , mPairs(pairs.get())
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;
573 template<
typename IndexT>
576 typedef std::pair<IndexT, IndexT>
Range;
581 IndexArray&
segment, IndexT& size)
583 , mPairs(pairs.get())
591 const IndexT start = mRange.first;
592 const IndexT end = mRange.second;
594 std::deque<IndexT> pageBreaks;
596 IndexT last = mPairs[start].first;
597 for (IndexT n = start + 1; n != end; ++n) {
599 if (last != pair.
first) {
601 pageBreaks.push_back(n);
605 if (!pageBreaks.empty()) {
607 IndexArray
segment(
new IndexT[pageBreaks.size()]);
610 typename std::deque<IndexT>::iterator it = pageBreaks.begin();
611 while (it != pageBreaks.end()) {
616 *mSize =
static_cast<IndexT
>(pageBreaks.size());
628 template<
typename IndexT, Index Log2Dim>
635 VoxelOrderOp(IndexArray& indices,
const IndexArray& pages,
const VoxelOffsetArray& offsets)
636 : mIndices(indices.get())
637 , mPages(pages.get())
638 , mVoxelOffsets(offsets.get())
643 void operator()(
const tbb::blocked_range<size_t>& range)
const {
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]));
650 const IndexT voxelCount = 1 << (3 * Log2Dim);
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]);
657 for (
size_t n(range.begin()), N(range.end()); n != N; ++n) {
659 IndexT *
const indices = mIndices + mPages[n];
660 pointCount = mPages[n + 1] - mPages[n];
663 for (IndexT i = 0; i < pointCount; ++i) {
664 offsets[i] = mVoxelOffsets[ indices[i] ];
668 memset(&histogram[0], 0, voxelCount *
sizeof(IndexT));
671 for (IndexT i = 0; i < pointCount; ++i) {
672 ++histogram[ offsets[i] ];
675 IndexT count = 0, startOffset;
676 for (
int i = 0; i < int(voxelCount); ++i) {
677 if (histogram[i] > 0) {
679 count += histogram[i];
680 histogram[i] = startOffset;
685 for (IndexT i = 0; i < pointCount; ++i) {
686 sortedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
689 memcpy(&indices[0], &sortedIndices[0],
sizeof(IndexT) * pointCount);
700 template<
typename IndexT>
706 : mIndices(indices.get()) , mPages(pages.get()) { }
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]);
718 template<
typename Po
intArray,
typename IndexT>
725 const IndexArray& indices,
const IndexArray& pages,
727 : mCoordinates(coordinates.get())
728 , mIndices(indices.get())
729 , mPages(pages.get())
736 void operator()(
const tbb::blocked_range<size_t>& range)
const {
738 const int mask = ~((1 << mLog2Dim) - 1);
740 typename PointArray::value_type pos;
741 for (
size_t n = range.begin(), N = range.end(); n != N; ++n) {
743 mPoints->getPos(mIndices[mPages[n]], pos);
745 if (boost::math::isfinite(pos[0]) &&
746 boost::math::isfinite(pos[1]) &&
747 boost::math::isfinite(pos[2])) {
749 ijk = mXForm.worldToIndexCellCentered(pos);
755 mCoordinates[n] = ijk;
777 template<
typename IntType>
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]);
785 uint64_t product = xdim * ydim;
796 template<
typename Po
intArray>
801 tbb::parallel_reduce(tbb::blocked_range<size_t>(0, points.size()), bboxOp);
811 box.min() = math::Coord::round(minIS);
812 box.max() = math::Coord::round(maxIS);
815 box.min() >>= log2dim;
816 box.max() >>= log2dim;
821 template<Index Log2Dim,
typename IndexT,
typename VoxelOffsetT,
typename Po
intArray>
825 const CoordBBox& bbox,
826 boost::scoped_array<IndexT>& pointIndices,
827 boost::scoped_array<IndexT>& pageOffsets,
829 boost::scoped_array<VoxelOffsetT>& voxelOffsets,
830 bool recordVoxelOffsets)
832 typedef tbb::atomic<IndexT> AtomicIndexT;
833 typedef boost::scoped_array<AtomicIndexT> AtomicIndexArray;
834 typedef boost::scoped_array<IndexT> IndexArray;
840 const size_t pointCount = points.size();
841 const tbb::blocked_range<size_t> pointRange(0, pointCount);
843 if (recordVoxelOffsets) {
844 voxelOffsets.reset(
new VoxelOffsetT[pointCount]);
846 voxelOffsets.reset();
849 IndexArray bucketOffsets(
new IndexT[pointCount]);
853 voxelOffsets, bucketOffsets, points, xform, bbox,
int(Log2Dim)));
857 const Index64 volume = bbox.volume();
859 pointIndices.reset(
new IndexT[pointCount]);
860 AtomicIndexArray bucketMap(
new AtomicIndexT[volume]);
861 memset(&bucketMap[0], 0,
sizeof(AtomicIndexT) * volume);
863 tbb::parallel_for(pointRange,
869 for (
size_t n(0), N(volume); n < N; ++n) {
870 pageCount +=
static_cast<IndexT
>(bucketMap[n] != 0);
873 pageOffsets.reset(
new IndexT[pageCount + 1]);
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];
884 pageOffsets[pageCount] = count;
889 tbb::parallel_for(pointRange,
897 pointIndices.swap(bucketOffsets);
898 bucketOffsets.reset();
902 template<Index Log2Dim,
typename IndexT,
typename VoxelOffsetT,
typename Po
intArray>
906 const CoordBBox& bbox,
907 boost::scoped_array<IndexT>& pointIndices,
908 boost::scoped_array<IndexT>& pageOffsets,
910 boost::scoped_array<VoxelOffsetT>& voxelOffsets,
911 bool recordVoxelOffsets)
913 typedef boost::scoped_array<IndexT> IndexArray;
915 typedef boost::scoped_array<IndexPairT> IndexPairArray;
919 const size_t pointCount = points.size();
920 const tbb::blocked_range<size_t> pointRange(0, pointCount);
922 if (recordVoxelOffsets) {
923 voxelOffsets.reset(
new VoxelOffsetT[pointCount]);
925 voxelOffsets.reset();
928 IndexPairArray bucketOffsets(
new IndexPairT[pointCount]);
931 voxelOffsets, bucketOffsets, points, xform, bbox,
int(Log2Dim)));
933 tbb::parallel_sort(bucketOffsets.get(), bucketOffsets.get() + pointCount);
936 const size_t nthreads = tbb::task_scheduler_init::default_num_threads();
937 const size_t ntasks = nthreads > 1 ? 2 * nthreads : 1;
941 IndexArray segmentSizes(
new IndexT[ntasks]);
942 memset(segmentSizes.get(), 0, ntasks *
sizeof(IndexT));
943 boost::scoped_array<IndexArray> segments(
new IndexArray[ntasks]);
945 const IndexT grainSize =
static_cast<IndexT
>(pointCount / ntasks);
946 const IndexT end =
static_cast<IndexT
>(grainSize * (ntasks - 1));
948 tbb::task_group tasks;
951 std::pair<IndexT, IndexT> range;
955 range.second = grainSize;
959 for (IndexT n = grainSize; n < end; n += grainSize) {
961 range.second = n+grainSize;
967 range.second =
static_cast<IndexT
>(pointCount);
974 for (
size_t n = 0; n < ntasks; ++n) {
975 pcount += segmentSizes[n];
978 pageCount =
static_cast<IndexT
>(pcount);
979 pageOffsets.reset(
new IndexT[pageCount + 1]);
982 for (
size_t n = 0; n < ntasks; ++n) {
983 const IndexT size = segmentSizes[n];
985 memcpy(pageOffsets.get() + pcount, segments[n].get(), size *
sizeof(IndexT));
991 pageOffsets[pageCount] =
static_cast<IndexT
>(pointCount);
995 std::deque<IndexT> pageBreaks;
996 IndexT last = bucketOffsets[0].first;
998 for (IndexT n = 1; n != pointCount; ++n) {
999 if (last != bucketOffsets[n].first) {
1000 last = bucketOffsets[n].first;
1001 pageBreaks.push_back(n);
1005 pageCount =
static_cast<IndexT
>(pageBreaks.size() + 1);
1006 pageOffsets.reset(
new IndexT[pageCount + 1]);
1008 if (!pageBreaks.empty()) {
1010 IndexT* item = pageOffsets.get() + 1;
1012 typename std::deque<IndexT>::iterator it = pageBreaks.begin();
1013 while (it != pageBreaks.end()) {
1019 pageOffsets[pageCount] =
static_cast<IndexT
>(pointCount);
1023 pointIndices.reset(
new IndexT[pointCount]);
1033 template<
typename Po
intIndexT, Index Log2Dim>
1035 : mPointIndices(NULL)
1036 , mVoxelOffsets(NULL)
1037 , mPageOffsets(NULL)
1038 , mPageCoordinates(NULL)
1044 template<
typename Po
intIndexT, Index Log2Dim>
1049 mPointIndices.reset();
1050 mVoxelOffsets.reset();
1051 mPageOffsets.reset();
1052 mPageCoordinates.reset();
1056 template<
typename Po
intIndexT, Index Log2Dim>
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);
1068 template<
typename Po
intIndexT, Index Log2Dim>
1072 assert(
bool(mPointIndices) &&
bool(mPageCount));
1074 mPointIndices.get() + mPageOffsets[n],
1075 mPointIndices.get() + mPageOffsets[n + 1]);
1079 template<
typename Po
intIndexT, Index Log2Dim>
1080 template<
typename Po
intArray>
1083 const math::Transform& xform,
bool voxelOrder,
bool recordVoxelOffsets)
1085 const CoordBBox bbox =
1088 if(!point_partitioner_internal::isVolumeCalculationOverflowSafe<PointIndexT>(bbox)) {
1092 "use uint64 for the PointIndexT type in the PointPartitioner.");
1100 point_partitioner_internal::sortPartition<Log2Dim>(points, xform, bbox,
1101 mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets, (voxelOrder || recordVoxelOffsets));
1103 point_partitioner_internal::partition<Log2Dim>(points, xform, bbox,
1104 mPointIndices, mPageOffsets, mPageCount, mVoxelOffsets, (voxelOrder || recordVoxelOffsets));
1107 const tbb::blocked_range<size_t> pageRange(0, mPageCount);
1109 tbb::parallel_for(pageRange,
1112 mPageCoordinates.reset(
new Coord[mPageCount]);
1114 tbb::parallel_for(pageRange,
1116 (mPageCoordinates, mPointIndices, mPageOffsets, points, xform, Log2Dim));
1118 if (mVoxelOffsets && voxelOrder) {
1120 IndexType, Log2Dim>(mPointIndices, mPageOffsets, mVoxelOffsets));
1123 if (mVoxelOffsets && !recordVoxelOffsets) {
1124 mVoxelOffsets.reset();
1129 template<
typename Po
intIndexT, Index Log2Dim>
1130 template<
typename Po
intArray>
1133 bool voxelOrder,
bool recordVoxelOffsets)
1136 ret->construct(points, xform, voxelOrder, recordVoxelOffsets);
1149 #endif // OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
IndexPair< IndexT > const *const mPairs
Definition: PointPartitioner.h:621
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:554
Definition: PointPartitioner.h:552
uint64_t Index64
Definition: Types.h:58
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
Range mRange
Definition: PointPartitioner.h:620
boost::scoped_array< IndexPair< IndexT > > IndexPairArray
Definition: PointPartitioner.h:578
PageOrderOp(IndexArray &pointIndices, const IndexPairArray &pairs)
Definition: PointPartitioner.h:557
void operator()() const
Definition: PointPartitioner.h:589
boost::scoped_array< IndexT > IndexArray
Definition: PointPartitioner.h:577
boost::scoped_array< IndexPair< IndexT > > IndexPairArray
Definition: PointPartitioner.h:555
#define OPENVDB_VERSION_NAME
Definition: version.h:43
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...
Definition: Exceptions.h:39
OPENVDB_API Hermite min(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
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
IndexArray *const mSegment
Definition: PointPartitioner.h:622
Definition: Exceptions.h:78
bool operator==(const Vec3< T0 > &v0, const Vec3< T1 > &v1)
Equality operator, does exact floating point comparisons.
Definition: Vec3.h:450
std::pair< IndexT, IndexT > Range
Definition: PointPartitioner.h:576
IndexT *const mSize
Definition: PointPartitioner.h:623
OPENVDB_API Hermite max(const Hermite &, const Hermite &)
min and max operations done directly on the compressed data.
void operator()(const tbb::blocked_range< size_t > &range) const
Definition: PointPartitioner.h:563
Definition: PointPartitioner.h:574
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
IndexPair< IndexT > const *const mPairs
Definition: PointPartitioner.h:570
IndexT *const mPointIndices
Definition: PointPartitioner.h:569