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 */
60graphene_triangle_t *
61graphene_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 */
74void
75graphene_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 */
93graphene_triangle_t *
94graphene_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 */
130graphene_triangle_t *
131graphene_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 */
169graphene_triangle_t *
170graphene_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 */
198void
199graphene_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 */
223void
224graphene_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 */
247float
248graphene_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 */
273void
274graphene_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 */
295void
296graphene_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 */
323void
324graphene_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 */
345void
346graphene_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 */
382bool
383graphene_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 */
449bool
450graphene_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 */
501bool
502graphene_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
521static bool
522triangle_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 */
544bool
545graphene_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

source code of gtk/subprojects/graphene/src/graphene-triangle.c