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