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] = NAN;
 226                 data[2][i] = NAN;
 227                 data[3][i] = NAN;
 228
 229                 data[4][i] = NAN;
 230                 data[5][i] = NAN;
 231                 data[6][i] = NAN;
 232
 233                 data[7][i] = NAN;
 234                 data[8][i] = NAN;
 235                 data[9][i] = NAN;
 236
 237                 data[10][i] = NAN;
 238                 data[11][i] = NAN;
 239                 data[12][i] = NAN;
 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