ClangFormat: apply to source, most of intern
[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   PROFILING_INIT(kg, PROFILING_INTERSECT);
190
191   if (!scene_intersect_valid(&ray)) {
192     return false;
193   }
194 #ifdef __EMBREE__
195   if (kernel_data.bvh.scene) {
196     isect->t = ray.t;
197     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_REGULAR);
198     IntersectContext rtc_ctx(&ctx);
199     RTCRayHit ray_hit;
200     kernel_embree_setup_rayhit(ray, ray_hit, visibility);
201     rtcIntersect1(kernel_data.bvh.scene, &rtc_ctx.context, &ray_hit);
202     if (ray_hit.hit.geomID != RTC_INVALID_GEOMETRY_ID &&
203         ray_hit.hit.primID != RTC_INVALID_GEOMETRY_ID) {
204       kernel_embree_convert_hit(kg, &ray_hit.ray, &ray_hit.hit, isect);
205       return true;
206     }
207     return false;
208   }
209 #endif /* __EMBREE__ */
210 #ifdef __OBJECT_MOTION__
211   if (kernel_data.bvh.have_motion) {
212 #  ifdef __HAIR__
213     if (kernel_data.bvh.have_curves)
214       return bvh_intersect_hair_motion(kg, &ray, isect, visibility, lcg_state, difl, extmax);
215 #  endif /* __HAIR__ */
216
217     return bvh_intersect_motion(kg, &ray, isect, visibility);
218   }
219 #endif /* __OBJECT_MOTION__ */
220
221 #ifdef __HAIR__
222   if (kernel_data.bvh.have_curves)
223     return bvh_intersect_hair(kg, &ray, isect, visibility, lcg_state, difl, extmax);
224 #endif /* __HAIR__ */
225
226 #ifdef __KERNEL_CPU__
227
228 #  ifdef __INSTANCING__
229   if (kernel_data.bvh.have_instancing)
230     return bvh_intersect_instancing(kg, &ray, isect, visibility);
231 #  endif /* __INSTANCING__ */
232
233   return bvh_intersect(kg, &ray, isect, visibility);
234 #else /* __KERNEL_CPU__ */
235
236 #  ifdef __INSTANCING__
237   return bvh_intersect_instancing(kg, &ray, isect, visibility);
238 #  else
239   return bvh_intersect(kg, &ray, isect, visibility);
240 #  endif /* __INSTANCING__ */
241
242 #endif /* __KERNEL_CPU__ */
243 }
244
245 #ifdef __BVH_LOCAL__
246 /* Note: ray is passed by value to work around a possible CUDA compiler bug. */
247 ccl_device_intersect bool scene_intersect_local(KernelGlobals *kg,
248                                                 const Ray ray,
249                                                 LocalIntersection *local_isect,
250                                                 int local_object,
251                                                 uint *lcg_state,
252                                                 int max_hits)
253 {
254   PROFILING_INIT(kg, PROFILING_INTERSECT_LOCAL);
255
256   if (!scene_intersect_valid(&ray)) {
257     local_isect->num_hits = 0;
258     return false;
259   }
260 #  ifdef __EMBREE__
261   if (kernel_data.bvh.scene) {
262     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_SSS);
263     ctx.lcg_state = lcg_state;
264     ctx.max_hits = max_hits;
265     ctx.ss_isect = local_isect;
266     local_isect->num_hits = 0;
267     ctx.sss_object_id = local_object;
268     IntersectContext rtc_ctx(&ctx);
269     RTCRay rtc_ray;
270     kernel_embree_setup_ray(ray, rtc_ray, PATH_RAY_ALL_VISIBILITY);
271
272     /* Get the Embree scene for this intersection. */
273     RTCGeometry geom = rtcGetGeometry(kernel_data.bvh.scene, local_object * 2);
274     if (geom) {
275       float3 P = ray.P;
276       float3 dir = ray.D;
277       float3 idir = ray.D;
278       const int object_flag = kernel_tex_fetch(__object_flag, local_object);
279       if (!(object_flag & SD_OBJECT_TRANSFORM_APPLIED)) {
280         Transform ob_itfm;
281         rtc_ray.tfar = bvh_instance_motion_push(
282             kg, local_object, &ray, &P, &dir, &idir, ray.t, &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, &ray, local_isect, local_object, lcg_state, max_hits);
306   }
307 #  endif /* __OBJECT_MOTION__ */
308   return bvh_intersect_local(kg, &ray, local_isect, local_object, lcg_state, max_hits);
309 }
310 #endif
311
312 #ifdef __SHADOW_RECORD_ALL__
313 ccl_device_intersect bool scene_intersect_shadow_all(KernelGlobals *kg,
314                                                      const Ray *ray,
315                                                      Intersection *isect,
316                                                      uint visibility,
317                                                      uint max_hits,
318                                                      uint *num_hits)
319 {
320   PROFILING_INIT(kg, PROFILING_INTERSECT_SHADOW_ALL);
321
322   if (!scene_intersect_valid(ray)) {
323     *num_hits = 0;
324     return false;
325   }
326 #  ifdef __EMBREE__
327   if (kernel_data.bvh.scene) {
328     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_SHADOW_ALL);
329     ctx.isect_s = isect;
330     ctx.max_hits = max_hits;
331     ctx.num_hits = 0;
332     IntersectContext rtc_ctx(&ctx);
333     RTCRay rtc_ray;
334     kernel_embree_setup_ray(*ray, rtc_ray, PATH_RAY_SHADOW);
335     rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
336
337     if (ctx.num_hits > max_hits) {
338       return true;
339     }
340     *num_hits = ctx.num_hits;
341     return rtc_ray.tfar == -INFINITY;
342   }
343 #  endif
344 #  ifdef __OBJECT_MOTION__
345   if (kernel_data.bvh.have_motion) {
346 #    ifdef __HAIR__
347     if (kernel_data.bvh.have_curves) {
348       return bvh_intersect_shadow_all_hair_motion(kg, ray, isect, visibility, max_hits, num_hits);
349     }
350 #    endif /* __HAIR__ */
351
352     return bvh_intersect_shadow_all_motion(kg, ray, isect, visibility, max_hits, num_hits);
353   }
354 #  endif /* __OBJECT_MOTION__ */
355
356 #  ifdef __HAIR__
357   if (kernel_data.bvh.have_curves) {
358     return bvh_intersect_shadow_all_hair(kg, ray, isect, visibility, max_hits, num_hits);
359   }
360 #  endif /* __HAIR__ */
361
362 #  ifdef __INSTANCING__
363   if (kernel_data.bvh.have_instancing) {
364     return bvh_intersect_shadow_all_instancing(kg, ray, isect, visibility, max_hits, num_hits);
365   }
366 #  endif /* __INSTANCING__ */
367
368   return bvh_intersect_shadow_all(kg, ray, isect, visibility, max_hits, num_hits);
369 }
370 #endif /* __SHADOW_RECORD_ALL__ */
371
372 #ifdef __VOLUME__
373 ccl_device_intersect bool scene_intersect_volume(KernelGlobals *kg,
374                                                  const Ray *ray,
375                                                  Intersection *isect,
376                                                  const uint visibility)
377 {
378   PROFILING_INIT(kg, PROFILING_INTERSECT_VOLUME);
379
380   if (!scene_intersect_valid(ray)) {
381     return false;
382   }
383 #  ifdef __OBJECT_MOTION__
384   if (kernel_data.bvh.have_motion) {
385     return bvh_intersect_volume_motion(kg, ray, isect, visibility);
386   }
387 #  endif /* __OBJECT_MOTION__ */
388 #  ifdef __KERNEL_CPU__
389 #    ifdef __INSTANCING__
390   if (kernel_data.bvh.have_instancing)
391     return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
392 #    endif /* __INSTANCING__ */
393   return bvh_intersect_volume(kg, ray, isect, visibility);
394 #  else /* __KERNEL_CPU__ */
395 #    ifdef __INSTANCING__
396   return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
397 #    else
398   return bvh_intersect_volume(kg, ray, isect, visibility);
399 #    endif /* __INSTANCING__ */
400 #  endif   /* __KERNEL_CPU__ */
401 }
402 #endif /* __VOLUME__ */
403
404 #ifdef __VOLUME_RECORD_ALL__
405 ccl_device_intersect uint scene_intersect_volume_all(KernelGlobals *kg,
406                                                      const Ray *ray,
407                                                      Intersection *isect,
408                                                      const uint max_hits,
409                                                      const uint visibility)
410 {
411   PROFILING_INIT(kg, PROFILING_INTERSECT_VOLUME_ALL);
412
413   if (!scene_intersect_valid(ray)) {
414     return false;
415   }
416 #  ifdef __EMBREE__
417   if (kernel_data.bvh.scene) {
418     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_VOLUME_ALL);
419     ctx.isect_s = isect;
420     ctx.max_hits = max_hits;
421     ctx.num_hits = 0;
422     IntersectContext rtc_ctx(&ctx);
423     RTCRay rtc_ray;
424     kernel_embree_setup_ray(*ray, rtc_ray, visibility);
425     rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
426     return rtc_ray.tfar == -INFINITY;
427   }
428 #  endif
429 #  ifdef __OBJECT_MOTION__
430   if (kernel_data.bvh.have_motion) {
431     return bvh_intersect_volume_all_motion(kg, ray, isect, max_hits, visibility);
432   }
433 #  endif /* __OBJECT_MOTION__ */
434 #  ifdef __INSTANCING__
435   if (kernel_data.bvh.have_instancing)
436     return bvh_intersect_volume_all_instancing(kg, ray, isect, max_hits, visibility);
437 #  endif /* __INSTANCING__ */
438   return bvh_intersect_volume_all(kg, ray, isect, max_hits, visibility);
439 }
440 #endif /* __VOLUME_RECORD_ALL__ */
441
442 /* Ray offset to avoid self intersection.
443  *
444  * This function should be used to compute a modified ray start position for
445  * rays leaving from a surface. */
446
447 ccl_device_inline float3 ray_offset(float3 P, float3 Ng)
448 {
449 #ifdef __INTERSECTION_REFINE__
450   const float epsilon_f = 1e-5f;
451   /* ideally this should match epsilon_f, but instancing and motion blur
452    * precision makes it problematic */
453   const float epsilon_test = 1.0f;
454   const int epsilon_i = 32;
455
456   float3 res;
457
458   /* x component */
459   if (fabsf(P.x) < epsilon_test) {
460     res.x = P.x + Ng.x * epsilon_f;
461   }
462   else {
463     uint ix = __float_as_uint(P.x);
464     ix += ((ix ^ __float_as_uint(Ng.x)) >> 31) ? -epsilon_i : epsilon_i;
465     res.x = __uint_as_float(ix);
466   }
467
468   /* y component */
469   if (fabsf(P.y) < epsilon_test) {
470     res.y = P.y + Ng.y * epsilon_f;
471   }
472   else {
473     uint iy = __float_as_uint(P.y);
474     iy += ((iy ^ __float_as_uint(Ng.y)) >> 31) ? -epsilon_i : epsilon_i;
475     res.y = __uint_as_float(iy);
476   }
477
478   /* z component */
479   if (fabsf(P.z) < epsilon_test) {
480     res.z = P.z + Ng.z * epsilon_f;
481   }
482   else {
483     uint iz = __float_as_uint(P.z);
484     iz += ((iz ^ __float_as_uint(Ng.z)) >> 31) ? -epsilon_i : epsilon_i;
485     res.z = __uint_as_float(iz);
486   }
487
488   return res;
489 #else
490   const float epsilon_f = 1e-4f;
491   return P + epsilon_f * Ng;
492 #endif
493 }
494
495 #if defined(__VOLUME_RECORD_ALL__) || (defined(__SHADOW_RECORD_ALL__) && defined(__KERNEL_CPU__))
496 /* ToDo: Move to another file? */
497 ccl_device int intersections_compare(const void *a, const void *b)
498 {
499   const Intersection *isect_a = (const Intersection *)a;
500   const Intersection *isect_b = (const Intersection *)b;
501
502   if (isect_a->t < isect_b->t)
503     return -1;
504   else if (isect_a->t > isect_b->t)
505     return 1;
506   else
507     return 0;
508 }
509 #endif
510
511 #if defined(__SHADOW_RECORD_ALL__)
512 ccl_device_inline void sort_intersections(Intersection *hits, uint num_hits)
513 {
514 #  ifdef __KERNEL_GPU__
515   /* Use bubble sort which has more friendly memory pattern on GPU. */
516   bool swapped;
517   do {
518     swapped = false;
519     for (int j = 0; j < num_hits - 1; ++j) {
520       if (hits[j].t > hits[j + 1].t) {
521         struct Intersection tmp = hits[j];
522         hits[j] = hits[j + 1];
523         hits[j + 1] = tmp;
524         swapped = true;
525       }
526     }
527     --num_hits;
528   } while (swapped);
529 #  else
530   qsort(hits, num_hits, sizeof(Intersection), intersections_compare);
531 #  endif
532 }
533 #endif /* __SHADOW_RECORD_ALL__ | __VOLUME_RECORD_ALL__ */
534
535 CCL_NAMESPACE_END