app
AI Flow: Routing
Public Made by Adomby adom
The routing stage of AI Flow: routes a placed KiCad board connection by connection and reports what it made, what it could not and why. A guide, never a gate.
main
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657
//! What makes copper look routed by a person, after the search has found it: a rail's topology
//! (bus on one layer, stubs to pads, taps with a legal shape), and the whole-board optimisation pass
//! (Part 3 step 8) that re-routes each connection once its neighbours are final.
//!
//! The optimisation pass follows the method of Freerouting's BatchOptimizer and TraceTightener and of
//! KiCadRoutingTools' cleanup: remove one connection, search again against the final obstacles, keep
//! the new one only if it is better. Written fresh from that description; no code is taken from them.
use crate::board::*;
use crate::classify::*;
use crate::conn::{touches, Piece, Uf};
use crate::geom::*;
use crate::index::*;
use crate::router::*;
use crate::search::*;
use std::collections::{BTreeMap, HashSet};
use crate::clock::Instant;
/// One connected piece of a net: what a tap may land on.
#[derive(Default, Debug)]
pub struct Comp {
pub pads: Vec<usize>,
pub segs: Vec<(P, P, usize, i64)>,
pub vias: Vec<P>,
pub zones: Vec<usize>,
}
/// How far a via stands off the track it branches from: 4.4's 0.6 to 0.85 mm, lower end.
const VIA_BRANCH: f64 = 0.6 * NM;
const TIGHT_BRANCH: f64 = 0.15 * NM;
/// What a branch off a track costs against reaching the next pad, in vias. A weight: 4.2 prefers a
/// chain and branching off a pad, and gives no number.
const BRANCH_VIAS: f64 = 0.5;
/// Same-net copper this close and parallel is a doubled run, the distance the reviewer's measure uses.
const DOUBLED_REACH: f64 = 0.4;
/// Cost per mm of a doubled run, over its length, so the optimiser takes it out when it can.
const DOUBLED: f64 = 3.0;
/// A rail's load from which one via is not enough. His PiProbe rails (0.177 A, 0.1 A) have none doubled,
/// and his Hardware Calculator's via model puts a 0.3/0.6 via well above that. A working number until
/// rails are sized from current, which needs his chart source.
use crate::current::VIA_PLATING_UM;
impl<'a> Router<'a> {
/// The layer a rail's bus runs on. With a solid plane inside, the bottom layer is free for it;
/// without one the bottom is the return path, so the rail stays on top (2.2, 4.3).
pub(crate) fn bus_of(&self, task: &Task) -> Option<usize> {
if task.zone != Some(RAIL_TAP) {
return None;
}
Some(self.bus_layer())
}
pub(crate) fn bus_layer(&self) -> usize {
let has_plane = !self.board.plane_nets().is_empty();
if has_plane { *self.world.route_layers.last().unwrap() } else { self.world.route_layers[0] }
}
/// The net's copper split into connected pieces, from what is on the board right now.
pub(crate) fn components(&self, net: NetId) -> Vec<Comp> {
self.components_with(net, true)
}
/// `fills` false leaves the net's pours out: pieces joined by tracks, vias and pads alone. For
/// mending a pour that does not in fact join the pads inside its outline.
pub(crate) fn components_with(&self, net: NetId, fills: bool) -> Vec<Comp> {
let skip: HashSet<&str> = self.rules.skip_refs.iter().map(|s| s.as_str()).collect();
let mut pieces: Vec<Piece> = Vec::new();
let mut comp_item: Vec<(u8, usize)> = Vec::new();
for (i, p) in self.board.pads.iter().enumerate() {
let f = &self.board.footprints[p.fp];
if p.net == net && !p.layers.is_empty() && !skip.contains(f.reference.as_str()) {
pieces.push(Piece::Pad(i));
comp_item.push((0, i));
}
}
let mut segs: Vec<(P, P, usize, i64)> = Vec::new();
let mut vias: Vec<P> = Vec::new();
for t in self.board.tracks.iter().filter(|t| t.net == net) {
segs.push((t.a, t.b, t.layer, t.width));
}
for v in self.board.vias.iter().filter(|v| v.net == net) {
vias.push(v.at);
}
for r in self.routes.values().filter(|r| r.task.net == net) {
for s in &r.segs {
segs.push((s.a, s.b, s.layer, s.width));
}
vias.extend(r.vias.iter().copied());
}
for (i, s) in segs.iter().enumerate() {
pieces.push(Piece::Seg { layer: s.2, a: s.0.into(), b: s.1.into(), r: s.3 as f64 / 2.0 });
comp_item.push((1, i));
}
let vr = self.rules.via as f64 / 2.0;
for (i, v) in vias.iter().enumerate() {
pieces.push(Piece::Via { at: (*v).into(), r: vr });
comp_item.push((2, i));
}
for (z, (zn, layer, poly)) in self.world.zones.iter().enumerate() {
if *zn == net && fills {
pieces.push(Piece::Fill { layer: *layer, pts: poly.clone() });
comp_item.push((3, z));
}
}
let mut uf = Uf::new(pieces.len());
for i in 0..pieces.len() {
for j in i + 1..pieces.len() {
if uf.find(i as u32) != uf.find(j as u32) && touches(&pieces[i], &pieces[j], self.board) {
uf.union(i as u32, j as u32);
}
}
}
let mut by: BTreeMap<u32, Comp> = BTreeMap::new();
for i in 0..pieces.len() {
let c = by.entry(uf.find(i as u32)).or_default();
let (kind, k) = comp_item[i];
match kind {
0 => c.pads.push(k),
1 => c.segs.push(segs[k]),
2 => c.vias.push(vias[k]),
_ => c.zones.push(k),
}
}
by.into_values().collect()
}
pub(crate) fn comp_terminals(&self, c: &Comp, stand_off: f64, out: &mut Vec<Terminal>) {
// A Kelvin tap is dedicated copper (4.2): nothing else on the net may land on it.
let tap_pads: HashSet<usize> = self.routes.values().filter(|r| r.task.level == Level::Kelvin).flat_map(|r| [r.task.a, r.task.b]).collect();
let tap_segs: HashSet<(P, P)> = self.routes.values().filter(|r| r.task.level == Level::Kelvin).flat_map(|r| r.segs.iter().map(|s| (s.a, s.b))).collect();
let amp_pin = |p: usize| tap_pads.contains(&p) && !crate::classify::is_passive2(self.board, self.board.pads[p].fp);
for &p in &c.pads {
if !amp_pin(p) {
out.push(self.pad_terminal(p));
}
}
for &z in &c.zones {
let (_, layer, poly) = &self.world.zones[z];
out.push(Terminal::Zone { layer: *layer, poly: poly.clone() });
}
for s in &c.segs {
if s.0 != s.1 && !tap_segs.contains(&(s.0, s.1)) {
out.push(Terminal::Track { a: s.0, b: s.1, layer: s.2, wide: s.3 >= self.rules.power_floor, stand_off });
}
}
// A via joins from the stub side only. On the bus layer the tap lands on the track, where its
// shape is checked: landing on the via could fold back acutely or put the via inside a run.
// Nor where a stub already ends on it: that stub is the place to join, angle checked.
let bus = self.bus_layer();
for v in &c.vias {
let layers: Vec<usize> = self.world.route_layers.iter().copied().filter(|&l| l != bus && !c.segs.iter().any(|s| s.2 == l && (s.0 == *v || s.1 == *v))).collect();
if !layers.is_empty() {
out.push(Terminal::Point { p: *v, layers });
}
}
}
/// What a rail task may land on. A pin's stub (`a != b`, not main) lands on its cap's own pad: cap
/// first (4.2). The trunk lands on anything joined to pad `b`. Otherwise any of the net's copper
/// not yet joined to pad `a`. Empty when there is nothing left to join.
pub(crate) fn rail_targets(&self, task: &Task, stand_off: f64) -> Vec<Terminal> {
let comps = self.components(task.net);
let own = comps.iter().position(|c| c.pads.contains(&task.a));
let mut out = Vec::new();
if task.a != task.b {
match comps.iter().position(|c| c.pads.contains(&task.b)) {
Some(i) if Some(i) != own => {
if task.main {
self.comp_terminals(&comps[i], stand_off, &mut out);
} else {
out.push(self.pad_terminal(task.b));
}
}
_ => {}
}
return out;
}
// A planned rail's tap lands only on its own part's pads and on the copper of the parts
// above it in the plan's tree (power.rs): the branch currents the widths were worked out
// from are then the currents in the copper. If none of that is laid yet it lands as below.
// A planned rail grows from its source: only a piece that already holds a source pad is
// landed on. (Two parts not yet joined to the source could otherwise join each other and
// stay apart from it: benchmark C's R46 and C30 on +5V_OUT did, 2026-11-10.)
let live: Vec<usize> = match (self.power.pads.contains_key(&task.a), self.power.sources.get(&task.net)) {
(true, Some(src)) => (0..comps.len()).filter(|&i| Some(i) != own && comps[i].pads.iter().any(|p| src.contains(p))).collect(),
_ => Vec::new(),
};
if let Some(pp) = self.power.pads.get(&task.a).filter(|pp| pp.anywhere && !live.is_empty()) {
let _ = pp;
for &i in &live {
self.comp_terminals(&comps[i], stand_off, &mut out);
}
return out;
}
if let Some(pp) = self.power.pads.get(&task.a).filter(|pp| !pp.anywhere) {
let segs: HashSet<(P, P, usize)> = self.routes.values().filter(|r| r.task.net == task.net && pp.allowed.contains(&r.task.a)).flat_map(|r| r.segs.iter().map(|s| (s.a, s.b, s.layer))).collect();
let vias: HashSet<P> = self.routes.values().filter(|r| r.task.net == task.net && pp.allowed.contains(&r.task.a)).flat_map(|r| r.vias.iter().copied()).collect();
for (i, c) in comps.iter().enumerate() {
if Some(i) != own && (live.is_empty() || live.contains(&i)) {
let only = Comp { pads: c.pads.iter().copied().filter(|x| pp.allowed.contains(x)).collect(), segs: c.segs.iter().copied().filter(|s| segs.contains(&(s.0, s.1, s.2)) || segs.contains(&(s.1, s.0, s.2))).collect(), vias: c.vias.iter().copied().filter(|v| vias.contains(v)).collect(), zones: c.zones.clone() };
self.comp_terminals(&only, stand_off, &mut out);
}
}
if !out.is_empty() {
return out;
}
}
// Every task joins its piece to one other, whichever is nearest, fills included: a fill is
// the natural hub. There is one task per piece, so the net ends up whole either way.
for (i, c) in comps.iter().enumerate() {
if Some(i) != own {
self.comp_terminals(c, stand_off, &mut out);
}
}
out
}
/// Route one rail task: from the pad, down its stub to the bus layer, along the bus to the
/// target. Widths step down only when there is no room, and `rail_notes` reports any that did.
/// True if joined, including when there was nothing left to join.
pub(crate) fn try_rail(&mut self, task: &Task) -> bool {
if self.rail_targets(task, 0.0).is_empty() {
return true;
}
self.rail_route_guarded(task).is_some()
}
/// `rail_route` behind its two guards; every caller goes through here (the first pass, the rail
/// repair and repair's `route_hard`, which used to call the search directly and so ran it without
/// either guard: on adom/esc-g431 that was where one tap got its 565 searches).
pub(crate) fn rail_route_guarded(&mut self, task: &Task) -> Option<u32> {
// A tap that found no way is not searched again until something near it, or its own net's
// copper, has changed: the whole ladder of widths and margins would only fail the same way.
let key = (task.a, task.b);
let stamp = self.rail_stamp(task);
if self.rail_walled.get(&key) == Some(&stamp) {
return None;
}
// And never more than a few times in one run, whatever changed round it: repair lifts and
// re-lays its neighbours over and over, each time a new state, each time the same ladder.
let tries = self.rail_tries.entry(key).or_insert(0);
if *tries >= if self.deep { RAIL_TRIES + 3 } else { RAIL_TRIES } {
return None;
}
*tries += 1;
let made = self.rail_route(task);
if made.is_some() {
self.rail_walled.remove(&key);
} else {
self.rail_walled.insert(key, stamp);
}
made
}
// (RAIL_TRIES is defined at the top of router.rs.)
/// What a rail tap's search depends on, as one number: the routes within 6 mm of its pad and
/// every route of its own net, by id (a route laid again has a new id).
fn rail_stamp(&self, task: &Task) -> u64 {
let c = self.board.pads[task.a].center;
let r = mm(6.0);
let near = |p: P| (p.0 - c.0).abs() <= r && (p.1 - c.1).abs() <= r;
let mut ids: Vec<(u32, usize, usize)> = self.routes.values().filter(|x| x.task.net == task.net || x.segs.iter().any(|s| near(s.a) || near(s.b)) || x.vias.iter().any(|v| near(*v))).map(|x| (x.id, x.segs.len(), x.vias.len())).collect();
ids.sort_unstable();
let mut h: u64 = 0xcbf29ce484222325 ^ (self.deep as u64) ^ ((self.rules.node_limit as u64) << 8);
for (id, a, b) in ids {
for v in [id as u64, a as u64, b as u64] {
h = (h ^ v).wrapping_mul(0x100000001b3);
}
}
h
}
/// The ways a rail task can be made: from its own pads to the other copper, or from the other
/// pads to its own copper. The second matters when its own piece already holds a long bus or a
/// fill: that copper can't be a place to start from, so a route from the pad alone would cross the
/// board to reach something a stub from the far side joins in 3 mm (piprobe_v13: +3V3 across U1).
fn rail_ways(&self, task: &Task, stand_off: f64) -> Vec<(Vec<Terminal>, Vec<Terminal>)> {
let targets = self.rail_targets(task, stand_off);
if targets.is_empty() {
return Vec::new();
}
let mut ways = vec![(vec![self.pad_terminal(task.a)], targets)];
// A pin's stub to its own cap goes pin to cap and nowhere else (4.2).
if task.a != task.b && !task.main {
return ways;
}
let comps = self.components(task.net);
let Some(own) = comps.iter().position(|c| c.pads.contains(&task.a)) else { return ways };
let is_trunk = task.a != task.b;
let others: Vec<usize> = comps.iter().enumerate().filter(|(i, c)| *i != own && (!is_trunk || c.pads.contains(&task.b))).flat_map(|(_, c)| self.feed_pads(c)).collect();
if !others.is_empty() {
let mut back = Vec::new();
self.comp_terminals(&comps[own], stand_off, &mut back);
ways.push((others.iter().map(|&p| self.pad_terminal(p)).collect(), back));
}
ways
}
/// The pads a piece of rail is fed from: its caps if it has any (cap first, 4.2), else all of them.
fn feed_pads(&self, c: &Comp) -> Vec<usize> {
let caps: Vec<usize> = c.pads.iter().copied().filter(|&p| is_passive2(self.board, self.board.pads[p].fp) && ref_prefix(&self.board.footprints[self.board.pads[p].fp].reference) == "C").collect();
if caps.is_empty() { c.pads.clone() } else { caps }
}
/// The route itself, with its id. The task stored is the way it was really made, so that a later
/// re-search starts from the pad this route leaves.
pub(crate) fn rail_route(&mut self, task: &Task) -> Option<u32> {
let bus = self.bus_layer();
let (w, stub) = self.widths_for(task);
let (neck, c, floor) = (self.rules.neck, self.rules.clearance_for(task.net, task.net), self.rules.power_floor);
// The margin also sets the node budget (search.rs pf_limit). A rail's targets usually span the
// board already, so the small budgets come first and only the last search may be expensive.
let tries = [
(w, stub, 2, 5.0 * NM, VIA_BRANCH),
(w, stub, 2, 5.0 * NM, 0.0),
(w, neck, 2, 5.0 * NM, 0.0),
(w.min(floor), neck, 3, 5.0 * NM, 0.0),
(stub, neck, 4, 5.0 * NM, 0.0),
(neck, neck, 4, 40.0 * NM, 0.0),
// Last resort, and his own bus has one: a via on the track itself (4.4 prefers not).
(neck, neck, 4, 40.0 * NM, -1.0),
];
// (A probe of the last rung right after the first failure was tried on 2026-11-10 and taken
// out: on a flight controller board the probe ran out of nodes instead of closing, so it proved
// nothing and only added work, 124 -> 121 joins.)
for (width, nk, vias, margin, off) in tries {
if self.over_time() {
return None;
}
let pf = Profile { width, neck: nk, clearance: c, target_gap: c, max_vias: vias, margin, layer_bias: Some(bus) };
let mut best: Option<Path> = None;
for (sources, targets) in self.rail_ways(task, off) {
let q = Query { net: task.net, also: None, sources: &sources, targets: &targets, profile: pf, rules: &self.rules, soft: None, via_in: None, history: Some(&self.history), free: &[], arrive: None };
self.searches += 1;
let t0 = Instant::now();
let found = search(&self.world, &q);
if std::env::var_os("ADOM_ROUTE_TRACE").is_some() {
eprintln!(" rail {} w={:.2} stub={:.2} vias={} margin={:.1} off={:.1}: {} sources, {} targets, {} in {:.2}s", self.board.pad_name(task.a), to_mm(width), to_mm(nk), vias, margin / NM, off / NM, sources.len(), targets.len(), if let Some(f) = &found { format!("found cost {:.1} nodes {}", f.cost / NM, f.nodes) } else { "none".to_string() }, t0.elapsed().as_secs_f64());
}
if let Some(path) = found {
self.nodes += path.nodes as u64;
if best.as_ref().map(|b| path.cost < b.cost).unwrap_or(true) {
best = Some(path);
}
}
}
if let Some(path) = best {
let made = self.task_as_made(task, &path);
let pts = self.finish_path_on(&path, task.net, NO_NET, &|l| if l == bus { width } else { nk });
return Some(self.commit_rail(&made, &pts, width, nk));
}
}
None
}
/// `task` as this path really made it: from the pad it starts at.
fn task_as_made(&self, task: &Task, path: &Path) -> Task {
let start = path.pts.first().map(|x| x.0);
let pad = self.board.pads.iter().position(|p| p.net == task.net && Some(snap(p.center)) == start);
match pad {
Some(p) if p != task.a && task.a == task.b => Task { a: p, b: p, ..task.clone() },
_ => task.clone(),
}
}
/// A rail's copper: the bus-layer part at the width it was searched at wherever that is legal,
/// the rest at the stub width. A piece inside the net's own fill stays: the fill in the file is the
/// old one, and on benchmark C a via left to rely on it came out of KiCad's refill stranded.
pub(crate) fn commit_rail(&mut self, task: &Task, pts: &[(P, usize)], width: i64, neck: i64) -> u32 {
let id = self.fresh_id();
let bus = self.bus_layer();
let rated = width > neck && self.rules.rail(self.board.net_name(task.net)).is_some();
let (mut segs, mut vias) = (Vec::new(), Vec::new());
for w in pts.windows(2) {
let ((a, la), (b, lb)) = (w[0], w[1]);
if la != lb {
if a == b {
vias.push(a);
}
continue;
}
if a == b {
continue;
}
// An approved current: full width on any layer, narrowed only over the stretch that
// lacks the room (the taper into a small pad), and there to the widest that fits. Drawn
// whole-segment and bus-layer-only, benchmark C's +5V to U10 ran 33.6 mm at 0.20 mm on B.Cu.
if rated {
for (p0, p1, wd) in self.taper(a, b, la, width, neck, task.net) {
segs.push(Seg { a: p0, b: p1, layer: la, width: wd });
}
continue;
}
let mut use_w = neck.min(width);
if la == bus {
for cand in [width, self.rules.power_floor.min(width)] {
if self.seg_clear(a, b, la, cand, task.net, NO_NET) {
use_w = cand;
break;
}
}
}
segs.push(Seg { a, b, layer: la, width: use_w });
}
merge_runs(&mut segs);
self.place(id, task.clone(), segs, vias);
if task.a == task.b && self.power.pads.get(&task.a).map(|p| !p.anywhere).unwrap_or(false) {
self.rail_laid.insert((task.a, task.b));
}
id
}
/// The widest width from `lo` (taken as clear) up to `hi` at which this stretch is clear, to 10 um.
pub(crate) fn widest_clear(&self, a: P, b: P, layer: usize, lo: i64, hi: i64, net: NetId) -> i64 {
if hi <= lo || self.seg_clear(a, b, layer, hi, net, NO_NET) {
return hi.max(lo);
}
let (mut lo, mut hi) = (lo, hi);
while hi - lo > 10_000 {
let mid = ((lo + hi) / 2 / 2_000) * 2_000;
if mid <= lo || mid >= hi {
break;
}
if self.seg_clear(a, b, layer, mid, net, NO_NET) {
lo = mid;
} else {
hi = mid;
}
}
lo
}
/// One straight run of a rated rail cut into stretches, each at the widest width that is clear
/// there: the full width wherever it fits, and across a stretch that lacks the room the widest
/// of a few steps down to the neck. Stretches are found in 0.1 mm steps along the run.
pub(crate) fn taper(&self, a: P, b: P, layer: usize, width: i64, neck: i64, net: NetId) -> Vec<(P, P, i64)> {
if self.seg_clear(a, b, layer, width, net, NO_NET) {
return vec![(a, b, width)];
}
let len = (a.0 - b.0).abs().max((a.1 - b.1).abs());
let d = ((b.0 - a.0).signum(), (b.1 - a.1).signum());
let at = |t: i64| -> P { if t >= len { b } else { (a.0 + d.0 * t, a.1 + d.1 * t) } };
let step = 100_000i64;
let n = ((len + step - 1) / step).max(1);
let mut steps: Vec<i64> = vec![width];
let mut wd = width;
while wd / 2 > neck {
wd = (wd / 2 / 10_000) * 10_000;
steps.push(wd);
}
steps.push(neck.min(width));
// The widest step each 0.1 mm piece can take.
let fit: Vec<i64> = (0..n).map(|k| {
let (p0, p1) = (at(k * step), at((k + 1) * step));
steps.iter().copied().find(|&s| self.seg_clear(p0, p1, layer, s, net, NO_NET)).unwrap_or(neck.min(width))
}).collect();
// Pieces of one width join into one stretch; a stretch shorter than it is wide takes its
// narrower neighbour's width, so the run doesn't flicker between widths.
let mut runs: Vec<(i64, i64, i64)> = Vec::new();
for (k, &f) in fit.iter().enumerate() {
match runs.last_mut() {
Some(r) if r.2 == f => r.1 = k as i64 + 1,
_ => runs.push((k as i64, k as i64 + 1, f)),
}
}
for i in 0..runs.len() {
let short = (runs[i].1 - runs[i].0) * step < runs[i].2;
if short {
let lower = [i.checked_sub(1), Some(i + 1)].into_iter().flatten().filter_map(|j| runs.get(j).map(|r| r.2)).filter(|&w| w < runs[i].2).max();
if let Some(w) = lower {
runs[i].2 = w;
}
}
}
let mut out: Vec<(P, P, i64)> = Vec::new();
for (k0, k1, wd) in runs {
let (p0, p1) = (at(k0 * step), at(k1 * step));
if p0 == p1 {
continue;
}
// Between the step that fits and the one above it, the widest that fits this stretch.
let wd = if wd < width { self.widest_clear(p0, p1, layer, wd, steps.iter().copied().filter(|&s| s > wd).min().unwrap_or(width), net) } else { wd };
match out.last_mut() {
Some(l) if l.2 == wd => l.1 = p1,
_ => out.push((p0, p1, wd)),
}
}
out
}
/// Cut a straight run where it crosses the edge of a fine-pitch escape. Each piece says whether
/// it lies inside. `active` false: the whole run, outside.
pub(crate) fn split_at_escape(&self, a: P, b: P, active: bool) -> Vec<(P, P, bool)> {
if !active {
return vec![(a, b, false)];
}
let len = (a.0 - b.0).abs().max((a.1 - b.1).abs());
let d = ((b.0 - a.0).signum(), (b.1 - a.1).signum());
let at = |t: i64| -> P { (a.0 + d.0 * t, a.1 + d.1 * t) };
let inside = |t: i64| self.world.in_escape(at(t).into());
let step = (0.05 * NM) as i64;
let mut out = Vec::new();
let (mut from, mut state) = (0i64, inside(0));
let mut t = step;
while t < len {
if inside(t) != state {
// Narrow the crossing down to a micron, on an even coordinate, so the run stays exact.
let (mut lo, mut hi) = (t - step, t);
while hi - lo > 2_000 {
let m = ((lo + hi) / 2) & !1;
if inside(m) == state { lo = m } else { hi = m }
}
out.push((at(from), at(hi), state));
from = hi;
state = !state;
}
t += step;
}
out.push((at(from), b, state));
out
}
/// Does this connection land on whatever copper its net has, rather than one pad? On a signal net
/// of three or more pads, a pair's side pads included. A crystal's line stays pad to pad: it must
/// run through the load cap's pad (4.2), and a two-pad net has nothing else to land on.
pub(crate) fn joins_copper(&self, task: &Task) -> bool {
matches!(task.level, Level::Data | Level::Other | Level::Pair) && self.net_info.get(&task.net).map(|(_, p)| p.len() >= 3).unwrap_or(false)
}
/// Everything joined to pad `b`: a route coming in lands on passing copper instead of returning
/// beside it. A branch is a Y (a signal track is never `wide`) with its via off the track (4.2, 4.4).
pub(crate) fn join_targets(&self, task: &Task) -> Vec<Terminal> {
let comps = self.components(task.net);
let mut out = Vec::new();
match comps.iter().find(|c| c.pads.contains(&task.b)) {
// 4.4 asks for the branch "where there is room". Dropping off a pad inside a big pour there
// is none: his own via at J1 stands about 0.2 mm off the run it joins.
Some(c) => self.comp_terminals(c, if self.pour_exit_pads.contains(&task.a) || self.pour_exit_pads.contains(&task.b) { TIGHT_BRANCH } else { VIA_BRANCH }, &mut out),
None => out.push(self.pad_terminal(task.b)),
}
out
}
/// The first search of `profiles` to find a way, with two weighings in the search's own costs. A
/// no-via route that costs more than two vias over the straight line isn't taken yet: a via route
/// is looked for and the cheaper kept ("don't hop to the bottom layer where the top works", but
/// "always weigh bends against distance", 4.2). And a route landing on a track rather than the pad
/// it was sent to has to save more than a branch costs (4.2: prefer a chain, branch off a pad).
pub(crate) fn weigh(&mut self, task: &Task, sources: &[Terminal], targets: &[Terminal], profiles: &[Profile], rules: &crate::rules::Rules) -> Option<(Path, Profile)> {
let straight = if task.a != task.b { hypot(sub(self.board.pads[task.a].center.into(), self.board.pads[task.b].center.into())) } else { 0.0 };
let mut held: Option<(Path, Profile)> = None;
for &pf in profiles {
self.searches += 1;
let q = Query { net: task.net, also: None, sources, targets, profile: pf, rules, soft: None, via_in: None, history: Some(&self.history), free: &[], arrive: None };
let Some(mut path) = search(&self.world, &q) else { continue };
self.nodes += path.nodes as u64;
if (self.pour_strict.contains(&task.net) || (self.pour_exit.contains(&task.net) && !self.pour_relax)) && self.pour_run(task.net, &path.pts) > self.pour_limit {
continue;
}
// A long run through a pour its pad happens to sit in splits the pour: look for a via
// route first, and fall back on this one only if none turns up.
if pf.max_vias == 0 && self.pour_run(task.net, &path.pts) > crate::router::POUR_RUN {
if held.as_ref().map(|h: &(Path, Profile)| path.cost < h.0.cost).unwrap_or(true) {
held = Some((path, pf));
}
continue;
}
let on_pad = task.a == task.b || task.zone.is_some() || path.pts.last().map(|x| x.0 == snap(self.board.pads[task.b].center)).unwrap_or(true);
if !on_pad && targets.len() > 1 {
let pad = [self.pad_terminal(task.b)];
let q = Query { net: task.net, also: None, sources, targets: &pad, profile: pf, rules, soft: None, via_in: None, history: Some(&self.history), free: &[], arrive: None };
self.searches += 1;
if let Some(p2) = search(&self.world, &q) {
if p2.cost <= path.cost + rules.cost_via * BRANCH_VIAS {
path = p2;
}
}
}
if pf.max_vias == 0 && task.a != task.b && path.cost > straight + 2.0 * rules.cost_via {
if held.as_ref().map(|h| path.cost < h.0.cost).unwrap_or(true) {
held = Some((path, pf));
}
continue;
}
// A held run through a pour is only the fallback for when nothing else turns up: being
// shorter than this way is exactly why it was tempting.
return match held.take() {
Some(h) if h.0.cost < path.cost && self.pour_run(task.net, &h.0.pts) <= crate::router::POUR_RUN => Some(h),
_ => Some((path, pf)),
};
}
held
}
/// After a pass, a ripped trunk can leave taps hanging and a failed stub may have been joined
/// another way. Work from the copper: join every piece still apart, fills included, and report
/// only what is really open.
pub(crate) fn repair_rails(&mut self, plan: &Plan, round: Vec<Task>) -> Vec<Task> {
let nets: Vec<NetId> = {
let mut v: Vec<NetId> = plan.tasks.iter().filter(|t| t.zone == Some(RAIL_TAP)).map(|t| t.net).collect();
v.sort_unstable();
v.dedup();
v
};
let mut failed: Vec<Task> = round.into_iter().filter(|t| !nets.contains(&t.net)).collect();
for net in nets {
let mut gave_up: Vec<usize> = Vec::new();
for _ in 0..64 {
// Join the smallest piece first; the biggest is the rail.
let comps = self.components(net);
if comps.iter().filter(|c| counts_as_piece(c)).count() < 2 {
break;
}
let next = comps.iter().filter(|c| !c.pads.is_empty() && !c.pads.iter().any(|p| gave_up.contains(p)) && counts_as_piece(c)).min_by_key(|c| c.segs.len() + c.pads.len());
let Some(pad) = next.map(|c| c.pads[0]) else { break };
let task = Task { net, level: Level::Power, a: pad, b: pad, main: true, zone: Some(RAIL_TAP) };
if !self.try_rail(&task) {
gave_up.push(pad);
failed.push(task);
}
}
}
failed
}
/// The last guard before the board is written: no route may touch copper of another net. An open
/// join is a fault the designer sees and fixes; a short is one he may not. Every search already
/// keeps clearance, so this finds only what a special case let through (a coupled pair treats its
/// partner as friendly: on a large Ethernet switch board one track crossed a pad of its partner).
/// The route laid later is the one taken off, and the note says so.
pub(crate) fn drop_shorts(&mut self) {
let mut ids: Vec<u32> = self.routes.keys().copied().collect();
ids.sort_unstable();
let mut gone: Vec<u32> = Vec::new();
for (i, &id) in ids.iter().enumerate() {
let r = &self.routes[&id];
let net = r.task.net;
let (vd, _) = self.rules.via_for(net);
let vr = vd as f64 / 2.0;
let mut with: Option<String> = None;
// Pads of other nets under this route's tracks or vias.
'pads: for p in self.board.pads.iter().filter(|p| p.net != net && p.net != NO_NET && !p.layers.is_empty()) {
for s in r.segs.iter().filter(|s| p.layers.contains(&s.layer)) {
if p.shape.dist_seg(s.a.into(), s.b.into()) - s.width as f64 / 2.0 < -1_000.0 {
with = Some(format!("pad {} ({})", self.board.pad_name(self.board.pads.iter().position(|q| std::ptr::eq(q, p)).unwrap()), self.board.net_name(p.net)));
break 'pads;
}
}
for v in &r.vias {
if p.shape.dist_pt((*v).into()) - vr < -1_000.0 {
with = Some(format!("pad {} ({})", self.board.pad_name(self.board.pads.iter().position(|q| std::ptr::eq(q, p)).unwrap()), self.board.net_name(p.net)));
break 'pads;
}
}
}
// Tracks of other nets laid before it (so the later of two is the one taken off).
if with.is_none() {
'routes: for &oid in &ids[..i] {
if gone.contains(&oid) {
continue;
}
let o = &self.routes[&oid];
if o.task.net == net {
continue;
}
for s in &r.segs {
for t in o.segs.iter().filter(|t| t.layer == s.layer) {
if seg_seg(s.a.into(), s.b.into(), t.a.into(), t.b.into()) - (s.width + t.width) as f64 / 2.0 < -1_000.0 {
with = Some(format!("a track of {}", self.board.net_name(o.task.net)));
break 'routes;
}
}
}
}
}
if let Some(w) = with {
self.notes.push(format!("for the designer: {} {} to {} was taken off again: its copper touched {w}, a short. The join is left open.", self.board.net_name(net), self.board.pad_name(r.task.a), self.board.pad_name(r.task.b)));
gone.push(id);
}
}
for id in gone {
self.unplace(id);
}
}
/// A route that starts or ends lying right on its own net's copper is that copper twice: cut it
/// back to where it leaves (4.2: fewest segments, branch rather than run alongside). This is exact
/// geometry, not a search, so it costs nothing and moves nothing else.
pub(crate) fn trim_overlaps(&mut self) {
let mut trimmed = 0;
let mut ids: Vec<u32> = self.routes.keys().copied().collect();
ids.sort_unstable();
for id in ids {
let Some(r) = self.routes.get(&id) else { continue };
if r.segs.is_empty() || matches!(r.task.level, Level::Pair | Level::Kelvin) {
continue;
}
let net = r.task.net;
let others: Vec<Seg> = self.routes.values().filter(|o| o.id != id && o.task.net == net).flat_map(|o| o.segs.iter().cloned()).collect();
let mut segs = r.segs.clone();
let before = segs.len();
let mut cut = false;
for _ in 0..2 {
// Off the front, then the same off the back.
while let Some(first) = segs.first().cloned() {
match overlap_end(&first, &others) {
Some(None) => {
segs.remove(0);
cut = true;
}
Some(Some(e)) => {
segs[0].a = e;
cut = true;
break;
}
None => break,
}
}
segs.reverse();
for s in &mut segs {
std::mem::swap(&mut s.a, &mut s.b);
}
}
if !cut || (segs.len() == before && segs == r.segs) {
continue;
}
let (task, vias) = (r.task.clone(), r.vias.clone());
let pieces = self.open_pieces(net);
let saved = self.unplace(id).unwrap();
self.place(id, task, segs, vias);
if self.open_pieces(net) > pieces {
self.unplace(id);
self.place(saved.id, saved.task, saved.segs, saved.vias);
} else {
trimmed += 1;
}
}
if trimmed > 0 {
self.log.push(format!("trimmed {trimmed} routes that lay on their own net's copper"));
}
}
/// One task for each fill that nothing feeds yet: a piece of copper that big is on the board
/// whether it is joined or not, so it has to be joined (4.3). A fill sliver too small for a via
/// can't be fed: that is for KiCad's refill to remove, and it is reported.
pub(crate) fn unfed_fills(&self) -> Vec<Task> {
let mut out = Vec::new();
let mut nets: Vec<NetId> = self.net_info.iter().filter(|(_, (l, _))| *l == Level::Power).map(|(n, _)| *n).collect();
nets.sort_unstable();
for net in nets {
let comps = self.components(net);
if comps.iter().filter(|c| counts_as_piece(c)).count() < 2 {
continue;
}
for c in comps.iter().filter(|c| c.pads.is_empty() && !c.zones.is_empty()) {
if !c.zones.iter().any(|&z| self.fill_area(z) >= self.via_area(net)) {
continue;
}
let z = c.zones[0];
let at = poly_center(&self.world.zones[z].2);
let pad = comps.iter().flat_map(|o| o.pads.iter().copied()).min_by(|&x, &y| hypot(sub(self.board.pads[x].center.into(), at)).total_cmp(&hypot(sub(self.board.pads[y].center.into(), at))));
if let Some(pad) = pad {
out.push(Task { net, level: Level::Power, a: pad, b: pad, main: true, zone: Some(RAIL_TAP) });
}
}
}
out
}
fn fill_area(&self, z: usize) -> f64 {
let p = &self.world.zones[z].2;
let n = p.len();
((0..n).map(|i| p[i].0 * p[(i + 1) % n].1 - p[(i + 1) % n].0 * p[i].1).sum::<f64>() / 2.0).abs()
}
fn via_area(&self, net: NetId) -> f64 {
let r = self.rules.via_for(net).0 as f64 / 2.0;
std::f64::consts::PI * r * r
}
/// 4.2: rate each rail track by the current actually through it and widen what falls short. Only
/// the finished copper says which way a branch went: a pin's tap can end up carrying another part's
/// current when that part joined the rail through it (benchmark C: U10's 1.24 A through a cap's tap).
/// Widening happens in place where it clears everything; what can't is left for the check to name.
/// Rails rated from the copper as laid, while the board is still empty: called once the heavy
/// rails are down and before any signal. Which tap ends up feeding which part is only known now
/// (a part joins the nearest copper of its net), and now every piece still has room to take the
/// width its real current needs. Left for the end, benchmark C's U10 branch had none (2026-11-06).
pub(crate) fn rate_rails_now(&mut self) {
if self.rules.rails.is_empty() {
return;
}
self.split_rails_at_taps();
let (mut widened, _) = self.size_in_place(true);
for _ in 0..12 {
let (changed, _) = self.widen_in_place();
widened += changed;
if changed == 0 {
break;
}
}
if widened > 0 {
self.log.push(format!("rails: {widened} track pieces set to their real current (wider or narrower) right after the rails were laid"));
}
}
pub(crate) fn rate_rails_last(&mut self) {
if self.rules.rails.is_empty() {
return;
}
let mut widened = 0usize;
for _ in 0..6 {
let (changed, _) = self.widen_in_place();
widened += changed;
if changed == 0 {
break;
}
}
if widened > 0 {
self.log.push(format!("rails: {widened} track pieces widened in the last sizing, after the other closing passes"));
}
}
pub(crate) fn widen_rails(&mut self) {
if self.rules.rails.is_empty() {
return;
}
self.split_rails_at_taps();
let (mut widened, _) = self.size_in_place(true);
let mut stuck: Vec<(u32, i64)> = Vec::new();
for _ in 0..12 {
let (changed, left) = self.widen_in_place();
widened += changed;
stuck = left;
if changed == 0 {
break;
}
}
// No room beside it: route it again at the width it needs, moving what is in the way. Nothing
// stands unless every join it touched is still made and no other connection was given up.
let mut moved = 0usize;
if !stuck.is_empty() {
self.grant_time(45.0);
stuck.sort_by_key(|x| std::cmp::Reverse(x.1));
for (id, need) in stuck.clone() {
if self.over_time() {
break;
}
let Some(old) = self.routes.get(&id) else { continue };
let task = old.task.clone();
let open = self.open_pieces(task.net);
let saved = self.unplace(id).unwrap();
self.rail_override.insert((task.a, task.b), need);
let ok = self.move_for_width(&task, open);
self.rail_override.remove(&(task.a, task.b));
if ok {
moved += 1;
} else {
self.place(saved.id, saved.task, saved.segs, saved.vias);
}
}
let (changed, left) = self.widen_in_place();
widened += changed;
stuck = left;
}
self.log.push(format!("rails: widened {widened} track pieces to the current through them, re-routed {moved} wider; {} still have no room", stuck.len()));
}
/// One pass: rate the finished copper, widen what fits where it lies. Returns how many pieces
/// changed, and the routes still short with the width each needs.
fn widen_in_place(&mut self) -> (usize, Vec<(u32, i64)>) {
self.size_in_place(false)
}
/// Cuts each rated rail's tracks where its own copper joins them part-way along: another track's
/// end, a via, a pad of the net. Current is rated per track, and a trunk with a tap in its middle
/// carries the rail's current on one side of the tap only: uncut, benchmark B's +3v3 ran at
/// 0.82 mm for 28 mm past the MCU module to an EEPROM that draws 3 mA (the designer, 2026-11-09).
pub(crate) fn split_rails_at_taps(&mut self) {
let nets: Vec<NetId> = { let mut v: Vec<NetId> = self.world.rail_nets.iter().copied().collect(); v.sort_unstable(); v };
for net in nets {
// (point, layer or MAX for every layer, how near the track's centre line counts as on it)
let mut joins: Vec<(P, usize, f64)> = Vec::new();
for r in self.routes.values().filter(|r| r.task.net == net) {
for s in &r.segs {
joins.push((s.a, s.layer, 2_000.0));
joins.push((s.b, s.layer, 2_000.0));
}
joins.extend(r.vias.iter().map(|&v| (v, usize::MAX, 2_000.0)));
}
for pd in self.board.pads.iter().filter(|pd| pd.net == net) {
for &l in &pd.layers {
joins.push((pd.center, l, 0.0));
}
}
let mut ids: Vec<u32> = self.routes.values().filter(|r| r.task.net == net).map(|r| r.id).collect();
ids.sort_unstable();
for id in ids {
let segs = self.routes[&id].segs.clone();
let (mut next, mut cut) = (Vec::new(), false);
for s in &segs {
let (a, b): (V, V) = (s.a.into(), s.b.into());
let len = hypot(sub(a, b));
let d = ((s.b.0 - s.a.0).signum(), (s.b.1 - s.a.1).signum());
let unit = if d.0 != 0 && d.1 != 0 { SQRT2 } else { 1.0 };
let mut at: Vec<i64> = joins.iter().filter(|(_, l, _)| *l == s.layer || *l == usize::MAX).filter_map(|(q, _, tol)| {
let v: V = (*q).into();
let along = hypot(sub(v, a));
// A pad counts when its centre lies under the track; other copper when it ends on the line.
let reach = if *tol == 0.0 { s.width as f64 / 2.0 } else { *tol };
(pt_seg(v, a, b) <= reach && along > 100_000.0 && len - along > 100_000.0).then_some(((along / unit).round() as i64 / 2) * 2)
}).collect();
at.sort_unstable();
at.dedup();
if at.is_empty() {
next.push(s.clone());
continue;
}
cut = true;
let mut from = s.a;
for t in at {
let q = (s.a.0 + d.0 * t, s.a.1 + d.1 * t);
if q != from && q != s.b {
next.push(Seg { a: from, b: q, layer: s.layer, width: s.width });
from = q;
}
}
next.push(Seg { a: from, b: s.b, layer: s.layer, width: s.width });
}
if cut {
let saved = self.unplace(id).unwrap();
self.place(saved.id, saved.task, next, saved.vias);
}
}
}
}
/// `widen_in_place`, and with `trim` also the other way: a track drawn more than twice as wide
/// as its real current needs comes down to that need (never under the net's plain track width).
/// The drop limit is then met by the widening passes that follow, from the real currents.
fn size_in_place(&mut self, trim: bool) -> (usize, Vec<(u32, i64)>) {
// In id order: a hash map's order changes on every start of the program (clock.rs).
let mut routes: Vec<&Route> = self.routes.values().collect();
routes.sort_by_key(|r| r.id);
let text = crate::write::render(self.board, &routes, &self.rules);
let Ok(written) = Board::parse(text) else { return (0, Vec::new()) };
let mut rules = self.rules.clone();
rules.bind(&written);
let mut want: Vec<(String, P, P, usize, i64)> = Vec::new();
let mut slim: Vec<(String, P, P, usize, i64)> = Vec::new();
for (name, rail) in &rules.rails {
let Some(net) = written.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v) else { continue };
for x in crate::current::rate_rail(&written, &rules, net, rail) {
let t = &written.tracks[x.track];
if t.width + 1000 < x.need {
want.push((written.net_name(net).to_string(), t.a, t.b, t.layer, x.need));
} else if trim && !x.by_drop {
let class = rules.track_for(net);
let floor = if class > mm(0.3) { rules.track } else { class };
let target = x.need.max(floor);
if target * 2 < t.width {
slim.push((written.net_name(net).to_string(), t.a, t.b, t.layer, target));
}
}
}
}
let near = |p: P, q: P| (p.0 - q.0).abs() <= 2_000 && (p.1 - q.1).abs() <= 2_000;
let mut changed = 0usize;
let mut stuck: Vec<(u32, i64)> = Vec::new();
let mut ids: Vec<u32> = self.routes.keys().copied().collect();
ids.sort_unstable();
for id in ids {
let net = self.routes[&id].task.net;
let name = self.board.net_name(net).to_string();
let mine: Vec<&(String, P, P, usize, i64)> = want.iter().filter(|w| w.0 == name).collect();
let thin: Vec<&(String, P, P, usize, i64)> = slim.iter().filter(|w| w.0 == name).collect();
if mine.is_empty() && thin.is_empty() {
continue;
}
let segs = self.routes[&id].segs.clone();
let mut next = segs.clone();
let mut any = false;
let mut short = 0i64;
for (k, s) in segs.iter().enumerate() {
if let Some(w) = thin.iter().find(|w| w.3 == s.layer && ((near(w.1, s.a) && near(w.2, s.b)) || (near(w.1, s.b) && near(w.2, s.a)))) {
if w.4 < s.width {
next[k].width = w.4;
any = true;
changed += 1;
}
continue;
}
let Some(w) = mine.iter().find(|w| w.3 == s.layer && ((near(w.1, s.a) && near(w.2, s.b)) || (near(w.1, s.b) && near(w.2, s.a)))) else { continue };
if self.seg_clear(s.a, s.b, s.layer, w.4, net, NO_NET) {
next[k].width = w.4;
any = true;
changed += 1;
} else {
// Not the whole need here: the widest this stretch can take, so the stretches
// with room make up the rest on the next rating (the drop is shared along the path).
let got = self.widest_clear(s.a, s.b, s.layer, s.width, w.4, net);
if got >= s.width + 20_000 {
next[k].width = got;
any = true;
changed += 1;
}
short = short.max(w.4);
}
}
if any {
// A later re-route of this connection keeps the width: its own pad's draw would
// size it thin again (widths_for), which is how the thin tap came about.
let widest = next.iter().map(|s| s.width).max().unwrap_or(0);
let saved = self.unplace(id).unwrap();
self.rail_override.insert((saved.task.a, saved.task.b), widest);
self.place(saved.id, saved.task, next, saved.vias);
}
if short > 0 {
stuck.push((id, short));
}
}
(changed, stuck)
}
/// How many vias a power layer change gets (reference approval 2026-11-09: area match, IPC-2152): enough
/// that their barrels' copper is at least the copper of the trace coming in. IPC-2152 p.26, as
/// quoted by Brooks and Adam ("Vias Are Cooler Than We Think", Signal Integrity Journal 2019):
/// "The cross-sectional area of a via should have at least the same cross-sectional area as the
/// conductor ... If the via has less cross-sectional area than the conductor, then multiple vias
/// can be used". A barrel's copper is pi x (drill + plating) x plating (Brooks and Graves,
/// "Current Carrying Capacity of Vias", 2003), plating 18 um: JLCPCB's capability table,
/// "Average Hole Plating Thickness 18 um". A 0.3 mm via matches 0.51 mm of 1 oz trace, so his
/// Benchmark C rails get 3 (+5V at 1.34 mm), 2 (+5V_OUT at 0.70 mm) and 1 (0.23 to 0.27 mm). The
/// trace's width already comes from its current, so this follows current too.
pub(crate) fn vias_for_width(&self, net: NetId, width: i64) -> usize {
let t = VIA_PLATING_UM / 1000.0;
let d = to_mm(self.rules.via_for(net).1);
let barrel = std::f64::consts::PI * (d + t) * t;
let trace = to_mm(width) * self.rules.copper_um / 1000.0;
((trace / barrel) - 1e-6).ceil().max(1.0) as usize
}
/// Adds the vias a power layer change still lacks (see `vias_for_width`), on nets with an approved
/// current. Each goes beside the first, joined to it on both layers at the trace's width where
/// that fits (no wider than the via), never in line with the trace (no via inside a trace) and
/// never in a fine-pitch escape. Copper is final by now, so this takes only room nothing else
/// wanted; where the room isn't there the rail note says how many are missing.
pub(crate) fn second_vias(&mut self) {
let (mut added, mut asked, mut short) = (0usize, 0usize, 0usize);
let bus = self.bus_layer();
let top = self.world.route_layers[0];
let mut ids: Vec<u32> = self.routes.values().filter(|r| r.task.level == Level::Power && self.rules.rail(self.board.net_name(r.task.net)).is_some() && !r.vias.is_empty()).map(|r| r.id).collect();
ids.sort_unstable();
for id in ids {
let (task, vias, segs) = {
let r = &self.routes[&id];
(r.task.clone(), r.vias.clone(), r.segs.clone())
};
let (via_dia, via_drill) = self.rules.via_for(task.net);
// Centre to centre: the holes' rule (2.2), and no closer than the vias touching.
let apart = via_dia.max(via_drill + self.rules.hole_to_hole());
let (_, stub) = self.widths_for(&task);
for v in vias {
let width = segs.iter().filter(|s| s.a == v || s.b == v).map(|s| s.width).max().unwrap_or(stub);
let need = self.vias_for_width(task.net, width);
if need < 2 {
continue;
}
asked += 1;
// What is already there: this net's vias within reach of this one, itself included.
let near = |p: P| hypot(sub(p.into(), v.into())) <= apart as f64 * 2.3;
let mut have: Vec<P> = self.routes.values().filter(|r| r.task.net == task.net).flat_map(|r| r.vias.iter().copied()).filter(|&p| near(p)).collect();
have.sort_unstable();
have.dedup();
if have.len() >= need || self.world.in_escape(v.into()) {
if have.len() < need {
short += 1;
}
continue;
}
let mut in_line: Vec<u8> = Vec::new();
for s in &segs {
if s.a == v || s.b == v {
if let Some(d) = dir_of(s.a, s.b) {
in_line.push(d);
in_line.push((d + 4) % 8);
}
}
}
let link = width.min(via_dia).max(stub);
for d in 0..8usize {
if have.len() >= need {
break;
}
if in_line.contains(&(d as u8)) {
continue;
}
let (dx, dy) = DIRS[d];
let t = if dx != 0 && dy != 0 { ((apart as f64 / SQRT2).ceil() as i64) + 2 } else { apart };
let w = snap((v.0 + dx * t, v.1 + dy * t));
if have.iter().any(|&h| h != v && hypot(sub(h.into(), w.into())) < apart as f64 - 1.0) || dir_of(v, w).is_none() {
continue;
}
let q = Query { net: task.net, also: None, sources: &[], targets: &[], profile: Profile { width: 0, neck: 0, clearance: self.rules.clearance_for(task.net, task.net), target_gap: 0, max_vias: 0, margin: 0.0, layer_bias: None }, rules: &self.rules, soft: None, via_in: None, history: None, free: &[], arrive: None };
let (mut b, mut c) = (Vec::new(), 0.0);
if !self.world.via_ok(w, &q, None, &mut b, &mut c) {
continue;
}
let fits = |me: &Self, wd: i64| me.world.route_layers.iter().all(|&l| (l != bus && l != top) || me.seg_clear(v, w, l, wd, task.net, NO_NET));
let Some(wd) = [link, stub].into_iter().find(|&wd| fits(self, wd)) else { continue };
let mut joins = vec![Seg { a: v, b: w, layer: top, width: wd }];
if bus != top {
joins.push(Seg { a: v, b: w, layer: bus, width: wd });
}
let nid = self.fresh_id();
self.place(nid, task.clone(), joins, vec![w]);
have.push(w);
added += 1;
}
if have.len() < need {
short += 1;
}
}
}
if asked > 0 {
self.log.push(format!("vias (4.4, IPC-2152 area match, {VIA_PLATING_UM} um plating): {added} added at {asked} power layer changes that need more than one; {short} still have less copper than their trace"));
}
}
/// The record 4.2 asks for on each power net: what was drawn. Currents are not known here, so
/// no margin is claimed.
pub(crate) fn rail_notes(&mut self) {
// Each rail's worst drop, from the copper as drawn.
let mut drop_of: std::collections::HashMap<String, String> = Default::default();
if !self.rules.rails.is_empty() {
// In id order: a hash map's order changes on every start of the program (clock.rs).
let mut routes: Vec<&Route> = self.routes.values().collect();
routes.sort_by_key(|r| r.id);
if let Ok(written) = Board::parse(crate::write::render(self.board, &routes, &self.rules)) {
let mut rules = self.rules.clone();
rules.bind(&written);
for (name, rail) in &rules.rails {
let Some(net) = written.net_ids.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, v)| *v) else { continue };
let text = match (rail.volts, crate::current::rail_drops(&written, &rules, net, rail).into_iter().max_by(|x, y| x.volts.total_cmp(&y.volts))) {
(None, _) => "No rail voltage in the spec, so the drop is not judged.".to_string(),
(Some(v), Some(d)) => format!("Worst copper drop {:.1} mV to {} at {} A, {:.2}% of {v} V (limit {:.2}%).", d.volts * 1000.0, d.load, d.amps, d.volts / v * 100.0, crate::current::DROP_LIMIT * 100.0),
(Some(_), None) => "No load reached through tracks, so no drop to report.".to_string(),
};
drop_of.insert(name.to_ascii_lowercase(), text);
}
}
}
self.notes.push(format!("DEFAULT: weights and lengths that are not from the design document, read off the reference boards or chosen: a wide stretch beside a neck is at least {:.1} mm, a branch costs {BRANCH_VIAS} via against reaching the next pad, a rail's stub layer costs {OFF_BUS} per mm against its bus. Via and bend weights are rules.rs's defaults", MIN_WIDE_RUN / NM));
let mut per: BTreeMap<NetId, (BTreeMap<i64, f64>, usize)> = BTreeMap::new();
for r in self.routes.values().filter(|r| r.task.level == Level::Power) {
let e = per.entry(r.task.net).or_default();
for s in &r.segs {
*e.0.entry(s.width).or_insert(0.0) += hypot(sub(s.a.into(), s.b.into())) / NM;
}
e.1 += r.vias.len();
}
let mut notes = Vec::new();
for (net, (w, v)) in per {
let text: Vec<String> = w.iter().rev().map(|(k, l)| format!("{:.2} mm: {:.1} mm", to_mm(*k), l)).collect();
let name = self.board.net_name(net);
let (main, _) = self.widths_for(&Task { net, level: Level::Power, a: 0, b: 0, main: true, zone: Some(RAIL_TAP) });
let spec = self.rules.wide.keys().any(|k| k.eq_ignore_ascii_case(name));
let from = if spec {
format!("spec wideNets main {:.2} mm", to_mm(main))
} else if main > self.rules.power_floor {
format!("net class main {:.2} mm", to_mm(main))
} else {
format!("no spec width, so 4.2's {:.2} mm floor", to_mm(main))
};
// 4.2 asks for IPC-2152's conservative chart. It isn't computed here: the only published
// formula at hand, the fit in his Hardware Calculator (hwcalc calcs.js:223, from smps.us),
// gives 1.13 mm for 4.2's own example of 3 A at 20 C where 4.2 says about 2.3 mm, and
// 0.008 mm for 0.177 A where his PiProbe spec says about 0.06 mm. So it isn't his chart.
let load = self.rules.loads.iter().find(|(k, _)| k.eq_ignore_ascii_case(name)).map(|(_, a)| *a);
// An approved rail: 4.2's record, chart, current, rise, required and drawn width, margin.
if let Some(rail) = self.rules.rail(name) {
let rise = self.rules.max_rise.unwrap_or(20.0);
let need = self.rules.rail_width(rail.amps, true);
let widest = w.keys().next_back().copied().unwrap_or(0);
// A rail whose pour joins its source to its heavy loads carries the current in the pour:
// its tracks are taps, and comparing the widest of them with the rail's width misleads
// (benchmark C +3V3_EXT read "margin 0.87 x" with its 0.55 A in the pour, 2026-11-09).
if self.pour_fed_net(name) {
notes.push(format!("{name}: conservative chart, {} A at {rise} C rise, {:.2} mm as a track; carried by its pour from source to loads, tracks are taps: drawn {}, {v} vias. {}", rail.amps, to_mm(need), text.join(", "), drop_of.get(&name.to_ascii_lowercase()).cloned().unwrap_or_default()));
} else {
notes.push(format!("{name}: conservative chart, {} A at {rise} C rise, requires {:.2} mm; drawn {}, {v} vias; margin {:.2} x on the widest. {}", rail.amps, to_mm(need), text.join(", "), widest as f64 / need.max(1) as f64, drop_of.get(&name.to_ascii_lowercase()).cloned().unwrap_or_default()));
}
continue;
}
let current = match (load, self.rules.max_rise) {
(Some(a), Some(r)) => format!(" Load {a} A at {r} C rise per the spec: required width not computed, IPC-2152's conservative chart isn't sourced here, so confirm the margin."),
(Some(a), None) => format!(" Load {a} A per the spec, no maxRiseC: required width not computed."),
_ => " No load in the spec: size it with IPC-2152 from the rail's current.".to_string(),
};
let unfed = self.components(net).iter().filter(|c| c.pads.is_empty() && !c.zones.is_empty()).map(|c| c.zones.len()).sum::<usize>();
let fills = if unfed > 0 { format!(" {unfed} fill pieces have no feed.") } else { String::new() };
notes.push(format!("{name}: {from}. Drawn {}, {} vias, bus on {}.{current}{fills}", text.join(", "), v, self.board.layers[self.bus_layer()].name));
}
self.notes.extend(notes);
}
/// What one connection costs on the final board, in the search's own terms, so it can be weighed
/// against what a new search finds: length, bends, vias, spacing below target (4.2).
pub(crate) fn route_cost(&self, r: &Route) -> f64 {
let rules = &self.rules;
let bus = self.bus_of(&r.task);
let mut cost = r.vias.len() as f64 * rules.cost_via;
// A long run through a pour its pad sits in can split that pour on refill: tidying must not
// trade a via for one because it is shorter (benchmark B: /USB2_CC1 through /USB2_VBUS).
let run = self.seg_pour_run(r);
if run > crate::router::POUR_RUN {
cost += 2.0 * rules.cost_via + run;
}
for (i, s) in r.segs.iter().enumerate() {
let len = hypot(sub(s.a.into(), s.b.into()));
cost += len * match bus {
Some(l) if l == s.layer => 1.0,
Some(_) => OFF_BUS,
None if s.layer == 0 => 1.0,
None => rules.cost_bottom,
};
if i > 0 {
let p = &r.segs[i - 1];
if p.layer == s.layer && p.b == s.a {
if let (Some(d1), Some(d2)) = (dir_of(p.a, p.b), dir_of(s.a, s.b)) {
let t = (d2 as i32 - d1 as i32).rem_euclid(8);
cost += match t.min(8 - t) {
0 => 0.0,
1 => rules.cost_bend45,
_ => rules.cost_bend90,
};
}
}
}
cost += self.doubled_along(r, i) * DOUBLED;
// Spacing below 2W outside an escape, and thin copper on an open run.
let m = V((s.a.0 + s.b.0) as f64 / 2.0, (s.a.1 + s.b.1) as f64 / 2.0);
if !self.world.in_escape(m) {
let half = s.width as f64 / 2.0;
let soft = (s.width * 2).max(rules.clearance) as f64;
let (a, b): (V, V) = (s.a.into(), s.b.into());
let reach = half + soft;
let bb = (a.0.min(b.0) - reach, a.1.min(b.1) - reach, a.0.max(b.0) + reach, a.1.max(b.1) + reach);
let mut gap = f64::INFINITY;
self.world.layers[s.layer].visit(bb, |o| {
if o.net != r.task.net && !matches!(o.owner, Owner::Zone(_)) {
gap = gap.min(o.shape.dist_seg(a, b) - half);
}
true
});
let hard = rules.clearance as f64;
if gap < soft {
cost += len * rules.cost_tight * (1.0 - (gap - hard).max(0.0) / (soft - hard).max(1.0));
}
}
}
cost
}
/// How much of this segment runs beside copper of its own net: another route's, or a part of its
/// own further along. Zero is what a person draws; the rest is a doubled run or a fold-back.
pub(crate) fn doubled_along(&self, r: &Route, i: usize) -> f64 {
let s = &r.segs[i];
let mut total = 0.0;
for (j, o) in r.segs.iter().enumerate() {
if j > i + 1 && o.layer == s.layer {
total += parallel_overlap(s, o);
}
}
for other in self.routes.values().filter(|o| o.id != r.id && o.task.net == r.task.net) {
for o in other.segs.iter().filter(|o| o.layer == s.layer) {
total += parallel_overlap(s, o);
}
}
total
}
/// How apart a net is, for a guard: pad islands first, then its connected pieces including fills.
/// Pieces alone miss a move that swaps a bridge for a landing on an unfed fill: same count, net
/// split. Islands alone miss a move that orphans a ring (4.3).
pub(crate) fn open_pieces(&self, net: NetId) -> usize {
self.islands(net).len() * 1000 + self.components(net).iter().filter(|c| counts_as_piece(c)).count()
}
/// Part 3 step 8: with everything placed, take each connection off and search again. A route that
/// had to dodge copper since moved straightens; a detour forced by routing order goes. The worst
/// connections go first, so a short budget is spent where it shows. A connection still far over
/// its straight line then gets the stronger move: take its way from whoever holds it. Never lets
/// a net come apart.
pub(crate) fn optimize(&mut self) {
if std::env::var_os("ADOM_ROUTE_NO_OPTIMISE").is_some() {
return;
}
let t0 = Instant::now();
let deadline = self.rules.deadline;
let out_of_time = |t: &Self| deadline.map(|d| Instant::now() > d).unwrap_or(t.over_time());
let (before_len, before_vias) = self.copper_totals();
let (mut tried, mut kept, mut swapped) = (0usize, 0usize, 0usize);
// Half the time for plain re-searches, so the stronger move below always gets some.
let halfway = Instant::now() + deadline.map(|d| d.saturating_duration_since(Instant::now())).unwrap_or_default() / 2;
// Small budgets first, so a large board gets through every connection before any gets more.
let limit = self.rules.node_limit;
let mut budget = 100_000usize.min(limit);
for _ in 0..4 {
// A connection already within one bend of its straight line has nothing to give.
let small = self.rules.cost_bend45;
// Doubled copper first: it is what he'd reject on sight, and the cheapest to take out.
// A bus row stays as the first pass laid it, beside its neighbours: a re-search one line
// at a time prices length, not keeping company, and took benchmark B's bus apart.
let mut work: Vec<(bool, f64, u32)> = self.routes.values().filter(|r| !self.in_bus_row(&r.task) && !matches!(r.task.level, Level::Pair | Level::Kelvin) && !(r.task.a == r.task.b && r.task.zone.is_none()) && !r.segs.is_empty()).map(|r| ((0..r.segs.len()).all(|i| self.doubled_along(r, i) == 0.0), self.excess(r), r.id)).filter(|x| x.1 > small).collect();
work.sort_by(|x, y| x.0.cmp(&y.0).then(y.1.total_cmp(&x.1)).then(x.2.cmp(&y.2)));
let work: Vec<(f64, u32)> = work.into_iter().map(|x| (x.1, x.2)).collect();
self.rules.node_limit = budget;
budget = (budget * 4).min(limit);
let mut kept_now = 0;
for (_, id) in work {
if out_of_time(self) || Instant::now() > halfway {
break;
}
if !self.routes.contains_key(&id) {
continue;
}
tried += 1;
if self.reroute(id, false) {
kept += 1;
kept_now += 1;
}
}
// The stronger move, only for what a plain search couldn't fix.
let mut heavy: Vec<(f64, u32)> = self.routes.values().filter(|r| !self.in_bus_row(&r.task) && !matches!(r.task.level, Level::Pair | Level::Kelvin | Level::PlaneFanout) && !r.segs.is_empty()).map(|r| (self.excess(r), r.id)).filter(|x| x.0 > self.rules.cost_via).collect();
heavy.sort_by(|x, y| y.0.total_cmp(&x.0).then(x.1.cmp(&y.1)));
for (_, id) in heavy {
if out_of_time(self) {
break;
}
if !self.routes.contains_key(&id) {
continue;
}
if self.reroute(id, true) {
swapped += 1;
kept_now += 1;
} else if self.trace_on() {
eprintln!(" no swap for route {id}");
}
}
if kept_now == 0 || out_of_time(self) {
break;
}
}
self.rules.node_limit = limit;
*self.world.follow.borrow_mut() = None;
let (after_len, after_vias) = self.copper_totals();
self.log.push(format!("optimise: {tried} connections tried, {kept} improved, {swapped} moved a neighbour; {:.1} -> {:.1} mm, {before_vias} -> {after_vias} vias, {:.1} s", before_len / NM, after_len / NM, t0.elapsed().as_secs_f64()));
}
fn trace_on(&self) -> bool {
std::env::var_os("ADOM_ROUTE_TRACE").is_some()
}
/// How far a connection's cost is over the straight line between what it joins.
fn excess(&self, r: &Route) -> f64 {
let straight = if r.task.a != r.task.b { hypot(sub(self.board.pads[r.task.a].center.into(), self.board.pads[r.task.b].center.into())) } else { 0.0 };
self.route_cost(r) - straight
}
/// Lift one connection and find it a better way. On a net of three or more pads it may come from
/// either side: of the two pieces it joined, whichever way doesn't have to run back along its own
/// copper. `displace`: the way is held by someone else, so move them.
fn reroute(&mut self, id: u32, displace: bool) -> bool {
let Some(old) = self.routes.get(&id) else { return false };
let task = old.task.clone();
self.set_follow(&task);
let old_cost = self.route_cost(old);
let pieces = self.open_pieces(task.net);
let saved = self.unplace(id).unwrap();
if displace {
if self.swap_for(&saved, old_cost, pieces) {
return true;
}
self.place(saved.id, saved.task, saved.segs, saved.vias);
return false;
}
let mut ways: Vec<(Task, Vec<Terminal>, Vec<Terminal>)> = Vec::new();
if task.zone == Some(RAIL_TAP) {
for (sources, targets) in self.rail_ways(&task, VIA_BRANCH) {
ways.push((task.clone(), sources, targets));
}
} else {
ways.push((task.clone(), if self.joins_copper(&task) { self.piece_pads(&task) } else { vec![self.pad_terminal(task.a)] }, self.targets_of(&task)));
if task.a != task.b && self.joins_copper(&task) {
let back = Task { a: task.b, b: task.a, ..task.clone() };
let (sources, targets) = (self.piece_pads(&back), self.targets_of(&back));
ways.push((back, sources, targets));
}
}
let bus = self.bus_of(&task);
let mut best: Option<(f64, Task, Vec<Seg>, Vec<P>)> = None;
for (way, sources, targets) in ways {
if targets.is_empty() {
continue;
}
for pf in self.opt_profiles(&way) {
let rules = self.rules.clone();
let one = [pf];
let Some((path, pf)) = self.weigh(&way, &sources, &targets, &one, &rules) else { continue };
let way = if way.zone == Some(RAIL_TAP) { self.task_as_made(&way, &path) } else { way.clone() };
let pts = match bus {
Some(l) => self.finish_path_on(&path, way.net, NO_NET, &|x| if x == l { pf.width } else { pf.neck }),
None => self.finish_path(&path, way.net, NO_NET, pf.neck),
};
let nid = self.commit(&way, &pts, pf.width, pf.neck, NO_NET);
let c = self.route_cost(self.routes.get(&nid).unwrap());
let ok = c + 0.05 * NM < old_cost && best.as_ref().map(|b| c < b.0).unwrap_or(true) && self.open_pieces(way.net) <= pieces;
let r = self.unplace(nid).unwrap();
if ok {
best = Some((c, way.clone(), r.segs, r.vias));
}
}
}
match best {
Some((_, way, segs, vias)) => {
self.place(id, way, segs, vias);
true
}
None => {
self.place(saved.id, saved.task, saved.segs, saved.vias);
false
}
}
}
/// All the pads already joined to pad `a`, as places to start from.
fn piece_pads(&self, task: &Task) -> Vec<Terminal> {
let comps = self.components(task.net);
match comps.iter().find(|c| c.pads.contains(&task.a)) {
Some(c) => c.pads.iter().map(|&p| self.pad_terminal(p)).collect(),
None => vec![self.pad_terminal(task.a)],
}
}
/// The searches worth trying for a connection on the finished board: the same widths the task
/// would get, with and without a via. Spacing is held at the target; dense spots keep what they have.
fn opt_profiles(&self, task: &Task) -> Vec<Profile> {
let (w, n) = self.widths_for(task);
let c = self.rules.clearance_for(task.net, task.net);
let tgt = match task.level {
Level::Crystal | Level::Kelvin => c,
_ => (w * 2).max(c),
};
let bias = self.bus_of(task);
let mk = |width: i64, target_gap: i64, max_vias: u32, margin: f64| Profile { width, neck: n, clearance: c, target_gap, max_vias, margin, layer_bias: bias };
if bias.is_some() {
return vec![mk(w, c, 2, 3.0 * NM), mk(w, c, 2, 8.0 * NM)];
}
let mut out = vec![mk(w, tgt, 0, 5.0 * NM)];
if !matches!(task.level, Level::Crystal | Level::Kelvin | Level::Pair) {
out.push(mk(w, tgt, 2, 5.0 * NM));
}
out
}
fn copper_totals(&self) -> (f64, usize) {
let mut len = 0.0;
let mut vias = 0;
for r in self.routes.values() {
vias += r.vias.len();
for s in &r.segs {
len += hypot(sub(s.a.into(), s.b.into()));
}
}
(len, vias)
}
}
/// How far a pin's stub to its cap may run: past this a stub on the pad layer costs more than going
/// down to the bus and back up, in the search's own weights (2 vias + d against OFF_BUS d, for
/// OFF_BUS 3). Nothing else sets it, so changing a weight moves it with the search.
pub fn cap_reach(rules: &crate::rules::Rules) -> f64 {
2.0 * rules.cost_via / (OFF_BUS - 1.0)
}
fn counts_as_piece(c: &Comp) -> bool {
!c.pads.is_empty() || !c.zones.is_empty()
}
fn poly_center(p: &[V]) -> V {
let n = p.len().max(1) as f64;
V(p.iter().map(|x| x.0).sum::<f64>() / n, p.iter().map(|x| x.1).sum::<f64>() / n)
}
/// Overlap along their length if two segments run parallel within a track's reach of each other,
/// centre to centre; else zero. Collinear retrace counts too.
fn parallel_overlap(s: &Seg, o: &Seg) -> f64 {
parallel_within(s, o, DOUBLED_REACH * NM)
}
fn parallel_within(s: &Seg, o: &Seg, reach: f64) -> f64 {
let (a, b): (V, V) = (s.a.into(), s.b.into());
let (c, d): (V, V) = (o.a.into(), o.b.into());
let l = hypot(sub(b, a));
let m = hypot(sub(d, c));
if l < 1.0 || m < 1.0 {
return 0.0;
}
let u = V((b.0 - a.0) / l, (b.1 - a.1) / l);
let v = V((d.0 - c.0) / m, (d.1 - c.1) / m);
if (u.0 * v.1 - u.1 * v.0).abs() > 0.02 {
return 0.0;
}
let off = ((c.0 - a.0) * -u.1 + (c.1 - a.1) * u.0).abs();
if off > reach {
return 0.0;
}
let t0 = (c.0 - a.0) * u.0 + (c.1 - a.1) * u.1;
let t1 = (d.0 - a.0) * u.0 + (d.1 - a.1) * u.1;
(l.min(t0.max(t1)) - t0.min(t1).max(0.0)).max(0.0)
}
/// Keep width steps to what they buy. A wide stretch between necks shorter than this goes at the neck.
/// A default read off the reference boards, not a rule from his document: his wide sections beside a neck run a
/// median of 3.7 mm on benchmark C (lower quartile 1.3) and 21 mm on benchmark B; on piprobe_v13 he
/// doesn't step signals at all.
const MIN_WIDE_RUN: f64 = 3.0 * NM;
/// One width along a route except where a neck really has to be. Runs are in path order; a via doesn't
/// break a stretch.
pub(crate) fn smooth_widths(segs: &mut [Seg], width: i64, neck: i64) {
if width <= neck || segs.iter().all(|s| s.width == width) {
return;
}
let mut i = 0;
while i < segs.len() {
if segs[i].width != width {
i += 1;
continue;
}
let mut j = i;
let mut len = 0.0;
while j < segs.len() && segs[j].width == width {
len += hypot(sub(segs[j].a.into(), segs[j].b.into()));
j += 1;
}
if len < MIN_WIDE_RUN {
for s in &mut segs[i..j] {
s.width = neck;
}
}
i = j;
}
}
/// If this segment starts lying along one of `others`: `Some(None)` when all of it does, else
/// `Some(Some(p))` with `p` where it comes off. `None` when it doesn't.
fn overlap_end(s: &Seg, others: &[Seg]) -> Option<Option<P>> {
let d = dir_of(s.a, s.b)?;
for o in others.iter().filter(|o| o.layer == s.layer) {
let Some(od) = dir_of(o.a, o.b) else { continue };
if od % 4 != d % 4 || pt_seg(s.a.into(), o.a.into(), o.b.into()) > 2.0 {
continue;
}
if pt_seg(s.b.into(), o.a.into(), o.b.into()) <= 2.0 {
return Some(None);
}
for e in [o.a, o.b] {
// The end of the other track that lies ahead on this one.
if e != s.a && pt_seg(e.into(), s.a.into(), s.b.into()) <= 2.0 {
return Some(Some(e));
}
}
}
None
}
/// How long two nets' copper runs parallel at this centre distance (a pair's pitch).
pub(crate) fn coupled_len(p: &[Seg], n: &[Seg], pitch: f64) -> f64 {
let mut total = 0.0;
for s in p {
for o in n.iter().filter(|o| o.layer == s.layer) {
total += parallel_within(s, o, pitch);
}
}
total
}
/// Join straight pieces of one width back into one segment.
pub(crate) fn merge_runs(segs: &mut Vec<Seg>) {
let mut merged: Vec<Seg> = Vec::new();
for s in segs.drain(..) {
if let Some(l) = merged.last_mut() {
if l.layer == s.layer && l.width == s.width && l.b == s.a && dir_of(l.a, l.b) == dir_of(s.a, s.b) {
l.b = s.b;
continue;
}
}
merged.push(s);
}
*segs = merged;
}
#[cfg(test)]
mod tests {
use super::*;
fn seg(a: P, b: P, width: i64) -> Seg {
Seg { a, b, layer: 0, width }
}
#[test]
fn a_short_wide_stretch_between_necks_goes_at_the_neck() {
let (w, n) = (mm(0.2), mm(0.15));
let mut v = vec![seg((0, 0), (mm(1.0), 0), n), seg((mm(1.0), 0), (mm(2.0), 0), w), seg((mm(2.0), 0), (mm(3.0), 0), n)];
smooth_widths(&mut v, w, n);
assert!(v.iter().all(|s| s.width == n));
// A long one is worth its two steps, and a route with no neck stays as it is however short.
let mut v = vec![seg((0, 0), (mm(1.0), 0), n), seg((mm(1.0), 0), (mm(5.0), 0), w)];
smooth_widths(&mut v, w, n);
assert_eq!(v[1].width, w);
let mut v = vec![seg((0, 0), (mm(1.0), 0), w)];
smooth_widths(&mut v, w, n);
assert_eq!(v[0].width, w);
}
#[test]
fn a_retrace_is_found_and_only_on_the_same_line() {
let other = [seg((0, 0), (mm(2.0), 0), mm(0.2))];
// All of it lies on the other track.
assert_eq!(overlap_end(&seg((mm(0.5), 0), (mm(1.5), 0), mm(0.2)), &other), Some(None));
// Runs off the end at 2 mm.
assert_eq!(overlap_end(&seg((mm(1.0), 0), (mm(3.0), 0), mm(0.2)), &other), Some(Some((mm(2.0), 0))));
// Leaves at an angle, or beside it: not a retrace.
assert_eq!(overlap_end(&seg((mm(1.0), 0), (mm(2.0), mm(1.0)), mm(0.2)), &other), None);
assert_eq!(overlap_end(&seg((mm(1.0), mm(0.1)), (mm(2.0), mm(0.1)), mm(0.2)), &other), None);
}
#[test]
fn doubled_copper_is_measured_side_by_side() {
let a = seg((0, 0), (mm(2.0), 0), mm(0.15));
assert!((parallel_overlap(&a, &seg((mm(1.0), mm(0.158)), (mm(3.0), mm(0.158)), mm(0.15))) - mm(1.0) as f64).abs() < 2.0);
assert_eq!(parallel_overlap(&a, &seg((0, mm(1.0)), (mm(2.0), mm(1.0)), mm(0.15))), 0.0);
assert_eq!(parallel_overlap(&a, &seg((0, 0), (0, mm(2.0)), mm(0.15))), 0.0);
}
#[test]
fn straight_pieces_of_one_width_merge() {
let s = |a: P, b: P, w: i64| Seg { a, b, layer: 0, width: w };
let mut v = vec![s((0, 0), (10, 0), 5), s((10, 0), (20, 0), 5), s((20, 0), (30, 0), 3), s((30, 0), (30, 10), 3)];
merge_runs(&mut v);
assert_eq!(v.len(), 3);
assert_eq!((v[0].a, v[0].b), ((0, 0), (20, 0)));
}
}