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