honeycomb_kernels/remeshing/
collapse.rs

1use honeycomb_core::{
2    attributes::{AttributeError, AttributeUpdate},
3    cmap::{
4        CMap2, DartIdType, EdgeIdType, LinkError, NULL_DART_ID, NULL_EDGE_ID, NULL_VERTEX_ID,
5        SewError, VertexIdType,
6    },
7    geometry::CoordsFloat,
8    stm::{Transaction, TransactionClosureResult, abort, retry, try_or_coerce},
9};
10
11use crate::utils::{EdgeAnchor, VertexAnchor, is_orbit_orientation_consistent};
12
13/// Error-modeling enum for edge collapse routine.
14#[derive(thiserror::Error, Debug, PartialEq, Eq)]
15pub enum EdgeCollapseError {
16    /// A core operation failed.
17    #[error("core operation failed: {0}")]
18    FailedCoreOp(#[from] SewError),
19    /// The edge passed as argument cannot be collapsed due to constraints on its vertices.
20    #[error("cannot collapse edge: {0}")]
21    NonCollapsibleEdge(&'static str),
22    /// The structure after collapse contains a triangle with inverted orientation, making the
23    /// geometry invalid.
24    #[error("collapsing would result in an inversion of geometry orientation")]
25    InvertedOrientation,
26    /// The edge passed as argument is null.
27    #[error("cannot collapse null edge")]
28    NullEdge,
29    /// One or both of the cells adjacent to the edge are not triangles.
30    #[error("cannot collapse an edge adjacent to a non-triangular cell")]
31    BadTopology,
32}
33
34impl From<LinkError> for EdgeCollapseError {
35    fn from(value: LinkError) -> Self {
36        Self::FailedCoreOp(SewError::FailedLink(value))
37    }
38}
39
40#[allow(clippy::missing_errors_doc)]
41/// Collapse an edge separating two triangles.
42///
43/// ```text
44/// +-----+-----+       +-----+-----+
45/// |    / \    |        \    |    /
46/// |   /   \   |         \  2-3  /
47/// 1  2     3  4          1  |  4
48/// | /       \ |           \ | /
49/// |/         \|            \|/
50/// +-----------+  -->        +
51/// |\    e    /|            /|\
52/// | \       / |           / | \
53/// 5  6     7  8          5  |  8
54/// |   \   /   |         /  6-7  \
55/// |    \ /    |        /    |    \
56/// +-----+-----+       +-----+-----+
57/// ```
58///
59/// This function expects to operate on a triangular mesh. The edge may be collapsed to one of
60/// the existing vertices, or to the average of their value; this is determined by the anchoring
61/// of the mesh to its geometry. If no anchoring attributes are present, the edge is always
62/// collapsed to the average value.
63///
64/// # Arguments
65///
66/// - `t: &mut Transaction` -- Associated transaction.
67/// - `map: &mut CMap2` -- Edited map.
68/// - `e: EdgeIdType` -- Edge to move.
69///
70/// # Return / Errors
71///
72/// Upon success, this function will return the ID of the new vertex formed after the collapse.
73/// Depending on the anchoring constraints, it may be placed on one of the two previously existing
74/// vertex, or to their average value.
75///
76/// This function will abort and raise an error if:
77/// - the transaction cannot be completed,
78/// - one internal sew operation fails,
79/// - the collapse cannot be completed; see [`EdgeCollapseError`] for more information.
80///
81/// The returned error can be used in conjunction with transaction control to avoid any
82/// modifications in case of failure at attribute level. The user can then choose to retry or
83/// abort as he wishes using `Transaction::with_control_and_err`.
84///
85/// <div class="warning">
86/// Note that the function will return `StmError::Retry` if it attempts to read a missing vertex.
87/// If used within a transaction which retries indefinitely (e.g. `atomically_with_err`), it can
88/// lead to an infinite loop.
89///
90/// This will not happen unless the map ends up in an incorrect state where topological vertices
91/// have no associated coordinates.
92/// </div>
93#[allow(clippy::many_single_char_names)]
94pub fn collapse_edge<T: CoordsFloat>(
95    t: &mut Transaction,
96    map: &CMap2<T>,
97    e: EdgeIdType,
98) -> TransactionClosureResult<VertexIdType, EdgeCollapseError> {
99    if e == NULL_EDGE_ID {
100        abort(EdgeCollapseError::NullEdge)?;
101    }
102    let (l, r) = (e as DartIdType, map.beta_transac::<2>(t, e as DartIdType)?);
103    let (b0l, b1l) = (map.beta_transac::<0>(t, l)?, map.beta_transac::<1>(t, l)?);
104    let (b0r, b1r) = (map.beta_transac::<0>(t, r)?, map.beta_transac::<1>(t, r)?);
105
106    if map.beta_transac::<1>(t, b1l)? != b0l {
107        abort(EdgeCollapseError::BadTopology)?;
108    }
109    if r != NULL_DART_ID && map.beta_transac::<1>(t, b1r)? != b0r {
110        abort(EdgeCollapseError::BadTopology)?;
111    }
112
113    let new_vid = match is_collapsible(t, map, e)? {
114        Collapsible::Average => try_or_coerce!(
115            collapse_edge_to_midpoint(t, map, (b0l, l, b1l), (b0r, r, b1r)),
116            EdgeCollapseError
117        ),
118        Collapsible::Left => try_or_coerce!(
119            collapse_edge_to_base(t, map, (b0l, l, b1l), (b0r, r, b1r)),
120            EdgeCollapseError
121        ),
122        Collapsible::Right => try_or_coerce!(
123            collapse_edge_to_base(t, map, (b0r, r, b1r), (b0l, l, b1l)),
124            EdgeCollapseError
125        ),
126    };
127
128    if !is_orbit_orientation_consistent(t, map, new_vid)? {
129        abort(EdgeCollapseError::InvertedOrientation)?;
130    }
131
132    Ok(new_vid)
133}
134
135// -- internals
136
137// ---- collapse criteria
138
139enum Collapsible {
140    Average,
141    Left,
142    Right,
143}
144
145fn is_collapsible<T: CoordsFloat>(
146    t: &mut Transaction,
147    map: &CMap2<T>,
148    e: EdgeIdType,
149) -> TransactionClosureResult<Collapsible, EdgeCollapseError> {
150    if !map.contains_attribute::<VertexAnchor>() {
151        // if there are no anchors, we'll assume we can naively collapse
152        return Ok(Collapsible::Average);
153    }
154    let (l, b1l) = (e as DartIdType, map.beta_transac::<1>(t, e as DartIdType)?);
155
156    // first check anchor predicates
157
158    let (l_vid, r_vid) = (map.vertex_id_transac(t, l)?, map.vertex_id_transac(t, b1l)?);
159    let (l_anchor, r_anchor, edge_anchor) = if let (Some(a1), Some(a2), Some(a3)) = (
160        map.read_attribute::<VertexAnchor>(t, l_vid)?,
161        map.read_attribute::<VertexAnchor>(t, r_vid)?,
162        map.read_attribute::<EdgeAnchor>(t, e)?,
163    ) {
164        (a1, a2, a3)
165    } else {
166        retry()?
167    };
168
169    match AttributeUpdate::merge(l_anchor, r_anchor) {
170        Ok(val) => {
171            // check ID too? did other checks filter that out already?
172            // does having different IDs here mean the classification is bad?
173            if edge_anchor.anchor_dim() == l_anchor.anchor_dim()
174                || edge_anchor.anchor_dim() == r_anchor.anchor_dim()
175            {
176                match (val == l_anchor, val == r_anchor) {
177                    (true, true) => Ok(Collapsible::Average),
178                    (true, false) => Ok(Collapsible::Left),
179                    (false, true) => Ok(Collapsible::Right),
180                    (false, false) => unreachable!(),
181                }
182            } else {
183                abort(EdgeCollapseError::NonCollapsibleEdge(
184                    "collapsing along this edge is impossible",
185                ))
186            }
187        }
188        Err(AttributeError::FailedMerge(_, _)) => abort(EdgeCollapseError::NonCollapsibleEdge(
189            "vertex have incompatible anchors",
190        )),
191        Err(AttributeError::FailedSplit(_, _) | AttributeError::InsufficientData(_, _)) => {
192            unreachable!();
193        }
194    }
195}
196
197// ---- midpoint collapse
198
199fn collapse_edge_to_midpoint<T: CoordsFloat>(
200    t: &mut Transaction,
201    map: &CMap2<T>,
202    (b0l, l, b1l): (DartIdType, DartIdType, DartIdType),
203    (b0r, r, b1r): (DartIdType, DartIdType, DartIdType),
204) -> TransactionClosureResult<VertexIdType, SewError> {
205    if r != NULL_DART_ID {
206        map.unsew::<2>(t, r)?;
207        collapse_halfcell_to_midpoint(t, map, (b0r, r, b1r))?;
208    }
209    // by this point l is 2-free, whether he was at the beginning or due to the 2-unsew
210    let b2b0l = map.beta_transac::<2>(t, b0l)?; // save this before left cell collapse
211    collapse_halfcell_to_midpoint(t, map, (b0l, l, b1l))?;
212
213    Ok(if b2b0l != NULL_DART_ID {
214        map.vertex_id_transac(t, b2b0l)?
215    } else if r != NULL_DART_ID {
216        map.vertex_id_transac(t, b1r)?
217    } else {
218        // this can happen from a valid configuration, so we handle it
219        NULL_VERTEX_ID
220    })
221}
222
223fn collapse_halfcell_to_midpoint<T: CoordsFloat>(
224    t: &mut Transaction,
225    map: &CMap2<T>,
226    (b0d, d, b1d): (DartIdType, DartIdType, DartIdType),
227) -> TransactionClosureResult<(), SewError> {
228    map.unsew::<1>(t, d)?;
229    map.unsew::<1>(t, b1d)?;
230    map.unsew::<1>(t, b0d)?;
231    let (b2b0d, b2b1d) = (
232        map.beta_transac::<2>(t, b0d)?,
233        map.beta_transac::<2>(t, b1d)?,
234    );
235    map.unsew::<2>(t, b0d)?;
236    map.unsew::<2>(t, b1d)?;
237    map.sew::<2>(t, b2b0d, b2b1d)?;
238    map.remove_free_dart_transac(t, d)?;
239    map.remove_free_dart_transac(t, b0d)?;
240    map.remove_free_dart_transac(t, b1d)?;
241    TransactionClosureResult::Ok(())
242}
243
244// ---- base collapse
245
246fn collapse_edge_to_base<T: CoordsFloat>(
247    t: &mut Transaction,
248    map: &CMap2<T>,
249    (b0l, l, b1l): (DartIdType, DartIdType, DartIdType), // base == l
250    (b0r, r, b1r): (DartIdType, DartIdType, DartIdType),
251) -> TransactionClosureResult<VertexIdType, EdgeCollapseError> {
252    // reading/writing the coordinates to collapse to is easier to handle split/merges correctly
253    let l_vid = map.vertex_id_transac(t, l)?;
254    let tmp_vertex = map.read_vertex(t, l_vid)?;
255    let tmp_anchor = map.read_attribute::<VertexAnchor>(t, l_vid)?;
256
257    if r != NULL_DART_ID {
258        try_or_coerce!(map.unsew::<2>(t, l), EdgeCollapseError);
259        try_or_coerce!(
260            collapse_halfcell_to_base(t, map, (b1r, r, b0r)),
261            EdgeCollapseError
262        );
263    }
264    // by this point l is 2-free, whether he was at the beginning or due to the 2-unsew
265    let b2b0l = map.beta_transac::<2>(t, b0l)?; // save this before left cell collapse
266    try_or_coerce!(
267        collapse_halfcell_to_base(t, map, (b0l, l, b1l)),
268        EdgeCollapseError
269    );
270
271    let new_vid = if b2b0l != NULL_DART_ID {
272        map.vertex_id_transac(t, b2b0l)?
273    } else if r != NULL_DART_ID {
274        map.vertex_id_transac(t, b1r)?
275    } else {
276        // this can happen from a valid configuration, so we handle it
277        NULL_VERTEX_ID
278    };
279
280    if new_vid != NULL_VERTEX_ID {
281        if let Some(v) = tmp_vertex {
282            map.write_vertex(t, new_vid, v)?;
283        } // else eprintln! ?
284        if let Some(a) = tmp_anchor {
285            map.write_attribute(t, new_vid, a)?;
286        }
287    }
288
289    Ok(new_vid)
290}
291
292fn collapse_halfcell_to_base<T: CoordsFloat>(
293    t: &mut Transaction,
294    map: &CMap2<T>,
295    // d_previous_edge, d_edge, d_next_edge
296    (d_pe, d_e, d_ne): (DartIdType, DartIdType, DartIdType),
297) -> TransactionClosureResult<(), SewError> {
298    let b2d_ne = map.beta_transac::<2>(t, d_ne)?;
299    let b0b2d_ne = map.beta_transac::<0>(t, b2d_ne)?;
300    let b1b2d_ne = map.beta_transac::<1>(t, b2d_ne)?;
301
302    map.unsew::<1>(t, d_e)?;
303    map.unsew::<1>(t, d_pe)?;
304    map.unsew::<1>(t, d_ne)?;
305    if b2d_ne != NULL_DART_ID {
306        map.unsew::<1>(t, b2d_ne)?;
307        map.unsew::<1>(t, b0b2d_ne)?;
308        try_or_coerce!(map.unlink::<2>(t, d_ne), SewError);
309        map.remove_free_dart_transac(t, d_e)?;
310        map.remove_free_dart_transac(t, d_ne)?;
311        map.remove_free_dart_transac(t, b2d_ne)?;
312        map.sew::<1>(t, d_pe, b1b2d_ne)?;
313        map.sew::<1>(t, b0b2d_ne, d_pe)?;
314    }
315
316    Ok(())
317}
honeycomb_kernels/remeshing/collapse.rs

honeycomb_kernels/remeshing/
collapse.rs
