brep_kernel/csg/

edge_split.rs

use crate::imprint::ImprintResultRecord;
use crate::topology::{BrepSolid, CoedgeRecord, EdgeRecord, VertexRecord};
use crate::{NurbsCurve, Vec3};
use rustc_hash::FxHashMap as HashMap;

fn subcurve_by_fraction(
    curve: &NurbsCurve,
    start_fraction: f64,
    end_fraction: f64,
) -> Result<NurbsCurve, String> {
    let [start, end] = curve.domain()?;
    let first = start + (end - start) * start_fraction;
    let second = start + (end - start) * end_fraction;
    let epsilon = (1e-9 * (end - start)).max(2e-9);
    let mut result = curve.clone();
    if first > start + epsilon && first < end - epsilon {
        result = result.split(first)?.1;
    }
    let domain = result.domain()?;
    if second < domain[1] - epsilon && second > domain[0] + epsilon {
        result = result.split(second)?.0;
    } else if std::env::var("BREP_DEBUG_SUBRANGE").is_ok() && second < domain[1] - epsilon {
        eprintln!("abnormal subrange skip in edge_split subcurve");
    }
    Ok(result)
}

fn claim_vertex(
    vertices: &mut Vec<VertexRecord>,
    imprint: &ImprintResultRecord,
    point: Vec3,
    next_id: &mut u64,
) -> u64 {
    let tolerance = 1e-5 * (1.0 + point.length());
    if let Some(vertex) = vertices
        .iter()
        .find(|vertex| vertex.point.sub(point).length() <= tolerance)
    {
        return vertex.id;
    }
    let canonical = imprint
        .vertices
        .iter()
        .filter_map(|vertex| {
            let distance = vertex.point.sub(point).length();
            (distance <= tolerance).then_some((vertex.point, distance))
        })
        .min_by(|a, b| a.1.total_cmp(&b.1))
        .map(|candidate| candidate.0)
        .unwrap_or(point);
    let id = *next_id;
    *next_id += 1;
    vertices.push(VertexRecord {
        id,
        point: canonical,
    });
    id
}

/// Apply the boundary-edge partition produced by imprint construction.
///
/// The original edge curve and parameter range semantics are preserved; only
/// coedge p-curves are restricted to traversal-aligned subcurves.
pub fn apply_edge_splits(
    solid: &BrepSolid,
    operand: u8,
    imprint: &ImprintResultRecord,
) -> Result<BrepSolid, String> {
    apply_edge_splits_with_map(solid, operand, imprint).map(|(result, _)| result)
}

