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