AI Flow: Reverse Engineering

//! A track that stops and goes on in line a little further is one track.
//!
//! The reader leans towards splitting: a gap line's loose end is walked on until it meets another barrier, a dome or a via pit in a track reads as a hole in it, a
//! dim stretch falls under the class threshold, and each of these cuts a track in two along its length. Two pieces of one track tell nothing about a net. A piece is
//! joined to the next when the next lies straight ahead of its end, within `MAX_BRIDGE_PX`, has the same width, runs on in the same line, and no detected gap line
//! lies between them. Only a track joins a track: an end that points at a pour, a pad or a crossing track is left as it is.
use crate::raster::Mask;

/// The longest break that is bridged, frame pixels at 40 px/mm: 0.5 mm. Not fitted to a photo: it is shorter than the smallest two-pad part with its pads (an 0201 is
/// 0.6 mm long before its lands), so a bridge can never run from the track at one end of a part to the track at the other, which is the one place where two track
/// ends of different nets regularly face each other in line.
pub const MAX_BRIDGE_PX: i64 = 20;
/// Copper wider than this to each side is a pour, not a track: `trace::POUR_HALF`, 0.35 mm.
const TRACK_HALF_MAX: f32 = crate::trace::POUR_HALF;
/// The next piece's half width against this one's: between 0.6 and 1.6 times, with a pixel of slack. A reading of a 5 px wide track varies by a pixel or two along
/// its length; a track of twice the width is another track.
const WIDTH_LO: f32 = 0.6;
const WIDTH_HI: f32 = 1.6;
/// How far each piece must run in the same line, behind this end and beyond the far one, frame pixels: 0.75 mm, or three half widths if that is more. A track
/// crossing at right angles is as long as it is wide along this line and fails, and so do the short curved pieces the reader makes of hole rings, lugs and the rims of
/// print: of 24 bridges drawn at random from the first try on the hub board's top, with 12 px asked of the far piece only, 3 joined a track and the rest joined such pieces.
const RUN_ON_PX: i64 = 30;
const RUN_ON_SHARE: f32 = 0.8;
/// A break the photo shows to be bare laminate is a break: this many pixels in a row on the line between the two ends that were read and lie at the laminate's
/// level (under `LAMINATE_VALUE` of the way up to copper). 4 px is 0.1 mm, the narrowest gap a board house makes. A dim stretch of track reads 0.3 to 0.5, a gap
/// line's walked-on end has copper under it, and print, glints and pits are not read at all.
const LAMINATE_RUN: usize = 4;
/// A track stands this far above what lies `FLANK_PX` beyond its edge on both sides, in the laminate-to-copper measure, over 6 in 10 of the places looked at:
/// `trace::REAL_STEP`, 0.4 of the separation of the levels. 4 px beyond the edge is the middle of a 0.15 to 0.2 mm clearance.
const FLANK_STEP: f32 = 0.4;
const FLANK_PX: f64 = 4.0;
const LAMINATE_VALUE: f32 = 0.25;

pub struct Bridged { pub count: usize, pub painted: Mask, /// each bridge drawn: from, to, half width, frame pixels
    pub segments: Vec<((i64, i64), (i64, i64), i64)> }

