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