axiolid_inspect/
coplanar.rs

1//! Surfaces that nearly share a plane.
2//!
3//! Two meshes whose faces lie in one plane in exact arithmetic come out of
4//! placement a rounding residue apart: each vertex rounds on its own. A
5//! boolean that decides on the raw values reads those faces as crossing at a
6//! sliver of an angle, or leaves a crack. This query finds such a pair: a
7//! triangle of each, within the search distance of each other, whose corners
8//! all lie within that distance of the other's plane, and which are not
9//! exactly coplanar. Exact contact (every corner on the plane, certified)
10//! is a decided case and is not reported; neither is a crossing at an angle.
11//!
12//! Distances are measurements (ADR 0045); only "exactly on the plane" is an
13//! `orient3d` sign.
14
15use axiolid_core::Point3;
16use axiolid_guarantees::Sign;
17use axiolid_mesh::TriMesh;
18use axiolid_predicates::orient3d;
19use axiolid_spatial::SpatialItem;
20
21use crate::clearance::{build_index, triangle_at, triangle_distance};
22
23/// A pair of triangles that nearly share a plane.
24#[derive(Debug, Clone, Copy, PartialEq)]
25pub struct NearCoplanar {
26    /// Triangle index in the first mesh.
27    pub first: usize,
28    /// Triangle index in the second mesh.
29    pub second: usize,
30    /// The largest distance from a corner of either triangle to the other's
31    /// plane.
32    pub offset: f64,
33}
34
35/// The first pair of triangles of `a` and `b` that nearly share a plane
36/// within `linear`, in ascending `(first, second)` order.
37///
38/// A pair qualifies when both triangles are non-degenerate, the distance
39/// between them is at most `linear`, every corner of each lies within
40/// `linear` of the other's plane, and at least one corner of the second is
41/// not exactly on the first's plane. `None` when no pair qualifies, and when
42/// `linear` is negative or not finite (zero is allowed: then only an offset
43/// of zero distance would qualify, which exact coplanarity excludes).
44///
45/// # Panics
46///
47/// Never. A malformed index buffer yields `None` rather than a panic.
48pub fn near_coplanar(a: &TriMesh, b: &TriMesh, linear: f64) -> Option<NearCoplanar> {
49    if !linear.is_finite() || linear < 0.0 {
50        return None;
51    }
52    let index = build_index(b, linear);
53    let mut candidates = Vec::new();
54    for first in 0..a.indices.len() / 3 {
55        let Some(first_triangle) = triangle_at(a, first) else {
56            continue;
57        };
58        let probe = crate::clearance::grow(crate::clearance::bounds_of(&first_triangle), linear);
59        candidates.clear();
60        index.query_aabb(&probe, &mut candidates);
61        let mut seconds: Vec<usize> = candidates
62            .iter()
63            .filter_map(|&candidate| {
64                index
65                    .item(candidate)
66                    .map(|item: &SpatialItem<u32>| item.key as usize)
67            })
68            .collect();
69        seconds.sort_unstable();
70        for second in seconds {
71            let Some(second_triangle) = triangle_at(b, second) else {
72                continue;
73            };
74            if let Some(offset) = nearly_share_a_plane(&first_triangle, &second_triangle, linear) {
75                return Some(NearCoplanar {
76                    first,
77                    second,
78                    offset,
79                });
80            }
81        }
82    }
83    None
84}
85
86/// The pair's offset when it qualifies.
87fn nearly_share_a_plane(a: &[Point3; 3], b: &[Point3; 3], linear: f64) -> Option<f64> {
88    let to_a = corner_distances(a, b)?;
89    let to_b = corner_distances(b, a)?;
90    let offset = to_a.max(to_b);
91    if offset > linear || triangle_distance(a, b) > linear {
92        return None;
93    }
94    let exactly_on_plane = b
95        .iter()
96        .all(|corner| orient3d(a[0], a[1], a[2], *corner).sign() == Some(Sign::Zero));
97    (!exactly_on_plane).then_some(offset)
98}
99
100/// The largest distance from a corner of `corners` to the plane of `plane`,
101/// or `None` if `plane` is degenerate.
102pub(crate) fn corner_distances(plane: &[Point3; 3], corners: &[Point3; 3]) -> Option<f64> {
103    let normal = (plane[1] - plane[0]).cross(plane[2] - plane[0]);
104    let length = normal.length();
105    if !length.is_finite() || length <= 0.0 {
106        return None;
107    }
108    let normal = normal / length;
109    Some(
110        corners
111            .iter()
112            .map(|corner| normal.dot(*corner - plane[0]).abs())
113            .fold(0.0, f64::max),
114    )
115}
axiolid_inspect/coplanar.rs

axiolid_inspect/
coplanar.rs
