axiolid_mesh/halfedge/
check.rs

1//! Full structural validation, independent of how the mesh was produced.
2
3use core::fmt;
4
5use super::{HalfedgeId, HalfedgeMesh, VertexId, NONE};
6
7/// The first structural invariant a [`HalfedgeMesh`] was found to break.
8#[non_exhaustive]
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct HalfedgeInvariantError {
11    /// Which rule broke, in words.
12    pub rule: &'static str,
13    /// Kind of element the rule was checked on.
14    pub element: &'static str,
15    /// Index of that element.
16    pub index: u32,
17}
18
19impl fmt::Display for HalfedgeInvariantError {
20    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
21        write!(f, "{} {}: {}", self.element, self.index, self.rule)
22    }
23}
24
25impl std::error::Error for HalfedgeInvariantError {}
26
27fn fail(rule: &'static str, element: &'static str, index: usize) -> HalfedgeInvariantError {
28    HalfedgeInvariantError {
29        rule,
30        element,
31        index: index as u32,
32    }
33}
34
35pub(super) fn validate(mesh: &HalfedgeMesh) -> Result<(), HalfedgeInvariantError> {
36    let live_count = |flags: &[bool]| flags.iter().filter(|&&alive| alive).count();
37    if live_count(&mesh.vertex_live) != mesh.live_vertices
38        || live_count(&mesh.edge_live) != mesh.live_edges
39        || live_count(&mesh.face_live) != mesh.live_faces
40        || mesh.vertex_live.len() != mesh.positions.len()
41        || mesh.vertex_out.len() != mesh.positions.len()
42        || mesh.links.len() != mesh.edge_live.len() * 2
43        || mesh.face_halfedge.len() != mesh.face_live.len()
44    {
45        return Err(fail("element counts disagree with storage", "mesh", 0));
46    }
47    let halfedge_live = |h: u32| h != NONE && mesh.edge_live.get((h / 2) as usize) == Some(&true);
48    let vertex_live = |v: u32| v != NONE && mesh.vertex_live.get(v as usize) == Some(&true);
49    let face_live = |f: u32| f != NONE && mesh.face_live.get(f as usize) == Some(&true);
50
51    let mut out_count = vec![0u32; mesh.positions.len()];
52    let mut boundary_out = vec![0u32; mesh.positions.len()];
53    for e in mesh.edges() {
54        let [a, b] = [e.0 * 2, e.0 * 2 + 1];
55        if mesh.links[a as usize].face == NONE && mesh.links[b as usize].face == NONE {
56            return Err(fail("both sides are boundary", "edge", e.index()));
57        }
58        for h in [a, b] {
59            let link = mesh.links[h as usize];
60            if !halfedge_live(link.next) || !halfedge_live(link.prev) {
61                return Err(fail("links to a removed halfedge", "halfedge", h as usize));
62            }
63            if mesh.links[link.next as usize].prev != h || mesh.links[link.prev as usize].next != h
64            {
65                return Err(fail(
66                    "next and prev are not inverse",
67                    "halfedge",
68                    h as usize,
69                ));
70            }
71            if !vertex_live(link.target) {
72                return Err(fail("targets a removed vertex", "halfedge", h as usize));
73            }
74            if link.face != NONE && !face_live(link.face) {
75                return Err(fail("lies on a removed face", "halfedge", h as usize));
76            }
77            if mesh.links[link.next as usize].face != link.face {
78                return Err(fail("next lies on another face", "halfedge", h as usize));
79            }
80            let source = mesh.links[(h ^ 1) as usize].target;
81            if mesh.links[link.prev as usize].target != source {
82                return Err(fail(
83                    "prev does not end at the source",
84                    "halfedge",
85                    h as usize,
86                ));
87            }
88            if source == link.target {
89                return Err(fail("joins a vertex to itself", "halfedge", h as usize));
90            }
91            out_count[source as usize] += 1;
92            if link.face == NONE {
93                boundary_out[source as usize] += 1;
94            }
95        }
96    }
97
98    for f in mesh.faces() {
99        let h = mesh.face_halfedge[f.index()];
100        if !halfedge_live(h) || mesh.links[h as usize].face != f.0 {
101            return Err(fail(
102                "stored halfedge is not on the face",
103                "face",
104                f.index(),
105            ));
106        }
107        let mut corners: Vec<u32> = Vec::new();
108        for g in mesh.loop_halfedges(HalfedgeId(h)) {
109            corners.push(mesh.links[g.index()].target);
110            if corners.len() > mesh.links.len() {
111                return Err(fail("loop does not close", "face", f.index()));
112            }
113        }
114        if corners.len() < 3 {
115            return Err(fail("fewer than three sides", "face", f.index()));
116        }
117        corners.sort_unstable();
118        if corners.windows(2).any(|pair| pair[0] == pair[1]) {
119            return Err(fail("visits a vertex twice", "face", f.index()));
120        }
121    }
122
123    let mut neighbours: Vec<VertexId> = Vec::new();
124    for v in mesh.vertices() {
125        let h = mesh.vertex_out[v.index()];
126        if h == NONE {
127            if out_count[v.index()] != 0 {
128                return Err(fail(
129                    "has edges but no stored halfedge",
130                    "vertex",
131                    v.index(),
132                ));
133            }
134            continue;
135        }
136        if !halfedge_live(h) || mesh.links[(h ^ 1) as usize].target != v.0 {
137            return Err(fail(
138                "stored halfedge does not leave it",
139                "vertex",
140                v.index(),
141            ));
142        }
143        if boundary_out[v.index()] > 1 {
144            return Err(fail("lies on more than one hole", "vertex", v.index()));
145        }
146        if boundary_out[v.index()] == 1 && mesh.links[h as usize].face != NONE {
147            return Err(fail(
148                "stored halfedge is not its boundary halfedge",
149                "vertex",
150                v.index(),
151            ));
152        }
153        neighbours.clear();
154        for g in mesh.outgoing_halfedges(v) {
155            neighbours.push(mesh.target(g));
156            if neighbours.len() > out_count[v.index()] as usize {
157                break;
158            }
159        }
160        if neighbours.len() != out_count[v.index()] as usize {
161            return Err(fail(
162                "rotation does not reach every outgoing halfedge",
163                "vertex",
164                v.index(),
165            ));
166        }
167        neighbours.sort_unstable();
168        if neighbours.windows(2).any(|pair| pair[0] == pair[1]) {
169            return Err(fail(
170                "two edges join the same neighbour",
171                "vertex",
172                v.index(),
173            ));
174        }
175    }
176    Ok(())
177}
axiolid_mesh/halfedge/check.rs

axiolid_mesh/halfedge/
check.rs
