70d003d938aaee47d73446801fe0c0f2d3112d4c
[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         for(int i = 0; i < num; i++) {
128                 float3 bb_min = bounds[i].min;
129                 float3 bb_max = bounds[i].max;
130
131                 data[1][i] = bb_min.x;
132                 data[2][i] = bb_max.x;
133                 data[3][i] = bb_min.y;
134                 data[4][i] = bb_max.y;
135                 data[5][i] = bb_min.z;
136                 data[6][i] = bb_max.z;
137
138                 data[7][i] = __int_as_float(child[i]);
139         }
140
141         for(int i = num; i < 8; i++) {
142                 /* We store BB which would never be recorded as intersection
143                 * so kernel might safely assume there are always 4 child nodes.
144                 */
145                 data[1][i] = FLT_MAX;
146                 data[2][i] = -FLT_MAX;
147
148                 data[3][i] = FLT_MAX;
149                 data[4][i] = -FLT_MAX;
150
151                 data[5][i] = FLT_MAX;
152                 data[6][i] = -FLT_MAX;
153
154                 data[7][i] = __int_as_float(0);
155         }
156         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_ONODE_SIZE);
157 }
158
159 void BVH8::pack_unaligned_inner(const BVHStackEntry& e,
160                                 const BVHStackEntry *en,
161                                 int num)
162 {
163         Transform aligned_space[8];
164         BoundBox bounds[8];
165         int child[8];
166         for(int i = 0; i < num; ++i) {
167                 aligned_space[i] = en[i].node->get_aligned_space();
168                 bounds[i] = en[i].node->bounds;
169                 child[i] = en[i].encodeIdx();
170         }
171         pack_unaligned_node(e.idx,
172                             aligned_space,
173                             bounds,
174                             child,
175                             e.node->visibility,
176                             e.node->time_from,
177                             e.node->time_to,
178                             num);
179 }
180
181 void BVH8::pack_unaligned_node(int idx,
182                                const Transform *aligned_space,
183                                const BoundBox *bounds,
184                                const int *child,
185                                const uint visibility,
186                                const float time_from,
187                                const float time_to,
188                                const int num)
189 {
190         float8 data[BVH_UNALIGNED_ONODE_SIZE];
191         memset(data, 0, sizeof(data));
192         data[0].a = __uint_as_float(visibility | PATH_RAY_NODE_UNALIGNED);
193         data[0].b = time_from;
194         data[0].c = time_to;
195
196         for(int i = 0; i < num; i++) {
197                 Transform space = BVHUnaligned::compute_node_transform(
198                         bounds[i],
199                         aligned_space[i]);
200
201                 data[1][i] = space.x.x;
202                 data[2][i] = space.x.y;
203                 data[3][i] = space.x.z;
204
205                 data[4][i] = space.y.x;
206                 data[5][i] = space.y.y;
207                 data[6][i] = space.y.z;
208
209                 data[7][i] = space.z.x;
210                 data[8][i] = space.z.y;
211                 data[9][i] = space.z.z;
212
213                 data[10][i] = space.x.w;
214                 data[11][i] = space.y.w;
215                 data[12][i] = space.z.w;
216
217                 data[13][i] = __int_as_float(child[i]);
218         }
219
220         for(int i = num; i < 8; i++) {
221                 /* We store BB which would never be recorded as intersection
222                  * so kernel might safely assume there are always 4 child nodes.
223                  */
224
225                 data[1][i] = 1.0f;
226                 data[2][i] = 0.0f;
227                 data[3][i] = 0.0f;
228
229                 data[4][i] = 0.0f;
230                 data[5][i] = 0.0f;
231                 data[6][i] = 0.0f;
232
233                 data[7][i] = 0.0f;
234                 data[8][i] = 0.0f;
235                 data[9][i] = 0.0f;
236
237                 data[10][i] = -FLT_MAX;
238                 data[11][i] = -FLT_MAX;
239                 data[12][i] = -FLT_MAX;
240
241                 data[13][i] = __int_as_float(0);
242         }
243
244         memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_ONODE_SIZE);
245 }
246
247 /* Quad SIMD Nodes */
248
249 void BVH8::pack_nodes(const BVHNode *root)
250 {
251         /* Calculate size of the arrays required. */
252         const size_t num_nodes = root->getSubtreeSize(BVH_STAT_ONODE_COUNT);
253         const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
254         assert(num_leaf_nodes <= num_nodes);
255         const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
256         size_t node_size;
257         if(params.use_unaligned_nodes) {
258                 const size_t num_unaligned_nodes =
259                         root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_ONODE_COUNT);
260                 node_size = (num_unaligned_nodes * BVH_UNALIGNED_ONODE_SIZE) +
261                         (num_inner_nodes - num_unaligned_nodes) * BVH_ONODE_SIZE;
262         }
263         else {
264                 node_size = num_inner_nodes * BVH_ONODE_SIZE;
265         }
266         /* Resize arrays. */
267         pack.nodes.clear();
268         pack.leaf_nodes.clear();
269         /* For top level BVH, first merge existing BVH's so we know the offsets. */
270         if(params.top_level) {
271                 pack_instances(node_size, num_leaf_nodes*BVH_ONODE_LEAF_SIZE);
272         }
273         else {
274                 pack.nodes.resize(node_size);
275                 pack.leaf_nodes.resize(num_leaf_nodes*BVH_ONODE_LEAF_SIZE);
276         }
277
278         int nextNodeIdx = 0, nextLeafNodeIdx = 0;
279
280         vector<BVHStackEntry> stack;
281         stack.reserve(BVHParams::MAX_DEPTH*2);
282         if(root->is_leaf()) {
283                 stack.push_back(BVHStackEntry(root, nextLeafNodeIdx++));
284         }
285         else {
286                 stack.push_back(BVHStackEntry(root, nextNodeIdx));
287                 nextNodeIdx += node_is_unaligned(root, bvh8)
288                                    ? BVH_UNALIGNED_ONODE_SIZE
289                                    : BVH_ONODE_SIZE;
290         }
291
292         while(stack.size()) {
293                 BVHStackEntry e = stack.back();
294                 stack.pop_back();
295
296                 if(e.node->is_leaf()) {
297                         /* leaf node */
298                         const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
299                         pack_leaf(e, leaf);
300                 }
301                 else {
302                         /* Inner node. */
303                         const BVHNode *node = e.node;
304                         const BVHNode *node0 = node->get_child(0);
305                         const BVHNode *node1 = node->get_child(1);
306                         /* Collect nodes. */
307                         const BVHNode *nodes[8];
308                         int numnodes = 0;
309                         if(node0->is_leaf()) {
310                                 nodes[numnodes++] = node0;
311                         }
312                         else {
313                                 const BVHNode *node00 = node0->get_child(0),
314                                               *node01 = node0->get_child(1);
315                                 if(node00->is_leaf()) {
316                                         nodes[numnodes++] = node00;
317                                 }
318                                 else {
319                                         nodes[numnodes++] = node00->get_child(0);
320                                         nodes[numnodes++] = node00->get_child(1);
321                                 }
322                                 if(node01->is_leaf()) {
323                                         nodes[numnodes++] = node01;
324                                 }
325                                 else {
326                                         nodes[numnodes++] = node01->get_child(0);
327                                         nodes[numnodes++] = node01->get_child(1);
328                                 }
329                         }
330                         if(node1->is_leaf()) {
331                                 nodes[numnodes++] = node1;
332                         }
333                         else {
334                                 const BVHNode *node10 = node1->get_child(0),
335                                               *node11 = node1->get_child(1);
336                                 if(node10->is_leaf()) {
337                                         nodes[numnodes++] = node10;
338                                 }
339                                 else {
340                                         nodes[numnodes++] = node10->get_child(0);
341                                         nodes[numnodes++] = node10->get_child(1);
342                                 }
343                                 if(node11->is_leaf()) {
344                                         nodes[numnodes++] = node11;
345                                 }
346                                 else {
347                                         nodes[numnodes++] = node11->get_child(0);
348                                         nodes[numnodes++] = node11->get_child(1);
349                                 }
350                         }
351                         /* Push entries on the stack. */
352                         for(int i = 0; i < numnodes; ++i) {
353                                 int idx;
354                                 if(nodes[i]->is_leaf()) {
355                                         idx = nextLeafNodeIdx++;
356                                 }
357                                 else {
358                                         idx = nextNodeIdx;
359                                         nextNodeIdx += node_is_unaligned(nodes[i], bvh8)
360                                                 ? BVH_UNALIGNED_ONODE_SIZE
361                                                 : BVH_ONODE_SIZE;
362                                 }
363                                 stack.push_back(BVHStackEntry(nodes[i], idx));
364                         }
365                         /* Set node. */
366                         pack_inner(e, &stack[stack.size() - numnodes], numnodes);
367                 }
368         }
369         assert(node_size == nextNodeIdx);
370         /* Root index to start traversal at, to handle case of single leaf node. */
371         pack.root_index = (root->is_leaf()) ? -1 : 0;
372 }
373
374 void BVH8::refit_nodes()
375 {
376         assert(!params.top_level);
377
378         BoundBox bbox = BoundBox::empty;
379         uint visibility = 0;
380         refit_node(0, (pack.root_index == -1)? true: false, bbox, visibility);
381 }
382
383 void BVH8::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
384 {
385         if(leaf) {
386                 int4 *data = &pack.leaf_nodes[idx];
387                 int4 c = data[0];
388                 /* Refit leaf node. */
389                 for(int prim = c.x; prim < c.y; prim++) {
390                         int pidx = pack.prim_index[prim];
391                         int tob = pack.prim_object[prim];
392                         Object *ob = objects[tob];
393
394                         if(pidx == -1) {
395                                 /* Object instance. */
396                                 bbox.grow(ob->bounds);
397                         }
398                         else {
399                                 /* Primitives. */
400                                 const Mesh *mesh = ob->mesh;
401
402                                 if(pack.prim_type[prim] & PRIMITIVE_ALL_CURVE) {
403                                         /* Curves. */
404                                         int str_offset = (params.top_level) ? mesh->curve_offset : 0;
405                                         Mesh::Curve curve = mesh->get_curve(pidx - str_offset);
406                                         int k = PRIMITIVE_UNPACK_SEGMENT(pack.prim_type[prim]);
407
408                                         curve.bounds_grow(k, &mesh->curve_keys[0], &mesh->curve_radius[0], bbox);
409
410                                         visibility |= PATH_RAY_CURVE;
411
412                                         /* Motion curves. */
413                                         if(mesh->use_motion_blur) {
414                                                 Attribute *attr = mesh->curve_attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
415
416                                                 if(attr) {
417                                                         size_t mesh_size = mesh->curve_keys.size();
418                                                         size_t steps = mesh->motion_steps - 1;
419                                                         float3 *key_steps = attr->data_float3();
420
421                                                         for(size_t i = 0; i < steps; i++) {
422                                                                 curve.bounds_grow(k, key_steps + i*mesh_size, &mesh->curve_radius[0], bbox);
423                                                         }
424                                                 }
425                                         }
426                                 }
427                                 else {
428                                         /* Triangles. */
429                                         int tri_offset = (params.top_level) ? mesh->tri_offset : 0;
430                                         Mesh::Triangle triangle = mesh->get_triangle(pidx - tri_offset);
431                                         const float3 *vpos = &mesh->verts[0];
432
433                                         triangle.bounds_grow(vpos, bbox);
434
435                                         /* Motion triangles. */
436                                         if(mesh->use_motion_blur) {
437                                                 Attribute *attr = mesh->attributes.find(ATTR_STD_MOTION_VERTEX_POSITION);
438
439                                                 if(attr) {
440                                                         size_t mesh_size = mesh->verts.size();
441                                                         size_t steps = mesh->motion_steps - 1;
442                                                         float3 *vert_steps = attr->data_float3();
443
444                                                         for(size_t i = 0; i < steps; i++) {
445                                                                 triangle.bounds_grow(vert_steps + i*mesh_size, bbox);
446                                                         }
447                                                 }
448                                         }
449                                 }
450                         }
451
452                         visibility |= ob->visibility;
453                 }
454
455                 float4 leaf_data[BVH_ONODE_LEAF_SIZE];
456                 leaf_data[0].x = __int_as_float(c.x);
457                 leaf_data[0].y = __int_as_float(c.y);
458                 leaf_data[0].z = __uint_as_float(visibility);
459                 leaf_data[0].w = __uint_as_float(c.w);
460                 memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_ONODE_LEAF_SIZE);
461         }
462         else {
463                 float8 *data = (float8*)&pack.nodes[idx];
464                 bool is_unaligned = (__float_as_uint(data[0].a) & PATH_RAY_NODE_UNALIGNED) != 0;
465                 /* Refit inner node, set bbox from children. */
466                 BoundBox child_bbox[8] = { BoundBox::empty, BoundBox::empty,
467                                            BoundBox::empty, BoundBox::empty,
468                                            BoundBox::empty, BoundBox::empty,
469                                            BoundBox::empty, BoundBox::empty };
470                 int child[8];
471                 uint child_visibility[8] = { 0 };
472                 int num_nodes = 0;
473
474                 for(int i = 0; i < 8; ++i) {
475                         child[i] = __float_as_int(data[(is_unaligned) ? 13: 7][i]);
476
477                         if(child[i] != 0) {
478                                 refit_node((child[i] < 0)? -child[i]-1: child[i], (child[i] < 0),
479                                            child_bbox[i], child_visibility[i]);
480                                 ++num_nodes;
481                                 bbox.grow(child_bbox[i]);
482                                 visibility |= child_visibility[i];
483                         }
484                 }
485
486                 if(is_unaligned) {
487                         Transform aligned_space[8] = { transform_identity(), transform_identity(),
488                                                        transform_identity(), transform_identity(),
489                                                        transform_identity(), transform_identity(),
490                                                        transform_identity(), transform_identity()};
491                         pack_unaligned_node(idx,
492                                             aligned_space,
493                                             child_bbox,
494                                             child,
495                                             visibility,
496                                             0.0f,
497                                             1.0f,
498                                             num_nodes);
499                 }
500                 else {
501                         pack_aligned_node(idx,
502                                           child_bbox,
503                                           child,
504                                           visibility,
505                                           0.0f,
506                                           1.0f,
507                                           num_nodes);
508                 }
509         }
510 }
511
512 CCL_NAMESPACE_END