mesh_graph/ops/

remove.rs

use hashbrown::HashSet;
use itertools::Itertools;
use tracing::{error, instrument};

use crate::{FaceId, HalfedgeId, MeshGraph, VertexId};

impl MeshGraph {
    /// Deletes a face from the mesh graph.
    ///
    /// It also deletes the vertices and halfedges that are no
    /// longer connected to any other faces.
    ///
    /// Returns the ids of the removed vertices and halfedges.
    #[instrument(skip(self))]
    pub fn remove_face(&mut self, face_id: FaceId) -> (Vec<VertexId>, Vec<HalfedgeId>) {
        if !self.faces.contains_key(face_id) {
            return (vec![], vec![]);
        }

        let halfedges = self
            .halfedges
            .iter()
            .filter_map(|(he_id, he)| {
                if he.face == Some(face_id) {
                    Some((he_id, *he))
                } else {
                    None
                }
            })
            .collect_vec();

        #[cfg(feature = "instrumentation")]
        crate::record_op_trace!(
            "remove_face({face_id:?}) members={:?}",
            halfedges.iter().map(|(id, _)| id).collect_vec()
        );

        let mut removed_halfedges = HashSet::with_capacity(4);

        for (he_id, he) in halfedges {
            // A twinless member (left over by a re-pair sever or a dangling-twin clear)
            // must not abort the face removal: remove the member itself. Same for a
            // member whose twin reference is dead.
            let Some(twin_id) = he.twin else {
                removed_halfedges.insert(he_id);
                continue;
            };
            let Some(twin) = self.halfedges.get(twin_id) else {
                removed_halfedges.insert(he_id);
                continue;
            };
            if twin.is_boundary() {
                removed_halfedges.insert(he_id);
                removed_halfedges.insert(twin_id);
            } else if twin.twin != Some(he_id) {
                removed_halfedges.insert(he_id);
            } else {
                // already checked above
                self.halfedges[he_id].face = None;
                self.halfedges[he_id].next = None;
            }
        }

        #[cfg(feature = "rerun")]
        self.log_hes_rerun(
            "deleted_by_face_deletion",
            &removed_halfedges.iter().copied().collect::<Vec<_>>(),
        );

        let mut removed_vertices = Vec::with_capacity(3);
        let mut touched_start_vertices = HashSet::with_capacity(3);

        // Update connections from vertices to deleted halfedges
        for &he_id in &removed_halfedges {
            // The start of a removed member is derived from its twin; for a member
            // whose twin is missing/dead/twinless it cannot be resolved. Skipping the
            // cleanup leaves a stale entry in `outgoing_halfedges` that the periodic
            // `contains_key` retain passes purge; aborting the removal instead would
            // leave the face half-detached (some members already nulled) and break
            // its chain, which is the layer-4 corruption.
            let Some(start_v_id) = self.halfedges[he_id].start_vertex(self) else {
                continue;
            };
            touched_start_vertices.insert(start_v_id);
            if let Some(out_he_ids) = self.outgoing_halfedges.get_mut(start_v_id) {
                out_he_ids.retain(|&id| id != he_id);
            } else {
                error!("No outgoing halfedges found for vertex {start_v_id:?}");
            }
        }

        for start_v_id in touched_start_vertices {
            // A vertex survives if it still has a live outgoing halfedge; in that
            // case refresh its seed pointer. Otherwise it is now isolated.
            let surviving_out_he = self
                .outgoing_halfedges
                .get(start_v_id)
                .and_then(|out_he_ids| out_he_ids.first().copied());

            if let Some(out_he_id) = surviving_out_he {
                if let Some(v) = self.vertices.get_mut(start_v_id) {
                    v.outgoing_halfedge = Some(out_he_id);
                } else {
                    error!("Vertex {start_v_id:?} not found");
                }
            } else {
                self.remove_only_vertex(start_v_id);
                removed_vertices.push(start_v_id);
            }
        }

        #[cfg(feature = "instrumentation")]
        self.probe_live_face_removal(
            &removed_halfedges.iter().copied().collect::<Vec<_>>(),
            "remove_face_tail",
        );

        for he_id in &removed_halfedges {
            self.halfedges.remove(*he_id);
        }

        // already checked at the start of the function
        self.bvh.remove(self.faces[face_id].index);
        self.faces.remove(face_id);
        #[cfg(feature = "instrumentation")]
        crate::record_face_death(face_id);

        (removed_vertices, Vec::from_iter(removed_halfedges))
    }

