1 | /* graphene-triangle.c: A triangle |
2 | * |
3 | * SPDX-License-Identifier: MIT |
4 | * |
5 | * Copyright 2014 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-triangle |
28 | * @Title: Triangle |
29 | * @Short_description: A triangle described by 3D points |
30 | * |
31 | * #graphene_triangle_t represents a triangle in 3D space. |
32 | * |
33 | */ |
34 | |
35 | #include "graphene-private.h" |
36 | |
37 | #include "graphene-triangle.h" |
38 | |
39 | #include "graphene-alloc-private.h" |
40 | #include "graphene-box.h" |
41 | #include "graphene-plane.h" |
42 | #include "graphene-point3d.h" |
43 | #include "graphene-vec2.h" |
44 | |
45 | #include <math.h> |
46 | |
47 | /** |
48 | * graphene_triangle_alloc: (constructor) |
49 | * |
50 | * Allocates a new #graphene_triangle_t. |
51 | * |
52 | * The contents of the returned structure are undefined. |
53 | * |
54 | * Returns: (transfer full): the newly allocated #graphene_triangle_t |
55 | * structure. Use graphene_triangle_free() to free the resources |
56 | * allocated by this function |
57 | * |
58 | * Since: 1.2 |
59 | */ |
60 | graphene_triangle_t * |
61 | graphene_triangle_alloc (void) |
62 | { |
63 | return graphene_aligned_alloc0 (size: sizeof (graphene_triangle_t), number: 1, alignment: 16); |
64 | } |
65 | |
66 | /** |
67 | * graphene_triangle_free: |
68 | * @t: a #graphene_triangle_t |
69 | * |
70 | * Frees the resources allocated by graphene_triangle_alloc(). |
71 | * |
72 | * Since: 1.2 |
73 | */ |
74 | void |
75 | graphene_triangle_free (graphene_triangle_t *t) |
76 | { |
77 | graphene_aligned_free (mem: t); |
78 | } |
79 | |
80 | /** |
81 | * graphene_triangle_init_from_point3d: |
82 | * @t: the #graphene_triangle_t to initialize |
83 | * @a: (nullable): a #graphene_point3d_t |
84 | * @b: (nullable): a #graphene_point3d_t |
85 | * @c: (nullable): a #graphene_point3d_t |
86 | * |
87 | * Initializes a #graphene_triangle_t using the three given 3D points. |
88 | * |
89 | * Returns: (transfer none): the initialized #graphene_triangle_t |
90 | * |
91 | * Since: 1.2 |
92 | */ |
93 | graphene_triangle_t * |
94 | graphene_triangle_init_from_point3d (graphene_triangle_t *t, |
95 | const graphene_point3d_t *a, |
96 | const graphene_point3d_t *b, |
97 | const graphene_point3d_t *c) |
98 | { |
99 | if (a != NULL) |
100 | graphene_point3d_to_vec3 (p: a, v: &t->a); |
101 | else |
102 | graphene_vec3_init_from_vec3 (v: &t->a, src: graphene_vec3_zero ()); |
103 | |
104 | if (b != NULL) |
105 | graphene_point3d_to_vec3 (p: b, v: &t->b); |
106 | else |
107 | graphene_vec3_init_from_vec3 (v: &t->b, src: graphene_vec3_zero ()); |
108 | |
109 | if (c != NULL) |
110 | graphene_point3d_to_vec3 (p: c, v: &t->c); |
111 | else |
112 | graphene_vec3_init_from_vec3 (v: &t->c, src: graphene_vec3_zero ()); |
113 | |
114 | return t; |
115 | } |
116 | |
117 | /** |
118 | * graphene_triangle_init_from_vec3: |
119 | * @t: the #graphene_triangle_t to initialize |
120 | * @a: (nullable): a #graphene_vec3_t |
121 | * @b: (nullable): a #graphene_vec3_t |
122 | * @c: (nullable): a #graphene_vec3_t |
123 | * |
124 | * Initializes a #graphene_triangle_t using the three given vectors. |
125 | * |
126 | * Returns: (transfer none): the initialized #graphene_triangle_t |
127 | * |
128 | * Since: 1.2 |
129 | */ |
130 | graphene_triangle_t * |
131 | graphene_triangle_init_from_vec3 (graphene_triangle_t *t, |
132 | const graphene_vec3_t *a, |
133 | const graphene_vec3_t *b, |
134 | const graphene_vec3_t *c) |
135 | { |
136 | if (a != NULL) |
137 | t->a = *a; |
138 | else |
139 | graphene_vec3_init_from_vec3 (v: &t->a, src: graphene_vec3_zero ()); |
140 | |
141 | if (b != NULL) |
142 | t->b = *b; |
143 | else |
144 | graphene_vec3_init_from_vec3 (v: &t->b, src: graphene_vec3_zero ()); |
145 | |
146 | if (c != NULL) |
147 | t->c = *c; |
148 | else |
149 | graphene_vec3_init_from_vec3 (v: &t->c, src: graphene_vec3_zero ()); |
150 | |
151 | return t; |
152 | } |
153 | |
154 | /** |
155 | * graphene_triangle_init_from_float: |
156 | * @t: the #graphene_triangle_t to initialize |
157 | * @a: (not nullable) (array fixed-size=3): an array of 3 floating point values |
158 | * @b: (not nullable) (array fixed-size=3): an array of 3 floating point values |
159 | * @c: (not nullable) (array fixed-size=3): an array of 3 floating point values |
160 | * |
161 | * Initializes a #graphene_triangle_t using the three given arrays |
162 | * of floating point values, each representing the coordinates of |
163 | * a point in 3D space. |
164 | * |
165 | * Returns: (transfer none): the initialized #graphene_triangle_t |
166 | * |
167 | * Since: 1.10 |
168 | */ |
169 | graphene_triangle_t * |
170 | graphene_triangle_init_from_float (graphene_triangle_t *t, |
171 | const float *a, |
172 | const float *b, |
173 | const float *c) |
174 | { |
175 | graphene_vec3_t va, vb, vc; |
176 | |
177 | return graphene_triangle_init_from_vec3 (t, |
178 | a: graphene_vec3_init_from_float (v: &va, src: a), |
179 | b: graphene_vec3_init_from_float (v: &vb, src: b), |
180 | c: graphene_vec3_init_from_float (v: &vc, src: c)); |
181 | } |
182 | |
183 | /** |
184 | * graphene_triangle_get_points: |
185 | * @t: a #graphene_triangle_t |
186 | * @a: (out caller-allocates) (optional): return location for the coordinates |
187 | * of the first vertex |
188 | * @b: (out caller-allocates) (optional): return location for the coordinates |
189 | * of the second vertex |
190 | * @c: (out caller-allocates) (optional): return location for the coordinates |
191 | * of the third vertex |
192 | * |
193 | * Retrieves the three vertices of the given #graphene_triangle_t and returns |
194 | * their coordinates as #graphene_point3d_t. |
195 | * |
196 | * Since: 1.2 |
197 | */ |
198 | void |
199 | graphene_triangle_get_points (const graphene_triangle_t *t, |
200 | graphene_point3d_t *a, |
201 | graphene_point3d_t *b, |
202 | graphene_point3d_t *c) |
203 | { |
204 | if (a != NULL) |
205 | graphene_point3d_init_from_vec3 (p: a, v: &t->a); |
206 | if (b != NULL) |
207 | graphene_point3d_init_from_vec3 (p: b, v: &t->b); |
208 | if (c != NULL) |
209 | graphene_point3d_init_from_vec3 (p: c, v: &t->c); |
210 | } |
211 | |
212 | /** |
213 | * graphene_triangle_get_vertices: |
214 | * @t: a #graphene_triangle_t |
215 | * @a: (out caller-allocates) (optional): return location for the first vertex |
216 | * @b: (out caller-allocates) (optional): return location for the second vertex |
217 | * @c: (out caller-allocates) (optional): return location for the third vertex |
218 | * |
219 | * Retrieves the three vertices of the given #graphene_triangle_t. |
220 | * |
221 | * Since: 1.2 |
222 | */ |
223 | void |
224 | graphene_triangle_get_vertices (const graphene_triangle_t *t, |
225 | graphene_vec3_t *a, |
226 | graphene_vec3_t *b, |
227 | graphene_vec3_t *c) |
228 | { |
229 | if (a != NULL) |
230 | *a = t->a; |
231 | if (b != NULL) |
232 | *b = t->b; |
233 | if (c != NULL) |
234 | *c = t->c; |
235 | } |
236 | |
237 | /** |
238 | * graphene_triangle_get_area: |
239 | * @t: a #graphene_triangle_t |
240 | * |
241 | * Computes the area of the given #graphene_triangle_t. |
242 | * |
243 | * Returns: the area of the triangle |
244 | * |
245 | * Since: 1.2 |
246 | */ |
247 | float |
248 | graphene_triangle_get_area (const graphene_triangle_t *t) |
249 | { |
250 | graphene_vec3_t v1, v2, tmp; |
251 | |
252 | graphene_vec3_subtract (a: &t->c, b: &t->b, res: &v1); |
253 | graphene_vec3_subtract (a: &t->a, b: &t->b, res: &v2); |
254 | |
255 | graphene_vec3_cross (a: &v1, b: &v2, res: &tmp); |
256 | |
257 | return graphene_vec3_length (v: &tmp) * .5f; |
258 | } |
259 | |
260 | /** |
261 | * graphene_triangle_get_midpoint: |
262 | * @t: a #graphene_triangle_t |
263 | * @res: (out caller-allocates): return location for the coordinates of |
264 | * the midpoint |
265 | * |
266 | * Computes the coordinates of the midpoint of the given #graphene_triangle_t. |
267 | * |
268 | * The midpoint G is the [centroid](https://en.wikipedia.org/wiki/Centroid#Triangle_centroid) |
269 | * of the triangle, i.e. the intersection of its medians. |
270 | * |
271 | * Since: 1.2 |
272 | */ |
273 | void |
274 | graphene_triangle_get_midpoint (const graphene_triangle_t *t, |
275 | graphene_point3d_t *res) |
276 | { |
277 | graphene_vec3_t tmp; |
278 | |
279 | graphene_vec3_add (a: &t->a, b: &t->b, res: &tmp); |
280 | graphene_vec3_add (a: &tmp, b: &t->c, res: &tmp); |
281 | graphene_vec3_scale (v: &tmp, factor: (1.f / 3.f), res: &tmp); |
282 | |
283 | graphene_point3d_init_from_vec3 (p: res, v: &tmp); |
284 | } |
285 | |
286 | /** |
287 | * graphene_triangle_get_normal: |
288 | * @t: a #graphene_triangle_t |
289 | * @res: (out caller-allocates): return location for the normal vector |
290 | * |
291 | * Computes the normal vector of the given #graphene_triangle_t. |
292 | * |
293 | * Since: 1.2 |
294 | */ |
295 | void |
296 | graphene_triangle_get_normal (const graphene_triangle_t *t, |
297 | graphene_vec3_t *res) |
298 | { |
299 | graphene_vec3_t v1, v2, tmp; |
300 | float length_sq; |
301 | |
302 | graphene_vec3_subtract (a: &t->c, b: &t->b, res: &v1); |
303 | graphene_vec3_subtract (a: &t->a, b: &t->b, res: &v2); |
304 | |
305 | graphene_vec3_cross (a: &v1, b: &v2, res: &tmp); |
306 | |
307 | length_sq = graphene_vec3_dot (a: &tmp, b: &tmp); |
308 | if (length_sq > 0) |
309 | graphene_vec3_scale (v: &tmp, factor: 1.f / sqrtf (x: length_sq), res); |
310 | else |
311 | graphene_vec3_init_from_vec3 (v: res, src: graphene_vec3_zero ()); |
312 | } |
313 | |
314 | /** |
315 | * graphene_triangle_get_plane: |
316 | * @t: a #graphene_triangle_t |
317 | * @res: (out caller-allocates): return location for the plane |
318 | * |
319 | * Computes the plane based on the vertices of the given #graphene_triangle_t. |
320 | * |
321 | * Since: 1.2 |
322 | */ |
323 | void |
324 | graphene_triangle_get_plane (const graphene_triangle_t *t, |
325 | graphene_plane_t *res) |
326 | { |
327 | graphene_point3d_t a, b, c; |
328 | |
329 | graphene_point3d_init_from_vec3 (p: &a, v: &t->a); |
330 | graphene_point3d_init_from_vec3 (p: &b, v: &t->b); |
331 | graphene_point3d_init_from_vec3 (p: &c, v: &t->c); |
332 | |
333 | graphene_plane_init_from_points (p: res, a: &a, b: &b, c: &c); |
334 | } |
335 | |
336 | /** |
337 | * graphene_triangle_get_bounding_box: |
338 | * @t: a #graphene_triangle_t |
339 | * @res: (out caller-allocates): return location for the box |
340 | * |
341 | * Computes the bounding box of the given #graphene_triangle_t. |
342 | * |
343 | * Since: 1.2 |
344 | */ |
345 | void |
346 | graphene_triangle_get_bounding_box (const graphene_triangle_t *t, |
347 | graphene_box_t *res) |
348 | { |
349 | graphene_box_init_from_box (box: res, src: graphene_box_empty ()); |
350 | graphene_box_expand_vec3 (box: res, vec: &t->a, res); |
351 | graphene_box_expand_vec3 (box: res, vec: &t->b, res); |
352 | graphene_box_expand_vec3 (box: res, vec: &t->c, res); |
353 | } |
354 | |
355 | /** |
356 | * graphene_triangle_get_uv: |
357 | * @t: a #graphene_triangle_t |
358 | * @p: (nullable): a #graphene_point3d_t |
359 | * @uv_a: the UV coordinates of the first point |
360 | * @uv_b: the UV coordinates of the second point |
361 | * @uv_c: the UV coordinates of the third point |
362 | * @res: (out caller-allocates): a vector containing the UV coordinates |
363 | * of the given point @p |
364 | * |
365 | * Computes the UV coordinates of the given point @p. |
366 | * |
367 | * The point @p must lie on the same plane as the triangle @t; if the point |
368 | * is not coplanar, the result of this function is undefined. If @p is %NULL, |
369 | * the point will be set in (0, 0, 0). |
370 | * |
371 | * The UV coordinates will be placed in the @res vector: |
372 | * |
373 | * - `res.x = u` |
374 | * - `res.y = v` |
375 | * |
376 | * See also: graphene_triangle_get_barycoords() |
377 | * |
378 | * Returns: `true` if the coordinates are valid |
379 | * |
380 | * Since: 1.10 |
381 | */ |
382 | bool |
383 | graphene_triangle_get_uv (const graphene_triangle_t *t, |
384 | const graphene_point3d_t *p, |
385 | const graphene_vec2_t *uv_a, |
386 | const graphene_vec2_t *uv_b, |
387 | const graphene_vec2_t *uv_c, |
388 | graphene_vec2_t *res) |
389 | { |
390 | graphene_vec2_t bc; |
391 | |
392 | graphene_vec2_init (v: res, x: 0.f, y: 0.f); |
393 | |
394 | if (!graphene_triangle_get_barycoords (t, p, res: &bc)) |
395 | return false; |
396 | |
397 | float u = graphene_vec2_get_x (v: &bc); |
398 | float v = graphene_vec2_get_y (v: &bc); |
399 | |
400 | /* We have the barycentric coordinates of three points, |
401 | * but barycentric coordinates must always sum to 1, so |
402 | * we can easily derive the third factor |
403 | */ |
404 | graphene_point3d_t barycoord = |
405 | GRAPHENE_POINT3D_INIT (1.f - u - v, v, u); |
406 | |
407 | graphene_vec2_t tmp; |
408 | |
409 | graphene_vec2_scale (v: uv_a, factor: barycoord.x, res: &tmp); |
410 | graphene_vec2_add (a: res, b: &tmp, res); |
411 | |
412 | graphene_vec2_scale (v: uv_b, factor: barycoord.y, res: &tmp); |
413 | graphene_vec2_add (a: res, b: &tmp, res); |
414 | |
415 | graphene_vec2_scale (v: uv_c, factor: barycoord.z, res: &tmp); |
416 | graphene_vec2_add (a: res, b: &tmp, res); |
417 | |
418 | return true; |
419 | } |
420 | |
421 | /** |
422 | * graphene_triangle_get_barycoords: |
423 | * @t: a #graphene_triangle_t |
424 | * @p: (nullable): a #graphene_point3d_t |
425 | * @res: (out caller-allocates): return location for the vector |
426 | * with the barycentric coordinates |
427 | * |
428 | * Computes the [barycentric coordinates](http://en.wikipedia.org/wiki/Barycentric_coordinate_system) |
429 | * of the given point @p. |
430 | * |
431 | * The point @p must lie on the same plane as the triangle @t; if the |
432 | * point is not coplanar, the result of this function is undefined. |
433 | * |
434 | * If we place the origin in the coordinates of the triangle's A point, |
435 | * the barycentric coordinates are `u`, which is on the AC vector; and `v` |
436 | * which is on the AB vector: |
437 | * |
438 | * ![](triangle-barycentric.png) |
439 | * |
440 | * The returned #graphene_vec2_t contains the following values, in order: |
441 | * |
442 | * - `res.x = u` |
443 | * - `res.y = v` |
444 | * |
445 | * Returns: `true` if the barycentric coordinates are valid |
446 | * |
447 | * Since: 1.2 |
448 | */ |
449 | bool |
450 | graphene_triangle_get_barycoords (const graphene_triangle_t *t, |
451 | const graphene_point3d_t *p, |
452 | graphene_vec2_t *res) |
453 | { |
454 | graphene_vec3_t point; |
455 | |
456 | if (p == NULL) |
457 | graphene_vec3_init (v: &point, x: 0.f, y: 0.f, z: 0.f); |
458 | else |
459 | graphene_point3d_to_vec3 (p, v: &point); |
460 | |
461 | graphene_vec3_t v0, v1, v2; |
462 | float dot00, dot01, dot02; |
463 | float dot11, dot12; |
464 | float denom, inv_denom; |
465 | |
466 | graphene_vec3_subtract (a: &t->c, b: &t->a, res: &v0); |
467 | graphene_vec3_subtract (a: &t->b, b: &t->a, res: &v1); |
468 | graphene_vec3_subtract (a: &point, b: &t->a, res: &v2); |
469 | |
470 | dot00 = graphene_vec3_dot (a: &v0, b: &v0); |
471 | dot01 = graphene_vec3_dot (a: &v0, b: &v1); |
472 | dot02 = graphene_vec3_dot (a: &v0, b: &v2); |
473 | dot11 = graphene_vec3_dot (a: &v1, b: &v1); |
474 | dot12 = graphene_vec3_dot (a: &v1, b: &v2); |
475 | |
476 | denom = dot00 * dot11 - dot01 * dot01; |
477 | if (fabsf (x: denom) <= FLT_EPSILON) |
478 | return false; |
479 | |
480 | inv_denom = 1.f / denom; |
481 | |
482 | float u = (dot11 * dot02 - dot01 * dot12) * inv_denom; |
483 | float v = (dot00 * dot12 - dot01 * dot02) * inv_denom; |
484 | |
485 | graphene_vec2_init (v: res, x: u, y: v); |
486 | |
487 | return true; |
488 | } |
489 | |
490 | /** |
491 | * graphene_triangle_contains_point: |
492 | * @t: a #graphene_triangle_t |
493 | * @p: a #graphene_point3d_t |
494 | * |
495 | * Checks whether the given triangle @t contains the point @p. |
496 | * |
497 | * Returns: `true` if the point is inside the triangle |
498 | * |
499 | * Since: 1.2 |
500 | */ |
501 | bool |
502 | graphene_triangle_contains_point (const graphene_triangle_t *t, |
503 | const graphene_point3d_t *p) |
504 | { |
505 | graphene_vec2_t res; |
506 | |
507 | /* we use the barycoordinates from the given point to check |
508 | * if the point is inside the triangle. |
509 | * |
510 | * see: http://www.blackpawn.com/texts/pointinpoly/default.html |
511 | */ |
512 | if (!graphene_triangle_get_barycoords (t, p, res: &res)) |
513 | return false; |
514 | |
515 | float u = graphene_vec2_get_x (v: &res); |
516 | float v = graphene_vec2_get_y (v: &res); |
517 | |
518 | return (u >= 0.f) && (v >= 0.f) && (u + v < 1.f); |
519 | } |
520 | |
521 | static bool |
522 | triangle_equal (const void *p1, |
523 | const void *p2) |
524 | { |
525 | const graphene_triangle_t *a = p1; |
526 | const graphene_triangle_t *b = p2; |
527 | |
528 | return graphene_vec3_equal (v1: &a->a, v2: &b->a) && |
529 | graphene_vec3_equal (v1: &a->b, v2: &b->b) && |
530 | graphene_vec3_equal (v1: &a->c, v2: &b->c); |
531 | } |
532 | |
533 | /** |
534 | * graphene_triangle_equal: |
535 | * @a: a #graphene_triangle_t |
536 | * @b: a #graphene_triangle_t |
537 | * |
538 | * Checks whether the two given #graphene_triangle_t are equal. |
539 | * |
540 | * Returns: `true` if the triangles are equal |
541 | * |
542 | * Since: 1.2 |
543 | */ |
544 | bool |
545 | graphene_triangle_equal (const graphene_triangle_t *a, |
546 | const graphene_triangle_t *b) |
547 | { |
548 | return graphene_pointer_equal (p1: a, p2: b, func: triangle_equal); |
549 | } |
550 | |