klyff_msdf 0.1.3

mod intersection;
mod recolor;
mod validity;

use glam::Vec2;
use recolor::RecolorVisit;

use crate::{Aabb, math_curve::are_very_close_points, math_segment::Segment};

const EPS: f32 = 1e-6;

#[derive(Default)]
pub(crate) struct IntersectRemoveState {
    visited: Vec<bool>,
    stack: Vec<RecolorVisit>,
    splits: Vec<Split>,
    valid_segment: Vec<bool>,
}

#[derive(Debug, Clone, Copy)]
struct Split {
    seg_index: usize,
    t: f32,
    pos: Vec2,
}

/// Split intersecting segments and discard edges that do not contribute to shape outline.
pub(crate) fn remove_intersecting_shapes(
    segments: &mut Vec<Segment>,
    state: &mut IntersectRemoveState,
) -> f32 {
    let mut shape_closest_distance_sqr = f32::MAX;
    state.splits.clear();

    // collect intersections
    for (i, seg) in segments.iter().enumerate() {
        let aabb = Aabb::from_segment(*seg);
        visit_bvh(segments, &|node_aabb| node_aabb.overlap(&aabb), &mut |j| {
            if j <= i {
                return;
            }
            let s2 = segments[j];
            match intersection::segment_intersection(seg.from, seg.to, s2.from, s2.to) {
                intersection::SegmentIntersection::Parallel => {}
                intersection::SegmentIntersection::Colinear => {}
                intersection::SegmentIntersection::NonIntersecting {
                    closest_distance_sqr,
                } => {
                    shape_closest_distance_sqr =
                        shape_closest_distance_sqr.min(closest_distance_sqr);
                }
                intersection::SegmentIntersection::Intersect { s1_t, s2_t, pos } => {
                    state.splits.push(Split {
                        seg_index: i,
                        t: s1_t,
                        pos,
                    });
                    state.splits.push(Split {
                        seg_index: j,
                        t: s2_t,
                        pos,
                    });
                }
            }
        });
    }

    if state.splits.is_empty() {
        return shape_closest_distance_sqr;
    }

    state
        .splits
        .sort_by(|x, y| match x.seg_index.cmp(&y.seg_index) {
            std::cmp::Ordering::Equal => x.t.total_cmp(&y.t).reverse(),
            cmp => cmp,
        });
    state
        .splits
        .dedup_by(|x, y| are_very_close_points(x.pos, y.pos) && x.seg_index == y.seg_index);

    let len_before_split = segments.len();

    // split segments at intersections
    for i in 0..state.splits.len() {
        let Split { seg_index, pos, .. } = state.splits[i];
        let seg = segments[seg_index];
        // TODO: All quads are flattened to line segment. We accepts a small loss in fidelity for now.
        let (seg1, seg2) = seg.split_at(pos);
        segments[seg_index] = seg1;
        segments.push(seg2);
    }

    state.valid_segment.resize(segments.len(), false);
    let mut s = "".to_string();
    for i in 0..segments.len() {
        state.valid_segment[i] = validity::is_valid_segment(i, segments, len_before_split);
        s.push_str(&format!("{:?} - {}\n", segments[i], state.valid_segment[i]));
    }
    for i in (0..segments.len()).rev() {
        if !state.valid_segment[i] {
            segments.remove(i);
        }
    }

    if segments.is_empty() {
        panic!("{s}");
    }
    recolor::recolor(segments, state);

    shape_closest_distance_sqr
}

// TEMP: BVH-free brute scan for bench comparison. Per-segment AABB test
// preserves the same filter semantics callers had before.
fn visit_bvh(segments: &[Segment], test: &impl Fn(&Aabb) -> bool, process: &mut impl FnMut(usize)) {
    for (i, seg) in segments.iter().enumerate() {
        let aabb = Aabb::from_segment(*seg);
        if test(&aabb) {
            process(i);
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use proptest::prelude::*;

    use crate::{math_segment::Segment, polygon_clipping::intersection::SegmentIntersection};

    proptest! {
        #[test]
        fn random_polygons(segments in Segment::arbitrary_poly_multi(0.2, 1..10, 3..15)) {
            test_random_polygons(segments);
        }
    }
    fn test_random_polygons(mut segs: Vec<Segment>) {
        let mut state = IntersectRemoveState::default();
        remove_intersecting_shapes(&mut segs, &mut state);

        let mut intersection = vec![];
        for (i, seg) in segs.iter().enumerate() {
            let aabb = Aabb::from_segment(*seg);
            visit_bvh(&segs, &|seg_aabb| seg_aabb.overlap(&aabb), &mut |j| {
                if j <= i {
                    return;
                }
                let s2 = segs[j];
                if let SegmentIntersection::Intersect { pos, s1_t, s2_t } =
                    intersection::segment_intersection(seg.from, seg.to, s2.from, s2.to)
                {
                    let eps = 1e-3;
                    if (seg.from.distance(pos) > eps && seg.to.distance(pos) > eps)
                        && (s2.from.distance(pos) > eps && s2.to.distance(pos) > eps)
                    {
                        intersection.push((seg, s2, pos, s1_t, s2_t));
                    }
                }
            });
        }

        let mut l = "".to_string();
        for seg in segs.iter() {
            l.push_str(&format!("{seg:?}\n"));
        }
        assert!(
            intersection.is_empty(),
            "There are still intersections left: {intersection:?}\n----\n{l}",
        );
    }
}