parry2d/shape/triangle.rs
1//! Definition of the triangle shape.
2
3use crate::math::{Isometry, Point, Real, Vector};
4use crate::shape::SupportMap;
5use crate::shape::{PolygonalFeature, Segment};
6use crate::utils;
7
8use core::mem;
9use na::{self, ComplexField, Unit};
10use num::Zero;
11
12#[cfg(feature = "dim3")]
13use {crate::shape::FeatureId, core::f64};
14
15#[cfg(feature = "dim2")]
16use crate::shape::PackedFeatureId;
17
18#[cfg(feature = "rkyv")]
19use rkyv::{bytecheck, CheckBytes};
20
21/// A triangle shape defined by three vertices.
22///
23/// A triangle is one of the most fundamental shapes in computational geometry.
24/// It's the simplest 2D polygon and the building block for triangle meshes.
25///
26/// # Structure
27///
28/// - **a, b, c**: The three vertices of the triangle
29/// - **Edges**: AB (from a to b), BC (from b to c), CA (from c to a)
30/// - **Orientation**: Counter-clockwise (CCW) is the standard convention
31///
32/// # Properties
33///
34/// - **Convex**: Always convex
35/// - **2D/3D**: Can be used in both dimensions
36/// - **In 2D**: A filled triangular region with area
37/// - **In 3D**: A flat surface embedded in 3D space (zero volume)
38///
39/// # Orientation Convention
40///
41/// Triangles are typically defined with counter-clockwise vertex order:
42/// - Looking at the triangle from the "front", vertices go a → b → c in CCW order
43/// - The normal vector (3D) points toward the observer
44/// - Right-hand rule: Curl fingers from a→b→c, thumb points along normal
45///
46/// # Use Cases
47///
48/// - **Mesh building block**: Fundamental unit of triangle meshes
49/// - **Simple collision shapes**: Fast collision detection
50/// - **Terrain representation**: Ground planes and surfaces
51/// - **Testing and debugging**: Simple shape for verification
52///
53/// # Example
54///
55/// ```rust
56/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
57/// use parry3d::shape::Triangle;
58/// use nalgebra::Point3;
59///
60/// // Create a right triangle in the XY plane
61/// let triangle = Triangle::new(
62/// Point3::origin(), // a: origin
63/// Point3::new(3.0, 0.0, 0.0), // b: along +X
64/// Point3::new(0.0, 4.0, 0.0) // c: along +Y
65/// );
66///
67/// // Area of 3-4-5 right triangle is 6.0
68/// assert_eq!(triangle.area(), 6.0);
69///
70/// // Check if a point is inside
71/// let inside = Point3::new(1.0, 1.0, 0.0);
72/// assert!(triangle.contains_point(&inside));
73/// # }
74/// ```
75#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
76#[cfg_attr(feature = "bytemuck", derive(bytemuck::Pod, bytemuck::Zeroable))]
77#[cfg_attr(feature = "encase", derive(encase::ShaderType))]
78#[cfg_attr(
79 feature = "rkyv",
80 derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize, CheckBytes),
81 archive(as = "Self")
82)]
83#[derive(PartialEq, Debug, Copy, Clone, Default)]
84#[repr(C)]
85pub struct Triangle {
86 /// The first vertex of the triangle.
87 pub a: Point<Real>,
88 /// The second vertex of the triangle.
89 pub b: Point<Real>,
90 /// The third vertex of the triangle.
91 pub c: Point<Real>,
92}
93
94/// Description of the location of a point on a triangle.
95#[derive(Copy, Clone, Debug)]
96pub enum TrianglePointLocation {
97 /// The point lies on a vertex.
98 OnVertex(u32),
99 /// The point lies on an edge.
100 ///
101 /// The 0-st edge is the segment AB.
102 /// The 1-st edge is the segment BC.
103 /// The 2-nd edge is the segment AC.
104 // XXX: it appears the conversion of edge indexing here does not match the
105 // convention of edge indexing for the `fn edge` method (from the ConvexPolyhedron impl).
106 OnEdge(u32, [Real; 2]),
107 /// The point lies on the triangle interior.
108 ///
109 /// The integer indicates on which side of the face the point is. 0 indicates the point
110 /// is on the half-space toward the CW normal of the triangle. 1 indicates the point is on the other
111 /// half-space. This is always set to 0 in 2D.
112 OnFace(u32, [Real; 3]),
113 /// The point lies on the triangle interior (for "solid" point queries).
114 OnSolid,
115}
116
117impl TrianglePointLocation {
118 /// The barycentric coordinates corresponding to this point location.
119 ///
120 /// Returns `None` if the location is `TrianglePointLocation::OnSolid`.
121 pub fn barycentric_coordinates(&self) -> Option<[Real; 3]> {
122 let mut bcoords = [0.0; 3];
123
124 match self {
125 TrianglePointLocation::OnVertex(i) => bcoords[*i as usize] = 1.0,
126 TrianglePointLocation::OnEdge(i, uv) => {
127 let idx = match i {
128 0 => (0, 1),
129 1 => (1, 2),
130 2 => (0, 2),
131 _ => unreachable!(),
132 };
133
134 bcoords[idx.0] = uv[0];
135 bcoords[idx.1] = uv[1];
136 }
137 TrianglePointLocation::OnFace(_, uvw) => {
138 bcoords[0] = uvw[0];
139 bcoords[1] = uvw[1];
140 bcoords[2] = uvw[2];
141 }
142 TrianglePointLocation::OnSolid => {
143 return None;
144 }
145 }
146
147 Some(bcoords)
148 }
149
150 /// Returns `true` if the point is located on the relative interior of the triangle.
151 pub fn is_on_face(&self) -> bool {
152 matches!(*self, TrianglePointLocation::OnFace(..))
153 }
154}
155
156/// Orientation of a triangle.
157#[derive(Copy, Clone, Debug, PartialEq, Eq)]
158pub enum TriangleOrientation {
159 /// Orientation with a clockwise orientation, i.e., with a positive signed area.
160 Clockwise,
161 /// Orientation with a clockwise orientation, i.e., with a negative signed area.
162 CounterClockwise,
163 /// Degenerate triangle.
164 Degenerate,
165}
166
167impl From<[Point<Real>; 3]> for Triangle {
168 fn from(arr: [Point<Real>; 3]) -> Self {
169 *Self::from_array(&arr)
170 }
171}
172
173impl Triangle {
174 /// Creates a triangle from three vertices.
175 ///
176 /// # Arguments
177 ///
178 /// * `a` - The first vertex
179 /// * `b` - The second vertex
180 /// * `c` - The third vertex
181 ///
182 /// # Convention
183 ///
184 /// For proper normal calculation and consistent collision detection, vertices
185 /// should be ordered counter-clockwise when viewed from the "front" side.
186 ///
187 /// # Example
188 ///
189 /// ```
190 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
191 /// use parry3d::shape::Triangle;
192 /// use nalgebra::Point3;
193 ///
194 /// // Create a triangle in the XY plane
195 /// let tri = Triangle::new(
196 /// Point3::origin(),
197 /// Point3::new(1.0, 0.0, 0.0),
198 /// Point3::new(0.0, 1.0, 0.0)
199 /// );
200 ///
201 /// assert_eq!(tri.area(), 0.5);
202 /// # }
203 /// ```
204 #[inline]
205 pub fn new(a: Point<Real>, b: Point<Real>, c: Point<Real>) -> Triangle {
206 Triangle { a, b, c }
207 }
208
209 /// Creates the reference to a triangle from the reference to an array of three points.
210 pub fn from_array(arr: &[Point<Real>; 3]) -> &Triangle {
211 unsafe { mem::transmute(arr) }
212 }
213
214 /// Reference to an array containing the three vertices of this triangle.
215 #[inline]
216 pub fn vertices(&self) -> &[Point<Real>; 3] {
217 unsafe { mem::transmute(self) }
218 }
219
220 /// The normal of this triangle assuming it is oriented ccw.
221 ///
222 /// The normal points such that it is collinear to `AB × AC` (where `×` denotes the cross
223 /// product).
224 #[inline]
225 #[cfg(feature = "dim3")]
226 pub fn normal(&self) -> Option<Unit<Vector<Real>>> {
227 Unit::try_new(self.scaled_normal(), crate::math::DEFAULT_EPSILON)
228 }
229
230 /// The three edges of this triangle: [AB, BC, CA].
231 #[inline]
232 pub fn edges(&self) -> [Segment; 3] {
233 [
234 Segment::new(self.a, self.b),
235 Segment::new(self.b, self.c),
236 Segment::new(self.c, self.a),
237 ]
238 }
239
240 /// Computes a scaled version of this triangle.
241 pub fn scaled(self, scale: &Vector<Real>) -> Self {
242 Self::new(
243 na::Scale::from(*scale) * self.a,
244 na::Scale::from(*scale) * self.b,
245 na::Scale::from(*scale) * self.c,
246 )
247 }
248
249 /// Returns a new triangle with vertices transformed by `m`.
250 #[inline]
251 pub fn transformed(&self, m: &Isometry<Real>) -> Self {
252 Triangle::new(m * self.a, m * self.b, m * self.c)
253 }
254
255 /// The three edges scaled directions of this triangle: [B - A, C - B, A - C].
256 #[inline]
257 pub fn edges_scaled_directions(&self) -> [Vector<Real>; 3] {
258 [self.b - self.a, self.c - self.b, self.a - self.c]
259 }
260
261 /// Return the edge segment of this cuboid with a normal cone containing
262 /// a direction that that maximizes the dot product with `local_dir`.
263 pub fn local_support_edge_segment(&self, dir: Vector<Real>) -> Segment {
264 let dots = na::Vector3::new(
265 dir.dot(&self.a.coords),
266 dir.dot(&self.b.coords),
267 dir.dot(&self.c.coords),
268 );
269
270 match dots.imin() {
271 0 => Segment::new(self.b, self.c),
272 1 => Segment::new(self.c, self.a),
273 _ => Segment::new(self.a, self.b),
274 }
275 }
276
277 /// Return the face of this triangle with a normal that maximizes
278 /// the dot product with `dir`.
279 #[cfg(feature = "dim3")]
280 pub fn support_face(&self, _dir: Vector<Real>) -> PolygonalFeature {
281 PolygonalFeature::from(*self)
282 }
283
284 /// Return the face of this triangle with a normal that maximizes
285 /// the dot product with `dir`.
286 #[cfg(feature = "dim2")]
287 pub fn support_face(&self, dir: Vector<Real>) -> PolygonalFeature {
288 let mut best = 0;
289 let mut best_dot = -Real::MAX;
290
291 for (i, tangent) in self.edges_scaled_directions().iter().enumerate() {
292 let normal = Vector::new(tangent.y, -tangent.x);
293 if let Some(normal) = Unit::try_new(normal, 0.0) {
294 let dot = normal.dot(&dir);
295 if normal.dot(&dir) > best_dot {
296 best = i;
297 best_dot = dot;
298 }
299 }
300 }
301
302 let pts = self.vertices();
303 let i1 = best;
304 let i2 = (best + 1) % 3;
305
306 PolygonalFeature {
307 vertices: [pts[i1], pts[i2]],
308 vids: PackedFeatureId::vertices([i1 as u32, i2 as u32]),
309 fid: PackedFeatureId::face(i1 as u32),
310 num_vertices: 2,
311 }
312 }
313
314 /// A vector normal of this triangle.
315 ///
316 /// The vector points such that it is collinear to `AB × AC` (where `×` denotes the cross
317 /// product).
318 ///
319 /// Note that on thin triangles the calculated normals can suffer from numerical issues.
320 /// For a more robust (but more computationally expensive) normal calculation, see
321 /// [`Triangle::robust_scaled_normal`].
322 #[inline]
323 #[cfg(feature = "dim3")]
324 pub fn scaled_normal(&self) -> Vector<Real> {
325 let ab = self.b - self.a;
326 let ac = self.c - self.a;
327 ab.cross(&ac)
328 }
329
330 /// Find a triangle normal more robustly than with [`Triangle::scaled_normal`].
331 ///
332 /// Thin triangles can cause numerical issues when computing its normal. This method accounts
333 /// for these numerical issues more robustly than [`Triangle::scaled_normal`], but is more
334 /// computationally expensive.
335 #[inline]
336 #[cfg(feature = "dim3")]
337 pub fn robust_scaled_normal(&self) -> na::Vector3<Real> {
338 let pts = self.vertices();
339 let best_vertex = self.angle_closest_to_90();
340 let d1 = pts[(best_vertex + 2) % 3] - pts[(best_vertex + 1) % 3];
341 let d2 = pts[best_vertex] - pts[(best_vertex + 1) % 3];
342
343 d1.cross(&d2)
344 }
345
346 /// Similar to [`Triangle::robust_scaled_normal`], but returns the unit length normal.
347 #[inline]
348 #[cfg(feature = "dim3")]
349 pub fn robust_normal(&self) -> na::Vector3<Real> {
350 self.robust_scaled_normal().normalize()
351 }
352
353 /// Computes the extents of this triangle on the given direction.
354 ///
355 /// This computes the min and max values of the dot products between each
356 /// vertex of this triangle and `dir`.
357 #[inline]
358 pub fn extents_on_dir(&self, dir: &Unit<Vector<Real>>) -> (Real, Real) {
359 let a = self.a.coords.dot(dir);
360 let b = self.b.coords.dot(dir);
361 let c = self.c.coords.dot(dir);
362
363 if a > b {
364 if b > c {
365 (c, a)
366 } else if a > c {
367 (b, a)
368 } else {
369 (b, c)
370 }
371 } else {
372 // b >= a
373 if a > c {
374 (c, b)
375 } else if b > c {
376 (a, b)
377 } else {
378 (a, c)
379 }
380 }
381 }
382 //
383 // #[cfg(feature = "dim3")]
384 // fn support_feature_id_toward(&self, local_dir: &Unit<Vector<Real>>, eps: Real) -> FeatureId {
385 // if let Some(normal) = self.normal() {
386 // let (seps, ceps) = ComplexField::sin_cos(eps);
387 //
388 // let normal_dot = local_dir.dot(&*normal);
389 // if normal_dot >= ceps {
390 // FeatureId::Face(0)
391 // } else if normal_dot <= -ceps {
392 // FeatureId::Face(1)
393 // } else {
394 // let edges = self.edges();
395 // let mut dots = [0.0; 3];
396 //
397 // let dir1 = edges[0].direction();
398 // if let Some(dir1) = dir1 {
399 // dots[0] = dir1.dot(local_dir);
400 //
401 // if dots[0].abs() < seps {
402 // return FeatureId::Edge(0);
403 // }
404 // }
405 //
406 // let dir2 = edges[1].direction();
407 // if let Some(dir2) = dir2 {
408 // dots[1] = dir2.dot(local_dir);
409 //
410 // if dots[1].abs() < seps {
411 // return FeatureId::Edge(1);
412 // }
413 // }
414 //
415 // let dir3 = edges[2].direction();
416 // if let Some(dir3) = dir3 {
417 // dots[2] = dir3.dot(local_dir);
418 //
419 // if dots[2].abs() < seps {
420 // return FeatureId::Edge(2);
421 // }
422 // }
423 //
424 // if dots[0] > 0.0 && dots[1] < 0.0 {
425 // FeatureId::Vertex(1)
426 // } else if dots[1] > 0.0 && dots[2] < 0.0 {
427 // FeatureId::Vertex(2)
428 // } else {
429 // FeatureId::Vertex(0)
430 // }
431 // }
432 // } else {
433 // FeatureId::Vertex(0)
434 // }
435 // }
436
437 /// The area of this triangle.
438 #[inline]
439 pub fn area(&self) -> Real {
440 // Kahan's formula.
441 let a = na::distance(&self.a, &self.b);
442 let b = na::distance(&self.b, &self.c);
443 let c = na::distance(&self.c, &self.a);
444
445 let (c, b, a) = utils::sort3(&a, &b, &c);
446 let a = *a;
447 let b = *b;
448 let c = *c;
449
450 let sqr = (a + (b + c)) * (c - (a - b)) * (c + (a - b)) * (a + (b - c));
451
452 // We take the max(0.0) because it can be slightly negative
453 // because of numerical errors due to almost-degenerate triangles.
454 ComplexField::sqrt(sqr.max(0.0)) * 0.25
455 }
456
457 /// Computes the unit angular inertia of this triangle.
458 #[cfg(feature = "dim2")]
459 pub fn unit_angular_inertia(&self) -> Real {
460 let factor = 1.0 / 6.0;
461
462 // Algorithm adapted from Box2D
463 let e1 = self.b - self.a;
464 let e2 = self.c - self.a;
465
466 let intx2 = e1.x * e1.x + e2.x * e1.x + e2.x * e2.x;
467 let inty2 = e1.y * e1.y + e2.y * e1.y + e2.y * e2.y;
468 factor * (intx2 + inty2)
469 }
470
471 /// The geometric center of this triangle.
472 #[inline]
473 pub fn center(&self) -> Point<Real> {
474 utils::center(&[self.a, self.b, self.c])
475 }
476
477 /// The perimeter of this triangle.
478 #[inline]
479 pub fn perimeter(&self) -> Real {
480 na::distance(&self.a, &self.b)
481 + na::distance(&self.b, &self.c)
482 + na::distance(&self.c, &self.a)
483 }
484
485 /// The circumcircle of this triangle.
486 pub fn circumcircle(&self) -> (Point<Real>, Real) {
487 let a = self.a - self.c;
488 let b = self.b - self.c;
489
490 let na = a.norm_squared();
491 let nb = b.norm_squared();
492
493 let dab = a.dot(&b);
494
495 let denom = 2.0 * (na * nb - dab * dab);
496
497 if denom.is_zero() {
498 // The triangle is degenerate (the three points are collinear).
499 // So we find the longest segment and take its center.
500 let c = self.a - self.b;
501 let nc = c.norm_squared();
502
503 if nc >= na && nc >= nb {
504 // Longest segment: [&self.a, &self.b]
505 (
506 na::center(&self.a, &self.b),
507 ComplexField::sqrt(nc) / na::convert::<f64, Real>(2.0f64),
508 )
509 } else if na >= nb && na >= nc {
510 // Longest segment: [&self.a, pc]
511 (
512 na::center(&self.a, &self.c),
513 ComplexField::sqrt(na) / na::convert::<f64, Real>(2.0f64),
514 )
515 } else {
516 // Longest segment: [&self.b, &self.c]
517 (
518 na::center(&self.b, &self.c),
519 ComplexField::sqrt(nb) / na::convert::<f64, Real>(2.0f64),
520 )
521 }
522 } else {
523 let k = b * na - a * nb;
524
525 let center = self.c + (a * k.dot(&b) - b * k.dot(&a)) / denom;
526 let radius = na::distance(&self.a, ¢er);
527
528 (center, radius)
529 }
530 }
531
532 /// Tests if this triangle is affinely dependent, i.e., its points are almost aligned.
533 #[cfg(feature = "dim3")]
534 pub fn is_affinely_dependent(&self) -> bool {
535 const EPS: Real = crate::math::DEFAULT_EPSILON * 100.0;
536
537 let p1p2 = self.b - self.a;
538 let p1p3 = self.c - self.a;
539 relative_eq!(p1p2.cross(&p1p3).norm_squared(), 0.0, epsilon = EPS * EPS)
540
541 // relative_eq!(
542 // self.area(),
543 // 0.0,
544 // epsilon = EPS * self.perimeter()
545 // )
546 }
547
548 /// Is this triangle degenerate or almost degenerate?
549 #[cfg(feature = "dim3")]
550 pub fn is_affinely_dependent_eps(&self, eps: Real) -> bool {
551 let p1p2 = self.b - self.a;
552 let p1p3 = self.c - self.a;
553 relative_eq!(
554 p1p2.cross(&p1p3).norm(),
555 0.0,
556 epsilon = eps * p1p2.norm().max(p1p3.norm())
557 )
558
559 // relative_eq!(
560 // self.area(),
561 // 0.0,
562 // epsilon = EPS * self.perimeter()
563 // )
564 }
565
566 /// Tests if a point is inside of this triangle.
567 #[cfg(feature = "dim2")]
568 pub fn contains_point(&self, p: &Point<Real>) -> bool {
569 let ab = self.b - self.a;
570 let bc = self.c - self.b;
571 let ca = self.a - self.c;
572 let sgn1 = ab.perp(&(p - self.a));
573 let sgn2 = bc.perp(&(p - self.b));
574 let sgn3 = ca.perp(&(p - self.c));
575 sgn1.signum() * sgn2.signum() >= 0.0
576 && sgn1.signum() * sgn3.signum() >= 0.0
577 && sgn2.signum() * sgn3.signum() >= 0.0
578 }
579
580 /// Tests if a point is inside of this triangle.
581 #[cfg(feature = "dim3")]
582 pub fn contains_point(&self, p: &Point<Real>) -> bool {
583 const EPS: Real = crate::math::DEFAULT_EPSILON;
584
585 let vb = self.b - self.a;
586 let vc = self.c - self.a;
587 let vp = p - self.a;
588
589 let n = vc.cross(&vb);
590 let n_norm = n.norm_squared();
591 if n_norm < EPS || vp.dot(&n).abs() > EPS * n_norm {
592 // the triangle is degenerate or the
593 // point does not lie on the same plane as the triangle.
594 return false;
595 }
596
597 // We are seeking B, C such that vp = vb * B + vc * C .
598 // If B and C are both in [0, 1] and B + C <= 1 then p is in the triangle.
599 //
600 // We can project this equation along a vector nb coplanar to the triangle
601 // and perpendicular to vb:
602 // vp.dot(nb) = vb.dot(nb) * B + vc.dot(nb) * C
603 // => C = vp.dot(nb) / vc.dot(nb)
604 // and similarly for B.
605 //
606 // In order to avoid divisions and sqrts we scale both B and C - so
607 // b = vb.dot(nc) * B and c = vc.dot(nb) * C - this results in harder-to-follow math but
608 // hopefully fast code.
609
610 let nb = vb.cross(&n);
611 let nc = vc.cross(&n);
612
613 let signed_blim = vb.dot(&nc);
614 let b = vp.dot(&nc) * signed_blim.signum();
615 let blim = signed_blim.abs();
616
617 let signed_clim = vc.dot(&nb);
618 let c = vp.dot(&nb) * signed_clim.signum();
619 let clim = signed_clim.abs();
620
621 c >= 0.0 && c <= clim && b >= 0.0 && b <= blim && c * blim + b * clim <= blim * clim
622 }
623
624 /// The normal of the given feature of this shape.
625 #[cfg(feature = "dim3")]
626 pub fn feature_normal(&self, _: FeatureId) -> Option<Unit<Vector<Real>>> {
627 self.normal()
628 }
629
630 /// The orientation of the triangle, based on its signed area.
631 ///
632 /// Returns `TriangleOrientation::Degenerate` if the triangle’s area is
633 /// smaller than `epsilon`.
634 #[cfg(feature = "dim2")]
635 pub fn orientation(&self, epsilon: Real) -> TriangleOrientation {
636 let area2 = (self.b - self.a).perp(&(self.c - self.a));
637 // println!("area2: {}", area2);
638 if area2 > epsilon {
639 TriangleOrientation::CounterClockwise
640 } else if area2 < -epsilon {
641 TriangleOrientation::Clockwise
642 } else {
643 TriangleOrientation::Degenerate
644 }
645 }
646
647 /// The orientation of the 2D triangle, based on its signed area.
648 ///
649 /// Returns `TriangleOrientation::Degenerate` if the triangle’s area is
650 /// smaller than `epsilon`.
651 pub fn orientation2d(
652 a: &na::Point2<Real>,
653 b: &na::Point2<Real>,
654 c: &na::Point2<Real>,
655 epsilon: Real,
656 ) -> TriangleOrientation {
657 let area2 = (b - a).perp(&(c - a));
658 // println!("area2: {}", area2);
659 if area2 > epsilon {
660 TriangleOrientation::CounterClockwise
661 } else if area2 < -epsilon {
662 TriangleOrientation::Clockwise
663 } else {
664 TriangleOrientation::Degenerate
665 }
666 }
667
668 /// Find the index of a vertex in this triangle, such that the two
669 /// edges incident in that vertex form the angle closest to 90
670 /// degrees in the triangle.
671 pub fn angle_closest_to_90(&self) -> usize {
672 let points = self.vertices();
673 let mut best_cos = 2.0;
674 let mut selected_i = 0;
675
676 for i in 0..3 {
677 let d1 = (points[i] - points[(i + 1) % 3]).normalize();
678 let d2 = (points[(i + 2) % 3] - points[(i + 1) % 3]).normalize();
679
680 let cos_abs = d1.dot(&d2).abs();
681
682 if cos_abs < best_cos {
683 best_cos = cos_abs;
684 selected_i = i;
685 }
686 }
687
688 selected_i
689 }
690
691 /// Reverse the orientation of this triangle by swapping b and c.
692 pub fn reverse(&mut self) {
693 mem::swap(&mut self.b, &mut self.c);
694 }
695}
696
697impl SupportMap for Triangle {
698 #[inline]
699 fn local_support_point(&self, dir: &Vector<Real>) -> Point<Real> {
700 let d1 = self.a.coords.dot(dir);
701 let d2 = self.b.coords.dot(dir);
702 let d3 = self.c.coords.dot(dir);
703
704 if d1 > d2 {
705 if d1 > d3 {
706 self.a
707 } else {
708 self.c
709 }
710 } else if d2 > d3 {
711 self.b
712 } else {
713 self.c
714 }
715 }
716}
717
718/*
719#[cfg(feature = "dim3")]
720impl ConvexPolyhedron for Triangle {
721 fn vertex(&self, id: FeatureId) -> Point<Real> {
722 match id.unwrap_vertex() {
723 0 => self.a,
724 1 => self.b,
725 2 => self.c,
726 _ => panic!("Triangle vertex index out of bounds."),
727 }
728 }
729 fn edge(&self, id: FeatureId) -> (Point<Real>, Point<Real>, FeatureId, FeatureId) {
730 match id.unwrap_edge() {
731 0 => (self.a, self.b, FeatureId::Vertex(0), FeatureId::Vertex(1)),
732 1 => (self.b, self.c, FeatureId::Vertex(1), FeatureId::Vertex(2)),
733 2 => (self.c, self.a, FeatureId::Vertex(2), FeatureId::Vertex(0)),
734 _ => panic!("Triangle edge index out of bounds."),
735 }
736 }
737
738 fn face(&self, id: FeatureId, face: &mut ConvexPolygonalFeature) {
739 face.clear();
740
741 if let Some(normal) = self.normal() {
742 face.set_feature_id(id);
743
744 match id.unwrap_face() {
745 0 => {
746 face.push(self.a, FeatureId::Vertex(0));
747 face.push(self.b, FeatureId::Vertex(1));
748 face.push(self.c, FeatureId::Vertex(2));
749 face.push_edge_feature_id(FeatureId::Edge(0));
750 face.push_edge_feature_id(FeatureId::Edge(1));
751 face.push_edge_feature_id(FeatureId::Edge(2));
752 face.set_normal(normal);
753 }
754 1 => {
755 face.push(self.a, FeatureId::Vertex(0));
756 face.push(self.c, FeatureId::Vertex(2));
757 face.push(self.b, FeatureId::Vertex(1));
758 face.push_edge_feature_id(FeatureId::Edge(2));
759 face.push_edge_feature_id(FeatureId::Edge(1));
760 face.push_edge_feature_id(FeatureId::Edge(0));
761 face.set_normal(-normal);
762 }
763 _ => unreachable!(),
764 }
765
766 face.recompute_edge_normals();
767 } else {
768 face.push(self.a, FeatureId::Vertex(0));
769 face.set_feature_id(FeatureId::Vertex(0));
770 }
771 }
772
773 fn support_face_toward(
774 &self,
775 m: &Isometry<Real>,
776 dir: &Unit<Vector<Real>>,
777 face: &mut ConvexPolygonalFeature,
778 ) {
779 let normal = self.scaled_normal();
780
781 if normal.dot(&*dir) >= 0.0 {
782 ConvexPolyhedron::face(self, FeatureId::Face(0), face);
783 } else {
784 ConvexPolyhedron::face(self, FeatureId::Face(1), face);
785 }
786 face.transform_by(m)
787 }
788
789 fn support_feature_toward(
790 &self,
791 transform: &Isometry<Real>,
792 dir: &Unit<Vector<Real>>,
793 eps: Real,
794 out: &mut ConvexPolygonalFeature,
795 ) {
796 out.clear();
797 let tri = self.transformed(transform);
798 let feature = tri.support_feature_id_toward(dir, eps);
799
800 match feature {
801 FeatureId::Vertex(_) => {
802 let v = tri.vertex(feature);
803 out.push(v, feature);
804 out.set_feature_id(feature);
805 }
806 FeatureId::Edge(_) => {
807 let (a, b, fa, fb) = tri.edge(feature);
808 out.push(a, fa);
809 out.push(b, fb);
810 out.push_edge_feature_id(feature);
811 out.set_feature_id(feature);
812 }
813 FeatureId::Face(_) => tri.face(feature, out),
814 _ => unreachable!(),
815 }
816 }
817
818 fn support_feature_id_toward(&self, local_dir: &Unit<Vector<Real>>) -> FeatureId {
819 self.support_feature_id_toward(local_dir, na::convert::<f64, Real>(f64::consts::PI / 180.0))
820 }
821}
822*/
823
824#[cfg(feature = "dim2")]
825#[cfg(test)]
826mod test {
827 use crate::shape::Triangle;
828 use na::Point2;
829
830 #[test]
831 fn test_triangle_area() {
832 let pa = Point2::new(5.0, 0.0);
833 let pb = Point2::origin();
834 let pc = Point2::new(0.0, 4.0);
835
836 assert!(relative_eq!(Triangle::new(pa, pb, pc).area(), 10.0));
837 }
838
839 #[test]
840 fn test_triangle_contains_point() {
841 let tri = Triangle::new(
842 Point2::new(5.0, 0.0),
843 Point2::origin(),
844 Point2::new(0.0, 4.0),
845 );
846
847 assert!(tri.contains_point(&Point2::new(1.0, 1.0)));
848 assert!(!tri.contains_point(&Point2::new(-1.0, 1.0)));
849 }
850
851 #[test]
852 fn test_obtuse_triangle_contains_point() {
853 let tri = Triangle::new(
854 Point2::new(-10.0, 10.0),
855 Point2::origin(),
856 Point2::new(20.0, 0.0),
857 );
858
859 assert!(tri.contains_point(&Point2::new(-3.0, 5.0)));
860 assert!(tri.contains_point(&Point2::new(5.0, 1.0)));
861 assert!(!tri.contains_point(&Point2::new(0.0, -1.0)));
862 }
863}
864
865#[cfg(feature = "dim3")]
866#[cfg(test)]
867mod test {
868 use crate::math::Real;
869 use crate::shape::Triangle;
870 use na::Point3;
871
872 #[test]
873 fn test_triangle_area() {
874 let pa = Point3::new(0.0, 5.0, 0.0);
875 let pb = Point3::origin();
876 let pc = Point3::new(0.0, 0.0, 4.0);
877
878 assert!(relative_eq!(Triangle::new(pa, pb, pc).area(), 10.0));
879 }
880
881 #[test]
882 fn test_triangle_contains_point() {
883 let tri = Triangle::new(
884 Point3::new(0.0, 5.0, 0.0),
885 Point3::origin(),
886 Point3::new(0.0, 0.0, 4.0),
887 );
888
889 assert!(tri.contains_point(&Point3::new(0.0, 1.0, 1.0)));
890 assert!(!tri.contains_point(&Point3::new(0.0, -1.0, 1.0)));
891 }
892
893 #[test]
894 fn test_obtuse_triangle_contains_point() {
895 let tri = Triangle::new(
896 Point3::new(-10.0, 10.0, 0.0),
897 Point3::origin(),
898 Point3::new(20.0, 0.0, 0.0),
899 );
900
901 assert!(tri.contains_point(&Point3::new(-3.0, 5.0, 0.0)));
902 assert!(tri.contains_point(&Point3::new(5.0, 1.0, 0.0)));
903 assert!(!tri.contains_point(&Point3::new(0.0, -1.0, 0.0)));
904 }
905
906 #[test]
907 fn test_3dtriangle_contains_point() {
908 let o = Point3::origin();
909 let pa = Point3::new(1.2, 1.4, 5.6);
910 let pb = Point3::new(1.5, 6.7, 1.9);
911 let pc = Point3::new(5.0, 2.1, 1.3);
912
913 let tri = Triangle::new(pa, pb, pc);
914
915 let va = pa - o;
916 let vb = pb - o;
917 let vc = pc - o;
918
919 let n = (pa - pb).cross(&(pb - pc));
920
921 // This is a simple algorithm for generating points that are inside the
922 // triangle: o + (va * alpha + vb * beta + vc * gamma) is always inside the
923 // triangle if:
924 // * each of alpha, beta, gamma is in (0, 1)
925 // * alpha + beta + gamma = 1
926 let contained_p = o + (va * 0.2 + vb * 0.3 + vc * 0.5);
927 let not_contained_coplanar_p = o + (va * -0.5 + vb * 0.8 + vc * 0.7);
928 let not_coplanar_p = o + (va * 0.2 + vb * 0.3 + vc * 0.5) + n * 0.1;
929 let not_coplanar_p2 = o + (va * -0.5 + vb * 0.8 + vc * 0.7) + n * 0.1;
930 assert!(tri.contains_point(&contained_p));
931 assert!(!tri.contains_point(¬_contained_coplanar_p));
932 assert!(!tri.contains_point(¬_coplanar_p));
933 assert!(!tri.contains_point(¬_coplanar_p2));
934
935 // Test that points that are clearly within the triangle as seen as such, by testing
936 // a number of points along a line intersecting the triangle.
937 for i in -50i16..150 {
938 let a = 0.15;
939 let b = 0.01 * Real::from(i); // b ranges from -0.5 to 1.5
940 let c = 1.0 - a - b;
941 let p = o + (va * a + vb * b + vc * c);
942
943 match i {
944 ii if ii < 0 || ii > 85 => assert!(
945 !tri.contains_point(&p),
946 "Should not contain: i = {}, b = {}",
947 i,
948 b
949 ),
950 ii if ii > 0 && ii < 85 => assert!(
951 tri.contains_point(&p),
952 "Should contain: i = {}, b = {}",
953 i,
954 b
955 ),
956 _ => (), // Points at the edge may be seen as inside or outside
957 }
958 }
959 }
960}