Cycles: Cleanup
[blender.git] / intern / cycles / bvh / bvh8.cpp
1 /*
2 * Original code Copyright 2017, Intel Corporation
3 * Modifications Copyright 2018, Blender Foundation.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * * Neither the name of Intel Corporation nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
24 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "bvh/bvh8.h"
30
31 #include "render/mesh.h"
32 #include "render/object.h"
33
34 #include "bvh/bvh_node.h"
35 #include "bvh/bvh_unaligned.h"
36
37 CCL_NAMESPACE_BEGIN
38
39 BVH8::BVH8(const BVHParams& params_, const vector<Object*>& objects_)
40 : BVH(params_, objects_)
41 {
42 }
43
44 void BVH8::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
45 {
46         float4 data[BVH_ONODE_LEAF_SIZE];
47         memset(data, 0, sizeof(data));
48         if(leaf->num_triangles() == 1 && pack.prim_index[leaf->lo] == -1) {
49                 /* object */
50                 data[0].x = __int_as_float(~(leaf->lo));
51                 data[0].y = __int_as_float(0);
52         }
53         else {
54                 /* triangle */
55                 data[0].x = __int_as_float(leaf->lo);
56                 data[0].y = __int_as_float(leaf->hi);
57         }
58         data[0].z = __uint_as_float(leaf->visibility);
59         if(leaf->num_triangles() != 0) {
60                 data[0].w = __uint_as_float(pack.prim_type[leaf->lo]);
61         }
62
63         memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_ONODE_LEAF_SIZE);
64 }
65
66 void BVH8::pack_inner(const BVHStackEntry& e,
67                       const BVHStackEntry *en,
68                       int num)
69 {
70         bool has_unaligned = false;
71         /* Check whether we have to create unaligned node or all nodes are aligned
72          * and we can cut some corner here.
73          */
74         if(params.use_unaligned_nodes) {
75                 for(int i = 0; i < num; i++) {
76                         if(en[i].node->is_unaligned) {
77                                 has_unaligned = true;
78                                 break;
79                         }
80                 }
81         }
82         if(has_unaligned) {
83                 /* There's no unaligned children, pack into AABB node. */
84                 pack_unaligned_inner(e, en, num);
85         }
86         else {
87                 /* Create unaligned node with orientation transform for each of the
88                  * children.
89                  */
90                 pack_aligned_inner(e, en, num);
91         }
92 }
93
94 void BVH8::pack_aligned_inner(const BVHStackEntry& e,
95                               const BVHStackEntry *en,
96                               int num)
97 {
98         BoundBox bounds[8];
99         int child[8];
100         for(int i = 0; i < num; ++i) {
101                 bounds[i] = en[i].node->bounds;
102                 child[i] = en[i].encodeIdx();
103         }
104         pack_aligned_node(e.idx,
105                           bounds,
106                           child,
107                           e.node->visibility,
108                           e.node->time_from,
109                           e.node->time_to,
110                           num);
111 }
112
113 void BVH8::pack_aligned_node(int idx,
114                              const BoundBox *bounds,
115                              const int *child,
116                              const uint visibility,
117                              const float time_from,
118                              const float time_to,
119                              const int num)
120 {
121         float8 data[8];
122         memset(data, 0, sizeof(data));
123
124         data[0].a = __uint_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED);
125         data[0].b = time_from;
126         data[0].c = time_to;
127
128         for(int i = 0; i < num; i++) {
129                 float3 bb_min = bounds[i].min;
130                 float3 bb_max = bounds[i].max;
131
132                 data[1][i] = bb_min.x;
133                 data[2][i] = bb_max.x;
134                 data[3][i] = bb_min.y;
135                 data[4][i] = bb_max.y;
136                 data[5][i] = bb_min.z;
137                 data[6][i] = bb_max.z;
138
139                 data[7][i] = __int_as_float(child[i]);
140         }
141
142         for(int i = num; i < 8; i++) {
143                 /* We store BB which would never be recorded as intersection
144                  * so kernel might safely assume there are always 4 child nodes.
145                  */
146                 data[1][i] = FLT_MAX;
147                 data[2][i] = -FLT_MAX;
148
149                 data[3][i] = FLT_MAX;
150                 data[4][i] = -FLT_MAX;
151
152                 data[5][i] = FLT_MAX;
153                 data[6][i] = -FLT_MAX;
154
155                 data[7][i] = __int_as_float(0);
156         }
157
158         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_ONODE_SIZE);
159 }
160
161 void BVH8::pack_unaligned_inner(const BVHStackEntry& e,
162                                 const BVHStackEntry *en,
163                                 int num)
164 {
165         Transform aligned_space[8];
166         BoundBox bounds[8];
167         int child[8];
168         for(int i = 0; i < num; ++i) {
169                 aligned_space[i] = en[i].node->get_aligned_space();
170                 bounds[i] = en[i].node->bounds;
171                 child[i] = en[i].encodeIdx();
172         }
173         pack_unaligned_node(e.idx,
174                             aligned_space,
175                             bounds,
176                             child,
177                             e.node->visibility,
178                             e.node->time_from,
179                             e.node->time_to,
180                             num);
181 }
182
183 void BVH8::pack_unaligned_node(int idx,
184                                const Transform *aligned_space,
185                                const BoundBox *bounds,
186                                const int *child,
187                                const uint visibility,
188                                const float time_from,
189                                const float time_to,
190                                const int num)
191 {
192         float8 data[BVH_UNALIGNED_ONODE_SIZE];
193         memset(data, 0, sizeof(data));
194
195         data[0].a = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED);
196         data[0].b = time_from;
197         data[0].c = time_to;
198
199         for(int i = 0; i < num; i++) {
200                 Transform space = BVHUnaligned::compute_node_transform(
201                         bounds[i],
202                         aligned_space[i]);
203
204                 data[1][i] = space.x.x;
205                 data[2][i] = space.x.y;
206                 data[3][i] = space.x.z;
207
208                 data[4][i] = space.y.x;
209                 data[5][i] = space.y.y;
210                 data[6][i] = space.y.z;
211
212                 data[7][i] = space.z.x;
213                 data[8][i] = space.z.y;
214                 data[9][i] = space.z.z;
215
216                 data[10][i] = space.x.w;
217                 data[11][i] = space.y.w;
218                 data[12][i] = space.z.w;
219
220                 data[13][i] = __int_as_float(child[i]);
221         }
222
223         for(int i = num; i < 8; i++) {
224                 /* We store BB which would never be recorded as intersection
225                  * so kernel might safely assume there are always 4 child nodes.
226                  */
227
228                 data[1][i] = NAN;
229                 data[2][i] = NAN;
230                 data[3][i] = NAN;
231
232                 data[4][i] = NAN;
233                 data[5][i] = NAN;
234                 data[6][i] = NAN;
235
236                 data[7][i] = NAN;
237                 data[8][i] = NAN;
238                 data[9][i] = NAN;
239
240                 data[10][i] = NAN;
241                 data[11][i] = NAN;
242                 data[12][i] = NAN;
243
244                 data[13][i] = __int_as_float(0);
245         }
246
247         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_ONODE_SIZE);
248 }
249
250 /* Quad SIMD Nodes */
251
252 void BVH8::pack_nodes(const BVHNode *root)
253 {
254         /* Calculate size of the arrays required. */
255         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_ONODE_COUNT);
256         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
257         assert(num_leaf_nodes <= num_nodes);
258         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
259         size_t node_size;
260         if(params.use_unaligned_nodes) {
261                 const size_t num_unaligned_nodes =
262                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_ONODE_COUNT);
263                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_ONODE_SIZE) +
264                         (num_inner_nodes - num_unaligned_nodes) * BVH_ONODE_SIZE;
265         }
266         else {
267                 node_size = num_inner_nodes * BVH_ONODE_SIZE;
268         }
269         /* Resize arrays. */
270         pack.nodes.clear();
271         pack.leaf_nodes.clear();
272         /* For top level BVH, first merge existing BVH's so we know the offsets. */
273         if(params.top_level) {
274                 pack_instances(node_size, num_leaf_nodes*BVH_ONODE_LEAF_SIZE);
275         }
276         else {
277                 pack.nodes.resize(node_size);
278                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_ONODE_LEAF_SIZE);
279         }
280
281         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
282
283         vector<BVHStackEntry> stack;
284         stack.reserve(BVHParams::MAX_DEPTH*2);
285         if(root->is_leaf()) {
286                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
287         }
288         else {
289                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
290                 nextNodeIdx += node_is_unaligned(root, bvh8)
291                                    ? BVH_UNALIGNED_ONODE_SIZE
292                                    : BVH_ONODE_SIZE;
293         }
294
295         while(stack.size()) {
296                 BVHStackEntry e = stack.back();
297                 stack.pop_back();
298
299                 if(e.node->is_leaf()) {
300                         /* leaf node */
301                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
302                         pack_leaf(e, leaf);
303                 }
304                 else {
305                         /* Inner node. */
306                         const BVHNode *node = e.node;
307                         const BVHNode *node0 = node->get_child(0);
308                         const BVHNode *node1 = node->get_child(1);
309                         /* Collect nodes. */
310                         const BVHNode *nodes[8];
311                         int numnodes = 0;
312                         if(node0->is_leaf()) {
313                                 nodes[numnodes++] = node0;
314                         }
315                         else {
316                                 const BVHNode *node00 = node0->get_child(0),
317                                               *node01 = node0->get_child(1);
318                                 if(node00->is_leaf()) {
319                                         nodes[numnodes++] = node00;
320                                 }
321                                 else {
322                                         nodes[numnodes++] = node00->get_child(0);
323                                         nodes[numnodes++] = node00->get_child(1);
324                                 }
325                                 if(node01->is_leaf()) {
326                                         nodes[numnodes++] = node01;
327                                 }
328                                 else {
329                                         nodes[numnodes++] = node01->get_child(0);
330                                         nodes[numnodes++] = node01->get_child(1);
331                                 }
332                         }
333                         if(node1->is_leaf()) {
334                                 nodes[numnodes++] = node1;
335                         }
336                         else {
337                                 const BVHNode *node10 = node1->get_child(0),
338                                               *node11 = node1->get_child(1);
339                                 if(node10->is_leaf()) {
340                                         nodes[numnodes++] = node10;
341                                 }
342                                 else {
343                                         nodes[numnodes++] = node10->get_child(0);
344                                         nodes[numnodes++] = node10->get_child(1);
345                                 }
346                                 if(node11->is_leaf()) {
347                                         nodes[numnodes++] = node11;
348                                 }
349                                 else {
350                                         nodes[numnodes++] = node11->get_child(0);
351                                         nodes[numnodes++] = node11->get_child(1);
352                                 }
353                         }
354                         /* Push entries on the stack. */
355                         for(int i = 0; i < numnodes; ++i) {
356                                 int idx;
357                                 if(nodes[i]->is_leaf()) {
358                                         idx = nextLeafNodeIdx++;
359                                 }
360                                 else {
361                                         idx = nextNodeIdx;
362                                         nextNodeIdx += node_is_unaligned(nodes[i], bvh8)
363                                                 ? BVH_UNALIGNED_ONODE_SIZE
364                                                 : BVH_ONODE_SIZE;
365                                 }
366                                 stack.push_back(BVHStackEntry(nodes[i], idx));
367                         }
368                         /* Set node. */
369                         pack_inner(e, &stack[stack.size() - numnodes], numnodes);
370                 }
371         }
372         assert(node_size == nextNodeIdx);
373         /* Root index to start traversal at, to handle case of single leaf node. */
374         pack.root_index = (root->is_leaf()) ? -1 : 0;
375 }
376
377 void BVH8::refit_nodes()
378 {
379         assert(!params.top_level);
380
381         BoundBox bbox = BoundBox::empty;
382         uint visibility = 0;
383         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
384 }
385
386 void BVH8::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
387 {
388         if(leaf) {
389                 int4 *data = &pack.leaf_nodes[idx];
390                 int4 c = data[0];
391                 /* Refit leaf node. */
392                 for(int prim = c.x; prim < c.y; prim++) {
393                         int pidx = pack.prim_index[prim];
394                         int tob = pack.prim_object[prim];
395                         Object *ob = objects[tob];
396
397                         if(pidx == -1) {
398                                 /* Object instance. */
399                                 bbox.grow(ob->bounds);
400                         }
401                         else {
402                                 /* Primitives. */
403                                 const Mesh *mesh = ob->mesh;
404
405                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
406                                         /* Curves. */
407                                         int str_offset = (params.top_level) ? mesh->curve_offset : 0;
408                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
409                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
410
411                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
412
413                                         visibility |= PATH_RAY_CURVE;
414
415                                         /* Motion curves. */
416                                         if(mesh->use_motion_blur) {
417                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
418
419                                                 if(attr) {
420                                                         size_t mesh_size = mesh->curve_keys.size();
421                                                         size_t steps = mesh->motion_steps - 1;
422                                                         float3 *key_steps = attr->data_float3();
423
424                                                         for(size_t i = 0; i < steps; i++) {
425                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
426                                                         }
427                                                 }
428                                         }
429                                 }
430                                 else {
431                                         /* Triangles. */
432                                         int tri_offset = (params.top_level) ? mesh->tri_offset : 0;
433                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
434                                         const float3 *vpos = &mesh->verts[0];
435
436                                         triangle.bounds_grow(vpos, bbox);
437
438                                         /* Motion triangles. */
439                                         if(mesh->use_motion_blur) {
440                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
441
442                                                 if(attr) {
443                                                         size_t mesh_size = mesh->verts.size();
444                                                         size_t steps = mesh->motion_steps - 1;
445                                                         float3 *vert_steps = attr->data_float3();
446
447                                                         for(size_t i = 0; i < steps; i++) {
448                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
449                                                         }
450                                                 }
451                                         }
452                                 }
453                         }
454
455                         visibility |= ob->visibility;
456                 }
457
458                 float4 leaf_data[BVH_ONODE_LEAF_SIZE];
459                 leaf_data[0].x = __int_as_float(c.x);
460                 leaf_data[0].y = __int_as_float(c.y);
461                 leaf_data[0].z = __uint_as_float(visibility);
462                 leaf_data[0].w = __uint_as_float(c.w);
463                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_ONODE_LEAF_SIZE);
464         }
465         else {
466                 float8 *data = (float8*)&pack.nodes[idx];
467                 bool is_unaligned = (__float_as_uint(data[0].a) & PATH_RAY_NODE_UNALIGNED) != 0;
468                 /* Refit inner node, set bbox from children. */
469                 BoundBox child_bbox[8] = { BoundBox::empty, BoundBox::empty,
470                                            BoundBox::empty, BoundBox::empty,
471                                            BoundBox::empty, BoundBox::empty,
472                                            BoundBox::empty, BoundBox::empty };
473                 int child[8];
474                 uint child_visibility[8] = { 0 };
475                 int num_nodes = 0;
476
477                 for(int i = 0; i < 8; ++i) {
478                         child[i] = __float_as_int(data[(is_unaligned) ? 13: 7][i]);
479
480                         if(child[i] != 0) {
481                                 refit_node((child[i] < 0)? -child[i]-1: child[i], (child[i] < 0),
482                                            child_bbox[i], child_visibility[i]);
483                                 ++num_nodes;
484                                 bbox.grow(child_bbox[i]);
485                                 visibility |= child_visibility[i];
486                         }
487                 }
488
489                 if(is_unaligned) {
490                         Transform aligned_space[8] = { transform_identity(), transform_identity(),
491                                                        transform_identity(), transform_identity(),
492                                                        transform_identity(), transform_identity(),
493                                                        transform_identity(), transform_identity()};
494                         pack_unaligned_node(idx,
495                                             aligned_space,
496                                             child_bbox,
497                                             child,
498                                             visibility,
499                                             0.0f,
500                                             1.0f,
501                                             num_nodes);
502                 }
503                 else {
504                         pack_aligned_node(idx,
505                                           child_bbox,
506                                           child,
507                                           visibility,
508                                           0.0f,
509                                           1.0f,
510                                           num_nodes);
511                 }
512         }
513 }
514
515 CCL_NAMESPACE_END