GCC Code Coverage Report

Directory: ./
File: openvdb/openvdb/tools/PointPartitioner.h
Date: 2022-07-25 17:40:05
Exec Total Coverage
Lines: 227 252 90.1%
Functions: 42 48 87.5%
Branches: 253 404 62.6%
Line Branch Exec Source
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3
4 /// @file PointPartitioner.h
5 ///
6 /// @brief Spatially partitions points using a parallel radix-based
7 /// sorting algorithm.
8 ///
9 /// @details Performs a stable deterministic sort; partitioning the same
10 /// point sequence will produce the same result each time.
11 /// @details The algorithm is unbounded meaning that points may be
12 /// distributed anywhere in index space.
13 /// @details The actual points are never stored in the tool, only
14 /// offsets into an external array.
15 ///
16 /// @author Mihai Alden
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 <tbb/blocked_range.h>
25 #include <tbb/parallel_for.h>
26 #include <tbb/task_arena.h>
27
28 #include <algorithm>
29 #include <cmath> // for std::isfinite()
30 #include <deque>
31 #include <map>
32 #include <set>
33 #include <utility> // std::pair
34 #include <vector>
35
36
37 namespace openvdb {
38 OPENVDB_USE_VERSION_NAMESPACE
39 namespace OPENVDB_VERSION_NAME {
40 namespace tools {
41
42
43 ////////////////////////////////////////
44
45
46 /// @brief Partitions points into @c BucketLog2Dim aligned buckets
47 /// using a parallel radix-based sorting algorithm.
48 ///
49 /// @interface PointArray
50 /// Expected interface for the PointArray container:
51 /// @code
52 /// template<typename VectorType>
53 /// struct PointArray
54 /// {
55 /// // The type used to represent world-space point positions
56 /// using PosType = VectorType;
57 ///
58 /// // Return the number of points in the array
59 /// size_t size() const;
60 ///
61 /// // Return the world-space position of the nth point in the array.
62 /// void getPos(size_t n, PosType& xyz) const;
63 /// };
64 /// @endcode
65 ///
66 /// @details Performs a stable deterministic sort; partitioning the same
67 /// point sequence will produce the same result each time.
68 /// @details The algorithm is unbounded meaning that points may be
69 /// distributed anywhere in index space.
70 /// @details The actual points are never stored in the tool, only
71 /// offsets into an external array.
72 /// @details @c BucketLog2Dim defines the bucket coordinate dimensions,
73 /// i.e. BucketLog2Dim = 3 corresponds to a bucket that spans
74 /// a (2^3)^3 = 8^3 voxel region.
75 template<typename PointIndexType = uint32_t, Index BucketLog2Dim = 3>
76 class PointPartitioner
77 {
78 public:
79 enum { LOG2DIM = BucketLog2Dim };
80
81 using Ptr = SharedPtr<PointPartitioner>;
82 using ConstPtr = SharedPtr<const PointPartitioner>;
83
84 using IndexType = PointIndexType;
85
86 static constexpr Index bits = 1 + (3 * BucketLog2Dim);
87 // signed, so if bits is exactly 16, int32 is required
88 using VoxelOffsetType = typename std::conditional<(bits < 16),
89 int16_t, typename std::conditional<(bits < 32), int32_t, int64_t>::type>::type;
90
91 using VoxelOffsetArray = std::unique_ptr<VoxelOffsetType[]>;
92
93 class IndexIterator;
94
95 //////////
96
97 PointPartitioner();
98
99 /// @brief Partitions point indices into @c BucketLog2Dim aligned buckets.
100 ///
101 /// @param points list of world space points.
102 /// @param xform world to index space transform.
103 /// @param voxelOrder sort point indices by local voxel offsets.
104 /// @param recordVoxelOffsets construct local voxel offsets
105 /// @param cellCenteredTransform toggle the cell-centered interpretation that imagines world
106 /// space as divided into discrete cells (e.g., cubes) centered
107 /// on the image of the index-space lattice points.
108 template<typename PointArray>
109 void construct(const PointArray& points, const math::Transform& xform,
110 bool voxelOrder = false, bool recordVoxelOffsets = false,
111 bool cellCenteredTransform = true);
112
113
114 /// @brief Partitions point indices into @c BucketLog2Dim aligned buckets.
115 ///
116 /// @param points list of world space points.
117 /// @param xform world to index space transform.
118 /// @param voxelOrder sort point indices by local voxel offsets.
119 /// @param recordVoxelOffsets construct local voxel offsets
120 /// @param cellCenteredTransform toggle the cell-centered interpretation that imagines world
121 /// space as divided into discrete cells (e.g., cubes) centered
122 /// on the image of the index-space lattice points.
123 template<typename PointArray>
124 static Ptr create(const PointArray& points, const math::Transform& xform,
125 bool voxelOrder = false, bool recordVoxelOffsets = false,
126 bool cellCenteredTransform = true);
127
128
129 /// @brief Returns the number of buckets.
130
6/9
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 709 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 5 times.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
 732 size_t size() const { return mPageCount; }
131
132 /// @brief true if the container size is 0, false otherwise.
133
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 bool empty() const { return mPageCount == 0; }
134
135 /// @brief Removes all data and frees up memory.
136 void clear();
137
138 /// @brief Exchanges the content of the container by another.
139 void swap(PointPartitioner&);
140
141 /// @brief Returns the point indices for bucket @a n
142 IndexIterator indices(size_t n) const;
143
144 /// @brief Returns the coordinate-aligned bounding box for bucket @a n
145 CoordBBox getBBox(size_t n) const {
146 return CoordBBox::createCube(mPageCoordinates[n], (1u << BucketLog2Dim));
147 }
148
149 /// @brief Returns the origin coordinate for bucket @a n
150 const Coord& origin(size_t n) const { return mPageCoordinates[n]; }
151
152 /// @brief Returns a list of @c LeafNode voxel offsets for the points.
153 /// @note The list is optionally constructed.
154 const VoxelOffsetArray& voxelOffsets() const { return mVoxelOffsets; }
155
156 /// @brief Returns @c true if this point partitioning was constructed
157 /// using a cell-centered transform.
158 /// @note Cell-centered interpretation is the default behavior.
159
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 709 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 9 times.
 720 bool usingCellCenteredTransform() const { return mUsingCellCenteredTransform; }
160
161 private:
162 // Disallow copying
163 PointPartitioner(const PointPartitioner&);
164 PointPartitioner& operator=(const PointPartitioner&);
165
166 std::unique_ptr<IndexType[]> mPointIndices;
167 VoxelOffsetArray mVoxelOffsets;
168
169 std::unique_ptr<IndexType[]> mPageOffsets;
170 std::unique_ptr<Coord[]> mPageCoordinates;
171 IndexType mPageCount;
172 bool mUsingCellCenteredTransform;
173 }; // class PointPartitioner
174
175
176 using UInt32PointPartitioner = PointPartitioner<uint32_t, 3>;
177
178
179 template<typename PointIndexType, Index BucketLog2Dim>
180 class PointPartitioner<PointIndexType, BucketLog2Dim>::IndexIterator
181 {
182 public:
183 using IndexType = PointIndexType;
184
185 86895 IndexIterator(IndexType* begin = nullptr, IndexType* end = nullptr)
186 86895 : mBegin(begin), mEnd(end), mItem(begin) {}
187
188 /// @brief Rewind to first item.
189 2 void reset() { mItem = mBegin; }
190
191 /// @brief Number of point indices in the iterator range.
192
3/5
✓ Branch 0 taken 6951 times.
✓ Branch 1 taken 36449 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 43401 size_t size() const { return mEnd - mBegin; }
193
194 /// @brief Returns the item to which this iterator is currently pointing.
195
10/18
✓ Branch 0 taken 43399 times.
✓ Branch 1 taken 18 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 10 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 10 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 10 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 4 times.
✗ Branch 18 not taken.
✓ Branch 19 taken 15 times.
✗ Branch 21 not taken.
✓ Branch 22 taken 23 times.
✗ Branch 24 not taken.
✓ Branch 25 taken 23 times.
 43530 IndexType& operator*() { assert(mItem != nullptr); return *mItem; }
196 const IndexType& operator*() const { assert(mItem != nullptr); return *mItem; }
197
198 /// @brief Return @c true if this iterator is not yet exhausted.
199
18/18
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 11 times.
✓ Branch 5 taken 10 times.
✓ Branch 6 taken 10 times.
✓ Branch 7 taken 10 times.
✓ Branch 8 taken 10 times.
✓ Branch 9 taken 10 times.
✓ Branch 10 taken 4 times.
✓ Branch 11 taken 3 times.
✓ Branch 12 taken 15 times.
✓ Branch 13 taken 14 times.
✓ Branch 14 taken 23 times.
✓ Branch 15 taken 14 times.
✓ Branch 16 taken 23 times.
✓ Branch 17 taken 14 times.
 228 operator bool() const { return mItem < mEnd; }
200
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 116 bool test() const { return mItem < mEnd; }
201
202 /// @brief Advance to the next item.
203
5/10
✗ Branch 0 not taken.
✓ Branch 1 taken 131 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✓ Branch 13 taken 1 times.
 133 IndexIterator& operator++() { assert(this->test()); ++mItem; return *this; }
204
205 /// @brief Advance to the next item.
206 bool next() { this->operator++(); return this->test(); }
207 bool increment() { this->next(); return this->test(); }
208
209 /// @brief Equality operators
210
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 bool operator==(const IndexIterator& other) const { return mItem == other.mItem; }
211
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 bool operator!=(const IndexIterator& other) const { return !this->operator==(other); }
212
213 private:
214 IndexType * const mBegin, * const mEnd;
215 IndexType * mItem;
216 }; // class PointPartitioner::IndexIterator
217
218
219 ////////////////////////////////////////
220 ////////////////////////////////////////
221
222 // Implementation details
223
224 /// @cond OPENVDB_DOCS_INTERNAL
225
226 namespace point_partitioner_internal {
227
228
229 template<typename PointIndexType>
230 struct ComputePointOrderOp
231 {
232 1670 ComputePointOrderOp(PointIndexType* pointOrder,
233 const PointIndexType* bucketCounters, const PointIndexType* bucketOffsets)
234 : mPointOrder(pointOrder)
235 , mBucketCounters(bucketCounters)
236 1670 , mBucketOffsets(bucketOffsets)
237 {
238 }
239
240 void operator()(const tbb::blocked_range<size_t>& range) const {
241
4/4
✓ Branch 0 taken 168492 times.
✓ Branch 1 taken 8998 times.
✓ Branch 2 taken 2494744 times.
✓ Branch 3 taken 89985 times.
 2762219 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
242 2663236 mPointOrder[n] += mBucketCounters[mBucketOffsets[n]];
243 }
244 }
245
246 PointIndexType * const mPointOrder;
247 PointIndexType const * const mBucketCounters;
248 PointIndexType const * const mBucketOffsets;
249 }; // struct ComputePointOrderOp
250
251
252 template<typename PointIndexType>
253 struct CreateOrderedPointIndexArrayOp
254 {
255 1670 CreateOrderedPointIndexArrayOp(PointIndexType* orderedIndexArray,
256 const PointIndexType* pointOrder, const PointIndexType* indices)
257 : mOrderedIndexArray(orderedIndexArray)
258 , mPointOrder(pointOrder)
259 1670 , mIndices(indices)
260 {
261 }
262
263 void operator()(const tbb::blocked_range<size_t>& range) const {
264
4/4
✓ Branch 0 taken 168707 times.
✓ Branch 1 taken 8974 times.
✓ Branch 2 taken 2494529 times.
✓ Branch 3 taken 89747 times.
 2761957 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
265 2663236 mOrderedIndexArray[mPointOrder[n]] = mIndices[n];
266 }
267 }
268
269 PointIndexType * const mOrderedIndexArray;
270 PointIndexType const * const mPointOrder;
271 PointIndexType const * const mIndices;
272 }; // struct CreateOrderedPointIndexArrayOp
273
274
275 template<typename PointIndexType, Index BucketLog2Dim>
276 struct VoxelOrderOp
277 {
278 static constexpr Index bits = 1 + (3 * BucketLog2Dim);
279 // signed, so if bits is exactly 16, int32 is required
280 using VoxelOffsetType = typename std::conditional<(bits < 16),
281 int16_t, typename std::conditional<(bits < 32), int32_t, int64_t>::type>::type;
282
283 using VoxelOffsetArray = std::unique_ptr<VoxelOffsetType[]>;
284 using IndexArray = std::unique_ptr<PointIndexType[]>;
285
286 ✗ VoxelOrderOp(IndexArray& indices, const IndexArray& pages,const VoxelOffsetArray& offsets)
287 : mIndices(indices.get())
288 , mPages(pages.get())
289 ✗ , mVoxelOffsets(offsets.get())
290 {
291 }
292
293 ✗ void operator()(const tbb::blocked_range<size_t>& range) const {
294
295 ✗ PointIndexType pointCount = 0;
296 ✗ for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
297 ✗ pointCount = std::max(pointCount, (mPages[n + 1] - mPages[n]));
298 }
299
300 const PointIndexType voxelCount = 1 << (3 * BucketLog2Dim);
301
302 // allocate histogram buffers
303 ✗ std::unique_ptr<VoxelOffsetType[]> offsets(new VoxelOffsetType[pointCount]);
304 ✗ std::unique_ptr<PointIndexType[]> sortedIndices(new PointIndexType[pointCount]);
305 ✗ std::unique_ptr<PointIndexType[]> histogram(new PointIndexType[voxelCount]);
306
307 ✗ for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
308
309 ✗ PointIndexType * const indices = mIndices + mPages[n];
310 ✗ pointCount = mPages[n + 1] - mPages[n];
311
312 // local copy of voxel offsets.
313 ✗ for (PointIndexType i = 0; i < pointCount; ++i) {
314 ✗ offsets[i] = mVoxelOffsets[ indices[i] ];
315 }
316
317 // reset histogram
318 ✗ memset(&histogram[0], 0, voxelCount * sizeof(PointIndexType));
319
320 // compute histogram
321 ✗ for (PointIndexType i = 0; i < pointCount; ++i) {
322 ✗ ++histogram[ offsets[i] ];
323 }
324
325 PointIndexType count = 0, startOffset;
326 ✗ for (int i = 0; i < int(voxelCount); ++i) {
327 ✗ if (histogram[i] > 0) {
328 startOffset = count;
329 ✗ count += histogram[i];
330 ✗ histogram[i] = startOffset;
331 }
332 }
333
334 // sort indices based on voxel offset
335 ✗ for (PointIndexType i = 0; i < pointCount; ++i) {
336 ✗ sortedIndices[ histogram[ offsets[i] ]++ ] = indices[i];
337 }
338
339 ✗ memcpy(&indices[0], &sortedIndices[0], sizeof(PointIndexType) * pointCount);
340 }
341 }
342
343 PointIndexType * const mIndices;
344 PointIndexType const * const mPages;
345 VoxelOffsetType const * const mVoxelOffsets;
346 }; // struct VoxelOrderOp
347
348
349 ////////////////////////////////////////
350
351
352 template<typename T>
353 3340 struct Array
354 {
355 using Ptr = std::unique_ptr<Array>;
356
357
1/2
✓ Branch 0 taken 3340 times.
✗ Branch 1 not taken.
 3340 Array(size_t size) : mSize(size), mData(new T[size]) { }
358
359
2/2
✓ Branch 0 taken 1319 times.
✓ Branch 1 taken 351 times.
 3340 size_t size() const { return mSize; }
360
361 T* data() { return mData.get(); }
362 const T* data() const { return mData.get(); }
363
364
1/2
✓ Branch 0 taken 1670 times.
✗ Branch 1 not taken.
 1670 void clear() { mSize = 0; mData.reset(); }
365
366 private:
367 size_t mSize;
368 std::unique_ptr<T[]> mData;
369 }; // struct Array
370
371
372 template<typename PointIndexType>
373 struct MoveSegmentDataOp
374 {
375 using SegmentPtr = typename Array<PointIndexType>::Ptr;
376
377
3/6
✓ Branch 1 taken 721 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
 732 MoveSegmentDataOp(std::vector<PointIndexType*>& indexLists, SegmentPtr* segments)
378 732 : mIndexLists(&indexLists[0]), mSegments(segments)
379 {
380 }
381
382 1231 void operator()(const tbb::blocked_range<size_t>& range) const {
383
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 1231 times.
 2901 for (size_t n(range.begin()), N(range.end()); n != N; ++n) {
384 1670 PointIndexType* indices = mIndexLists[n];
385 1670 SegmentPtr& segment = mSegments[n];
386
387
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 tbb::parallel_for(tbb::blocked_range<size_t>(0, segment->size()),
388 CopyData(indices, segment->data()));
389
390 segment.reset(); // clear data
391 }
392 1231 }
393
394 private:
395
396 struct CopyData
397 {
398 1670 CopyData(PointIndexType* lhs, const PointIndexType* rhs) : mLhs(lhs), mRhs(rhs) { }
399
400 void operator()(const tbb::blocked_range<size_t>& range) const {
401
4/4
✓ Branch 0 taken 164269 times.
✓ Branch 1 taken 8976 times.
✓ Branch 2 taken 2498967 times.
✓ Branch 3 taken 89805 times.
 2762017 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
402 2663236 mLhs[n] = mRhs[n];
403 }
404 }
405
406 PointIndexType * const mLhs;
407 PointIndexType const * const mRhs;
408 };
409
410 PointIndexType * const * const mIndexLists;
411 SegmentPtr * const mSegments;
412 }; // struct MoveSegmentDataOp
413
414
415 template<typename PointIndexType>
416 struct MergeBinsOp
417 {
418 using Segment = Array<PointIndexType>;
419 using SegmentPtr = typename Segment::Ptr;
420
421 using IndexPair = std::pair<PointIndexType, PointIndexType>;
422 using IndexPairList = std::deque<IndexPair>;
423 using IndexPairListPtr = std::shared_ptr<IndexPairList>;
424 using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
425 using IndexPairListMapPtr = std::shared_ptr<IndexPairListMap>;
426
427 732 MergeBinsOp(IndexPairListMapPtr* bins,
428 SegmentPtr* indexSegments,
429 SegmentPtr* offsetSegments,
430 Coord* coords,
431 size_t numSegments)
432 : mBins(bins)
433 , mIndexSegments(indexSegments)
434 , mOffsetSegments(offsetSegments)
435 , mCoords(coords)
436
3/6
✓ Branch 1 taken 721 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
 732 , mNumSegments(numSegments)
437 {
438 }
439
440 1217 void operator()(const tbb::blocked_range<size_t>& range) const {
441
442 std::vector<IndexPairListPtr*> data;
443 std::vector<PointIndexType> arrayOffsets;
444
445
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 1217 times.
 2887 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
446
447
2/2
✓ Branch 0 taken 453 times.
✓ Branch 1 taken 1217 times.
 1670 const Coord& ijk = mCoords[n];
448 size_t numIndices = 0;
449
450 data.clear();
451
452
2/2
✓ Branch 0 taken 5011 times.
✓ Branch 1 taken 1670 times.
 6681 for (size_t i = 0, I = mNumSegments; i < I; ++i) {
453
454 5011 IndexPairListMap& idxMap = *mBins[i];
455
2/2
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 2646 times.
 5011 typename IndexPairListMap::iterator iter = idxMap.find(ijk);
456
457
3/4
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 2646 times.
✓ Branch 2 taken 2365 times.
✗ Branch 3 not taken.
 5011 if (iter != idxMap.end() && iter->second) {
458 2365 IndexPairListPtr& idxListPtr = iter->second;
459
460
1/2
✓ Branch 1 taken 2365 times.
✗ Branch 2 not taken.
 2365 data.push_back(&idxListPtr);
461 2365 numIndices += idxListPtr->size();
462 }
463 }
464
465
2/4
✓ Branch 0 taken 1670 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1670 times.
✗ Branch 3 not taken.
 1670 if (data.empty() || numIndices == 0) continue;
466
467 1670 SegmentPtr& indexSegment = mIndexSegments[n];
468 1670 SegmentPtr& offsetSegment = mOffsetSegments[n];
469
470
2/4
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1670 times.
✗ Branch 5 not taken.
 1670 indexSegment.reset(new Segment(numIndices));
471
2/4
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1670 times.
✗ Branch 5 not taken.
 1670 offsetSegment.reset(new Segment(numIndices));
472
473 arrayOffsets.clear();
474
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 arrayOffsets.reserve(data.size());
475
476
2/2
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 1670 times.
 4035 for (size_t i = 0, count = 0, I = data.size(); i < I; ++i) {
477
1/2
✓ Branch 1 taken 2365 times.
✗ Branch 2 not taken.
 2365 arrayOffsets.push_back(PointIndexType(count));
478 2365 count += (*data[i])->size();
479 }
480
481
1/4
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1670 tbb::parallel_for(tbb::blocked_range<size_t>(0, data.size()),
482 CopyData(&data[0], &arrayOffsets[0], indexSegment->data(), offsetSegment->data()));
483 }
484 1217 }
485
486 private:
487
488 struct CopyData
489 {
490 1670 CopyData(IndexPairListPtr** indexLists,
491 const PointIndexType* arrayOffsets,
492 PointIndexType* indices,
493 PointIndexType* offsets)
494 : mIndexLists(indexLists)
495 , mArrayOffsets(arrayOffsets)
496 , mIndices(indices)
497
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 , mOffsets(offsets)
498 {
499 }
500
501 2365 void operator()(const tbb::blocked_range<size_t>& range) const {
502
503 using CIter = typename IndexPairList::const_iterator;
504
505
2/2
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 2365 times.
 4730 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
506
507 2365 const PointIndexType arrayOffset = mArrayOffsets[n];
508 2365 PointIndexType* indexPtr = &mIndices[arrayOffset];
509 2365 PointIndexType* offsetPtr = &mOffsets[arrayOffset];
510
511 2365 IndexPairListPtr& list = *mIndexLists[n];
512
513
2/2
✓ Branch 0 taken 2663236 times.
✓ Branch 1 taken 2365 times.
 2665601 for (CIter it = list->begin(), end = list->end(); it != end; ++it) {
514 const IndexPair& data = *it;
515 2663236 *indexPtr++ = data.first;
516
2/2
✓ Branch 0 taken 2622005 times.
✓ Branch 1 taken 41231 times.
 2663236 *offsetPtr++ = data.second;
517 }
518
519 list.reset(); // clear data
520 }
521 2365 }
522
523 IndexPairListPtr * const * const mIndexLists;
524 PointIndexType const * const mArrayOffsets;
525 PointIndexType * const mIndices;
526 PointIndexType * const mOffsets;
527 }; // struct CopyData
528
529 IndexPairListMapPtr * const mBins;
530 SegmentPtr * const mIndexSegments;
531 SegmentPtr * const mOffsetSegments;
532 Coord const * const mCoords;
533 size_t const mNumSegments;
534 }; // struct MergeBinsOp
535
536
537 template<typename PointArray, typename PointIndexType, typename VoxelOffsetType>
538
4/12
✓ Branch 4 taken 717 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✓ Branch 16 taken 9 times.
✗ Branch 17 not taken.
 1270 struct BinPointIndicesOp