/// Join track pieces across short breaks. `lines`: detected gap lines, which nothing crosses. `value`: each pixel's brightness between the laminate level (0) and
/// the copper level (1); `unseen`: where that was not read.
pub fn bridge(labels: &mut [u32], lines: &Mask, value: &crate::raster::Plane, unseen: &Mask, w: usize, h: usize) -> Bridged {
    let n = w * h;
    let on = Mask { w, h, d: labels.iter().map(|l| *l != 0).collect() };
    let dt = on.not().distance_to_set();
    // the thin parts of the copper, as `trace::split_necks` finds them, and their centre lines
    let wide = Mask { w, h, d: dt.d.iter().map(|v| *v >= TRACK_HALF_MAX).collect() };
    let core = wide.dilate(TRACK_HALF_MAX).and(&on);
    let mut skel: Vec<bool> = (0..n).map(|i| on.d[i] && !core.d[i]).collect();
    crate::trace::thin(&mut skel, w, h);
    let at = |x: i64, y: i64| -> Option<usize> { if x < 0 || y < 0 || x >= w as i64 || y >= h as i64 { None } else { Some(y as usize * w + x as usize) } };
    let mut found: Vec<(u32, u32, (i64, i64), (i64, i64), i64)> = vec![];
    for y in 1..h as i64 - 1 { for x in 1..w as i64 - 1 { let e = y as usize * w + x as usize; if !skel[e] { continue; }
        let nb = [e - w - 1, e - w, e - w + 1, e - 1, e + 1, e + w - 1, e + w, e + w + 1].iter().filter(|j| skel[**j]).count(); if nb != 1 { continue; }
        let own = labels[e];
        // which way the track points at this end: from the middle of its last 10 px of centre line to the end
        let (mut sx, mut sy, mut c, mut hw) = (0f64, 0f64, 0f64, 0f32);
        for dy in -10i64..=10 { for dx in -10i64..=10 { if let Some(j) = at(x + dx, y + dy) { if skel[j] && labels[j] == own { sx += (x + dx) as f64; sy += (y + dy) as f64; c += 1.0; hw = hw.max(dt.d[j]); } } } }
        if c < 6.0 || hw < 1.0 { continue; }
        let (ux, uy) = (x as f64 - sx / c, y as f64 - sy / c); let len = (ux * ux + uy * uy).sqrt(); if len < 2.0 { continue; }
        let (ux, uy) = (ux / len, uy / len); let (px, py) = (-uy, ux);
        let pt = |t: f64, s: f64| -> Option<usize> { at((x as f64 + ux * t + px * s).round() as i64, (y as f64 + uy * t + py * s).round() as i64) };
        let side = (hw as f64 / 2.0).max(1.0);
        let (mut gap, mut t) = (0i64, 1i64);
        let hit = loop {
            if gap > MAX_BRIDGE_PX || t > MAX_BRIDGE_PX + 3 * hw as i64 + 8 { break None; }
            let Some(i) = pt(t as f64, 0.0) else { break None };
            if lines.d[i] { break None; }
            if labels[i] == own { t += 1; continue; }
            // the next piece: on the line itself, or just beside it
            let other = [0.0, side, -side].iter().filter_map(|s| pt(t as f64, *s)).map(|j| labels[j]).find(|l| *l != 0 && *l != own);
            if let Some(o) = other { break Some((o, t)); }
            if labels[i] == 0 { gap += 1; }
            t += 1;
        };
        let Some((other, t0)) = hit else { continue };
        if gap == 0 { continue; }
        // the break itself: not bare laminate
        { let (mut run, mut worst) = (0usize, 0usize); for k in 1..t0 { if let Some(i) = pt(k as f64, 0.0) { if labels[i] == 0 && !unseen.d[i] && value.d[i] < LAMINATE_VALUE { run += 1; worst = worst.max(run); } else { run = 0; } } } if worst >= LAMINATE_RUN { continue; } }
        // both pieces stand clear of what lies to each side of them, as a track does and a streak of grain or the rim of a pour does not
        let stands = |from: i64, to: i64, lab: u32, half: f32| -> bool { let (mut ok, mut all) = (0, 0); let off = half as f64 + FLANK_PX;
            let mut k = from; while k <= to { if let (Some(c), Some(a), Some(b)) = (pt(k as f64, 0.0), pt(k as f64, off), pt(k as f64, -off)) { if labels[c] == lab { all += 1;
                if !unseen.d[a] && !unseen.d[b] && !unseen.d[c] && labels[a] != lab && labels[b] != lab && value.d[c] - value.d[a].max(value.d[b]) >= FLANK_STEP { ok += 1; } } } k += 3; }
            all >= 4 && ok * 10 >= all * 6 };
        // this piece runs straight up to its end
        { let back = RUN_ON_PX.max(3 * hw as i64); let n_in = (1..=back).filter(|k| [0.0, side, -side].iter().filter_map(|s| pt(-(*k as f64), *s)).any(|j| labels[j] == own)).count(); if (n_in as f32) < RUN_ON_SHARE * back as f32 { continue; } }
        // the same width, and it runs on in this line
        let run = RUN_ON_PX.max(3 * hw as i64);
        let (mut inside, mut hw2) = (0, 0f32);
        for k in 1..=run { let ok = [0.0, side, -side].iter().filter_map(|s| pt((t0 + k) as f64, *s)).any(|j| labels[j] == other); if ok { inside += 1; }
            for s in [0.0, side, -side] { if let Some(j) = pt((t0 + k) as f64, s) { if labels[j] == other { hw2 = hw2.max(dt.d[j]); } } } }
        if (inside as f32) < RUN_ON_SHARE * run as f32 { continue; }
        if !stands(-RUN_ON_PX.max(3 * hw as i64), -2, own, hw) || !stands(t0 + 2, t0 + run, other, hw2) { continue; }
        if hw2 < WIDTH_LO * hw - 1.0 || hw2 > WIDTH_HI * hw + 1.0 || hw2 >= TRACK_HALF_MAX { continue; }
        found.push((own, other, (x, y), ((x as f64 + ux * (t0 + 1) as f64).round() as i64, (y as f64 + uy * (t0 + 1) as f64).round() as i64), hw.min(hw2).max(1.0) as i64));
    } }
    // join, lowest label kept, and draw each bridge as wide as the narrower piece
    let max = labels.iter().copied().max().unwrap_or(0) as usize;
    let mut root: Vec<u32> = (0..=max as u32).collect();
    fn find(r: &mut [u32], x: u32) -> u32 { let mut a = x; while r[a as usize] != a { a = r[a as usize]; } let mut c = x; while r[c as usize] != a { let nx = r[c as usize]; r[c as usize] = a; c = nx; } a }
    let mut painted = Mask::new(w, h); let mut count = 0;
    let mut todo: Vec<(usize, u32)> = vec![];
    for (a, b, p, q, half) in &found {
        let (ra, rb) = (find(&mut root, *a), find(&mut root, *b)); if ra != rb { root[ra.max(rb) as usize] = ra.min(rb); count += 1; }
        let steps = (q.0 - p.0).abs().max((q.1 - p.1).abs()).max(1);
        for k in 0..=steps { let (cx, cy) = (p.0 + (q.0 - p.0) * k / steps, p.1 + (q.1 - p.1) * k / steps);
            for dy in -half..=*half { for dx in -half..=*half { if dx * dx + dy * dy > half * half { continue; } if let Some(j) = at(cx + dx, cy + dy) { if labels[j] == 0 && !lines.d[j] { todo.push((j, *a)); } } } } }
    }
    for (j, a) in todo { if labels[j] == 0 { labels[j] = a; painted.d[j] = true; } }
    for l in labels.iter_mut() { if *l != 0 { *l = find(&mut root, *l); } }
    Bridged { count, painted, segments: found.iter().map(|f| (f.2, f.3, f.4)).collect() }
}

