Blender V5.3
math_intersect.h
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2011-2022 Blender Foundation
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#pragma once
6
7#include "util/math_float2.h"
8#include "util/math_float3.h"
9#include "util/math_float4.h"
10
12
13/* Ray Intersection */
14
16 const float3 ray_D,
17 const float ray_tmin,
18 const float ray_tmax,
19 const float3 sphere_P,
20 const float sphere_radius,
21 ccl_private float3 *isect_P,
22 ccl_private float *isect_t)
23{
24 const float3 d_vec = sphere_P - ray_P;
25 const float r_sq = sphere_radius * sphere_radius;
26 const float d_sq = dot(d_vec, d_vec);
27 const float d_cos_theta = dot(d_vec, ray_D);
28
29 if (d_sq > r_sq && d_cos_theta < 0.0f) {
30 /* Ray origin outside sphere and points away from sphere. */
31 return false;
32 }
33
34 const float d_sin_theta_sq = len_squared(d_vec - d_cos_theta * ray_D);
35
36 if (d_sin_theta_sq > r_sq) {
37 /* Closest point on ray outside sphere. */
38 return false;
39 }
40
41 /* Law of cosines. */
42 const float t = d_cos_theta - copysignf(sqrtf(r_sq - d_sin_theta_sq), d_sq - r_sq);
43
44 if (t > ray_tmin && t < ray_tmax) {
45 *isect_t = t;
46 *isect_P = ray_P + ray_D * t;
47 return true;
48 }
49
50 return false;
51}
52
54 const float3 ray_D,
55 const float ray_tmin,
56 const float ray_tmax,
57 const float3 disk_P,
58 const float disk_radius,
59 ccl_private float3 *isect_P,
60 ccl_private float *isect_t)
61{
62 /* Aligned disk normal. */
63 float disk_t;
64 const float3 disk_N = normalize_len(ray_P - disk_P, &disk_t);
65 const float div = dot(ray_D, disk_N);
66 if (UNLIKELY(div == 0.0f)) {
67 return false;
68 }
69 /* Compute t to intersection point. */
70 const float t = -disk_t / div;
71 if (!(t > ray_tmin && t < ray_tmax)) {
72 return false;
73 }
74 /* Test if within radius. */
75 const float3 P = ray_P + ray_D * t;
76 if (len_squared(P - disk_P) > disk_radius * disk_radius) {
77 return false;
78 }
79 *isect_P = P;
80 *isect_t = t;
81 return true;
82}
83
85 const float3 ray_D,
86 const float ray_tmin,
87 const float ray_tmax,
88 const float3 disk_P,
89 const float3 disk_N,
90 const float disk_radius,
91 ccl_private float3 *isect_P,
92 ccl_private float *isect_t)
93{
94 const float3 vp = ray_P - disk_P;
95 const float dp = dot(vp, disk_N);
96 const float cos_angle = dot(disk_N, -ray_D);
97 if (dp * cos_angle > 0.f) { // front of light
98 const float t = dp / cos_angle;
99 if (t < 0.f) { /* Ray points away from the light. */
100 return false;
101 }
102 const float3 P = ray_P + t * ray_D;
103 const float3 T = P - disk_P;
104
105 if (dot(T, T) < sqr(disk_radius) && (t > ray_tmin && t < ray_tmax)) {
106 *isect_P = ray_P + t * ray_D;
107 *isect_t = t;
108 return true;
109 }
110 }
111 return false;
112}
113
114/* Custom rcp, cross and dot implementations that match Embree bit for bit. */
116{
117#ifdef __KERNEL_NEON__
118 /* Move scalar to vector register and do rcp. */
119 __m128 a = {0};
120 a = vsetq_lane_f32(x, a, 0);
121 float32x4_t rt_rcp = vrecpeq_f32(a);
122 rt_rcp = vmulq_f32(vrecpsq_f32(a, rt_rcp), rt_rcp);
123 rt_rcp = vmulq_f32(vrecpsq_f32(a, rt_rcp), rt_rcp);
124 return vgetq_lane_f32(rt_rcp, 0);
125#elif defined(__KERNEL_SSE__)
126 const __m128 a = _mm_set_ss(x);
127 const __m128 r = _mm_rcp_ss(a);
128
129# ifdef __KERNEL_AVX2_
130 return _mm_cvtss_f32(_mm_mul_ss(r, _mm_fnmadd_ss(r, a, _mm_set_ss(2.0f))));
131# else
132 return _mm_cvtss_f32(_mm_mul_ss(r, _mm_sub_ss(_mm_set_ss(2.0f), _mm_mul_ss(r, a))));
133# endif
134#else
135 return 1.0f / x;
136#endif
137}
138
140{
141#if defined(__KERNEL_SSE42__) && defined(__KERNEL_SSE__)
142 return madd(make_float4(a.x),
143 make_float4(b.x),
144 madd(make_float4(a.y), make_float4(b.y), make_float4(a.z) * make_float4(b.z)))[0];
145#else
146 return a.x * b.x + a.y * b.y + a.z * b.z;
147#endif
148}
149
151{
152#if defined(__KERNEL_SSE42__) && defined(__KERNEL_SSE__)
153 return make_float3(
156 msub(make_float4(a.x), make_float4(b.y), make_float4(a.y) * make_float4(b.x))[0]);
157#else
158 return make_float3(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
159#endif
160}
161
163 const float3 ray_D,
164 const float ray_tmin,
165 const float ray_tmax,
166 const float3 tri_a,
167 const float3 tri_b,
168 const float3 tri_c,
169 ccl_private float *isect_u,
170 ccl_private float *isect_v,
171 ccl_private float *isect_t)
172{
173 /* This implementation matches the Plücker coordinates triangle intersection
174 * in Embree. */
175
176 /* Calculate vertices relative to ray origin. */
177 const float3 v0 = tri_a - ray_P;
178 const float3 v1 = tri_b - ray_P;
179 const float3 v2 = tri_c - ray_P;
180
181 /* Calculate triangle edges. */
182 const float3 e0 = v2 - v0;
183 const float3 e1 = v0 - v1;
184 const float3 e2 = v1 - v2;
185
186 /* Perform edge tests. */
187 const float U = ray_triangle_dot(ray_triangle_cross(e0, v2 + v0), ray_D);
188 const float V = ray_triangle_dot(ray_triangle_cross(e1, v0 + v1), ray_D);
189 const float W = ray_triangle_dot(ray_triangle_cross(e2, v1 + v2), ray_D);
190
191 const float UVW = U + V + W;
192 const float eps = FLT_EPSILON * fabsf(UVW);
193 const float minUVW = min(U, min(V, W));
194 const float maxUVW = max(U, max(V, W));
195
196 if (!(minUVW >= -eps || maxUVW <= eps)) {
197 return false;
198 }
199
200 /* Calculate geometry normal and denominator. */
201 const float3 Ng1 = ray_triangle_cross(e1, e0);
202 const float3 Ng = Ng1 + Ng1;
203 const float den = dot(Ng, ray_D);
204 /* Avoid division by 0. */
205 if (UNLIKELY(den == 0.0f)) {
206 return false;
207 }
208
209 /* Perform depth test. */
210 const float T = dot(v0, Ng);
211 const float t = T / den;
212 if (!(t >= ray_tmin && t <= ray_tmax)) {
213 return false;
214 }
215
216 const float rcp_uvw = (fabsf(UVW) < 1e-18f) ? 0.0f : ray_triangle_reciprocal(UVW);
217 *isect_u = min(U * rcp_uvw, 1.0f);
218 *isect_v = min(V * rcp_uvw, 1.0f);
219 *isect_t = t;
220 return true;
221}
222
224 const float3 ray_D,
225 const float3 tri_a,
226 const float3 tri_b,
227 const float3 tri_c)
228{
229 /* Matches ray_triangle-intersect, for an intersection known to exist. */
230
231 /* Calculate vertices relative to ray origin. */
232 const float3 v0 = tri_a - ray_P;
233 const float3 v1 = tri_b - ray_P;
234 const float3 v2 = tri_c - ray_P;
235
236 /* Calculate triangle edges. */
237 const float3 e0 = v2 - v0;
238 const float3 e1 = v0 - v1;
239 const float3 e2 = v1 - v2;
240
241 /* Compute barycentric coordinates. */
242 const float U = ray_triangle_dot(ray_triangle_cross(e0, v2 + v0), ray_D);
243 const float V = ray_triangle_dot(ray_triangle_cross(e1, v0 + v1), ray_D);
244 const float W = ray_triangle_dot(ray_triangle_cross(e2, v1 + v2), ray_D);
245 const float UVW = U + V + W;
246
247 const float rcp_uvw = (fabsf(UVW) < 1e-18f) ? 0.0f : ray_triangle_reciprocal(UVW);
248 return make_float2(clamp(U * rcp_uvw, 0.0f, 1.0f), clamp(V * rcp_uvw, 0.0f, 1.0f));
249}
250
252 const float3 ray_D,
253 const float3 verts[3])
254{
255 /* Matches logic in ray_triangle_intersect, self intersection test to validate
256 * if a ray is going to hit self or might incorrectly hit a neighboring triangle. */
257
258 /* Calculate vertices relative to ray origin. */
259 const float3 v0 = verts[0] - ray_P;
260 const float3 v1 = verts[1] - ray_P;
261 const float3 v2 = verts[2] - ray_P;
262
263 /* Calculate triangle edges. */
264 const float3 e0 = v2 - v0;
265 const float3 e1 = v0 - v1;
266 const float3 e2 = v1 - v2;
267
268 /* Perform edge tests. */
269 const float U = ray_triangle_dot(ray_triangle_cross(v2 + v0, e0), ray_D);
270 const float V = ray_triangle_dot(ray_triangle_cross(v0 + v1, e1), ray_D);
271 const float W = ray_triangle_dot(ray_triangle_cross(v1 + v2, e2), ray_D);
272
273 const float eps = FLT_EPSILON * fabsf(U + V + W);
274 const float minUVW = min(U, min(V, W));
275 const float maxUVW = max(U, max(V, W));
276
277 /* Note the extended epsilon compared to ray_triangle_intersect, to account
278 * for intersections with neighboring triangles that have an epsilon. */
279 return (minUVW >= eps || maxUVW <= -eps);
280}
281
282/* Tests for an intersection between a ray and a quad defined by
283 * its midpoint, normal and sides.
284 * If ellipse is true, hits outside the ellipse that's enclosed by the
285 * quad are rejected.
286 */
288 const float3 ray_D,
289 const float ray_tmin,
290 const float ray_tmax,
291 const float3 quad_P,
292 const float3 inv_quad_u,
293 const float3 inv_quad_v,
294 const float3 quad_n,
295 ccl_private float3 *isect_P,
296 ccl_private float *isect_t,
297 ccl_private float *isect_u,
298 ccl_private float *isect_v,
299 bool ellipse)
300{
301 /* Perform intersection test. */
302 const float t = -(dot(ray_P, quad_n) - dot(quad_P, quad_n)) / dot(ray_D, quad_n);
303 if (!(t > ray_tmin && t < ray_tmax)) {
304 return false;
305 }
306 const float3 hit = ray_P + t * ray_D;
307 const float3 inplane = hit - quad_P;
308 const float u = dot(inplane, inv_quad_u);
309 if (u < -0.5f || u > 0.5f) {
310 return false;
311 }
312 const float v = dot(inplane, inv_quad_v);
313 if (v < -0.5f || v > 0.5f) {
314 return false;
315 }
316 if (ellipse && (u * u + v * v > 0.25f)) {
317 return false;
318 }
319 /* Store the result. */
320 /* TODO(sergey): Check whether we can avoid some checks here. */
321 if (isect_P != nullptr) {
322 *isect_P = hit;
323 }
324 if (isect_t != nullptr) {
325 *isect_t = t;
326 }
327
328 /* NOTE: Return barycentric coordinates in the same notation as Embree and OptiX. */
329 if (isect_u != nullptr) {
330 *isect_u = v + 0.5f;
331 }
332 if (isect_v != nullptr) {
333 *isect_v = -u - v;
334 }
335
336 return true;
337}
338
339/* Find the ray segment that lies in the same side as the normal `N` of the plane.
340 * `P` is the vector pointing from any point on the plane to the ray origin. */
342 const float3 P,
343 const float3 ray_D,
345{
346 const float DN = dot(ray_D, N);
347
348 /* Distance from P to the plane. */
349 const float t = -dot(P, N) / DN;
350
351 /* Limit the range to the positive side. */
352 if (DN > 0.0f) {
353 t_range->min = fmaxf(t_range->min, t);
354 }
355 else {
356 t_range->max = fminf(t_range->max, t);
357 }
358
359 return !t_range->is_empty();
360}
361
362/* Find the ray segment inside an axis-aligned bounding box. */
364 const float3 bbox_max,
365 const float3 ray_P,
366 const float3 ray_D,
368{
369 const float3 inv_ray_D = reciprocal(ray_D);
370
371 /* Absolute distances to lower and upper box coordinates; */
372 const float3 t_lower = (bbox_min - ray_P) * inv_ray_D;
373 const float3 t_upper = (bbox_max - ray_P) * inv_ray_D;
374
375 /* The four t-intervals (for x-/y-/z-slabs, and ray p(t)). */
376 const float4 tmins = make_float4(min(t_lower, t_upper), t_range->min);
377 const float4 tmaxes = make_float4(max(t_lower, t_upper), t_range->max);
378
379 /* Max of mins and min of maxes. */
380 const float tmin = reduce_max(tmins);
381 const float tmax = reduce_min(tmaxes);
382
383 *t_range = {tmin, tmax};
384
385 return !t_range->is_empty();
386}
387
388/* Find the segment of a ray defined by P + D * t that lies inside a cylinder defined by
389 * (x / len_u)^2 + (y / len_v)^2 = 1. */
391 const float3 D,
392 const float len_u,
393 const float len_v,
395{
396 /* Convert to a 2D problem. */
397 const float2 inv_len = 1.0f / make_float2(len_u, len_v);
398 float2 P_proj = make_float2(P) * inv_len;
399 const float2 D_proj = make_float2(D) * inv_len;
400
401 /* Solve quadratic equation a*t^2 + 2b*t + c = 0. */
402 const float a = dot(D_proj, D_proj);
403 float b = dot(P_proj, D_proj);
404
405 /* Move ray origin closer to the cylinder to prevent precision issue when the ray is far away. */
406 const float t_mid = -b / a;
407 P_proj += D_proj * t_mid;
408
409 /* Recompute b from the shifted origin. */
410 b = dot(P_proj, D_proj);
411 const float c = dot(P_proj, P_proj) - 1.0f;
412
413 float tmin;
414 float tmax;
415 const bool valid = solve_quadratic(a, 2.0f * b, c, tmin, tmax);
416
417 *t_range = intervals_intersection(*t_range, {tmin + t_mid, tmax + t_mid});
418
419 return valid && !t_range->is_empty();
420}
421
435 const float3 P,
436 float3 D,
437 const float cos_angle_sq,
439{
440 if (cos_angle_sq < 1e-4f) {
441 /* The cone is nearly a plane. */
442 return ray_plane_intersect(axis, P, D, t_range);
443 }
444
445 const float inv_len = inversesqrtf(len_squared(D));
446 D *= inv_len;
447
448 const float AD = dot(axis, D);
449 const float AP = dot(axis, P);
450
451 const float a = sqr(AD) - cos_angle_sq;
452 const float b = 2.0f * (AD * AP - cos_angle_sq * dot(D, P));
453 const float c = sqr(AP) - cos_angle_sq * dot(P, P);
454
455 float tmin = 0.0f;
456 float tmax = FLT_MAX;
457 bool valid = solve_quadratic(a, b, c, tmin, tmax);
458
459 /* Check if the intersections are in the same hemisphere as the cone. */
460 const bool tmin_valid = AP + tmin * AD > 0.0f;
461 const bool tmax_valid = AP + tmax * AD > 0.0f;
462
463 valid &= (tmin_valid || tmax_valid);
464
465 if (!tmax_valid) {
466 tmax = tmin;
467 tmin = 0.0f;
468 }
469 else if (!tmin_valid) {
470 tmin = tmax;
471 tmax = FLT_MAX;
472 }
473
474 *t_range = intervals_intersection(*t_range, {tmin * inv_len, tmax * inv_len});
475
476 return valid && !t_range->is_empty();
477}
478
#define D
#define U
#define UNLIKELY(x)
btScalar max
#define ccl_device_forceinline
#define ccl_private
#define ccl_device_inline
#define CCL_NAMESPACE_END
ccl_device_forceinline float3 make_float3(const float x, const float y, const float z)
#define copysignf(x, y)
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
constexpr T clamp(T, U, U) RET
float reduce_min(float2 a)
float reduce_max(float2 a)
ccl_device_inline float inversesqrtf(const float f)
Definition math_base.h:576
ccl_device_inline bool solve_quadratic(const float a, const float b, const float c, ccl_private float &x1, ccl_private float &x2)
Definition math_base.h:888
ccl_device_inline Interval< T > intervals_intersection(const ccl_private Interval< T > &first, const ccl_private Interval< T > &second)
Definition math_base.h:947
ccl_device_inline dual1 len_squared(const ccl_private dual< T > &a)
Definition math_dual.h:273
CCL_NAMESPACE_BEGIN ccl_device_inline float madd(const float a, const float b, const float c)
Definition math_fast.h:35
ccl_device_inline float2 normalize_len(const float2 a, ccl_private float *t)
ccl_device_inline float3 reciprocal(const float3 a)
Definition math_float3.h:36
ccl_device_inline float4 msub(const float4 a, const float4 b, const float4 c)
ccl_device_inline bool ray_cone_intersect(const float3 axis, const float3 P, float3 D, const float cos_angle_sq, ccl_private Interval< float > *t_range)
ccl_device bool ray_disk_intersect(const float3 ray_P, const float3 ray_D, const float ray_tmin, const float ray_tmax, const float3 disk_P, const float3 disk_N, const float disk_radius, ccl_private float3 *isect_P, ccl_private float *isect_t)
ccl_device bool ray_aabb_intersect(const float3 bbox_min, const float3 bbox_max, const float3 ray_P, const float3 ray_D, ccl_private Interval< float > *t_range)
ccl_device_forceinline float2 ray_triangle_uv(const float3 ray_P, const float3 ray_D, const float3 tri_a, const float3 tri_b, const float3 tri_c)
CCL_NAMESPACE_BEGIN ccl_device bool ray_sphere_intersect(const float3 ray_P, const float3 ray_D, const float ray_tmin, const float ray_tmax, const float3 sphere_P, const float sphere_radius, ccl_private float3 *isect_P, ccl_private float *isect_t)
ccl_device_forceinline bool ray_triangle_intersect(const float3 ray_P, const float3 ray_D, const float ray_tmin, const float ray_tmax, const float3 tri_a, const float3 tri_b, const float3 tri_c, ccl_private float *isect_u, ccl_private float *isect_v, ccl_private float *isect_t)
ccl_device_forceinline float ray_triangle_reciprocal(const float x)
ccl_device bool ray_aligned_disk_intersect(const float3 ray_P, const float3 ray_D, const float ray_tmin, const float ray_tmax, const float3 disk_P, const float disk_radius, ccl_private float3 *isect_P, ccl_private float *isect_t)
ccl_device_inline bool ray_infinite_cylinder_intersect(const float3 P, const float3 D, const float len_u, const float len_v, ccl_private Interval< float > *t_range)
ccl_device bool ray_plane_intersect(const float3 N, const float3 P, const float3 ray_D, ccl_private Interval< float > *t_range)
ccl_device_forceinline bool ray_triangle_intersect_self(const float3 ray_P, const float3 ray_D, const float3 verts[3])
ccl_device_inline float3 ray_triangle_cross(const float3 a, const float3 b)
ccl_device bool ray_quad_intersect(const float3 ray_P, const float3 ray_D, const float ray_tmin, const float ray_tmax, const float3 quad_P, const float3 inv_quad_u, const float3 inv_quad_v, const float3 quad_n, ccl_private float3 *isect_P, ccl_private float *isect_t, ccl_private float *isect_u, ccl_private float *isect_v, bool ellipse)
ccl_device_inline float ray_triangle_dot(const float3 a, const float3 b)
#define N
#define T
const btScalar eps
Definition poly34.cpp:11
#define sqr
#define fabsf
#define sqrtf
#define ccl_device
#define fmaxf
#define make_float2
#define make_float4
#define fminf
#define min(a, b)
Definition sort.cc:38
float z
Definition sky_math.h:136
float y
Definition sky_math.h:136
float x
Definition sky_math.h:136
CCL_NAMESPACE_BEGIN struct Window V