Merged changes in the trunk up to revision 46045.
[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.triangle_cost(i) +
58                                 right_bounds.safe_area() * builder->params.triangle_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.triangle_cost(leftNum) +
154                                 builder->spatial_right_bounds[i - 1].safe_area() * builder->params.triangle_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.triangle_cost(left_end - left_start);
213                 float rac = builder->params.triangle_cost(right_end - right_start);
214                 float lbc = builder->params.triangle_cost(left_end - left_start + 1);
215                 float rbc = builder->params.triangle_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_reference(BVHBuild *builder, BVHReference& left, BVHReference& right, const BVHReference& ref, int dim, float pos)
247 {
248         /* initialize boundboxes */
249         BoundBox left_bounds = BoundBox::empty;
250         BoundBox right_bounds = BoundBox::empty;
251
252         /* loop over vertices/edges. */
253         Object *ob = builder->objects[ref.prim_object()];
254         const Mesh *mesh = ob->mesh;
255         const int *inds = mesh->triangles[ref.prim_index()].v;
256         const float3 *verts = &mesh->verts[0];
257         const float3* v1 = &verts[inds[2]];
258
259         for(int i = 0; i < 3; i++) {
260                 const float3* v0 = v1;
261                 int vindex = inds[i];
262                 v1 = &verts[vindex];
263                 float v0p = (*v0)[dim];
264                 float v1p = (*v1)[dim];
265
266                 /* insert vertex to the boxes it belongs to. */
267                 if(v0p <= pos)
268                         left_bounds.grow(*v0);
269
270                 if(v0p >= pos)
271                         right_bounds.grow(*v0);
272
273                 /* edge intersects the plane => insert intersection to both boxes. */
274                 if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
275                         float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
276                         left_bounds.grow(t);
277                         right_bounds.grow(t);
278                 }
279         }
280
281         /* intersect with original bounds. */
282         left_bounds.max[dim] = pos;
283         right_bounds.min[dim] = pos;
284         left_bounds.intersect(ref.bounds());
285         right_bounds.intersect(ref.bounds());
286
287         /* set referecnes */
288         left = BVHReference(left_bounds, ref.prim_index(), ref.prim_object());
289         right = BVHReference(right_bounds, ref.prim_index(), ref.prim_object());
290 }
291
292 CCL_NAMESPACE_END
293