#[cfg(test)]
mod tests {
    use super::*;
    fn track(l: &mut [u32], w: usize, id: u32, x0: usize, x1: usize, y0: usize, y1: usize) { for y in y0..y1 { for x in x0..x1 { l[y * w + x] = id; } } }
    /// Copper at its level, the break between pieces half way (a dim stretch), everything else laminate.
    fn seen(l: &[u32], w: usize, h: usize) -> crate::raster::Plane { crate::raster::Plane { w, h, d: (0..w * h).map(|i| if l[i] != 0 { 1.0 } else if (37..43).contains(&(i / w)) { 0.45 } else { 0.0 }).collect() } }
    #[test]
    fn a_streak_with_nothing_darker_beside_it_is_not_a_track() {
        let (w, h) = (200usize, 80usize); let mut l = vec![0u32; w * h];
        track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 190, 37, 43);
        assert_eq!(bridge(&mut l, &Mask::new(w, h), &crate::raster::Plane::new(w, h, 0.9), &Mask::new(w, h), w, h).count, 0);
    }
    #[test]
    fn two_pieces_of_one_track_in_line_are_joined_and_drawn() {
        let (w, h) = (200usize, 80usize); let mut l = vec![0u32; w * h];
        track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 190, 37, 43);
        let b = { let v = seen(&l, w, h); bridge(&mut l, &Mask::new(w, h), &v, &Mask::new(w, h), w, h) };
        assert_eq!(b.count, 1);
        assert_eq!(l[40 * w + 50], l[40 * w + 150]);
        assert_ne!(l[40 * w + 95], 0, "the break is drawn");
    }
    #[test]
    fn a_gap_line_between_them_a_long_break_a_wider_piece_and_a_crossing_track_are_not_bridged() {
        let (w, h) = (200usize, 80usize);
        // a detected gap line across the break
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 190, 37, 43);
        let mut lines = Mask::new(w, h); for y in 20..60 { lines.d[y * w + 95] = true; }
        assert_eq!({ let v = seen(&l, w, h); bridge(&mut l, &lines, &v, &Mask::new(w, h), w, h) }.count, 0);
        // 30 px apart: longer than any break this module bridges
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 10, 80, 37, 43); track(&mut l, w, 2, 110, 190, 37, 43);
        assert_eq!({ let v = seen(&l, w, h); bridge(&mut l, &Mask::new(w, h), &v, &Mask::new(w, h), w, h) }.count, 0);
        // the piece ahead is three times as wide
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 190, 30, 50);
        assert_eq!({ let v = seen(&l, w, h); bridge(&mut l, &Mask::new(w, h), &v, &Mask::new(w, h), w, h) }.count, 0);
        // the break reads as bare laminate
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 190, 37, 43);
        assert_eq!(bridge(&mut l, &Mask::new(w, h), &crate::raster::Plane::new(w, h, 0.05), &Mask::new(w, h), w, h).count, 0);
        // a short stub is not a track
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 72, 90, 37, 43); track(&mut l, w, 2, 100, 190, 37, 43);
        assert_eq!({ let v = seen(&l, w, h); bridge(&mut l, &Mask::new(w, h), &v, &Mask::new(w, h), w, h) }.count, 0);
        // a track crossing at right angles ahead
        let mut l = vec![0u32; w * h]; track(&mut l, w, 1, 10, 90, 37, 43); track(&mut l, w, 2, 100, 106, 2, 78);
        assert_eq!({ let v = seen(&l, w, h); bridge(&mut l, &Mask::new(w, h), &v, &Mask::new(w, h), w, h) }.count, 0);
    }
}