ogeom_mesh/
parity.rs

1//! Inside or outside a closed mesh, by the parity of its crossings along a
2//! line parallel to `x`.
3//!
4//! The triangles the line crosses are found exactly. A line through an edge
5//! or a vertex is moved by `(ε, ε²)` in `(y, z)`, `ε` infinitesimal, a
6//! simulation of simplicity, so that two triangles sharing an edge never
7//! both count it and never both miss it. A point on the line is inside
8//! where an odd number of the crossings lie ahead of it, each decided by
9//! the exact side of the point on the triangle's plane, and on the mesh
10//! where it lies exactly in a crossed triangle.
11//!
12//! The answer is the mesh's own wherever every edge is used an even number
13//! of times, as [`Triangulation::is_closed`](ogeom_topo::Triangulation::is_closed)
14//! asks of a closed mesh: such a mesh bounds the points it winds about an
15//! odd number of times, and only those.
16
17use ogeom_core::{Exact, P3, Predicates, Sign};
18use ogeom_math::Point;
19
20use crate::Bvh;
21
22/// Where a point lies against a closed mesh.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub enum Lies {
25    /// Strictly inside.
26    Inside,
27    /// Strictly outside.
28    Outside,
29    /// Exactly in a triangle the line through it crosses.
30    On,
31}
32
33impl Lies {
34    /// Whether the point is inside or on the mesh.
35    #[must_use]
36    pub const fn is_inside_or_on(self) -> bool {
37        matches!(self, Self::Inside | Self::On)
38    }
39}
40
41/// A triangle the line crosses.
42#[derive(Debug, Clone, Copy)]
43struct Crossing {
44    corners: [P3; 3],
45    /// The triangle's extent along the line.
46    low: f64,
47    high: f64,
48    /// The sign of its normal along the line.
49    facing: Sign,
50}
51
52/// The line along `x` through `(y, z)`, with the triangles of a mesh it
53/// crosses.
54#[derive(Debug, Clone)]
55pub struct Line {
56    y: f64,
57    z: f64,
58    crossings: Vec<Crossing>,
59}
60
61fn coords(p: Point) -> P3 {
62    [p.x, p.y, p.z]
63}
64
65/// The sign of `a - b`, exactly.
66fn order(a: f64, b: f64) -> Sign {
67    if a > b {
68        Sign::Positive
69    } else if a < b {
70        Sign::Negative
71    } else {
72        Sign::Zero
73    }
74}
75
76/// Whether the line along `x` through `(y, z)` crosses the triangle, moved
77/// by `(ε, ε²)` in `(y, z)`; if so, the sign of the triangle's normal along
78/// `x`.
79fn crosses(p: &[P3; 3], y: f64, z: f64) -> Option<Sign> {
80    let flat = p.map(|c| [c[1], c[2]]);
81    let facing = Exact::orient2d(flat[0], flat[1], flat[2]);
82    if facing.is_zero() {
83        return None;
84    }
85    for k in 0..3 {
86        let (a, b) = (p[k], p[(k + 1) % 3]);
87        let mut o = Exact::orient2d(flat[k], flat[(k + 1) % 3], [y, z]);
88        if o.is_zero() {
89            o = order(a[2], b[2]);
90        }
91        if o.is_zero() {
92            o = order(b[1], a[1]);
93        }
94        if o != facing {
95            return None;
96        }
97    }
98    Some(facing)
99}
100
101impl Line {
102    /// The line along `x` through `(y, z)`, and the triangles of `bvh` it
103    /// crosses.
104    #[must_use]
105    pub fn through(bvh: &Bvh, y: f64, z: f64) -> Self {
106        let mut crossings = Vec::new();
107        for t in bvh.triangles_where(|b| match (b.low(), b.high()) {
108            (Some(l), Some(h)) => l.y <= y && y <= h.y && l.z <= z && z <= h.z,
109            _ => false,
110        }) {
111            let Some(corners) = bvh.triangle(t).map(|c| c.map(coords)) else {
112                continue;
113            };
114            if let Some(facing) = crosses(&corners, y, z) {
115                let xs = corners.map(|c| c[0]);
116                crossings.push(Crossing {
117                    corners,
118                    low: xs[0].min(xs[1]).min(xs[2]),
119                    high: xs[0].max(xs[1]).max(xs[2]),
120                    facing,
121                });
122            }
123        }
124        Self { y, z, crossings }
125    }
126
127    /// Where the point of the line at `x` lies against the mesh.
128    #[must_use]
129    pub fn lies(&self, x: f64) -> Lies {
130        let node = [x, self.y, self.z];
131        let mut ahead = 0_u32;
132        for c in &self.crossings {
133            if x < c.low {
134                ahead += 1;
135            } else if x <= c.high {
136                // The node's side of the plane is the crossing's side of
137                // the node along the line, times its facing.
138                let s = Exact::orient3d(c.corners[0], c.corners[1], c.corners[2], node);
139                if s.is_zero() {
140                    return Lies::On;
141                }
142                if s == c.facing {
143                    ahead += 1;
144                }
145            }
146        }
147        if ahead % 2 == 1 {
148            Lies::Inside
149        } else {
150            Lies::Outside
151        }
152    }
153}
ogeom_mesh/parity.rs

ogeom_mesh/
parity.rs
