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