/// [`apply_edge_splits`] plus the identity ledger: original edge id → the
/// minted sub-edge ids that replaced it. Consumers keyed on ORIGINAL edge
/// ids (the fragment-selection barrier set) must remap through it, since the
/// split solid's coedges reference the minted ids.
pub fn apply_edge_splits_with_map(
    solid: &BrepSolid,
    operand: u8,
    imprint: &ImprintResultRecord,
) -> Result<(BrepSolid, HashMap<u64, Vec<u64>>), String> {
    let requested = imprint
        .edge_splits
        .iter()
        .filter(|split| split.operand == operand)
        .map(|split| (split.edge_id, split.parameters.as_slice()))
        .collect::<HashMap<_, _>>();
    if requested.is_empty() {
        return Ok((solid.clone(), HashMap::default()));
    }

    let mut result = solid.clone();
    let mut next_vertex_id = result
        .vertices
        .iter()
        .map(|vertex| vertex.id)
        .max()
        .unwrap_or(0)
        + 1;
    let mut next_edge_id = result.edges.iter().map(|edge| edge.id).max().unwrap_or(0) + 1;
    let mut next_coedge_id = result
        .shells
        .iter()
        .flat_map(|shell| &shell.faces)
        .flat_map(|face| &face.loops)
        .flat_map(|loop_record| &loop_record.coedges)
        .map(|coedge| coedge.id)
        .max()
        .unwrap_or(0)
        + 1;
    let mut pieces: HashMap<u64, Vec<EdgeRecord>> = HashMap::default();

    for edge in &solid.edges {
        let Some(parameters) = requested.get(&edge.id) else {
            continue;
        };
        let parameter_tolerance = (edge.t1 - edge.t0).abs() * 1e-10;
        let mut partition = parameters
            .iter()
            .copied()
            .filter(|parameter| {
                *parameter > edge.t0 + parameter_tolerance
                    && *parameter < edge.t1 - parameter_tolerance
            })
            .collect::<Vec<_>>();
        partition.sort_by(f64::total_cmp);
        partition.dedup_by(|a, b| (*a - *b).abs() <= parameter_tolerance);
        partition.insert(0, edge.t0);
        partition.push(edge.t1);
        if partition.len() <= 2 {
            continue;
        }
        let mut vertex_ids = vec![edge.start_vertex_id];
        for parameter in &partition[1..partition.len() - 1] {
            let point = edge.curve.evaluate(*parameter)?;
            vertex_ids.push(claim_vertex(
                &mut result.vertices,
                imprint,
                point,
                &mut next_vertex_id,
            ));
        }
        vertex_ids.push(edge.end_vertex_id);
        let mut edge_pieces = Vec::new();
        for index in 0..partition.len() - 1 {
            // First piece keeps the source name; later pieces get the
            // deterministic `_1`, `_2` split suffixes the application uses.
            let name = edge.name.as_ref().map(|name| {
                if index == 0 {
                    name.clone()
                } else {
                    format!("{name}_{index}")
                }
            });
            edge_pieces.push(EdgeRecord {
                id: next_edge_id,
                curve: edge.curve.clone(),
                t0: partition[index],
                t1: partition[index + 1],
                start_vertex_id: vertex_ids[index],
                end_vertex_id: vertex_ids[index + 1],
                degenerate: false,
                name,
            });
            next_edge_id += 1;
        }
        pieces.insert(edge.id, edge_pieces);
    }

    result.edges.retain(|edge| !pieces.contains_key(&edge.id));
    for edge_pieces in pieces.values() {
        result.edges.extend(edge_pieces.iter().cloned());
    }

    // id -> source edge, built once. The per-coedge `solid.edges.iter().find`
    // below was O(edges) inside the face/loop/coedge loops. `solid` is the
    // immutable source, so the lookup returns the identical record.
    let source_edges: HashMap<u64, &EdgeRecord> =
        solid.edges.iter().map(|edge| (edge.id, edge)).collect();

    for face in result
        .shells
        .iter_mut()
        .flat_map(|shell| shell.faces.iter_mut())
    {
        for loop_record in &mut face.loops {
            let mut rebuilt = Vec::new();
            for coedge in &loop_record.coedges {
                let Some(edge_pieces) = pieces.get(&coedge.edge_id) else {
                    rebuilt.push(coedge.clone());
                    continue;
                };
                let original = *source_edges
                    .get(&coedge.edge_id)
                    .ok_or_else(|| "apply_edge_splits: missing source edge".to_string())?;
                let span = original.t1 - original.t0;
                let indices: Box<dyn Iterator<Item = usize>> = if coedge.forward {
                    Box::new(0..edge_pieces.len())
                } else {
                    Box::new((0..edge_pieces.len()).rev())
                };
                for index in indices {
                    let piece = &edge_pieces[index];
                    let start_fraction = if coedge.forward {
                        (piece.t0 - original.t0) / span
                    } else {
                        (original.t1 - piece.t1) / span
                    };
                    let end_fraction = if coedge.forward {
                        (piece.t1 - original.t0) / span
                    } else {
                        (original.t1 - piece.t0) / span
                    };
                    rebuilt.push(CoedgeRecord {
                        id: next_coedge_id,
                        edge_id: piece.id,
                        forward: coedge.forward,
                        pcurve: subcurve_by_fraction(&coedge.pcurve, start_fraction, end_fraction)?,
                    });
                    next_coedge_id += 1;
                }
            }
            loop_record.coedges = rebuilt;
        }
    }
    let map = pieces
        .iter()
        .map(|(source_id, edge_pieces)| {
            (
                *source_id,
                edge_pieces.iter().map(|piece| piece.id).collect(),
            )
        })
        .collect();
    Ok((result, map))
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{build_imprints, make_box_brep, ImprintOptions};

    #[test]
    fn split_edges_keep_each_solid_manifold_and_pcurves_aligned() {
        let first = make_box_brep(Vec3::default(), 4.0, 4.0, 4.0).unwrap();
        let second = make_box_brep(Vec3::new(2.0, 1.0, 1.0), 4.0, 4.0, 4.0).unwrap();
        let imprint = build_imprints(&first, &second, &ImprintOptions::default()).unwrap();
        let split_first = apply_edge_splits(&first, 0, &imprint).unwrap();
        let split_second = apply_edge_splits(&second, 1, &imprint).unwrap();
        assert!(split_first.validate().is_empty());
        assert!(split_second.validate().is_empty());
        assert!(
            split_first.edges.len() > first.edges.len()
                || split_second.edges.len() > second.edges.len()
        );
    }
}