1
2 //
3 // This source file is part of appleseed.
4 // Visit https://appleseedhq.net/ for additional information and resources.
5 //
6 // This software is released under the MIT license.
7 //
8 // Copyright (c) 2010-2013 Francois Beaune, Jupiter Jazz Limited
9 // Copyright (c) 2014-2018 Francois Beaune, The appleseedhq Organization
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining a copy
12 // of this software and associated documentation files (the "Software"), to deal
13 // in the Software without restriction, including without limitation the rights
14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 // copies of the Software, and to permit persons to whom the Software is
16 // furnished to do so, subject to the following conditions:
17 //
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
20 //
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 // THE SOFTWARE.
28 //
29
30 #pragma once
31
32 // appleseed.foundation headers.
33 #include "foundation/core/concepts/noncopyable.h"
34 #include "foundation/math/aabb.h"
35 #include "foundation/math/bvh/bvh_bboxsortpredicate.h"
36 #include "foundation/math/scalar.h"
37 #include "foundation/math/split.h"
38 #include "foundation/platform/types.h"
39
40 // Standard headers.
41 #include <algorithm>
42 #include <cassert>
43 #include <cstddef>
44 #include <limits>
45 #include <vector>
46
47 namespace foundation {
48 namespace bvh {
49
50 //
51 // A partitioner implementing the SBVH algorithm (use with foundation::bvh::SpatialBuilder).
52 //
53 // Reference:
54 //
55 // http://www.nvidia.com/docs/IO/77714/sbvh.pdf
56 //
57 // The ItemHandler class must conform to the following prototype:
58 //
59 // class ItemHandler
60 // : public foundation::NonCopyable
61 // {
62 // public:
63 // ValueType get_bbox_grow_eps() const;
64 //
65 // AABBType clip(
66 // const size_t item_index,
67 // const size_t dimension,
68 // const ValueType slab_min,
69 // const ValueType slab_max) const;
70 //
71 // bool intersect(
72 // const size_t item_index,
73 // const AABBType& bbox) const;
74 // };
75 //
76
77 // When defined, additional costly correctness checks are enabled (only in Debug).
78 #undef FOUNDATION_SBVH_DEEPCHECK
79
80 template <typename ItemHandler, typename AABBVector>
81 class SBVHPartitioner
82 : public foundation::NonCopyable
83 {
84 public:
85 typedef AABBVector AABBVectorType;
86 typedef typename AABBVectorType::value_type AABBType;
87 typedef typename AABBType::ValueType ValueType;
88 static const size_t Dimension = AABBType::Dimension;
89
90 struct LeafType
91 {
92 std::vector<size_t> m_indices[Dimension];
93
sizeLeafType94 size_t size() const
95 {
96 return m_indices[0].size();
97 }
98 };
99
100 // Constructor.
101 SBVHPartitioner(
102 ItemHandler& item_handler,
103 const AABBVectorType& bboxes,
104 const size_t max_leaf_size = 1,
105 const size_t bin_count = 64,
106 const ValueType interior_node_traversal_cost = ValueType(1.0),
107 const ValueType item_intersection_cost = ValueType(1.0));
108
109 // Create the root leaf of the tree. Ownership of the leaf is passed to the caller.
110 LeafType* create_root_leaf() const;
111
112 // Compute the bounding box of a given leaf.
113 AABBType compute_leaf_bbox(const LeafType& leaf) const;
114
115 // Split a leaf. Return true if the split should be split or false if it should be kept unsplit.
116 bool split(
117 LeafType& leaf,
118 const AABBType& leaf_bbox,
119 LeafType& left_leaf,
120 AABBType& left_leaf_bbox,
121 LeafType& right_leaf,
122 AABBType& right_leaf_bbox);
123
124 // Store a leaf. Return the index of the first stored item.
125 size_t store(const LeafType& leaf);
126
127 // Return the items ordering.
128 const std::vector<size_t>& get_item_ordering() const;
129
130 // Split counters.
131 size_t get_spatial_split_count() const;
132 size_t get_object_split_count() const;
133
134 private:
135 typedef Split<ValueType> SplitType;
136
137 struct Bin
138 {
139 AABBType m_bin_bbox; // bbox of this bin
140 AABBType m_left_bbox; // bbox of all the bins to the left of this one
141 size_t m_entry_counter; // number of items that begin in this bin
142 size_t m_exit_counter; // number of items that end in this bin
143 };
144
145 ItemHandler& m_item_handler;
146 const AABBVectorType& m_bboxes;
147 const size_t m_max_leaf_size;
148 const size_t m_bin_count;
149 const ValueType m_rcp_bin_count;
150 const ValueType m_interior_node_traversal_cost;
151 const ValueType m_item_intersection_cost;
152
153 ValueType m_root_bbox_rcp_sa;
154 std::vector<AABBType> m_left_bboxes;
155 std::vector<Bin> m_bins;
156 std::vector<uint8> m_tags;
157 std::vector<size_t> m_final_indices;
158
159 size_t m_spatial_split_count;
160 size_t m_object_split_count;
161
162 void compute_root_bbox_surface_area();
163
164 ValueType compute_final_split_cost(
165 const AABBType& bbox,
166 const double cost) const;
167
168 // Find the best object split for a given set of items.
169 void find_object_split(
170 LeafType& leaf,
171 const AABBType& leaf_bbox,
172 AABBType& left_leaf_bbox,
173 AABBType& right_leaf_bbox,
174 size_t& best_split_dim,
175 size_t& best_split_pivot,
176 ValueType& best_split_cost);
177
178 // Find the best spatial split for a given set of items.
179 void find_spatial_split(
180 const LeafType& leaf,
181 const AABBType& leaf_bbox,
182 AABBType& left_leaf_bbox,
183 AABBType& right_leaf_bbox,
184 SplitType& best_split,
185 ValueType& best_split_cost);
186
187 // Sort a set of items into two subsets according to a given object split.
188 void object_sort(
189 LeafType& leaf,
190 const size_t split_dim,
191 const size_t split_pivot,
192 const AABBType& left_leaf_bbox,
193 const AABBType& right_leaf_bbox,
194 LeafType& left_leaf,
195 LeafType& right_leaf);
196
197 // Sort a set of items into two subsets according to a given spatial split.
198 void spatial_sort(
199 const LeafType& leaf,
200 const SplitType& split,
201 const AABBType& left_leaf_bbox,
202 const AABBType& right_leaf_bbox,
203 LeafType& left_leaf,
204 LeafType& right_leaf) const;
205 };
206
207
208 //
209 // SBVHPartitioner class implementation.
210 //
211
212 template <typename ItemHandler, typename AABBVector>
SBVHPartitioner(ItemHandler & item_handler,const AABBVectorType & bboxes,const size_t max_leaf_size,const size_t bin_count,const ValueType interior_node_traversal_cost,const ValueType item_intersection_cost)213 SBVHPartitioner<ItemHandler, AABBVector>::SBVHPartitioner(
214 ItemHandler& item_handler,
215 const AABBVectorType& bboxes,
216 const size_t max_leaf_size,
217 const size_t bin_count,
218 const ValueType interior_node_traversal_cost,
219 const ValueType item_intersection_cost)
220 : m_item_handler(item_handler)
221 , m_bboxes(bboxes)
222 , m_max_leaf_size(max_leaf_size)
223 , m_bin_count(bin_count)
224 , m_rcp_bin_count(ValueType(1.0) / bin_count)
225 , m_interior_node_traversal_cost(interior_node_traversal_cost)
226 , m_item_intersection_cost(item_intersection_cost)
227 , m_left_bboxes(bboxes.size() > 1 ? bboxes.size() - 1 : 0)
228 , m_bins(bin_count)
229 , m_tags(bboxes.size())
230 , m_spatial_split_count(0)
231 , m_object_split_count(0)
232 {
233 compute_root_bbox_surface_area();
234 }
235
236 template <typename ItemHandler, typename AABBVector>
create_root_leaf()237 typename SBVHPartitioner<ItemHandler, AABBVector>::LeafType* SBVHPartitioner<ItemHandler, AABBVector>::create_root_leaf() const
238 {
239 LeafType* leaf = new LeafType();
240
241 const size_t size = m_bboxes.size();
242
243 for (size_t d = 0; d < Dimension; ++d)
244 {
245 std::vector<size_t>& indices = leaf->m_indices[d];
246
247 // Identity ordering.
248 indices.resize(size);
249 for (size_t i = 0; i < size; ++i)
250 indices[i] = i;
251
252 // Sort the items according to their bounding boxes.
253 StableBboxSortPredicate<AABBVectorType> predicate(m_bboxes, d);
254 std::sort(indices.begin(), indices.end(), predicate);
255 }
256
257 return leaf;
258 }
259
260 template <typename ItemHandler, typename AABBVector>
compute_leaf_bbox(const LeafType & leaf)261 typename AABBVector::value_type SBVHPartitioner<ItemHandler, AABBVector>::compute_leaf_bbox(const LeafType& leaf) const
262 {
263 AABBType bbox;
264 bbox.invalidate();
265
266 const std::vector<size_t>& indices = leaf.m_indices[0];
267 const size_t size = indices.size();
268
269 for (size_t i = 0; i < size; ++i)
270 bbox.insert(m_bboxes[indices[i]]);
271
272 return bbox;
273 }
274
275 template <typename ItemHandler, typename AABBVector>
split(LeafType & leaf,const AABBType & leaf_bbox,LeafType & left_leaf,AABBType & left_leaf_bbox,LeafType & right_leaf,AABBType & right_leaf_bbox)276 bool SBVHPartitioner<ItemHandler, AABBVector>::split(
277 LeafType& leaf,
278 const AABBType& leaf_bbox,
279 LeafType& left_leaf,
280 AABBType& left_leaf_bbox,
281 LeafType& right_leaf,
282 AABBType& right_leaf_bbox)
283 {
284 assert(!leaf_bbox.is_valid() || leaf_bbox.rank() >= Dimension - 1);
285
286 #ifdef FOUNDATION_SBVH_DEEPCHECK
287 // Make sure every item intersects the leaf it belongs to.
288 for (size_t i = 0; i < leaf.m_indices[0].size(); ++i)
289 {
290 const size_t item_index = leaf.m_indices[0][i];
291 const AABBType& item_bbox = m_bboxes[item_index];
292 assert(AABBType::overlap(item_bbox, leaf_bbox));
293 }
294 #endif
295
296 // Don't split leaves with less than two items.
297 if (leaf.m_indices[0].size() < 2)
298 return false;
299
300 // Find the best object split.
301 AABBType object_split_left_bbox;
302 AABBType object_split_right_bbox;
303 size_t object_split_dim;
304 size_t object_split_pivot;
305 ValueType object_split_cost = std::numeric_limits<ValueType>::max();
306 find_object_split(
307 leaf,
308 leaf_bbox,
309 object_split_left_bbox,
310 object_split_right_bbox,
311 object_split_dim,
312 object_split_pivot,
313 object_split_cost);
314
315 // Don't try to find a spatial split if the object split is good enough.
316 bool do_find_spatial_split = true;
317 if (object_split_cost < std::numeric_limits<ValueType>::max())
318 {
319 const AABBType overlap_bbox =
320 AABBType::intersect(object_split_left_bbox, object_split_right_bbox);
321 if (!overlap_bbox.is_valid())
322 do_find_spatial_split = false;
323 else
324 {
325 const ValueType overlap_sa = surface_area(overlap_bbox);
326 const ValueType overlap_factor = overlap_sa * m_root_bbox_rcp_sa;
327 const ValueType Alpha = ValueType(1.0e-4);
328 if (overlap_factor <= Alpha)
329 do_find_spatial_split = false;
330 }
331 }
332
333 // Find the best spatial split.
334 AABBType spatial_split_left_bbox;
335 AABBType spatial_split_right_bbox;
336 SplitType spatial_split;
337 ValueType spatial_split_cost = std::numeric_limits<ValueType>::max();
338 if (do_find_spatial_split)
339 {
340 find_spatial_split(
341 leaf,
342 leaf_bbox,
343 spatial_split_left_bbox,
344 spatial_split_right_bbox,
345 spatial_split,
346 spatial_split_cost);
347 }
348
349 // Compute the cost of keeping the leaf unsplit.
350 const ValueType leaf_cost = leaf.size() * m_item_intersection_cost;
351
352 // Select the cheapest option.
353 if (leaf_cost <= object_split_cost && leaf_cost <= spatial_split_cost)
354 {
355 // Don't split, make a leaf.
356 return false;
357 }
358 else if (object_split_cost <= spatial_split_cost)
359 {
360 // Perform the object split.
361 left_leaf_bbox = object_split_left_bbox;
362 right_leaf_bbox = object_split_right_bbox;
363 object_sort(
364 leaf,
365 object_split_dim,
366 object_split_pivot,
367 left_leaf_bbox,
368 right_leaf_bbox,
369 left_leaf,
370 right_leaf);
371 ++m_object_split_count;
372 return true;
373 }
374 else
375 {
376 // Perform the spatial split.
377 left_leaf_bbox = spatial_split_left_bbox;
378 right_leaf_bbox = spatial_split_right_bbox;
379 spatial_sort(
380 leaf,
381 spatial_split,
382 left_leaf_bbox,
383 right_leaf_bbox,
384 left_leaf,
385 right_leaf);
386 ++m_spatial_split_count;
387 return true;
388 }
389 }
390
391 template <typename ItemHandler, typename AABBVector>
compute_root_bbox_surface_area()392 void SBVHPartitioner<ItemHandler, AABBVector>::compute_root_bbox_surface_area()
393 {
394 AABBType root_bbox;
395 root_bbox.invalidate();
396
397 const size_t size = m_bboxes.size();
398
399 for (size_t i = 0; i < size; ++i)
400 root_bbox.insert(m_bboxes[i]);
401
402 m_root_bbox_rcp_sa =
403 size > 0
404 ? ValueType(1.0) / surface_area(root_bbox)
405 : ValueType(0.0);
406 }
407
408 template <typename ItemHandler, typename AABBVector>
compute_final_split_cost(const AABBType & bbox,const double cost)409 inline typename AABBVector::value_type::ValueType SBVHPartitioner<ItemHandler, AABBVector>::compute_final_split_cost(
410 const AABBType& bbox,
411 const double cost) const
412 {
413 assert(bbox.is_valid());
414
415 if (!(cost < std::numeric_limits<ValueType>::max()))
416 return cost;
417
418 const ValueType bbox_half_surface_area = half_surface_area(bbox);
419
420 assert(bbox_half_surface_area > ValueType(0.0));
421
422 return
423 m_interior_node_traversal_cost +
424 m_item_intersection_cost * (cost / bbox_half_surface_area);
425 }
426
427 template <typename ItemHandler, typename AABBVector>
find_object_split(LeafType & leaf,const AABBType & leaf_bbox,AABBType & left_leaf_bbox,AABBType & right_leaf_bbox,size_t & best_split_dim,size_t & best_split_pivot,ValueType & best_split_cost)428 void SBVHPartitioner<ItemHandler, AABBVector>::find_object_split(
429 LeafType& leaf,
430 const AABBType& leaf_bbox,
431 AABBType& left_leaf_bbox,
432 AABBType& right_leaf_bbox,
433 size_t& best_split_dim,
434 size_t& best_split_pivot,
435 ValueType& best_split_cost)
436 {
437 for (size_t d = 0; d < Dimension; ++d)
438 {
439 const std::vector<size_t>& indices = leaf.m_indices[d];
440 const size_t item_count = indices.size();
441
442 AABBType bbox_accumulator;
443
444 // Left-to-right sweep to accumulate bounding boxes and compute their surface area.
445 bbox_accumulator.invalidate();
446 for (size_t i = 0; i < item_count - 1; ++i)
447 {
448 const size_t item_index = indices[i];
449 const AABBType& item_bbox = m_bboxes[item_index];
450 const AABBType clipped_item_bbox = AABBType::intersect(item_bbox, leaf_bbox);
451 assert(clipped_item_bbox.is_valid());
452 bbox_accumulator.insert(clipped_item_bbox);
453 m_left_bboxes[i] = bbox_accumulator;
454 }
455
456 // Right-to-left sweep to accumulate bounding boxes, compute their surface area find the best partition.
457 bbox_accumulator.invalidate();
458 for (size_t i = item_count - 1; i > 0; --i)
459 {
460 // Compute right bounding box.
461 const size_t item_index = indices[i];
462 const AABBType& item_bbox = m_bboxes[item_index];
463 const AABBType clipped_item_bbox = AABBType::intersect(item_bbox, leaf_bbox);
464 assert(clipped_item_bbox.is_valid());
465 bbox_accumulator.insert(clipped_item_bbox);
466
467 // Compute the cost of this partition.
468 const ValueType left_cost = half_surface_area(m_left_bboxes[i - 1]) * i;
469 const ValueType right_cost = half_surface_area(bbox_accumulator) * (item_count - i);
470 const ValueType split_cost = left_cost + right_cost;
471
472 // Keep track of the partition with the lowest cost.
473 if (best_split_cost > split_cost)
474 {
475 best_split_cost = split_cost;
476 best_split_dim = d;
477 best_split_pivot = i;
478 left_leaf_bbox = m_left_bboxes[i - 1];
479 right_leaf_bbox = bbox_accumulator;
480 }
481 }
482 }
483
484 best_split_cost = compute_final_split_cost(leaf_bbox, best_split_cost);
485 }
486
487 template <typename ItemHandler, typename AABBVector>
find_spatial_split(const LeafType & leaf,const AABBType & leaf_bbox,AABBType & left_leaf_bbox,AABBType & right_leaf_bbox,SplitType & best_split,ValueType & best_split_cost)488 void SBVHPartitioner<ItemHandler, AABBVector>::find_spatial_split(
489 const LeafType& leaf,
490 const AABBType& leaf_bbox,
491 AABBType& left_leaf_bbox,
492 AABBType& right_leaf_bbox,
493 SplitType& best_split,
494 ValueType& best_split_cost)
495 {
496 for (size_t d = 0; d < Dimension; ++d)
497 {
498 const std::vector<size_t>& indices = leaf.m_indices[d];
499 const size_t item_count = indices.size();
500
501 // Compute the extent of the leaf in the splitting dimension.
502 const ValueType bbox_min = leaf_bbox.min[d];
503 const ValueType bbox_max = leaf_bbox.max[d];
504 const ValueType bbox_extent = bbox_max - bbox_min;
505 const ValueType rcp_bin_size = m_bin_count / bbox_extent;
506
507 // This node is flat in this dimension.
508 if (bbox_extent == ValueType(0.0))
509 continue;
510
511 // Clear the bins.
512 for (size_t i = 0; i < m_bin_count; ++i)
513 {
514 Bin& bin = m_bins[i];
515 bin.m_bin_bbox.invalidate();
516 bin.m_entry_counter = 0;
517 bin.m_exit_counter = 0;
518 }
519
520 // Push the items through the bins.
521 for (size_t i = 0; i < item_count; ++i)
522 {
523 // Compute the extent of this item in the splitting dimension.
524 const size_t item_index = indices[i];
525 const AABBType& item_bbox = m_bboxes[item_index];
526 const ValueType item_bbox_min = item_bbox.min[d];
527 const ValueType item_bbox_max = item_bbox.max[d];
528 assert(item_bbox_min <= bbox_max && item_bbox_max >= bbox_min);
529
530 // Find the range of bins covered by this item.
531 const size_t begin_bin =
532 item_bbox_min > bbox_min
533 ? std::min<size_t>(truncate<size_t>((item_bbox_min - bbox_min) * rcp_bin_size), m_bin_count - 1)
534 : 0;
535 const size_t end_bin =
536 std::min<size_t>(truncate<size_t>((item_bbox_max - bbox_min) * rcp_bin_size), m_bin_count - 1);
537 assert(begin_bin < m_bin_count);
538 assert(end_bin < m_bin_count);
539 assert(begin_bin <= end_bin);
540
541 // Update the bins that this item overlaps.
542 for (size_t b = begin_bin; b <= end_bin; ++b)
543 {
544 // Compute the bounds of this bin.
545 const ValueType bin_min = lerp(bbox_min, bbox_max, (b + 0) * m_rcp_bin_count);
546 const ValueType bin_max = lerp(bbox_min, bbox_max, (b + 1) * m_rcp_bin_count);
547
548 // Clip the item against the bin boundaries.
549 const AABBType item_clipped_bbox =
550 m_item_handler.clip(
551 item_index,
552 d,
553 bin_min,
554 bin_max);
555 assert(item_clipped_bbox.is_valid());
556
557 // Grow the bounding box associated with this bin.
558 m_bins[b].m_bin_bbox.insert(item_clipped_bbox);
559 }
560
561 // Update the enter/leave counters.
562 ++m_bins[begin_bin].m_entry_counter;
563 ++m_bins[end_bin].m_exit_counter;
564 }
565
566 AABBType bbox_accumulator;
567
568 // Left-to-right sweep to compute the left bounding boxes.
569 bbox_accumulator = m_bins[0].m_bin_bbox;
570 for (size_t i = 1; i < m_bin_count; ++i)
571 {
572 Bin& bin = m_bins[i];
573 bin.m_left_bbox = bbox_accumulator;
574 bbox_accumulator.insert(bin.m_bin_bbox);
575 }
576
577 // Right-to-left sweep to compute the right bounding boxes and find the best split.
578 size_t left_item_count = item_count;
579 size_t right_item_count = 0;
580 bbox_accumulator.invalidate();
581 for (size_t i = m_bin_count - 1; i > 0; --i)
582 {
583 const Bin& bin = m_bins[i];
584
585 // Compute the right bounding box.
586 bbox_accumulator.insert(bin.m_bin_bbox);
587
588 // We need to have items on both the left and right sides.
589 if (!bin.m_left_bbox.is_valid() || !bbox_accumulator.is_valid())
590 continue;
591
592 // Update the item counters.
593 assert(left_item_count >= bin.m_entry_counter);
594 left_item_count -= bin.m_entry_counter;
595 right_item_count += bin.m_exit_counter;
596
597 // Compute the cost of this split.
598 const ValueType left_cost = half_surface_area(bin.m_left_bbox) * left_item_count;
599 const ValueType right_cost = half_surface_area(bbox_accumulator) * right_item_count;
600 const ValueType split_cost = left_cost + right_cost;
601
602 // Keep track of the partition with the lowest cost.
603 if (best_split_cost > split_cost)
604 {
605 best_split_cost = split_cost;
606 best_split.m_dimension = d;
607 best_split.m_abscissa = bbox_accumulator.min[d];
608 left_leaf_bbox = bin.m_left_bbox;
609 right_leaf_bbox = bbox_accumulator;
610 }
611 }
612 }
613
614 best_split_cost = compute_final_split_cost(leaf_bbox, best_split_cost);
615
616 if (best_split_cost < std::numeric_limits<ValueType>::max())
617 {
618 // In the case of a spatial split, the bounding boxes of the child nodes must be disjoint.
619 assert(AABBType::intersect(left_leaf_bbox, right_leaf_bbox).rank() < Dimension);
620 }
621 }
622
623 template <typename ItemHandler, typename AABBVector>
object_sort(LeafType & leaf,const size_t split_dim,const size_t split_pivot,const AABBType & left_leaf_bbox,const AABBType & right_leaf_bbox,LeafType & left_leaf,LeafType & right_leaf)624 void SBVHPartitioner<ItemHandler, AABBVector>::object_sort(
625 LeafType& leaf,
626 const size_t split_dim,
627 const size_t split_pivot,
628 const AABBType& left_leaf_bbox,
629 const AABBType& right_leaf_bbox,
630 LeafType& left_leaf,
631 LeafType& right_leaf)
632 {
633 const std::vector<size_t>& split_indices = leaf.m_indices[split_dim];
634 const size_t size = split_indices.size();
635
636 enum { Left = 0, Right = 1 };
637
638 for (size_t i = 0; i < split_pivot; ++i)
639 m_tags[split_indices[i]] = Left;
640
641 for (size_t i = split_pivot; i < size; ++i)
642 m_tags[split_indices[i]] = Right;
643
644 for (size_t d = 0; d < Dimension; ++d)
645 {
646 left_leaf.m_indices[d].resize(split_pivot);
647 right_leaf.m_indices[d].resize(size - split_pivot);
648
649 if (d == split_dim)
650 {
651 for (size_t i = 0; i < split_pivot; ++i)
652 {
653 const size_t item_index = leaf.m_indices[d][i];
654
655 #ifdef FOUNDATION_SBVH_DEEPCHECK
656 assert(AABBType::overlap(m_bboxes[item_index], left_leaf_bbox));
657 #endif
658
659 left_leaf.m_indices[d][i] = item_index;
660 }
661
662 for (size_t i = split_pivot; i < size; ++i)
663 {
664 const size_t item_index = leaf.m_indices[d][i];
665
666 #ifdef FOUNDATION_SBVH_DEEPCHECK
667 assert(AABBType::overlap(m_bboxes[item_index], right_leaf_bbox));
668 #endif
669
670 right_leaf.m_indices[d][i - split_pivot] = item_index;
671 }
672 }
673 else
674 {
675 size_t left = 0;
676 size_t right = 0;
677
678 for (size_t i = 0; i < size; ++i)
679 {
680 const size_t item_index = leaf.m_indices[d][i];
681
682 if (m_tags[item_index] == Left)
683 {
684 assert(left < split_pivot);
685 left_leaf.m_indices[d][left++] = item_index;
686 }
687 else
688 {
689 assert(right < size - split_pivot);
690 right_leaf.m_indices[d][right++] = item_index;
691 }
692 }
693
694 assert(left == split_pivot);
695 assert(right == size - split_pivot);
696 }
697 }
698 }
699
700 template <typename ItemHandler, typename AABBVector>
spatial_sort(const LeafType & leaf,const SplitType & split,const AABBType & left_leaf_bbox,const AABBType & right_leaf_bbox,LeafType & left_leaf,LeafType & right_leaf)701 void SBVHPartitioner<ItemHandler, AABBVector>::spatial_sort(
702 const LeafType& leaf,
703 const SplitType& split,
704 const AABBType& left_leaf_bbox,
705 const AABBType& right_leaf_bbox,
706 LeafType& left_leaf,
707 LeafType& right_leaf) const
708 {
709 // Prevent numerical instabilities by slightly enlarging the left and right bounding boxes.
710 const ValueType eps = m_item_handler.get_bbox_grow_eps();
711 AABBType enlarged_left_bbox(left_leaf_bbox);
712 AABBType enlarged_right_bbox(right_leaf_bbox);
713 enlarged_left_bbox.robust_grow(eps);
714 enlarged_right_bbox.robust_grow(eps);
715
716 const size_t item_count = leaf.size();
717
718 for (size_t i = 0; i < item_count; ++i)
719 {
720 const size_t item_index = leaf.m_indices[split.m_dimension][i];
721 const AABBType& item_bbox = m_bboxes[item_index];
722
723 if (item_bbox.max[split.m_dimension] <= split.m_abscissa)
724 {
725 #ifdef FOUNDATION_SBVH_DEEPCHECK
726 assert(AABBType::overlap(item_bbox, left_leaf_bbox));
727 #endif
728 left_leaf.m_indices[split.m_dimension].push_back(item_index);
729 }
730 else if (item_bbox.min[split.m_dimension] >= split.m_abscissa)
731 {
732 #ifdef FOUNDATION_SBVH_DEEPCHECK
733 assert(AABBType::overlap(item_bbox, right_leaf_bbox));
734 #endif
735 right_leaf.m_indices[split.m_dimension].push_back(item_index);
736 }
737 else
738 {
739 const bool in_left = m_item_handler.intersect(item_index, enlarged_left_bbox);
740 const bool in_right = !in_left || m_item_handler.intersect(item_index, enlarged_right_bbox);
741
742 assert(in_left || in_right);
743
744 if (in_left)
745 left_leaf.m_indices[split.m_dimension].push_back(item_index);
746
747 if (in_right)
748 right_leaf.m_indices[split.m_dimension].push_back(item_index);
749 }
750 }
751
752 // Basic check to make sure we didn't loose any items.
753 assert(
754 left_leaf.m_indices[split.m_dimension].size() +
755 right_leaf.m_indices[split.m_dimension].size() >=
756 leaf.m_indices[split.m_dimension].size());
757
758 // Unlike object splits, spatial splits break items orderings, so we need to sort
759 // again the items in the left and right leaf nodes, along all dimensions.
760 for (size_t d = 0; d < Dimension; ++d)
761 {
762 if (d != split.m_dimension)
763 {
764 left_leaf.m_indices[d] = left_leaf.m_indices[split.m_dimension];
765 right_leaf.m_indices[d] = right_leaf.m_indices[split.m_dimension];
766
767 // Sort the items according to their bounding boxes.
768 StableBboxSortPredicate<AABBVectorType> predicate(m_bboxes, d);
769 std::sort(left_leaf.m_indices[d].begin(), left_leaf.m_indices[d].end(), predicate);
770 std::sort(right_leaf.m_indices[d].begin(), right_leaf.m_indices[d].end(), predicate);
771 }
772 }
773 }
774
775 template <typename ItemHandler, typename AABBVector>
store(const LeafType & leaf)776 inline size_t SBVHPartitioner<ItemHandler, AABBVector>::store(const LeafType& leaf)
777 {
778 const size_t first = m_final_indices.size();
779
780 const std::vector<size_t>& indices = leaf.m_indices[0];
781 const size_t size = indices.size();
782
783 for (size_t i = 0; i < size; ++i)
784 m_final_indices.push_back(indices[i]);
785
786 return first;
787 }
788
789 template <typename ItemHandler, typename AABBVector>
get_item_ordering()790 inline const std::vector<size_t>& SBVHPartitioner<ItemHandler, AABBVector>::get_item_ordering() const
791 {
792 return m_final_indices;
793 }
794
795 template <typename ItemHandler, typename AABBVector>
get_spatial_split_count()796 inline size_t SBVHPartitioner<ItemHandler, AABBVector>::get_spatial_split_count() const
797 {
798 return m_spatial_split_count;
799 }
800
801 template <typename ItemHandler, typename AABBVector>
get_object_split_count()802 inline size_t SBVHPartitioner<ItemHandler, AABBVector>::get_object_split_count() const
803 {
804 return m_object_split_count;
805 }
806
807 } // namespace bvh
808 } // namespace foundation
809