539 {
540 using PosType = typename PointArray::PosType;
541 using IndexPair = std::pair<PointIndexType, PointIndexType>;
542 using IndexPairList = std::deque<IndexPair>;
543 using IndexPairListPtr = std::shared_ptr<IndexPairList>;
544 using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
545 using IndexPairListMapPtr = std::shared_ptr<IndexPairListMap>;
546
547 732 BinPointIndicesOp(IndexPairListMapPtr* data,
548 const PointArray& points,
549 VoxelOffsetType* voxelOffsets,
550 const math::Transform& m,
551 Index binLog2Dim,
552 Index bucketLog2Dim,
553 size_t numSegments,
554 bool cellCenteredTransform)
555 : mData(data)
556 , mPoints(&points)
557 , mVoxelOffsets(voxelOffsets)
558 , mXForm(m)
559 , mBinLog2Dim(binLog2Dim)
560 , mBucketLog2Dim(bucketLog2Dim)
561 , mNumSegments(numSegments)
562
6/12
✓ Branch 1 taken 721 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 721 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 9 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 9 times.
✗ Branch 17 not taken.
 732 , mCellCenteredTransform(cellCenteredTransform)
563 {
564 }
565
566 1326 void operator()(const tbb::blocked_range<size_t>& range) const {
567
568 1326 const Index log2dim = mBucketLog2Dim;
569 1326 const Index log2dim2 = 2 * log2dim;
570 1326 const Index bucketMask = (1u << log2dim) - 1u;
571
572 1326 const Index binLog2dim = mBinLog2Dim;
573 1326 const Index binLog2dim2 = 2 * binLog2dim;
574
575 1326 const Index binMask = (1u << (log2dim + binLog2dim)) - 1u;
576 const Index invBinMask = ~binMask;
577
578 IndexPairList * idxList = nullptr;
579 Coord ijk(0, 0, 0), loc(0, 0, 0), binCoord(0, 0, 0), lastBinCoord(1, 2, 3);
580 PosType pos;
581
582 PointIndexType bucketOffset = 0;
583 VoxelOffsetType voxelOffset = 0;
584
585 1326 const bool cellCentered = mCellCenteredTransform;
586
587 1326 const size_t numPoints = mPoints->size();
588 1326 const size_t segmentSize = numPoints / mNumSegments;
589
590
2/2
✓ Branch 0 taken 1270 times.
✓ Branch 1 taken 1270 times.
 2652 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
591
592
1/2
✓ Branch 0 taken 1270 times.
✗ Branch 1 not taken.
 1326 IndexPairListMapPtr& dataPtr = mData[n];
593
1/2
✓ Branch 0 taken 1270 times.
✗ Branch 1 not taken.
 1326 if (!dataPtr) dataPtr.reset(new IndexPairListMap());
594 IndexPairListMap& idxMap = *dataPtr;
595
596 1326 const bool isLastSegment = (n + 1) >= mNumSegments;
597
598 1326 const size_t start = n * segmentSize;
599
2/2
✓ Branch 0 taken 538 times.
✓ Branch 1 taken 732 times.
 1326 const size_t end = isLastSegment ? numPoints : (start + segmentSize);
600
601
2/2
✓ Branch 0 taken 1270 times.
✓ Branch 1 taken 2663240 times.
 4182599 for (size_t i = start; i != end; ++i) {
602
603
2/2
✓ Branch 0 taken 2663236 times.
✓ Branch 1 taken 4 times.
 4181273 mPoints->getPos(i, pos);
604
605
4/6
✓ Branch 0 taken 2663236 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2663236 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2663236 times.
✗ Branch 5 not taken.
 4181273 if (std::isfinite(pos[0]) && std::isfinite(pos[1]) && std::isfinite(pos[2])) {
606
2/6
✓ Branch 0 taken 2663236 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1401704 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 4181265 ijk = cellCentered ? mXForm.worldToIndexCellCentered(pos) :
607 mXForm.worldToIndexNodeCentered(pos);
608
609
2/2
✓ Branch 0 taken 2653121 times.
✓ Branch 1 taken 10115 times.
 4181265 if (mVoxelOffsets) {
610 4171150 loc[0] = ijk[0] & bucketMask;
611 4171150 loc[1] = ijk[1] & bucketMask;
612 4171150 loc[2] = ijk[2] & bucketMask;
613 4171150 voxelOffset = VoxelOffsetType(
614 4171150 (loc[0] << log2dim2) + (loc[1] << log2dim) + loc[2]);
615 }
616
617 4181265 binCoord[0] = ijk[0] & invBinMask;
618 4181265 binCoord[1] = ijk[1] & invBinMask;
619 4181265 binCoord[2] = ijk[2] & invBinMask;
620
621 4181265 ijk[0] &= binMask;
622 4181265 ijk[1] &= binMask;
623 4181265 ijk[2] &= binMask;
624
625 4181265 ijk[0] >>= log2dim;
626 4181265 ijk[1] >>= log2dim;
627 4181265 ijk[2] >>= log2dim;
628
629 bucketOffset = PointIndexType(
630
2/2
✓ Branch 0 taken 2653266 times.
✓ Branch 1 taken 9970 times.
 4181265 (ijk[0] << binLog2dim2) + (ijk[1] << binLog2dim) + ijk[2]);
631
632 if (lastBinCoord != binCoord) {
633 34405 lastBinCoord = binCoord;
634 34405 IndexPairListPtr& idxListPtr = idxMap[lastBinCoord];
635
2/2
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 16896 times.
 37765 if (!idxListPtr) idxListPtr.reset(new IndexPairList());
636 idxList = idxListPtr.get();
637 }
638
639 4181265 idxList->push_back(IndexPair(PointIndexType(i), bucketOffset));
640
2/2
✓ Branch 0 taken 2653121 times.
✓ Branch 1 taken 10115 times.
 4181265 if (mVoxelOffsets) mVoxelOffsets[i] = voxelOffset;
641 }
642 }
643 }
644 1326 }
645
646 IndexPairListMapPtr * const mData;
647 PointArray const * const mPoints;
648 VoxelOffsetType * const mVoxelOffsets;
649 math::Transform const mXForm;
650 Index const mBinLog2Dim;
651 Index const mBucketLog2Dim;
652 size_t const mNumSegments;
653 bool const mCellCenteredTransform;
654 }; // struct BinPointIndicesOp
655
656
657 template<typename PointIndexType>
658 struct OrderSegmentsOp
659 {
660 using IndexArray = std::unique_ptr<PointIndexType[]>;
661 using SegmentPtr = typename Array<PointIndexType>::Ptr;
662
663 732 OrderSegmentsOp(SegmentPtr* indexSegments, SegmentPtr* offsetSegments,
664 IndexArray* pageOffsetArrays, IndexArray* pageIndexArrays, Index binVolume)
665 : mIndexSegments(indexSegments)
666 , mOffsetSegments(offsetSegments)
667 , mPageOffsetArrays(pageOffsetArrays)
668 , mPageIndexArrays(pageIndexArrays)
669 732 , mBinVolume(binVolume)
670 {
671 }
672
673 1212 void operator()(const tbb::blocked_range<size_t>& range) const {
674
675 1212 const size_t bucketCountersSize = size_t(mBinVolume);
676 1212 IndexArray bucketCounters(new PointIndexType[bucketCountersSize]);
677
678 1212 size_t maxSegmentSize = 0;
679
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 1212 times.
 2882 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
680
2/2
✓ Branch 0 taken 1319 times.
✓ Branch 1 taken 351 times.
 2989 maxSegmentSize = std::max(maxSegmentSize, mIndexSegments[n]->size());
681 }
682
683
2/4
✓ Branch 0 taken 1212 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1212 times.
✗ Branch 4 not taken.
 1212 IndexArray bucketIndices(new PointIndexType[maxSegmentSize]);
684
685
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 1212 times.
 2882 for (size_t n = range.begin(), N = range.end(); n != N; ++n) {
686
687 1670 memset(bucketCounters.get(), 0, sizeof(PointIndexType) * bucketCountersSize);
688
689 1670 const size_t segmentSize = mOffsetSegments[n]->size();
690 PointIndexType* offsets = mOffsetSegments[n]->data();
691
692 // Count the number of points per bucket and assign a local bucket index
693 // to each point.
694
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 2663236 times.
 2664906 for (size_t i = 0; i < segmentSize; ++i) {
695 2663236 bucketIndices[i] = bucketCounters[offsets[i]]++;
696 }
697
698 PointIndexType nonemptyBucketCount = 0;
699
2/2
✓ Branch 0 taken 54722560 times.
✓ Branch 1 taken 1670 times.
 54724230 for (size_t i = 0; i < bucketCountersSize; ++i) {
700 54722560 nonemptyBucketCount += static_cast<PointIndexType>(bucketCounters[i] != 0);
701 }
702
703
704 1670 IndexArray& pageOffsets = mPageOffsetArrays[n];
705
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 pageOffsets.reset(new PointIndexType[nonemptyBucketCount + 1]);
706 1670 pageOffsets[0] = nonemptyBucketCount + 1; // stores array size in first element
707
708 1670 IndexArray& pageIndices = mPageIndexArrays[n];
709
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 pageIndices.reset(new PointIndexType[nonemptyBucketCount]);
710
711 // Compute bucket counter prefix sum
712 PointIndexType count = 0, idx = 0;
713
2/2
✓ Branch 0 taken 54722560 times.
✓ Branch 1 taken 1670 times.
 54724230 for (size_t i = 0; i < bucketCountersSize; ++i) {
714
2/2
✓ Branch 0 taken 44744 times.
✓ Branch 1 taken 54677816 times.
 54722560 if (bucketCounters[i] != 0) {
715 44744 pageIndices[idx] = static_cast<PointIndexType>(i);
716 44744 pageOffsets[idx+1] = bucketCounters[i];
717 44744 bucketCounters[i] = count;
718 44744 count += pageOffsets[idx+1];
719 ++idx;
720 }
721 }
722
723
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 PointIndexType* indices = mIndexSegments[n]->data();
724 const tbb::blocked_range<size_t> segmentRange(0, segmentSize);
725
726 // Compute final point order by incrementing the local bucket point index
727 // with the prefix sum offset.
728
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 1670 tbb::parallel_for(segmentRange, ComputePointOrderOp<PointIndexType>(
729 bucketIndices.get(), bucketCounters.get(), offsets));
730
731
1/4
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1670 tbb::parallel_for(segmentRange, CreateOrderedPointIndexArrayOp<PointIndexType>(
732 offsets, bucketIndices.get(), indices));
733
734
1/2
✓ Branch 0 taken 1670 times.
✗ Branch 1 not taken.
 1670 mIndexSegments[n]->clear(); // clear data
735 }
736 1212 }
737
738 SegmentPtr * const mIndexSegments;
739 SegmentPtr * const mOffsetSegments;
740 IndexArray * const mPageOffsetArrays;
741 IndexArray * const mPageIndexArrays;
742 Index const mBinVolume;
743 }; // struct OrderSegmentsOp
744
745
746 ////////////////////////////////////////
747
748
749 /// @brief Segment points using one level of least significant digit radix bins.
750 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
751 747 inline void binAndSegment(
752 const PointArray& points,
753 const math::Transform& xform,
754 std::unique_ptr<typename Array<PointIndexType>::Ptr[]>& indexSegments,
755 std::unique_ptr<typename Array<PointIndexType>::Ptr[]>& offsetSegments,
756 std::vector<Coord>& coords,
757 const Index binLog2Dim,
758 const Index bucketLog2Dim,
759 VoxelOffsetType* voxelOffsets = nullptr,
760 bool cellCenteredTransform = true)
761 {
762 using IndexPair = std::pair<PointIndexType, PointIndexType>;
763 using IndexPairList = std::deque<IndexPair>;
764 using IndexPairListPtr = std::shared_ptr<IndexPairList>;
765 using IndexPairListMap = std::map<Coord, IndexPairListPtr>;
766 using IndexPairListMapPtr = std::shared_ptr<IndexPairListMap>;
767
768
2/2
✓ Branch 0 taken 660 times.
✓ Branch 1 taken 72 times.
 747 size_t numTasks = 1, numThreads = size_t(tbb::this_task_arena::max_concurrency());
769
2/2
✓ Branch 0 taken 660 times.
✓ Branch 1 taken 72 times.
 747 if (points.size() > (numThreads * 2)) numTasks = numThreads * 2;
770
2/2
✓ Branch 0 taken 322 times.
✓ Branch 1 taken 338 times.
 662 else if (points.size() > numThreads) numTasks = numThreads;
771
772
3/4
✓ Branch 0 taken 394 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1270 times.
✓ Branch 4 taken 732 times.
 2073 std::unique_ptr<IndexPairListMapPtr[]> bins(new IndexPairListMapPtr[numTasks]);
773
774 using BinOp = BinPointIndicesOp<PointArray, PointIndexType, VoxelOffsetType>;
775
776
2/8
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
 1494 tbb::parallel_for(tbb::blocked_range<size_t>(0, numTasks),
777 BinOp(bins.get(), points, voxelOffsets, xform, binLog2Dim, bucketLog2Dim,
778 numTasks, cellCenteredTransform));
779
780 std::set<Coord> uniqueCoords;
781
782
2/2
✓ Branch 0 taken 1270 times.
✓ Branch 1 taken 732 times.
 2073 for (size_t i = 0; i < numTasks; ++i) {
783 IndexPairListMap& idxMap = *bins[i];
784
2/2
✓ Branch 0 taken 2365 times.
✓ Branch 1 taken 1270 times.
 4686 for (typename IndexPairListMap::iterator it = idxMap.begin(); it != idxMap.end(); ++it) {
785
1/2
✓ Branch 1 taken 2365 times.
✗ Branch 2 not taken.
 3360 uniqueCoords.insert(it->first);
786 }
787 }
788
789 747 coords.assign(uniqueCoords.begin(), uniqueCoords.end());
790 uniqueCoords.clear();
791
792 size_t segmentCount = coords.size();
793
794 using SegmentPtr = typename Array<PointIndexType>::Ptr;
795
796
4/6
✓ Branch 0 taken 732 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1670 times.
✓ Branch 6 taken 732 times.
 3197 indexSegments.reset(new SegmentPtr[segmentCount]);
797
3/4
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1670 times.
✓ Branch 4 taken 732 times.
 3197 offsetSegments.reset(new SegmentPtr[segmentCount]);
798
799 using MergeOp = MergeBinsOp<PointIndexType>;
800
801
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 tbb::parallel_for(tbb::blocked_range<size_t>(0, segmentCount),
802 MergeOp(bins.get(), indexSegments.get(), offsetSegments.get(), &coords[0], numTasks));
803 747 }
804
805
806 template<typename PointIndexType, typename VoxelOffsetType, typename PointArray>
807 747 inline void partition(
808 const PointArray& points,
809 const math::Transform& xform,
810 const Index bucketLog2Dim,
811 std::unique_ptr<PointIndexType[]>& pointIndices,
812 std::unique_ptr<PointIndexType[]>& pageOffsets,
813 std::unique_ptr<Coord[]>& pageCoordinates,
814 PointIndexType& pageCount,
815 std::unique_ptr<VoxelOffsetType[]>& voxelOffsets,
816 bool recordVoxelOffsets,
817 bool cellCenteredTransform)
818 {
819 using SegmentPtr = typename Array<PointIndexType>::Ptr;
820
821
3/4
✓ Branch 0 taken 719 times.
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 719 times.
✗ Branch 3 not taken.
 747 if (recordVoxelOffsets) voxelOffsets.reset(new VoxelOffsetType[points.size()]);
822 else voxelOffsets.reset();
823
824
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 const Index binLog2Dim = 5u;
825 // note: Bins span a (2^(binLog2Dim + bucketLog2Dim))^3 voxel region,
826 // i.e. bucketLog2Dim = 3 and binLog2Dim = 5 corresponds to a
827 // (2^8)^3 = 256^3 voxel region.
828
829
830 std::vector<Coord> segmentCoords;
831
832 747 std::unique_ptr<SegmentPtr[]> indexSegments;
833 747 std::unique_ptr<SegmentPtr[]> offsetSegments;
834
835
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 binAndSegment<PointIndexType, VoxelOffsetType, PointArray>(points, xform,
836 indexSegments, offsetSegments, segmentCoords, binLog2Dim, bucketLog2Dim,
837 voxelOffsets.get(), cellCenteredTransform);
838
839 size_t numSegments = segmentCoords.size();
840
841 const tbb::blocked_range<size_t> segmentRange(0, numSegments);
842
843 using IndexArray = std::unique_ptr<PointIndexType[]>;
844
4/6
✓ Branch 0 taken 732 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1670 times.
✓ Branch 6 taken 732 times.
 3197 std::unique_ptr<IndexArray[]> pageOffsetArrays(new IndexArray[numSegments]);
845
3/4
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1670 times.
✓ Branch 4 taken 732 times.
 3197 std::unique_ptr<IndexArray[]> pageIndexArrays(new IndexArray[numSegments]);
846
847 const Index binVolume = 1u << (3u * binLog2Dim);
848
849
2/6
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 747 tbb::parallel_for(segmentRange, OrderSegmentsOp<PointIndexType>
850 (indexSegments.get(), offsetSegments.get(),
851 pageOffsetArrays.get(), pageIndexArrays.get(), binVolume));
852
853 indexSegments.reset();
854
855 std::vector<Index> segmentOffsets;
856
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 segmentOffsets.reserve(numSegments);
857
858 747 pageCount = 0;
859
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 732 times.
 3197 for (size_t n = 0; n < numSegments; ++n) {
860
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 2450 segmentOffsets.push_back(pageCount);
861 2450 pageCount += pageOffsetArrays[n][0] - 1;
862 }
863
864
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 pageOffsets.reset(new PointIndexType[pageCount + 1]);
865
866 PointIndexType count = 0;
867
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 732 times.
 3197 for (size_t n = 0, idx = 0; n < numSegments; ++n) {
868
869 PointIndexType* offsets = pageOffsetArrays[n].get();
870 2450 size_t size = size_t(offsets[0]);
871
872
2/2
✓ Branch 0 taken 44744 times.
✓ Branch 1 taken 1670 times.
 78422 for (size_t i = 1; i < size; ++i) {
873 75972 pageOffsets[idx++] = count;
874 75972 count += offsets[i];
875 }
876 }
877
878
1/2
✓ Branch 0 taken 732 times.
✗ Branch 1 not taken.
 747 pageOffsets[pageCount] = count;
879
880
2/4
✓ Branch 0 taken 732 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
 747 pointIndices.reset(new PointIndexType[points.size()]);
881
882 std::vector<PointIndexType*> indexArray;
883
1/2
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
 747 indexArray.reserve(numSegments);
884
885 747 PointIndexType* index = pointIndices.get();
886
2/2
✓ Branch 0 taken 1670 times.
✓ Branch 1 taken 732 times.
 3197 for (size_t n = 0; n < numSegments; ++n) {
887
1/2
✓ Branch 1 taken 1670 times.
✗ Branch 2 not taken.
 2450 indexArray.push_back(index);
888 2450 index += offsetSegments[n]->size();
889 }
890
891 // compute leaf node origin for each page
892
893
3/4
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44744 times.
✓ Branch 4 taken 732 times.
 76719 pageCoordinates.reset(new Coord[pageCount]);
894
895
2/4
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 732 times.
✗ Branch 5 not taken.
 747 tbb::parallel_for(segmentRange,
896 2882 [&](tbb::blocked_range<size_t>& range)
897 {
898
6/6
✓ Branch 0 taken 916 times.
✓ Branch 1 taken 916 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 742 times.
✓ Branch 5 taken 284 times.
 2882 for (size_t n = range.begin(); n < range.end(); n++)
899 {
900 1670 Index segmentOffset = segmentOffsets[n];
901 1670 PointIndexType* indices = pageIndexArrays[n].get();
902
903 const Coord& segmentCoord = segmentCoords[n];
904
905 // segment size stored in the first value of the offset array
906 1670 const size_t segmentSize = pageOffsetArrays[n][0] - 1;
907 tbb::blocked_range<size_t> copyRange(0, segmentSize);
908 1670 tbb::parallel_for(copyRange,
909 32296 [&](tbb::blocked_range<size_t>& r)
910 {
911
6/6
✓ Branch 0 taken 16372 times.
✓ Branch 1 taken 8288 times.
✓ Branch 2 taken 1761 times.
✓ Branch 3 taken 913 times.
✓ Branch 4 taken 26611 times.
✓ Branch 5 taken 23095 times.
 77040 for (size_t i = r.begin(); i < r.end(); i++)
912 {
913 44744 Index pageIndex = indices[i];
914 44744 Coord& ijk = pageCoordinates[segmentOffset+i];
915
916 44744 ijk[0] = pageIndex >> (2 * binLog2Dim);
917 44744 Index pageIndexModulo = pageIndex - (ijk[0] << (2 * binLog2Dim));
918 44744 ijk[1] = pageIndexModulo >> binLog2Dim;
919 44744 ijk[2] = pageIndexModulo - (ijk[1] << binLog2Dim);
920
921 44744 ijk = (ijk << bucketLog2Dim) + segmentCoord;
922 }
923 }
924 );
925 }
926 }
927 );
928
929 // move segment data
930
931
2/6
✓ Branch 1 taken 732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 732 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 747 tbb::parallel_for(segmentRange,
932 MoveSegmentDataOp<PointIndexType>(indexArray, offsetSegments.get()));
933 747 }
934
935
936 } // namespace point_partitioner_internal
937
938 /// @endcond
939
940 ////////////////////////////////////////
941
942
943 template<typename PointIndexType, Index BucketLog2Dim>
944
4/8
✓ Branch 1 taken 711 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 5 times.
✗ Branch 11 not taken.
 732 inline PointPartitioner<PointIndexType, BucketLog2Dim>::PointPartitioner()
