1 /*
2 * Adapted from code copyright 2009-2010 NVIDIA Corporation
3 * Modifications Copyright 2011, Blender Foundation.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "bvh/bvh_split.h"
19
20 #include "bvh/bvh_build.h"
21 #include "bvh/bvh_sort.h"
22
23 #include "render/hair.h"
24 #include "render/mesh.h"
25 #include "render/object.h"
26
27 #include "util/util_algorithm.h"
28
29 CCL_NAMESPACE_BEGIN
30
31 /* Object Split */
32
BVHObjectSplit(BVHBuild * builder,BVHSpatialStorage * storage,const BVHRange & range,vector<BVHReference> & references,float nodeSAH,const BVHUnaligned * unaligned_heuristic,const Transform * aligned_space)33 BVHObjectSplit::BVHObjectSplit(BVHBuild *builder,
34 BVHSpatialStorage *storage,
35 const BVHRange &range,
36 vector<BVHReference> &references,
37 float nodeSAH,
38 const BVHUnaligned *unaligned_heuristic,
39 const Transform *aligned_space)
40 : sah(FLT_MAX),
41 dim(0),
42 num_left(0),
43 left_bounds(BoundBox::empty),
44 right_bounds(BoundBox::empty),
45 storage_(storage),
46 references_(&references),
47 unaligned_heuristic_(unaligned_heuristic),
48 aligned_space_(aligned_space)
49 {
50 const BVHReference *ref_ptr = &references_->at(range.start());
51 float min_sah = FLT_MAX;
52
53 storage_->right_bounds.resize(range.size());
54
55 for (int dim = 0; dim < 3; dim++) {
56 /* Sort references. */
57 bvh_reference_sort(range.start(),
58 range.end(),
59 &references_->at(0),
60 dim,
61 unaligned_heuristic_,
62 aligned_space_);
63
64 /* sweep right to left and determine bounds. */
65 BoundBox right_bounds = BoundBox::empty;
66 for (int i = range.size() - 1; i > 0; i--) {
67 BoundBox prim_bounds = get_prim_bounds(ref_ptr[i]);
68 right_bounds.grow(prim_bounds);
69 storage_->right_bounds[i - 1] = right_bounds;
70 }
71
72 /* sweep left to right and select lowest SAH. */
73 BoundBox left_bounds = BoundBox::empty;
74
75 for (int i = 1; i < range.size(); i++) {
76 BoundBox prim_bounds = get_prim_bounds(ref_ptr[i - 1]);
77 left_bounds.grow(prim_bounds);
78 right_bounds = storage_->right_bounds[i - 1];
79
80 float sah = nodeSAH + left_bounds.safe_area() * builder->params.primitive_cost(i) +
81 right_bounds.safe_area() * builder->params.primitive_cost(range.size() - i);
82
83 if (sah < min_sah) {
84 min_sah = sah;
85
86 this->sah = sah;
87 this->dim = dim;
88 this->num_left = i;
89 this->left_bounds = left_bounds;
90 this->right_bounds = right_bounds;
91 }
92 }
93 }
94 }
95
split(BVHRange & left,BVHRange & right,const BVHRange & range)96 void BVHObjectSplit::split(BVHRange &left, BVHRange &right, const BVHRange &range)
97 {
98 assert(references_->size() > 0);
99 /* sort references according to split */
100 bvh_reference_sort(range.start(),
101 range.end(),
102 &references_->at(0),
103 this->dim,
104 unaligned_heuristic_,
105 aligned_space_);
106
107 BoundBox effective_left_bounds, effective_right_bounds;
108 const int num_right = range.size() - this->num_left;
109 if (aligned_space_ == NULL) {
110 effective_left_bounds = left_bounds;
111 effective_right_bounds = right_bounds;
112 }
113 else {
114 effective_left_bounds = BoundBox::empty;
115 effective_right_bounds = BoundBox::empty;
116 for (int i = 0; i < this->num_left; ++i) {
117 BoundBox prim_boundbox = references_->at(range.start() + i).bounds();
118 effective_left_bounds.grow(prim_boundbox);
119 }
120 for (int i = 0; i < num_right; ++i) {
121 BoundBox prim_boundbox = references_->at(range.start() + this->num_left + i).bounds();
122 effective_right_bounds.grow(prim_boundbox);
123 }
124 }
125
126 /* split node ranges */
127 left = BVHRange(effective_left_bounds, range.start(), this->num_left);
128 right = BVHRange(effective_right_bounds, left.end(), num_right);
129 }
130
131 /* Spatial Split */
132
BVHSpatialSplit(const BVHBuild & builder,BVHSpatialStorage * storage,const BVHRange & range,vector<BVHReference> & references,float nodeSAH,const BVHUnaligned * unaligned_heuristic,const Transform * aligned_space)133 BVHSpatialSplit::BVHSpatialSplit(const BVHBuild &builder,
134 BVHSpatialStorage *storage,
135 const BVHRange &range,
136 vector<BVHReference> &references,
137 float nodeSAH,
138 const BVHUnaligned *unaligned_heuristic,
139 const Transform *aligned_space)
140 : sah(FLT_MAX),
141 dim(0),
142 pos(0.0f),
143 storage_(storage),
144 references_(&references),
145 unaligned_heuristic_(unaligned_heuristic),
146 aligned_space_(aligned_space)
147 {
148 /* initialize bins. */
149 BoundBox range_bounds;
150 if (aligned_space == NULL) {
151 range_bounds = range.bounds();
152 }
153 else {
154 range_bounds = unaligned_heuristic->compute_aligned_boundbox(
155 range, &references_->at(0), *aligned_space);
156 }
157
158 float3 origin = range_bounds.min;
159 float3 binSize = (range_bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
160 float3 invBinSize = 1.0f / binSize;
161
162 for (int dim = 0; dim < 3; dim++) {
163 for (int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) {
164 BVHSpatialBin &bin = storage_->bins[dim][i];
165
166 bin.bounds = BoundBox::empty;
167 bin.enter = 0;
168 bin.exit = 0;
169 }
170 }
171
172 /* chop references into bins. */
173 for (unsigned int refIdx = range.start(); refIdx < range.end(); refIdx++) {
174 const BVHReference &ref = references_->at(refIdx);
175 BoundBox prim_bounds = get_prim_bounds(ref);
176 float3 firstBinf = (prim_bounds.min - origin) * invBinSize;
177 float3 lastBinf = (prim_bounds.max - origin) * invBinSize;
178 int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z);
179 int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z);
180
181 firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1);
182 lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1);
183
184 for (int dim = 0; dim < 3; dim++) {
185 BVHReference currRef(
186 get_prim_bounds(ref), ref.prim_index(), ref.prim_object(), ref.prim_type());
187
188 for (int i = firstBin[dim]; i < lastBin[dim]; i++) {
189 BVHReference leftRef, rightRef;
190
191 split_reference(
192 builder, leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1));
193 storage_->bins[dim][i].bounds.grow(leftRef.bounds());
194 currRef = rightRef;
195 }
196
197 storage_->bins[dim][lastBin[dim]].bounds.grow(currRef.bounds());
198 storage_->bins[dim][firstBin[dim]].enter++;
199 storage_->bins[dim][lastBin[dim]].exit++;
200 }
201 }
202
203 /* select best split plane. */
204 storage_->right_bounds.resize(BVHParams::NUM_SPATIAL_BINS);
205 for (int dim = 0; dim < 3; dim++) {
206 /* sweep right to left and determine bounds. */
207 BoundBox right_bounds = BoundBox::empty;
208 for (int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) {
209 right_bounds.grow(storage_->bins[dim][i].bounds);
210 storage_->right_bounds[i - 1] = right_bounds;
211 }
212
213 /* sweep left to right and select lowest SAH. */
214 BoundBox left_bounds = BoundBox::empty;
215 int leftNum = 0;
216 int rightNum = range.size();
217
218 for (int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) {
219 left_bounds.grow(storage_->bins[dim][i - 1].bounds);
220 leftNum += storage_->bins[dim][i - 1].enter;
221 rightNum -= storage_->bins[dim][i - 1].exit;
222
223 float sah = nodeSAH + left_bounds.safe_area() * builder.params.primitive_cost(leftNum) +
224 storage_->right_bounds[i - 1].safe_area() *
225 builder.params.primitive_cost(rightNum);
226
227 if (sah < this->sah) {
228 this->sah = sah;
229 this->dim = dim;
230 this->pos = origin[dim] + binSize[dim] * (float)i;
231 }
232 }
233 }
234 }
235
split(BVHBuild * builder,BVHRange & left,BVHRange & right,const BVHRange & range)236 void BVHSpatialSplit::split(BVHBuild *builder,
237 BVHRange &left,
238 BVHRange &right,
239 const BVHRange &range)
240 {
241 /* Categorize references and compute bounds.
242 *
243 * Left-hand side: [left_start, left_end[
244 * Uncategorized/split: [left_end, right_start[
245 * Right-hand side: [right_start, refs.size()[ */
246
247 vector<BVHReference> &refs = *references_;
248 int left_start = range.start();
249 int left_end = left_start;
250 int right_start = range.end();
251 int right_end = range.end();
252 BoundBox left_bounds = BoundBox::empty;
253 BoundBox right_bounds = BoundBox::empty;
254
255 for (int i = left_end; i < right_start; i++) {
256 BoundBox prim_bounds = get_prim_bounds(refs[i]);
257 if (prim_bounds.max[this->dim] <= this->pos) {
258 /* entirely on the left-hand side */
259 left_bounds.grow(prim_bounds);
260 swap(refs[i], refs[left_end++]);
261 }
262 else if (prim_bounds.min[this->dim] >= this->pos) {
263 /* entirely on the right-hand side */
264 right_bounds.grow(prim_bounds);
265 swap(refs[i--], refs[--right_start]);
266 }
267 }
268
269 /* Duplicate or unsplit references intersecting both sides.
270 *
271 * Duplication happens into a temporary pre-allocated vector in order to
272 * reduce number of memmove() calls happening in vector.insert().
273 */
274 vector<BVHReference> &new_refs = storage_->new_references;
275 new_refs.clear();
276 new_refs.reserve(right_start - left_end);
277 while (left_end < right_start) {
278 /* split reference. */
279 BVHReference curr_ref(get_prim_bounds(refs[left_end]),
280 refs[left_end].prim_index(),
281 refs[left_end].prim_object(),
282 refs[left_end].prim_type());
283 BVHReference lref, rref;
284 split_reference(*builder, lref, rref, curr_ref, this->dim, this->pos);
285
286 /* compute SAH for duplicate/unsplit candidates. */
287 BoundBox lub = left_bounds; // Unsplit to left: new left-hand bounds.
288 BoundBox rub = right_bounds; // Unsplit to right: new right-hand bounds.
289 BoundBox ldb = left_bounds; // Duplicate: new left-hand bounds.
290 BoundBox rdb = right_bounds; // Duplicate: new right-hand bounds.
291
292 lub.grow(curr_ref.bounds());
293 rub.grow(curr_ref.bounds());
294 ldb.grow(lref.bounds());
295 rdb.grow(rref.bounds());
296
297 float lac = builder->params.primitive_cost(left_end - left_start);
298 float rac = builder->params.primitive_cost(right_end - right_start);
299 float lbc = builder->params.primitive_cost(left_end - left_start + 1);
300 float rbc = builder->params.primitive_cost(right_end - right_start + 1);
301
302 float unsplitLeftSAH = lub.safe_area() * lbc + right_bounds.safe_area() * rac;
303 float unsplitRightSAH = left_bounds.safe_area() * lac + rub.safe_area() * rbc;
304 float duplicateSAH = ldb.safe_area() * lbc + rdb.safe_area() * rbc;
305 float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH);
306
307 if (minSAH == unsplitLeftSAH) {
308 /* unsplit to left */
309 left_bounds = lub;
310 left_end++;
311 }
312 else if (minSAH == unsplitRightSAH) {
313 /* unsplit to right */
314 right_bounds = rub;
315 swap(refs[left_end], refs[--right_start]);
316 }
317 else {
318 /* duplicate */
319 left_bounds = ldb;
320 right_bounds = rdb;
321 refs[left_end++] = lref;
322 new_refs.push_back(rref);
323 right_end++;
324 }
325 }
326 /* Insert duplicated references into actual array in one go. */
327 if (new_refs.size() != 0) {
328 refs.insert(refs.begin() + (right_end - new_refs.size()), new_refs.begin(), new_refs.end());
329 }
330 if (aligned_space_ != NULL) {
331 left_bounds = right_bounds = BoundBox::empty;
332 for (int i = left_start; i < left_end - left_start; ++i) {
333 BoundBox prim_boundbox = references_->at(i).bounds();
334 left_bounds.grow(prim_boundbox);
335 }
336 for (int i = right_start; i < right_end - right_start; ++i) {
337 BoundBox prim_boundbox = references_->at(i).bounds();
338 right_bounds.grow(prim_boundbox);
339 }
340 }
341 left = BVHRange(left_bounds, left_start, left_end - left_start);
342 right = BVHRange(right_bounds, right_start, right_end - right_start);
343 }
344
split_triangle_primitive(const Mesh * mesh,const Transform * tfm,int prim_index,int dim,float pos,BoundBox & left_bounds,BoundBox & right_bounds)345 void BVHSpatialSplit::split_triangle_primitive(const Mesh *mesh,
346 const Transform *tfm,
347 int prim_index,
348 int dim,
349 float pos,
350 BoundBox &left_bounds,
351 BoundBox &right_bounds)
352 {
353 Mesh::Triangle t = mesh->get_triangle(prim_index);
354 const float3 *verts = &mesh->verts[0];
355 float3 v1 = tfm ? transform_point(tfm, verts[t.v[2]]) : verts[t.v[2]];
356 v1 = get_unaligned_point(v1);
357
358 for (int i = 0; i < 3; i++) {
359 float3 v0 = v1;
360 int vindex = t.v[i];
361 v1 = tfm ? transform_point(tfm, verts[vindex]) : verts[vindex];
362 v1 = get_unaligned_point(v1);
363 float v0p = v0[dim];
364 float v1p = v1[dim];
365
366 /* insert vertex to the boxes it belongs to. */
367 if (v0p <= pos)
368 left_bounds.grow(v0);
369
370 if (v0p >= pos)
371 right_bounds.grow(v0);
372
373 /* edge intersects the plane => insert intersection to both boxes. */
374 if ((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
375 float3 t = lerp(v0, v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
376 left_bounds.grow(t);
377 right_bounds.grow(t);
378 }
379 }
380 }
381
split_curve_primitive(const Hair * hair,const Transform * tfm,int prim_index,int segment_index,int dim,float pos,BoundBox & left_bounds,BoundBox & right_bounds)382 void BVHSpatialSplit::split_curve_primitive(const Hair *hair,
383 const Transform *tfm,
384 int prim_index,
385 int segment_index,
386 int dim,
387 float pos,
388 BoundBox &left_bounds,
389 BoundBox &right_bounds)
390 {
391 /* curve split: NOTE - Currently ignores curve width and needs to be fixed.*/
392 Hair::Curve curve = hair->get_curve(prim_index);
393 const int k0 = curve.first_key + segment_index;
394 const int k1 = k0 + 1;
395 float3 v0 = hair->curve_keys[k0];
396 float3 v1 = hair->curve_keys[k1];
397
398 if (tfm != NULL) {
399 v0 = transform_point(tfm, v0);
400 v1 = transform_point(tfm, v1);
401 }
402 v0 = get_unaligned_point(v0);
403 v1 = get_unaligned_point(v1);
404
405 float v0p = v0[dim];
406 float v1p = v1[dim];
407
408 /* insert vertex to the boxes it belongs to. */
409 if (v0p <= pos)
410 left_bounds.grow(v0);
411
412 if (v0p >= pos)
413 right_bounds.grow(v0);
414
415 if (v1p <= pos)
416 left_bounds.grow(v1);
417
418 if (v1p >= pos)
419 right_bounds.grow(v1);
420
421 /* edge intersects the plane => insert intersection to both boxes. */
422 if ((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
423 float3 t = lerp(v0, v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
424 left_bounds.grow(t);
425 right_bounds.grow(t);
426 }
427 }
428
split_triangle_reference(const BVHReference & ref,const Mesh * mesh,int dim,float pos,BoundBox & left_bounds,BoundBox & right_bounds)429 void BVHSpatialSplit::split_triangle_reference(const BVHReference &ref,
430 const Mesh *mesh,
431 int dim,
432 float pos,
433 BoundBox &left_bounds,
434 BoundBox &right_bounds)
435 {
436 split_triangle_primitive(mesh, NULL, ref.prim_index(), dim, pos, left_bounds, right_bounds);
437 }
438
split_curve_reference(const BVHReference & ref,const Hair * hair,int dim,float pos,BoundBox & left_bounds,BoundBox & right_bounds)439 void BVHSpatialSplit::split_curve_reference(const BVHReference &ref,
440 const Hair *hair,
441 int dim,
442 float pos,
443 BoundBox &left_bounds,
444 BoundBox &right_bounds)
445 {
446 split_curve_primitive(hair,
447 NULL,
448 ref.prim_index(),
449 PRIMITIVE_UNPACK_SEGMENT(ref.prim_type()),
450 dim,
451 pos,
452 left_bounds,
453 right_bounds);
454 }
455
split_object_reference(const Object * object,int dim,float pos,BoundBox & left_bounds,BoundBox & right_bounds)456 void BVHSpatialSplit::split_object_reference(
457 const Object *object, int dim, float pos, BoundBox &left_bounds, BoundBox &right_bounds)
458 {
459 Geometry *geom = object->geometry;
460
461 if (geom->type == Geometry::MESH || geom->type == Geometry::VOLUME) {
462 Mesh *mesh = static_cast<Mesh *>(geom);
463 for (int tri_idx = 0; tri_idx < mesh->num_triangles(); ++tri_idx) {
464 split_triangle_primitive(mesh, &object->tfm, tri_idx, dim, pos, left_bounds, right_bounds);
465 }
466 }
467 else if (geom->type == Geometry::HAIR) {
468 Hair *hair = static_cast<Hair *>(geom);
469 for (int curve_idx = 0; curve_idx < hair->num_curves(); ++curve_idx) {
470 Hair::Curve curve = hair->get_curve(curve_idx);
471 for (int segment_idx = 0; segment_idx < curve.num_keys - 1; ++segment_idx) {
472 split_curve_primitive(
473 hair, &object->tfm, curve_idx, segment_idx, dim, pos, left_bounds, right_bounds);
474 }
475 }
476 }
477 }
478
split_reference(const BVHBuild & builder,BVHReference & left,BVHReference & right,const BVHReference & ref,int dim,float pos)479 void BVHSpatialSplit::split_reference(const BVHBuild &builder,
480 BVHReference &left,
481 BVHReference &right,
482 const BVHReference &ref,
483 int dim,
484 float pos)
485 {
486 /* initialize boundboxes */
487 BoundBox left_bounds = BoundBox::empty;
488 BoundBox right_bounds = BoundBox::empty;
489
490 /* loop over vertices/edges. */
491 const Object *ob = builder.objects[ref.prim_object()];
492
493 if (ref.prim_type() & PRIMITIVE_ALL_TRIANGLE) {
494 Mesh *mesh = static_cast<Mesh *>(ob->geometry);
495 split_triangle_reference(ref, mesh, dim, pos, left_bounds, right_bounds);
496 }
497 else if (ref.prim_type() & PRIMITIVE_ALL_CURVE) {
498 Hair *hair = static_cast<Hair *>(ob->geometry);
499 split_curve_reference(ref, hair, dim, pos, left_bounds, right_bounds);
500 }
501 else {
502 split_object_reference(ob, dim, pos, left_bounds, right_bounds);
503 }
504
505 /* intersect with original bounds. */
506 left_bounds.max[dim] = pos;
507 right_bounds.min[dim] = pos;
508
509 left_bounds.intersect(ref.bounds());
510 right_bounds.intersect(ref.bounds());
511
512 /* set references */
513 left = BVHReference(left_bounds, ref.prim_index(), ref.prim_object(), ref.prim_type());
514 right = BVHReference(right_bounds, ref.prim_index(), ref.prim_object(), ref.prim_type());
515 }
516
517 CCL_NAMESPACE_END
518