use crate::core::boolean_geom::{merge_two_closed_rings_at_cut, split_closed_ring_at_indices};
use crate::core::{
extract_segments, hit_test_segments, split_contour_segment, ContourSegment, FontPoint, Node,
NodeId, NodeType,
};
use crate::tokens::{
KNIFE_CUBIC_SUBDIVISIONS, KNIFE_MIN_DRAG_UPM, KNIFE_PARAM_DEDUP_EPS, KNIFE_SEG_T_MAX,
KNIFE_SEG_T_MIN, SNAP_LINE_INTERSECT_DET_EPS,
};
use kurbo::ParamCurve;
#[must_use]
pub fn constrain_knife_endpoint(start: FontPoint, raw: FontPoint, shift: bool) -> FontPoint {
if !shift {
return raw;
}
let dx = (raw.x.0 - start.x.0).abs();
let dy = (raw.y.0 - start.y.0).abs();
if dx > dy {
FontPoint::new(raw.x.0, start.y.0)
} else {
FontPoint::new(start.x.0, raw.y.0)
}
}
#[must_use]
pub fn intersect_finite_segments(
a0: FontPoint,
a1: FontPoint,
b0: FontPoint,
b1: FontPoint,
) -> Option<(f64, f64, FontPoint)> {
let r_x = a1.x.0 - a0.x.0;
let r_y = a1.y.0 - a0.y.0;
let s_x = b1.x.0 - b0.x.0;
let s_y = b1.y.0 - b0.y.0;
let det = r_x * s_y - r_y * s_x;
if det.abs() <= SNAP_LINE_INTERSECT_DET_EPS {
return None;
}
let qp_x = b0.x.0 - a0.x.0;
let qp_y = b0.y.0 - a0.y.0;
let u = (qp_x * s_y - qp_y * s_x) / det;
let v = (qp_x * r_y - qp_y * r_x) / det;
let range = -KNIFE_PARAM_DEDUP_EPS..=(1.0 + KNIFE_PARAM_DEDUP_EPS);
if range.contains(&u) && range.contains(&v) {
let u_clamped = u.clamp(0.0, 1.0);
let v_clamped = v.clamp(0.0, 1.0);
Some((
u_clamped,
v_clamped,
FontPoint::new(a0.x.0 + u_clamped * r_x, a0.y.0 + u_clamped * r_y),
))
} else {
None
}
}
#[must_use]
pub fn contour_intersections_with_segment(
nodes: &[Node],
closed: bool,
start: FontPoint,
end: FontPoint,
) -> Vec<(f64, FontPoint)> {
let mut hits: Vec<(f64, FontPoint)> = Vec::new();
for seg in extract_segments(nodes, closed) {
match seg {
ContourSegment::Line { line, .. } => {
let b0 = FontPoint::new(line.p0.x, line.p0.y);
let b1 = FontPoint::new(line.p1.x, line.p1.y);
if let Some((u, _v, pt)) = intersect_finite_segments(start, end, b0, b1) {
hits.push((u, pt));
}
}
ContourSegment::Cubic { cubic, .. } => {
let n = KNIFE_CUBIC_SUBDIVISIONS;
for step in 0..n {
let t0 = step as f64 / n as f64;
let t1 = (step + 1) as f64 / n as f64;
let p0 = cubic.eval(t0);
let p1 = cubic.eval(t1);
let b0 = FontPoint::new(p0.x, p0.y);
let b1 = FontPoint::new(p1.x, p1.y);
if let Some((u, v_sub, _)) = intersect_finite_segments(start, end, b0, b1) {
let t_exact = (t0 + v_sub * (t1 - t0)).clamp(0.0, 1.0);
let p_exact = cubic.eval(t_exact);
hits.push((u, FontPoint::new(p_exact.x, p_exact.y)));
}
}
}
}
}
hits.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
let mut deduped: Vec<(f64, FontPoint)> = Vec::with_capacity(hits.len());
for (u, pt) in hits {
if deduped.last().is_none_or(|(prev_u, prev_pt)| {
(u - *prev_u).abs() > KNIFE_PARAM_DEDUP_EPS
&& pt.distance_to(*prev_pt) > KNIFE_MIN_DRAG_UPM
}) {
deduped.push((u, pt));
}
}
deduped
}
fn resolve_or_insert_cut_node(
contour: &mut Vec<Node>,
closed: bool,
pt: FontPoint,
next_node_id: &mut u64,
) -> Option<NodeId> {
if let Some(existing) = contour.iter().find(|n| {
n.node_type != NodeType::OffCurve && n.point.distance_to(pt) <= KNIFE_MIN_DRAG_UPM
}) {
return Some(existing.id);
}
let seg_hit = hit_test_segments(std::slice::from_ref(contour), &[closed], pt, 2.0)?;
let t_clamped = seg_hit.t.clamp(KNIFE_SEG_T_MIN, KNIFE_SEG_T_MAX);
Some(split_contour_segment(
contour,
seg_hit.segment,
t_clamped,
next_node_id,
))
}
#[must_use]
pub fn compute_knife_intersections(
contours: &[Vec<Node>],
closed_flags: &[bool],
start: FontPoint,
end: FontPoint,
) -> Vec<FontPoint> {
let mut all_hits: Vec<(f64, FontPoint)> = Vec::new();
for (c_idx, nodes) in contours.iter().enumerate() {
let closed = closed_flags.get(c_idx).copied().unwrap_or(true);
all_hits.extend(contour_intersections_with_segment(
nodes, closed, start, end,
));
}
all_hits.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
all_hits.into_iter().map(|(_, pt)| pt).collect()
}
pub fn knife_add_nodes_in_layer(
contours: &mut [Vec<Node>],
closed_flags: &[bool],
start: FontPoint,
end: FontPoint,
next_node_id: &mut u64,
) -> Vec<NodeId> {
let mut inserted = Vec::new();
for (c_idx, contour) in contours.iter_mut().enumerate() {
let closed = closed_flags.get(c_idx).copied().unwrap_or(true);
let hits = contour_intersections_with_segment(contour, closed, start, end);
for (_, pt) in hits {
if let Some(id) = resolve_or_insert_cut_node(contour, closed, pt, next_node_id) {
if !inserted.contains(&id) {
inserted.push(id);
}
}
}
}
inserted
}
pub fn knife_cut_paths_in_layer(
contours: &mut Vec<Vec<Node>>,
closed_flags: &mut Vec<bool>,
start: FontPoint,
end: FontPoint,
next_node_id: &mut u64,
) -> bool {
let mut new_contours: Vec<Vec<Node>> = Vec::with_capacity(contours.len() + 2);
let mut new_closed: Vec<bool> = Vec::with_capacity(closed_flags.len() + 2);
let mut touched_closed: Vec<Vec<Node>> = Vec::new();
let mut closed_hits: Vec<(f64, FontPoint, NodeId)> = Vec::new();
let mut mutated = false;
for (c_idx, orig_contour) in contours.iter().enumerate() {
let is_closed = closed_flags.get(c_idx).copied().unwrap_or(true);
let hits = contour_intersections_with_segment(orig_contour, is_closed, start, end);
if hits.is_empty() {
new_contours.push(orig_contour.clone());
new_closed.push(is_closed);
continue;
}
mutated = true;
let mut working = orig_contour.clone();
let mut cut_ids: Vec<(f64, FontPoint, NodeId)> = Vec::with_capacity(hits.len());
for (u, pt) in &hits {
if let Some(id) = resolve_or_insert_cut_node(&mut working, is_closed, *pt, next_node_id)
{
if !cut_ids.iter().any(|(_, _, cid)| *cid == id) {
cut_ids.push((*u, *pt, id));
}
}
}
if is_closed {
closed_hits.extend(cut_ids);
touched_closed.push(working);
} else {
let mut pieces = vec![working];
for (_, _, cid) in cut_ids {
if let Some(p_idx) = pieces.iter().position(|p| {
p.iter().position(|n| n.id == cid).is_some_and(|i| {
i > 0 && i + 1 < p.len() && p[i].node_type != NodeType::OffCurve
})
}) {
let piece = pieces.remove(p_idx);
let cut_idx = piece.iter().position(|n| n.id == cid).unwrap_or(0);
let mut part1 = piece[..=cut_idx].to_vec();
let mut part2 = piece[cut_idx..].to_vec();
if let Some(last) = part1.last_mut() {
last.node_type = NodeType::Corner;
}
if let Some(first) = part2.first_mut() {
first.id = NodeId(*next_node_id);
*next_node_id += 1;
first.node_type = NodeType::Corner;
}
let count_on = |v: &[Node]| {
v.iter()
.filter(|n| n.node_type != NodeType::OffCurve)
.count()
};
if count_on(&part1) >= 2 {
pieces.push(part1);
}
if count_on(&part2) >= 2 {
pieces.push(part2);
}
}
}
for piece in pieces {
new_contours.push(piece);
new_closed.push(false);
}
}
}
if !touched_closed.is_empty() {
closed_hits.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
let (pairs, remainder) = closed_hits.as_chunks::<2>();
let has_oncurve = |r: &[Node], id: NodeId| {
r.iter()
.any(|n| n.id == id && n.node_type != NodeType::OffCurve)
};
for &[(_, _, id_a), (_, _, id_b)] in pairs {
let pos_a = touched_closed.iter().position(|r| has_oncurve(r, id_a));
let pos_b = touched_closed.iter().position(|r| has_oncurve(r, id_b));
match (pos_a, pos_b) {
(Some(r_a), Some(r_b)) if r_a == r_b => {
let ring = touched_closed.remove(r_a);
let ia = ring.iter().position(|n| n.id == id_a).unwrap_or(0);
let ib = ring.iter().position(|n| n.id == id_b).unwrap_or(0);
if ia != ib {
let (half1, half2) =
split_closed_ring_at_indices(&ring, ia, ib, next_node_id);
touched_closed.push(half1);
touched_closed.push(half2);
} else {
touched_closed.push(ring);
}
}
(Some(r_a), Some(r_b)) => {
let (hi, lo) = if r_a > r_b { (r_a, r_b) } else { (r_b, r_a) };
let ring_hi = touched_closed.remove(hi);
let ring_lo = touched_closed.remove(lo);
let (ring_a, ring_b) = if r_a < r_b {
(ring_lo, ring_hi)
} else {
(ring_hi, ring_lo)
};
let ia = ring_a.iter().position(|n| n.id == id_a).unwrap_or(0);
let ib = ring_b.iter().position(|n| n.id == id_b).unwrap_or(0);
touched_closed.push(merge_two_closed_rings_at_cut(
&ring_a,
ia,
&ring_b,
ib,
start,
end,
next_node_id,
));
}
_ => {}
}
}
if let &[(_, _, id_rem)] = remainder {
if let Some(r_rem) = touched_closed.iter().position(|r| has_oncurve(r, id_rem)) {
let working = touched_closed.remove(r_rem);
if let Some(cut_idx) = working
.iter()
.position(|n| n.id == id_rem && n.node_type != NodeType::OffCurve)
{
let len = working.len();
let mut opened: Vec<Node> = (0..len)
.map(|k| working[(cut_idx + k) % len].clone())
.collect();
opened[0].node_type = NodeType::Corner;
let end_pt = opened[0].point;
let end_id = NodeId(*next_node_id);
*next_node_id += 1;
opened.push(Node::new(end_id, end_pt.x.0, end_pt.y.0, NodeType::Corner));
new_contours.push(opened);
new_closed.push(false);
} else {
touched_closed.push(working);
}
}
}
for ring in touched_closed {
new_contours.push(ring);
new_closed.push(true);
}
}
if mutated {
*contours = new_contours;
*closed_flags = new_closed;
}
mutated
}