Cycles: Code cleanup, spaces around keywords
[blender-staging.git] / intern / cycles / bvh / bvh.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 "mesh.h"
19 #include "object.h"
20 #include "scene.h"
21 #include "curves.h"
22
23 #include "bvh.h"
24 #include "bvh_build.h"
25 #include "bvh_node.h"
26 #include "bvh_params.h"
27
28 #include "util_cache.h"
29 #include "util_debug.h"
30 #include "util_foreach.h"
31 #include "util_map.h"
32 #include "util_progress.h"
33 #include "util_system.h"
34 #include "util_types.h"
35 #include "util_math.h"
36
37 CCL_NAMESPACE_BEGIN
38
39 /* Pack Utility */
40
41 struct BVHStackEntry
42 {
43         const BVHNode *node;
44         int idx;
45
46         BVHStackEntry(const BVHNode* n = 0, int i = 0)
47         : node(n), idx(i)
48         {
49         }
50
51         int encodeIdx() const
52         {
53                 return (node->is_leaf())? ~idx: idx;
54         }
55 };
56
57 /* BVH */
58
59 BVH::BVH(const BVHParams& params_, const vector<Object*>& objects_)
60 : params(params_), objects(objects_)
61 {
62 }
63
64 BVH *BVH::create(const BVHParams& params, const vector<Object*>& objects)
65 {
66         if(params.use_qbvh)
67                 return new QBVH(params, objects);
68         else
69                 return new RegularBVH(params, objects);
70 }
71
72 /* Cache */
73
74 bool BVH::cache_read(CacheData& key)
75 {
76         key.add(system_cpu_bits());
77         key.add(&params, sizeof(params));
78
79         foreach(Object *ob, objects) {
80                 Mesh *mesh = ob->mesh;
81
82                 key.add(mesh->verts);
83                 key.add(mesh->triangles);
84                 key.add(mesh->curve_keys);
85                 key.add(mesh->curves);
86                 key.add(&ob->bounds, sizeof(ob->bounds));
87                 key.add(&ob->visibility, sizeof(ob->visibility));
88                 key.add(&mesh->transform_applied, sizeof(bool));
89
90                 if(mesh->use_motion_blur) {
91                         Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
92                         if(attr)
93                                 key.add(attr->buffer);
94
95                         attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
96                         if(attr)
97                                 key.add(attr->buffer);
98                 }
99         }
100
101         CacheData value;
102
103         if(Cache::global.lookup(key, value)) {
104                 cache_filename = key.get_filename();
105
106                 if(!(value.read(pack.root_index) &&
107                      value.read(pack.SAH) &&
108                      value.read(pack.nodes) &&
109                      value.read(pack.object_node) &&
110                      value.read(pack.tri_woop) &&
111                      value.read(pack.prim_type) &&
112                      value.read(pack.prim_visibility) &&
113                      value.read(pack.prim_index) &&
114                      value.read(pack.prim_object) &&
115                      value.read(pack.is_leaf)))
116                 {
117                         /* Clear the pack if load failed. */
118                         pack.root_index = 0;
119                         pack.SAH = 0.0f;
120                         pack.nodes.clear();
121                         pack.object_node.clear();
122                         pack.tri_woop.clear();
123                         pack.prim_type.clear();
124                         pack.prim_visibility.clear();
125                         pack.prim_index.clear();
126                         pack.prim_object.clear();
127                         pack.is_leaf.clear();
128                         return false;
129                 }
130                 return true;
131         }
132
133         return false;
134 }
135
136 void BVH::cache_write(CacheData& key)
137 {
138         CacheData value;
139
140         value.add(pack.root_index);
141         value.add(pack.SAH);
142
143         value.add(pack.nodes);
144         value.add(pack.object_node);
145         value.add(pack.tri_woop);
146         value.add(pack.prim_type);
147         value.add(pack.prim_visibility);
148         value.add(pack.prim_index);
149         value.add(pack.prim_object);
150         value.add(pack.is_leaf);
151
152         Cache::global.insert(key, value);
153
154         cache_filename = key.get_filename();
155 }
156
157 void BVH::clear_cache_except()
158 {
159         set<string> except;
160
161         if(!cache_filename.empty())
162                 except.insert(cache_filename);
163
164         foreach(Object *ob, objects) {
165                 Mesh *mesh = ob->mesh;
166                 BVH *bvh = mesh->bvh;
167
168                 if(bvh && !bvh->cache_filename.empty())
169                         except.insert(bvh->cache_filename);
170         }
171
172         Cache::global.clear_except("bvh", except);
173 }
174
175 /* Building */
176
177 void BVH::build(Progress& progress)
178 {
179         progress.set_substatus("Building BVH");
180
181         /* cache read */
182         CacheData key("bvh");
183
184         if(params.use_cache) {
185                 progress.set_substatus("Looking in BVH cache");
186
187                 if(cache_read(key))
188                         return;
189         }
190
191         /* build nodes */
192         vector<int> prim_type;
193         vector<int> prim_index;
194         vector<int> prim_object;
195
196         BVHBuild bvh_build(objects, prim_type, prim_index, prim_object, params, progress);
197         BVHNode *root = bvh_build.run();
198
199         if(progress.get_cancel()) {
200                 if(root) root->deleteSubtree();
201                 return;
202         }
203
204         /* todo: get rid of this copy */
205         pack.prim_type = prim_type;
206         pack.prim_index = prim_index;
207         pack.prim_object = prim_object;
208         prim_type.free_memory();
209         prim_index.free_memory();
210         prim_object.free_memory();
211
212         /* compute SAH */
213         if(!params.top_level)
214                 pack.SAH = root->computeSubtreeSAHCost(params);
215
216         if(progress.get_cancel()) {
217                 root->deleteSubtree();
218                 return;
219         }
220
221         /* pack triangles */
222         progress.set_substatus("Packing BVH triangles and strands");
223         pack_primitives();
224
225         if(progress.get_cancel()) {
226                 root->deleteSubtree();
227                 return;
228         }
229
230         /* pack nodes */
231         progress.set_substatus("Packing BVH nodes");
232         pack_nodes(root);
233
234         /* free build nodes */
235         root->deleteSubtree();
236
237         if(progress.get_cancel()) return;
238
239         /* cache write */
240         if(params.use_cache) {
241                 progress.set_substatus("Writing BVH cache");
242                 cache_write(key);
243
244                 /* clear other bvh files from cache */
245                 if(params.top_level)
246                         clear_cache_except();
247         }
248 }
249
250 /* Refitting */
251
252 void BVH::refit(Progress& progress)
253 {
254         progress.set_substatus("Packing BVH primitives");
255         pack_primitives();
256
257         if(progress.get_cancel()) return;
258
259         progress.set_substatus("Refitting BVH nodes");
260         refit_nodes();
261 }
262
263 /* Triangles */
264
265 void BVH::pack_triangle(int idx, float4 woop[3])
266 {
267         int tob = pack.prim_object[idx];
268         assert(tob >= 0 && tob < objects.size());
269         const Mesh *mesh = objects[tob]->mesh;
270
271         int tidx = pack.prim_index[idx];
272         const int *vidx = mesh->triangles[tidx].v;
273         const float3* vpos = &mesh->verts[0];
274         float3 v0 = vpos[vidx[0]];
275         float3 v1 = vpos[vidx[1]];
276         float3 v2 = vpos[vidx[2]];
277
278         woop[0] = float3_to_float4(v0);
279         woop[1] = float3_to_float4(v1);
280         woop[2] = float3_to_float4(v2);
281 }
282
283 /* Curves*/
284
285 void BVH::pack_primitives()
286 {
287         int nsize = TRI_NODE_SIZE;
288         size_t tidx_size = pack.prim_index.size();
289
290         pack.tri_woop.clear();
291         pack.tri_woop.resize(tidx_size * nsize);
292         pack.prim_visibility.clear();
293         pack.prim_visibility.resize(tidx_size);
294
295         for(unsigned int i = 0; i < tidx_size; i++) {
296                 if(pack.prim_index[i] != -1) {
297                         float4 woop[3];
298
299                         if(pack.prim_type[i] & PRIMITIVE_TRIANGLE) {
300                                 pack_triangle(i, woop);
301                         }
302                         else {
303                                 /* Avoid use of uninitialized memory. */
304                                 memset(&woop, 0, sizeof(woop));
305                         }
306
307                         memcpy(&pack.tri_woop[i * nsize], woop, sizeof(float4)*3);
308
309                         int tob = pack.prim_object[i];
310                         Object *ob = objects[tob];
311                         pack.prim_visibility[i] = ob->visibility;
312
313                         if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
314                                 pack.prim_visibility[i] |= PATH_RAY_CURVE;
315                 }
316                 else {
317                         memset(&pack.tri_woop[i * nsize], 0, sizeof(float4)*3);
318                         pack.prim_visibility[i] = 0;
319                 }
320         }
321 }
322
323 /* Pack Instances */
324
325 void BVH::pack_instances(size_t nodes_size)
326 {
327         /* The BVH's for instances are built separately, but for traversal all
328          * BVH's are stored in global arrays. This function merges them into the
329          * top level BVH, adjusting indexes and offsets where appropriate. */
330         bool use_qbvh = params.use_qbvh;
331         size_t nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
332
333         /* adjust primitive index to point to the triangle in the global array, for
334          * meshes with transform applied and already in the top level BVH */
335         for(size_t i = 0; i < pack.prim_index.size(); i++)
336                 if(pack.prim_index[i] != -1) {
337                         if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
338                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->curve_offset;
339                         else
340                                 pack.prim_index[i] += objects[pack.prim_object[i]]->mesh->tri_offset;
341                 }
342
343         /* track offsets of instanced BVH data in global array */
344         size_t prim_offset = pack.prim_index.size();
345         size_t nodes_offset = nodes_size;
346
347         /* clear array that gives the node indexes for instanced objects */
348         pack.object_node.clear();
349
350         /* reserve */
351         size_t prim_index_size = pack.prim_index.size();
352         size_t tri_woop_size = pack.tri_woop.size();
353
354         size_t pack_prim_index_offset = prim_index_size;
355         size_t pack_tri_woop_offset = tri_woop_size;
356         size_t pack_nodes_offset = nodes_size;
357         size_t object_offset = 0;
358
359         map<Mesh*, int> mesh_map;
360
361         foreach(Object *ob, objects) {
362                 Mesh *mesh = ob->mesh;
363                 BVH *bvh = mesh->bvh;
364
365                 if(!mesh->transform_applied) {
366                         if(mesh_map.find(mesh) == mesh_map.end()) {
367                                 prim_index_size += bvh->pack.prim_index.size();
368                                 tri_woop_size += bvh->pack.tri_woop.size();
369                                 nodes_size += bvh->pack.nodes.size();
370
371                                 mesh_map[mesh] = 1;
372                         }
373                 }
374         }
375
376         mesh_map.clear();
377
378         pack.prim_index.resize(prim_index_size);
379         pack.prim_type.resize(prim_index_size);
380         pack.prim_object.resize(prim_index_size);
381         pack.prim_visibility.resize(prim_index_size);
382         pack.tri_woop.resize(tri_woop_size);
383         pack.nodes.resize(nodes_size);
384         pack.object_node.resize(objects.size());
385
386         int *pack_prim_index = (pack.prim_index.size())? &pack.prim_index[0]: NULL;
387         int *pack_prim_type = (pack.prim_type.size())? &pack.prim_type[0]: NULL;
388         int *pack_prim_object = (pack.prim_object.size())? &pack.prim_object[0]: NULL;
389         uint *pack_prim_visibility = (pack.prim_visibility.size())? &pack.prim_visibility[0]: NULL;
390         float4 *pack_tri_woop = (pack.tri_woop.size())? &pack.tri_woop[0]: NULL;
391         int4 *pack_nodes = (pack.nodes.size())? &pack.nodes[0]: NULL;
392
393         /* merge */
394         foreach(Object *ob, objects) {
395                 Mesh *mesh = ob->mesh;
396
397                 /* if mesh transform is applied, that means it's already in the top
398                  * level BVH, and we don't need to merge it in */
399                 if(mesh->transform_applied) {
400                         pack.object_node[object_offset++] = 0;
401                         continue;
402                 }
403
404                 /* if mesh already added once, don't add it again, but used set
405                  * node offset for this object */
406                 map<Mesh*, int>::iterator it = mesh_map.find(mesh);
407
408                 if(mesh_map.find(mesh) != mesh_map.end()) {
409                         int noffset = it->second;
410                         pack.object_node[object_offset++] = noffset;
411                         continue;
412                 }
413
414                 BVH *bvh = mesh->bvh;
415
416                 int noffset = nodes_offset/nsize;
417                 int mesh_tri_offset = mesh->tri_offset;
418                 int mesh_curve_offset = mesh->curve_offset;
419
420                 /* fill in node indexes for instances */
421                 if((bvh->pack.is_leaf.size() != 0) && bvh->pack.is_leaf[0])
422                         pack.object_node[object_offset++] = -noffset-1;
423                 else
424                         pack.object_node[object_offset++] = noffset;
425
426                 mesh_map[mesh] = pack.object_node[object_offset-1];
427
428                 /* merge primitive and object indexes */
429                 if(bvh->pack.prim_index.size()) {
430                         size_t bvh_prim_index_size = bvh->pack.prim_index.size();
431                         int *bvh_prim_index = &bvh->pack.prim_index[0];
432                         int *bvh_prim_type = &bvh->pack.prim_type[0];
433                         uint *bvh_prim_visibility = &bvh->pack.prim_visibility[0];
434
435                         for(size_t i = 0; i < bvh_prim_index_size; i++) {
436                                 if(bvh->pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
437                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_curve_offset;
438                                 else
439                                         pack_prim_index[pack_prim_index_offset] = bvh_prim_index[i] + mesh_tri_offset;
440
441                                 pack_prim_type[pack_prim_index_offset] = bvh_prim_type[i];
442                                 pack_prim_visibility[pack_prim_index_offset] = bvh_prim_visibility[i];
443                                 pack_prim_object[pack_prim_index_offset] = 0;  // unused for instances
444                                 pack_prim_index_offset++;
445                         }
446                 }
447
448                 /* merge triangle intersection data */
449                 if(bvh->pack.tri_woop.size()) {
450                         memcpy(pack_tri_woop + pack_tri_woop_offset, &bvh->pack.tri_woop[0],
451                                 bvh->pack.tri_woop.size()*sizeof(float4));
452                         pack_tri_woop_offset += bvh->pack.tri_woop.size();
453                 }
454
455                 /* merge nodes */
456                 if(bvh->pack.nodes.size()) {
457                         /* For QBVH we're packing a child bbox into 6 float4,
458                          * and for regular BVH they're packed into 3 float4.
459                          */
460                         size_t nsize_bbox = (use_qbvh)? 6: 3;
461                         int4 *bvh_nodes = &bvh->pack.nodes[0];
462                         size_t bvh_nodes_size = bvh->pack.nodes.size(); 
463                         bool *bvh_is_leaf = (bvh->pack.is_leaf.size() != 0) ? &bvh->pack.is_leaf[0] : NULL;
464
465                         for(size_t i = 0, j = 0; i < bvh_nodes_size; i+=nsize, j++) {
466                                 memcpy(pack_nodes + pack_nodes_offset, bvh_nodes + i, nsize_bbox*sizeof(int4));
467
468                                 /* modify offsets into arrays */
469                                 int4 data = bvh_nodes[i + nsize_bbox];
470
471                                 if(bvh_is_leaf && bvh_is_leaf[j]) {
472                                         data.x += prim_offset;
473                                         data.y += prim_offset;
474                                 }
475                                 else {
476                                         data.x += (data.x < 0)? -noffset: noffset;
477                                         data.y += (data.y < 0)? -noffset: noffset;
478
479                                         if(use_qbvh) {
480                                                 data.z += (data.z < 0)? -noffset: noffset;
481                                                 data.w += (data.w < 0)? -noffset: noffset;
482                                         }
483                                 }
484
485                                 pack_nodes[pack_nodes_offset + nsize_bbox] = data;
486
487                                 /* Usually this copies nothing, but we better
488                                  * be prepared for possible node size extension.
489                                  */
490                                 memcpy(&pack_nodes[pack_nodes_offset + nsize_bbox+1],
491                                        &bvh_nodes[i + nsize_bbox+1],
492                                        sizeof(int4) * (nsize - (nsize_bbox+1)));
493
494                                 pack_nodes_offset += nsize;
495                         }
496                 }
497
498                 nodes_offset += bvh->pack.nodes.size();
499                 prim_offset += bvh->pack.prim_index.size();
500         }
501 }
502
503 /* Regular BVH */
504
505 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
506 : BVH(params_, objects_)
507 {
508 }
509
510 void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
511 {
512         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
513                 /* object */
514                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds, ~(leaf->m_lo), 0,
515                           leaf->m_visibility, leaf->m_visibility);
516         }
517         else {
518                 int prim_type = leaf->num_triangles() ? pack.prim_type[leaf->m_lo] : 0;
519                 /* Triangle/curve primitive leaf.  */
520                 pack_node(e.idx, leaf->m_bounds, leaf->m_bounds,
521                           leaf->m_lo, leaf->m_hi,
522                           leaf->m_visibility,
523                           prim_type);
524         }
525
526 }
527
528 void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
529 {
530         pack_node(e.idx, e0.node->m_bounds, e1.node->m_bounds, e0.encodeIdx(), e1.encodeIdx(), e0.node->m_visibility, e1.node->m_visibility);
531 }
532
533 void RegularBVH::pack_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1)
534 {
535         int4 data[BVH_NODE_SIZE] =
536         {
537                 make_int4(__float_as_int(b0.min.x), __float_as_int(b1.min.x), __float_as_int(b0.max.x), __float_as_int(b1.max.x)),
538                 make_int4(__float_as_int(b0.min.y), __float_as_int(b1.min.y), __float_as_int(b0.max.y), __float_as_int(b1.max.y)),
539                 make_int4(__float_as_int(b0.min.z), __float_as_int(b1.min.z), __float_as_int(b0.max.z), __float_as_int(b1.max.z)),
540                 make_int4(c0, c1, visibility0, visibility1)
541         };
542
543         memcpy(&pack.nodes[idx * BVH_NODE_SIZE], data, sizeof(int4)*BVH_NODE_SIZE);
544 }
545
546 void RegularBVH::pack_nodes(const BVHNode *root)
547 {
548         size_t node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
549
550         /* resize arrays */
551         pack.nodes.clear();
552         pack.is_leaf.clear();
553         pack.is_leaf.resize(node_size);
554
555         /* for top level BVH, first merge existing BVH's so we know the offsets */
556         if(params.top_level)
557                 pack_instances(node_size*BVH_NODE_SIZE);
558         else
559                 pack.nodes.resize(node_size*BVH_NODE_SIZE);
560
561         int nextNodeIdx = 0;
562
563         vector<BVHStackEntry> stack;
564         stack.reserve(BVHParams::MAX_DEPTH*2);
565         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
566
567         while(stack.size()) {
568                 BVHStackEntry e = stack.back();
569                 stack.pop_back();
570
571                 pack.is_leaf[e.idx] = e.node->is_leaf();
572
573                 if(e.node->is_leaf()) {
574                         /* leaf node */
575                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
576                         pack_leaf(e, leaf);
577                 }
578                 else {
579                         /* innner node */
580                         stack.push_back(BVHStackEntry(e.node->get_child(0), nextNodeIdx++));
581                         stack.push_back(BVHStackEntry(e.node->get_child(1), nextNodeIdx++));
582
583                         pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
584                 }
585         }
586
587         /* root index to start traversal at, to handle case of single leaf node */
588         pack.root_index = (pack.is_leaf[0])? -1: 0;
589 }
590
591 void RegularBVH::refit_nodes()
592 {
593         assert(!params.top_level);
594
595         BoundBox bbox = BoundBox::empty;
596         uint visibility = 0;
597         refit_node(0, (pack.is_leaf[0])? true: false, bbox, visibility);
598 }
599
600 void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
601 {
602         int4 *data = &pack.nodes[idx*BVH_NODE_SIZE];
603
604         int c0 = data[3].x;
605         int c1 = data[3].y;
606
607         if(leaf) {
608                 /* refit leaf node */
609                 for(int prim = c0; prim < c1; prim++) {
610                         int pidx = pack.prim_index[prim];
611                         int tob = pack.prim_object[prim];
612                         Object *ob = objects[tob];
613
614                         if(pidx == -1) {
615                                 /* object instance */
616                                 bbox.grow(ob->bounds);
617                         }
618                         else {
619                                 /* primitives */
620                                 const Mesh *mesh = ob->mesh;
621
622                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
623                                         /* curves */
624                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
625                                         const Mesh::Curve& curve = mesh->curves[pidx - str_offset];
626                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
627
628                                         curve.bounds_grow(k, &mesh->curve_keys[0], bbox);
629
630                                         visibility |= PATH_RAY_CURVE;
631
632                                         /* motion curves */
633                                         if(mesh->use_motion_blur) {
634                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
635
636                                                 if(attr) {
637                                                         size_t mesh_size = mesh->curve_keys.size();
638                                                         size_t steps = mesh->motion_steps - 1;
639                                                         float4 *key_steps = attr->data_float4();
640
641                                                         for(size_t i = 0; i < steps; i++)
642                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, bbox);
643                                                 }
644                                         }
645                                 }
646                                 else {
647                                         /* triangles */
648                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
649                                         const Mesh::Triangle& triangle = mesh->triangles[pidx - tri_offset];
650                                         const float3 *vpos = &mesh->verts[0];
651
652                                         triangle.bounds_grow(vpos, bbox);
653
654                                         /* motion triangles */
655                                         if(mesh->use_motion_blur) {
656                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
657
658                                                 if(attr) {
659                                                         size_t mesh_size = mesh->verts.size();
660                                                         size_t steps = mesh->motion_steps - 1;
661                                                         float3 *vert_steps = attr->data_float3();
662
663                                                         for(size_t i = 0; i < steps; i++)
664                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
665                                                 }
666                                         }
667                                 }
668                         }
669
670                         visibility |= ob->visibility;
671                 }
672
673                 pack_node(idx, bbox, bbox, c0, c1, visibility, data[3].w);
674         }
675         else {
676                 /* refit inner node, set bbox from children */
677                 BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
678                 uint visibility0 = 0, visibility1 = 0;
679
680                 refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
681                 refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
682
683                 pack_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
684
685                 bbox.grow(bbox0);
686                 bbox.grow(bbox1);
687                 visibility = visibility0|visibility1;
688         }
689 }
690
691 /* QBVH */
692
693 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
694 : BVH(params_, objects_)
695 {
696         params.use_qbvh = true;
697 }
698
699 void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
700 {
701         float4 data[BVH_QNODE_SIZE];
702
703         memset(data, 0, sizeof(data));
704
705         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->m_lo] == -1) {
706                 /* object */
707                 data[6].x = __int_as_float(~(leaf->m_lo));
708                 data[6].y = __int_as_float(0);
709         }
710         else {
711                 /* triangle */
712                 data[6].x = __int_as_float(leaf->m_lo);
713                 data[6].y = __int_as_float(leaf->m_hi);
714         }
715         data[6].z = __uint_as_float(leaf->m_visibility);
716         if(leaf->num_triangles() != 0) {
717                 data[6].w = __uint_as_float(pack.prim_type[leaf->m_lo]);
718         }
719
720         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
721 }
722
723 void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
724 {
725         float4 data[BVH_QNODE_SIZE];
726
727         for(int i = 0; i < num; i++) {
728                 float3 bb_min = en[i].node->m_bounds.min;
729                 float3 bb_max = en[i].node->m_bounds.max;
730
731                 data[0][i] = bb_min.x;
732                 data[1][i] = bb_max.x;
733                 data[2][i] = bb_min.y;
734                 data[3][i] = bb_max.y;
735                 data[4][i] = bb_min.z;
736                 data[5][i] = bb_max.z;
737
738                 data[6][i] = __int_as_float(en[i].encodeIdx());
739         }
740
741         for(int i = num; i < 4; i++) {
742                 /* We store BB which would never be recorded as intersection
743                  * so kernel might safely assume there are always 4 child nodes.
744                  */
745                 data[0][i] = FLT_MAX;
746                 data[1][i] = -FLT_MAX;
747
748                 data[2][i] = FLT_MAX;
749                 data[3][i] = -FLT_MAX;
750
751                 data[4][i] = FLT_MAX;
752                 data[5][i] = -FLT_MAX;
753
754                 data[6][i] = __int_as_float(0);
755         }
756
757         memcpy(&pack.nodes[e.idx * BVH_QNODE_SIZE], data, sizeof(float4)*BVH_QNODE_SIZE);
758 }
759
760 /* Quad SIMD Nodes */
761
762 void QBVH::pack_nodes(const BVHNode *root)
763 {
764         size_t node_size = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
765
766         /* resize arrays */
767         pack.nodes.clear();
768         pack.is_leaf.clear();
769         pack.is_leaf.resize(node_size);
770
771         /* for top level BVH, first merge existing BVH's so we know the offsets */
772         if(params.top_level)
773                 pack_instances(node_size*BVH_QNODE_SIZE);
774         else
775                 pack.nodes.resize(node_size*BVH_QNODE_SIZE);
776
777         int nextNodeIdx = 0;
778
779         vector<BVHStackEntry> stack;
780         stack.reserve(BVHParams::MAX_DEPTH*2);
781         stack.push_back(BVHStackEntry(root, nextNodeIdx++));
782
783         while(stack.size()) {
784                 BVHStackEntry e = stack.back();
785                 stack.pop_back();
786
787                 pack.is_leaf[e.idx] = e.node->is_leaf();
788
789                 if(e.node->is_leaf()) {
790                         /* leaf node */
791                         const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
792                         pack_leaf(e, leaf);
793                 }
794                 else {
795                         /* inner node */
796                         const BVHNode *node = e.node;
797                         const BVHNode *node0 = node->get_child(0);
798                         const BVHNode *node1 = node->get_child(1);
799
800                         /* collect nodes */
801                         const BVHNode *nodes[4];
802                         int numnodes = 0;
803
804                         if(node0->is_leaf()) {
805                                 nodes[numnodes++] = node0;
806                         }
807                         else {
808                                 nodes[numnodes++] = node0->get_child(0);
809                                 nodes[numnodes++] = node0->get_child(1);
810                         }
811
812                         if(node1->is_leaf()) {
813                                 nodes[numnodes++] = node1;
814                         }
815                         else {
816                                 nodes[numnodes++] = node1->get_child(0);
817                                 nodes[numnodes++] = node1->get_child(1);
818                         }
819
820                         /* push entries on the stack */
821                         for(int i = 0; i < numnodes; i++)
822                                 stack.push_back(BVHStackEntry(nodes[i], nextNodeIdx++));
823
824                         /* set node */
825                         pack_inner(e, &stack[stack.size()-numnodes], numnodes);
826                 }
827         }
828
829         /* root index to start traversal at, to handle case of single leaf node */
830         pack.root_index = (pack.is_leaf[0])? -1: 0;
831 }
832
833 void QBVH::refit_nodes()
834 {
835         assert(!params.top_level);
836
837         BoundBox bbox = BoundBox::empty;
838         uint visibility = 0;
839         refit_node(0, (pack.is_leaf[0])? true: false, bbox, visibility);
840 }
841
842 void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
843 {
844         int4 *data = &pack.nodes[idx*BVH_QNODE_SIZE];
845         int4 c = data[6];
846         if(leaf) {
847                 /* Refit leaf node. */
848                 for(int prim = c.x; prim < c.y; prim++) {
849                         int pidx = pack.prim_index[prim];
850                         int tob = pack.prim_object[prim];
851                         Object *ob = objects[tob];
852
853                         if(pidx == -1) {
854                                 /* Object instance. */
855                                 bbox.grow(ob->bounds);
856                         }
857                         else {
858                                 /* Primitives. */
859                                 const Mesh *mesh = ob->mesh;
860
861                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
862                                         /* Curves. */
863                                         int str_offset = (params.top_level)? mesh->curve_offset: 0;
864                                         const Mesh::Curve& curve = mesh->curves[pidx - str_offset];
865                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
866
867                                         curve.bounds_grow(k, &mesh->curve_keys[0], bbox);
868
869                                         visibility |= PATH_RAY_CURVE;
870
871                                         /* Motion curves. */
872                                         if(mesh->use_motion_blur) {
873                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
874
875                                                 if(attr) {
876                                                         size_t mesh_size = mesh->curve_keys.size();
877                                                         size_t steps = mesh->motion_steps - 1;
878                                                         float4 *key_steps = attr->data_float4();
879
880                                                         for(size_t i = 0; i < steps; i++)
881                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, bbox);
882                                                 }
883                                         }
884                                 }
885                                 else {
886                                         /* Triangles. */
887                                         int tri_offset = (params.top_level)? mesh->tri_offset: 0;
888                                         const Mesh::Triangle& triangle = mesh->triangles[pidx - tri_offset];
889                                         const float3 *vpos = &mesh->verts[0];
890
891                                         triangle.bounds_grow(vpos, bbox);
892
893                                         /* Motion triangles. */
894                                         if(mesh->use_motion_blur) {
895                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
896
897                                                 if(attr) {
898                                                         size_t mesh_size = mesh->verts.size();
899                                                         size_t steps = mesh->motion_steps - 1;
900                                                         float3 *vert_steps = attr->data_float3();
901
902                                                         for(size_t i = 0; i < steps; i++)
903                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
904                                                 }
905                                         }
906                                 }
907                         }
908
909                         visibility |= ob->visibility;
910                 }
911
912                 /* TODO(sergey): This is actually a copy of pack_leaf(),
913                  * but this chunk of code only knows actual data and has
914                  * no idea about BVHNode.
915                  *
916                  * Would be nice to de-duplicate code, but trying to make
917                  * making code more general ends up in much nastier code
918                  * in my opinion so far.
919                  *
920                  * Same applies to the inner nodes case below.
921                  */
922                 float4 leaf_data[BVH_QNODE_SIZE];
923                 memset(leaf_data, 0, sizeof(leaf_data));
924                 leaf_data[6].x = __int_as_float(c.x);
925                 leaf_data[6].y = __int_as_float(c.y);
926                 leaf_data[6].z = __uint_as_float(visibility);
927                 leaf_data[6].w = __uint_as_float(c.w);
928                 memcpy(&pack.nodes[idx * BVH_QNODE_SIZE],
929                        leaf_data,
930                        sizeof(float4)*BVH_QNODE_SIZE);
931         }
932         else {
933                 /* Refit inner node, set bbox from children. */
934                 BoundBox child_bbox[4] = {BoundBox::empty,
935                                           BoundBox::empty,
936                                           BoundBox::empty,
937                                           BoundBox::empty};
938                 uint child_visibility[4] = {0};
939                 int num_nodes = 0;
940
941                 for(int i = 0; i < 4; ++i) {
942                         if(c[i] != 0) {
943                                 refit_node((c[i] < 0)? -c[i]-1: c[i], (c[i] < 0),
944                                            child_bbox[i], child_visibility[i]);
945                                 ++num_nodes;
946                                 bbox.grow(child_bbox[i]);
947                                 visibility |= child_visibility[i];
948                         }
949                 }
950
951                 float4 inner_data[BVH_QNODE_SIZE];
952                 for(int i = 0; i < 4; ++i) {
953                         float3 bb_min = child_bbox[i].min;
954                         float3 bb_max = child_bbox[i].max;
955                         inner_data[0][i] = bb_min.x;
956                         inner_data[1][i] = bb_max.x;
957                         inner_data[2][i] = bb_min.y;
958                         inner_data[3][i] = bb_max.y;
959                         inner_data[4][i] = bb_min.z;
960                         inner_data[5][i] = bb_max.z;
961                         inner_data[6][i] = __int_as_float(c[i]);
962                 }
963                 memcpy(&pack.nodes[idx * BVH_QNODE_SIZE],
964                        inner_data,
965                        sizeof(float4)*BVH_QNODE_SIZE);
966         }
967 }
968
969 CCL_NAMESPACE_END