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