intern/cycles/kernel/geom/geom_qbvh_volume_all.h

   1 /*
   2  * Adapted from code Copyright 2009-2010 NVIDIA Corporation,
   3  * and code copyright 2009-2012 Intel Corporation
   4  *
   5  * Modifications Copyright 2011-2014, Blender Foundation.
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  * http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 /* This is a template BVH traversal function for volumes, where
  21  * various features can be enabled/disabled. This way we can compile optimized
  22  * versions for each case without new features slowing things down.
  23  *
  24  * BVH_INSTANCING: object instancing
  25  * BVH_HAIR: hair curve rendering
  26  * BVH_MOTION: motion blur rendering
  27  *
  28  */
  29
  30 ccl_device uint BVH_FUNCTION_FULL_NAME(QBVH)(KernelGlobals *kg,
  31                                              const Ray *ray,
  32                                              Intersection *isect_array,
  33                                              const uint max_hits)
  34 {
  35         /* TODO(sergey):
  36          * - Test if pushing distance on the stack helps.
  37          * - Likely and unlikely for if() statements.
  38          * - Test restrict attribute for pointers.
  39          */
  40
  41         /* Traversal stack in CUDA thread-local memory. */
  42         QBVHStackItem traversalStack[BVH_QSTACK_SIZE];
  43         traversalStack[0].addr = ENTRYPOINT_SENTINEL;
  44
  45         /* Traversal variables in registers. */
  46         int stackPtr = 0;
  47         int nodeAddr = kernel_data.bvh.root;
  48
  49         /* Ray parameters in registers. */
  50         const float tmax = ray->t;
  51         float3 P = ray->P;
  52         float3 dir = bvh_clamp_direction(ray->D);
  53         float3 idir = bvh_inverse_direction(dir);
  54         int object = OBJECT_NONE;
  55         float isect_t = tmax;
  56
  57         const uint visibility = PATH_RAY_ALL_VISIBILITY;
  58
  59 #if BVH_FEATURE(BVH_MOTION)
  60         Transform ob_itfm;
  61 #endif
  62
  63         uint num_hits = 0;
  64         isect_array->t = tmax;
  65
  66 #ifndef __KERNEL_SSE41__
  67         if(!isfinite(P.x)) {
  68                 return false;
  69         }
  70 #endif
  71
  72 #if BVH_FEATURE(BVH_INSTANCING)
  73         int num_hits_in_instance = 0;
  74 #endif
  75
  76         ssef tnear(0.0f), tfar(isect_t);
  77         sse3f idir4(ssef(idir.x), ssef(idir.y), ssef(idir.z));
  78
  79 #ifdef __KERNEL_AVX2__
  80         float3 P_idir = P*idir;
  81         sse3f P_idir4 = sse3f(P_idir.x, P_idir.y, P_idir.z);
  82 #else
  83         sse3f org = sse3f(ssef(P.x), ssef(P.y), ssef(P.z));
  84 #endif
  85
  86         /* Offsets to select the side that becomes the lower or upper bound. */
  87         int near_x, near_y, near_z;
  88         int far_x, far_y, far_z;
  89
  90         if(idir.x >= 0.0f) { near_x = 0; far_x = 1; } else { near_x = 1; far_x = 0; }
  91         if(idir.y >= 0.0f) { near_y = 2; far_y = 3; } else { near_y = 3; far_y = 2; }
  92         if(idir.z >= 0.0f) { near_z = 4; far_z = 5; } else { near_z = 5; far_z = 4; }
  93
  94         IsectPrecalc isect_precalc;
  95         triangle_intersect_precalc(dir, &isect_precalc);
  96
  97         /* Traversal loop. */
  98         do {
  99                 do {
 100                         /* Traverse internal nodes. */
 101                         while(nodeAddr >= 0 && nodeAddr != ENTRYPOINT_SENTINEL) {
 102                                 ssef dist;
 103                                 int traverseChild = qbvh_node_intersect(kg,
 104                                                                         tnear,
 105                                                                         tfar,
 106 #ifdef __KERNEL_AVX2__
 107                                                                         P_idir4,
 108 #else
 109                                                                         org,
 110 #endif
 111                                                                         idir4,
 112                                                                         near_x, near_y, near_z,
 113                                                                         far_x, far_y, far_z,
 114                                                                         nodeAddr,
 115                                                                         &dist);
 116
 117                                 if(traverseChild != 0) {
 118                                         float4 cnodes = kernel_tex_fetch(__bvh_nodes, nodeAddr*BVH_QNODE_SIZE+6);
 119
 120                                         /* One child is hit, continue with that child. */
 121                                         int r = __bscf(traverseChild);
 122                                         if(traverseChild == 0) {
 123                                                 nodeAddr = __float_as_int(cnodes[r]);
 124                                                 continue;
 125                                         }
 126
 127                                         /* Two children are hit, push far child, and continue with
 128                                          * closer child.
 129                                          */
 130                                         int c0 = __float_as_int(cnodes[r]);
 131                                         float d0 = ((float*)&dist)[r];
 132                                         r = __bscf(traverseChild);
 133                                         int c1 = __float_as_int(cnodes[r]);
 134                                         float d1 = ((float*)&dist)[r];
 135                                         if(traverseChild == 0) {
 136                                                 if(d1 < d0) {
 137                                                         nodeAddr = c1;
 138                                                         ++stackPtr;
 139                                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 140                                                         traversalStack[stackPtr].addr = c0;
 141                                                         traversalStack[stackPtr].dist = d0;
 142                                                         continue;
 143                                                 }
 144                                                 else {
 145                                                         nodeAddr = c0;
 146                                                         ++stackPtr;
 147                                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 148                                                         traversalStack[stackPtr].addr = c1;
 149                                                         traversalStack[stackPtr].dist = d1;
 150                                                         continue;
 151                                                 }
 152                                         }
 153
 154                                         /* Here starts the slow path for 3 or 4 hit children. We push
 155                                          * all nodes onto the stack to sort them there.
 156                                          */
 157                                         ++stackPtr;
 158                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 159                                         traversalStack[stackPtr].addr = c1;
 160                                         traversalStack[stackPtr].dist = d1;
 161                                         ++stackPtr;
 162                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 163                                         traversalStack[stackPtr].addr = c0;
 164                                         traversalStack[stackPtr].dist = d0;
 165
 166                                         /* Three children are hit, push all onto stack and sort 3
 167                                          * stack items, continue with closest child.
 168                                          */
 169                                         r = __bscf(traverseChild);
 170                                         int c2 = __float_as_int(cnodes[r]);
 171                                         float d2 = ((float*)&dist)[r];
 172                                         if(traverseChild == 0) {
 173                                                 ++stackPtr;
 174                                                 kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 175                                                 traversalStack[stackPtr].addr = c2;
 176                                                 traversalStack[stackPtr].dist = d2;
 177                                                 qbvh_stack_sort(&traversalStack[stackPtr],
 178                                                                 &traversalStack[stackPtr - 1],
 179                                                                 &traversalStack[stackPtr - 2]);
 180                                                 nodeAddr = traversalStack[stackPtr].addr;
 181                                                 --stackPtr;
 182                                                 continue;
 183                                         }
 184
 185                                         /* Four children are hit, push all onto stack and sort 4
 186                                          * stack items, continue with closest child.
 187                                          */
 188                                         r = __bscf(traverseChild);
 189                                         int c3 = __float_as_int(cnodes[r]);
 190                                         float d3 = ((float*)&dist)[r];
 191                                         ++stackPtr;
 192                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 193                                         traversalStack[stackPtr].addr = c3;
 194                                         traversalStack[stackPtr].dist = d3;
 195                                         ++stackPtr;
 196                                         kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 197                                         traversalStack[stackPtr].addr = c2;
 198                                         traversalStack[stackPtr].dist = d2;
 199                                         qbvh_stack_sort(&traversalStack[stackPtr],
 200                                                         &traversalStack[stackPtr - 1],
 201                                                         &traversalStack[stackPtr - 2],
 202                                                         &traversalStack[stackPtr - 3]);
 203                                 }
 204
 205                                 nodeAddr = traversalStack[stackPtr].addr;
 206                                 --stackPtr;
 207                         }
 208
 209                         /* If node is leaf, fetch triangle list. */
 210                         if(nodeAddr < 0) {
 211                                 float4 leaf = kernel_tex_fetch(__bvh_leaf_nodes, (-nodeAddr-1)*BVH_QNODE_LEAF_SIZE);
 212                                 int primAddr = __float_as_int(leaf.x);
 213
 214 #if BVH_FEATURE(BVH_INSTANCING)
 215                                 if(primAddr >= 0) {
 216 #endif
 217                                         int primAddr2 = __float_as_int(leaf.y);
 218                                         const uint type = __float_as_int(leaf.w);
 219                                         const uint p_type = type & PRIMITIVE_ALL;
 220                                         bool hit;
 221
 222                                         /* Pop. */
 223                                         nodeAddr = traversalStack[stackPtr].addr;
 224                                         --stackPtr;
 225
 226                                         /* Primitive intersection. */
 227                                         switch(p_type) {
 228                                                 case PRIMITIVE_TRIANGLE: {
 229                                                         for(; primAddr < primAddr2; primAddr++) {
 230                                                                 kernel_assert(kernel_tex_fetch(__prim_type, primAddr) == type);
 231                                                                 /* Only primitives from volume object. */
 232                                                                 uint tri_object = (object == OBJECT_NONE)? kernel_tex_fetch(__prim_object, primAddr): object;
 233                                                                 int object_flag = kernel_tex_fetch(__object_flag, tri_object);
 234                                                                 if((object_flag & SD_OBJECT_HAS_VOLUME) == 0) {
 235                                                                         continue;
 236                                                                 }
 237                                                                 /* Intersect ray against primitive. */
 238                                                                 hit = triangle_intersect(kg, &isect_precalc, isect_array, P, visibility, object, primAddr);
 239                                                                 if(hit) {
 240                                                                         /* Move on to next entry in intersections array. */
 241                                                                         isect_array++;
 242                                                                         num_hits++;
 243 #if BVH_FEATURE(BVH_INSTANCING)
 244                                                                         num_hits_in_instance++;
 245 #endif
 246                                                                         isect_array->t = isect_t;
 247                                                                         if(num_hits == max_hits) {
 248 #if BVH_FEATURE(BVH_INSTANCING)
 249 #  if BVH_FEATURE(BVH_MOTION)
 250                                                                                 float t_fac = 1.0f / len(transform_direction(&ob_itfm, dir));
 251 #  else
 252                                                                                 Transform itfm = object_fetch_transform(kg, object, OBJECT_INVERSE_TRANSFORM);
 253                                                                                 float t_fac = 1.0f / len(transform_direction(&itfm, dir));
 254 #  endif
 255                                                                                 for(int i = 0; i < num_hits_in_instance; i++) {
 256                                                                                         (isect_array-i-1)->t *= t_fac;
 257                                                                                 }
 258 #endif  /* BVH_FEATURE(BVH_INSTANCING) */
 259                                                                                 return num_hits;
 260                                                                         }
 261                                                                 }
 262                                                         }
 263                                                         break;
 264                                                 }
 265 #if BVH_FEATURE(BVH_MOTION)
 266                                                 case PRIMITIVE_MOTION_TRIANGLE: {
 267                                                         for(; primAddr < primAddr2; primAddr++) {
 268                                                                 kernel_assert(kernel_tex_fetch(__prim_type, primAddr) == type);
 269                                                                 /* Only primitives from volume object. */
 270                                                                 uint tri_object = (object == OBJECT_NONE)? kernel_tex_fetch(__prim_object, primAddr): object;
 271                                                                 int object_flag = kernel_tex_fetch(__object_flag, tri_object);
 272                                                                 if((object_flag & SD_OBJECT_HAS_VOLUME) == 0) {
 273                                                                         continue;
 274                                                                 }
 275                                                                 /* Intersect ray against primitive. */
 276                                                                 hit = motion_triangle_intersect(kg, isect_array, P, dir, ray->time, visibility, object, primAddr);
 277                                                                 if(hit) {
 278                                                                         /* Move on to next entry in intersections array. */
 279                                                                         isect_array++;
 280                                                                         num_hits++;
 281 #  if BVH_FEATURE(BVH_INSTANCING)
 282                                                                         num_hits_in_instance++;
 283 #  endif
 284                                                                         isect_array->t = isect_t;
 285                                                                         if(num_hits == max_hits) {
 286 #  if BVH_FEATURE(BVH_INSTANCING)
 287 #    if BVH_FEATURE(BVH_MOTION)
 288                                                                                 float t_fac = 1.0f / len(transform_direction(&ob_itfm, dir));
 289 #    else
 290                                                                                 Transform itfm = object_fetch_transform(kg, object, OBJECT_INVERSE_TRANSFORM);
 291                                                                                 float t_fac = 1.0f / len(transform_direction(&itfm, dir));
 292 #    endif
 293                                                                                 for(int i = 0; i < num_hits_in_instance; i++) {
 294                                                                                         (isect_array-i-1)->t *= t_fac;
 295                                                                                 }
 296 #  endif  /* BVH_FEATURE(BVH_INSTANCING) */
 297                                                                                 return num_hits;
 298                                                                         }
 299                                                                 }
 300                                                         }
 301                                                         break;
 302                                                 }
 303 #endif
 304 #if BVH_FEATURE(BVH_HAIR)
 305                                                 case PRIMITIVE_CURVE:
 306                                                 case PRIMITIVE_MOTION_CURVE: {
 307                                                         for(; primAddr < primAddr2; primAddr++) {
 308                                                                 kernel_assert(kernel_tex_fetch(__prim_type, primAddr) == type);
 309                                                                 /* Only primitives from volume object. */
 310                                                                 uint tri_object = (object == OBJECT_NONE)? kernel_tex_fetch(__prim_object, primAddr): object;
 311                                                                 int object_flag = kernel_tex_fetch(__object_flag, tri_object);
 312                                                                 if((object_flag & SD_OBJECT_HAS_VOLUME) == 0) {
 313                                                                         continue;
 314                                                                 }
 315                                                                 /* Intersect ray against primitive. */
 316                                                                 if(kernel_data.curve.curveflags & CURVE_KN_INTERPOLATE)
 317                                                                         hit = bvh_cardinal_curve_intersect(kg, isect_array, P, dir, visibility, object, primAddr, ray->time, type, NULL, 0, 0);
 318                                                                 else
 319                                                                         hit = bvh_curve_intersect(kg, isect_array, P, dir, visibility, object, primAddr, ray->time, type, NULL, 0, 0);
 320                                                                 if(hit) {
 321                                                                         /* Move on to next entry in intersections array. */
 322                                                                         isect_array++;
 323                                                                         num_hits++;
 324 #  if BVH_FEATURE(BVH_INSTANCING)
 325                                                                         num_hits_in_instance++;
 326 #  endif
 327                                                                         isect_array->t = isect_t;
 328                                                                         if(num_hits == max_hits) {
 329 #  if BVH_FEATURE(BVH_INSTANCING)
 330 #    if BVH_FEATURE(BVH_MOTION)
 331                                                                                 float t_fac = 1.0f / len(transform_direction(&ob_itfm, dir));
 332 #    else
 333                                                                                 Transform itfm = object_fetch_transform(kg, object, OBJECT_INVERSE_TRANSFORM);
 334                                                                                 float t_fac = 1.0f / len(transform_direction(&itfm, dir));
 335 #    endif
 336                                                                                 for(int i = 0; i < num_hits_in_instance; i++) {
 337                                                                                         (isect_array-i-1)->t *= t_fac;
 338                                                                                 }
 339 #  endif  /* BVH_FEATURE(BVH_INSTANCING) */
 340                                                                                 return num_hits;
 341                                                                         }
 342                                                                 }
 343                                                         }
 344                                                         break;
 345                                                 }
 346 #endif  /* BVH_HAIR */
 347                                         }
 348                                 }
 349 #if BVH_FEATURE(BVH_INSTANCING)
 350                                 else {
 351                                         /* Instance push. */
 352                                         object = kernel_tex_fetch(__prim_object, -primAddr-1);
 353                                         int object_flag = kernel_tex_fetch(__object_flag, object);
 354
 355                                         if(object_flag & SD_OBJECT_HAS_VOLUME) {
 356
 357 #  if BVH_FEATURE(BVH_MOTION)
 358                                                 bvh_instance_motion_push(kg, object, ray, &P, &dir, &idir, &isect_t, &ob_itfm);
 359 #  else
 360                                                 bvh_instance_push(kg, object, ray, &P, &dir, &idir, &isect_t);
 361 #  endif
 362
 363                                                 if(idir.x >= 0.0f) { near_x = 0; far_x = 1; } else { near_x = 1; far_x = 0; }
 364                                                 if(idir.y >= 0.0f) { near_y = 2; far_y = 3; } else { near_y = 3; far_y = 2; }
 365                                                 if(idir.z >= 0.0f) { near_z = 4; far_z = 5; } else { near_z = 5; far_z = 4; }
 366                                                 tfar = ssef(isect_t);
 367                                                 idir4 = sse3f(ssef(idir.x), ssef(idir.y), ssef(idir.z));
 368 #  ifdef __KERNEL_AVX2__
 369                                                 P_idir = P*idir;
 370                                                 P_idir4 = sse3f(P_idir.x, P_idir.y, P_idir.z);
 371 #  else
 372                                                 org = sse3f(ssef(P.x), ssef(P.y), ssef(P.z));
 373 #  endif
 374                                                 triangle_intersect_precalc(dir, &isect_precalc);
 375                                                 num_hits_in_instance = 0;
 376                                                 isect_array->t = isect_t;
 377
 378                                                 ++stackPtr;
 379                                                 kernel_assert(stackPtr < BVH_QSTACK_SIZE);
 380                                                 traversalStack[stackPtr].addr = ENTRYPOINT_SENTINEL;
 381
 382                                                 nodeAddr = kernel_tex_fetch(__object_node, object);
 383                                         }
 384                                         else {
 385                                                 /* Pop. */
 386                                                 object = OBJECT_NONE;
 387                                                 nodeAddr = traversalStack[stackPtr].addr;
 388                                                 --stackPtr;
 389                                         }
 390                                 }
 391                         }
 392 #endif  /* FEATURE(BVH_INSTANCING) */
 393                 } while(nodeAddr != ENTRYPOINT_SENTINEL);
 394
 395 #if BVH_FEATURE(BVH_INSTANCING)
 396                 if(stackPtr >= 0) {
 397                         kernel_assert(object != OBJECT_NONE);
 398
 399                         /* Instance pop. */
 400                         if(num_hits_in_instance) {
 401                                 float t_fac;
 402 #  if BVH_FEATURE(BVH_MOTION)
 403                                 bvh_instance_motion_pop_factor(kg, object, ray, &P, &dir, &idir, &t_fac, &ob_itfm);
 404 #  else
 405                                 bvh_instance_pop_factor(kg, object, ray, &P, &dir, &idir, &t_fac);
 406 #  endif
 407                                 triangle_intersect_precalc(dir, &isect_precalc);
 408                                 /* Scale isect->t to adjust for instancing. */
 409                                 for(int i = 0; i < num_hits_in_instance; i++) {
 410                                         (isect_array-i-1)->t *= t_fac;
 411                                 }
 412                         }
 413                         else {
 414                                 float ignore_t = FLT_MAX;
 415 #  if BVH_FEATURE(BVH_MOTION)
 416                                 bvh_instance_motion_pop(kg, object, ray, &P, &dir, &idir, &ignore_t, &ob_itfm);
 417 #  else
 418                                 bvh_instance_pop(kg, object, ray, &P, &dir, &idir, &ignore_t);
 419 #  endif
 420                                 triangle_intersect_precalc(dir, &isect_precalc);
 421                         }
 422
 423                         if(idir.x >= 0.0f) { near_x = 0; far_x = 1; } else { near_x = 1; far_x = 0; }
 424                         if(idir.y >= 0.0f) { near_y = 2; far_y = 3; } else { near_y = 3; far_y = 2; }
 425                         if(idir.z >= 0.0f) { near_z = 4; far_z = 5; } else { near_z = 5; far_z = 4; }
 426                         tfar = ssef(isect_t);
 427                         idir4 = sse3f(ssef(idir.x), ssef(idir.y), ssef(idir.z));
 428 #  ifdef __KERNEL_AVX2__
 429                         P_idir = P*idir;
 430                         P_idir4 = sse3f(P_idir.x, P_idir.y, P_idir.z);
 431 #  else
 432                         org = sse3f(ssef(P.x), ssef(P.y), ssef(P.z));
 433 #  endif
 434                         triangle_intersect_precalc(dir, &isect_precalc);
 435                         isect_t = tmax;
 436                         isect_array->t = isect_t;
 437
 438                         object = OBJECT_NONE;
 439                         nodeAddr = traversalStack[stackPtr].addr;
 440                         --stackPtr;
 441                 }
 442 #endif  /* FEATURE(BVH_INSTANCING) */
 443         } while(nodeAddr != ENTRYPOINT_SENTINEL);
 444
 445         return num_hits;
 446 }