axiolid_reference/
triangle_triangle.rs

1//! Certified triangle/triangle topology classification.
2//!
3//! Coplanar triangle overlap is deliberately reported as [`TriangleTriangleRelation::Coplanar`]
4//! rather than collapsed into contact. It requires a caller to make any 2D surface policy explicit.
5
6use axiolid_contracts::Sign;
7use axiolid_core::{Point2, Point3};
8
9use crate::{orient2d, segment_triangle_relation, SegmentTriangleRelation};
10
11/// The exact topological relation between two finite triangles.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum TriangleTriangleRelation {
14    /// The closed triangle primitives have no common point.
15    Disjoint,
16    /// The triangles cross transversally through both interiors.
17    Proper,
18    /// The triangles meet at a vertex, edge, or other non-transverse contact.
19    Touching,
20    /// All vertices lie in one plane. This does not assert planar overlap.
21    Coplanar,
22    /// At least one triangle has collinear vertices.
23    DegenerateTriangle,
24}
25
26/// Classify two triangles using certified orientation predicates.
27///
28/// This accepts no tolerance: it reports topology for the supplied binary64
29/// coordinates. Metric overlap lengths and coplanar-surface policy belong in
30/// higher layers.
31#[must_use]
32pub fn triangle_triangle_relation(
33    first: [Point3; 3],
34    second: [Point3; 3],
35) -> TriangleTriangleRelation {
36    if degenerate(first) || degenerate(second) {
37        return TriangleTriangleRelation::DegenerateTriangle;
38    }
39
40    let second_in_first_plane =
41        second.map(|point| sign(crate::orient3d(first[0], first[1], first[2], point)));
42    if second_in_first_plane.iter().all(|&side| side == Sign::Zero) {
43        return TriangleTriangleRelation::Coplanar;
44    }
45
46    let mut touching = false;
47    for triangle in [first, second] {
48        let other = if triangle == first { second } else { first };
49        for edge in [
50            [triangle[0], triangle[1]],
51            [triangle[1], triangle[2]],
52            [triangle[2], triangle[0]],
53        ] {
54            match segment_triangle_relation(edge[0], edge[1], other) {
55                SegmentTriangleRelation::Proper => return TriangleTriangleRelation::Proper,
56                SegmentTriangleRelation::Touching => touching = true,
57                SegmentTriangleRelation::Coplanar => {
58                    touching |= coplanar_segment_touches_triangle(edge, other);
59                }
60                SegmentTriangleRelation::Disjoint => {}
61                SegmentTriangleRelation::DegenerateSegment
62                | SegmentTriangleRelation::DegenerateTriangle => {
63                    unreachable!("validated triangles have non-degenerate edges")
64                }
65            }
66        }
67    }
68
69    if touching {
70        TriangleTriangleRelation::Touching
71    } else {
72        TriangleTriangleRelation::Disjoint
73    }
74}
75
76fn degenerate([a, b, c]: [Point3; 3]) -> bool {
77    (b - a).cross(c - a).length_squared() == 0.0
78}
79
80fn coplanar_segment_touches_triangle(segment: [Point3; 2], triangle: [Point3; 3]) -> bool {
81    let normal = (triangle[1] - triangle[0]).cross(triangle[2] - triangle[0]);
82    let axis = dominant_axis(normal);
83    let [start, end] = segment.map(|point| project(point, axis));
84    let projected = triangle.map(|point| project(point, axis));
85
86    point_in_triangle(start, projected)
87        || point_in_triangle(end, projected)
88        || [
89            [projected[0], projected[1]],
90            [projected[1], projected[2]],
91            [projected[2], projected[0]],
92        ]
93        .into_iter()
94        .any(|edge| segments_touch([start, end], edge))
95}
96
97fn point_in_triangle(point: Point2, [a, b, c]: [Point2; 3]) -> bool {
98    let signs = [
99        sign(orient2d(a, b, point)),
100        sign(orient2d(b, c, point)),
101        sign(orient2d(c, a, point)),
102    ];
103    signs.iter().all(|&side| side != Sign::Negative)
104        || signs.iter().all(|&side| side != Sign::Positive)
105}
106
107fn segments_touch([a, b]: [Point2; 2], [c, d]: [Point2; 2]) -> bool {
108    let ab_c = sign(orient2d(a, b, c));
109    let ab_d = sign(orient2d(a, b, d));
110    let cd_a = sign(orient2d(c, d, a));
111    let cd_b = sign(orient2d(c, d, b));
112    straddles(ab_c, ab_d) && straddles(cd_a, cd_b)
113}
114
115fn straddles(first: Sign, second: Sign) -> bool {
116    first == Sign::Zero || second == Sign::Zero || first != second
117}
118
119fn dominant_axis(vector: Point3) -> usize {
120    let absolute = vector.abs();
121    if absolute.x >= absolute.y && absolute.x >= absolute.z {
122        0
123    } else if absolute.y >= absolute.z {
124        1
125    } else {
126        2
127    }
128}
129
130fn project(point: Point3, axis: usize) -> Point2 {
131    match axis {
132        0 => Point2::new(point.y, point.z),
133        1 => Point2::new(point.x, point.z),
134        _ => Point2::new(point.x, point.y),
135    }
136}
137
138fn sign(value: axiolid_contracts::Certified) -> Sign {
139    value.sign().expect("certified predicates are total")
140}
axiolid_reference/triangle_triangle.rs

axiolid_reference/
triangle_triangle.rs
