AI Flow: Routing

//! Solder mask bridges, as KiCad's DRC reports them. Worked out from its output on the designer's boards
//! and the routed PiProbe, not from a guess:
//!
//!   copper of net A bridges the opening of a pad of net B on the same outer layer when the edge
//!   to edge distance from that copper to the pad's copper is under
//!   pad mask margin + solder_mask_to_copper_clearance.
//!
//! The margin is the pad's own, else the footprint's, else the board's pad_to_mask_clearance. The
//! evidence: on the routed PiProbe (margin 0.102, project 0.1, limit 0.202) a track at 0.171 and a
//! teardrop fill at 0.20002 from a pad are reported; on his v1.3 the same teardrop's fill at 0.2066
//! from the same pad is not; on the benchmark B a via 0.1 from pad J1.B7 is reported, the only one on
//! the board. So a route at the project clearance (0.17) can still bridge a 0.102 pad. Tenting does
//! not change this: the via's own mask does not cover what the pad's opening exposes.
//!
//! Not modelled: openings drawn as F.Mask or B.Mask graphics, and teardrops KiCad has not generated
//! yet. A route with no teardrops in the file gets them at refill, and KiCad's DRC can then report
//! a teardrop that this cannot see in advance.

use crate::board::*;
use crate::geom::*;
use crate::index::*;
use crate::rules::Rules;

pub struct MaskMap {
    /// Added to each pad's limit: a hair under for judging, KiCad's polygon error over for laying.
    slack: f64,
    front: Grid,
    back: Grid,
    last: usize,
    /// Per pad: the limit for foreign copper, margin + mask-to-copper.
    limit: Vec<f64>,
    reach: f64,
}

impl MaskMap {
    pub fn new(board: &Board, rules: &Rules) -> MaskMap {
        let extra = rules.min.mask_to_copper as f64;
        let bb = if board.edges.is_empty() {
            let mut b = (f64::MAX, f64::MAX, f64::MIN, f64::MIN);
            for p in &board.pads {
                let s = p.shape.bbox();
                b = (b.0.min(s.0), b.1.min(s.1), b.2.max(s.2), b.3.max(s.3));
            }
            b
        } else {
            board.bbox
        };
        let mut m = MaskMap { slack: -500.0, front: Grid::new(bb, 1.0 * NM), back: Grid::new(bb, 1.0 * NM), last: board.layers.len() - 1, limit: Vec::with_capacity(board.pads.len()), reach: 0.0 };
        for (i, p) in board.pads.iter().enumerate() {
            let limit = (p.mask_margin + extra).max(0.0);
            m.limit.push(limit);
            // A hole with no copper has an opening too, but nothing of its own to bridge to.
            if p.npth || p.layers.is_empty() {
                continue;
            }
            m.reach = m.reach.max(limit);
            if p.mask.0 && p.layers.contains(&0) {
                m.front.add(p.shape.clone(), p.net, Owner::Pad(i as u32));
            }
            if p.mask.1 && p.layers.contains(&m.last) {
                m.back.add(p.shape.clone(), p.net, Owner::Pad(i as u32));
            }
        }
        m
    }

    /// For laying copper rather than judging it: KiCad tests mask openings as polygons, whose arcs
    /// may sit up to the project's max_error (0.005 mm) off the true curve, so new copper keeps that
    /// much more away. adom/rp2350a-ads1220: two vias placed 0.1899 mm from a rounded pad corner
    /// against a 0.19 mm limit were exact by the arc and bridged by KiCad's polygon.
    pub fn guarded(mut self) -> MaskMap {
        self.slack = 6_000.0;
        self
    }

    /// How much farther than the limit copper being laid keeps from a curve (0 when judging).
    pub fn guard(&self) -> f64 {
        self.slack.max(0.0)
    }

    /// The limit for foreign copper around a pad: route guide lines hug at this distance.
    pub fn limit_of(&self, pad: usize) -> f64 {
        self.limit.get(pad).copied().unwrap_or(0.0)
    }

    fn grid(&self, layer: usize) -> Option<&Grid> {
        if layer == 0 {
            Some(&self.front)
        } else if layer == self.last {
            Some(&self.back)
        } else {
            None
        }
    }

    fn first_hit(&self, net: NetId, also: NetId, layer: usize, bb: (f64, f64, f64, f64), dist: impl Fn(&Shape) -> f64) -> Option<(usize, f64)> {
        self.first_hit_slack(net, also, layer, bb, dist, -500.0)
    }

    fn first_hit_slack(&self, net: NetId, also: NetId, layer: usize, bb: (f64, f64, f64, f64), dist: impl Fn(&Shape) -> f64, slack: f64) -> Option<(usize, f64)> {
        let g = self.grid(layer)?;
        let r = self.reach;
        let mut hit: Option<(usize, f64)> = None;
        let r = r + slack.max(0.0);
        g.visit((bb.0 - r, bb.1 - r, bb.2 + r, bb.3 + r), |o| {
            if o.net == net || (also != NO_NET && o.net == also) {
                return true;
            }
            if let Owner::Pad(i) = o.owner {
                let d = dist(&o.shape);
                if d < self.limit[i as usize] + slack && hit.map(|h| d < h.1).unwrap_or(true) {
                    hit = Some((i as usize, d));
                }
            }
            true
        });
        hit
    }

