Cycles: threading optimizations
[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_binning.h"
19 #include "bvh_build.h"
20 #include "bvh_node.h"
21 #include "bvh_params.h"
22 #include "bvh_split.h"
23
24 #include "mesh.h"
25 #include "object.h"
26 #include "scene.h"
27
28 #include "util_debug.h"
29 #include "util_foreach.h"
30 #include "util_progress.h"
31 #include "util_time.h"
32
33 CCL_NAMESPACE_BEGIN
34
35 /* BVH Build Task */
36
37 class BVHBuildTask : public Task {
38 public:
39         BVHBuildTask(BVHBuild *build, InnerNode *node, int child, BVHObjectBinning& range_, int level)
40         : range(range_)
41         {
42                 run = function_bind(&BVHBuild::thread_build_node, build, node, child, &range, level);
43         }
44
45         BVHObjectBinning range;
46 };
47
48 /* Constructor / Destructor */
49
50 BVHBuild::BVHBuild(const vector<Object*>& objects_,
51         vector<int>& prim_index_, vector<int>& prim_object_,
52         const BVHParams& params_, Progress& progress_)
53 : objects(objects_),
54   prim_index(prim_index_),
55   prim_object(prim_object_),
56   params(params_),
57   progress(progress_),
58   progress_start_time(0.0)
59 {
60         spatial_min_overlap = 0.0f;
61 }
62
63 BVHBuild::~BVHBuild()
64 {
65 }
66
67 /* Adding References */
68
69 void BVHBuild::add_reference_mesh(BoundBox& root, BoundBox& center, Mesh *mesh, int i)
70 {
71         for(uint j = 0; j < mesh->triangles.size(); j++) {
72                 Mesh::Triangle t = mesh->triangles[j];
73                 BoundBox bounds = BoundBox::empty;
74
75                 for(int k = 0; k < 3; k++) {
76                         float3 pt = mesh->verts[t.v[k]];
77                         bounds.grow(pt);
78                 }
79
80                 if(bounds.valid()) {
81                         references.push_back(BVHReference(bounds, j, i));
82                         root.grow(bounds);
83                         center.grow(bounds.center2());
84                 }
85         }
86 }
87
88 void BVHBuild::add_reference_object(BoundBox& root, BoundBox& center, Object *ob, int i)
89 {
90         references.push_back(BVHReference(ob->bounds, -1, i));
91         root.grow(ob->bounds);
92         center.grow(ob->bounds.center2());
93 }
94
95 void BVHBuild::add_references(BVHRange& root)
96 {
97         /* reserve space for references */
98         size_t num_alloc_references = 0;
99
100         foreach(Object *ob, objects) {
101                 if(params.top_level) {
102                         if(ob->mesh->transform_applied)
103                                 num_alloc_references += ob->mesh->triangles.size();
104                         else
105                                 num_alloc_references++;
106                 }
107                 else
108                         num_alloc_references += ob->mesh->triangles.size();
109         }
110
111         references.reserve(num_alloc_references);
112
113         /* add references from objects */
114         BoundBox bounds = BoundBox::empty, center = BoundBox::empty;
115         int i = 0;
116
117         foreach(Object *ob, objects) {
118                 if(params.top_level) {
119                         if(ob->mesh->transform_applied)
120                                 add_reference_mesh(bounds, center, ob->mesh, i);
121                         else
122                                 add_reference_object(bounds, center, ob, i);
123                 }
124                 else
125                         add_reference_mesh(bounds, center, ob->mesh, i);
126
127                 i++;
128
129                 if(progress.get_cancel()) return;
130         }
131
132         /* happens mostly on empty meshes */
133         if(!bounds.valid())
134                 bounds.grow(make_float3(0.0f, 0.0f, 0.0f));
135
136         root = BVHRange(bounds, center, 0, references.size());
137 }
138
139 /* Build */
140
141 BVHNode* BVHBuild::run()
142 {
143         BVHRange root;
144
145         /* add references */
146         add_references(root);
147
148         if(progress.get_cancel())
149                 return NULL;
150
151         /* init spatial splits */
152         if(params.top_level) /* todo: get rid of this */
153                 params.use_spatial_split = false;
154
155         spatial_min_overlap = root.bounds().safe_area() * params.spatial_split_alpha;
156         spatial_right_bounds.clear();
157         spatial_right_bounds.resize(max(root.size(), (int)BVHParams::NUM_SPATIAL_BINS) - 1);
158
159         /* init progress updates */
160         progress_start_time = time_dt();
161         progress_count = 0;
162         progress_total = references.size();
163         progress_original_total = progress_total;
164
165         prim_index.resize(references.size());
166         prim_object.resize(references.size());
167
168         /* build recursively */
169         BVHNode *rootnode;
170
171         if(params.use_spatial_split) {
172                 /* singlethreaded spatial split build */
173                 rootnode = build_node(root, 0);
174         }
175         else {
176                 /* multithreaded binning build */
177                 BVHObjectBinning rootbin(root, (references.size())? &references[0]: NULL);
178                 rootnode = build_node(rootbin, 0);
179                 task_pool.wait_work();
180         }
181
182         /* delete if we cancelled */
183         if(rootnode) {
184                 if(progress.get_cancel()) {
185                         rootnode->deleteSubtree();
186                         rootnode = NULL;
187                 }
188                 else if(!params.use_spatial_split) {
189                         /*rotate(rootnode, 4, 5);*/
190                         rootnode->update_visibility();
191                 }
192         }
193
194         return rootnode;
195 }
196
197 void BVHBuild::progress_update()
198 {
199         if(time_dt() - progress_start_time < 0.25f)
200                 return;
201         
202         double progress_start = (double)progress_count/(double)progress_total;
203         double duplicates = (double)(progress_total - progress_original_total)/(double)progress_total;
204
205         string msg = string_printf("Building BVH %.0f%%, duplicates %.0f%%",
206                 progress_start*100.0f, duplicates*100.0f);
207
208         progress.set_substatus(msg);
209         progress_start_time = time_dt(); 
210 }
211
212 void BVHBuild::thread_build_node(InnerNode *inner, int child, BVHObjectBinning *range, int level)
213 {
214         if(progress.get_cancel())
215                 return;
216
217         /* build nodes */
218         BVHNode *node = build_node(*range, level);
219
220         /* set child in inner node */
221         inner->children[child] = node;
222
223         /* update progress */
224         if(range->size() < THREAD_TASK_SIZE) {
225                 /*rotate(node, INT_MAX, 5);*/
226
227                 thread_scoped_lock lock(build_mutex);
228
229                 progress_count += range->size();
230                 progress_update();
231         }
232 }
233
234 /* multithreaded binning builder */
235 BVHNode* BVHBuild::build_node(const BVHObjectBinning& range, int level)
236 {
237         size_t size = range.size();
238         float leafSAH = params.sah_triangle_cost * range.leafSAH;
239         float splitSAH = params.sah_node_cost * range.bounds().half_area() + params.sah_triangle_cost * range.splitSAH;
240
241         /* make leaf node when threshold reached or SAH tells us */
242         if(params.small_enough_for_leaf(size, level) || (size <= params.max_leaf_size && leafSAH < splitSAH))
243                 return create_leaf_node(range);
244
245         /* perform split */
246         BVHObjectBinning left, right;
247         range.split(&references[0], left, right);
248
249         /* create inner node. */
250         InnerNode *inner;
251
252         if(range.size() < THREAD_TASK_SIZE) {
253                 /* local build */
254                 BVHNode *leftnode = build_node(left, level + 1);
255                 BVHNode *rightnode = build_node(right, level + 1);
256
257                 inner = new InnerNode(range.bounds(), leftnode, rightnode);
258         }
259         else {
260                 /* threaded build */
261                 inner = new InnerNode(range.bounds());
262
263                 task_pool.push(new BVHBuildTask(this, inner, 0, left, level + 1), true);
264                 task_pool.push(new BVHBuildTask(this, inner, 1, right, level + 1), true);
265         }
266
267         return inner;
268 }
269
270 /* single threaded spatial split builder */
271 BVHNode* BVHBuild::build_node(const BVHRange& range, int level)
272 {
273         /* progress update */
274         progress_update();
275         if(progress.get_cancel())
276                 return NULL;
277
278         /* small enough or too deep => create leaf. */
279         if(params.small_enough_for_leaf(range.size(), level)) {
280                 progress_count += range.size();
281                 return create_leaf_node(range);
282         }
283
284         /* splitting test */
285         BVHMixedSplit split(this, range, level);
286
287         if(split.no_split) {
288                 progress_count += range.size();
289                 return create_leaf_node(range);
290         }
291         
292         /* do split */
293         BVHRange left, right;
294         split.split(this, left, right, range);
295
296         progress_total += left.size() + right.size() - range.size();
297         size_t total = progress_total;
298
299         /* leaft node */
300         BVHNode *leftnode = build_node(left, level + 1);
301
302         /* right node (modify start for splits) */
303         right.set_start(right.start() + progress_total - total);
304         BVHNode *rightnode = build_node(right, level + 1);
305
306         /* inner node */
307         return new InnerNode(range.bounds(), leftnode, rightnode);
308 }
309
310 /* Create Nodes */
311
312 BVHNode *BVHBuild::create_object_leaf_nodes(const BVHReference *ref, int start, int num)
313 {
314         if(num == 0) {
315                 BoundBox bounds = BoundBox::empty;
316                 return new LeafNode(bounds, 0, 0, 0);
317         }
318         else if(num == 1) {
319                 if(start == prim_index.size()) {
320                         assert(params.use_spatial_split);
321
322                         prim_index.push_back(ref->prim_index());
323                         prim_object.push_back(ref->prim_object());
324                 }
325                 else {
326                         prim_index[start] = ref->prim_index();
327                         prim_object[start] = ref->prim_object();
328                 }
329
330                 uint visibility = objects[ref->prim_object()]->visibility;
331                 return new LeafNode(ref->bounds(), visibility, start, start+1);
332         }
333         else {
334                 int mid = num/2;
335                 BVHNode *leaf0 = create_object_leaf_nodes(ref, start, mid); 
336                 BVHNode *leaf1 = create_object_leaf_nodes(ref+mid, start+mid, num-mid); 
337
338                 BoundBox bounds = BoundBox::empty;
339                 bounds.grow(leaf0->m_bounds);
340                 bounds.grow(leaf1->m_bounds);
341
342                 return new InnerNode(bounds, leaf0, leaf1);
343         }
344 }
345
346 BVHNode* BVHBuild::create_leaf_node(const BVHRange& range)
347 {
348         vector<int>& p_index = prim_index;
349         vector<int>& p_object = prim_object;
350         BoundBox bounds = BoundBox::empty;
351         int num = 0, ob_num = 0;
352         uint visibility = 0;
353
354         for(int i = 0; i < range.size(); i++) {
355                 BVHReference& ref = references[range.start() + i];
356
357                 if(ref.prim_index() != -1) {
358                         if(range.start() + num == prim_index.size()) {
359                                 assert(params.use_spatial_split);
360
361                                 p_index.push_back(ref.prim_index());
362                                 p_object.push_back(ref.prim_object());
363                         }
364                         else {
365                                 p_index[range.start() + num] = ref.prim_index();
366                                 p_object[range.start() + num] = ref.prim_object();
367                         }
368
369                         bounds.grow(ref.bounds());
370                         visibility |= objects[ref.prim_object()]->visibility;
371                         num++;
372                 }
373                 else {
374                         if(ob_num < i)
375                                 references[range.start() + ob_num] = ref;
376                         ob_num++;
377                 }
378         }
379
380         BVHNode *leaf = NULL;
381         
382         if(num > 0) {
383                 leaf = new LeafNode(bounds, visibility, range.start(), range.start() + num);
384
385                 if(num == range.size())
386                         return leaf;
387         }
388
389         /* while there may be multiple triangles in a leaf, for object primitives
390          * we want there to be the only one, so we keep splitting */
391         const BVHReference *ref = (ob_num)? &references[range.start()]: NULL;
392         BVHNode *oleaf = create_object_leaf_nodes(ref, range.start() + num, ob_num);
393         
394         if(leaf)
395                 return new InnerNode(range.bounds(), leaf, oleaf);
396         else
397                 return oleaf;
398 }
399
400 /* Tree Rotations */
401
402 void BVHBuild::rotate(BVHNode *node, int max_depth, int iterations)
403 {
404         /* in tested scenes, this resulted in slightly slower raytracing, so disabled
405          * it for now. could be implementation bug, or depend on the scene */
406         if(node)
407                 for(int i = 0; i < iterations; i++)
408                         rotate(node, max_depth);
409 }
410
411 void BVHBuild::rotate(BVHNode *node, int max_depth)
412 {
413         /* nothing to rotate if we reached a leaf node. */
414         if(node->is_leaf() || max_depth < 0)
415                 return;
416         
417         InnerNode *parent = (InnerNode*)node;
418
419         /* rotate all children first */
420         for(size_t c = 0; c < 2; c++)
421                 rotate(parent->children[c], max_depth-1);
422
423         /* compute current area of all children */
424         BoundBox bounds0 = parent->children[0]->m_bounds;
425         BoundBox bounds1 = parent->children[1]->m_bounds;
426
427         float area0 = bounds0.half_area();
428         float area1 = bounds1.half_area();
429         float4 child_area = make_float4(area0, area1, 0.0f, 0.0f);
430
431         /* find best rotation. we pick a target child of a first child, and swap
432          * this with an other child. we perform the best such swap. */
433         float best_cost = FLT_MAX;
434         int best_child = -1, bets_target = -1, best_other = -1;
435
436         for(size_t c = 0; c < 2; c++) {
437                 /* ignore leaf nodes as we cannot descent into */
438                 if(parent->children[c]->is_leaf())
439                         continue;
440
441                 InnerNode *child = (InnerNode*)parent->children[c];
442                 BoundBox& other = (c == 0)? bounds1: bounds0;
443
444                 /* transpose child bounds */
445                 BoundBox target0 = child->children[0]->m_bounds;
446                 BoundBox target1 = child->children[1]->m_bounds;
447
448                 /* compute cost for both possible swaps */
449                 float cost0 = merge(other, target1).half_area() - child_area[c];
450                 float cost1 = merge(target0, other).half_area() - child_area[c];
451
452                 if(min(cost0,cost1) < best_cost) {
453                         best_child = (int)c;
454                         best_other = (int)(1-c);
455
456                         if(cost0 < cost1) {
457                                 best_cost = cost0;
458                                 bets_target = 0;
459                         }
460                         else {
461                                 best_cost = cost0;
462                                 bets_target = 1;
463                         }
464                 }
465         }
466
467         /* if we did not find a swap that improves the SAH then do nothing */
468         if(best_cost >= 0)
469                 return;
470
471         /* perform the best found tree rotation */
472         InnerNode *child = (InnerNode*)parent->children[best_child];
473
474         swap(parent->children[best_other], child->children[bets_target]);
475         child->m_bounds = merge(child->children[0]->m_bounds, child->children[1]->m_bounds);
476 }
477
478 CCL_NAMESPACE_END
479