Cycles: Cleanup, indentation in preprocessor
[blender.git] / intern / cycles / kernel / bvh / bvh.h
1 /*
2  * Copyright 2011-2013 Blender Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 /* BVH
18  *
19  * Bounding volume hierarchy for ray tracing. We compile different variations
20  * of the same BVH traversal function for faster rendering when some types of
21  * primitives are not needed, using #includes to work around the lack of
22  * C++ templates in OpenCL.
23  *
24  * Originally based on "Understanding the Efficiency of Ray Traversal on GPUs",
25  * the code has been extended and modified to support more primitives and work
26  * with CPU/CUDA/OpenCL. */
27
28 #ifdef __EMBREE__
29 #  include "kernel/bvh/bvh_embree.h"
30 #endif
31
32 CCL_NAMESPACE_BEGIN
33
34 #include "kernel/bvh/bvh_types.h"
35
36 /* Common QBVH functions. */
37 #ifdef __QBVH__
38 #  include "kernel/bvh/qbvh_nodes.h"
39 #  ifdef __KERNEL_AVX2__
40 #    include "kernel/bvh/obvh_nodes.h"
41 #  endif
42 #endif
43
44 /* Regular BVH traversal */
45
46 #include "kernel/bvh/bvh_nodes.h"
47
48 #define BVH_FUNCTION_NAME bvh_intersect
49 #define BVH_FUNCTION_FEATURES 0
50 #include "kernel/bvh/bvh_traversal.h"
51
52 #if defined(__INSTANCING__)
53 #  define BVH_FUNCTION_NAME bvh_intersect_instancing
54 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING
55 #  include "kernel/bvh/bvh_traversal.h"
56 #endif
57
58 #if defined(__HAIR__)
59 #  define BVH_FUNCTION_NAME bvh_intersect_hair
60 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_HAIR_MINIMUM_WIDTH
61 #  include "kernel/bvh/bvh_traversal.h"
62 #endif
63
64 #if defined(__OBJECT_MOTION__)
65 #  define BVH_FUNCTION_NAME bvh_intersect_motion
66 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION
67 #  include "kernel/bvh/bvh_traversal.h"
68 #endif
69
70 #if defined(__HAIR__) && defined(__OBJECT_MOTION__)
71 #  define BVH_FUNCTION_NAME bvh_intersect_hair_motion
72 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_HAIR_MINIMUM_WIDTH|BVH_MOTION
73 #  include "kernel/bvh/bvh_traversal.h"
74 #endif
75
76 /* Subsurface scattering BVH traversal */
77
78 #if defined(__BVH_LOCAL__)
79 #  define BVH_FUNCTION_NAME bvh_intersect_local
80 #  define BVH_FUNCTION_FEATURES BVH_HAIR
81 #  include "kernel/bvh/bvh_local.h"
82
83 #  if defined(__OBJECT_MOTION__)
84 #    define BVH_FUNCTION_NAME bvh_intersect_local_motion
85 #    define BVH_FUNCTION_FEATURES BVH_MOTION|BVH_HAIR
86 #    include "kernel/bvh/bvh_local.h"
87 #  endif
88 #endif  /* __BVH_LOCAL__ */
89
90 /* Volume BVH traversal */
91
92 #if defined(__VOLUME__)
93 #  define BVH_FUNCTION_NAME bvh_intersect_volume
94 #  define BVH_FUNCTION_FEATURES BVH_HAIR
95 #  include "kernel/bvh/bvh_volume.h"
96
97 #  if defined(__INSTANCING__)
98 #    define BVH_FUNCTION_NAME bvh_intersect_volume_instancing
99 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
100 #    include "kernel/bvh/bvh_volume.h"
101 #  endif
102
103 #  if defined(__OBJECT_MOTION__)
104 #    define BVH_FUNCTION_NAME bvh_intersect_volume_motion
105 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION|BVH_HAIR
106 #    include "kernel/bvh/bvh_volume.h"
107 #  endif
108 #endif  /* __VOLUME__ */
109
110 /* Record all intersections - Shadow BVH traversal */
111
112 #if defined(__SHADOW_RECORD_ALL__)
113 #  define BVH_FUNCTION_NAME bvh_intersect_shadow_all
114 #  define BVH_FUNCTION_FEATURES 0
115 #  include "kernel/bvh/bvh_shadow_all.h"
116
117 #  if defined(__INSTANCING__)
118 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_instancing
119 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING
120 #    include "kernel/bvh/bvh_shadow_all.h"
121 #  endif
122
123 #  if defined(__HAIR__)
124 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair
125 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
126 #    include "kernel/bvh/bvh_shadow_all.h"
127 #  endif
128
129 #  if defined(__OBJECT_MOTION__)
130 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_motion
131 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION
132 #    include "kernel/bvh/bvh_shadow_all.h"
133 #  endif
134
135 #  if defined(__HAIR__) && defined(__OBJECT_MOTION__)
136 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair_motion
137 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_MOTION
138 #    include "kernel/bvh/bvh_shadow_all.h"
139 #  endif
140 #endif  /* __SHADOW_RECORD_ALL__ */
141
142 /* Record all intersections - Volume BVH traversal  */
143
144 #if defined(__VOLUME_RECORD_ALL__)
145 #  define BVH_FUNCTION_NAME bvh_intersect_volume_all
146 #  define BVH_FUNCTION_FEATURES BVH_HAIR
147 #  include "kernel/bvh/bvh_volume_all.h"
148
149 #  if defined(__INSTANCING__)
150 #    define BVH_FUNCTION_NAME bvh_intersect_volume_all_instancing
151 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
152 #    include "kernel/bvh/bvh_volume_all.h"
153 #  endif
154
155 #  if defined(__OBJECT_MOTION__)
156 #    define BVH_FUNCTION_NAME bvh_intersect_volume_all_motion
157 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION|BVH_HAIR
158 #    include "kernel/bvh/bvh_volume_all.h"
159 #  endif
160 #endif  /* __VOLUME_RECORD_ALL__ */
161
162 #undef BVH_FEATURE
163 #undef BVH_NAME_JOIN
164 #undef BVH_NAME_EVAL
165 #undef BVH_FUNCTION_FULL_NAME
166
167 ccl_device_inline bool scene_intersect_valid(const Ray *ray)
168 {
169         /* NOTE: Due to some vectorization code  non-finite origin point might
170          * cause lots of false-positive intersections which will overflow traversal
171          * stack.
172          * This code is a quick way to perform early output, to avoid crashes in
173          * such cases.
174          * From production scenes so far it seems it's enough to test first element
175          * only.
176          */
177         return isfinite(ray->P.x);
178 }
179
180 /* Note: ray is passed by value to work around a possible CUDA compiler bug. */
181 ccl_device_intersect bool scene_intersect(KernelGlobals *kg,
182                                           const Ray ray,
183                                           const uint visibility,
184                                           Intersection *isect,
185                                           uint *lcg_state,
186                                           float difl,
187                                           float extmax)
188 {
189         if (!scene_intersect_valid(&ray)) {
190                 return false;
191         }
192 #ifdef __EMBREE__
193         if(kernel_data.bvh.scene) {
194                 isect->t = ray.t;
195                 CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_REGULAR);
196                 IntersectContext rtc_ctx(&ctx);
197                 RTCRayHit ray_hit;
198                 kernel_embree_setup_rayhit(ray, ray_hit, visibility);
199                 rtcIntersect1(kernel_data.bvh.scene, &rtc_ctx.context, &ray_hit);
200                 if(ray_hit.hit.geomID != RTC_INVALID_GEOMETRY_ID && ray_hit.hit.primID != RTC_INVALID_GEOMETRY_ID) {
201                         kernel_embree_convert_hit(kg, &ray_hit.ray, &ray_hit.hit, isect);
202                         return true;
203                 }
204                 return false;
205         }
206 #endif  /* __EMBREE__ */
207 #ifdef __OBJECT_MOTION__
208         if(kernel_data.bvh.have_motion) {
209 #  ifdef __HAIR__
210                 if(kernel_data.bvh.have_curves)
211                         return bvh_intersect_hair_motion(kg, &ray, isect, visibility, lcg_state, difl, extmax);
212 #  endif  /* __HAIR__ */
213
214                 return bvh_intersect_motion(kg, &ray, isect, visibility);
215         }
216 #endif  /* __OBJECT_MOTION__ */
217
218 #ifdef __HAIR__
219         if(kernel_data.bvh.have_curves)
220                 return bvh_intersect_hair(kg, &ray, isect, visibility, lcg_state, difl, extmax);
221 #endif  /* __HAIR__ */
222
223 #ifdef __KERNEL_CPU__
224
225 #  ifdef __INSTANCING__
226         if(kernel_data.bvh.have_instancing)
227                 return bvh_intersect_instancing(kg, &ray, isect, visibility);
228 #  endif  /* __INSTANCING__ */
229
230         return bvh_intersect(kg, &ray, isect, visibility);
231 #else  /* __KERNEL_CPU__ */
232
233 #  ifdef __INSTANCING__
234         return bvh_intersect_instancing(kg, &ray, isect, visibility);
235 #  else
236         return bvh_intersect(kg, &ray, isect, visibility);
237 #  endif  /* __INSTANCING__ */
238
239 #endif  /* __KERNEL_CPU__ */
240 }
241
242 #ifdef __BVH_LOCAL__
243 /* Note: ray is passed by value to work around a possible CUDA compiler bug. */
244 ccl_device_intersect bool scene_intersect_local(KernelGlobals *kg,
245                                                 const Ray ray,
246                                                 LocalIntersection *local_isect,
247                                                 int local_object,
248                                                 uint *lcg_state,
249                                                 int max_hits)
250 {
251         if (!scene_intersect_valid(&ray)) {
252                 return false;
253         }
254 #ifdef __EMBREE__
255         if(kernel_data.bvh.scene) {
256                 CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_SSS);
257                 ctx.lcg_state = lcg_state;
258                 ctx.max_hits = max_hits;
259                 ctx.ss_isect = local_isect;
260                 local_isect->num_hits = 0;
261                 ctx.sss_object_id = local_object;
262                 IntersectContext rtc_ctx(&ctx);
263                 RTCRay rtc_ray;
264                 kernel_embree_setup_ray(ray, rtc_ray, PATH_RAY_ALL_VISIBILITY);
265
266                 /* Get the Embree scene for this intersection. */
267                 RTCGeometry geom = rtcGetGeometry(kernel_data.bvh.scene, local_object * 2);
268                 if(geom) {
269                         float3 P = ray.P;
270                         float3 dir = ray.D;
271                         float3 idir = ray.D;
272                         const int object_flag = kernel_tex_fetch(__object_flag, local_object);
273                         if(!(object_flag & SD_OBJECT_TRANSFORM_APPLIED)) {
274                                 Transform ob_itfm;
275                                 rtc_ray.tfar = bvh_instance_motion_push(kg,
276                                                                         local_object,
277                                                                         &ray,
278                                                                         &P,
279                                                                         &dir,
280                                                                         &idir,
281                                                                         ray.t,
282                                                                         &ob_itfm);
283                                 /* bvh_instance_motion_push() returns the inverse transform but
284                                  * it's not needed here. */
285                                 (void) ob_itfm;
286
287                                 rtc_ray.org_x = P.x;
288                                 rtc_ray.org_y = P.y;
289                                 rtc_ray.org_z = P.z;
290                                 rtc_ray.dir_x = dir.x;
291                                 rtc_ray.dir_y = dir.y;
292                                 rtc_ray.dir_z = dir.z;
293                         }
294                         RTCScene scene = (RTCScene)rtcGetGeometryUserData(geom);
295                         if(scene) {
296                                 rtcOccluded1(scene, &rtc_ctx.context, &rtc_ray);
297                         }
298                 }
299
300                 return local_isect->num_hits > 0;
301         }
302 #endif  /* __EMBREE__ */
303 #ifdef __OBJECT_MOTION__
304         if(kernel_data.bvh.have_motion) {
305                 return bvh_intersect_local_motion(kg,
306                                                   &ray,
307                                                   local_isect,
308                                                   local_object,
309                                                   lcg_state,
310                                                   max_hits);
311         }
312 #endif  /* __OBJECT_MOTION__ */
313         return bvh_intersect_local(kg,
314                                     &ray,
315                                     local_isect,
316                                     local_object,
317                                     lcg_state,
318                                     max_hits);
319 }
320 #endif
321
322 #ifdef __SHADOW_RECORD_ALL__
323 ccl_device_intersect bool scene_intersect_shadow_all(KernelGlobals *kg,
324                                                      const Ray *ray,
325                                                      Intersection *isect,
326                                                      uint visibility,
327                                                      uint max_hits,
328                                                      uint *num_hits)
329 {
330         if (!scene_intersect_valid(ray)) {
331                 return false;
332         }
333 #  ifdef __EMBREE__
334         if(kernel_data.bvh.scene) {
335                 CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_SHADOW_ALL);
336                 ctx.isect_s = isect;
337                 ctx.max_hits = max_hits;
338                 ctx.num_hits = 0;
339                 IntersectContext rtc_ctx(&ctx);
340                 RTCRay rtc_ray;
341                 kernel_embree_setup_ray(*ray, rtc_ray, PATH_RAY_SHADOW);
342                 rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
343
344                 if(ctx.num_hits > max_hits) {
345                         return true;
346                 }
347                 *num_hits = ctx.num_hits;
348                 return rtc_ray.tfar == -INFINITY;
349         }
350 #  endif
351 #  ifdef __OBJECT_MOTION__
352         if(kernel_data.bvh.have_motion) {
353 #    ifdef __HAIR__
354                 if(kernel_data.bvh.have_curves) {
355                         return bvh_intersect_shadow_all_hair_motion(kg,
356                                                                     ray,
357                                                                     isect,
358                                                                     visibility,
359                                                                     max_hits,
360                                                                     num_hits);
361                 }
362 #    endif  /* __HAIR__ */
363
364                 return bvh_intersect_shadow_all_motion(kg,
365                                                        ray,
366                                                        isect,
367                                                        visibility,
368                                                        max_hits,
369                                                        num_hits);
370         }
371 #  endif  /* __OBJECT_MOTION__ */
372
373 #  ifdef __HAIR__
374         if(kernel_data.bvh.have_curves) {
375                 return bvh_intersect_shadow_all_hair(kg,
376                                                      ray,
377                                                      isect,
378                                                      visibility,
379                                                      max_hits,
380                                                      num_hits);
381         }
382 #  endif  /* __HAIR__ */
383
384 #  ifdef __INSTANCING__
385         if(kernel_data.bvh.have_instancing) {
386                 return bvh_intersect_shadow_all_instancing(kg,
387                                                            ray,
388                                                            isect,
389                                                            visibility,
390                                                            max_hits,
391                                                            num_hits);
392         }
393 #  endif  /* __INSTANCING__ */
394
395         return bvh_intersect_shadow_all(kg,
396                                         ray,
397                                         isect,
398                                         visibility,
399                                         max_hits,
400                                         num_hits);
401 }
402 #endif  /* __SHADOW_RECORD_ALL__ */
403
404 #ifdef __VOLUME__
405 ccl_device_intersect bool scene_intersect_volume(KernelGlobals *kg,
406                                                  const Ray *ray,
407                                                  Intersection *isect,
408                                                  const uint visibility)
409 {
410         if (!scene_intersect_valid(ray)) {
411                 return false;
412         }
413 #  ifdef __OBJECT_MOTION__
414         if(kernel_data.bvh.have_motion) {
415                 return bvh_intersect_volume_motion(kg, ray, isect, visibility);
416         }
417 #  endif  /* __OBJECT_MOTION__ */
418 #  ifdef __KERNEL_CPU__
419 #    ifdef __INSTANCING__
420         if(kernel_data.bvh.have_instancing)
421                 return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
422 #    endif  /* __INSTANCING__ */
423         return bvh_intersect_volume(kg, ray, isect, visibility);
424 #  else  /* __KERNEL_CPU__ */
425 #    ifdef __INSTANCING__
426         return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
427 #    else
428         return bvh_intersect_volume(kg, ray, isect, visibility);
429 #    endif  /* __INSTANCING__ */
430 #  endif  /* __KERNEL_CPU__ */
431 }
432 #endif  /* __VOLUME__ */
433
434 #ifdef __VOLUME_RECORD_ALL__
435 ccl_device_intersect uint scene_intersect_volume_all(KernelGlobals *kg,
436                                                      const Ray *ray,
437                                                      Intersection *isect,
438                                                      const uint max_hits,
439                                                      const uint visibility)
440 {
441         if (!scene_intersect_valid(ray)) {
442                 return false;
443         }
444 #  ifdef __EMBREE__
445         if(kernel_data.bvh.scene) {
446                 CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_VOLUME_ALL);
447                 ctx.isect_s = isect;
448                 ctx.max_hits = max_hits;
449                 ctx.num_hits = 0;
450                 IntersectContext rtc_ctx(&ctx);
451                 RTCRay rtc_ray;
452                 kernel_embree_setup_ray(*ray, rtc_ray, visibility);
453                 rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
454                 return rtc_ray.tfar == -INFINITY;
455         }
456 #  endif
457 #  ifdef __OBJECT_MOTION__
458         if(kernel_data.bvh.have_motion) {
459                 return bvh_intersect_volume_all_motion(kg, ray, isect, max_hits, visibility);
460         }
461 #  endif  /* __OBJECT_MOTION__ */
462 #  ifdef __INSTANCING__
463         if(kernel_data.bvh.have_instancing)
464                 return bvh_intersect_volume_all_instancing(kg, ray, isect, max_hits, visibility);
465 #  endif  /* __INSTANCING__ */
466         return bvh_intersect_volume_all(kg, ray, isect, max_hits, visibility);
467 }
468 #endif  /* __VOLUME_RECORD_ALL__ */
469
470
471 /* Ray offset to avoid self intersection.
472  *
473  * This function should be used to compute a modified ray start position for
474  * rays leaving from a surface. */
475
476 ccl_device_inline float3 ray_offset(float3 P, float3 Ng)
477 {
478 #ifdef __INTERSECTION_REFINE__
479         const float epsilon_f = 1e-5f;
480         /* ideally this should match epsilon_f, but instancing and motion blur
481          * precision makes it problematic */
482         const float epsilon_test = 1.0f;
483         const int epsilon_i = 32;
484
485         float3 res;
486
487         /* x component */
488         if(fabsf(P.x) < epsilon_test) {
489                 res.x = P.x + Ng.x*epsilon_f;
490         }
491         else {
492                 uint ix = __float_as_uint(P.x);
493                 ix += ((ix ^ __float_as_uint(Ng.x)) >> 31)? -epsilon_i: epsilon_i;
494                 res.x = __uint_as_float(ix);
495         }
496
497         /* y component */
498         if(fabsf(P.y) < epsilon_test) {
499                 res.y = P.y + Ng.y*epsilon_f;
500         }
501         else {
502                 uint iy = __float_as_uint(P.y);
503                 iy += ((iy ^ __float_as_uint(Ng.y)) >> 31)? -epsilon_i: epsilon_i;
504                 res.y = __uint_as_float(iy);
505         }
506
507         /* z component */
508         if(fabsf(P.z) < epsilon_test) {
509                 res.z = P.z + Ng.z*epsilon_f;
510         }
511         else {
512                 uint iz = __float_as_uint(P.z);
513                 iz += ((iz ^ __float_as_uint(Ng.z)) >> 31)? -epsilon_i: epsilon_i;
514                 res.z = __uint_as_float(iz);
515         }
516
517         return res;
518 #else
519         const float epsilon_f = 1e-4f;
520         return P + epsilon_f*Ng;
521 #endif
522 }
523
524 #if defined(__VOLUME_RECORD_ALL__) || (defined(__SHADOW_RECORD_ALL__) && defined(__KERNEL_CPU__))
525 /* ToDo: Move to another file? */
526 ccl_device int intersections_compare(const void *a, const void *b)
527 {
528         const Intersection *isect_a = (const Intersection*)a;
529         const Intersection *isect_b = (const Intersection*)b;
530
531         if(isect_a->t < isect_b->t)
532                 return -1;
533         else if(isect_a->t > isect_b->t)
534                 return 1;
535         else
536                 return 0;
537 }
538 #endif
539
540 #if defined(__SHADOW_RECORD_ALL__)
541 ccl_device_inline void sort_intersections(Intersection *hits, uint num_hits)
542 {
543 #ifdef __KERNEL_GPU__
544         /* Use bubble sort which has more friendly memory pattern on GPU. */
545         bool swapped;
546         do {
547                 swapped = false;
548                 for(int j = 0; j < num_hits - 1; ++j) {
549                         if(hits[j].t > hits[j + 1].t) {
550                                 struct Intersection tmp = hits[j];
551                                 hits[j] = hits[j + 1];
552                                 hits[j + 1] = tmp;
553                                 swapped = true;
554                         }
555                 }
556                 --num_hits;
557         } while(swapped);
558 #else
559         qsort(hits, num_hits, sizeof(Intersection), intersections_compare);
560 #endif
561 }
562 #endif  /* __SHADOW_RECORD_ALL__ | __VOLUME_RECORD_ALL__ */
563
564 CCL_NAMESPACE_END