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