Cycles: svn merge -r41225:41232 ^/trunk/blender
[blender.git] / intern / cycles / bvh / bvh_build.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_node.h"
20 #include "bvh_params.h"
21 #include "bvh_sort.h"
22
23 #include "mesh.h"
24 #include "object.h"
25 #include "scene.h"
26
27 #include "util_algorithm.h"
28 #include "util_foreach.h"
29 #include "util_progress.h"
30 #include "util_time.h"
31
32 CCL_NAMESPACE_BEGIN
33
34 /* Constructor / Destructor */
35
36 BVHBuild::BVHBuild(const vector<Object*>& objects_,
37         vector<int>& prim_index_, vector<int>& prim_object_,
38         const BVHParams& params_, Progress& progress_)
39 : objects(objects_),
40   prim_index(prim_index_),
41   prim_object(prim_object_),
42   params(params_),
43   progress(progress_),
44   progress_start_time(0.0)
45 {
46         spatial_min_overlap = 0.0f;
47         progress_num_duplicates = 0;
48 }
49
50 BVHBuild::~BVHBuild()
51 {
52 }
53
54 /* Adding References */
55
56 void BVHBuild::add_reference_mesh(NodeSpec& root, Mesh *mesh, int i)
57 {
58         for(uint j = 0; j < mesh->triangles.size(); j++) {
59                 Mesh::Triangle t = mesh->triangles[j];
60                 Reference ref;
61
62                 ref.prim_index = j;
63                 ref.prim_object = i;
64
65                 for(int k = 0; k < 3; k++) {
66                         float3 pt = mesh->verts[t.v[k]];
67                         ref.bounds.grow(pt);
68                 }
69
70                 references.push_back(ref);
71                 root.bounds.grow(ref.bounds);
72         }
73 }
74
75 void BVHBuild::add_reference_object(NodeSpec& root, Object *ob, int i)
76 {
77         Reference ref;
78
79         ref.prim_index = -1;
80         ref.prim_object = i;
81         ref.bounds = ob->bounds;
82
83         references.push_back(ref);
84         root.bounds.grow(ref.bounds);
85 }
86
87 void BVHBuild::add_references(NodeSpec& root)
88 {
89         /* init root spec */
90         root.num = 0;
91         root.bounds = BoundBox();
92
93         /* add objects */
94         int i = 0;
95
96         foreach(Object *ob, objects) {
97                 if(params.top_level) {
98                         if(ob->mesh->transform_applied)
99                                 add_reference_mesh(root, ob->mesh, i);
100                         else
101                                 add_reference_object(root, ob, i);
102                 }
103                 else
104                         add_reference_mesh(root, ob->mesh, i);
105
106                 i++;
107
108                 if(progress.get_cancel()) return;
109         }
110
111         /* happens mostly on empty meshes */
112         if(!root.bounds.valid())
113                 root.bounds.grow(make_float3(0.0f, 0.0f, 0.0f));
114
115         root.num = references.size();
116 }
117
118 /* Build */
119
120 BVHNode* BVHBuild::run()
121 {
122         NodeSpec root;
123
124         /* add references */
125         add_references(root);
126
127         if(progress.get_cancel()) return NULL;
128
129         /* init spatial splits */
130         if(params.top_level) /* todo: get rid of this */
131                 params.use_spatial_split = false;
132
133         spatial_min_overlap = root.bounds.area() * params.spatial_split_alpha;
134         spatial_right_bounds.clear();
135         spatial_right_bounds.resize(max(root.num, (int)BVHParams::NUM_SPATIAL_BINS) - 1);
136
137         /* init progress updates */
138         progress_num_duplicates = 0;
139         progress_start_time = time_dt();
140
141         /* build recursively */
142         return build_node(root, 0, 0.0f, 1.0f);
143 }
144
145 void BVHBuild::progress_update(float progress_start, float progress_end)
146 {
147         if(time_dt() - progress_start_time < 0.25f)
148                 return;
149
150         float duplicates = (float)progress_num_duplicates/(float)references.size();
151         string msg = string_printf("Building BVH %.0f%%, duplicates %.0f%%",
152                 progress_start*100.0f, duplicates*100.0f);
153
154         progress.set_substatus(msg);
155         progress_start_time = time_dt();
156 }
157
158 BVHNode* BVHBuild::build_node(const NodeSpec& spec, int level, float progress_start, float progress_end)
159 {
160         /* progress update */
161         progress_update(progress_start, progress_end);
162         if(progress.get_cancel()) return NULL;
163
164         /* small enough or too deep => create leaf. */
165         if(spec.num <= params.min_leaf_size || level >= BVHParams::MAX_DEPTH)
166                 return create_leaf_node(spec);
167
168         /* find split candidates. */
169         float area = spec.bounds.area();
170         float leafSAH = area * params.triangle_cost(spec.num);
171         float nodeSAH = area * params.node_cost(2);
172         ObjectSplit object = find_object_split(spec, nodeSAH);
173         SpatialSplit spatial;
174
175         if(params.use_spatial_split && level < BVHParams::MAX_SPATIAL_DEPTH) {
176                 BoundBox overlap = object.left_bounds;
177                 overlap.intersect(object.right_bounds);
178
179                 if(overlap.area() >= spatial_min_overlap)
180                         spatial = find_spatial_split(spec, nodeSAH);
181         }
182
183         /* leaf SAH is the lowest => create leaf. */
184         float minSAH = min(min(leafSAH, object.sah), spatial.sah);
185
186         if(minSAH == leafSAH && spec.num <= params.max_leaf_size)
187                 return create_leaf_node(spec);
188
189         /* perform split. */
190         NodeSpec left, right;
191
192         if(params.use_spatial_split && minSAH == spatial.sah)
193                 do_spatial_split(left, right, spec, spatial);
194         if(!left.num || !right.num)
195                 do_object_split(left, right, spec, object);
196
197         /* create inner node. */
198         progress_num_duplicates += left.num + right.num - spec.num;
199
200         float progress_mid = lerp(progress_start, progress_end, (float)right.num / (float)(left.num + right.num));
201
202         BVHNode* rightNode = build_node(right, level + 1, progress_start, progress_mid);
203         if(progress.get_cancel()) {
204                 if(rightNode) rightNode->deleteSubtree();
205                 return NULL;
206         }
207
208         BVHNode* leftNode = build_node(left, level + 1, progress_mid, progress_end);
209         if(progress.get_cancel()) {
210                 if(leftNode) leftNode->deleteSubtree();
211                 return NULL;
212         }
213
214         return new InnerNode(spec.bounds, leftNode, rightNode);
215 }
216
217 BVHNode *BVHBuild::create_object_leaf_nodes(const Reference *ref, int num)
218 {
219         if(num == 0) {
220                 BoundBox bounds;
221                 return new LeafNode(bounds, 0, 0, 0);
222         }
223         else if(num == 1) {
224                 prim_index.push_back(ref[0].prim_index);
225                 prim_object.push_back(ref[0].prim_object);
226                 uint visibility = objects[ref[0].prim_object]->visibility;
227                 return new LeafNode(ref[0].bounds, visibility, prim_index.size()-1, prim_index.size());
228         }
229         else {
230                 int mid = num/2;
231                 BVHNode *leaf0 = create_object_leaf_nodes(ref, mid); 
232                 BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, num-mid); 
233
234                 BoundBox bounds;
235                 bounds.grow(leaf0->m_bounds);
236                 bounds.grow(leaf1->m_bounds);
237
238                 return new InnerNode(bounds, leaf0, leaf1);
239         }
240 }
241
242 BVHNode* BVHBuild::create_leaf_node(const NodeSpec& spec)
243 {
244         vector<int>& p_index = prim_index;
245         vector<int>& p_object = prim_object;
246         BoundBox bounds;
247         int num = 0;
248         uint visibility = 0;
249
250         for(int i = 0; i < spec.num; i++) {
251                 if(references.back().prim_index != -1) {
252                         p_index.push_back(references.back().prim_index);
253                         p_object.push_back(references.back().prim_object);
254                         bounds.grow(references.back().bounds);
255                         visibility |= objects[references.back().prim_object]->visibility;
256                         references.pop_back();
257                         num++;
258                 }
259         }
260
261         BVHNode *leaf = NULL;
262         
263         if(num > 0) {
264                 leaf = new LeafNode(bounds, visibility, p_index.size() - num, p_index.size());
265
266                 if(num == spec.num)
267                         return leaf;
268         }
269
270         /* while there may be multiple triangles in a leaf, for object primitives
271          * we want them to be the only one, so we  */
272         int ob_num = spec.num - num;
273         const Reference *ref = (ob_num)? &references.back() - (ob_num - 1): NULL;
274         BVHNode *oleaf = create_object_leaf_nodes(ref, ob_num);
275         for(int i = 0; i < ob_num; i++)
276                 references.pop_back();
277         
278         if(leaf)
279                 return new InnerNode(spec.bounds, leaf, oleaf);
280         else
281                 return oleaf;
282 }
283
284 /* Object Split */
285
286 BVHBuild::ObjectSplit BVHBuild::find_object_split(const NodeSpec& spec, float nodeSAH)
287 {
288         ObjectSplit split;
289         const Reference *ref_ptr = &references[references.size() - spec.num];
290
291         for(int dim = 0; dim < 3; dim++) {
292                 /* sort references */
293                 bvh_reference_sort(references.size() - spec.num, references.size(), &references[0], dim);
294
295                 /* sweep right to left and determine bounds. */
296                 BoundBox right_bounds;
297
298                 for(int i = spec.num - 1; i > 0; i--) {
299                         right_bounds.grow(ref_ptr[i].bounds);
300                         spatial_right_bounds[i - 1] = right_bounds;
301                 }
302
303                 /* sweep left to right and select lowest SAH. */
304                 BoundBox left_bounds;
305
306                 for(int i = 1; i < spec.num; i++) {
307                         left_bounds.grow(ref_ptr[i - 1].bounds);
308                         right_bounds = spatial_right_bounds[i - 1];
309
310                         float sah = nodeSAH +
311                                 left_bounds.area() * params.triangle_cost(i) +
312                                 right_bounds.area() * params.triangle_cost(spec.num - i);
313
314                         if(sah < split.sah) {
315                                 split.sah = sah;
316                                 split.dim = dim;
317                                 split.num_left = i;
318                                 split.left_bounds = left_bounds;
319                                 split.right_bounds = right_bounds;
320                         }
321                 }
322         }
323
324         return split;
325 }
326
327 void BVHBuild::do_object_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const ObjectSplit& split)
328 {
329         /* sort references according to split */
330         int start = references.size() - spec.num;
331         int end = references.size(); /* todo: is this right? */
332
333         bvh_reference_sort(start, end, &references[0], split.dim);
334
335         /* split node specs */
336         left.num = split.num_left;
337         left.bounds = split.left_bounds;
338         right.num = spec.num - split.num_left;
339         right.bounds = split.right_bounds;
340 }
341
342 /* Spatial Split */
343
344 BVHBuild::SpatialSplit BVHBuild::find_spatial_split(const NodeSpec& spec, float nodeSAH)
345 {
346         /* initialize bins. */
347         float3 origin = spec.bounds.min;
348         float3 binSize = (spec.bounds.max - origin) * (1.0f / (float)BVHParams::NUM_SPATIAL_BINS);
349         float3 invBinSize = 1.0f / binSize;
350
351         for(int dim = 0; dim < 3; dim++) {
352                 for(int i = 0; i < BVHParams::NUM_SPATIAL_BINS; i++) {
353                         SpatialBin& bin = spatial_bins[dim][i];
354
355                         bin.bounds = BoundBox();
356                         bin.enter = 0;
357                         bin.exit = 0;
358                 }
359         }
360
361         /* chop references into bins. */
362         for(unsigned int refIdx = references.size() - spec.num; refIdx < references.size(); refIdx++) {
363                 const Reference& ref = references[refIdx];
364                 float3 firstBinf = (ref.bounds.min - origin) * invBinSize;
365                 float3 lastBinf = (ref.bounds.max - origin) * invBinSize;
366                 int3 firstBin = make_int3((int)firstBinf.x, (int)firstBinf.y, (int)firstBinf.z);
367                 int3 lastBin = make_int3((int)lastBinf.x, (int)lastBinf.y, (int)lastBinf.z);
368
369                 firstBin = clamp(firstBin, 0, BVHParams::NUM_SPATIAL_BINS - 1);
370                 lastBin = clamp(lastBin, firstBin, BVHParams::NUM_SPATIAL_BINS - 1);
371
372                 for(int dim = 0; dim < 3; dim++) {
373                         Reference currRef = ref;
374
375                         for(int i = firstBin[dim]; i < lastBin[dim]; i++) {
376                                 Reference leftRef, rightRef;
377
378                                 split_reference(leftRef, rightRef, currRef, dim, origin[dim] + binSize[dim] * (float)(i + 1));
379                                 spatial_bins[dim][i].bounds.grow(leftRef.bounds);
380                                 currRef = rightRef;
381                         }
382
383                         spatial_bins[dim][lastBin[dim]].bounds.grow(currRef.bounds);
384                         spatial_bins[dim][firstBin[dim]].enter++;
385                         spatial_bins[dim][lastBin[dim]].exit++;
386                 }
387         }
388
389         /* select best split plane. */
390         SpatialSplit split;
391
392         for(int dim = 0; dim < 3; dim++) {
393                 /* sweep right to left and determine bounds. */
394                 BoundBox right_bounds;
395
396                 for(int i = BVHParams::NUM_SPATIAL_BINS - 1; i > 0; i--) {
397                         right_bounds.grow(spatial_bins[dim][i].bounds);
398                         spatial_right_bounds[i - 1] = right_bounds;
399                 }
400
401                 /* sweep left to right and select lowest SAH. */
402                 BoundBox left_bounds;
403                 int leftNum = 0;
404                 int rightNum = spec.num;
405
406                 for(int i = 1; i < BVHParams::NUM_SPATIAL_BINS; i++) {
407                         left_bounds.grow(spatial_bins[dim][i - 1].bounds);
408                         leftNum += spatial_bins[dim][i - 1].enter;
409                         rightNum -= spatial_bins[dim][i - 1].exit;
410
411                         float sah = nodeSAH +
412                                 left_bounds.area() * params.triangle_cost(leftNum) +
413                                 spatial_right_bounds[i - 1].area() * params.triangle_cost(rightNum);
414
415                         if(sah < split.sah) {
416                                 split.sah = sah;
417                                 split.dim = dim;
418                                 split.pos = origin[dim] + binSize[dim] * (float)i;
419                         }
420                 }
421         }
422
423         return split;
424 }
425
426 void BVHBuild::do_spatial_split(NodeSpec& left, NodeSpec& right, const NodeSpec& spec, const SpatialSplit& split)
427 {
428         /* Categorize references and compute bounds.
429          *
430          * Left-hand side:                      [left_start, left_end[
431          * Uncategorized/split:         [left_end, right_start[
432          * Right-hand side:                     [right_start, refs.size()[ */
433
434         vector<Reference>& refs = references;
435         int left_start = refs.size() - spec.num;
436         int left_end = left_start;
437         int right_start = refs.size();
438
439         left.bounds = right.bounds = BoundBox();
440
441         for(int i = left_end; i < right_start; i++) {
442                 if(refs[i].bounds.max[split.dim] <= split.pos) {
443                         /* entirely on the left-hand side */
444                         left.bounds.grow(refs[i].bounds);
445                         swap(refs[i], refs[left_end++]);
446                 }
447                 else if(refs[i].bounds.min[split.dim] >= split.pos) {
448                         /* entirely on the right-hand side */
449                         right.bounds.grow(refs[i].bounds);
450                         swap(refs[i--], refs[--right_start]);
451                 }
452         }
453
454         /* duplicate or unsplit references intersecting both sides. */
455         while(left_end < right_start) {
456                 /* split reference. */
457                 Reference lref, rref;
458
459                 split_reference(lref, rref, refs[left_end], split.dim, split.pos);
460
461                 /* compute SAH for duplicate/unsplit candidates. */
462                 BoundBox lub = left.bounds;             // Unsplit to left:             new left-hand bounds.
463                 BoundBox rub = right.bounds;    // Unsplit to right:    new right-hand bounds.
464                 BoundBox ldb = left.bounds;             // Duplicate:                   new left-hand bounds.
465                 BoundBox rdb = right.bounds;    // Duplicate:                   new right-hand bounds.
466
467                 lub.grow(refs[left_end].bounds);
468                 rub.grow(refs[left_end].bounds);
469                 ldb.grow(lref.bounds);
470                 rdb.grow(rref.bounds);
471
472                 float lac = params.triangle_cost(left_end - left_start);
473                 float rac = params.triangle_cost(refs.size() - right_start);
474                 float lbc = params.triangle_cost(left_end - left_start + 1);
475                 float rbc = params.triangle_cost(refs.size() - right_start + 1);
476
477                 float unsplitLeftSAH = lub.area() * lbc + right.bounds.area() * rac;
478                 float unsplitRightSAH = left.bounds.area() * lac + rub.area() * rbc;
479                 float duplicateSAH = ldb.area() * lbc + rdb.area() * rbc;
480                 float minSAH = min(min(unsplitLeftSAH, unsplitRightSAH), duplicateSAH);
481
482                 if(minSAH == unsplitLeftSAH) {
483                         /* unsplit to left */
484                         left.bounds = lub;
485                         left_end++;
486                 }
487                 else if(minSAH == unsplitRightSAH) {
488                         /* unsplit to right */
489                         right.bounds = rub;
490                         swap(refs[left_end], refs[--right_start]);
491                 }
492                 else {
493                         /* duplicate */
494                         left.bounds = ldb;
495                         right.bounds = rdb;
496                         refs[left_end++] = lref;
497                         refs.push_back(rref);
498                 }
499         }
500
501         left.num = left_end - left_start;
502         right.num = refs.size() - right_start;
503 }
504
505 void BVHBuild::split_reference(Reference& left, Reference& right, const Reference& ref, int dim, float pos)
506 {
507         /* initialize references. */
508         left.prim_index = right.prim_index = ref.prim_index;
509         left.prim_object = right.prim_object = ref.prim_object;
510         left.bounds = right.bounds = BoundBox();
511
512         /* loop over vertices/edges. */
513         Object *ob = objects[ref.prim_object];
514         const Mesh *mesh = ob->mesh;
515         const int *inds = mesh->triangles[ref.prim_index].v;
516         const float3 *verts = &mesh->verts[0];
517         const float3* v1 = &verts[inds[2]];
518
519         for(int i = 0; i < 3; i++) {
520                 const float3* v0 = v1;
521                 int vindex = inds[i];
522                 v1 = &verts[vindex];
523                 float v0p = (*v0)[dim];
524                 float v1p = (*v1)[dim];
525
526                 /* insert vertex to the boxes it belongs to. */
527                 if(v0p <= pos)
528                         left.bounds.grow(*v0);
529
530                 if(v0p >= pos)
531                         right.bounds.grow(*v0);
532
533                 /* edge intersects the plane => insert intersection to both boxes. */
534                 if((v0p < pos && v1p > pos) || (v0p > pos && v1p < pos)) {
535                         float3 t = lerp(*v0, *v1, clamp((pos - v0p) / (v1p - v0p), 0.0f, 1.0f));
536                         left.bounds.grow(t);
537                         right.bounds.grow(t);
538                 }
539         }
540
541         /* intersect with original bounds. */
542         left.bounds.max[dim] = pos;
543         right.bounds.min[dim] = pos;
544         left.bounds.intersect(ref.bounds);
545         right.bounds.intersect(ref.bounds);
546 }
547
548 CCL_NAMESPACE_END
549