axiolid_mesh/halfedge/
build.rs

1//! Building a halfedge mesh from an indexed face list, refusing what a
2//! halfedge structure cannot represent.
3
4use core::fmt;
5
6use axiolid_core::Point3;
7
8use super::{HalfedgeMesh, Link, VertexId, NONE};
9
10/// Why a face list cannot become a [`HalfedgeMesh`].
11///
12/// Each refusal names the configuration and the elements involved, so a
13/// caller can repair or report the input instead of guessing.
14#[non_exhaustive]
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub enum HalfedgeBuildError {
17    /// The triangle index buffer is not divisible by three.
18    IncompleteTriangle {
19        /// Indices found.
20        index_count: usize,
21    },
22    /// A face has fewer than three corners.
23    FaceTooSmall {
24        /// The face.
25        face: usize,
26        /// Corners found.
27        corners: usize,
28    },
29    /// A corner names a position that does not exist.
30    IndexOutOfRange {
31        /// The face.
32        face: usize,
33        /// The offending index.
34        index: u32,
35        /// Positions available.
36        position_count: usize,
37    },
38    /// A face visits the same vertex twice.
39    DegenerateFace {
40        /// The face.
41        face: usize,
42        /// The repeated vertex.
43        vertex: u32,
44    },
45    /// More than two faces share an edge.
46    NonManifoldEdge {
47        /// Lower endpoint.
48        a: u32,
49        /// Higher endpoint.
50        b: u32,
51        /// Faces using the edge.
52        faces: usize,
53    },
54    /// Two faces traverse a shared edge in the same direction: their windings
55    /// disagree (or the same face appears twice).
56    InconsistentOrientation {
57        /// Source of the doubly-used direction.
58        from: u32,
59        /// Target of the doubly-used direction.
60        to: u32,
61    },
62    /// The faces around a vertex form more than one fan: two cones touching
63    /// at a point, or a boundary vertex where two holes meet.
64    NonManifoldVertex {
65        /// The vertex.
66        vertex: u32,
67    },
68    /// The mesh needs more elements than 32-bit ids can address.
69    TooLarge,
70}
71
72impl fmt::Display for HalfedgeBuildError {
73    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
74        match self {
75            Self::IncompleteTriangle { index_count } => {
76                write!(f, "index count {index_count} is not divisible by three")
77            }
78            Self::FaceTooSmall { face, corners } => {
79                write!(f, "face {face} has {corners} corners, fewer than three")
80            }
81            Self::IndexOutOfRange {
82                face,
83                index,
84                position_count,
85            } => write!(
86                f,
87                "face {face} names position {index}, but there are {position_count}"
88            ),
89            Self::DegenerateFace { face, vertex } => {
90                write!(f, "face {face} visits vertex {vertex} twice")
91            }
92            Self::NonManifoldEdge { a, b, faces } => {
93                write!(f, "edge {a}-{b} is shared by {faces} faces")
94            }
95            Self::InconsistentOrientation { from, to } => write!(
96                f,
97                "two faces traverse edge {from}->{to} in the same direction"
98            ),
99            Self::NonManifoldVertex { vertex } => {
100                write!(f, "vertex {vertex} joins more than one fan of faces")
101            }
102            Self::TooLarge => write!(f, "mesh exceeds 32-bit element ids"),
103        }
104    }
105}
106
107impl std::error::Error for HalfedgeBuildError {}
108
109/// One face corner's directed edge, sortable by its undirected key.
110#[derive(Clone, Copy)]
111struct Use {
112    lower: u32,
113    upper: u32,
114    from: u32,
115    to: u32,
116    corner: u32,
117}
118
119pub(super) fn build<F: AsRef<[u32]>>(
120    positions: Vec<Point3>,
121    faces: &[F],
122) -> Result<HalfedgeMesh, HalfedgeBuildError> {
123    let position_count = positions.len();
124    let corner_count: usize = faces.iter().map(|face| face.as_ref().len()).sum();
125    // Every corner contributes at most one edge, so `2 * corners` halfedges
126    // bounds the build; ids must stay below the `NONE` sentinel.
127    if position_count >= NONE as usize
128        || faces.len() >= NONE as usize
129        || corner_count.saturating_mul(2) >= NONE as usize
130    {
131        return Err(HalfedgeBuildError::TooLarge);
132    }
133
134    let mut face_start = Vec::with_capacity(faces.len() + 1);
135    let mut uses = Vec::with_capacity(corner_count);
136    let mut sorted = Vec::new();
137    for (face_index, face) in faces.iter().enumerate() {
138        let face = face.as_ref();
139        if face.len() < 3 {
140            return Err(HalfedgeBuildError::FaceTooSmall {
141                face: face_index,
142                corners: face.len(),
143            });
144        }
145        if let Some(&index) = face.iter().find(|&&i| i as usize >= position_count) {
146            return Err(HalfedgeBuildError::IndexOutOfRange {
147                face: face_index,
148                index,
149                position_count,
150            });
151        }
152        sorted.clear();
153        sorted.extend_from_slice(face);
154        sorted.sort_unstable();
155        if let Some(pair) = sorted.windows(2).find(|pair| pair[0] == pair[1]) {
156            return Err(HalfedgeBuildError::DegenerateFace {
157                face: face_index,
158                vertex: pair[0],
159            });
160        }
161        face_start.push(uses.len() as u32);
162        for (i, &from) in face.iter().enumerate() {
163            let to = face[(i + 1) % face.len()];
164            uses.push(Use {
165                lower: from.min(to),
166                upper: from.max(to),
167                from,
168                to,
169                corner: uses.len() as u32,
170            });
171        }
172    }
173    face_start.push(uses.len() as u32);
174
175    // Group corners by undirected edge; within a group, by corner so the
176    // first face to use an edge decides its halfedge `2e`.
177    let mut order = uses.clone();
178    order.sort_unstable_by_key(|u| (u.lower, u.upper, u.corner));
179
180    let mut corner_halfedge = vec![NONE; corner_count];
181    let mut links: Vec<Link> = Vec::with_capacity(corner_count * 2);
182    let mut group_start = 0;
183    while group_start < order.len() {
184        let first = order[group_start];
185        let mut group_end = group_start + 1;
186        while group_end < order.len()
187            && (order[group_end].lower, order[group_end].upper) == (first.lower, first.upper)
188        {
189            group_end += 1;
190        }
191        let group = &order[group_start..group_end];
192        if group.len() > 2 {
193            return Err(HalfedgeBuildError::NonManifoldEdge {
194                a: first.lower,
195                b: first.upper,
196                faces: group.len(),
197            });
198        }
199        if group.len() == 2 && group[1].from == first.from {
200            return Err(HalfedgeBuildError::InconsistentOrientation {
201                from: first.from,
202                to: first.to,
203            });
204        }
205        let h = links.len() as u32;
206        // Boundary until a face claims the side.
207        links.push(Link {
208            target: first.to,
209            ..super::DEAD_LINK
210        });
211        links.push(Link {
212            target: first.from,
213            ..super::DEAD_LINK
214        });
215        corner_halfedge[first.corner as usize] = h;
216        if let Some(second) = group.get(1) {
217            corner_halfedge[second.corner as usize] = h + 1;
218        }
219        group_start = group_end;
220    }
221
222    // Face loops.
223    let mut face_halfedge = Vec::with_capacity(faces.len());
224    for face in 0..faces.len() {
225        let start = face_start[face] as usize;
226        let end = face_start[face + 1] as usize;
227        let len = end - start;
228        for corner in start..end {
229            let h = corner_halfedge[corner] as usize;
230            let next = corner_halfedge[start + (corner - start + 1) % len];
231            let prev = corner_halfedge[start + (corner - start + len - 1) % len];
232            links[h].next = next;
233            links[h].prev = prev;
234            links[h].face = face as u32;
235        }
236        face_halfedge.push(corner_halfedge[start]);
237    }
238
239    // Boundary loops: each vertex may leave by at most one boundary halfedge.
240    let mut vertex_out = vec![NONE; position_count];
241    let mut boundary_out = vec![NONE; position_count];
242    let mut out_count = vec![0u32; position_count];
243    for h in 0..links.len() {
244        let source = links[h ^ 1].target as usize;
245        out_count[source] += 1;
246        if links[h].face == NONE {
247            if boundary_out[source] != NONE {
248                return Err(HalfedgeBuildError::NonManifoldVertex {
249                    vertex: source as u32,
250                });
251            }
252            boundary_out[source] = h as u32;
253        }
254        if vertex_out[source] == NONE {
255            vertex_out[source] = h as u32;
256        }
257    }
258    for h in 0..links.len() {
259        if links[h].face == NONE {
260            // A vertex has as many incoming as outgoing boundary halfedges,
261            // so the target of a boundary halfedge always leaves by one.
262            let next = boundary_out[links[h].target as usize];
263            links[h].next = next;
264            links[next as usize].prev = h as u32;
265        }
266    }
267    for v in 0..position_count {
268        if boundary_out[v] != NONE {
269            vertex_out[v] = boundary_out[v];
270        }
271    }
272
273    let edge_count = links.len() / 2;
274    let mesh = HalfedgeMesh {
275        positions,
276        vertex_live: vec![true; position_count],
277        vertex_out,
278        edge_live: vec![true; edge_count],
279        links,
280        face_live: vec![true; face_halfedge.len()],
281        live_faces: face_halfedge.len(),
282        face_halfedge,
283        live_vertices: position_count,
284        live_edges: edge_count,
285    };
286
287    // A manifold vertex's outgoing halfedges form one rotation orbit.
288    for (v, &count) in out_count.iter().enumerate() {
289        if count == 0 {
290            continue;
291        }
292        let orbit = mesh.outgoing_halfedges(VertexId(v as u32)).count() as u32;
293        if orbit != count {
294            return Err(HalfedgeBuildError::NonManifoldVertex { vertex: v as u32 });
295        }
296    }
297    debug_assert!(mesh.validate().is_ok(), "{:?}", mesh.validate());
298    Ok(mesh)
299}
axiolid_mesh/halfedge/build.rs

axiolid_mesh/halfedge/
build.rs
