axiolid_mesh/halfedge/
edit.rs

1//! Local connectivity edits. Each one checks its preconditions before
2//! touching anything, so a refused edit leaves the mesh exactly as it was,
3//! and an accepted one leaves every invariant intact.
4
5use core::fmt;
6
7use axiolid_core::Point3;
8
9use super::{EdgeId, FaceId, HalfedgeId, HalfedgeMesh, Link, VertexId, DEAD_LINK, NONE};
10
11/// Why a local edit or a conversion was refused.
12#[non_exhaustive]
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub enum HalfedgeEditError {
15    /// The id names an element that was removed or never existed.
16    RemovedElement {
17        /// `"vertex"`, `"halfedge"`, `"edge"` or `"face"`.
18        element: &'static str,
19        /// The id.
20        index: u32,
21    },
22    /// The edit needs a face on both sides of the edge.
23    BoundaryEdge {
24        /// The edge.
25        edge: EdgeId,
26    },
27    /// The edit needs a triangle here.
28    NotATriangle {
29        /// The face.
30        face: FaceId,
31        /// Its number of sides.
32        degree: usize,
33    },
34    /// The edit would add an edge between vertices already joined, making
35    /// the mesh non-simple.
36    EdgeExists {
37        /// One endpoint.
38        a: VertexId,
39        /// The other endpoint.
40        b: VertexId,
41    },
42    /// Collapsing the edge would pinch the surface: its endpoints share a
43    /// neighbour that is not opposite the edge, or both lie on a boundary the
44    /// edge does not run along (Dey et al.'s link condition).
45    LinkCondition {
46        /// The edge.
47        edge: EdgeId,
48    },
49    /// The edit would leave a degenerate surface: collapsing an edge of a
50    /// tetrahedron, of a lone triangle or of a two-triangle pillow, or
51    /// flipping an edge whose two opposite corners coincide.
52    WouldDegenerate {
53        /// The edge.
54        edge: EdgeId,
55    },
56    /// The halfedge has a face; filling needs a boundary halfedge.
57    NotBoundary {
58        /// The halfedge.
59        halfedge: HalfedgeId,
60    },
61    /// The two halfedges do not lie on the same face.
62    NotSameFace {
63        /// First halfedge.
64        a: HalfedgeId,
65        /// Second halfedge.
66        b: HalfedgeId,
67    },
68    /// The two corners are the same or already joined by a side of the face.
69    AdjacentCorners {
70        /// First halfedge.
71        a: HalfedgeId,
72        /// Second halfedge.
73        b: HalfedgeId,
74    },
75    /// The edit needs more elements than 32-bit ids can address.
76    TooLarge,
77}
78
79impl fmt::Display for HalfedgeEditError {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        match self {
82            Self::RemovedElement { element, index } => {
83                write!(f, "{element} {index} is not a live element")
84            }
85            Self::BoundaryEdge { edge } => write!(f, "edge {edge} lies on a boundary"),
86            Self::NotATriangle { face, degree } => {
87                write!(f, "face {face} has {degree} sides, not three")
88            }
89            Self::EdgeExists { a, b } => write!(f, "vertices {a} and {b} are already joined"),
90            Self::LinkCondition { edge } => {
91                write!(f, "collapsing edge {edge} violates the link condition")
92            }
93            Self::WouldDegenerate { edge } => {
94                write!(f, "editing edge {edge} would leave a degenerate surface")
95            }
96            Self::NotBoundary { halfedge } => {
97                write!(f, "halfedge {halfedge} is not a boundary halfedge")
98            }
99            Self::NotSameFace { a, b } => {
100                write!(f, "halfedges {a} and {b} lie on different faces")
101            }
102            Self::AdjacentCorners { a, b } => write!(
103                f,
104                "the targets of halfedges {a} and {b} are already joined by a side"
105            ),
106            Self::TooLarge => write!(f, "mesh exceeds 32-bit element ids"),
107        }
108    }
109}
110
111impl std::error::Error for HalfedgeEditError {}
112
113type EditResult<T> = Result<T, HalfedgeEditError>;
114
115impl HalfedgeMesh {
116    /// Replace an edge between two triangles by the other diagonal of the
117    /// quadrilateral they form. Counts, and so the Euler characteristic, are
118    /// unchanged; the edge keeps its id.
119    ///
120    /// # Errors
121    ///
122    /// [`HalfedgeEditError::BoundaryEdge`], [`HalfedgeEditError::NotATriangle`],
123    /// [`HalfedgeEditError::WouldDegenerate`] when the two opposite corners are
124    /// one vertex, and [`HalfedgeEditError::EdgeExists`] when they are already
125    /// joined.
126    pub fn flip_edge(&mut self, e: EdgeId) -> EditResult<()> {
127        self.require_edge(e)?;
128        let h = e.0 * 2;
129        let o = h + 1;
130        let (f1, f2) = (self.links[h as usize].face, self.links[o as usize].face);
131        if f1 == NONE || f2 == NONE {
132            return Err(HalfedgeEditError::BoundaryEdge { edge: e });
133        }
134        self.require_triangle(FaceId(f1))?;
135        self.require_triangle(FaceId(f2))?;
136        let (hn, hp) = (self.links[h as usize].next, self.links[h as usize].prev);
137        let (on, op) = (self.links[o as usize].next, self.links[o as usize].prev);
138        let a = self.links[o as usize].target;
139        let b = self.links[h as usize].target;
140        let c = self.links[hn as usize].target;
141        let d = self.links[on as usize].target;
142        if c == d {
143            return Err(HalfedgeEditError::WouldDegenerate { edge: e });
144        }
145        if self.find_halfedge(VertexId(c), VertexId(d)).is_some() {
146            return Err(HalfedgeEditError::EdgeExists {
147                a: VertexId(c),
148                b: VertexId(d),
149            });
150        }
151
152        // Quad a -> d -> b -> c; new diagonal h: d -> c, o: c -> d.
153        self.link(hp, on);
154        self.link(on, h);
155        self.link(h, hp);
156        self.link(op, hn);
157        self.link(hn, o);
158        self.link(o, op);
159        self.links[h as usize].target = c;
160        self.links[o as usize].target = d;
161        self.links[on as usize].face = f1;
162        self.links[hn as usize].face = f2;
163        self.face_halfedge[f1 as usize] = h;
164        self.face_halfedge[f2 as usize] = o;
165        if self.vertex_out[a as usize] == h {
166            self.vertex_out[a as usize] = on;
167        }
168        if self.vertex_out[b as usize] == o {
169            self.vertex_out[b as usize] = hn;
170        }
171        Ok(())
172    }
173
174    /// Insert a vertex at `position` on an edge and join it to the opposite
175    /// corner of each adjacent triangle, so a triangle mesh stays a triangle
176    /// mesh. A non-triangular adjacent face just gains a side. The Euler
177    /// characteristic is unchanged.
178    ///
179    /// The old edge keeps its id and runs from its original source to the
180    /// new vertex.
181    ///
182    /// # Errors
183    ///
184    /// [`HalfedgeEditError::RemovedElement`] and [`HalfedgeEditError::TooLarge`].
185    pub fn split_edge(&mut self, e: EdgeId, position: Point3) -> EditResult<VertexId> {
186        self.require_edge(e)?;
187        self.require_room(1, 3, 2)?;
188        let h = e.0 * 2;
189        let o = h + 1;
190        let fh = self.links[h as usize].face;
191        let fo = self.links[o as usize].face;
192        let split_h = fh != NONE && self.face_degree(FaceId(fh)) == 3;
193        let split_o = fo != NONE && self.face_degree(FaceId(fo)) == 3;
194        let b = self.links[h as usize].target;
195        let hn = self.links[h as usize].next;
196        let op = self.links[o as usize].prev;
197
198        let m = self.new_vertex(position);
199        let g = self.new_edge(m, b);
200        // h: a -> m, g: m -> b on h's side; g^1: b -> m, o: m -> a on o's side.
201        self.links[h as usize].target = m;
202        self.link(h, g);
203        self.link(g, hn);
204        self.links[g as usize].face = fh;
205        self.link(op, g ^ 1);
206        self.link(g ^ 1, o);
207        self.links[(g ^ 1) as usize].face = fo;
208        self.vertex_out[m as usize] = if fo == NONE { o } else { g };
209        if self.vertex_out[b as usize] == o {
210            self.vertex_out[b as usize] = g ^ 1;
211        }
212        if split_h {
213            self.insert_diagonal(h, hn);
214        }
215        if split_o {
216            let on = self.links[o as usize].next;
217            self.insert_diagonal(g ^ 1, on);
218        }
219        Ok(VertexId(m))
220    }
221
222    /// Collapse halfedge `h` by merging its source into its target, which
223    /// keeps its id and position (move it with
224    /// [`HalfedgeMesh::set_position`]). The incident triangles disappear and
225    /// their remaining sides merge pairwise. Removes one vertex, three edges
226    /// on an interior edge (two on a boundary edge) and the adjacent faces,
227    /// so the Euler characteristic is unchanged.
228    ///
229    /// # Errors
230    ///
231    /// [`HalfedgeEditError::NotATriangle`] when a face around the removed
232    /// vertex is not a triangle, [`HalfedgeEditError::LinkCondition`] when the
233    /// collapse would pinch the surface, and
234    /// [`HalfedgeEditError::WouldDegenerate`] for a tetrahedron, a lone
235    /// triangle or a two-triangle pillow.
236    pub fn collapse_edge(&mut self, h: HalfedgeId) -> EditResult<VertexId> {
237        self.require_edge(self.edge(h))?;
238        let edge = self.edge(h);
239        let h = h.0;
240        let o = h ^ 1;
241        let a = VertexId(self.links[o as usize].target);
242        let b = VertexId(self.links[h as usize].target);
243        let fh = self.links[h as usize].face;
244        let fo = self.links[o as usize].face;
245        for f in self.vertex_faces(a) {
246            self.require_triangle(f)?;
247        }
248        let opposite_corner = |mesh: &Self, side: u32| {
249            (mesh.links[side as usize].face != NONE)
250                .then(|| VertexId(mesh.links[mesh.links[side as usize].next as usize].target))
251        };
252        let c = opposite_corner(self, h);
253        let d = opposite_corner(self, o);
254        if c.is_some() && c == d {
255            return Err(HalfedgeEditError::WouldDegenerate { edge });
256        }
257
258        // Link condition: every common neighbour is a corner opposite the
259        // edge, and the boundary (a virtual vertex joined to every boundary
260        // vertex) is a common neighbour only when the edge runs along it.
261        let around_a: Vec<VertexId> = self.vertex_vertices(a).collect();
262        if self
263            .vertex_vertices(b)
264            .any(|n| n != a && around_a.contains(&n) && Some(n) != c && Some(n) != d)
265        {
266            return Err(HalfedgeEditError::LinkCondition { edge });
267        }
268        if self.is_boundary_vertex(a) && self.is_boundary_vertex(b) && !self.is_boundary_edge(edge)
269        {
270            return Err(HalfedgeEditError::LinkCondition { edge });
271        }
272        // The link condition holds on the boundary of a tetrahedron, which
273        // still collapses to nothing; with the boundary as a virtual vertex,
274        // a lone triangle is that case too.
275        match (c, d) {
276            (Some(c), Some(d)) => {
277                if [a, b, c, d]
278                    .iter()
279                    .all(|&v| !self.is_boundary_vertex(v) && self.degree(v) == 3)
280                {
281                    return Err(HalfedgeEditError::WouldDegenerate { edge });
282                }
283            }
284            _ => {
285                let hole = if fh == NONE { h } else { o };
286                if self.loop_halfedges(HalfedgeId(hole)).count() == 3 {
287                    return Err(HalfedgeEditError::WouldDegenerate { edge });
288                }
289            }
290        }
291
292        let incoming: Vec<u32> = self.incoming_halfedges(a).map(|g| g.0).collect();
293        let (hn, hp) = (self.links[h as usize].next, self.links[h as usize].prev);
294        let (on, op) = (self.links[o as usize].next, self.links[o as usize].prev);
295        for g in incoming {
296            self.links[g as usize].target = b.0;
297        }
298        self.link(hp, hn);
299        self.link(op, on);
300        if self.vertex_out[b.index()] == o {
301            self.vertex_out[b.index()] = hn;
302        }
303        if fh != NONE {
304            self.remove_loop(hn);
305        }
306        if fo != NONE {
307            self.remove_loop(on);
308        }
309        self.remove_edge(edge.0);
310        self.remove_vertex(a.0);
311        for v in [Some(b), c, d].into_iter().flatten() {
312            self.adjust_outgoing(v.0);
313        }
314        Ok(b)
315    }
316
317    /// Insert a vertex at `position` inside a face and fan the face into
318    /// triangles around it, one per side. The face keeps its id as the
319    /// triangle on its stored halfedge. The Euler characteristic is
320    /// unchanged.
321    ///
322    /// # Errors
323    ///
324    /// [`HalfedgeEditError::RemovedElement`] and [`HalfedgeEditError::TooLarge`].
325    pub fn split_face(&mut self, f: FaceId, position: Point3) -> EditResult<VertexId> {
326        self.require_face(f)?;
327        let sides: Vec<u32> = self.face_halfedges(f).map(|h| h.0).collect();
328        let n = sides.len();
329        self.require_room(1, n, n)?;
330        let center = self.new_vertex(position);
331        // spoke[i]: center -> source(sides[i]); spoke[i] ^ 1 runs back.
332        let spokes: Vec<u32> = sides
333            .iter()
334            .map(|&h| {
335                let corner = self.links[(h ^ 1) as usize].target;
336                self.new_edge(center, corner)
337            })
338            .collect();
339        for i in 0..n {
340            let side = sides[i];
341            let up = spokes[(i + 1) % n] ^ 1;
342            let down = spokes[i];
343            let face = if i == 0 { f.0 } else { self.new_face(side) };
344            self.link(side, up);
345            self.link(up, down);
346            self.link(down, side);
347            for g in [side, up, down] {
348                self.links[g as usize].face = face;
349            }
350        }
351        self.face_halfedge[f.index()] = sides[0];
352        self.vertex_out[center as usize] = spokes[0];
353        Ok(VertexId(center))
354    }
355
356    /// Split a face by a new edge from `target(a)` to `target(b)`, two
357    /// corners of the same face that are not already joined. Returns the new
358    /// halfedge running from `target(a)` to `target(b)`; it stays on the
359    /// original face, which keeps `a`, and the other part becomes a new
360    /// face. The Euler characteristic is unchanged.
361    ///
362    /// This triangulates a polygon one diagonal at a time, for example a
363    /// hole closed with [`HalfedgeMesh::fill_hole`].
364    ///
365    /// # Errors
366    ///
367    /// [`HalfedgeEditError::NotSameFace`] (boundary halfedges included),
368    /// [`HalfedgeEditError::AdjacentCorners`], and
369    /// [`HalfedgeEditError::EdgeExists`] when the corners are joined through
370    /// another face.
371    pub fn split_face_diagonal(&mut self, a: HalfedgeId, b: HalfedgeId) -> EditResult<HalfedgeId> {
372        self.require_edge(self.edge(a))?;
373        self.require_edge(self.edge(b))?;
374        let face = self.links[a.index()].face;
375        if face == NONE || self.links[b.index()].face != face {
376            return Err(HalfedgeEditError::NotSameFace { a, b });
377        }
378        if a == b || self.next(a) == b || self.next(b) == a {
379            return Err(HalfedgeEditError::AdjacentCorners { a, b });
380        }
381        let (u, w) = (self.target(a), self.target(b));
382        if self.find_halfedge(u, w).is_some() {
383            return Err(HalfedgeEditError::EdgeExists { a: u, b: w });
384        }
385        self.require_room(0, 1, 1)?;
386        Ok(HalfedgeId(self.insert_diagonal(a.0, b.0)))
387    }
388
389    /// Close the hole bounded by boundary halfedge `h` with one new face.
390    /// The Euler characteristic rises by one.
391    ///
392    /// # Errors
393    ///
394    /// [`HalfedgeEditError::NotBoundary`] when `h` already has a face.
395    pub fn fill_hole(&mut self, h: HalfedgeId) -> EditResult<FaceId> {
396        self.require_edge(self.edge(h))?;
397        if !self.is_boundary_halfedge(h) {
398            return Err(HalfedgeEditError::NotBoundary { halfedge: h });
399        }
400        self.require_room(0, 0, 1)?;
401        let face = self.new_face(h.0);
402        let sides: Vec<HalfedgeId> = self.loop_halfedges(h).collect();
403        for g in sides {
404            self.links[g.index()].face = face;
405        }
406        Ok(FaceId(face))
407    }
408
409    // ---- preconditions ----------------------------------------------------
410
411    fn require_edge(&self, e: EdgeId) -> EditResult<()> {
412        if self.contains_edge(e) {
413            Ok(())
414        } else {
415            Err(HalfedgeEditError::RemovedElement {
416                element: "edge",
417                index: e.0,
418            })
419        }
420    }
421
422    fn require_face(&self, f: FaceId) -> EditResult<()> {
423        if self.contains_face(f) {
424            Ok(())
425        } else {
426            Err(HalfedgeEditError::RemovedElement {
427                element: "face",
428                index: f.0,
429            })
430        }
431    }
432
433    fn require_triangle(&self, f: FaceId) -> EditResult<()> {
434        let degree = self.face_degree(f);
435        if degree == 3 {
436            Ok(())
437        } else {
438            Err(HalfedgeEditError::NotATriangle { face: f, degree })
439        }
440    }
441
442    fn require_room(&self, vertices: usize, edges: usize, faces: usize) -> EditResult<()> {
443        let limit = NONE as usize;
444        if self.positions.len() + vertices >= limit
445            || (self.edge_live.len() + edges) * 2 >= limit
446            || self.face_live.len() + faces >= limit
447        {
448            Err(HalfedgeEditError::TooLarge)
449        } else {
450            Ok(())
451        }
452    }
453
454    // ---- primitive mutations ----------------------------------------------
455
456    fn new_vertex(&mut self, position: Point3) -> u32 {
457        self.positions.push(position);
458        self.vertex_out.push(NONE);
459        self.vertex_live.push(true);
460        self.live_vertices += 1;
461        (self.positions.len() - 1) as u32
462    }
463
464    /// New edge with dangling links; returns the halfedge `from -> to`.
465    fn new_edge(&mut self, from: u32, to: u32) -> u32 {
466        let h = self.links.len() as u32;
467        self.links.push(Link {
468            target: to,
469            ..DEAD_LINK
470        });
471        self.links.push(Link {
472            target: from,
473            ..DEAD_LINK
474        });
475        self.edge_live.push(true);
476        self.live_edges += 1;
477        h
478    }
479
480    fn new_face(&mut self, h: u32) -> u32 {
481        self.face_halfedge.push(h);
482        self.face_live.push(true);
483        self.live_faces += 1;
484        (self.face_halfedge.len() - 1) as u32
485    }
486
487    fn remove_vertex(&mut self, v: u32) {
488        self.vertex_live[v as usize] = false;
489        self.vertex_out[v as usize] = NONE;
490        self.live_vertices -= 1;
491    }
492
493    fn remove_edge(&mut self, e: u32) {
494        self.edge_live[e as usize] = false;
495        self.links[(e * 2) as usize] = DEAD_LINK;
496        self.links[(e * 2 + 1) as usize] = DEAD_LINK;
497        self.live_edges -= 1;
498    }
499
500    fn remove_face(&mut self, f: u32) {
501        self.face_live[f as usize] = false;
502        self.face_halfedge[f as usize] = NONE;
503        self.live_faces -= 1;
504    }
505
506    /// Join `target(h1)` to `target(h2)` across their shared face. The face
507    /// keeps `h1` and the new halfedge; the other part becomes a new face.
508    fn insert_diagonal(&mut self, h1: u32, h2: u32) -> u32 {
509        let face = self.links[h1 as usize].face;
510        let u = self.links[h1 as usize].target;
511        let w = self.links[h2 as usize].target;
512        let n1 = self.links[h1 as usize].next;
513        let n2 = self.links[h2 as usize].next;
514        let d = self.new_edge(u, w);
515        self.link(h1, d);
516        self.link(d, n2);
517        self.links[d as usize].face = face;
518        self.link(h2, d ^ 1);
519        self.link(d ^ 1, n1);
520        let other = self.new_face(d ^ 1);
521        let sides: Vec<HalfedgeId> = self.loop_halfedges(HalfedgeId(d ^ 1)).collect();
522        for g in sides {
523            self.links[g.index()].face = other;
524        }
525        self.face_halfedge[face as usize] = h1;
526        d
527    }
528
529    /// Dissolve a two-sided loop `h0 -> h1 -> h0` left by a collapse: `h0`
530    /// takes the place of `opposite(h1)`, whose edge and the loop's face are
531    /// removed, so the two sides merge into `h0`'s edge.
532    fn remove_loop(&mut self, h0: u32) {
533        let h1 = self.links[h0 as usize].next;
534        debug_assert_eq!(self.links[h1 as usize].next, h0);
535        let o0 = h0 ^ 1;
536        let o1 = h1 ^ 1;
537        let face = self.links[h0 as usize].face;
538        let v0 = self.links[h0 as usize].target;
539        let v1 = self.links[h1 as usize].target;
540        let Link {
541            prev,
542            next,
543            face: outer,
544            ..
545        } = self.links[o1 as usize];
546        self.link(prev, h0);
547        self.link(h0, next);
548        self.links[h0 as usize].face = outer;
549        if outer != NONE && self.face_halfedge[outer as usize] == o1 {
550            self.face_halfedge[outer as usize] = h0;
551        }
552        if self.vertex_out[v0 as usize] == h1 {
553            self.vertex_out[v0 as usize] = o0;
554        }
555        if self.vertex_out[v1 as usize] == o1 {
556            self.vertex_out[v1 as usize] = h0;
557        }
558        self.remove_face(face);
559        self.remove_edge(h1 / 2);
560    }
561
562    /// Restore the rule that a boundary vertex stores its boundary halfedge.
563    fn adjust_outgoing(&mut self, v: u32) {
564        if self.vertex_out[v as usize] == NONE {
565            return;
566        }
567        let boundary = self
568            .outgoing_halfedges(VertexId(v))
569            .find(|&h| self.is_boundary_halfedge(h));
570        if let Some(h) = boundary {
571            self.vertex_out[v as usize] = h.0;
572        }
573    }
574}
axiolid_mesh/halfedge/edit.rs

axiolid_mesh/halfedge/
edit.rs
