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 #ifndef __KERNEL_OPTIX__
37 
38 /* Regular BVH traversal */
39 
40 #  include "kernel/bvh/bvh_nodes.h"
41 
42 #  define BVH_FUNCTION_NAME bvh_intersect
43 #  define BVH_FUNCTION_FEATURES 0
44 #  include "kernel/bvh/bvh_traversal.h"
45 
46 #  if defined(__HAIR__)
47 #    define BVH_FUNCTION_NAME bvh_intersect_hair
48 #    define BVH_FUNCTION_FEATURES BVH_HAIR
49 #    include "kernel/bvh/bvh_traversal.h"
50 #  endif
51 
52 #  if defined(__OBJECT_MOTION__)
53 #    define BVH_FUNCTION_NAME bvh_intersect_motion
54 #    define BVH_FUNCTION_FEATURES BVH_MOTION
55 #    include "kernel/bvh/bvh_traversal.h"
56 #  endif
57 
58 #  if defined(__HAIR__) && defined(__OBJECT_MOTION__)
59 #    define BVH_FUNCTION_NAME bvh_intersect_hair_motion
60 #    define BVH_FUNCTION_FEATURES BVH_HAIR | BVH_MOTION
61 #    include "kernel/bvh/bvh_traversal.h"
62 #  endif
63 
64 /* Subsurface scattering BVH traversal */
65 
66 #  if defined(__BVH_LOCAL__)
67 #    define BVH_FUNCTION_NAME bvh_intersect_local
68 #    define BVH_FUNCTION_FEATURES BVH_HAIR
69 #    include "kernel/bvh/bvh_local.h"
70 
71 #    if defined(__OBJECT_MOTION__)
72 #      define BVH_FUNCTION_NAME bvh_intersect_local_motion
73 #      define BVH_FUNCTION_FEATURES BVH_MOTION | BVH_HAIR
74 #      include "kernel/bvh/bvh_local.h"
75 #    endif
76 #  endif /* __BVH_LOCAL__ */
77 
78 /* Volume BVH traversal */
79 
80 #  if defined(__VOLUME__)
81 #    define BVH_FUNCTION_NAME bvh_intersect_volume
82 #    define BVH_FUNCTION_FEATURES BVH_HAIR
83 #    include "kernel/bvh/bvh_volume.h"
84 
85 #    if defined(__OBJECT_MOTION__)
86 #      define BVH_FUNCTION_NAME bvh_intersect_volume_motion
87 #      define BVH_FUNCTION_FEATURES BVH_MOTION | BVH_HAIR
88 #      include "kernel/bvh/bvh_volume.h"
89 #    endif
90 #  endif /* __VOLUME__ */
91 
92 /* Record all intersections - Shadow BVH traversal */
93 
94 #  if defined(__SHADOW_RECORD_ALL__)
95 #    define BVH_FUNCTION_NAME bvh_intersect_shadow_all
96 #    define BVH_FUNCTION_FEATURES 0
97 #    include "kernel/bvh/bvh_shadow_all.h"
98 
99 #    if defined(__HAIR__)
100 #      define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair
101 #      define BVH_FUNCTION_FEATURES BVH_HAIR
102 #      include "kernel/bvh/bvh_shadow_all.h"
103 #    endif
104 
105 #    if defined(__OBJECT_MOTION__)
106 #      define BVH_FUNCTION_NAME bvh_intersect_shadow_all_motion
107 #      define BVH_FUNCTION_FEATURES BVH_MOTION
108 #      include "kernel/bvh/bvh_shadow_all.h"
109 #    endif
110 
111 #    if defined(__HAIR__) && defined(__OBJECT_MOTION__)
112 #      define BVH_FUNCTION_NAME bvh_intersect_shadow_all_hair_motion
113 #      define BVH_FUNCTION_FEATURES BVH_HAIR | BVH_MOTION
114 #      include "kernel/bvh/bvh_shadow_all.h"
115 #    endif
116 #  endif /* __SHADOW_RECORD_ALL__ */
117 
118 /* Record all intersections - Volume BVH traversal  */
119 
120 #  if defined(__VOLUME_RECORD_ALL__)
121 #    define BVH_FUNCTION_NAME bvh_intersect_volume_all
122 #    define BVH_FUNCTION_FEATURES BVH_HAIR
123 #    include "kernel/bvh/bvh_volume_all.h"
124 
125 #    if defined(__OBJECT_MOTION__)
126 #      define BVH_FUNCTION_NAME bvh_intersect_volume_all_motion
127 #      define BVH_FUNCTION_FEATURES BVH_MOTION | BVH_HAIR
128 #      include "kernel/bvh/bvh_volume_all.h"
129 #    endif
130 #  endif /* __VOLUME_RECORD_ALL__ */
131 
132 #  undef BVH_FEATURE
133 #  undef BVH_NAME_JOIN
134 #  undef BVH_NAME_EVAL
135 #  undef BVH_FUNCTION_FULL_NAME
136 
137 #endif /* __KERNEL_OPTIX__ */
138 
scene_intersect_valid(const Ray * ray)139 ccl_device_inline bool scene_intersect_valid(const Ray *ray)
140 {
141   /* NOTE: Due to some vectorization code  non-finite origin point might
142    * cause lots of false-positive intersections which will overflow traversal
143    * stack.
144    * This code is a quick way to perform early output, to avoid crashes in
145    * such cases.
146    * From production scenes so far it seems it's enough to test first element
147    * only.
148    * Scene intersection may also called with empty rays for conditional trace
149    * calls that evaluate to false, so filter those out.
150    */
151   return isfinite_safe(ray->P.x) && isfinite_safe(ray->D.x) && len_squared(ray->D) != 0.0f;
152 }
153 
scene_intersect(KernelGlobals * kg,const Ray * ray,const uint visibility,Intersection * isect)154 ccl_device_intersect bool scene_intersect(KernelGlobals *kg,
155                                           const Ray *ray,
156                                           const uint visibility,
157                                           Intersection *isect)
158 {
159   PROFILING_INIT(kg, PROFILING_INTERSECT);
160 
161 #ifdef __KERNEL_OPTIX__
162   uint p0 = 0;
163   uint p1 = 0;
164   uint p2 = 0;
165   uint p3 = 0;
166   uint p4 = visibility;
167   uint p5 = PRIMITIVE_NONE;
168 
169   optixTrace(scene_intersect_valid(ray) ? kernel_data.bvh.scene : 0,
170              ray->P,
171              ray->D,
172              0.0f,
173              ray->t,
174              ray->time,
175              0xF,
176              OPTIX_RAY_FLAG_NONE,
177              0,  // SBT offset for PG_HITD
178              0,
179              0,
180              p0,
181              p1,
182              p2,
183              p3,
184              p4,
185              p5);
186 
187   isect->t = __uint_as_float(p0);
188   isect->u = __uint_as_float(p1);
189   isect->v = __uint_as_float(p2);
190   isect->prim = p3;
191   isect->object = p4;
192   isect->type = p5;
193 
194   return p5 != PRIMITIVE_NONE;
195 #else /* __KERNEL_OPTIX__ */
196   if (!scene_intersect_valid(ray)) {
197     return false;
198   }
199 
200 #  ifdef __EMBREE__
201   if (kernel_data.bvh.scene) {
202     isect->t = ray->t;
203     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_REGULAR);
204     IntersectContext rtc_ctx(&ctx);
205     RTCRayHit ray_hit;
206     kernel_embree_setup_rayhit(*ray, ray_hit, visibility);
207     rtcIntersect1(kernel_data.bvh.scene, &rtc_ctx.context, &ray_hit);
208     if (ray_hit.hit.geomID != RTC_INVALID_GEOMETRY_ID &&
209         ray_hit.hit.primID != RTC_INVALID_GEOMETRY_ID) {
210       kernel_embree_convert_hit(kg, &ray_hit.ray, &ray_hit.hit, isect);
211       return true;
212     }
213     return false;
214   }
215 #  endif /* __EMBREE__ */
216 
217 #  ifdef __OBJECT_MOTION__
218   if (kernel_data.bvh.have_motion) {
219 #    ifdef __HAIR__
220     if (kernel_data.bvh.have_curves) {
221       return bvh_intersect_hair_motion(kg, ray, isect, visibility);
222     }
223 #    endif /* __HAIR__ */
224 
225     return bvh_intersect_motion(kg, ray, isect, visibility);
226   }
227 #  endif   /* __OBJECT_MOTION__ */
228 
229 #  ifdef __HAIR__
230   if (kernel_data.bvh.have_curves) {
231     return bvh_intersect_hair(kg, ray, isect, visibility);
232   }
233 #  endif /* __HAIR__ */
234 
235   return bvh_intersect(kg, ray, isect, visibility);
236 #endif   /* __KERNEL_OPTIX__ */
237 }
238 
239 #ifdef __BVH_LOCAL__
scene_intersect_local(KernelGlobals * kg,const Ray * ray,LocalIntersection * local_isect,int local_object,uint * lcg_state,int max_hits)240 ccl_device_intersect bool scene_intersect_local(KernelGlobals *kg,
241                                                 const Ray *ray,
242                                                 LocalIntersection *local_isect,
243                                                 int local_object,
244                                                 uint *lcg_state,
245                                                 int max_hits)
246 {
247   PROFILING_INIT(kg, PROFILING_INTERSECT_LOCAL);
248 
249 #  ifdef __KERNEL_OPTIX__
250   uint p0 = ((uint64_t)lcg_state) & 0xFFFFFFFF;
251   uint p1 = (((uint64_t)lcg_state) >> 32) & 0xFFFFFFFF;
252   uint p2 = ((uint64_t)local_isect) & 0xFFFFFFFF;
253   uint p3 = (((uint64_t)local_isect) >> 32) & 0xFFFFFFFF;
254   uint p4 = local_object;
255   // Is set to zero on miss or if ray is aborted, so can be used as return value
256   uint p5 = max_hits;
257 
258   if (local_isect) {
259     local_isect->num_hits = 0;  // Initialize hit count to zero
260   }
261   optixTrace(scene_intersect_valid(ray) ? kernel_data.bvh.scene : 0,
262              ray->P,
263              ray->D,
264              0.0f,
265              ray->t,
266              ray->time,
267              // Skip curves
268              0x3,
269              // Need to always call into __anyhit__kernel_optix_local_hit
270              OPTIX_RAY_FLAG_ENFORCE_ANYHIT,
271              2,  // SBT offset for PG_HITL
272              0,
273              0,
274              p0,
275              p1,
276              p2,
277              p3,
278              p4,
279              p5);
280 
281   return p5;
282 #  else /* __KERNEL_OPTIX__ */
283   if (!scene_intersect_valid(ray)) {
284     if (local_isect) {
285       local_isect->num_hits = 0;
286     }
287     return false;
288   }
289 
290 #    ifdef __EMBREE__
291   if (kernel_data.bvh.scene) {
292     const bool has_bvh = !(kernel_tex_fetch(__object_flag, local_object) &
293                            SD_OBJECT_TRANSFORM_APPLIED);
294     CCLIntersectContext ctx(
295         kg, has_bvh ? CCLIntersectContext::RAY_SSS : CCLIntersectContext::RAY_LOCAL);
296     ctx.lcg_state = lcg_state;
297     ctx.max_hits = max_hits;
298     ctx.local_isect = local_isect;
299     if (local_isect) {
300       local_isect->num_hits = 0;
301     }
302     ctx.local_object_id = local_object;
303     IntersectContext rtc_ctx(&ctx);
304     RTCRay rtc_ray;
305     kernel_embree_setup_ray(*ray, rtc_ray, PATH_RAY_ALL_VISIBILITY);
306 
307     /* If this object has its own BVH, use it. */
308     if (has_bvh) {
309       RTCGeometry geom = rtcGetGeometry(kernel_data.bvh.scene, local_object * 2);
310       if (geom) {
311         float3 P = ray->P;
312         float3 dir = ray->D;
313         float3 idir = ray->D;
314         Transform ob_itfm;
315         rtc_ray.tfar = bvh_instance_motion_push(
316             kg, local_object, ray, &P, &dir, &idir, ray->t, &ob_itfm);
317         /* bvh_instance_motion_push() returns the inverse transform but
318          * it's not needed here. */
319         (void)ob_itfm;
320 
321         rtc_ray.org_x = P.x;
322         rtc_ray.org_y = P.y;
323         rtc_ray.org_z = P.z;
324         rtc_ray.dir_x = dir.x;
325         rtc_ray.dir_y = dir.y;
326         rtc_ray.dir_z = dir.z;
327         RTCScene scene = (RTCScene)rtcGetGeometryUserData(geom);
328         kernel_assert(scene);
329         if (scene) {
330           rtcOccluded1(scene, &rtc_ctx.context, &rtc_ray);
331         }
332       }
333     }
334     else {
335       rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
336     }
337 
338     /* rtcOccluded1 sets tfar to -inf if a hit was found. */
339     return (local_isect && local_isect->num_hits > 0) || (rtc_ray.tfar < 0);
340     ;
341   }
342 #    endif /* __EMBREE__ */
343 
344 #    ifdef __OBJECT_MOTION__
345   if (kernel_data.bvh.have_motion) {
346     return bvh_intersect_local_motion(kg, ray, local_isect, local_object, lcg_state, max_hits);
347   }
348 #    endif /* __OBJECT_MOTION__ */
349   return bvh_intersect_local(kg, ray, local_isect, local_object, lcg_state, max_hits);
350 #  endif   /* __KERNEL_OPTIX__ */
351 }
352 #endif
353 
354 #ifdef __SHADOW_RECORD_ALL__
scene_intersect_shadow_all(KernelGlobals * kg,const Ray * ray,Intersection * isect,uint visibility,uint max_hits,uint * num_hits)355 ccl_device_intersect bool scene_intersect_shadow_all(KernelGlobals *kg,
356                                                      const Ray *ray,
357                                                      Intersection *isect,
358                                                      uint visibility,
359                                                      uint max_hits,
360                                                      uint *num_hits)
361 {
362   PROFILING_INIT(kg, PROFILING_INTERSECT_SHADOW_ALL);
363 
364 #  ifdef __KERNEL_OPTIX__
365   uint p0 = ((uint64_t)isect) & 0xFFFFFFFF;
366   uint p1 = (((uint64_t)isect) >> 32) & 0xFFFFFFFF;
367   uint p3 = max_hits;
368   uint p4 = visibility;
369   uint p5 = false;
370 
371   *num_hits = 0;  // Initialize hit count to zero
372   optixTrace(scene_intersect_valid(ray) ? kernel_data.bvh.scene : 0,
373              ray->P,
374              ray->D,
375              0.0f,
376              ray->t,
377              ray->time,
378              0xF,
379              // Need to always call into __anyhit__kernel_optix_shadow_all_hit
380              OPTIX_RAY_FLAG_ENFORCE_ANYHIT,
381              1,  // SBT offset for PG_HITS
382              0,
383              0,
384              p0,
385              p1,
386              *num_hits,
387              p3,
388              p4,
389              p5);
390 
391   return p5;
392 #  else /* __KERNEL_OPTIX__ */
393   if (!scene_intersect_valid(ray)) {
394     *num_hits = 0;
395     return false;
396   }
397 
398 #    ifdef __EMBREE__
399   if (kernel_data.bvh.scene) {
400     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_SHADOW_ALL);
401     ctx.isect_s = isect;
402     ctx.max_hits = max_hits;
403     ctx.num_hits = 0;
404     IntersectContext rtc_ctx(&ctx);
405     RTCRay rtc_ray;
406     kernel_embree_setup_ray(*ray, rtc_ray, visibility);
407     rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
408 
409     if (ctx.num_hits > max_hits) {
410       return true;
411     }
412     *num_hits = ctx.num_hits;
413     return rtc_ray.tfar == -INFINITY;
414   }
415 #    endif /* __EMBREE__ */
416 
417 #    ifdef __OBJECT_MOTION__
418   if (kernel_data.bvh.have_motion) {
419 #      ifdef __HAIR__
420     if (kernel_data.bvh.have_curves) {
421       return bvh_intersect_shadow_all_hair_motion(kg, ray, isect, visibility, max_hits, num_hits);
422     }
423 #      endif /* __HAIR__ */
424 
425     return bvh_intersect_shadow_all_motion(kg, ray, isect, visibility, max_hits, num_hits);
426   }
427 #    endif   /* __OBJECT_MOTION__ */
428 
429 #    ifdef __HAIR__
430   if (kernel_data.bvh.have_curves) {
431     return bvh_intersect_shadow_all_hair(kg, ray, isect, visibility, max_hits, num_hits);
432   }
433 #    endif /* __HAIR__ */
434 
435   return bvh_intersect_shadow_all(kg, ray, isect, visibility, max_hits, num_hits);
436 #  endif   /* __KERNEL_OPTIX__ */
437 }
438 #endif /* __SHADOW_RECORD_ALL__ */
439 
440 #ifdef __VOLUME__
scene_intersect_volume(KernelGlobals * kg,const Ray * ray,Intersection * isect,const uint visibility)441 ccl_device_intersect bool scene_intersect_volume(KernelGlobals *kg,
442                                                  const Ray *ray,
443                                                  Intersection *isect,
444                                                  const uint visibility)
445 {
446   PROFILING_INIT(kg, PROFILING_INTERSECT_VOLUME);
447 
448 #  ifdef __KERNEL_OPTIX__
449   uint p0 = 0;
450   uint p1 = 0;
451   uint p2 = 0;
452   uint p3 = 0;
453   uint p4 = visibility;
454   uint p5 = PRIMITIVE_NONE;
455 
456   optixTrace(scene_intersect_valid(ray) ? kernel_data.bvh.scene : 0,
457              ray->P,
458              ray->D,
459              0.0f,
460              ray->t,
461              ray->time,
462              // Skip everything but volumes
463              0x2,
464              OPTIX_RAY_FLAG_NONE,
465              0,  // SBT offset for PG_HITD
466              0,
467              0,
468              p0,
469              p1,
470              p2,
471              p3,
472              p4,
473              p5);
474 
475   isect->t = __uint_as_float(p0);
476   isect->u = __uint_as_float(p1);
477   isect->v = __uint_as_float(p2);
478   isect->prim = p3;
479   isect->object = p4;
480   isect->type = p5;
481 
482   return p5 != PRIMITIVE_NONE;
483 #  else /* __KERNEL_OPTIX__ */
484   if (!scene_intersect_valid(ray)) {
485     return false;
486   }
487 
488 #    ifdef __OBJECT_MOTION__
489   if (kernel_data.bvh.have_motion) {
490     return bvh_intersect_volume_motion(kg, ray, isect, visibility);
491   }
492 #    endif /* __OBJECT_MOTION__ */
493 
494   return bvh_intersect_volume(kg, ray, isect, visibility);
495 #  endif   /* __KERNEL_OPTIX__ */
496 }
497 #endif /* __VOLUME__ */
498 
499 #ifdef __VOLUME_RECORD_ALL__
scene_intersect_volume_all(KernelGlobals * kg,const Ray * ray,Intersection * isect,const uint max_hits,const uint visibility)500 ccl_device_intersect uint scene_intersect_volume_all(KernelGlobals *kg,
501                                                      const Ray *ray,
502                                                      Intersection *isect,
503                                                      const uint max_hits,
504                                                      const uint visibility)
505 {
506   PROFILING_INIT(kg, PROFILING_INTERSECT_VOLUME_ALL);
507 
508   if (!scene_intersect_valid(ray)) {
509     return false;
510   }
511 
512 #  ifdef __EMBREE__
513   if (kernel_data.bvh.scene) {
514     CCLIntersectContext ctx(kg, CCLIntersectContext::RAY_VOLUME_ALL);
515     ctx.isect_s = isect;
516     ctx.max_hits = max_hits;
517     ctx.num_hits = 0;
518     IntersectContext rtc_ctx(&ctx);
519     RTCRay rtc_ray;
520     kernel_embree_setup_ray(*ray, rtc_ray, visibility);
521     rtcOccluded1(kernel_data.bvh.scene, &rtc_ctx.context, &rtc_ray);
522     return ctx.num_hits;
523   }
524 #  endif /* __EMBREE__ */
525 
526 #  ifdef __OBJECT_MOTION__
527   if (kernel_data.bvh.have_motion) {
528     return bvh_intersect_volume_all_motion(kg, ray, isect, max_hits, visibility);
529   }
530 #  endif /* __OBJECT_MOTION__ */
531 
532   return bvh_intersect_volume_all(kg, ray, isect, max_hits, visibility);
533 }
534 #endif /* __VOLUME_RECORD_ALL__ */
535 
536 /* Ray offset to avoid self intersection.
537  *
538  * This function should be used to compute a modified ray start position for
539  * rays leaving from a surface. */
540 
ray_offset(float3 P,float3 Ng)541 ccl_device_inline float3 ray_offset(float3 P, float3 Ng)
542 {
543 #ifdef __INTERSECTION_REFINE__
544   const float epsilon_f = 1e-5f;
545   /* ideally this should match epsilon_f, but instancing and motion blur
546    * precision makes it problematic */
547   const float epsilon_test = 1.0f;
548   const int epsilon_i = 32;
549 
550   float3 res;
551 
552   /* x component */
553   if (fabsf(P.x) < epsilon_test) {
554     res.x = P.x + Ng.x * epsilon_f;
555   }
556   else {
557     uint ix = __float_as_uint(P.x);
558     ix += ((ix ^ __float_as_uint(Ng.x)) >> 31) ? -epsilon_i : epsilon_i;
559     res.x = __uint_as_float(ix);
560   }
561 
562   /* y component */
563   if (fabsf(P.y) < epsilon_test) {
564     res.y = P.y + Ng.y * epsilon_f;
565   }
566   else {
567     uint iy = __float_as_uint(P.y);
568     iy += ((iy ^ __float_as_uint(Ng.y)) >> 31) ? -epsilon_i : epsilon_i;
569     res.y = __uint_as_float(iy);
570   }
571 
572   /* z component */
573   if (fabsf(P.z) < epsilon_test) {
574     res.z = P.z + Ng.z * epsilon_f;
575   }
576   else {
577     uint iz = __float_as_uint(P.z);
578     iz += ((iz ^ __float_as_uint(Ng.z)) >> 31) ? -epsilon_i : epsilon_i;
579     res.z = __uint_as_float(iz);
580   }
581 
582   return res;
583 #else
584   const float epsilon_f = 1e-4f;
585   return P + epsilon_f * Ng;
586 #endif
587 }
588 
589 #if defined(__VOLUME_RECORD_ALL__) || (defined(__SHADOW_RECORD_ALL__) && defined(__KERNEL_CPU__))
590 /* ToDo: Move to another file? */
intersections_compare(const void * a,const void * b)591 ccl_device int intersections_compare(const void *a, const void *b)
592 {
593   const Intersection *isect_a = (const Intersection *)a;
594   const Intersection *isect_b = (const Intersection *)b;
595 
596   if (isect_a->t < isect_b->t)
597     return -1;
598   else if (isect_a->t > isect_b->t)
599     return 1;
600   else
601     return 0;
602 }
603 #endif
604 
605 #if defined(__SHADOW_RECORD_ALL__)
sort_intersections(Intersection * hits,uint num_hits)606 ccl_device_inline void sort_intersections(Intersection *hits, uint num_hits)
607 {
608 #  ifdef __KERNEL_GPU__
609   /* Use bubble sort which has more friendly memory pattern on GPU. */
610   bool swapped;
611   do {
612     swapped = false;
613     for (int j = 0; j < num_hits - 1; ++j) {
614       if (hits[j].t > hits[j + 1].t) {
615         struct Intersection tmp = hits[j];
616         hits[j] = hits[j + 1];
617         hits[j + 1] = tmp;
618         swapped = true;
619       }
620     }
621     --num_hits;
622   } while (swapped);
623 #  else
624   qsort(hits, num_hits, sizeof(Intersection), intersections_compare);
625 #  endif
626 }
627 #endif /* __SHADOW_RECORD_ALL__ | __VOLUME_RECORD_ALL__ */
628 
629 CCL_NAMESPACE_END
630