945 : mPointIndices(nullptr)
946 , mVoxelOffsets(nullptr)
947 , mPageOffsets(nullptr)
948 , mPageCoordinates(nullptr)
949 , mPageCount(0)
950
4/8
✓ Branch 1 taken 711 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 5 times.
✗ Branch 11 not taken.
 732 , mUsingCellCenteredTransform(true)
951 {
952 }
953
954
955 template<typename PointIndexType, Index BucketLog2Dim>
956 inline void
957 PointPartitioner<PointIndexType, BucketLog2Dim>::clear()
958 {
959 mPageCount = 0;
960 mUsingCellCenteredTransform = true;
961 mPointIndices.reset();
962 mVoxelOffsets.reset();
963 mPageOffsets.reset();
964 mPageCoordinates.reset();
965 }
966
967
968 template<typename PointIndexType, Index BucketLog2Dim>
969 inline void
970 PointPartitioner<PointIndexType, BucketLog2Dim>::swap(PointPartitioner& rhs)
971 {
972 const IndexType tmpLhsPageCount = mPageCount;
973 mPageCount = rhs.mPageCount;
974 rhs.mPageCount = tmpLhsPageCount;
975
976 mPointIndices.swap(rhs.mPointIndices);
977 mVoxelOffsets.swap(rhs.mVoxelOffsets);
978 mPageOffsets.swap(rhs.mPageOffsets);
979 mPageCoordinates.swap(rhs.mPageCoordinates);
980
981 bool lhsCellCenteredTransform = mUsingCellCenteredTransform;
982 mUsingCellCenteredTransform = rhs.mUsingCellCenteredTransform;
983 rhs.mUsingCellCenteredTransform = lhsCellCenteredTransform;
984 }
985
986
987 template<typename PointIndexType, Index BucketLog2Dim>
988 inline typename PointPartitioner<PointIndexType, BucketLog2Dim>::IndexIterator
989
1/2
✓ Branch 0 taken 86895 times.
✗ Branch 1 not taken.
 86895 PointPartitioner<PointIndexType, BucketLog2Dim>::indices(size_t n) const
