Cycles: Make all #include statements relative to cycles source directory
[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 CCL_NAMESPACE_BEGIN
29
30 #include "kernel/bvh/bvh_types.h"
31
32 /* Common QBVH functions. */
33 #ifdef __QBVH__
34 #  include "kernel/bvh/qbvh_nodes.h"
35 #endif
36
37 /* Regular BVH traversal */
38
39 #include "kernel/bvh/bvh_nodes.h"
40
41 #define BVH_FUNCTION_NAME bvh_intersect
42 #define BVH_FUNCTION_FEATURES 0
43 #include "kernel/bvh/bvh_traversal.h"
44
45 #if defined(__INSTANCING__)
46 #  define BVH_FUNCTION_NAME bvh_intersect_instancing
47 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING
48 #  include "kernel/bvh/bvh_traversal.h"
49 #endif
50
51 #if defined(__HAIR__)
52 #  define BVH_FUNCTION_NAME bvh_intersect_hair
53 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_HAIR_MINIMUM_WIDTH
54 #  include "kernel/bvh/bvh_traversal.h"
55 #endif
56
57 #if defined(__OBJECT_MOTION__)
58 #  define BVH_FUNCTION_NAME bvh_intersect_motion
59 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION
60 #  include "kernel/bvh/bvh_traversal.h"
61 #endif
62
63 #if defined(__HAIR__) && defined(__OBJECT_MOTION__)
64 #  define BVH_FUNCTION_NAME bvh_intersect_hair_motion
65 #  define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_HAIR_MINIMUM_WIDTH|BVH_MOTION
66 #  include "kernel/bvh/bvh_traversal.h"
67 #endif
68
69 /* Subsurface scattering BVH traversal */
70
71 #if defined(__SUBSURFACE__)
72 #  define BVH_FUNCTION_NAME bvh_intersect_subsurface
73 #  define BVH_FUNCTION_FEATURES BVH_HAIR
74 #  include "kernel/bvh/bvh_subsurface.h"
75
76 #  if defined(__OBJECT_MOTION__)
77 #    define BVH_FUNCTION_NAME bvh_intersect_subsurface_motion
78 #    define BVH_FUNCTION_FEATURES BVH_MOTION|BVH_HAIR
79 #    include "kernel/bvh/bvh_subsurface.h"
80 #  endif
81 #endif  /* __SUBSURFACE__ */
82
83 /* Volume BVH traversal */
84
85 #if defined(__VOLUME__)
86 #  define BVH_FUNCTION_NAME bvh_intersect_volume
87 #  define BVH_FUNCTION_FEATURES BVH_HAIR
88 #  include "kernel/bvh/bvh_volume.h"
89
90 #  if defined(__INSTANCING__)
91 #    define BVH_FUNCTION_NAME bvh_intersect_volume_instancing
92 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
93 #    include "kernel/bvh/bvh_volume.h"
94 #  endif
95
96 #  if defined(__OBJECT_MOTION__)
97 #    define BVH_FUNCTION_NAME bvh_intersect_volume_motion
98 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION|BVH_HAIR
99 #    include "kernel/bvh/bvh_volume.h"
100 #  endif
101 #endif  /* __VOLUME__ */
102
103 /* Record all intersections - Shadow BVH traversal */
104
105 #if defined(__SHADOW_RECORD_ALL__)
106 #  define BVH_FUNCTION_NAME bvh_intersect_shadow_all
107 #  define BVH_FUNCTION_FEATURES 0
108 #  include "kernel/bvh/bvh_shadow_all.h"
109
110 #  if defined(__INSTANCING__)
111 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_instancing
112 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING
113 #    include "kernel/bvh/bvh_shadow_all.h"
114 #  endif
115
116 #  if defined(__HAIR__)
117 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair
118 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
119 #    include "kernel/bvh/bvh_shadow_all.h"
120 #  endif
121
122 #  if defined(__OBJECT_MOTION__)
123 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_motion
124 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION
125 #    include "kernel/bvh/bvh_shadow_all.h"
126 #  endif
127
128 #  if defined(__HAIR__) && defined(__OBJECT_MOTION__)
129 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair_motion
130 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR|BVH_MOTION
131 #    include "kernel/bvh/bvh_shadow_all.h"
132 #  endif
133 #endif  /* __SHADOW_RECORD_ALL__ */
134
135 /* Record all intersections - Volume BVH traversal  */
136
137 #if defined(__VOLUME_RECORD_ALL__)
138 #  define BVH_FUNCTION_NAME bvh_intersect_volume_all
139 #  define BVH_FUNCTION_FEATURES BVH_HAIR
140 #  include "kernel/bvh/bvh_volume_all.h"
141
142 #  if defined(__INSTANCING__)
143 #    define BVH_FUNCTION_NAME bvh_intersect_volume_all_instancing
144 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_HAIR
145 #    include "kernel/bvh/bvh_volume_all.h"
146 #  endif
147
148 #  if defined(__OBJECT_MOTION__)
149 #    define BVH_FUNCTION_NAME bvh_intersect_volume_all_motion
150 #    define BVH_FUNCTION_FEATURES BVH_INSTANCING|BVH_MOTION|BVH_HAIR
151 #    include "kernel/bvh/bvh_volume_all.h"
152 #  endif
153 #endif  /* __VOLUME_RECORD_ALL__ */
154
155 #undef BVH_FEATURE
156 #undef BVH_NAME_JOIN
157 #undef BVH_NAME_EVAL
158 #undef BVH_FUNCTION_FULL_NAME
159
160 /* Note: ray is passed by value to work around a possible CUDA compiler bug. */
161 ccl_device_intersect bool scene_intersect(KernelGlobals *kg,
162                                           const Ray ray,
163                                           const uint visibility,
164                                           Intersection *isect,
165                                           uint *lcg_state,
166                                           float difl,
167                                           float extmax)
168 {
169 #ifdef __OBJECT_MOTION__
170         if(kernel_data.bvh.have_motion) {
171 #  ifdef __HAIR__
172                 if(kernel_data.bvh.have_curves)
173                         return bvh_intersect_hair_motion(kg, &ray, isect, visibility, lcg_state, difl, extmax);
174 #  endif /* __HAIR__ */
175
176                 return bvh_intersect_motion(kg, &ray, isect, visibility);
177         }
178 #endif /* __OBJECT_MOTION__ */
179
180 #ifdef __HAIR__
181         if(kernel_data.bvh.have_curves)
182                 return bvh_intersect_hair(kg, &ray, isect, visibility, lcg_state, difl, extmax);
183 #endif /* __HAIR__ */
184
185 #ifdef __KERNEL_CPU__
186
187 #  ifdef __INSTANCING__
188         if(kernel_data.bvh.have_instancing)
189                 return bvh_intersect_instancing(kg, &ray, isect, visibility);
190 #  endif /* __INSTANCING__ */
191
192         return bvh_intersect(kg, &ray, isect, visibility);
193 #else /* __KERNEL_CPU__ */
194
195 #  ifdef __INSTANCING__
196         return bvh_intersect_instancing(kg, &ray, isect, visibility);
197 #  else
198         return bvh_intersect(kg, &ray, isect, visibility);
199 #  endif /* __INSTANCING__ */
200
201 #endif /* __KERNEL_CPU__ */
202 }
203
204 #ifdef __SUBSURFACE__
205 /* Note: ray is passed by value to work around a possible CUDA compiler bug. */
206 ccl_device_intersect void scene_intersect_subsurface(KernelGlobals *kg,
207                                                      const Ray ray,
208                                                      SubsurfaceIntersection *ss_isect,
209                                                      int subsurface_object,
210                                                      uint *lcg_state,
211                                                      int max_hits)
212 {
213 #ifdef __OBJECT_MOTION__
214         if(kernel_data.bvh.have_motion) {
215                 return bvh_intersect_subsurface_motion(kg,
216                                                        &ray,
217                                                        ss_isect,
218                                                        subsurface_object,
219                                                        lcg_state,
220                                                        max_hits);
221         }
222 #endif /* __OBJECT_MOTION__ */
223         return bvh_intersect_subsurface(kg,
224                                         &ray,
225                                         ss_isect,
226                                         subsurface_object,
227                                         lcg_state,
228                                         max_hits);
229 }
230 #endif
231
232 #ifdef __SHADOW_RECORD_ALL__
233 ccl_device_intersect bool scene_intersect_shadow_all(KernelGlobals *kg,
234                                                      const Ray *ray,
235                                                      Intersection *isect,
236                                                      int skip_object,
237                                                      uint max_hits,
238                                                      uint *num_hits)
239 {
240 #  ifdef __OBJECT_MOTION__
241         if(kernel_data.bvh.have_motion) {
242 #    ifdef __HAIR__
243                 if(kernel_data.bvh.have_curves) {
244                         return bvh_intersect_shadow_all_hair_motion(kg,
245                                                                     ray,
246                                                                     isect,
247                                                                     skip_object,
248                                                                     max_hits,
249                                                                     num_hits);
250                 }
251 #    endif /* __HAIR__ */
252
253                 return bvh_intersect_shadow_all_motion(kg,
254                                                        ray,
255                                                        isect,
256                                                        skip_object,
257                                                        max_hits,
258                                                        num_hits);
259         }
260 #  endif /* __OBJECT_MOTION__ */
261
262 #  ifdef __HAIR__
263         if(kernel_data.bvh.have_curves) {
264                 return bvh_intersect_shadow_all_hair(kg,
265                                                      ray,
266                                                      isect,
267                                                      skip_object,
268                                                      max_hits,
269                                                      num_hits);
270         }
271 #  endif /* __HAIR__ */
272
273 #  ifdef __INSTANCING__
274         if(kernel_data.bvh.have_instancing) {
275                 return bvh_intersect_shadow_all_instancing(kg,
276                                                            ray,
277                                                            isect,
278                                                            skip_object,
279                                                            max_hits,
280                                                            num_hits);
281         }
282 #  endif /* __INSTANCING__ */
283
284         return bvh_intersect_shadow_all(kg,
285                                         ray,
286                                         isect,
287                                         skip_object,
288                                         max_hits,
289                                         num_hits);
290 }
291 #endif  /* __SHADOW_RECORD_ALL__ */
292
293 #ifdef __VOLUME__
294 ccl_device_intersect bool scene_intersect_volume(KernelGlobals *kg,
295                                                  const Ray *ray,
296                                                  Intersection *isect,
297                                                  const uint visibility)
298 {
299 #  ifdef __OBJECT_MOTION__
300         if(kernel_data.bvh.have_motion) {
301                 return bvh_intersect_volume_motion(kg, ray, isect, visibility);
302         }
303 #  endif /* __OBJECT_MOTION__ */
304 #  ifdef __KERNEL_CPU__
305 #    ifdef __INSTANCING__
306         if(kernel_data.bvh.have_instancing)
307                 return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
308 #    endif /* __INSTANCING__ */
309         return bvh_intersect_volume(kg, ray, isect, visibility);
310 #  else /* __KERNEL_CPU__ */
311 #    ifdef __INSTANCING__
312         return bvh_intersect_volume_instancing(kg, ray, isect, visibility);
313 #    else
314         return bvh_intersect_volume(kg, ray, isect, visibility);
315 #    endif /* __INSTANCING__ */
316 #  endif /* __KERNEL_CPU__ */
317 }
318 #endif  /* __VOLUME__ */
319
320 #ifdef __VOLUME_RECORD_ALL__
321 ccl_device_intersect uint scene_intersect_volume_all(KernelGlobals *kg,
322                                                      const Ray *ray,
323                                                      Intersection *isect,
324                                                      const uint max_hits,
325                                                      const uint visibility)
326 {
327 #  ifdef __OBJECT_MOTION__
328         if(kernel_data.bvh.have_motion) {
329                 return bvh_intersect_volume_all_motion(kg, ray, isect, max_hits, visibility);
330         }
331 #  endif /* __OBJECT_MOTION__ */
332 #  ifdef __INSTANCING__
333         if(kernel_data.bvh.have_instancing)
334                 return bvh_intersect_volume_all_instancing(kg, ray, isect, max_hits, visibility);
335 #  endif /* __INSTANCING__ */
336         return bvh_intersect_volume_all(kg, ray, isect, max_hits, visibility);
337 }
338 #endif  /* __VOLUME_RECORD_ALL__ */
339
340
341 /* Ray offset to avoid self intersection.
342  *
343  * This function should be used to compute a modified ray start position for
344  * rays leaving from a surface. */
345
346 ccl_device_inline float3 ray_offset(float3 P, float3 Ng)
347 {
348 #ifdef __INTERSECTION_REFINE__
349         const float epsilon_f = 1e-5f;
350         /* ideally this should match epsilon_f, but instancing and motion blur
351          * precision makes it problematic */
352         const float epsilon_test = 1.0f;
353         const int epsilon_i = 32;
354
355         float3 res;
356
357         /* x component */
358         if(fabsf(P.x) < epsilon_test) {
359                 res.x = P.x + Ng.x*epsilon_f;
360         }
361         else {
362                 uint ix = __float_as_uint(P.x);
363                 ix += ((ix ^ __float_as_uint(Ng.x)) >> 31)? -epsilon_i: epsilon_i;
364                 res.x = __uint_as_float(ix);
365         }
366
367         /* y component */
368         if(fabsf(P.y) < epsilon_test) {
369                 res.y = P.y + Ng.y*epsilon_f;
370         }
371         else {
372                 uint iy = __float_as_uint(P.y);
373                 iy += ((iy ^ __float_as_uint(Ng.y)) >> 31)? -epsilon_i: epsilon_i;
374                 res.y = __uint_as_float(iy);
375         }
376
377         /* z component */
378         if(fabsf(P.z) < epsilon_test) {
379                 res.z = P.z + Ng.z*epsilon_f;
380         }
381         else {
382                 uint iz = __float_as_uint(P.z);
383                 iz += ((iz ^ __float_as_uint(Ng.z)) >> 31)? -epsilon_i: epsilon_i;
384                 res.z = __uint_as_float(iz);
385         }
386
387         return res;
388 #else
389         const float epsilon_f = 1e-4f;
390         return P + epsilon_f*Ng;
391 #endif
392 }
393
394 #if defined(__VOLUME_RECORD_ALL__) || (defined(__SHADOW_RECORD_ALL__) && defined(__KERNEL_CPU__))
395 /* ToDo: Move to another file? */
396 ccl_device int intersections_compare(const void *a, const void *b)
397 {
398         const Intersection *isect_a = (const Intersection*)a;
399         const Intersection *isect_b = (const Intersection*)b;
400
401         if(isect_a->t < isect_b->t)
402                 return -1;
403         else if(isect_a->t > isect_b->t)
404                 return 1;
405         else
406                 return 0;
407 }
408 #endif
409
410 #if defined(__SHADOW_RECORD_ALL__)
411 ccl_device_inline void sort_intersections(Intersection *hits, uint num_hits)
412 {
413 #ifdef __KERNEL_GPU__
414         /* Use bubble sort which has more friendly memory pattern on GPU. */
415         bool swapped;
416         do {
417                 swapped = false;
418                 for(int j = 0; j < num_hits - 1; ++j) {
419                         if(hits[j].t > hits[j + 1].t) {
420                                 struct Intersection tmp = hits[j];
421                                 hits[j] = hits[j + 1];
422                                 hits[j + 1] = tmp;
423                                 swapped = true;
424                         }
425                 }
426                 --num_hits;
427         } while(swapped);
428 #else
429         qsort(hits, num_hits, sizeof(Intersection), intersections_compare);
430 #endif
431 }
432 #endif  /* __SHADOW_RECORD_ALL__ | __VOLUME_RECORD_ALL__ */
433
434 CCL_NAMESPACE_END