use super::*;
struct FacePatch {
shell_index: usize,
face_ids: HashSet<u64>,
dropped_loops: Vec<(usize, usize, usize)>,
edges: HashSet<u64>,
}
#[derive(Clone, Copy, Default)]
struct EdgeCensus {
selected: usize,
kept: usize,
}
fn census(solid: &BrepSolid, face_ids: &HashSet<u64>) -> HashMap<u64, EdgeCensus> {
let mut counts: HashMap<u64, EdgeCensus> = HashMap::default();
for face in solid.shells.iter().flat_map(|shell| &shell.faces) {
let selected = face_ids.contains(&face.id);
for coedge in face.loops.iter().flat_map(|loop_record| &loop_record.coedges) {
let entry = counts.entry(coedge.edge_id).or_default();
if selected {
entry.selected += 1;
} else {
entry.kept += 1;
}
}
}
counts
}
fn classify_patch(solid: &BrepSolid, face_ids: &[u64]) -> Option<FacePatch> {
let selected: HashSet<u64> = face_ids.iter().copied().collect();
let mut shells = face_ids
.iter()
.filter_map(|face_id| find_face(solid, *face_id))
.map(|(shell_index, _)| shell_index);
let shell_index = shells.next()?;
if shells.any(|other| other != shell_index) {
return None;
}
let counts = census(solid, &selected);
let mut dropped_loops = Vec::new();
for (shell_position, shell) in solid.shells.iter().enumerate() {
for (face_position, face) in shell.faces.iter().enumerate() {
if selected.contains(&face.id) {
continue;
}
for (loop_index, loop_record) in face.loops.iter().enumerate() {
let mut touches = false;
let mut whole = true;
for coedge in &loop_record.coedges {
if counts
.get(&coedge.edge_id)
.is_some_and(|count| count.selected > 0)
{
touches = true;
} else {
whole = false;
}
}
if !touches {
continue;
}
if !whole {
return None;
}
dropped_loops.push((shell_position, face_position, loop_index));
}
}
}
if dropped_loops.is_empty() {
return None;
}
let edges: HashSet<u64> = counts
.iter()
.filter(|(_, count)| count.selected > 0)
.map(|(edge_id, _)| *edge_id)
.collect();
Some(FacePatch {
shell_index,
face_ids: selected,
dropped_loops,
edges,
})
}
fn euler_characteristic(solid: &BrepSolid) -> i64 {
let referenced: HashSet<u64> = solid
.edges
.iter()
.filter(|edge| !edge.degenerate)
.flat_map(|edge| [edge.start_vertex_id, edge.end_vertex_id])
.collect();
let vertices = solid
.vertices
.iter()
.filter(|vertex| referenced.contains(&vertex.id))
.count() as i64;
let edges = solid.edges.iter().filter(|edge| !edge.degenerate).count() as i64;
let faces = solid
.shells
.iter()
.map(|shell| shell.faces.len())
.sum::<usize>() as i64;
let holes: i64 = solid
.shells
.iter()
.flat_map(|shell| &shell.faces)
.map(|face| face.loops.len().saturating_sub(1) as i64)
.sum();
vertices - edges + faces - holes
}
fn face_label(face: &FaceRecord) -> String {
match &face.name {
Some(name) => format!("`{name}`"),
None => format!("face {}", face.id),
}
}
fn cap_face_patch(solid: &BrepSolid, patch: &FacePatch, op: &str) -> Result<BrepSolid, String> {
let mut per_face: HashMap<(usize, usize), Vec<usize>> = HashMap::default();
for (shell_position, face_position, loop_index) in &patch.dropped_loops {
per_face
.entry((*shell_position, *face_position))
.or_default()
.push(*loop_index);
}
for ((shell_position, face_position), loop_indices) in &per_face {
let face = &solid.shells[*shell_position].faces[*face_position];
if loop_indices.len() >= face.loops.len() {
return Err(format!(
"{op}: the selection is the whole boundary of {} — it is part of the \
pocket, not the face the pocket was sunk into. Select it as well \
(a patch is capped by the face AROUND it, which has to keep a loop).",
face_label(face)
));
}
let mut areas = Vec::with_capacity(face.loops.len());
for index in 0..face.loops.len() {
areas.push(loop_signed_area(face, index)?);
}
let host = (0..areas.len())
.max_by(|a, b| areas[*a].abs().total_cmp(&areas[*b].abs()))
.expect("the face has at least two loops here");
for loop_index in loop_indices {
if *loop_index == host || areas[host] * areas[*loop_index] >= 0.0 {
return Err(format!(
"{op}: the loop the selection would leave open in {} bounds that \
face's material rather than a hole in it — capping it would erase \
the face (deferred)",
face_label(face)
));
}
}
}
let mut healed = solid.clone();
for ((shell_position, face_position), loop_indices) in &per_face {
let mut loop_indices = loop_indices.clone();
loop_indices.sort_unstable_by(|a, b| b.cmp(a));
for loop_index in loop_indices {
healed.shells[*shell_position].faces[*face_position]
.loops
.remove(loop_index);
}
}
for shell in &mut healed.shells {
shell.faces.retain(|face| !patch.face_ids.contains(&face.id));
}
healed.edges.retain(|edge| !patch.edges.contains(&edge.id));
let used: HashSet<u64> = healed
.edges
.iter()
.flat_map(|edge| [edge.start_vertex_id, edge.end_vertex_id])
.collect();
healed.vertices.retain(|vertex| used.contains(&vertex.id));
if !faces_are_connected(&healed.shells[patch.shell_index].faces) {
return Err(format!(
"{op}: the selected faces are what joins two otherwise separate parts of \
the body — removing them would sever the solid, which this operation \
cannot represent (deferred)"
));
}
let shift = euler_characteristic(solid) - euler_characteristic(&healed);
if shift % 2 != 0 {
return Err(format!(
"{op}: the selection does not close into whole handles \
(Euler characteristic shifts by an odd {shift}) — refusing rather than \
emitting a solid whose genus is a guess"
));
}
healed.genus += shift / 2;
if healed.genus < 0 {
return Err(format!(
"{op}: capping the selection leaves genus {}, so the solid's stated genus \
did not account for the feature it carries (deferred)",
healed.genus
));
}
let issues = healed.validate();
if !issues.is_empty() {
return Err(format!("{op}: the capped solid failed validation: {issues:?}"));
}
Ok(healed)
}
pub fn delete_faces_and_heal(solid: &BrepSolid, face_ids: &[u64]) -> Result<BrepSolid, String> {
let op = "delete_faces_and_heal";
let mut seen: HashSet<u64> = HashSet::default();
let face_ids: Vec<u64> = face_ids
.iter()
.copied()
.filter(|face_id| seen.insert(*face_id))
.collect();
if face_ids.is_empty() {
return Err(format!("{op}: no faces selected"));
}
for face_id in &face_ids {
if find_face(solid, *face_id).is_none() {
return Err(format!("{op}: no face with id {face_id}"));
}
}
if face_ids.len() == 1 {
return delete_face_and_heal(solid, face_ids[0]);
}
if let Some(patch) = classify_patch(solid, &face_ids) {
return cap_face_patch(solid, &patch, op);
}
let mut healed = solid.clone();
for face_id in &face_ids {
healed = delete_face_and_heal(&healed, *face_id)?;
}
Ok(healed)
}
#[cfg(test)]
mod delete_faces_tests {
use super::*;
use crate::{
boolean_operation, chamfer_edge, make_box_brep, make_cylinder_brep,
solid_mass_properties, BooleanOperation, BooleanOptions,
};
fn volume(solid: &BrepSolid) -> f64 {
solid_mass_properties(solid)
.expect("mass properties")
.volume
}
fn face_count(solid: &BrepSolid) -> usize {
solid.shells.iter().map(|shell| shell.faces.len()).sum()
}
fn cube_with_square_pocket() -> BrepSolid {
let cube = make_box_brep(Vec3::default(), 20.0, 20.0, 20.0).unwrap();
let cutter = make_box_brep(Vec3::new(5.0, 5.0, 15.0), 8.0, 8.0, 10.0).unwrap();
let cut = boolean_operation(
&cube,
&cutter,
BooleanOperation::Subtract,
&BooleanOptions::default(),
)
.unwrap();
assert!(cut.validate().is_empty(), "{:?}", cut.validate());
cut
}
fn faces_bounded_within(solid: &BrepSolid, inside: impl Fn(Vec3) -> bool) -> Vec<u64> {
solid
.shells
.iter()
.flat_map(|shell| &shell.faces)
.filter(|face| {
face.loops
.iter()
.flat_map(|loop_record| &loop_record.coedges)
.all(|coedge| {
solid
.edges
.iter()
.find(|edge| edge.id == coedge.edge_id)
.and_then(|edge| edge.curve.evaluate(0.5 * (edge.t0 + edge.t1)).ok())
.map(&inside)
.unwrap_or(false)
})
})
.map(|face| face.id)
.collect()
}
fn pocket_faces(solid: &BrepSolid) -> Vec<u64> {
faces_bounded_within(solid, |point| {
point.x > 4.0 && point.x < 14.0 && point.y > 4.0 && point.y < 14.0 && point.z > 14.0
})
}
#[test]
fn capping_a_blind_pocket_restores_the_cube() {
let cut = cube_with_square_pocket();
let pocket = pocket_faces(&cut);
assert_eq!(pocket.len(), 5, "four walls and a floor");
assert_eq!(face_count(&cut), 11, "the cube's six plus the pocket's five");
let healed = delete_faces_and_heal(&cut, &pocket).expect("the pocket caps");
assert!(healed.validate().is_empty(), "{:?}", healed.validate());
assert_eq!(face_count(&healed), 6, "the cube's six faces");
assert!(
healed
.shells
.iter()
.flat_map(|shell| &shell.faces)
.all(|face| face.loops.len() == 1),
"no face keeps the pocket's mouth loop"
);
assert_eq!(healed.genus, 0, "a pocket is not a handle");
assert!(
(volume(&healed) - 8000.0).abs() < 1e-9,
"the cube is back: {}",
volume(&healed)
);
}
#[test]
fn refuses_a_pocket_whose_floor_was_not_selected() {
let cut = cube_with_square_pocket();
let pocket = pocket_faces(&cut);
let floor = cut
.shells
.iter()
.flat_map(|shell| &shell.faces)
.find(|face| {
pocket.contains(&face.id)
&& face
.surface
.evaluate(0.5, 0.5)
.map(|point| (point.z - 15.0).abs() < 1e-9)
.unwrap_or(false)
})
.expect("the pocket floor")
.id;
let walls: Vec<u64> = pocket.iter().copied().filter(|id| *id != floor).collect();
assert_eq!(walls.len(), 4);
let error = delete_faces_and_heal(&cut, &walls).unwrap_err();
assert!(
error.contains("Select it as well"),
"the refusal must say what to do: {error}"
);
}
#[test]
fn a_non_patch_selection_still_chains() {
let cylinder =
make_cylinder_brep(Vec3::default(), Vec3::new(0.0, 0.0, 1.0), 4.0, 6.0).unwrap();
let full = volume(&cylinder);
let rim_at = |solid: &BrepSolid, z: f64| {
solid
.edges
.iter()
.find(|edge| {
!edge.degenerate
&& edge.start_vertex_id == edge.end_vertex_id
&& edge
.curve
.evaluate(0.5 * (edge.t0 + edge.t1))
.map(|point| (point.z - z).abs() < 1e-9)
.unwrap_or(false)
})
.map(|edge| edge.id)
.expect("closed rim")
};
let top = rim_at(&cylinder, 6.0);
let chamfered = chamfer_edge(&cylinder, top, 1.0, Some("C1")).unwrap();
let bottom = rim_at(&chamfered, 0.0);
let chamfered = chamfer_edge(&chamfered, bottom, 1.0, Some("C2")).unwrap();
assert!(chamfered.validate().is_empty(), "{:?}", chamfered.validate());
let strips: Vec<u64> = chamfered
.shells
.iter()
.flat_map(|shell| &shell.faces)
.filter(|face| matches!(face.name.as_deref(), Some("C1") | Some("C2")))
.map(|face| face.id)
.collect();
assert_eq!(strips.len(), 2, "both chamfer strips are named");
assert!(
classify_patch(&chamfered, &strips).is_none(),
"two chamfer strips are not a patch"
);
let healed = delete_faces_and_heal(&chamfered, &strips).expect("the chain heals both");
assert!(healed.validate().is_empty(), "{:?}", healed.validate());
assert_eq!(face_count(&healed), 3, "wall, top, bottom");
assert!(
(volume(&healed) - full).abs() <= 1e-6 * full,
"the cylinder is back: {} vs {full}",
volume(&healed)
);
}
#[test]
fn capping_a_through_bore_and_a_pocket_together_drops_one_handle() {
let plate = make_box_brep(Vec3::default(), 20.0, 20.0, 20.0).unwrap();
let drill = make_cylinder_brep(
Vec3::new(5.0, 5.0, -5.0),
Vec3::new(0.0, 0.0, 1.0),
2.0,
30.0,
)
.unwrap();
let drilled = boolean_operation(
&plate,
&drill,
BooleanOperation::Subtract,
&BooleanOptions::default(),
)
.unwrap();
let pocket_cutter = make_box_brep(Vec3::new(12.0, 12.0, 15.0), 5.0, 5.0, 10.0).unwrap();
let cut = boolean_operation(
&drilled,
&pocket_cutter,
BooleanOperation::Subtract,
&BooleanOptions::default(),
)
.unwrap();
assert!(cut.validate().is_empty(), "{:?}", cut.validate());
assert_eq!(cut.genus, 1, "the bore is a handle");
let outer = |point: Vec3| {
point.x.abs() < 1e-9
|| (point.x - 20.0).abs() < 1e-9
|| point.y.abs() < 1e-9
|| (point.y - 20.0).abs() < 1e-9
|| point.z.abs() < 1e-9
|| (point.z - 20.0).abs() < 1e-9
};
let selection: Vec<u64> = cut
.shells
.iter()
.flat_map(|shell| &shell.faces)
.filter(|face| !face.surface.evaluate(0.5, 0.5).map(outer).unwrap_or(true))
.map(|face| face.id)
.collect();
assert_eq!(selection.len(), 6, "the bore wall plus the pocket's five");
let healed = delete_faces_and_heal(&cut, &selection).expect("both cap");
assert!(healed.validate().is_empty(), "{:?}", healed.validate());
assert_eq!(face_count(&healed), 6, "the plate's six faces");
assert_eq!(healed.genus, 0, "closing the bore removes the handle");
assert!(
(volume(&healed) - 8000.0).abs() < 1e-6,
"the plate is back: {}",
volume(&healed)
);
}
#[test]
fn refuses_a_patch_whose_removal_would_sever_the_body() {
let lower = make_box_brep(Vec3::new(0.0, 0.0, 0.0), 20.0, 20.0, 4.0).unwrap();
let upper = make_box_brep(Vec3::new(0.0, 0.0, 12.0), 20.0, 20.0, 4.0).unwrap();
let post = make_box_brep(Vec3::new(8.0, 8.0, 4.0), 4.0, 4.0, 8.0).unwrap();
let options = BooleanOptions::default();
let joined = boolean_operation(&lower, &post, BooleanOperation::Union, &options)
.and_then(|solid| {
boolean_operation(&solid, &upper, BooleanOperation::Union, &options)
})
.expect("the sandwich unions");
assert!(joined.validate().is_empty(), "{:?}", joined.validate());
let walls = faces_bounded_within(&joined, |point| {
point.x >= 7.9 && point.x <= 12.1 && point.y >= 7.9 && point.y <= 12.1
});
assert_eq!(walls.len(), 4, "the post's four walls");
assert!(
classify_patch(&joined, &walls).is_some(),
"the post's walls ARE a patch — the refusal has to come from the \
connectivity check, not from the gate"
);
let error = delete_faces_and_heal(&joined, &walls).unwrap_err();
assert!(
error.contains("sever the solid"),
"unexpected refusal: {error}"
);
}
#[test]
fn refuses_a_face_that_does_not_exist() {
let cube = make_box_brep(Vec3::default(), 1.0, 1.0, 1.0).unwrap();
let error = delete_faces_and_heal(&cube, &[999_999, 1]).unwrap_err();
assert!(
error.contains("no face with id 999999"),
"unexpected refusal: {error}"
);
}
#[test]
fn refuses_an_empty_selection() {
let cube = make_box_brep(Vec3::default(), 1.0, 1.0, 1.0).unwrap();
let error = delete_faces_and_heal(&cube, &[]).unwrap_err();
assert!(error.contains("no faces selected"), "{error}");
}
}