    pub fn seg_hit(&self, net: NetId, layer: usize, a: V, b: V, half: f64) -> Option<(usize, f64)> {
        self.seg_hit_also(net, NO_NET, layer, a, b, half)
    }

    /// Whether the nearest part of a pad's outline to the segment a-b is a curve the segment passes
    /// at an angle. Only there can KiCad's polygon stand off the true outline: where the segment runs
    /// parallel to a straight side (a track leaving a fine-pitch row between its neighbours) the
    /// polygon and the outline are the same line.
    fn curved_near(shape: &Shape, a: V, b: V, half: f64, d: f64) -> bool {
        let dir = sub(b, a);
        let len = hypot(dir);
        let parallel = |e: V| len > 0.0 && hypot(e) > 0.0 && ((dir.0 * e.1 - dir.1 * e.0) / (len * hypot(e))).abs() < 0.02;
        match shape {
            Shape::Circle { .. } => true,
            Shape::Capsule { a: ca, b: cb, r } => !parallel(sub(*cb, *ca)) && (pt_seg(*ca, a, b).min(pt_seg(*cb, a, b)) - r - half) <= d + 200.0,
            Shape::Poly { pts, r } => {
                // A rounded rectangle is stored as its outline with short facets round each corner
                // (board.rs `rect_pts`), radius 0: a corner vertex is one with a short facet beside it.
                let n = pts.len();
                let short = 0.06 * NM;
                (0..n).any(|i| {
                    let v = pts[i];
                    if pt_seg(v, a, b) - r - half > d + 200.0 {
                        return false;
                    }
                    let (e1, e2) = (sub(v, pts[(i + n - 1) % n]), sub(pts[(i + 1) % n], v));
                    if *r > 0.0 {
                        return !parallel(e1) && !parallel(e2);
                    }
                    let (s1, s2) = (hypot(e1) < short, hypot(e2) < short);
                    (s1 || s2) && !((!s1 && parallel(e1)) || (!s2 && parallel(e2)))
                })
            }
            Shape::Multi(parts) => parts.iter().any(|p| Self::curved_near(p, a, b, half, d)),
        }
    }

    /// `seg_hit` for copper shared by a pair: the partner's own pads are not another net's. Starting
    /// between its two pads, every first move of a coupled run met the partner's opening otherwise.
    pub fn seg_hit_also(&self, net: NetId, also: NetId, layer: usize, a: V, b: V, half: f64) -> Option<(usize, f64)> {
        let bb = (a.0.min(b.0) - half, a.1.min(b.1) - half, a.0.max(b.0) + half, a.1.max(b.1) + half);
        if self.slack <= 0.0 {
            return self.first_hit(net, also, layer, bb, |s| (s.dist_seg(a, b) - half).max(0.0));
        }
        // Laying: the guard counts only past a curve (see `curved_near`); a straight side keeps the
        // exact limit. The distance handed back is lifted by the guard where it does not apply, so
        // the one comparison in `first_hit_slack` serves both.
        let slack = self.slack;
        self.first_hit_slack(net, also, layer, bb, |s| {
            let d = (s.dist_seg(a, b) - half).max(0.0);
            if Self::curved_near(s, a, b, half, d) { d } else { d + slack + 500.0 }
        }, slack)
    }

    /// A through via at `at`, radius `r`: tested against the openings on both outer layers.
    pub fn via_hit(&self, net: NetId, at: V, r: f64) -> Option<(usize, f64)> {
        let bb = (at.0 - r, at.1 - r, at.0 + r, at.1 + r);
        let d = |s: &Shape| (s.dist_pt(at) - r).max(0.0);
        // Only vias take the laying guard: a via and a rounded pad corner are both arcs KiCad turns
        // into polygons. A track's sides are straight and exact, and 6 um more on those shut the
        // escapes of a 0.4 mm pitch part (rp2350a-ads1220 lost nine joins to it).
        self.first_hit_slack(net, NO_NET, 0, bb, d, self.slack).or_else(|| self.first_hit_slack(net, NO_NET, self.last, bb, d, self.slack))
    }

    /// Copper KiCad hasn't drawn yet, predicted as a polygon: `slack` allows for the prediction.
    pub fn poly_near(&self, net: NetId, layer: usize, pts: &[V], slack: f64) -> Option<(usize, f64)> {
        let poly = Shape::Poly { pts: pts.to_vec(), r: 0.0 };
        let bb = poly.bbox();
        self.first_hit(net, NO_NET, layer, (bb.0 - slack, bb.1 - slack, bb.2 + slack, bb.3 + slack), |s| (poly.dist_shape(s) - slack).max(0.0))
    }

    /// Filled copper given as a polygon, such as a teardrop.
    pub fn poly_hit(&self, net: NetId, layer: usize, pts: &[V]) -> Option<(usize, f64)> {
        let poly = Shape::Poly { pts: pts.to_vec(), r: 0.0 };
        let bb = poly.bbox();
        self.first_hit(net, NO_NET, layer, bb, |s| poly.dist_shape(s))
    }
}