    /// Deletes only a vertex, without deleting any faces or halfedges connected to it.
    pub fn remove_only_vertex(&mut self, vertex_id: VertexId) {
        self.outgoing_halfedges.remove(vertex_id);
        self.positions.remove(vertex_id);
        if let Some(normals) = &mut self.vertex_normals {
            normals.remove(vertex_id);
        }
        self.vertices.remove(vertex_id);
    }

    /// Deletes only a halfedge, without deleting any faces or vertices connected to it.
    /// No other halfedge is modified: the twin (if any) keeps its `twin` pointer,
    /// which now refers to a removed halfedge. The caller must re-pair the twin or
    /// remove it before its operation terminates (flap cleanup does both below).
    pub fn remove_only_halfedge(&mut self, he_id: HalfedgeId) {
        if let Some(he) = self.halfedges.get(he_id) {
            if let Some(start_v_id) = he.start_vertex(self)
                && let Some(hes) = self.outgoing_halfedges.get_mut(start_v_id)
            {
                hes.retain(|out_he_id| *out_he_id != he_id);
            }

            #[cfg(feature = "instrumentation")]
            self.probe_live_face_removal(&[he_id], "remove_only_halfedge");
            self.halfedges.remove(he_id);
        }
    }

    pub fn remove_only_halfedge_and_twin(&mut self, he_id: HalfedgeId) {
        if let Some(he) = self.halfedges.get(he_id) {
            if let Some(start_v_id) = he.start_vertex(self)
                && let Some(hes) = self.outgoing_halfedges.get_mut(start_v_id)
            {
                hes.retain(|out_he_id| *out_he_id != he_id);
            }

            if let Some(twin_he_id) = he.twin {
                self.remove_only_halfedge(twin_he_id);
            }

            // The twin was just removed. `he_id`'s own twin pointer is left as-is
            // (dead reference inside this call); nothing else survives to re-pair.
            #[cfg(feature = "instrumentation")]
            self.probe_live_face_removal(&[he_id], "remove_only_halfedge_and_twin");
            self.halfedges.remove(he_id);
        }
    }
}

#[cfg(test)]
mod tests {
    use glam::{Mat4, vec3};

    use crate::{
        utils::{extend_with, get_tracing_subscriber},
        *,
    };

    #[test]
    fn test_remove_face() {
        get_tracing_subscriber();
        let mut meshgraph = MeshGraph::new();
        let p_c = vec3(0.0, 0.0, 0.0);
        let p_1 = vec3(0.0, 1.0, 0.0);
        let p_2 = vec3(-1.0, 0.5, 0.0);
        let p_3 = vec3(-1.0, -0.5, 0.0);
        let p_4 = vec3(0.0, -1.0, 0.0);
        let p_5 = vec3(1.0, -0.5, 0.0);
        let p_6 = vec3(1.0, 0.5, 0.0);

        let points = vec![p_c, p_1, p_2, p_3, p_4, p_5, p_6];
        let vertex_ids = extend_with(&mut meshgraph, &points.clone(), Mat4::default(), 5.0, 0);

        #[cfg(feature = "rerun")]
        {
            meshgraph.log_rerun();
            RR.flush_blocking().unwrap();
        }

        let face_count = meshgraph.faces.len();
        let face_id = meshgraph.vertices[vertex_ids[6]]
            .faces(&meshgraph)
            .next()
            .unwrap();
        meshgraph.remove_face(face_id);
        #[cfg(feature = "rerun")]
        {
            meshgraph.log_rerun();
            RR.flush_blocking().unwrap();
        }

        assert_eq!(meshgraph.faces.len(), face_count - 1);
    }
}