990 {
991
2/4
✓ Branch 0 taken 86895 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 86895 times.
 86895 assert(bool(mPointIndices) && bool(mPageCount));
992 return IndexIterator(
993 86895 mPointIndices.get() + mPageOffsets[n],
994 86895 mPointIndices.get() + mPageOffsets[n + 1]);
995 }
996
997
998 template<typename PointIndexType, Index BucketLog2Dim>
999 template<typename PointArray>
1000 inline void
1001 747 PointPartitioner<PointIndexType, BucketLog2Dim>::construct(
1002 const PointArray& points,
1003 const math::Transform& xform,
1004 bool voxelOrder,
1005 bool recordVoxelOffsets,
1006 bool cellCenteredTransform)
1007 {
1008 747 mUsingCellCenteredTransform = cellCenteredTransform;
1009
1010 747 point_partitioner_internal::partition(points, xform, BucketLog2Dim,
1011 747 mPointIndices, mPageOffsets, mPageCoordinates, mPageCount, mVoxelOffsets,
1012 747 (voxelOrder || recordVoxelOffsets), cellCenteredTransform);
1013
1014
2/2
✓ Branch 0 taken 719 times.
✓ Branch 1 taken 13 times.
 747 const tbb::blocked_range<size_t> pageRange(0, mPageCount);
1015
1016
3/4
✓ Branch 0 taken 719 times.
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 719 times.
 747 if (mVoxelOffsets && voxelOrder) {
1017 ✗ tbb::parallel_for(pageRange, point_partitioner_internal::VoxelOrderOp<
1018 IndexType, BucketLog2Dim>(mPointIndices, mPageOffsets, mVoxelOffsets));
1019 }
1020
1021
3/4
✓ Branch 0 taken 719 times.
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 719 times.
 747 if (mVoxelOffsets && !recordVoxelOffsets) {
1022 mVoxelOffsets.reset();
1023 }
1024 747 }
1025
1026
1027 template<typename PointIndexType, Index BucketLog2Dim>
1028 template<typename PointArray>
1029 inline typename PointPartitioner<PointIndexType, BucketLog2Dim>::Ptr
1030 1 PointPartitioner<PointIndexType, BucketLog2Dim>::create(
1031 const PointArray& points,
1032 const math::Transform& xform,
1033 bool voxelOrder,
1034 bool recordVoxelOffsets,
1035 bool cellCenteredTransform)
1036 {
1037 1 Ptr ret(new PointPartitioner());
1038
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 ret->construct(points, xform, voxelOrder, recordVoxelOffsets, cellCenteredTransform);
1039 1 return ret;
1040 }
1041
1042
1043 ////////////////////////////////////////
1044
1045
1046 } // namespace tools
1047 } // namespace OPENVDB_VERSION_NAME
1048 } // namespace openvdb
1049
1050
1051 #endif // OPENVDB_TOOLS_POINT_PARTITIONER_HAS_BEEN_INCLUDED
1052