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