honeycomb_kernels/remeshing/
collapse.rs

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

honeycomb_kernels/remeshing/
collapse.rs
