Blender  V3.3
traversal.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0
2  * Adapted from code Copyright 2009-2010 NVIDIA Corporation,
3  * and code copyright 2009-2012 Intel Corporation
4  *
5  * Modifications Copyright 2011-2022 Blender Foundation. */
6 
7 #if BVH_FEATURE(BVH_HAIR)
8 # define NODE_INTERSECT bvh_node_intersect
9 #else
10 # define NODE_INTERSECT bvh_aligned_node_intersect
11 #endif
12 
13 /* This is a template BVH traversal function, where various features can be
14  * enabled/disabled. This way we can compile optimized versions for each case
15  * without new features slowing things down.
16  *
17  * BVH_HAIR: hair curve rendering
18  * BVH_POINTCLOUD: point cloud rendering
19  * BVH_MOTION: motion blur rendering
20  */
21 
23  ccl_private const Ray *ray,
25  const uint visibility)
26 {
27  /* todo:
28  * - test if pushing distance on the stack helps (for non shadow rays)
29  * - separate version for shadow rays
30  * - likely and unlikely for if() statements
31  * - test restrict attribute for pointers
32  */
33 
34  /* traversal stack in CUDA thread-local memory */
37 
38  /* traversal variables in registers */
39  int stack_ptr = 0;
40  int node_addr = kernel_data.bvh.root;
41 
42  /* ray parameters in registers */
43  float3 P = ray->P;
44  float3 dir = bvh_clamp_direction(ray->D);
45  float3 idir = bvh_inverse_direction(dir);
46  const float tmin = ray->tmin;
47  int object = OBJECT_NONE;
48 
49  isect->t = ray->tmax;
50  isect->u = 0.0f;
51  isect->v = 0.0f;
52  isect->prim = PRIM_NONE;
53  isect->object = OBJECT_NONE;
54 
55  /* traversal loop */
56  do {
57  do {
58  /* traverse internal nodes */
59  while (node_addr >= 0 && node_addr != ENTRYPOINT_SENTINEL) {
60  int node_addr_child1, traverse_mask;
61  float dist[2];
62  float4 cnodes = kernel_data_fetch(bvh_nodes, node_addr + 0);
63 
64  {
65  traverse_mask = NODE_INTERSECT(kg,
66  P,
68  dir,
69 #endif
70  idir,
71  tmin,
72  isect->t,
73  node_addr,
74  visibility,
75  dist);
76  }
77 
78  node_addr = __float_as_int(cnodes.z);
79  node_addr_child1 = __float_as_int(cnodes.w);
80 
81  if (traverse_mask == 3) {
82  /* Both children were intersected, push the farther one. */
83  bool is_closest_child1 = (dist[1] < dist[0]);
84  if (is_closest_child1) {
85  int tmp = node_addr;
86  node_addr = node_addr_child1;
87  node_addr_child1 = tmp;
88  }
89 
90  ++stack_ptr;
91  kernel_assert(stack_ptr < BVH_STACK_SIZE);
92  traversal_stack[stack_ptr] = node_addr_child1;
93  }
94  else {
95  /* One child was intersected. */
96  if (traverse_mask == 2) {
97  node_addr = node_addr_child1;
98  }
99  else if (traverse_mask == 0) {
100  /* Neither child was intersected. */
101  node_addr = traversal_stack[stack_ptr];
102  --stack_ptr;
103  }
104  }
105  }
106 
107  /* if node is leaf, fetch triangle list */
108  if (node_addr < 0) {
109  float4 leaf = kernel_data_fetch(bvh_leaf_nodes, (-node_addr - 1));
110  int prim_addr = __float_as_int(leaf.x);
111 
112  if (prim_addr >= 0) {
113  const int prim_addr2 = __float_as_int(leaf.y);
114  const uint type = __float_as_int(leaf.w);
115 
116  /* pop */
117  node_addr = traversal_stack[stack_ptr];
118  --stack_ptr;
119 
120  /* primitive intersection */
121  for (; prim_addr < prim_addr2; prim_addr++) {
122  kernel_assert(kernel_data_fetch(prim_type, prim_addr) == type);
123 
124  const int prim_object = (object == OBJECT_NONE) ?
125  kernel_data_fetch(prim_object, prim_addr) :
126  object;
127  const int prim = kernel_data_fetch(prim_index, prim_addr);
128  if (intersection_skip_self_shadow(ray->self, prim_object, prim)) {
129  continue;
130  }
131 
132  switch (type & PRIMITIVE_ALL) {
133  case PRIMITIVE_TRIANGLE: {
134  if (triangle_intersect(kg,
135  isect,
136  P,
137  dir,
138  tmin,
139  isect->t,
140  visibility,
141  prim_object,
142  prim,
143  prim_addr)) {
144  /* shadow ray early termination */
145  if (visibility & PATH_RAY_SHADOW_OPAQUE)
146  return true;
147  }
148  break;
149  }
150 #if BVH_FEATURE(BVH_MOTION)
153  isect,
154  P,
155  dir,
156  tmin,
157  isect->t,
158  ray->time,
159  visibility,
160  prim_object,
161  prim,
162  prim_addr)) {
163  /* shadow ray early termination */
164  if (visibility & PATH_RAY_SHADOW_OPAQUE)
165  return true;
166  }
167  break;
168  }
169 #endif /* BVH_FEATURE(BVH_MOTION) */
170 #if BVH_FEATURE(BVH_HAIR)
175  if ((type & PRIMITIVE_MOTION) && kernel_data.bvh.use_bvh_steps) {
176  const float2 prim_time = kernel_data_fetch(prim_time, prim_addr);
177  if (ray->time < prim_time.x || ray->time > prim_time.y) {
178  break;
179  }
180  }
181 
182  const int curve_type = kernel_data_fetch(prim_type, prim_addr);
183  const bool hit = curve_intersect(
184  kg, isect, P, dir, tmin, isect->t, prim_object, prim, ray->time, curve_type);
185  if (hit) {
186  /* shadow ray early termination */
187  if (visibility & PATH_RAY_SHADOW_OPAQUE)
188  return true;
189  }
190  break;
191  }
192 #endif /* BVH_FEATURE(BVH_HAIR) */
193 #if BVH_FEATURE(BVH_POINTCLOUD)
194  case PRIMITIVE_POINT:
195  case PRIMITIVE_MOTION_POINT: {
196  if ((type & PRIMITIVE_MOTION) && kernel_data.bvh.use_bvh_steps) {
197  const float2 prim_time = kernel_data_fetch(prim_time, prim_addr);
198  if (ray->time < prim_time.x || ray->time > prim_time.y) {
199  break;
200  }
201  }
202 
203  const int point_type = kernel_data_fetch(prim_type, prim_addr);
204  const bool hit = point_intersect(
205  kg, isect, P, dir, tmin, isect->t, prim_object, prim, ray->time, point_type);
206  if (hit) {
207  /* shadow ray early termination */
208  if (visibility & PATH_RAY_SHADOW_OPAQUE)
209  return true;
210  }
211  break;
212  }
213 #endif /* BVH_FEATURE(BVH_POINTCLOUD) */
214  }
215  }
216  }
217  else {
218  /* instance push */
219  object = kernel_data_fetch(prim_object, -prim_addr - 1);
220 
221 #if BVH_FEATURE(BVH_MOTION)
222  bvh_instance_motion_push(kg, object, ray, &P, &dir, &idir);
223 #else
224  bvh_instance_push(kg, object, ray, &P, &dir, &idir);
225 #endif
226 
227  ++stack_ptr;
228  kernel_assert(stack_ptr < BVH_STACK_SIZE);
230 
231  node_addr = kernel_data_fetch(object_node, object);
232  }
233  }
234  } while (node_addr != ENTRYPOINT_SENTINEL);
235 
236  if (stack_ptr >= 0) {
237  kernel_assert(object != OBJECT_NONE);
238 
239  /* instance pop */
240  bvh_instance_pop(ray, &P, &dir, &idir);
241 
242  object = OBJECT_NONE;
243  node_addr = traversal_stack[stack_ptr];
244  --stack_ptr;
245  }
246  } while (node_addr != ENTRYPOINT_SENTINEL);
247 
248  return (isect->prim != PRIM_NONE);
249 }
250 
252  ccl_private const Ray *ray,
253  ccl_private Intersection *isect,
254  const uint visibility)
255 {
256  return BVH_FUNCTION_FULL_NAME(BVH)(kg, ray, isect, visibility);
257 }
258 
259 #undef BVH_FUNCTION_NAME
260 #undef BVH_FUNCTION_FEATURES
261 #undef NODE_INTERSECT
unsigned int uint
Definition: BLI_sys_types.h:67
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
float float4[4]
Definition: bvh/bvh.h:63
#define kernel_assert(cond)
Definition: cpu/compat.h:34
#define ccl_private
Definition: cuda/compat.h:48
#define ccl_device_inline
Definition: cuda/compat.h:34
#define ccl_device_noinline
Definition: cuda/compat.h:40
ccl_device_inline bool intersection_skip_self_shadow(ccl_private const RaySelfPrimitives &self, const int object, const int prim)
BLI_Stack * traversal_stack
#define kernel_data
const KernelGlobalsCPU *ccl_restrict KernelGlobals
#define kernel_data_fetch(name, index)
#define BVH_STACK_SIZE
#define BVH_FEATURE(f)
#define ENTRYPOINT_SENTINEL
#define BVH_HAIR
#define BVH_FUNCTION_FULL_NAME(prefix)
ccl_device_inline void bvh_instance_push(KernelGlobals kg, int object, ccl_private const Ray *ray, ccl_private float3 *P, ccl_private float3 *dir, ccl_private float3 *idir)
ccl_device_inline float3 bvh_clamp_direction(float3 dir)
ccl_device_inline void bvh_instance_pop(ccl_private const Ray *ray, ccl_private float3 *P, ccl_private float3 *dir, ccl_private float3 *idir)
ccl_device_inline float3 bvh_inverse_direction(float3 dir)
@ PRIMITIVE_MOTION_CURVE_RIBBON
Definition: kernel/types.h:561
@ PRIMITIVE_ALL
Definition: kernel/types.h:566
@ PRIMITIVE_MOTION
Definition: kernel/types.h:558
@ PRIMITIVE_MOTION_TRIANGLE
Definition: kernel/types.h:559
@ PRIMITIVE_CURVE_RIBBON
Definition: kernel/types.h:553
@ PRIMITIVE_MOTION_CURVE_THICK
Definition: kernel/types.h:560
@ PRIMITIVE_CURVE_THICK
Definition: kernel/types.h:552
@ PRIMITIVE_TRIANGLE
Definition: kernel/types.h:551
@ PRIMITIVE_MOTION_POINT
Definition: kernel/types.h:562
@ PRIMITIVE_POINT
Definition: kernel/types.h:554
#define PRIM_NONE
Definition: kernel/types.h:41
@ PATH_RAY_SHADOW_OPAQUE
Definition: kernel/types.h:204
#define OBJECT_NONE
Definition: kernel/types.h:40
static float P(float k)
Definition: math_interp.c:25
ccl_device_inline bool motion_triangle_intersect(KernelGlobals kg, ccl_private Intersection *isect, float3 P, float3 dir, float tmin, float tmax, float time, uint visibility, int object, int prim, int prim_addr)
float x
Definition: types_float2.h:15
float y
Definition: types_float2.h:15
ccl_device_inline bool BVH_FUNCTION_NAME(KernelGlobals kg, ccl_private const Ray *ray, ccl_private Intersection *isect, const uint visibility)
Definition: traversal.h:251
#define NODE_INTERSECT
Definition: traversal.h:10
CCL_NAMESPACE_BEGIN ccl_device_inline bool triangle_intersect(KernelGlobals kg, ccl_private Intersection *isect, float3 P, float3 dir, float tmin, float tmax, uint visibility, int object, int prim, int prim_addr)
ccl_device_inline int __float_as_int(float f)
Definition: util/math.h:243