1 | /* graphene-ray.c: A ray emitted from an origin in a given direction |
2 | * |
3 | * SPDX-License-Identifier: MIT |
4 | * |
5 | * Copyright 2015 Emmanuele Bassi |
6 | * |
7 | * Permission is hereby granted, free of charge, to any person obtaining a copy |
8 | * of this software and associated documentation files (the "Software"), to deal |
9 | * in the Software without restriction, including without limitation the rights |
10 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
11 | * copies of the Software, and to permit persons to whom the Software is |
12 | * furnished to do so, subject to the following conditions: |
13 | * |
14 | * The above copyright notice and this permission notice shall be included in |
15 | * all copies or substantial portions of the Software. |
16 | * |
17 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
18 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
19 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
20 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
21 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
22 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
23 | * THE SOFTWARE. |
24 | */ |
25 | |
26 | /** |
27 | * SECTION:graphene-ray |
28 | * @Title: Ray |
29 | * @Short_Description: A ray emitted from an origin in a given direction |
30 | * |
31 | * #graphene_ray_t is a structure representing a ray emitted by an origin, |
32 | * identified by a point in 3D space, in a given direction, identified |
33 | * by a vector with 3 components. |
34 | * |
35 | * A common use of #graphene_ray_t is ray-casting to find which objects in |
36 | * a 3D scene are under the coordinates of the pointer. |
37 | */ |
38 | |
39 | #include "graphene-private.h" |
40 | |
41 | #include "graphene-ray.h" |
42 | |
43 | #include "graphene-alloc-private.h" |
44 | #include "graphene-box.h" |
45 | #include "graphene-plane.h" |
46 | #include "graphene-point3d.h" |
47 | #include "graphene-simd4f.h" |
48 | #include "graphene-sphere.h" |
49 | #include "graphene-vec3.h" |
50 | #include "graphene-triangle.h" |
51 | |
52 | #include <math.h> |
53 | #include <float.h> |
54 | |
55 | #if defined(_M_X64) && ! defined(isnanf) |
56 | # define isnanf(x) _isnanf(x) |
57 | # define HAVE_ISNANF |
58 | #endif |
59 | |
60 | /** |
61 | * graphene_ray_alloc: (constructor) |
62 | * |
63 | * Allocates a new #graphene_ray_t structure. |
64 | * |
65 | * The contents of the returned structure are undefined. |
66 | * |
67 | * Returns: (transfer full): the newly allocated #graphene_ray_t. |
68 | * Use graphene_ray_free() to free the resources allocated by |
69 | * this function |
70 | * |
71 | * Since: 1.4 |
72 | */ |
73 | graphene_ray_t * |
74 | graphene_ray_alloc (void) |
75 | { |
76 | return graphene_aligned_alloc (size: sizeof (graphene_ray_t), number: 1, alignment: 16); |
77 | } |
78 | |
79 | /** |
80 | * graphene_ray_free: |
81 | * @r: a #graphene_ray_t |
82 | * |
83 | * Frees the resources allocated by graphene_ray_alloc(). |
84 | * |
85 | * Since: 1.4 |
86 | */ |
87 | void |
88 | graphene_ray_free (graphene_ray_t *r) |
89 | { |
90 | graphene_aligned_free (mem: r); |
91 | } |
92 | |
93 | /** |
94 | * graphene_ray_init: |
95 | * @r: the #graphene_ray_t to initialize |
96 | * @origin: (nullable): the origin of the ray |
97 | * @direction: (nullable): the direction vector |
98 | * |
99 | * Initializes the given #graphene_ray_t using the given @origin |
100 | * and @direction values. |
101 | * |
102 | * Returns: (transfer none): the initialized ray |
103 | * |
104 | * Since: 1.4 |
105 | */ |
106 | graphene_ray_t * |
107 | graphene_ray_init (graphene_ray_t *r, |
108 | const graphene_point3d_t *origin, |
109 | const graphene_vec3_t *direction) |
110 | { |
111 | if (origin != NULL) |
112 | graphene_point3d_to_vec3 (p: origin, v: &r->origin); |
113 | else |
114 | graphene_vec3_init_from_vec3 (v: &r->origin, src: graphene_vec3_zero ()); |
115 | |
116 | if (direction != NULL) |
117 | graphene_vec3_normalize (v: direction, res: &r->direction); |
118 | else |
119 | graphene_vec3_init_from_vec3 (v: &r->direction, src: graphene_vec3_zero ()); |
120 | |
121 | return r; |
122 | } |
123 | |
124 | /** |
125 | * graphene_ray_init_from_ray: |
126 | * @r: the #graphene_ray_t to initialize |
127 | * @src: a #graphene_ray_t |
128 | * |
129 | * Initializes the given #graphene_ray_t using the origin and direction |
130 | * values of another #graphene_ray_t. |
131 | * |
132 | * Returns: (transfer none): the initialized ray |
133 | * |
134 | * Since: 1.4 |
135 | */ |
136 | graphene_ray_t * |
137 | graphene_ray_init_from_ray (graphene_ray_t *r, |
138 | const graphene_ray_t *src) |
139 | { |
140 | return graphene_ray_init_from_vec3 (r, origin: &src->origin, direction: &src->direction); |
141 | } |
142 | |
143 | /** |
144 | * graphene_ray_init_from_vec3: |
145 | * @r: the #graphene_ray_t to initialize |
146 | * @origin: (nullable): a #graphene_vec3_t |
147 | * @direction: (nullable): a #graphene_vec3_t |
148 | * |
149 | * Initializes the given #graphene_ray_t using the given vectors. |
150 | * |
151 | * Returns: (transfer none): the initialized ray |
152 | * |
153 | * Since: 1.4 |
154 | */ |
155 | graphene_ray_t * |
156 | graphene_ray_init_from_vec3 (graphene_ray_t *r, |
157 | const graphene_vec3_t *origin, |
158 | const graphene_vec3_t *direction) |
159 | { |
160 | if (origin != NULL) |
161 | graphene_vec3_init_from_vec3 (v: &r->origin, src: origin); |
162 | else |
163 | graphene_vec3_init_from_vec3 (v: &r->origin, src: graphene_vec3_zero ()); |
164 | |
165 | if (direction != NULL) |
166 | graphene_vec3_normalize (v: direction, res: &r->direction); |
167 | else |
168 | graphene_vec3_init_from_vec3 (v: &r->direction, src: graphene_vec3_zero ()); |
169 | |
170 | return r; |
171 | } |
172 | |
173 | /** |
174 | * graphene_ray_get_origin: |
175 | * @r: a #graphene_ray_t |
176 | * @origin: (out caller-allocates): return location for the origin |
177 | * |
178 | * Retrieves the origin of the given #graphene_ray_t. |
179 | * |
180 | * Since: 1.4 |
181 | */ |
182 | void |
183 | graphene_ray_get_origin (const graphene_ray_t *r, |
184 | graphene_point3d_t *origin) |
185 | { |
186 | graphene_point3d_init_from_vec3 (p: origin, v: &r->origin); |
187 | } |
188 | |
189 | /** |
190 | * graphene_ray_get_direction: |
191 | * @r: a #graphene_ray_t |
192 | * @direction: (out caller-allocates): return location for the direction |
193 | * |
194 | * Retrieves the direction of the given #graphene_ray_t. |
195 | * |
196 | * Since: 1.4 |
197 | */ |
198 | void |
199 | graphene_ray_get_direction (const graphene_ray_t *r, |
200 | graphene_vec3_t *direction) |
201 | { |
202 | graphene_vec3_init_from_vec3 (v: direction, src: &r->direction); |
203 | } |
204 | |
205 | /** |
206 | * graphene_ray_get_position_at: |
207 | * @r: a #graphene_ray_t |
208 | * @t: the distance along the ray |
209 | * @position: (out caller-allocates): return location for the position |
210 | * |
211 | * Retrieves the coordinates of a point at the distance @t along the |
212 | * given #graphene_ray_t. |
213 | * |
214 | * Since: 1.4 |
215 | */ |
216 | void |
217 | graphene_ray_get_position_at (const graphene_ray_t *r, |
218 | float t, |
219 | graphene_point3d_t *position) |
220 | { |
221 | graphene_vec3_t res; |
222 | |
223 | graphene_vec3_scale (v: &r->direction, factor: t, res: &res); |
224 | graphene_vec3_add (a: &res, b: &r->origin, res: &res); |
225 | |
226 | graphene_point3d_init_from_vec3 (p: position, v: &res); |
227 | } |
228 | |
229 | /** |
230 | * graphene_ray_get_distance_to_point: |
231 | * @r: a #graphene_ray_t |
232 | * @p: a #graphene_point3d_t |
233 | * |
234 | * Computes the distance of the closest approach between the |
235 | * given #graphene_ray_t @r and the point @p. |
236 | * |
237 | * The closest approach to a ray from a point is the distance |
238 | * between the point and the projection of the point on the |
239 | * ray itself. |
240 | * |
241 | * Returns: the distance of the point |
242 | * |
243 | * Since: 1.4 |
244 | */ |
245 | float |
246 | graphene_ray_get_distance_to_point (const graphene_ray_t *r, |
247 | const graphene_point3d_t *p) |
248 | { |
249 | graphene_vec3_t point; |
250 | graphene_vec3_t tmp; |
251 | float distance; |
252 | |
253 | graphene_point3d_to_vec3 (p, v: &point); |
254 | |
255 | graphene_vec3_subtract (a: &point, b: &r->origin, res: &tmp); |
256 | distance = graphene_vec3_dot (a: &tmp, b: &r->direction); |
257 | |
258 | /* the point is behind the ray */ |
259 | if (distance < 0) |
260 | { |
261 | graphene_vec3_subtract (a: &r->origin, b: &point, res: &tmp); |
262 | return graphene_vec3_length (v: &tmp); |
263 | } |
264 | |
265 | /* get the position on the ray at the given distance */ |
266 | graphene_vec3_scale (v: &r->direction, factor: distance, res: &tmp); |
267 | graphene_vec3_add (a: &tmp, b: &r->origin, res: &tmp); |
268 | |
269 | /* distance */ |
270 | graphene_vec3_subtract (a: &tmp, b: &point, res: &tmp); |
271 | return graphene_vec3_length (v: &tmp); |
272 | } |
273 | |
274 | /** |
275 | * graphene_ray_get_distance_to_plane: |
276 | * @r: a #graphene_ray_t |
277 | * @p: a #graphene_plane_t |
278 | * |
279 | * Computes the distance of the origin of the given #graphene_ray_t from the |
280 | * given plane. |
281 | * |
282 | * If the ray does not intersect the plane, this function returns `INFINITY`. |
283 | * |
284 | * Returns: the distance of the origin of the ray from the plane |
285 | * |
286 | * Since: 1.4 |
287 | */ |
288 | float |
289 | graphene_ray_get_distance_to_plane (const graphene_ray_t *r, |
290 | const graphene_plane_t *p) |
291 | { |
292 | float denom, t; |
293 | |
294 | denom = graphene_vec3_dot (a: &p->normal, b: &r->direction); |
295 | if (fabsf (x: denom) < GRAPHENE_FLOAT_EPSILON) |
296 | { |
297 | graphene_point3d_t tmp; |
298 | |
299 | /* If the ray is coplanar, return 0 */ |
300 | graphene_point3d_init_from_vec3 (p: &tmp, v: &r->origin); |
301 | if (fabsf (x: graphene_plane_distance (p, point: &tmp)) < GRAPHENE_FLOAT_EPSILON) |
302 | return 0.f; |
303 | |
304 | return INFINITY; |
305 | } |
306 | |
307 | t = -1.f * (graphene_vec3_dot (a: &r->origin, b: &p->normal) + p->constant) / denom; |
308 | if (t >= 0.f) |
309 | return t; |
310 | |
311 | return INFINITY; |
312 | } |
313 | |
314 | static bool |
315 | ray_equal (const void *p1, |
316 | const void *p2) |
317 | { |
318 | const graphene_ray_t *a = p1; |
319 | const graphene_ray_t *b = p2; |
320 | |
321 | return graphene_vec3_equal (v1: &a->origin, v2: &b->origin) && |
322 | graphene_vec3_equal (v1: &a->direction, v2: &b->direction); |
323 | } |
324 | |
325 | /** |
326 | * graphene_ray_equal: |
327 | * @a: a #graphene_ray_t |
328 | * @b: a #graphene_ray_t |
329 | * |
330 | * Checks whether the two given #graphene_ray_t are equal. |
331 | * |
332 | * Returns: `true` if the given rays are equal |
333 | * |
334 | * Since: 1.4 |
335 | */ |
336 | bool |
337 | graphene_ray_equal (const graphene_ray_t *a, |
338 | const graphene_ray_t *b) |
339 | { |
340 | return graphene_pointer_equal (p1: a, p2: b, func: ray_equal); |
341 | } |
342 | |
343 | /** |
344 | * graphene_ray_get_closest_point_to_point: |
345 | * @r: a #graphene_ray_t |
346 | * @p: a #graphene_point3d_t |
347 | * @res: (out caller-allocates): return location for the closest point3d |
348 | * |
349 | * Computes the point on the given #graphene_ray_t that is closest to the |
350 | * given point @p. |
351 | * |
352 | * Since: 1.4 |
353 | */ |
354 | void |
355 | graphene_ray_get_closest_point_to_point (const graphene_ray_t *r, |
356 | const graphene_point3d_t *p, |
357 | graphene_point3d_t *res) |
358 | { |
359 | graphene_vec3_t point, result; |
360 | float distance; |
361 | |
362 | graphene_point3d_to_vec3 (p, v: &point); |
363 | graphene_vec3_subtract (a: &point, b: &r->origin, res: &result); |
364 | |
365 | distance = graphene_vec3_dot (a: &result, b: &r->direction); |
366 | if (distance < 0) |
367 | graphene_vec3_init_from_vec3 (v: &result, src: &r->origin); |
368 | else |
369 | { |
370 | graphene_vec3_scale (v: &r->direction, factor: distance, res: &result); |
371 | graphene_vec3_add (a: &result, b: &r->origin, res: &result); |
372 | } |
373 | |
374 | graphene_point3d_init_from_vec3 (p: res, v: &result); |
375 | } |
376 | |
377 | /** |
378 | * graphene_ray_intersect_sphere: |
379 | * @r: a #graphene_ray_t |
380 | * @s: a #graphene_sphere_t |
381 | * @t_out: (out): the distance of the point on the ray that intersects the sphere |
382 | * |
383 | * Intersects the given #graphene_ray_t @r with the given |
384 | * #graphene_sphere_t @s. |
385 | * |
386 | * Returns: the type of intersection |
387 | * |
388 | * Since: 1.10 |
389 | */ |
390 | graphene_ray_intersection_kind_t |
391 | graphene_ray_intersect_sphere (const graphene_ray_t *r, |
392 | const graphene_sphere_t *s, |
393 | float *t_out) |
394 | { |
395 | graphene_vec3_t v1; |
396 | |
397 | graphene_vec3_subtract (a: &s->center, b: &r->origin, res: &v1); |
398 | |
399 | /* initialize t_out, if set, so we don't have to do that every |
400 | * time we bail out with no intersection |
401 | */ |
402 | if (t_out != NULL) |
403 | *t_out = 0.f; |
404 | |
405 | /* (signed) distance along ray to point nearest sphere center */ |
406 | float tca = graphene_vec3_dot (a: &v1, b: &r->direction); |
407 | |
408 | /* square of distance from ray line to sphere center */ |
409 | float d2 = graphene_vec3_dot (a: &v1, b: &v1) - tca * tca; |
410 | |
411 | float radius2 = s->radius * s->radius; |
412 | if (d2 > radius2) |
413 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
414 | |
415 | /* Distance to entry/exit point */ |
416 | float thc = sqrtf (x: radius2 - d2); |
417 | |
418 | /* t0 = first intersect point - entrance on front of sphere */ |
419 | float t0 = tca - thc; |
420 | |
421 | /* t1 = second intersect point - exit point on back of sphere */ |
422 | float t1 = tca + thc; |
423 | |
424 | // test to see if both t0 and t1 are behind the ray - if so, no intersection |
425 | if (t0 < 0 && t1 < 0) |
426 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
427 | |
428 | /* test to see if t0 is behind the ray. |
429 | * |
430 | * 1) if it is, the ray is inside the sphere, so return t1, |
431 | * in order to always return an intersect point that is |
432 | * in front of the ray. |
433 | */ |
434 | if (t0 < 0) |
435 | { |
436 | if (t_out) |
437 | *t_out = t1; |
438 | |
439 | return GRAPHENE_RAY_INTERSECTION_KIND_LEAVE; |
440 | } |
441 | |
442 | /* 2) t0 is in front of the ray, so return t0 */ |
443 | if (t_out) |
444 | *t_out = t0; |
445 | |
446 | return GRAPHENE_RAY_INTERSECTION_KIND_ENTER; |
447 | } |
448 | |
449 | /** |
450 | * graphene_ray_intersects_sphere: |
451 | * @r: a #graphene_ray_t |
452 | * @s: a #graphene_sphere_t |
453 | * |
454 | * Checks if the given #graphene_ray_t @r intersects the |
455 | * given #graphene_sphere_t @s. |
456 | * |
457 | * See also: graphene_ray_intersect_sphere() |
458 | * |
459 | * Returns: `true` if the ray intersects the sphere |
460 | * |
461 | * Since: 1.10 |
462 | */ |
463 | bool |
464 | graphene_ray_intersects_sphere (const graphene_ray_t *r, |
465 | const graphene_sphere_t *s) |
466 | { |
467 | return graphene_ray_intersect_sphere (r, s, NULL) != GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
468 | } |
469 | |
470 | static inline float |
471 | nudge_off_axis (float v) |
472 | { |
473 | if (graphene_approx_val (a: v, b: 0.f)) |
474 | { |
475 | if (v < 0.f) |
476 | return -2 * FLT_EPSILON; |
477 | else |
478 | return 2 * FLT_EPSILON; |
479 | } |
480 | else |
481 | { |
482 | return v; |
483 | } |
484 | } |
485 | |
486 | /** |
487 | * graphene_ray_intersect_box: |
488 | * @r: a #graphene_ray_t |
489 | * @b: a #graphene_box_t |
490 | * @t_out: (out): the distance of the point on the ray that intersects the box |
491 | * |
492 | * Intersects the given #graphene_ray_t @r with the given |
493 | * #graphene_box_t @b. |
494 | * |
495 | * Returns: the type of intersection |
496 | * |
497 | * Since: 1.10 |
498 | */ |
499 | graphene_ray_intersection_kind_t |
500 | graphene_ray_intersect_box (const graphene_ray_t *r, |
501 | const graphene_box_t *b, |
502 | float *t_out) |
503 | { |
504 | graphene_vec3_t safe_direction; |
505 | graphene_vec3_t inv_dir; |
506 | float d[3]; |
507 | |
508 | graphene_vec3_to_float (v: &r->direction, dest: d); |
509 | graphene_vec3_init (v: &safe_direction, |
510 | x: nudge_off_axis (v: d[0]), |
511 | y: nudge_off_axis (v: d[1]), |
512 | z: nudge_off_axis (v: d[2])); |
513 | |
514 | /* FIXME: Needs a graphene_vec3_reciprocal() */ |
515 | inv_dir.value = graphene_simd4f_reciprocal (safe_direction.value); |
516 | |
517 | graphene_vec3_t inv_min; |
518 | graphene_vec3_subtract (a: &(b->min), b: &r->origin, res: &inv_min); |
519 | graphene_vec3_multiply (a: &inv_min, b: &inv_dir, res: &inv_min); |
520 | |
521 | graphene_vec3_t inv_max; |
522 | graphene_vec3_subtract (a: &(b->max), b: &r->origin, res: &inv_max); |
523 | graphene_vec3_multiply (a: &inv_max, b: &inv_dir, res: &inv_max); |
524 | |
525 | float tx_min, tx_max; |
526 | if (graphene_vec3_get_x (v: &inv_dir) >= 0.f) |
527 | { |
528 | tx_min = graphene_vec3_get_x (v: &inv_min); |
529 | tx_max = graphene_vec3_get_x (v: &inv_max); |
530 | } |
531 | else |
532 | { |
533 | tx_min = graphene_vec3_get_x (v: &inv_max); |
534 | tx_max = graphene_vec3_get_x (v: &inv_min); |
535 | } |
536 | |
537 | float ty_min, ty_max; |
538 | if (graphene_vec3_get_y (v: &inv_dir) >= 0.f) |
539 | { |
540 | ty_min = graphene_vec3_get_y (v: &inv_min); |
541 | ty_max = graphene_vec3_get_y (v: &inv_max); |
542 | } |
543 | else |
544 | { |
545 | ty_min = graphene_vec3_get_y (v: &inv_max); |
546 | ty_max = graphene_vec3_get_y (v: &inv_min); |
547 | } |
548 | |
549 | if (t_out != NULL) |
550 | *t_out = 0.f; |
551 | |
552 | if ((tx_min > ty_max) || (ty_min > tx_max)) |
553 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
554 | |
555 | /* These lines also handle the case where tx_min or tx_max is NaN |
556 | * (result of 0 * INFINITY): NaN != NaN |
557 | */ |
558 | #ifdef HAVE_ISNANF |
559 | if (ty_min > tx_min || isnanf (value: tx_min)) |
560 | tx_min = ty_min; |
561 | if (ty_max < tx_max || isnanf (value: tx_max)) |
562 | tx_max = ty_max; |
563 | #else |
564 | if (ty_min > tx_min || fpclassify (tx_min) == FP_NAN) |
565 | tx_min = ty_min; |
566 | if (ty_max > tx_max || fpclassify (tx_max) == FP_NAN) |
567 | tx_max = ty_max; |
568 | #endif |
569 | |
570 | float tz_min, tz_max; |
571 | if (graphene_vec3_get_z (v: &inv_dir) >= 0.f) |
572 | { |
573 | tz_min = graphene_vec3_get_z (v: &inv_min); |
574 | tz_max = graphene_vec3_get_z (v: &inv_max); |
575 | } |
576 | else |
577 | { |
578 | tz_min = graphene_vec3_get_z (v: &inv_max); |
579 | tz_max = graphene_vec3_get_z (v: &inv_min); |
580 | } |
581 | |
582 | if ((tx_min > tz_max) || (tz_min > tx_max)) |
583 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
584 | |
585 | #ifdef HAVE_ISNANF |
586 | if (tz_min > tx_min || isnanf (value: tx_min)) |
587 | tx_min = tz_min; |
588 | if (tz_max < tx_max || isnanf (value: tx_max)) |
589 | tx_max = tz_max; |
590 | #else |
591 | if (tz_min > tx_min || fpclassify (tx_min) == FP_NAN) |
592 | tx_min = tz_min; |
593 | if (tz_max < tx_max || fpclassify (tx_max) == FP_NAN) |
594 | tx_max = tz_max; |
595 | #endif |
596 | |
597 | /* return the point closest to the ray (positive side) */ |
598 | if (tx_max < 0) |
599 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
600 | |
601 | if (tx_min >= 0) |
602 | { |
603 | if (t_out) |
604 | *t_out = tx_min; |
605 | |
606 | return GRAPHENE_RAY_INTERSECTION_KIND_ENTER; |
607 | } |
608 | |
609 | if (t_out) |
610 | *t_out = tx_max; |
611 | |
612 | return GRAPHENE_RAY_INTERSECTION_KIND_LEAVE; |
613 | } |
614 | |
615 | /** |
616 | * graphene_ray_intersects_box: |
617 | * @r: a #graphene_ray_t |
618 | * @b: a #graphene_box_t |
619 | * |
620 | * Checks whether the given #graphene_ray_t @r intersects the |
621 | * given #graphene_box_t @b. |
622 | * |
623 | * See also: graphene_ray_intersect_box() |
624 | * |
625 | * Returns: `true` if the ray intersects the box |
626 | * |
627 | * Since: 1.10 |
628 | */ |
629 | bool |
630 | graphene_ray_intersects_box (const graphene_ray_t *r, |
631 | const graphene_box_t *b) |
632 | { |
633 | return graphene_ray_intersect_box (r, b, NULL) != GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
634 | } |
635 | |
636 | /** |
637 | * graphene_ray_intersect_triangle: |
638 | * @r: a #graphene_ray_t |
639 | * @t: a #graphene_triangle_t |
640 | * @t_out: (out): the distance of the point on the ray that intersects the triangle |
641 | * |
642 | * Intersects the given #graphene_ray_t @r with the given |
643 | * #graphene_triangle_t @t. |
644 | * |
645 | * Returns: the type of intersection |
646 | * |
647 | * Since: 1.10 |
648 | */ |
649 | graphene_ray_intersection_kind_t |
650 | graphene_ray_intersect_triangle (const graphene_ray_t *r, |
651 | const graphene_triangle_t *t, |
652 | float *t_out) |
653 | { |
654 | graphene_vec3_t diff, edge1, edge2, normal; |
655 | graphene_ray_intersection_kind_t kind; |
656 | |
657 | /* from http://www.geometrictools.com/GTEngine/Include/Mathematics/GteIntrRay3Triangle3.h */ |
658 | |
659 | /* Compute the offset origin, edges, and normal */ |
660 | graphene_vec3_subtract (a: &t->b, b: &t->a, res: &edge1); |
661 | graphene_vec3_subtract (a: &t->c, b: &t->a, res: &edge2); |
662 | graphene_vec3_cross (a: &edge1, b: &edge2, res: &normal); |
663 | |
664 | /* Solve: |
665 | * |
666 | * Q + t * D = b1 * E1 + b2 * E2 |
667 | * |
668 | * Where: |
669 | * * Q = kDiff |
670 | * * D = ray direction |
671 | * * E1 = kEdge1 |
672 | * * E2 = kEdge2 |
673 | * * N = Cross(E1,E2) |
674 | * |
675 | * by: |
676 | * |
677 | * |Dot(D,N)| * b1 = sign(Dot(D,N)) * Dot(D,Cross(Q,E2)) |
678 | * |Dot(D,N)| * b2 = sign(Dot(D,N)) * Dot(D,Cross(E1,Q)) |
679 | * |Dot(D,N)| * t = -sign(Dot(D,N)) * Dot(Q,N) |
680 | */ |
681 | float DdN = graphene_vec3_dot (a: &r->direction, b: &normal); |
682 | float sign; |
683 | |
684 | /* Ray and triangle are parallel, call it a "no intersection" |
685 | * even if the ray does intersect |
686 | */ |
687 | if (graphene_approx_val (a: DdN, b: 0.f)) |
688 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
689 | else if (DdN > 0) |
690 | { |
691 | kind = GRAPHENE_RAY_INTERSECTION_KIND_LEAVE; |
692 | sign = 1.f; |
693 | |
694 | } |
695 | else |
696 | { |
697 | kind = GRAPHENE_RAY_INTERSECTION_KIND_ENTER; |
698 | sign = -1.f; |
699 | DdN = -DdN; |
700 | } |
701 | |
702 | graphene_vec3_subtract (a: &r->origin, b: &t->a, res: &diff); |
703 | graphene_vec3_cross (a: &diff, b: &edge2, res: &edge2); |
704 | float DdQxE2 = sign * graphene_vec3_dot (a: &r->direction, b: &edge2); |
705 | |
706 | /* b1 < 0, no intersection */ |
707 | if (DdQxE2 < 0) |
708 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
709 | |
710 | graphene_vec3_cross (a: &edge1, b: &diff, res: &edge1); |
711 | |
712 | float DdE1xQ = sign * graphene_vec3_dot (a: &r->direction, b: &edge1); |
713 | |
714 | /* b2 < 0, no intersection */ |
715 | if (DdE1xQ < 0) |
716 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
717 | |
718 | /* b1 + b2 > 1, no intersection */ |
719 | if (DdQxE2 + DdE1xQ > DdN) |
720 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
721 | |
722 | /* Line intersects triangle, check if ray does */ |
723 | float QdN = -sign * graphene_vec3_dot (a: &diff, |
724 | b: &normal); |
725 | |
726 | /* t < 0, no intersection */ |
727 | if ( QdN < 0 ) |
728 | return GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
729 | |
730 | if (t_out != NULL) |
731 | *t_out = QdN / DdN; |
732 | |
733 | return kind; |
734 | } |
735 | |
736 | /** |
737 | * graphene_ray_intersects_triangle: |
738 | * @r: a #graphene_ray_t |
739 | * @t: a #graphene_triangle_t |
740 | * |
741 | * Checks whether the given #graphene_ray_t @r intersects the |
742 | * given #graphene_triangle_t @b. |
743 | * |
744 | * See also: graphene_ray_intersect_triangle() |
745 | * |
746 | * Returns: `true` if the ray intersects the triangle |
747 | * |
748 | * Since: 1.10 |
749 | */ |
750 | bool |
751 | graphene_ray_intersects_triangle (const graphene_ray_t *r, |
752 | const graphene_triangle_t *t) |
753 | { |
754 | return graphene_ray_intersect_triangle (r, t, NULL) != GRAPHENE_RAY_INTERSECTION_KIND_NONE; |
755 | } |
756 | |