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, retry, try_or_coerce},
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) = if let (Some(a1), Some(a2), Some(a3)) = (
172        map.read_attribute::<VertexAnchor>(t, l_vid)?,
173        map.read_attribute::<VertexAnchor>(t, r_vid)?,
174        map.read_attribute::<EdgeAnchor>(t, e)?,
175    ) {
176        (a1, a2, a3)
177    } else {
178        retry()?
179    };
180
181    match AttributeUpdate::merge(l_anchor, r_anchor) {
182        Ok(val) => {
183            // check ID too? did other checks filter that out already?
184            // does having different IDs here mean the classification is bad?
185            if edge_anchor.anchor_dim() == l_anchor.anchor_dim()
186                || edge_anchor.anchor_dim() == r_anchor.anchor_dim()
187            {
188                match (val == l_anchor, val == r_anchor) {
189                    (true, true) => Ok(Collapsible::Average),
190                    (true, false) => Ok(Collapsible::Left),
191                    (false, true) => Ok(Collapsible::Right),
192                    (false, false) => unreachable!(),
193                }
194            } else {
195                abort(EdgeCollapseError::NonCollapsibleEdge(
196                    "collapsing along this edge is impossible",
197                ))
198            }
199        }
200        Err(AttributeError::FailedMerge(_, _)) => abort(EdgeCollapseError::NonCollapsibleEdge(
201            "vertex have incompatible anchors",
202        )),
203        Err(AttributeError::FailedSplit(_, _) | AttributeError::InsufficientData(_, _)) => {
204            unreachable!();
205        }
206    }
207}
208
209// ---- midpoint collapse
210
211fn collapse_edge_to_midpoint<T: CoordsFloat>(
212    t: &mut Transaction,
213    map: &CMap2<T>,
214    (b0l, l, b1l): (DartIdType, DartIdType, DartIdType),
215    (b0r, r, b1r): (DartIdType, DartIdType, DartIdType),
216) -> TransactionClosureResult<VertexIdType, EdgeCollapseError> {
217    let b2b1r = map.beta_tx::<2>(t, b1r)?;
218    let b1b2b1r = map.beta_tx::<1>(t, b2b1r)?;
219    if r != NULL_DART_ID {
220        try_or_coerce!(map.unsew::<2>(t, r), EdgeCollapseError);
221        collapse_halfcell_to_midpoint(t, map, (b0r, r, b1r))?;
222    }
223    // by this point l is 2-free, whether he was at the beginning or due to the 2-unsew
224    let b2b0l = map.beta_tx::<2>(t, b0l)?; // save this before left cell collapse
225    collapse_halfcell_to_midpoint(t, map, (b0l, l, b1l))?;
226
227    Ok(if b2b0l != NULL_DART_ID {
228        map.vertex_id_tx(t, b2b0l)?
229    } else if r != NULL_DART_ID {
230        map.vertex_id_tx(t, b1b2b1r)?
231    } else {
232        // this can happen from a valid configuration, so we handle it
233        NULL_VERTEX_ID
234    })
235}
236
237fn collapse_halfcell_to_midpoint<T: CoordsFloat>(
238    t: &mut Transaction,
239    map: &CMap2<T>,
240    (b0d, d, b1d): (DartIdType, DartIdType, DartIdType),
241) -> TransactionClosureResult<(), EdgeCollapseError> {
242    try_or_coerce!(map.unsew::<1>(t, d), EdgeCollapseError);
243    try_or_coerce!(map.unsew::<1>(t, b1d), EdgeCollapseError);
244    try_or_coerce!(map.unsew::<1>(t, b0d), EdgeCollapseError);
245    let (b2b0d, b2b1d) = (map.beta_tx::<2>(t, b0d)?, map.beta_tx::<2>(t, b1d)?);
246    match (b2b0d == NULL_DART_ID, b2b1d == NULL_DART_ID) {
247        (false, false) => {
248            try_or_coerce!(map.unsew::<2>(t, b0d), EdgeCollapseError);
249            try_or_coerce!(map.unsew::<2>(t, b1d), EdgeCollapseError);
250            try_or_coerce!(map.sew::<2>(t, b2b0d, b2b1d), EdgeCollapseError);
251        }
252        (true, false) => {
253            try_or_coerce!(map.unsew::<2>(t, b1d), EdgeCollapseError);
254        }
255        (false, true) => {
256            try_or_coerce!(map.unsew::<2>(t, b0d), EdgeCollapseError);
257        }
258        (true, true) => {}
259    }
260
261    try_or_coerce!(map.release_dart_tx(t, d), EdgeCollapseError);
262    try_or_coerce!(map.release_dart_tx(t, b0d), EdgeCollapseError);
263    try_or_coerce!(map.release_dart_tx(t, b1d), EdgeCollapseError);
264    TransactionClosureResult::Ok(())
265}
266
267// ---- base collapse
268
269fn collapse_edge_to_base<T: CoordsFloat>(
270    t: &mut Transaction,
271    map: &CMap2<T>,
272    (b0l, l, b1l): (DartIdType, DartIdType, DartIdType), // base == l
273    (b0r, r, b1r): (DartIdType, DartIdType, DartIdType),
274) -> TransactionClosureResult<VertexIdType, EdgeCollapseError> {
275    // reading/writing the coordinates to collapse to is easier to handle split/merges correctly
276    let b2b1l = map.beta_tx::<2>(t, b1l)?;
277    let b2b0r = map.beta_tx::<2>(t, b0r)?;
278    let l_vid = map.vertex_id_tx(t, l)?;
279    let l_fid = map.face_id_tx(t, b2b1l)?;
280    let r_fid = map.face_id_tx(t, b2b0r)?;
281    let tmp_vertex = map.read_vertex(t, l_vid)?;
282    let tmp_anchor = map.read_attribute::<VertexAnchor>(t, l_vid)?;
283    let l_face_anchor = map.read_attribute::<FaceAnchor>(t, l_fid)?;
284    let r_face_anchor = map.read_attribute::<FaceAnchor>(t, r_fid)?;
285
286    if r != NULL_DART_ID {
287        try_or_coerce!(map.unsew::<2>(t, l), EdgeCollapseError);
288        try_or_coerce!(
289            collapse_halfcell_to_base(t, map, (b1r, r, b0r)),
290            EdgeCollapseError
291        );
292    }
293    // by this point l is 2-free, whether he was at the beginning or due to the 2-unsew
294    let b2b0l = map.beta_tx::<2>(t, b0l)?; // save this before left cell collapse
295    try_or_coerce!(
296        collapse_halfcell_to_base(t, map, (b0l, l, b1l)),
297        EdgeCollapseError
298    );
299
300    let new_vid = if b2b0l != NULL_DART_ID {
301        map.vertex_id_tx(t, b2b0l)?
302    } else if r != NULL_DART_ID {
303        map.vertex_id_tx(t, b1r)?
304    } else {
305        // this can happen from a valid configuration, so we handle it
306        NULL_VERTEX_ID
307    };
308
309    if new_vid != NULL_VERTEX_ID {
310        if let Some(v) = tmp_vertex {
311            map.write_vertex(t, new_vid, v)?;
312        } // else eprintln! ?
313        if let Some(a) = tmp_anchor {
314            map.write_attribute(t, new_vid, a)?;
315        }
316    }
317    if let Some(f_a) = l_face_anchor {
318        if !map.is_unused_tx(t, b0l)? {
319            let new_fid = map.face_id_tx(t, b0l)?;
320            map.write_attribute(t, new_fid, f_a)?;
321        }
322    }
323    if let Some(f_a) = r_face_anchor {
324        let new_fid = map.face_id_tx(t, b1r)?;
325        map.write_attribute(t, new_fid, f_a)?;
326    }
327
328    Ok(new_vid)
329}
330
331fn collapse_halfcell_to_base<T: CoordsFloat>(
332    t: &mut Transaction,
333    map: &CMap2<T>,
334    // d_previous_edge, d_edge, d_next_edge
335    (d_pe, d_e, d_ne): (DartIdType, DartIdType, DartIdType),
336) -> TransactionClosureResult<(), EdgeCollapseError> {
337    let b2d_ne = map.beta_tx::<2>(t, d_ne)?;
338    let b0b2d_ne = map.beta_tx::<0>(t, b2d_ne)?;
339    let b1b2d_ne = map.beta_tx::<1>(t, b2d_ne)?;
340
341    try_or_coerce!(map.unsew::<1>(t, d_e), EdgeCollapseError);
342    try_or_coerce!(map.unsew::<1>(t, d_pe), EdgeCollapseError);
343    try_or_coerce!(map.unsew::<1>(t, d_ne), EdgeCollapseError);
344    if b2d_ne == NULL_DART_ID {
345        try_or_coerce!(map.unsew::<2>(t, d_pe), EdgeCollapseError);
346        try_or_coerce!(map.release_dart_tx(t, d_pe), EdgeCollapseError);
347    } else {
348        try_or_coerce!(map.unsew::<1>(t, b2d_ne), EdgeCollapseError);
349        try_or_coerce!(map.unsew::<1>(t, b0b2d_ne), EdgeCollapseError);
350        try_or_coerce!(map.unlink::<2>(t, d_ne), EdgeCollapseError);
351        try_or_coerce!(map.release_dart_tx(t, b2d_ne), EdgeCollapseError);
352        try_or_coerce!(map.sew::<1>(t, d_pe, b1b2d_ne), EdgeCollapseError);
353        try_or_coerce!(map.sew::<1>(t, b0b2d_ne, d_pe), EdgeCollapseError);
354    }
355    try_or_coerce!(map.release_dart_tx(t, d_e), EdgeCollapseError);
356    try_or_coerce!(map.release_dart_tx(t, d_ne), EdgeCollapseError);
357
358    Ok(())
359}
honeycomb_kernels/remeshing/collapse.rs

honeycomb_kernels/remeshing/
collapse.rs
