Compare commits
17
Commits
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
83ad0f8ef7 | ||
|
|
6e852a929b | ||
|
|
f56bb10996 | ||
|
|
8f656006a6 | ||
|
|
6cc2406583 | ||
|
|
30297e94dc | ||
|
|
45b3753cff | ||
|
|
7d8e5d5c10 | ||
|
|
8152619541 | ||
|
|
714fa873ae | ||
|
|
4a844e8cd7 | ||
|
|
783dd8f0d1 | ||
|
|
8a82143517 | ||
|
|
8a50bde531 | ||
|
|
0f6a2a0812 | ||
|
|
245cd91c0e | ||
|
|
019b043cd5 |
+32
-2
@@ -106,6 +106,15 @@ def _capture_conflicts() -> list:
|
|||||||
return log
|
return log
|
||||||
|
|
||||||
|
|
||||||
|
def _wall_name(wall, names) -> str:
|
||||||
|
if isinstance(wall, str):
|
||||||
|
if wall.startswith("fixed copper of net "):
|
||||||
|
net = int(wall.rsplit(" ", 1)[1])
|
||||||
|
return f"fixed copper of {names.get(net, net)}"
|
||||||
|
return wall
|
||||||
|
return names.get(wall, "pads/keepouts")
|
||||||
|
|
||||||
|
|
||||||
def _gap(a, b) -> int:
|
def _gap(a, b) -> int:
|
||||||
dx = max(b.ll.x - a.ur.x, a.ll.x - b.ur.x, 0)
|
dx = max(b.ll.x - a.ur.x, a.ll.x - b.ur.x, 0)
|
||||||
dy = max(b.ll.y - a.ur.y, a.ll.y - b.ur.y, 0)
|
dy = max(b.ll.y - a.ur.y, a.ll.y - b.ur.y, 0)
|
||||||
@@ -118,6 +127,25 @@ def _fresh(seen) -> GridRouter:
|
|||||||
return router
|
return router
|
||||||
|
|
||||||
|
|
||||||
|
def _static_wall(router: GridRouter, node) -> str:
|
||||||
|
"""What static copper closes a node: a keepout, copper already on the
|
||||||
|
board (a fixed via or track, by net), or a pad."""
|
||||||
|
if node in router._keepout:
|
||||||
|
return "keepout"
|
||||||
|
fixed = getattr(router, "_diag_fixed", None)
|
||||||
|
if fixed is None:
|
||||||
|
fixed = router._diag_fixed = {}
|
||||||
|
margin = router.clearance + router.half_width
|
||||||
|
for net, layers, box in router.board.get_fixed_copper():
|
||||||
|
for cell in router._cells_in_box(box, margin):
|
||||||
|
for layer in layers:
|
||||||
|
fixed[(*cell, layer)] = net
|
||||||
|
net = fixed.get(node)
|
||||||
|
if net is not None:
|
||||||
|
return f"fixed copper of net {net}"
|
||||||
|
return "pads"
|
||||||
|
|
||||||
|
|
||||||
def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
|
def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
|
||||||
"""How many nodes a pin can reach through free cells (up to FLOOD_LIMIT),
|
"""How many nodes a pin can reach through free cells (up to FLOOD_LIMIT),
|
||||||
and which other nets' copper bounds the region."""
|
and which other nets' copper bounds the region."""
|
||||||
@@ -146,7 +174,7 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
|
|||||||
for owner in owners:
|
for owner in owners:
|
||||||
walls[conns[owner].net_no] += 1
|
walls[conns[owner].net_no] += 1
|
||||||
if not owners:
|
if not owners:
|
||||||
walls[0] += 1 # a pad or keepout
|
walls[_static_wall(router, n)] += 1
|
||||||
continue
|
continue
|
||||||
seen.add(n)
|
seen.add(n)
|
||||||
frontier.append(n)
|
frontier.append(n)
|
||||||
@@ -224,7 +252,9 @@ def diagnose(
|
|||||||
if reach < FLOOD_LIMIT:
|
if reach < FLOOD_LIMIT:
|
||||||
walled.append({
|
walled.append({
|
||||||
"pin": end, "reach": reach,
|
"pin": end, "reach": reach,
|
||||||
"walls": [names.get(n, "pads/keepouts") for n, _ in walls.most_common(4)],
|
"walls": [
|
||||||
|
_wall_name(n, names) for n, _ in walls.most_common(4)
|
||||||
|
],
|
||||||
})
|
})
|
||||||
row["kind"] = "walled-in" if walled else "congestion"
|
row["kind"] = "walled-in" if walled else "congestion"
|
||||||
if walled:
|
if walled:
|
||||||
|
|||||||
@@ -70,6 +70,27 @@ class BasicBoard:
|
|||||||
def get_traces(self) -> list[Trace]:
|
def get_traces(self) -> list[Trace]:
|
||||||
return [it for it in self._items if isinstance(it, Trace)]
|
return [it for it in self._items if isinstance(it, Trace)]
|
||||||
|
|
||||||
|
def get_fixed_copper(self) -> list[tuple[int, frozenset[int], IntBox]]:
|
||||||
|
"""Copper already routed on the board (the DSN's ``wiring``), as
|
||||||
|
``(net, layers, box)``. A track is its segments, its corners and the
|
||||||
|
round caps at its ends (as squares); a via is its largest pad."""
|
||||||
|
from freeroute.geometry.polyline import Polyline, PolylineShape, corner_box
|
||||||
|
|
||||||
|
out: list[tuple[int, frozenset[int], IntBox]] = []
|
||||||
|
for item in self._items:
|
||||||
|
if not item.fixed or not item.net_nos:
|
||||||
|
continue
|
||||||
|
net = item.net_nos[0]
|
||||||
|
if isinstance(item, Trace) and not item.is_empty():
|
||||||
|
layers = frozenset({item.layer})
|
||||||
|
for box in PolylineShape(Polyline(item.corners), item.half_width).tiles():
|
||||||
|
out.append((net, layers, box))
|
||||||
|
for end in (item.corners[0], item.corners[-1]):
|
||||||
|
out.append((net, layers, corner_box(end, item.half_width)))
|
||||||
|
elif isinstance(item, Via) and item.shape is not None:
|
||||||
|
out.append((net, frozenset(item.layers), item.shape.bounding_box()))
|
||||||
|
return out
|
||||||
|
|
||||||
def get_vias(self) -> list[Via]:
|
def get_vias(self) -> list[Via]:
|
||||||
return [it for it in self._items if isinstance(it, Via)]
|
return [it for it in self._items if isinstance(it, Via)]
|
||||||
|
|
||||||
|
|||||||
@@ -23,6 +23,7 @@ the containment invariant, and pads are centre-symmetric in practice).
|
|||||||
from __future__ import annotations
|
from __future__ import annotations
|
||||||
|
|
||||||
import math
|
import math
|
||||||
|
import re
|
||||||
|
|
||||||
from freeroute.dsn.model import DsnBoard
|
from freeroute.dsn.model import DsnBoard
|
||||||
from freeroute.dsn.shapes import Circle, Path, Polygon, Rectangle, Shape
|
from freeroute.dsn.shapes import Circle, Path, Polygon, Rectangle, Shape
|
||||||
@@ -31,13 +32,16 @@ from freeroute.geometry.polygon_shape import PolygonShape
|
|||||||
|
|
||||||
from .board import BasicBoard
|
from .board import BasicBoard
|
||||||
from .clearance import ClearanceMatrix
|
from .clearance import ClearanceMatrix
|
||||||
from .items import ConductionArea, ObstacleArea, Pin
|
from .items import ConductionArea, ObstacleArea, Pin, Trace, Via
|
||||||
from .layer import Layer, LayerStructure
|
from .layer import Layer, LayerStructure
|
||||||
from .net import Nets
|
from .net import Nets
|
||||||
from .transform import CoordinateTransform
|
from .transform import CoordinateTransform
|
||||||
|
|
||||||
__all__ = ["build_board"]
|
__all__ = ["build_board"]
|
||||||
|
|
||||||
|
# DSN units per micrometre, for drills KiCad gives in um in via padstack names
|
||||||
|
_DSN_PER_UM = {"um": 1.0, "mm": 0.001, "mil": 1 / 25.4, "inch": 1 / 25400}
|
||||||
|
|
||||||
|
|
||||||
def build_board(dsn: DsnBoard) -> BasicBoard:
|
def build_board(dsn: DsnBoard) -> BasicBoard:
|
||||||
"""Construct a :class:`BasicBoard` from a parsed :class:`DsnBoard`."""
|
"""Construct a :class:`BasicBoard` from a parsed :class:`DsnBoard`."""
|
||||||
@@ -56,6 +60,7 @@ def build_board(dsn: DsnBoard) -> BasicBoard:
|
|||||||
_insert_keepouts(dsn, board, transform)
|
_insert_keepouts(dsn, board, transform)
|
||||||
_insert_image_keepouts(dsn, board, transform)
|
_insert_image_keepouts(dsn, board, transform)
|
||||||
_insert_zones(dsn, board, transform, nets)
|
_insert_zones(dsn, board, transform, nets)
|
||||||
|
_insert_wiring(dsn, board, transform, nets)
|
||||||
return board
|
return board
|
||||||
|
|
||||||
|
|
||||||
@@ -471,6 +476,52 @@ def _placed_area_tiles(shape: Shape, place, transform: CoordinateTransform) -> l
|
|||||||
return [tile for tile in PolygonShape(pts).split_to_convex() if not tile.is_empty()]
|
return [tile for tile in PolygonShape(pts).split_to_convex() if not tile.is_empty()]
|
||||||
|
|
||||||
|
|
||||||
|
def _insert_wiring(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransform, nets) -> None:
|
||||||
|
"""Tracks and vias already on the board, as fixed copper of their nets."""
|
||||||
|
layer_no = {layer.name: i for i, layer in enumerate(dsn.layers)}
|
||||||
|
signal_layers = [i for i, layer in enumerate(dsn.layers) if layer.is_signal]
|
||||||
|
numbers = {net.name: net.net_number for net in nets}
|
||||||
|
for wire in dsn.wires:
|
||||||
|
if wire.net not in numbers or wire.layer not in layer_no:
|
||||||
|
continue
|
||||||
|
c = wire.coords
|
||||||
|
corners = [transform.dsn_to_board_point(c[i], c[i + 1]) for i in range(0, len(c) - 1, 2)]
|
||||||
|
if len(corners) < 2:
|
||||||
|
continue
|
||||||
|
board.insert(
|
||||||
|
Trace(
|
||||||
|
net_nos=[numbers[wire.net]], fixed=True, layer=layer_no[wire.layer],
|
||||||
|
half_width=max(round(transform.dsn_to_board(wire.width / 2)), 1), corners=corners,
|
||||||
|
)
|
||||||
|
)
|
||||||
|
for via in dsn.vias:
|
||||||
|
padstack = dsn.padstack(via.padstack)
|
||||||
|
if via.net not in numbers or padstack is None or not padstack.shapes:
|
||||||
|
continue
|
||||||
|
layers: set[int] = set()
|
||||||
|
for shape in padstack.shapes:
|
||||||
|
if shape.layer in ("signal", "pcb"):
|
||||||
|
layers.update(signal_layers)
|
||||||
|
elif shape.layer in layer_no:
|
||||||
|
layers.add(layer_no[shape.layer])
|
||||||
|
location = transform.dsn_to_board_point(via.x, via.y)
|
||||||
|
pad = _pad_tile(max(padstack.shapes, key=_shape_extent), transform)
|
||||||
|
box = pad.bounding_box()
|
||||||
|
drill = re.search(r"_([\d.]+):([\d.]+)_um", via.padstack)
|
||||||
|
drill_board = (
|
||||||
|
round(transform.dsn_to_board(float(drill.group(2)) * _DSN_PER_UM.get(dsn.unit, 1.0)))
|
||||||
|
if drill else 0
|
||||||
|
)
|
||||||
|
board.insert(
|
||||||
|
Via(
|
||||||
|
net_nos=[numbers[via.net]], fixed=True, padstack_name=via.padstack,
|
||||||
|
drill=drill_board, location=location, layers=sorted(layers or signal_layers),
|
||||||
|
shape=IntBox(box.ll.x + location.x, box.ll.y + location.y,
|
||||||
|
box.ur.x + location.x, box.ur.y + location.y),
|
||||||
|
)
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
def _insert_zones(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransform, nets) -> None:
|
def _insert_zones(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransform, nets) -> None:
|
||||||
"""Each DSN plane as a ConductionArea of its net on its layer."""
|
"""Each DSN plane as a ConductionArea of its net on its layer."""
|
||||||
layer_no = {layer.name: i for i, layer in enumerate(dsn.layers)}
|
layer_no = {layer.name: i for i, layer in enumerate(dsn.layers)}
|
||||||
|
|||||||
@@ -114,6 +114,11 @@ class Via(Item):
|
|||||||
|
|
||||||
padstack_name: str = ""
|
padstack_name: str = ""
|
||||||
location: IntPoint = field(default_factory=lambda: IntPoint(0, 0))
|
location: IntPoint = field(default_factory=lambda: IntPoint(0, 0))
|
||||||
|
#: layer indices the via's pads occupy, and the largest pad as a box
|
||||||
|
layers: list[int] = field(default_factory=list)
|
||||||
|
shape: object = None
|
||||||
|
#: drill diameter in board units, when the padstack name gives it
|
||||||
|
drill: int = 0
|
||||||
|
|
||||||
|
|
||||||
@dataclass
|
@dataclass
|
||||||
|
|||||||
@@ -175,6 +175,14 @@ def build_parser() -> argparse.ArgumentParser:
|
|||||||
"connections a rip-up displaces are rerouted at once and the rip-up is undone "
|
"connections a rip-up displaces are rerouted at once and the rip-up is undone "
|
||||||
"if fewer connections end up routed",
|
"if fewer connections end up routed",
|
||||||
)
|
)
|
||||||
|
parser.add_argument(
|
||||||
|
"--hole-to-hole",
|
||||||
|
type=float,
|
||||||
|
default=0.25,
|
||||||
|
metavar="MM",
|
||||||
|
help="grid and exact engines: least distance between the edges of any two via "
|
||||||
|
"holes, of one net or two (KiCad's min_hole_to_hole; default 0.25)",
|
||||||
|
)
|
||||||
parser.add_argument(
|
parser.add_argument(
|
||||||
"--jobs",
|
"--jobs",
|
||||||
type=int,
|
type=int,
|
||||||
@@ -239,6 +247,7 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
"resolution": 2 if args.grid_resolution is None else args.grid_resolution,
|
"resolution": 2 if args.grid_resolution is None else args.grid_resolution,
|
||||||
"heuristic_weight": args.heuristic_weight,
|
"heuristic_weight": args.heuristic_weight,
|
||||||
"access_cost": args.access_cost or 0.0,
|
"access_cost": args.access_cost or 0.0,
|
||||||
|
"hole_to_hole_mm": args.hole_to_hole,
|
||||||
"rollback": args.rollback,
|
"rollback": args.rollback,
|
||||||
}
|
}
|
||||||
elif args.engine == "grid":
|
elif args.engine == "grid":
|
||||||
@@ -249,6 +258,7 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
"edge_clearance_mm": args.edge_clearance,
|
"edge_clearance_mm": args.edge_clearance,
|
||||||
"resolution": 1 if args.grid_resolution is None else args.grid_resolution,
|
"resolution": 1 if args.grid_resolution is None else args.grid_resolution,
|
||||||
"access_cost": args.access_cost or 0.0,
|
"access_cost": args.access_cost or 0.0,
|
||||||
|
"hole_to_hole_mm": args.hole_to_hole,
|
||||||
"rollback": args.rollback,
|
"rollback": args.rollback,
|
||||||
}
|
}
|
||||||
if args.engine == "room":
|
if args.engine == "room":
|
||||||
@@ -287,6 +297,14 @@ def main(argv: list[str] | None = None) -> int:
|
|||||||
print(f"freeroute: {len(missing)} connection(s) not routed:", file=sys.stderr)
|
print(f"freeroute: {len(missing)} connection(s) not routed:", file=sys.stderr)
|
||||||
for net, a, b, _zone in missing:
|
for net, a, b, _zone in missing:
|
||||||
print(f" {net}: {a} to {b}", file=sys.stderr)
|
print(f" {net}: {a} to {b}", file=sys.stderr)
|
||||||
|
if result.narrowed:
|
||||||
|
print(
|
||||||
|
f"freeroute: {len(result.narrowed)} connection(s) of a wider net class only fitted "
|
||||||
|
"at the default width; their nets are written at the default width:",
|
||||||
|
file=sys.stderr,
|
||||||
|
)
|
||||||
|
for net, a, b in result.narrowed:
|
||||||
|
print(f" {net}: {a} to {b}", file=sys.stderr)
|
||||||
if in_zone:
|
if in_zone:
|
||||||
print(
|
print(
|
||||||
f"freeroute: {len(in_zone)} more connection(s) left to a zone fill that may join them:",
|
f"freeroute: {len(in_zone)} more connection(s) left to a zone fill that may join them:",
|
||||||
|
|||||||
@@ -27,6 +27,8 @@ __all__ = [
|
|||||||
"NetPin",
|
"NetPin",
|
||||||
"Net",
|
"Net",
|
||||||
"NetClass",
|
"NetClass",
|
||||||
|
"WiringVia",
|
||||||
|
"WiringWire",
|
||||||
"Keepout",
|
"Keepout",
|
||||||
"DsnBoard",
|
"DsnBoard",
|
||||||
]
|
]
|
||||||
@@ -186,6 +188,26 @@ class Keepout:
|
|||||||
kind: str = "keepout" # keepout | via_keepout | wire_keepout | place_keepout
|
kind: str = "keepout" # keepout | via_keepout | wire_keepout | place_keepout
|
||||||
|
|
||||||
|
|
||||||
|
@dataclass
|
||||||
|
class WiringWire:
|
||||||
|
"""A track already on the board: ``(wire (path LAYER WIDTH x y ...) (net N))``."""
|
||||||
|
|
||||||
|
net: str
|
||||||
|
layer: str
|
||||||
|
width: float
|
||||||
|
coords: list[float] = field(default_factory=list)
|
||||||
|
|
||||||
|
|
||||||
|
@dataclass
|
||||||
|
class WiringVia:
|
||||||
|
"""A via already on the board: ``(via PADSTACK x y (net N))``."""
|
||||||
|
|
||||||
|
net: str
|
||||||
|
padstack: str
|
||||||
|
x: float
|
||||||
|
y: float
|
||||||
|
|
||||||
|
|
||||||
@dataclass
|
@dataclass
|
||||||
class DsnBoard:
|
class DsnBoard:
|
||||||
"""The fully parsed DSN file."""
|
"""The fully parsed DSN file."""
|
||||||
@@ -197,6 +219,9 @@ class DsnBoard:
|
|||||||
layers: list[Layer] = field(default_factory=list)
|
layers: list[Layer] = field(default_factory=list)
|
||||||
#: copper zones, as planes of a net
|
#: copper zones, as planes of a net
|
||||||
planes: list[Plane] = field(default_factory=list)
|
planes: list[Plane] = field(default_factory=list)
|
||||||
|
#: copper already routed (the ``wiring`` scope), kept fixed
|
||||||
|
wires: list[WiringWire] = field(default_factory=list)
|
||||||
|
vias: list[WiringVia] = field(default_factory=list)
|
||||||
#: bounding-box boundary shape (layer ``pcb``), if present
|
#: bounding-box boundary shape (layer ``pcb``), if present
|
||||||
boundary: Shape | None = None
|
boundary: Shape | None = None
|
||||||
#: outline shapes (layer ``signal``)
|
#: outline shapes (layer ``signal``)
|
||||||
|
|||||||
@@ -27,6 +27,8 @@ from .model import (
|
|||||||
Pin,
|
Pin,
|
||||||
Resolution,
|
Resolution,
|
||||||
WidthRule,
|
WidthRule,
|
||||||
|
WiringVia,
|
||||||
|
WiringWire,
|
||||||
)
|
)
|
||||||
from .sexp import SExp, parse
|
from .sexp import SExp, parse
|
||||||
from .shapes import Shape, read_area, read_shape
|
from .shapes import Shape, read_area, read_shape
|
||||||
@@ -531,11 +533,45 @@ def parse_dsn(text: str) -> DsnBoard:
|
|||||||
_read_placement(it, board)
|
_read_placement(it, board)
|
||||||
elif head == "network":
|
elif head == "network":
|
||||||
_read_network(it, board)
|
_read_network(it, board)
|
||||||
# `wiring` and unknown scopes are intentionally ignored for now.
|
elif head == "wiring":
|
||||||
|
_read_wiring(it, board)
|
||||||
|
# unknown scopes are ignored
|
||||||
|
|
||||||
return board
|
return board
|
||||||
|
|
||||||
|
|
||||||
|
def _read_wiring(node: SExp, board: DsnBoard) -> None:
|
||||||
|
"""Tracks and vias already on the board. They stay where they are: the
|
||||||
|
router treats them as copper of their net that other nets keep clear of."""
|
||||||
|
for it in node.items:
|
||||||
|
if not isinstance(it, SExp):
|
||||||
|
continue
|
||||||
|
net_scope = it.child("net")
|
||||||
|
net = _first_value(net_scope) if net_scope is not None else None
|
||||||
|
if not net:
|
||||||
|
continue # netless copper would need a keepout, not a wire
|
||||||
|
if it.head == "wire":
|
||||||
|
path = it.child("path") or it.child("polyline_path")
|
||||||
|
vals = [v.text for v in path.values()] if path is not None else []
|
||||||
|
if len(vals) < 6:
|
||||||
|
continue
|
||||||
|
try:
|
||||||
|
width = float(vals[1])
|
||||||
|
coords = [float(v) for v in vals[2:]]
|
||||||
|
except ValueError:
|
||||||
|
continue
|
||||||
|
board.wires.append(WiringWire(net=net, layer=vals[0], width=width, coords=coords))
|
||||||
|
elif it.head == "via":
|
||||||
|
vals = [v.text for v in it.values()]
|
||||||
|
if len(vals) < 3:
|
||||||
|
continue
|
||||||
|
try:
|
||||||
|
x, y = float(vals[1]), float(vals[2])
|
||||||
|
except ValueError:
|
||||||
|
continue
|
||||||
|
board.vias.append(WiringVia(net=net, padstack=vals[0], x=x, y=y))
|
||||||
|
|
||||||
|
|
||||||
def _read_plane(node: SExp):
|
def _read_plane(node: SExp):
|
||||||
"""``(plane <net> (polygon <layer> <width> x y ...))`` -> :class:`Plane`."""
|
"""``(plane <net> (polygon <layer> <width> x y ...))`` -> :class:`Plane`."""
|
||||||
from .model import Plane
|
from .model import Plane
|
||||||
|
|||||||
@@ -31,7 +31,7 @@ from dataclasses import dataclass, field
|
|||||||
import math
|
import math
|
||||||
|
|
||||||
from freeroute.board.board import BasicBoard
|
from freeroute.board.board import BasicBoard
|
||||||
from freeroute.board.items import Pin
|
from freeroute.board.items import Pin, Via
|
||||||
from freeroute.board.search_tree import ShapeSearchTree, TreeShape
|
from freeroute.board.search_tree import ShapeSearchTree, TreeShape
|
||||||
from freeroute.geometry import (
|
from freeroute.geometry import (
|
||||||
IntBox,
|
IntBox,
|
||||||
@@ -99,6 +99,9 @@ def route_board_exact(
|
|||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
|
net_widths: dict[int, int] | None = None,
|
||||||
|
via_drill: int | None = None,
|
||||||
|
hole_to_hole: int = 0,
|
||||||
) -> ExactRouteResult:
|
) -> ExactRouteResult:
|
||||||
"""Route ``board`` orthogonally and verify the result with exact geometry.
|
"""Route ``board`` orthogonally and verify the result with exact geometry.
|
||||||
|
|
||||||
@@ -131,6 +134,9 @@ def route_board_exact(
|
|||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
|
net_widths=net_widths,
|
||||||
|
via_drill=via_drill,
|
||||||
|
hole_to_hole=hole_to_hole,
|
||||||
)
|
)
|
||||||
edge = 0 if edge_clearance is None else edge_clearance
|
edge = 0 if edge_clearance is None else edge_clearance
|
||||||
outline = board.outline
|
outline = board.outline
|
||||||
@@ -149,6 +155,10 @@ def route_board_exact(
|
|||||||
pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
|
pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
|
||||||
if pin_layers:
|
if pin_layers:
|
||||||
tree.insert(TreeShape(next(owner), net, pin_layers, box))
|
tree.insert(TreeShape(next(owner), net, pin_layers, box))
|
||||||
|
for net, copper_layers, box in board.get_fixed_copper():
|
||||||
|
on = frozenset(layer for layer in copper_layers if layer in signal_layers)
|
||||||
|
if on and not box.is_empty():
|
||||||
|
tree.insert(TreeShape(next(owner), net, on, box))
|
||||||
for obstacle in board.get_obstacle_areas():
|
for obstacle in board.get_obstacle_areas():
|
||||||
if obstacle.layer not in signal_layers:
|
if obstacle.layer not in signal_layers:
|
||||||
continue
|
continue
|
||||||
@@ -168,23 +178,32 @@ def route_board_exact(
|
|||||||
|
|
||||||
via_layers = frozenset(signal_layers)
|
via_layers = frozenset(signal_layers)
|
||||||
accepted: dict[int, _Accepted] = {}
|
accepted: dict[int, _Accepted] = {}
|
||||||
|
fixed_vias = {
|
||||||
|
(item.net_nos[0], item.location)
|
||||||
|
for item in board.get_items()
|
||||||
|
if isinstance(item, Via) and item.fixed and item.net_nos
|
||||||
|
}
|
||||||
|
|
||||||
# Verify connection by connection, so one conflicting segment of a
|
# Verify connection by connection, so one conflicting segment of a
|
||||||
# 25-pin supply net costs that one connection, not the whole net.
|
# 25-pin supply net costs that one connection, not the whole net.
|
||||||
rejected: list[tuple[int, str, str]] = []
|
rejected: list[tuple[int, str, str]] = []
|
||||||
ends_list = result.connection_ends or [("?", "?", "")] * len(result.connections)
|
ends_list = result.connection_ends or [("?", "?", "")] * len(result.connections)
|
||||||
|
# each net is checked at the width it will be written at: its class's
|
||||||
|
# when all of its connections went in at that, else the default
|
||||||
|
net_half = dict(result.net_half)
|
||||||
for (net_no, wires, vias), ends in sorted(
|
for (net_no, wires, vias), ends in sorted(
|
||||||
zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
|
zip(result.connections, ends_list, strict=False), key=lambda c: c[0][0]
|
||||||
):
|
):
|
||||||
boxes = _copper_boxes(wires, vias, half_width, via_layers, via_half)
|
wire_half = net_half.get(net_no, half_width)
|
||||||
wire_count = len(_copper_boxes(wires, [], half_width, via_layers, via_half))
|
boxes = _copper_boxes(wires, vias, wire_half, via_layers, via_half)
|
||||||
|
wire_count = len(_copper_boxes(wires, [], wire_half, via_layers, via_half))
|
||||||
if any(
|
if any(
|
||||||
tree.clearance_conflict(
|
tree.clearance_conflict(
|
||||||
box, net_no, layer, clearance, "wire" if i < wire_count else "via"
|
box, net_no, layer, clearance, "wire" if i < wire_count else "via"
|
||||||
)
|
)
|
||||||
for i, (box, box_layers) in enumerate(boxes)
|
for i, (box, box_layers) in enumerate(boxes)
|
||||||
for layer in box_layers
|
for layer in box_layers
|
||||||
) or _end_in_rule_area(tree, wires, half_width) or (
|
) or _end_in_rule_area(tree, wires, wire_half) or (
|
||||||
outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
|
outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
|
||||||
):
|
):
|
||||||
rejected.append((net_no, *ends))
|
rejected.append((net_no, *ends))
|
||||||
@@ -193,7 +212,12 @@ def route_board_exact(
|
|||||||
if acc is None:
|
if acc is None:
|
||||||
acc = accepted[net_no] = _Accepted(wires=[], vias=[])
|
acc = accepted[net_no] = _Accepted(wires=[], vias=[])
|
||||||
acc.wires.extend(wires)
|
acc.wires.extend(wires)
|
||||||
acc.vias.extend(vias)
|
# connections of one net that end on the same plane cell share its
|
||||||
|
# via: write it once, and never on top of a via already on the board
|
||||||
|
acc.vias.extend(
|
||||||
|
v for v in dict.fromkeys(vias)
|
||||||
|
if v not in acc.vias and not _on_fixed_via(net_no, v, fixed_vias, via_half)
|
||||||
|
)
|
||||||
for box, box_layers in boxes:
|
for box, box_layers in boxes:
|
||||||
oid = next(owner)
|
oid = next(owner)
|
||||||
tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
|
tree.insert(TreeShape(oid, net_no, box_layers, box, routed=True))
|
||||||
@@ -243,6 +267,17 @@ def route_board_exact(
|
|||||||
for net_no, acc in accepted.items():
|
for net_no, acc in accepted.items():
|
||||||
clean.wires[net_no] = acc.wires
|
clean.wires[net_no] = acc.wires
|
||||||
clean.vias[net_no] = acc.vias
|
clean.vias[net_no] = acc.vias
|
||||||
|
# shove and the diagonal pass lay copper at the default width: nets they
|
||||||
|
# recovered, and nets whose traces shove pushed aside
|
||||||
|
reshaped = (set(accepted) - accepted_before_recovery) | {
|
||||||
|
net for net, acc in accepted.items() if acc.shove_count
|
||||||
|
}
|
||||||
|
if diagonal:
|
||||||
|
reshaped = set(accepted)
|
||||||
|
clean.net_half = {
|
||||||
|
net: half for net, half in net_half.items() if net in accepted and net not in reshaped
|
||||||
|
}
|
||||||
|
clean.narrowed = list(result.narrowed)
|
||||||
|
|
||||||
drc_clean = tree.has_violation(clearance) is None
|
drc_clean = tree.has_violation(clearance) is None
|
||||||
return ExactRouteResult(result=clean, tree=tree, drc_clean=drc_clean, shoves=shoves)
|
return ExactRouteResult(result=clean, tree=tree, drc_clean=drc_clean, shoves=shoves)
|
||||||
@@ -611,6 +646,15 @@ def _end_in_rule_area(tree, wires, half_width) -> bool:
|
|||||||
return False
|
return False
|
||||||
|
|
||||||
|
|
||||||
|
def _on_fixed_via(net_no, point, fixed_vias, via_half) -> bool:
|
||||||
|
"""A routed via that reuses a via already on the board: the grid put it
|
||||||
|
on the fixed via's cell, a little off its centre, and it is not written."""
|
||||||
|
return any(
|
||||||
|
net == net_no and abs(loc.x - point.x) <= via_half and abs(loc.y - point.y) <= via_half
|
||||||
|
for net, loc in fixed_vias
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
|
def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
|
||||||
via_half = via_half or half_width
|
via_half = via_half or half_width
|
||||||
boxes: list[tuple[IntBox, frozenset[int]]] = []
|
boxes: list[tuple[IntBox, frozenset[int]]] = []
|
||||||
|
|||||||
@@ -31,7 +31,7 @@ import math
|
|||||||
import random
|
import random
|
||||||
|
|
||||||
from freeroute.board.board import BasicBoard
|
from freeroute.board.board import BasicBoard
|
||||||
from freeroute.board.items import ConductionArea, ObstacleArea, Pin
|
from freeroute.board.items import ConductionArea, ObstacleArea, Pin, Via
|
||||||
from freeroute.geometry import IntBox, IntPoint
|
from freeroute.geometry import IntBox, IntPoint
|
||||||
from freeroute.geometry.polyline import corner_box
|
from freeroute.geometry.polyline import corner_box
|
||||||
|
|
||||||
@@ -61,7 +61,10 @@ class RouteResult:
|
|||||||
``routed_net_numbers`` are the nets that got any wire or via.
|
``routed_net_numbers`` are the nets that got any wire or via.
|
||||||
"""
|
"""
|
||||||
|
|
||||||
__slots__ = ("wires", "vias", "half_width", "unrouted", "connections", "connection_ends", "failed")
|
__slots__ = (
|
||||||
|
"wires", "vias", "half_width", "unrouted", "connections", "connection_ends", "failed",
|
||||||
|
"net_half", "narrowed",
|
||||||
|
)
|
||||||
|
|
||||||
def __init__(self, half_width: int) -> None:
|
def __init__(self, half_width: int) -> None:
|
||||||
self.wires: dict[int, list[tuple[int, list[IntPoint]]]] = {}
|
self.wires: dict[int, list[tuple[int, list[IntPoint]]]] = {}
|
||||||
@@ -76,6 +79,10 @@ class RouteResult:
|
|||||||
self.connection_ends: list[tuple[str, str, str]] = []
|
self.connection_ends: list[tuple[str, str, str]] = []
|
||||||
#: connections left unrouted: (net_no, one end, the other end)
|
#: connections left unrouted: (net_no, one end, the other end)
|
||||||
self.failed: list[tuple[int, str, str]] = []
|
self.failed: list[tuple[int, str, str]] = []
|
||||||
|
#: half width of each net routed wider than the default (its class)
|
||||||
|
self.net_half: dict[int, int] = {}
|
||||||
|
#: connections of a wider class that only fitted at the default width
|
||||||
|
self.narrowed: list[tuple[int, str, str]] = []
|
||||||
|
|
||||||
def add_wire(self, net_no: int, layer: int, path: list[IntPoint]) -> None:
|
def add_wire(self, net_no: int, layer: int, path: list[IntPoint]) -> None:
|
||||||
self.wires.setdefault(net_no, []).append((layer, path))
|
self.wires.setdefault(net_no, []).append((layer, path))
|
||||||
@@ -114,6 +121,8 @@ class _Connection:
|
|||||||
"a_end",
|
"a_end",
|
||||||
"b_end",
|
"b_end",
|
||||||
"path",
|
"path",
|
||||||
|
"narrow",
|
||||||
|
"half",
|
||||||
)
|
)
|
||||||
|
|
||||||
def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
|
def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
|
||||||
@@ -137,6 +146,10 @@ class _Connection:
|
|||||||
self.b_end: Pin | None = b
|
self.b_end: Pin | None = b
|
||||||
# the node path last committed, so a rip-up can be undone
|
# the node path last committed, so a rip-up can be undone
|
||||||
self.path: list[Node] | None = None
|
self.path: list[Node] | None = None
|
||||||
|
# a connection of a wider class that did not fit at that width is
|
||||||
|
# routed at the default width instead; the half width it went in at
|
||||||
|
self.narrow = False
|
||||||
|
self.half = 0
|
||||||
|
|
||||||
|
|
||||||
class GridRouter:
|
class GridRouter:
|
||||||
@@ -163,6 +176,9 @@ class GridRouter:
|
|||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
|
net_widths: dict[int, int] | None = None,
|
||||||
|
via_drill: int | None = None,
|
||||||
|
hole_to_hole: int = 0,
|
||||||
) -> None:
|
) -> None:
|
||||||
self.board = board
|
self.board = board
|
||||||
# Pin access: while a pin still has connections to route, the cells
|
# Pin access: while a pin still has connections to route, the cells
|
||||||
@@ -223,6 +239,38 @@ class GridRouter:
|
|||||||
self.edge_clearance = 0 if edge_clearance is None else edge_clearance
|
self.edge_clearance = 0 if edge_clearance is None else edge_clearance
|
||||||
need = self.via_half + self.clearance + self.half_width
|
need = self.via_half + self.clearance + self.half_width
|
||||||
self.via_reach = max(0, math.ceil(need / self.step) - 1)
|
self.via_reach = max(0, math.ceil(need / self.step) - 1)
|
||||||
|
# Net classes wider than the default: the grid is laid out for the
|
||||||
|
# default width, so a wider trace must also find the cells around its
|
||||||
|
# own free, out to its extra half width, and claims a wider halo.
|
||||||
|
self._net_half = {
|
||||||
|
net: max(width // 2, 1)
|
||||||
|
for net, width in (net_widths or {}).items()
|
||||||
|
if width // 2 > self.half_width
|
||||||
|
}
|
||||||
|
self._spread: list[tuple[int, int]] = [] # the current search's
|
||||||
|
self._cur_half = self.half_width
|
||||||
|
self._halo_by_half: dict[int, list[tuple[int, int]]] = {self.half_width: self._halo_offsets}
|
||||||
|
# Hole-to-hole spacing holds between any two vias, of one net or two.
|
||||||
|
# Other nets' vias are kept further apart already; a net's own vias
|
||||||
|
# (every pin of a supply dropping to its plane) are not, so a via
|
||||||
|
# must keep its drill plus the spacing from every via centre, except
|
||||||
|
# an own-net via at the very same cell, which it simply reuses.
|
||||||
|
drill = via_drill if via_drill else 2 * self.via_half
|
||||||
|
need = drill + max(hole_to_hole, 0)
|
||||||
|
self._via_drill, self._hole_gap, self._hole_need = drill, max(hole_to_hole, 0), need
|
||||||
|
reach = math.ceil(need / self.step)
|
||||||
|
self._hole_offsets = [
|
||||||
|
(dx, dy)
|
||||||
|
for dx in range(-reach, reach + 1)
|
||||||
|
for dy in range(-reach, reach + 1)
|
||||||
|
if (dx or dy) and math.hypot(dx, dy) * self.step < need
|
||||||
|
]
|
||||||
|
self._via_nets: dict[Cell, dict[int, int]] = {} # routed via centres
|
||||||
|
self._via_centres: list[IntPoint] | None = None # cache for _hole_clear_at
|
||||||
|
self._fixed_vias: dict[Cell, int] = {}
|
||||||
|
# fixed vias sit anywhere, not on cell centres: exact hole checks
|
||||||
|
self._fixed_holes: list[tuple[IntPoint, int]] = []
|
||||||
|
self._fixed_via_points: set[tuple[int, IntPoint]] = set()
|
||||||
|
|
||||||
if layers is None:
|
if layers is None:
|
||||||
layers = [i for i, layer in enumerate(board.layer_structure.arr) if layer.is_signal]
|
layers = [i for i, layer in enumerate(board.layer_structure.arr) if layer.is_signal]
|
||||||
@@ -250,6 +298,29 @@ class GridRouter:
|
|||||||
# trace halos: node -> indices of the connections claiming it
|
# trace halos: node -> indices of the connections claiming it
|
||||||
self._halo: dict[Node, list[int]] = {}
|
self._halo: dict[Node, list[int]] = {}
|
||||||
self._rasterize_obstacles()
|
self._rasterize_obstacles()
|
||||||
|
self._rasterize_fixed_copper()
|
||||||
|
for item in board.get_items():
|
||||||
|
if isinstance(item, Via) and item.fixed and item.net_nos:
|
||||||
|
self._fixed_vias[self._cell_of(item.location)] = item.net_nos[0]
|
||||||
|
self._fixed_via_points.add((item.net_nos[0], item.location))
|
||||||
|
# its own drill, from KiCad's padstack name (Via[0-3]_500:250_um)
|
||||||
|
reach = self._via_drill // 2 + (item.drill or self._via_drill) // 2 + self._hole_gap
|
||||||
|
self._fixed_holes.append((item.location, reach))
|
||||||
|
# Through-hole pads have holes too, and a route changes layer at one
|
||||||
|
# for free, so no via (of any net) goes within hole spacing of one.
|
||||||
|
# The DSN has no drill for a pad; its smaller half size stands in.
|
||||||
|
self._tht_holes: list[tuple[IntPoint, int]] = []
|
||||||
|
self._tht_block: set[Cell] = set()
|
||||||
|
for pin in board.get_pins():
|
||||||
|
if pin.shape is None or sum(1 for layer in pin.layers if layer in self.layers) < 2:
|
||||||
|
continue
|
||||||
|
box = pin.shape.bounding_box()
|
||||||
|
radius = min(box.ur.x - box.ll.x, box.ur.y - box.ll.y) // 2
|
||||||
|
reach = radius + self._via_drill // 2 + self._hole_gap
|
||||||
|
self._tht_holes.append((pin.location, reach))
|
||||||
|
ring = IntBox(pin.location.x, pin.location.y, pin.location.x, pin.location.y)
|
||||||
|
for cell in self._cells_in_box(ring, reach):
|
||||||
|
self._tht_block.add(cell)
|
||||||
|
|
||||||
# --- grid helpers -------------------------------------------------------
|
# --- grid helpers -------------------------------------------------------
|
||||||
|
|
||||||
@@ -310,6 +381,9 @@ class GridRouter:
|
|||||||
self._via_edge_block: set[Cell] = set()
|
self._via_edge_block: set[Cell] = set()
|
||||||
# wire keepouts as boxes, to check a pin stub the way the exact engine will
|
# wire keepouts as boxes, to check a pin stub the way the exact engine will
|
||||||
self._keepout_boxes: dict[int, list[tuple[IntBox, bool]]] = {}
|
self._keepout_boxes: dict[int, list[tuple[IntBox, bool]]] = {}
|
||||||
|
# via keepouts as boxes, and other copper a via in a pad must clear
|
||||||
|
self._via_keepout_boxes: list[tuple[IntBox, bool]] = []
|
||||||
|
self._static_copper: list[tuple[IntBox, int]] | None = None
|
||||||
# pin end nodes no wire can reach without entering a keepout
|
# pin end nodes no wire can reach without entering a keepout
|
||||||
self._via_only: set[Node] = set()
|
self._via_only: set[Node] = set()
|
||||||
if outline is not None:
|
if outline is not None:
|
||||||
@@ -359,6 +433,18 @@ class GridRouter:
|
|||||||
self._keepout.add((*cell, item.layer))
|
self._keepout.add((*cell, item.layer))
|
||||||
if item.blocks_vias:
|
if item.blocks_vias:
|
||||||
self._via_keepout.add((*cell, item.layer))
|
self._via_keepout.add((*cell, item.layer))
|
||||||
|
if item.blocks_vias:
|
||||||
|
self._via_keepout_boxes.append((box, item.clearance))
|
||||||
|
|
||||||
|
def _rasterize_fixed_copper(self) -> None:
|
||||||
|
"""Tracks and vias already on the board: copper of their net, which
|
||||||
|
other nets keep the same distance from as from a pad."""
|
||||||
|
margin = self.clearance + self.half_width
|
||||||
|
for net, layers, box in self.board.get_fixed_copper():
|
||||||
|
on = [layer for layer in layers if layer in self.layers]
|
||||||
|
for cell in self._cells_in_box(box, margin):
|
||||||
|
for layer in on:
|
||||||
|
self._pad_block.setdefault((*cell, layer), set()).add(net)
|
||||||
|
|
||||||
# --- occupancy cost -----------------------------------------------------
|
# --- occupancy cost -----------------------------------------------------
|
||||||
|
|
||||||
@@ -370,6 +456,30 @@ class GridRouter:
|
|||||||
allow_ripup: bool,
|
allow_ripup: bool,
|
||||||
conns: list[_Connection],
|
conns: list[_Connection],
|
||||||
wire_keepout: bool = True,
|
wire_keepout: bool = True,
|
||||||
|
) -> float | None:
|
||||||
|
""":meth:`_enter_cost_base`, and for a trace wider than the default
|
||||||
|
the same for every cell its extra width reaches (the worst of them)."""
|
||||||
|
cost = self._enter_cost_base(cell, layer, net_no, allow_ripup, conns, wire_keepout)
|
||||||
|
if cost is None or not self._spread:
|
||||||
|
return cost
|
||||||
|
for dx, dy in self._spread:
|
||||||
|
c = (cell[0] + dx, cell[1] + dy)
|
||||||
|
if not (0 <= c[0] < self.cols and 0 <= c[1] < self.rows):
|
||||||
|
return None
|
||||||
|
more = self._enter_cost_base(c, layer, net_no, allow_ripup, conns, wire_keepout)
|
||||||
|
if more is None:
|
||||||
|
return None
|
||||||
|
cost = max(cost, more)
|
||||||
|
return cost
|
||||||
|
|
||||||
|
def _enter_cost_base(
|
||||||
|
self,
|
||||||
|
cell: Cell,
|
||||||
|
layer: int,
|
||||||
|
net_no: int,
|
||||||
|
allow_ripup: bool,
|
||||||
|
conns: list[_Connection],
|
||||||
|
wire_keepout: bool = True,
|
||||||
) -> float | None:
|
) -> float | None:
|
||||||
"""Cost to enter ``(cell, layer)`` for ``net_no``; ``None`` if blocked.
|
"""Cost to enter ``(cell, layer)`` for ``net_no``; ``None`` if blocked.
|
||||||
|
|
||||||
@@ -424,14 +534,101 @@ class GridRouter:
|
|||||||
for layer in self.layers:
|
for layer in self.layers:
|
||||||
if (*c, layer) in self._via_keepout:
|
if (*c, layer) in self._via_keepout:
|
||||||
return False
|
return False
|
||||||
if self._enter_cost(c, layer, net_no, False, conns, wire_keepout=False) != 0.0:
|
if self._enter_cost_base(c, layer, net_no, False, conns, wire_keepout=False) != 0.0:
|
||||||
return False
|
return False
|
||||||
return True
|
return self._holes_clear(cell, net_no)
|
||||||
|
|
||||||
|
def _near_path_via(self, node: Node, cell: Cell, came_from: dict) -> bool:
|
||||||
|
"""A layer change earlier on the route that reaches ``node`` sits
|
||||||
|
within hole spacing of ``cell`` (and is not the same through via).
|
||||||
|
Committed vias are checked elsewhere; a route's own are not yet
|
||||||
|
committed while it is searched. Looks back far enough to cover the
|
||||||
|
hole spacing twice over, not along the whole route."""
|
||||||
|
limit = 4 * (math.ceil(self._hole_need / self.step) + 1)
|
||||||
|
need = self._hole_need / self.step
|
||||||
|
steps = 0
|
||||||
|
while node in came_from and steps < limit:
|
||||||
|
prev = came_from[node]
|
||||||
|
changes_layer = prev[:2] == node[:2] and prev[2] != node[2]
|
||||||
|
if changes_layer and node[:2] != cell and (
|
||||||
|
math.hypot(node[0] - cell[0], node[1] - cell[1]) < need
|
||||||
|
):
|
||||||
|
return True
|
||||||
|
node = prev
|
||||||
|
steps += 1
|
||||||
|
return False
|
||||||
|
|
||||||
|
def _via_nets_at(self, cell: Cell) -> set[int]:
|
||||||
|
nets = {net for net, n in self._via_nets.get(cell, {}).items() if n > 0}
|
||||||
|
fixed = self._fixed_vias.get(cell)
|
||||||
|
if fixed is not None:
|
||||||
|
nets.add(fixed)
|
||||||
|
return nets
|
||||||
|
|
||||||
|
def _holes_clear(self, cell: Cell, net_no: int) -> bool:
|
||||||
|
"""No via centre within hole-to-hole reach, but an own-net one here,
|
||||||
|
and no through-hole pad's hole within reach at all."""
|
||||||
|
if cell in self._tht_block:
|
||||||
|
return False
|
||||||
|
if self._fixed_holes:
|
||||||
|
here = self._cell_center(cell)
|
||||||
|
for loc, reach in self._fixed_holes:
|
||||||
|
d = math.hypot(loc.x - here.x, loc.y - here.y)
|
||||||
|
if d < reach and d > self.step: # beyond its own cell: too close
|
||||||
|
return False
|
||||||
|
if self._via_nets_at(cell) - {net_no}:
|
||||||
|
return False
|
||||||
|
cx, cy = cell
|
||||||
|
return not any(self._via_nets_at((cx + dx, cy + dy)) for dx, dy in self._hole_offsets)
|
||||||
|
|
||||||
# --- A* search ----------------------------------------------------------
|
# --- A* search ----------------------------------------------------------
|
||||||
|
|
||||||
|
def _conn_half(self, conn: _Connection) -> int:
|
||||||
|
"""The half width a connection is routed at: its class's, unless it
|
||||||
|
has fallen back to the default."""
|
||||||
|
return self.half_width if conn.narrow else self._net_half.get(conn.net_no, self.half_width)
|
||||||
|
|
||||||
|
def _spread_for(self, half: int) -> list[tuple[int, int]]:
|
||||||
|
"""Cells a trace of ``half`` also needs free: those whose centre is
|
||||||
|
within its extra half width (plus half a cell, for the grid)."""
|
||||||
|
extra = half - self.half_width
|
||||||
|
if extra <= 0:
|
||||||
|
return []
|
||||||
|
reach = math.ceil(extra / self.step) + 1
|
||||||
|
limit = extra + self.step / 2
|
||||||
|
return [
|
||||||
|
(dx, dy)
|
||||||
|
for dx in range(-reach, reach + 1)
|
||||||
|
for dy in range(-reach, reach + 1)
|
||||||
|
if (dx or dy) and math.hypot(dx, dy) * self.step <= limit
|
||||||
|
]
|
||||||
|
|
||||||
|
def _halo_for(self, half: int) -> list[tuple[int, int]]:
|
||||||
|
"""Cells a committed trace of ``half`` claims from default-width traces."""
|
||||||
|
offsets = self._halo_by_half.get(half)
|
||||||
|
if offsets is None:
|
||||||
|
need = half + self.clearance + self.half_width
|
||||||
|
reach = math.ceil(need / self.step)
|
||||||
|
offsets = self._halo_by_half[half] = [
|
||||||
|
(dx, dy)
|
||||||
|
for dx in range(-reach, reach + 1)
|
||||||
|
for dy in range(-reach, reach + 1)
|
||||||
|
if (dx or dy) and math.hypot(dx, dy) * self.step < need
|
||||||
|
]
|
||||||
|
return offsets
|
||||||
|
|
||||||
def _search(
|
def _search(
|
||||||
self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
|
self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
|
||||||
|
) -> list[Node] | None:
|
||||||
|
half = self._conn_half(conn)
|
||||||
|
self._cur_half, self._spread = half, self._spread_for(half)
|
||||||
|
try:
|
||||||
|
return self._search_at_width(conn, allow_ripup, conns)
|
||||||
|
finally:
|
||||||
|
self._cur_half, self._spread = self.half_width, []
|
||||||
|
|
||||||
|
def _search_at_width(
|
||||||
|
self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
|
||||||
) -> list[Node] | None:
|
) -> list[Node] | None:
|
||||||
goal_cell = self._group_target(conn.b_group)
|
goal_cell = self._group_target(conn.b_group)
|
||||||
if not conn.b_group[0] and any(z.layer in self._power_layers for z in conn.b_group[1]):
|
if not conn.b_group[0] and any(z.layer in self._power_layers for z in conn.b_group[1]):
|
||||||
@@ -441,7 +638,14 @@ class GridRouter:
|
|||||||
goals = self._group_ends(conn.b_group, conn.net_no, conns)
|
goals = self._group_ends(conn.b_group, conn.net_no, conns)
|
||||||
if not starts or not goals:
|
if not starts or not goals:
|
||||||
return None
|
return None
|
||||||
common = sorted(set(starts) & set(goals))
|
# A start that is already an end joins at once, except that ending on
|
||||||
|
# a plane there needs a via: one that cannot be placed (a via keepout,
|
||||||
|
# another net's pad) is no end, and the search goes on from there.
|
||||||
|
common = [
|
||||||
|
n for n in sorted(set(starts) & set(goals))
|
||||||
|
if not isinstance(goals[n], ConductionArea)
|
||||||
|
or self._via_placeable((n[0], n[1]), conn.net_no, conns)
|
||||||
|
]
|
||||||
if common:
|
if common:
|
||||||
conn.a_end, conn.b_end = starts[common[0]], goals[common[0]]
|
conn.a_end, conn.b_end = starts[common[0]], goals[common[0]]
|
||||||
return [common[0]]
|
return [common[0]]
|
||||||
@@ -451,10 +655,11 @@ class GridRouter:
|
|||||||
g_score: dict[Node, float] = {}
|
g_score: dict[Node, float] = {}
|
||||||
came_from: dict[Node, Node] = {}
|
came_from: dict[Node, Node] = {}
|
||||||
# a stub costs its length, so the nearest cell wins unless it is blocked
|
# a stub costs its length, so the nearest cell wins unless it is blocked
|
||||||
goal_stub = {n: self._stub_cost(p, n) for n, p in goals.items() if p is not None}
|
# a pin end costs its stub; a zone or plane end is entered normally
|
||||||
|
goal_stub = {n: self._stub_cost(p, n) for n, p in goals.items() if isinstance(p, Pin)}
|
||||||
for s in sorted(starts):
|
for s in sorted(starts):
|
||||||
pin = starts[s]
|
pin = starts[s]
|
||||||
g_score[s] = self._stub_cost(pin, s) if pin is not None else 0.0
|
g_score[s] = self._stub_cost(pin, s) if isinstance(pin, Pin) else 0.0
|
||||||
heapq.heappush(open_heap, (g_score[s] + self._h(s, goal_cell), s))
|
heapq.heappush(open_heap, (g_score[s] + self._h(s, goal_cell), s))
|
||||||
|
|
||||||
# Via footprints are checked lazily: a layer change goes on the heap as
|
# Via footprints are checked lazily: a layer change goes on the heap as
|
||||||
@@ -473,6 +678,14 @@ class GridRouter:
|
|||||||
ok = via_ok.get(cell)
|
ok = via_ok.get(cell)
|
||||||
if ok is None:
|
if ok is None:
|
||||||
ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
|
ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
|
||||||
|
# a via leaving or reaching a walled-in pin goes in its pad
|
||||||
|
# (see _commit), so it has to fit there exactly
|
||||||
|
for node, ends in ((source, starts), (target, goals)):
|
||||||
|
pin = ends.get(node)
|
||||||
|
if ok and isinstance(pin, Pin) and self._walled(node):
|
||||||
|
ok = self._via_fits_at(pin.location, net_no)
|
||||||
|
if ok and self._near_path_via(source, cell, came_from):
|
||||||
|
ok = False # too close to a via earlier on this same route
|
||||||
if ok:
|
if ok:
|
||||||
self._relax(source, target, g_via, goal_cell, g_score, came_from, open_heap)
|
self._relax(source, target, g_via, goal_cell, g_score, came_from, open_heap)
|
||||||
continue
|
continue
|
||||||
@@ -484,6 +697,8 @@ class GridRouter:
|
|||||||
ok = via_ok.get(cell)
|
ok = via_ok.get(cell)
|
||||||
if ok is None:
|
if ok is None:
|
||||||
ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
|
ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
|
||||||
|
if ok and self._near_path_via(current, cell, came_from):
|
||||||
|
ok = False
|
||||||
else:
|
else:
|
||||||
ok = True
|
ok = True
|
||||||
if ok:
|
if ok:
|
||||||
@@ -536,12 +751,51 @@ class GridRouter:
|
|||||||
# copper too, or a stub ends up closer than clearance to a trace in the
|
# copper too, or a stub ends up closer than clearance to a trace in the
|
||||||
# cell beside it.
|
# cell beside it.
|
||||||
|
|
||||||
def _stub_cells(self, pin_location: IntPoint, cell: Cell) -> list[Cell]:
|
def _walled(self, node: Node) -> bool:
|
||||||
|
"""A pin end no wire may leave or reach: only a via in its pad will do."""
|
||||||
|
return node in self._keepout or node in self._via_only
|
||||||
|
|
||||||
|
def _via_fits_at(self, point: IntPoint, net_no: int) -> bool:
|
||||||
|
"""A via centred exactly on ``point`` clears every via keepout and all
|
||||||
|
other nets' pads and fixed copper (what a via in a pad must meet)."""
|
||||||
|
via = IntBox(point.x - self.via_half, point.y - self.via_half,
|
||||||
|
point.x + self.via_half, point.y + self.via_half)
|
||||||
|
grown = via.offset(self.clearance)
|
||||||
|
for box, needs in self._via_keepout_boxes:
|
||||||
|
if box.overlaps(grown if needs else via):
|
||||||
|
return False
|
||||||
|
if self._static_copper is None:
|
||||||
|
copper = [
|
||||||
|
(p.shape.bounding_box(), p.net_nos[0] if p.net_nos else -1)
|
||||||
|
for p in self.board.get_pins()
|
||||||
|
if p.shape is not None and any(layer in self.layers for layer in p.layers)
|
||||||
|
]
|
||||||
|
copper += [(box, net) for net, _, box in self.board.get_fixed_copper()]
|
||||||
|
self._static_copper = copper
|
||||||
|
if any(net != net_no and box.overlaps(grown) for box, net in self._static_copper):
|
||||||
|
return False
|
||||||
|
return self._hole_clear_at(point)
|
||||||
|
|
||||||
|
def _hole_clear_at(self, point: IntPoint) -> bool:
|
||||||
|
"""Hole spacing measured exactly from ``point`` to every via and
|
||||||
|
through-hole pad (a via moved into a pad is not on its cell's centre)."""
|
||||||
|
need = self._hole_need
|
||||||
|
if self._via_centres is None: # rebuilt only after vias change
|
||||||
|
self._via_centres = [loc for _net, loc in self._fixed_via_points] + [
|
||||||
|
self._cell_center(c) for c, count in self._via_nets.items() if any(count.values())
|
||||||
|
]
|
||||||
|
if any(math.hypot(c.x - point.x, c.y - point.y) < need for c in self._via_centres):
|
||||||
|
return False
|
||||||
|
return not any(
|
||||||
|
math.hypot(loc.x - point.x, loc.y - point.y) < reach for loc, reach in self._tht_holes
|
||||||
|
)
|
||||||
|
|
||||||
|
def _stub_cells(self, pin_location: IntPoint, cell: Cell, half: int | None = None) -> list[Cell]:
|
||||||
"""Cells where another net's trace would come too close to the stub."""
|
"""Cells where another net's trace would come too close to the stub."""
|
||||||
from freeroute.board.outline import _point_segment
|
from freeroute.board.outline import _point_segment
|
||||||
|
|
||||||
end = self._cell_center(cell)
|
end = self._cell_center(cell)
|
||||||
reach = 2 * self.half_width + self.clearance
|
reach = (half or self._cur_half) + self.half_width + self.clearance
|
||||||
box = IntBox(
|
box = IntBox(
|
||||||
min(pin_location.x, end.x), min(pin_location.y, end.y),
|
min(pin_location.x, end.x), min(pin_location.y, end.y),
|
||||||
max(pin_location.x, end.x), max(pin_location.y, end.y),
|
max(pin_location.x, end.x), max(pin_location.y, end.y),
|
||||||
@@ -563,12 +817,12 @@ class GridRouter:
|
|||||||
|
|
||||||
end = self._cell_center(cell)
|
end = self._cell_center(cell)
|
||||||
if end != pin.location:
|
if end != pin.location:
|
||||||
for tile in PolylineShape(Polyline([pin.location, end]), self.half_width).tiles():
|
for tile in PolylineShape(Polyline([pin.location, end]), self._cur_half).tiles():
|
||||||
grown = tile.offset(self.clearance)
|
grown = tile.offset(self.clearance)
|
||||||
if any(k.overlaps(grown if needs else tile) for k, needs in keepouts):
|
if any(k.overlaps(grown if needs else tile) for k, needs in keepouts):
|
||||||
return False
|
return False
|
||||||
# the track's round end at the pin, for a rule area
|
# the track's round end at the pin, for a rule area
|
||||||
cap = corner_box(pin.location, self.half_width)
|
cap = corner_box(pin.location, self._cur_half)
|
||||||
if any(not needs and k.overlaps(cap) for k, needs in keepouts):
|
if any(not needs and k.overlaps(cap) for k, needs in keepouts):
|
||||||
return False
|
return False
|
||||||
if keepouts_only:
|
if keepouts_only:
|
||||||
@@ -807,11 +1061,18 @@ class GridRouter:
|
|||||||
via_cells.append((path[-1][0], path[-1][1]))
|
via_cells.append((path[-1][0], path[-1][1]))
|
||||||
conn.trace_cells = [(cell, layer) for layer, cells in wire_segs for cell in cells]
|
conn.trace_cells = [(cell, layer) for layer, cells in wire_segs for cell in cells]
|
||||||
conn.via_cells = list(via_cells)
|
conn.via_cells = list(via_cells)
|
||||||
|
for cell in conn.via_cells:
|
||||||
|
count = self._via_nets.setdefault(cell, {})
|
||||||
|
count[conn.net_no] = count.get(conn.net_no, 0) + 1
|
||||||
|
if conn.via_cells:
|
||||||
|
self._via_centres = None
|
||||||
for cell, layer in conn.trace_cells:
|
for cell, layer in conn.trace_cells:
|
||||||
self._cell_owner[(*cell, layer)] = conn.index
|
self._cell_owner[(*cell, layer)] = conn.index
|
||||||
|
conn.half = half = self._conn_half(conn)
|
||||||
|
halo = self._halo_for(half)
|
||||||
conn.halo_nodes = []
|
conn.halo_nodes = []
|
||||||
for (cx, cy), layer in conn.trace_cells:
|
for (cx, cy), layer in conn.trace_cells:
|
||||||
for dx, dy in self._halo_offsets:
|
for dx, dy in halo:
|
||||||
x, y = cx + dx, cy + dy
|
x, y = cx + dx, cy + dy
|
||||||
if 0 <= x < self.cols and 0 <= y < self.rows:
|
if 0 <= x < self.cols and 0 <= y < self.rows:
|
||||||
node = (x, y, layer)
|
node = (x, y, layer)
|
||||||
@@ -828,7 +1089,7 @@ class GridRouter:
|
|||||||
if not isinstance(pin, Pin):
|
if not isinstance(pin, Pin):
|
||||||
continue # ended on a zone or a plane: no stub
|
continue # ended on a zone or a plane: no stub
|
||||||
cell = cells[at]
|
cell = cells[at]
|
||||||
for c in self._stub_cells(pin.location, cell):
|
for c in self._stub_cells(pin.location, cell, half):
|
||||||
node = (*c, layer)
|
node = (*c, layer)
|
||||||
if node not in self._cell_owner:
|
if node not in self._cell_owner:
|
||||||
self._cell_owner[node] = conn.index
|
self._cell_owner[node] = conn.index
|
||||||
@@ -879,6 +1140,12 @@ class GridRouter:
|
|||||||
del self._halo[node]
|
del self._halo[node]
|
||||||
conn.halo_nodes = []
|
conn.halo_nodes = []
|
||||||
conn.trace_cells = []
|
conn.trace_cells = []
|
||||||
|
for cell in conn.via_cells:
|
||||||
|
count = self._via_nets.get(cell)
|
||||||
|
if count and count.get(conn.net_no):
|
||||||
|
count[conn.net_no] -= 1
|
||||||
|
if conn.via_cells:
|
||||||
|
self._via_centres = None
|
||||||
conn.via_cells = []
|
conn.via_cells = []
|
||||||
conn.wires = []
|
conn.wires = []
|
||||||
conn.vias = []
|
conn.vias = []
|
||||||
@@ -959,6 +1226,7 @@ class GridRouter:
|
|||||||
best_count = -1
|
best_count = -1
|
||||||
best_snapshot: list[tuple[int, list, list]] | None = None
|
best_snapshot: list[tuple[int, list, list]] | None = None
|
||||||
best_unrouted = len(conns)
|
best_unrouted = len(conns)
|
||||||
|
best_widths: tuple[dict[int, int], list] = ({}, [])
|
||||||
# conns[i].index == i is what rip-up relies on, so shuffle a view
|
# conns[i].index == i is what rip-up relies on, so shuffle a view
|
||||||
order = list(conns)
|
order = list(conns)
|
||||||
if self.seed is not None:
|
if self.seed is not None:
|
||||||
@@ -978,13 +1246,25 @@ class GridRouter:
|
|||||||
best_count = routed_count
|
best_count = routed_count
|
||||||
best_unrouted = len(conns) - routed_count
|
best_unrouted = len(conns) - routed_count
|
||||||
best_snapshot = self._snapshot(conns)
|
best_snapshot = self._snapshot(conns)
|
||||||
|
best_widths = self._net_widths(conns)
|
||||||
if routed_count == len(conns):
|
if routed_count == len(conns):
|
||||||
break
|
break
|
||||||
if not changed:
|
if not changed:
|
||||||
break
|
break
|
||||||
return self._result_from(best_snapshot or [], best_unrouted)
|
result = self._result_from(best_snapshot or [], best_unrouted)
|
||||||
|
result.net_half, result.narrowed = best_widths
|
||||||
|
return result
|
||||||
|
|
||||||
def _try_route(self, conn: _Connection, conns: list[_Connection]) -> bool:
|
def _try_route(self, conn: _Connection, conns: list[_Connection]) -> bool:
|
||||||
|
if self._route_once(conn, conns):
|
||||||
|
return True
|
||||||
|
if conn.narrow or conn.net_no not in self._net_half:
|
||||||
|
return False
|
||||||
|
# a wider class that does not fit: route it at the default width
|
||||||
|
conn.narrow = True
|
||||||
|
return self._route_once(conn, conns)
|
||||||
|
|
||||||
|
def _route_once(self, conn: _Connection, conns: list[_Connection]) -> bool:
|
||||||
path = self._search(conn, allow_ripup=False, conns=conns)
|
path = self._search(conn, allow_ripup=False, conns=conns)
|
||||||
if path is None:
|
if path is None:
|
||||||
if not self.rip_up:
|
if not self.rip_up:
|
||||||
@@ -1048,7 +1328,9 @@ class GridRouter:
|
|||||||
# deterministic: fewer-pin nets first, then by net number
|
# deterministic: fewer-pin nets first, then by net number
|
||||||
for net_no in sorted(nets, key=lambda n: (len(pins_by_net.get(n, [])), n)):
|
for net_no in sorted(nets, key=lambda n: (len(pins_by_net.get(n, [])), n)):
|
||||||
zones = zones_by_net.get(net_no, []) + planes_by_net.get(net_no, [])
|
zones = zones_by_net.get(net_no, []) + planes_by_net.get(net_no, [])
|
||||||
groups = _connected_groups(pins_by_net.get(net_no, []), zones, plane_ids)
|
groups = _connected_groups(
|
||||||
|
pins_by_net.get(net_no, []), zones, plane_ids, self._fixed_pieces(net_no)
|
||||||
|
)
|
||||||
hubs = [g for g in groups if any(id(z) in plane_ids for z in g[1])]
|
hubs = [g for g in groups if any(id(z) in plane_ids for z in g[1])]
|
||||||
if hubs:
|
if hubs:
|
||||||
# a plane net: every other group goes straight to the plane
|
# a plane net: every other group goes straight to the plane
|
||||||
@@ -1062,6 +1344,28 @@ class GridRouter:
|
|||||||
conns.append(conn)
|
conns.append(conn)
|
||||||
return conns
|
return conns
|
||||||
|
|
||||||
|
def _fixed_pieces(self, net_no: int) -> list[_FixedPiece]:
|
||||||
|
"""The net's tracks and vias already on the board, as connectivity."""
|
||||||
|
cache = getattr(self, "_fixed_cache", None)
|
||||||
|
if cache is None:
|
||||||
|
from freeroute.board.items import Trace
|
||||||
|
from freeroute.geometry.polyline import Polyline, PolylineShape, corner_box
|
||||||
|
|
||||||
|
cache = self._fixed_cache = {}
|
||||||
|
for item in self.board.get_items():
|
||||||
|
if not item.fixed or not item.net_nos:
|
||||||
|
continue
|
||||||
|
if isinstance(item, Via) and item.shape is not None:
|
||||||
|
piece = _FixedPiece(item.layers, [item.shape.bounding_box()], via=item)
|
||||||
|
elif isinstance(item, Trace) and not item.is_empty():
|
||||||
|
boxes = list(PolylineShape(Polyline(item.corners), item.half_width).tiles())
|
||||||
|
boxes += [corner_box(e, item.half_width) for e in (item.corners[0], item.corners[-1])]
|
||||||
|
piece = _FixedPiece([item.layer], boxes)
|
||||||
|
else:
|
||||||
|
continue
|
||||||
|
cache.setdefault(item.net_nos[0], []).append(piece)
|
||||||
|
return cache.get(net_no, [])
|
||||||
|
|
||||||
def _pins_by_net(self) -> dict[int, list[Pin]]:
|
def _pins_by_net(self) -> dict[int, list[Pin]]:
|
||||||
by_net: dict[int, list[Pin]] = {}
|
by_net: dict[int, list[Pin]] = {}
|
||||||
for pin in self.board.get_pins():
|
for pin in self.board.get_pins():
|
||||||
@@ -1071,6 +1375,21 @@ class GridRouter:
|
|||||||
by_net.setdefault(net_no, []).append(pin)
|
by_net.setdefault(net_no, []).append(pin)
|
||||||
return by_net
|
return by_net
|
||||||
|
|
||||||
|
def _net_widths(self, conns: list[_Connection]) -> tuple[dict[int, int], list]:
|
||||||
|
"""Half width of each wider-class net whose routed connections all went
|
||||||
|
in at it (a net is written at one width), and the connections that
|
||||||
|
had to fall back to the default."""
|
||||||
|
halves: dict[int, int] = {}
|
||||||
|
narrowed = []
|
||||||
|
for c in conns:
|
||||||
|
if not c.routed:
|
||||||
|
continue
|
||||||
|
halves[c.net_no] = min(halves.get(c.net_no, c.half), c.half)
|
||||||
|
if c.narrow:
|
||||||
|
narrowed.append((c.net_no, *_ends_of(c)))
|
||||||
|
wide = {net: half for net, half in halves.items() if half > self.half_width}
|
||||||
|
return wide, narrowed
|
||||||
|
|
||||||
def _snapshot(self, conns: list[_Connection]) -> list[tuple]:
|
def _snapshot(self, conns: list[_Connection]) -> list[tuple]:
|
||||||
return [
|
return [
|
||||||
(c.net_no, [(layer, list(pts)) for layer, pts in c.wires], list(c.vias),
|
(c.net_no, [(layer, list(pts)) for layer, pts in c.wires], list(c.vias),
|
||||||
@@ -1081,11 +1400,16 @@ class GridRouter:
|
|||||||
|
|
||||||
def _result_from(self, snapshot, unrouted: int) -> RouteResult:
|
def _result_from(self, snapshot, unrouted: int) -> RouteResult:
|
||||||
result = RouteResult(self.half_width)
|
result = RouteResult(self.half_width)
|
||||||
|
written: set[tuple[int, IntPoint]] = set()
|
||||||
result.unrouted = unrouted
|
result.unrouted = unrouted
|
||||||
for net_no, wires, vias, ends in snapshot:
|
for net_no, wires, vias, ends in snapshot:
|
||||||
for layer, points in wires:
|
for layer, points in wires:
|
||||||
result.add_wire(net_no, layer, points)
|
result.add_wire(net_no, layer, points)
|
||||||
for location in vias:
|
for location in vias:
|
||||||
|
spot = (net_no, location)
|
||||||
|
if spot in written or spot in self._fixed_via_points:
|
||||||
|
continue # a via reused by another connection, or already on the board
|
||||||
|
written.add(spot)
|
||||||
result.add_via(net_no, location)
|
result.add_via(net_no, location)
|
||||||
result.connections.append((net_no, wires, vias))
|
result.connections.append((net_no, wires, vias))
|
||||||
result.connection_ends.append(ends)
|
result.connection_ends.append(ends)
|
||||||
@@ -1136,13 +1460,49 @@ def _pin_touches_zone(pin: Pin, zone, plane: bool = False) -> bool:
|
|||||||
return any(zone.polygon.contains(c) for c in corners)
|
return any(zone.polygon.contains(c) for c in corners)
|
||||||
|
|
||||||
|
|
||||||
|
def _touches(a: IntBox, b: IntBox) -> bool:
|
||||||
|
return not (a.ur.x < b.ll.x or b.ur.x < a.ll.x or a.ur.y < b.ll.y or b.ur.y < a.ll.y)
|
||||||
|
|
||||||
|
|
||||||
|
def _fixed_joins_zone(piece, zone, plane: bool) -> bool:
|
||||||
|
"""A through via inside a plane joins it; copper inside a zone on its
|
||||||
|
own layer joins that zone."""
|
||||||
|
if zone.polygon is None:
|
||||||
|
return False
|
||||||
|
if piece.via is not None:
|
||||||
|
if plane or zone.layer in piece.layers:
|
||||||
|
return zone.polygon.contains(piece.via.location)
|
||||||
|
return False
|
||||||
|
return zone.layer in piece.layers and any(
|
||||||
|
zone.polygon.contains(IntPoint((b.ll.x + b.ur.x) // 2, (b.ll.y + b.ur.y) // 2))
|
||||||
|
for b in piece.boxes
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
class _FixedPiece:
|
||||||
|
"""One track or via already on the board, as connectivity."""
|
||||||
|
|
||||||
|
__slots__ = ("layers", "boxes", "via")
|
||||||
|
|
||||||
|
def __init__(self, layers, boxes, via=None) -> None:
|
||||||
|
self.layers = frozenset(layers)
|
||||||
|
self.boxes = boxes
|
||||||
|
self.via = via # the Via item, for a via
|
||||||
|
|
||||||
|
|
||||||
def _connected_groups(
|
def _connected_groups(
|
||||||
pins: list[Pin], zones: list, planes: frozenset = frozenset()
|
pins: list[Pin], zones: list, planes: frozenset = frozenset(), fixed: list | None = None
|
||||||
) -> list[tuple[list[Pin], list]]:
|
) -> list[tuple[list[Pin], list]]:
|
||||||
"""Pins and zones of one net that copper already joins: a pad in a zone
|
"""Pins and zones of one net that copper already joins: a pad in a zone
|
||||||
is connected to it, and two zones sharing a pad are one. Only the groups
|
is connected to it, two zones sharing a pad are one, and copper already
|
||||||
need routing between them. Pin groups come first, in pin order."""
|
on the board (tracks and vias, ``fixed``) joins whatever it touches. Only
|
||||||
parent = list(range(len(pins) + len(zones)))
|
the groups need routing between them. Pin groups come first, in pin
|
||||||
|
order. A group's fixed vias join its pins as extra route ends, so a
|
||||||
|
fanned-out pin is routed from its via; copper that touches no pin and no
|
||||||
|
zone adds nothing to route."""
|
||||||
|
fixed = fixed or []
|
||||||
|
n_pins, n_zones = len(pins), len(zones)
|
||||||
|
parent = list(range(n_pins + n_zones + len(fixed)))
|
||||||
|
|
||||||
def find(i: int) -> int:
|
def find(i: int) -> int:
|
||||||
while parent[i] != i:
|
while parent[i] != i:
|
||||||
@@ -1154,6 +1514,24 @@ def _connected_groups(
|
|||||||
for i, pin in enumerate(pins):
|
for i, pin in enumerate(pins):
|
||||||
if _pin_touches_zone(pin, zone, id(zone) in planes):
|
if _pin_touches_zone(pin, zone, id(zone) in planes):
|
||||||
parent[find(i)] = find(len(pins) + j)
|
parent[find(i)] = find(len(pins) + j)
|
||||||
|
base = n_pins + n_zones
|
||||||
|
for k, piece in enumerate(fixed):
|
||||||
|
me = base + k
|
||||||
|
for i, pin in enumerate(pins):
|
||||||
|
if pin.shape is None or not piece.layers & set(pin.layers):
|
||||||
|
continue
|
||||||
|
pad = pin.shape.bounding_box()
|
||||||
|
if any(_touches(pad, b) for b in piece.boxes):
|
||||||
|
parent[find(i)] = find(me)
|
||||||
|
for j, zone in enumerate(zones):
|
||||||
|
if _fixed_joins_zone(piece, zone, id(zone) in planes):
|
||||||
|
parent[find(n_pins + j)] = find(me)
|
||||||
|
for k2 in range(k):
|
||||||
|
other = fixed[k2]
|
||||||
|
if piece.layers & other.layers and any(
|
||||||
|
_touches(a, b) for a in piece.boxes for b in other.boxes
|
||||||
|
):
|
||||||
|
parent[find(base + k2)] = find(me)
|
||||||
groups: dict[int, tuple[list[Pin], list]] = {}
|
groups: dict[int, tuple[list[Pin], list]] = {}
|
||||||
order: list[int] = []
|
order: list[int] = []
|
||||||
for i, pin in enumerate(pins):
|
for i, pin in enumerate(pins):
|
||||||
@@ -1168,9 +1546,22 @@ def _connected_groups(
|
|||||||
groups[root] = ([], [])
|
groups[root] = ([], [])
|
||||||
order.append(root)
|
order.append(root)
|
||||||
groups[root][1].append(zone)
|
groups[root][1].append(zone)
|
||||||
|
for k, piece in enumerate(fixed):
|
||||||
|
root = find(base + k)
|
||||||
|
if piece.via is not None and root in groups:
|
||||||
|
groups[root][0].append(_via_end(piece.via))
|
||||||
return [groups[r] for r in order]
|
return [groups[r] for r in order]
|
||||||
|
|
||||||
|
|
||||||
|
def _via_end(via) -> Pin:
|
||||||
|
"""A fixed via as a place a route may start or end (not a pad to route)."""
|
||||||
|
return Pin(
|
||||||
|
net_nos=list(via.net_nos), fixed=True, name="via", component_ref="",
|
||||||
|
padstack_name=via.padstack_name, location=via.location,
|
||||||
|
layers=list(via.layers), shape=via.shape,
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
def _split_path(path: list[Node]) -> tuple[list[tuple[int, list[Cell]]], list[Cell]]:
|
def _split_path(path: list[Node]) -> tuple[list[tuple[int, list[Cell]]], list[Cell]]:
|
||||||
"""Split a node path into per-layer wire segments and via cells."""
|
"""Split a node path into per-layer wire segments and via cells."""
|
||||||
wires: list[tuple[int, list[Cell]]] = []
|
wires: list[tuple[int, list[Cell]]] = []
|
||||||
@@ -1231,6 +1622,9 @@ def route_board(
|
|||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
|
net_widths: dict[int, int] | None = None,
|
||||||
|
via_drill: int | None = None,
|
||||||
|
hole_to_hole: int = 0,
|
||||||
) -> RouteResult:
|
) -> RouteResult:
|
||||||
"""Convenience wrapper: build a :class:`GridRouter` and route the board."""
|
"""Convenience wrapper: build a :class:`GridRouter` and route the board."""
|
||||||
router = GridRouter(
|
router = GridRouter(
|
||||||
@@ -1250,5 +1644,8 @@ def route_board(
|
|||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
|
net_widths=net_widths,
|
||||||
|
via_drill=via_drill,
|
||||||
|
hole_to_hole=hole_to_hole,
|
||||||
)
|
)
|
||||||
return router.route()
|
return router.route()
|
||||||
|
|||||||
@@ -12,6 +12,8 @@ to DSN units (dividing by the resolution) for the SES ``(wire (path ...))`` and
|
|||||||
|
|
||||||
from __future__ import annotations
|
from __future__ import annotations
|
||||||
|
|
||||||
|
import re
|
||||||
|
|
||||||
from freeroute.board import build_board
|
from freeroute.board import build_board
|
||||||
from freeroute.dsn import DsnBoard, parse_dsn
|
from freeroute.dsn import DsnBoard, parse_dsn
|
||||||
from freeroute.ses import RoutedVia, RoutedWire, RoutingResult, write_ses
|
from freeroute.ses import RoutedVia, RoutedWire, RoutingResult, write_ses
|
||||||
@@ -34,6 +36,25 @@ def _rule_width_dsn(dsn: DsnBoard) -> float:
|
|||||||
return rules[0].value if rules else _DEFAULT_WIDTH_DSN
|
return rules[0].value if rules else _DEFAULT_WIDTH_DSN
|
||||||
|
|
||||||
|
|
||||||
|
def _net_widths_board(dsn: DsnBoard, scale: int) -> dict[int, int]:
|
||||||
|
"""Track width of every net whose class asks for more than the default,
|
||||||
|
in board units, by net number (build_board numbers nets in DSN order)."""
|
||||||
|
default = _rule_width_dsn(dsn)
|
||||||
|
by_name: dict[str, float] = {}
|
||||||
|
for net_class in dsn.net_classes:
|
||||||
|
if not net_class.width_rules:
|
||||||
|
continue
|
||||||
|
width = net_class.width_rules[0].value
|
||||||
|
if width > default:
|
||||||
|
for name in net_class.net_names:
|
||||||
|
by_name[name] = max(by_name.get(name, 0.0), width)
|
||||||
|
return {
|
||||||
|
i + 1: round(by_name[net.name] * scale)
|
||||||
|
for i, net in enumerate(dsn.nets)
|
||||||
|
if net.name in by_name
|
||||||
|
}
|
||||||
|
|
||||||
|
|
||||||
def _rule_clearance_dsn(dsn: DsnBoard) -> float:
|
def _rule_clearance_dsn(dsn: DsnBoard) -> float:
|
||||||
for rule in dsn.structure_rules.clearance_rules:
|
for rule in dsn.structure_rules.clearance_rules:
|
||||||
if not rule.class_pairs: # the layer-wide default clearance
|
if not rule.class_pairs: # the layer-wide default clearance
|
||||||
@@ -53,6 +74,20 @@ def _mm_to_board(dsn: DsnBoard, scale: int, value_mm: float | None) -> int | Non
|
|||||||
return round(value_mm / unit_mm * scale)
|
return round(value_mm / unit_mm * scale)
|
||||||
|
|
||||||
|
|
||||||
|
def _via_drill_board(dsn: DsnBoard, scale: int) -> int | None:
|
||||||
|
"""The via's drill in board units, from KiCad's padstack name
|
||||||
|
(``Via[0-1]_600:300_um`` is a 600 um pad with a 300 um drill); None when
|
||||||
|
the name does not say, and the pad size stands in for it."""
|
||||||
|
match = re.search(r"_([\d.]+):([\d.]+)_um", _via_padstack(dsn))
|
||||||
|
if not match:
|
||||||
|
return None
|
||||||
|
return round(float(match.group(2)) * _dsn_units_per_um(dsn) * scale)
|
||||||
|
|
||||||
|
|
||||||
|
def _dsn_units_per_um(dsn: DsnBoard) -> float:
|
||||||
|
return {"um": 1.0, "mm": 0.001, "mil": 1 / 25.4, "inch": 1 / 25400}.get(dsn.unit, 1.0)
|
||||||
|
|
||||||
|
|
||||||
def _via_half_board(dsn: DsnBoard, scale: int) -> int | None:
|
def _via_half_board(dsn: DsnBoard, scale: int) -> int | None:
|
||||||
"""Half the via pad's size in board units, from the DSN's via padstack.
|
"""Half the via pad's size in board units, from the DSN's via padstack.
|
||||||
|
|
||||||
@@ -83,6 +118,7 @@ def route_dsn_board(
|
|||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
|
hole_to_hole_mm: float = 0.25,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
) -> tuple[RouteResult, int, list[str]]:
|
) -> tuple[RouteResult, int, list[str]]:
|
||||||
"""Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
|
"""Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
|
||||||
@@ -108,6 +144,9 @@ def route_dsn_board(
|
|||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
|
net_widths=_net_widths_board(dsn, scale),
|
||||||
|
via_drill=_via_drill_board(dsn, scale),
|
||||||
|
hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
|
||||||
)
|
)
|
||||||
return result, scale, [layer.name for layer in dsn.layers]
|
return result, scale, [layer.name for layer in dsn.layers]
|
||||||
|
|
||||||
@@ -122,6 +161,9 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
|
|||||||
result = RoutingResult()
|
result = RoutingResult()
|
||||||
for net_no, segments in route.wires.items():
|
for net_no, segments in route.wires.items():
|
||||||
name = numbers_to_names.get(net_no, str(net_no))
|
name = numbers_to_names.get(net_no, str(net_no))
|
||||||
|
# its class's width when every connection of the net went in at it
|
||||||
|
half = getattr(route, "net_half", {}).get(net_no)
|
||||||
|
net_width = 2 * half / scale if half else width_dsn
|
||||||
for layer_index, path in segments:
|
for layer_index, path in segments:
|
||||||
layer_name = layer_names[layer_index] if layer_index < len(layer_names) else "F.Cu"
|
layer_name = layer_names[layer_index] if layer_index < len(layer_names) else "F.Cu"
|
||||||
coords: list[float] = []
|
coords: list[float] = []
|
||||||
@@ -129,7 +171,7 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
|
|||||||
coords.append(point.x / scale)
|
coords.append(point.x / scale)
|
||||||
coords.append(point.y / scale)
|
coords.append(point.y / scale)
|
||||||
if len(coords) >= 4:
|
if len(coords) >= 4:
|
||||||
result.add_wire(name, RoutedWire(layer=layer_name, width=width_dsn, coords=coords))
|
result.add_wire(name, RoutedWire(layer=layer_name, width=net_width, coords=coords))
|
||||||
for net_no, locations in route.vias.items():
|
for net_no, locations in route.vias.items():
|
||||||
name = numbers_to_names.get(net_no, str(net_no))
|
name = numbers_to_names.get(net_no, str(net_no))
|
||||||
for loc in locations:
|
for loc in locations:
|
||||||
@@ -137,6 +179,9 @@ def _to_routing_result(route, dsn: DsnBoard, scale: int, layer_names: list[str])
|
|||||||
result.unrouted = [
|
result.unrouted = [
|
||||||
(numbers_to_names.get(n, str(n)), a, b, zone) for n, a, b, zone in getattr(route, "failed", [])
|
(numbers_to_names.get(n, str(n)), a, b, zone) for n, a, b, zone in getattr(route, "failed", [])
|
||||||
]
|
]
|
||||||
|
result.narrowed = [
|
||||||
|
(numbers_to_names.get(n, str(n)), a, b) for n, a, b in getattr(route, "narrowed", [])
|
||||||
|
]
|
||||||
return result
|
return result
|
||||||
|
|
||||||
|
|
||||||
@@ -151,6 +196,7 @@ def build_routing_result(
|
|||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
|
hole_to_hole_mm: float = 0.25,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
) -> RoutingResult:
|
) -> RoutingResult:
|
||||||
"""Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
|
"""Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
|
||||||
@@ -159,6 +205,7 @@ def build_routing_result(
|
|||||||
edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
|
edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
|
hole_to_hole_mm=hole_to_hole_mm,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
)
|
)
|
||||||
return _to_routing_result(route, dsn, scale, layer_names)
|
return _to_routing_result(route, dsn, scale, layer_names)
|
||||||
@@ -178,6 +225,7 @@ def route_dsn_board_exact(
|
|||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
|
hole_to_hole_mm: float = 0.25,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
) -> tuple[ExactRouteResult, int, list[str]]:
|
) -> tuple[ExactRouteResult, int, list[str]]:
|
||||||
"""Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
|
"""Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
|
||||||
@@ -207,6 +255,9 @@ def route_dsn_board_exact(
|
|||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
|
net_widths=_net_widths_board(dsn, scale),
|
||||||
|
via_drill=_via_drill_board(dsn, scale),
|
||||||
|
hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
|
||||||
)
|
)
|
||||||
return exact, scale, [layer.name for layer in dsn.layers]
|
return exact, scale, [layer.name for layer in dsn.layers]
|
||||||
|
|
||||||
@@ -225,6 +276,7 @@ def build_exact_routing_result(
|
|||||||
seed: int | None = None,
|
seed: int | None = None,
|
||||||
route_first: frozenset | None = None,
|
route_first: frozenset | None = None,
|
||||||
access_cost: float = 0.0,
|
access_cost: float = 0.0,
|
||||||
|
hole_to_hole_mm: float = 0.25,
|
||||||
rollback: bool = True,
|
rollback: bool = True,
|
||||||
) -> RoutingResult:
|
) -> RoutingResult:
|
||||||
"""Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
|
"""Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
|
||||||
@@ -241,6 +293,7 @@ def build_exact_routing_result(
|
|||||||
seed=seed,
|
seed=seed,
|
||||||
route_first=route_first,
|
route_first=route_first,
|
||||||
access_cost=access_cost,
|
access_cost=access_cost,
|
||||||
|
hole_to_hole_mm=hole_to_hole_mm,
|
||||||
rollback=rollback,
|
rollback=rollback,
|
||||||
)
|
)
|
||||||
return _to_routing_result(exact.result, dsn, scale, layer_names)
|
return _to_routing_result(exact.result, dsn, scale, layer_names)
|
||||||
|
|||||||
@@ -515,6 +515,10 @@ def route_board_rooms(
|
|||||||
pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
|
pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
|
||||||
if pin_layers:
|
if pin_layers:
|
||||||
tree.insert(TreeShape(next(owner), net, pin_layers, box))
|
tree.insert(TreeShape(next(owner), net, pin_layers, box))
|
||||||
|
for net, copper_layers, box in board.get_fixed_copper():
|
||||||
|
on = frozenset(layer for layer in copper_layers if layer in signal_layers)
|
||||||
|
if on and not box.is_empty():
|
||||||
|
tree.insert(TreeShape(next(owner), net, on, box))
|
||||||
for obstacle in board.get_obstacle_areas():
|
for obstacle in board.get_obstacle_areas():
|
||||||
if obstacle.layer not in signal_layers:
|
if obstacle.layer not in signal_layers:
|
||||||
continue
|
continue
|
||||||
|
|||||||
@@ -60,6 +60,9 @@ class RoutingResult:
|
|||||||
#: connections the router could not make: (net name, one end, other end,
|
#: connections the router could not make: (net name, one end, other end,
|
||||||
#: the zone both ends sit in or "") -- a zone's fill may join the latter
|
#: the zone both ends sit in or "") -- a zone's fill may join the latter
|
||||||
unrouted: list[tuple[str, str, str, str]] = field(default_factory=list)
|
unrouted: list[tuple[str, str, str, str]] = field(default_factory=list)
|
||||||
|
#: connections of a wider net class that only fitted at the default width
|
||||||
|
#: (net name, one end, other end); their net is written at the default
|
||||||
|
narrowed: list[tuple[str, str, str]] = field(default_factory=list)
|
||||||
|
|
||||||
def net(self, name: str, *, create: bool = False) -> RoutedNet | None:
|
def net(self, name: str, *, create: bool = False) -> RoutedNet | None:
|
||||||
"""Return the :class:`RoutedNet` with ``name`` (creating it if asked)."""
|
"""Return the :class:`RoutedNet` with ``name`` (creating it if asked)."""
|
||||||
|
|||||||
@@ -0,0 +1,108 @@
|
|||||||
|
"""Tracks and vias already on the board (the DSN's wiring) are fixed copper."""
|
||||||
|
|
||||||
|
from __future__ import annotations
|
||||||
|
|
||||||
|
from freeroute.board import build_board
|
||||||
|
from freeroute.dsn import parse_dsn
|
||||||
|
from freeroute.route.pipeline import route_dsn_board_exact
|
||||||
|
|
||||||
|
_DSN = """(pcb wired (parser) (resolution um 10) (unit um)
|
||||||
|
(structure
|
||||||
|
(layer F.Cu (type signal)) (layer B.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 30000 0 30000 -20000 0 -20000 0 0))
|
||||||
|
(via "Via[0-1]_600:300_um") (rule (width 250) (clearance 200)))
|
||||||
|
(placement (component S (place A1 5000 -10000 front 0) (place A2 25000 -10000 front 0)))
|
||||||
|
(library
|
||||||
|
(image S (pin smd 1 0 0))
|
||||||
|
(padstack smd (shape (rect F.Cu -400 -400 400 400)) (attach off))
|
||||||
|
(padstack "Via[0-1]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
|
||||||
|
(network (net SIG (pins A1-1 A2-1)) (net GND))
|
||||||
|
(wiring
|
||||||
|
(wire (path F.Cu 400 15000 0 15000 -20000) (net GND) (type route))
|
||||||
|
(via "Via[0-1]_600:300_um" 8000 -14000 (net GND) (type route))))"""
|
||||||
|
|
||||||
|
|
||||||
|
def test_wiring_is_read_with_its_nets():
|
||||||
|
dsn = parse_dsn(_DSN)
|
||||||
|
assert [(w.net, w.layer, w.width) for w in dsn.wires] == [("GND", "F.Cu", 400.0)]
|
||||||
|
assert [(v.net, v.x, v.y) for v in dsn.vias] == [("GND", 8000.0, -14000.0)]
|
||||||
|
|
||||||
|
|
||||||
|
def test_wiring_is_fixed_copper_and_not_a_connection_to_route():
|
||||||
|
board = build_board(parse_dsn(_DSN))
|
||||||
|
copper = board.get_fixed_copper()
|
||||||
|
gnd = next(n.net_number for n in board.nets if n.name == "GND")
|
||||||
|
assert copper and all(net == gnd for net, _, _ in copper)
|
||||||
|
assert not any(gnd in p.net_nos for p in board.get_pins())
|
||||||
|
|
||||||
|
|
||||||
|
def test_other_nets_route_around_a_fixed_track():
|
||||||
|
dsn = parse_dsn(_DSN)
|
||||||
|
exact, scale, names = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
|
||||||
|
assert sig in exact.result.routed_net_numbers
|
||||||
|
assert exact.drc_clean
|
||||||
|
wall = 15000 * scale
|
||||||
|
for layer, pts in exact.result.wires.get(sig, []):
|
||||||
|
if names[layer] != "F.Cu":
|
||||||
|
continue
|
||||||
|
for p, q in zip(pts, pts[1:], strict=False):
|
||||||
|
assert not (min(p.x, q.x) < wall < max(p.x, q.x)), "crossed the GND track on F.Cu"
|
||||||
|
|
||||||
|
|
||||||
|
# --- fixed wiring as connectivity ------------------------------------------
|
||||||
|
|
||||||
|
_FANOUT = """(pcb fanout (parser) (resolution um 10) (unit um)
|
||||||
|
(structure
|
||||||
|
(layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
|
||||||
|
(layer B.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 30000 0 30000 -20000 0 -20000 0 0))
|
||||||
|
(plane GND (polygon In1.Cu 0 500 -500 29500 -500 29500 -19500 500 -19500 500 -500))
|
||||||
|
(via "Via[0-3]_600:300_um") (rule (width 150) (clearance 150)))
|
||||||
|
(placement (component S (place G1 5000 -10000 front 0) (place A 10000 -10000 front 0)
|
||||||
|
(place B 25000 -11500 back 0)))
|
||||||
|
(library
|
||||||
|
(image S (pin smd 1 0 0))
|
||||||
|
(padstack smd (shape (rect F.Cu -300 -300 300 300)) (attach off))
|
||||||
|
(padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
|
||||||
|
(network (net GND (pins G1-1)) (net SIG (pins A-1 B-1)))
|
||||||
|
(wiring
|
||||||
|
(wire (path F.Cu 150 5000 -10000 5000 -11500) (net GND) (type route))
|
||||||
|
(via "Via[0-3]_600:300_um" 5000 -11500 (net GND) (type route))
|
||||||
|
(wire (path F.Cu 150 10000 -10000 10000 -11500) (net SIG) (type route))
|
||||||
|
(via "Via[0-3]_600:300_um" 10000 -11500 (net SIG) (type route))
|
||||||
|
(wire (path F.Cu 300 2000 -2000 8000 -2000) (net GND) (type route))))"""
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_pad_fanned_out_to_its_plane_needs_no_route():
|
||||||
|
dsn = parse_dsn(_FANOUT)
|
||||||
|
exact, _scale, _names = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
|
||||||
|
assert exact.result.failed == []
|
||||||
|
assert not exact.result.vias.get(gnd) and not exact.result.wires.get(gnd)
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_fanned_out_signal_is_routed_from_its_via():
|
||||||
|
# B is on the bottom face, level with A's fan-out via: starting from that
|
||||||
|
# via on B.Cu is the cheapest way, and needs no via of its own
|
||||||
|
dsn = parse_dsn(_FANOUT)
|
||||||
|
exact, scale, names = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
|
||||||
|
assert sig in exact.result.routed_net_numbers
|
||||||
|
assert not exact.result.vias.get(sig), "the fan-out via is already there"
|
||||||
|
assert {names[layer] for layer, _ in exact.result.wires[sig]} == {"B.Cu"}
|
||||||
|
|
||||||
|
|
||||||
|
def test_the_session_never_repeats_copper_already_on_the_board():
|
||||||
|
# the JAR writes the DSN's wiring back into its session, and an applier
|
||||||
|
# then adds it a second time on top of itself; freeroute writes only
|
||||||
|
# what it routed
|
||||||
|
from freeroute.route.pipeline import build_exact_routing_result
|
||||||
|
|
||||||
|
fixed_vias = {(5000.0, -11500.0), (10000.0, -11500.0)}
|
||||||
|
fixed_paths = {(5000.0, -10000.0, 5000.0, -11500.0), (10000.0, -10000.0, 10000.0, -11500.0),
|
||||||
|
(2000.0, -2000.0, 8000.0, -2000.0)}
|
||||||
|
result = build_exact_routing_result(parse_dsn(_FANOUT), resolution=2)
|
||||||
|
for net in result.nets:
|
||||||
|
assert not {(v.x, v.y) for v in net.vias} & fixed_vias
|
||||||
|
assert not {tuple(w.coords) for w in net.wires} & fixed_paths
|
||||||
@@ -0,0 +1,42 @@
|
|||||||
|
"""Net classes wider than the default are routed at their width where it fits."""
|
||||||
|
|
||||||
|
from __future__ import annotations
|
||||||
|
|
||||||
|
from freeroute.dsn import parse_dsn
|
||||||
|
from freeroute.route.pipeline import build_exact_routing_result
|
||||||
|
|
||||||
|
_BOARD = """(pcb widths (parser) (resolution um 10) (unit um)
|
||||||
|
(structure
|
||||||
|
(layer F.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 20000 0 20000 -10000 0 -10000 0 0))
|
||||||
|
{keepouts}
|
||||||
|
(rule (width 150) (clearance 150)))
|
||||||
|
(placement (component S (place P1 2000 -5000 front 0) (place P2 18000 -5000 front 0)))
|
||||||
|
(library (image S (pin pad 1 0 0)) (padstack pad (shape (rect F.Cu -600 -600 600 600)) (attach off)))
|
||||||
|
(network (net PWR (pins P1-1 P2-1))
|
||||||
|
(class Power PWR (rule (width 400) (clearance 150)))))"""
|
||||||
|
|
||||||
|
# two keepouts leave a 0.65 mm channel: room for 0.15 mm (0.45), not for 0.4 mm (0.7)
|
||||||
|
_CHANNEL = (
|
||||||
|
'(keepout "" (polygon F.Cu 0 9000 0 11000 0 11000 -4675 9000 -4675))\n'
|
||||||
|
' (keepout "" (polygon F.Cu 0 9000 -5325 11000 -5325 11000 -10000 9000 -10000))'
|
||||||
|
)
|
||||||
|
|
||||||
|
|
||||||
|
def _route(keepouts=""):
|
||||||
|
return build_exact_routing_result(parse_dsn(_BOARD.format(keepouts=keepouts)), resolution=2)
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_wider_class_is_routed_and_written_at_its_width():
|
||||||
|
result = _route()
|
||||||
|
assert result.unrouted == [] and result.narrowed == []
|
||||||
|
widths = {w.width for net in result.nets for w in net.wires}
|
||||||
|
assert widths == {400.0}
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_wider_class_that_does_not_fit_falls_back_to_the_default():
|
||||||
|
result = _route(_CHANNEL)
|
||||||
|
assert result.unrouted == []
|
||||||
|
assert [net for net, _a, _b in result.narrowed] == ["PWR"]
|
||||||
|
widths = {w.width for net in result.nets for w in net.wires}
|
||||||
|
assert widths == {150.0}
|
||||||
@@ -202,6 +202,18 @@ def test_smd_pads_reach_an_inner_plane_by_their_own_via():
|
|||||||
assert all(names[layer] in ("F.Cu", "B.Cu") for segs in result.result.wires.values() for layer, _ in segs)
|
assert all(names[layer] in ("F.Cu", "B.Cu") for segs in result.result.wires.values() for layer, _ in segs)
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_pad_outside_the_plane_routes_to_it():
|
||||||
|
# G1 sits left of a plane that covers only the right half, so its route
|
||||||
|
# has to reach the plane's cells: those ends are the plane, not a pin
|
||||||
|
dsn_text = _four_layer_dsn().replace(
|
||||||
|
"(plane GND (polygon In1.Cu 0 500 -500 29500 -500 29500 -29500 500 -29500 500 -500))",
|
||||||
|
"(plane GND (polygon In1.Cu 0 15000 -500 29500 -500 29500 -29500 15000 -29500 15000 -500))",
|
||||||
|
)
|
||||||
|
result, _scale, _names = route_dsn_board_exact(parse_dsn(dsn_text))
|
||||||
|
gnd = next(i + 1 for i, n in enumerate(parse_dsn(dsn_text).nets) if n.name == "GND")
|
||||||
|
assert gnd in result.result.routed_net_numbers
|
||||||
|
|
||||||
|
|
||||||
def test_a_through_hole_pad_inside_a_plane_needs_no_route():
|
def test_a_through_hole_pad_inside_a_plane_needs_no_route():
|
||||||
from freeroute.route.grid_router import _connected_groups
|
from freeroute.route.grid_router import _connected_groups
|
||||||
|
|
||||||
@@ -211,3 +223,29 @@ def test_a_through_hole_pad_inside_a_plane_needs_no_route():
|
|||||||
groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
|
groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
|
||||||
hub = next(g for g in groups if g[1])
|
hub = next(g for g in groups if g[1])
|
||||||
assert [p.component_ref for p in hub[0]] == ["GT"]
|
assert [p.component_ref for p in hub[0]] == ["GT"]
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_pad_inside_a_via_keepout_reaches_the_plane_by_a_via_outside_it():
|
||||||
|
# a sensor's GND pad: vias are forbidden under the body, so the route
|
||||||
|
# has to leave on the top layer and drop to the plane past the keepout
|
||||||
|
dsn = parse_dsn("""(pcb repro (parser) (resolution um 10) (unit um)
|
||||||
|
(structure
|
||||||
|
(layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
|
||||||
|
(layer B.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 20000 0 20000 -20000 0 -20000 0 0))
|
||||||
|
(plane GND (polygon In1.Cu 0 500 -500 19500 -500 19500 -19500 500 -19500 500 -500))
|
||||||
|
(via_keepout "" (polygon signal 0 8500 -8500 11500 -8500 11500 -11500 8500 -11500 8500 -8500))
|
||||||
|
(via "Via[0-3]_600:300_um") (rule (width 150) (clearance 150)))
|
||||||
|
(placement (component S (place G1 10000 -10000 front 0)))
|
||||||
|
(library
|
||||||
|
(image S (pin smd 1 0 0))
|
||||||
|
(padstack smd (shape (rect F.Cu -175 -300 175 300)) (attach off))
|
||||||
|
(padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
|
||||||
|
(network (net GND (pins G1-1))))""")
|
||||||
|
exact, scale, _names = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
assert exact.result.failed == []
|
||||||
|
(via,) = exact.result.vias[1]
|
||||||
|
half = 300 * scale # the via's radius
|
||||||
|
outside = (via.x + half <= 8500 * scale or via.x - half >= 11500 * scale
|
||||||
|
or via.y - half >= -8500 * scale or via.y + half <= -11500 * scale)
|
||||||
|
assert outside, f"via at {via} is inside the via keepout"
|
||||||
|
|||||||
@@ -0,0 +1,136 @@
|
|||||||
|
"""Vias keep hole-to-hole spacing, even within one net."""
|
||||||
|
|
||||||
|
from __future__ import annotations
|
||||||
|
|
||||||
|
import itertools
|
||||||
|
import math
|
||||||
|
|
||||||
|
from freeroute.dsn import parse_dsn
|
||||||
|
from freeroute.route.pipeline import route_dsn_board_exact
|
||||||
|
|
||||||
|
# four GND pads 0.5 mm apart over a GND plane: each drops a via to the plane
|
||||||
|
_DSN = """(pcb holes (parser) (resolution um 10) (unit um)
|
||||||
|
(structure
|
||||||
|
(layer F.Cu (type signal)) (layer In1.Cu (type power)) (layer In2.Cu (type power))
|
||||||
|
(layer B.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 20000 0 20000 -20000 0 -20000 0 0))
|
||||||
|
(plane GND (polygon In1.Cu 0 500 -500 19500 -500 19500 -19500 500 -19500 500 -500))
|
||||||
|
(via "Via[0-3]_500:300_um") (rule (width 150) (clearance 150)))
|
||||||
|
(placement (component S (place G1 9000 -10000 front 0) (place G2 9500 -10000 front 0)
|
||||||
|
(place G3 10000 -10000 front 0) (place G4 10500 -10000 front 0)))
|
||||||
|
(library
|
||||||
|
(image S (pin smd 1 0 0))
|
||||||
|
(padstack smd (shape (rect F.Cu -150 -300 150 300)) (attach off))
|
||||||
|
(padstack "Via[0-3]_500:300_um" (shape (circle F.Cu 500)) (shape (circle B.Cu 500)) (attach off)))
|
||||||
|
(network (net GND (pins G1-1 G2-1 G3-1 G4-1))))"""
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_nets_own_vias_keep_hole_to_hole_spacing():
|
||||||
|
dsn = parse_dsn(_DSN)
|
||||||
|
exact, scale, _ = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
assert exact.result.failed == []
|
||||||
|
vias = exact.result.vias[1]
|
||||||
|
assert len(set(vias)) == len(vias), "a via written twice"
|
||||||
|
need = (300 + 250) * scale # drill + 0.25 mm, centre to centre
|
||||||
|
for a, b in itertools.combinations(vias, 2):
|
||||||
|
assert math.hypot(a.x - b.x, a.y - b.y) >= need, f"vias at {a} and {b} too close"
|
||||||
|
|
||||||
|
|
||||||
|
def test_connections_sharing_a_plane_via_write_it_once():
|
||||||
|
# eight GND pads 0.4 mm apart: the hole spacing makes several of them
|
||||||
|
# end on the same plane via, which must come out once, not once each
|
||||||
|
pads = " ".join(f"(place G{i} {9000 + 400 * i} -10000 front 0)" for i in range(8))
|
||||||
|
pins = " ".join(f"G{i}-1" for i in range(8))
|
||||||
|
dsn = parse_dsn(
|
||||||
|
_DSN.replace(
|
||||||
|
"(place G1 9000 -10000 front 0) (place G2 9500 -10000 front 0)\n"
|
||||||
|
" (place G3 10000 -10000 front 0) (place G4 10500 -10000 front 0)",
|
||||||
|
pads,
|
||||||
|
)
|
||||||
|
.replace("(pins G1-1 G2-1 G3-1 G4-1)", f"(pins {pins})")
|
||||||
|
.replace("(rect F.Cu -150 -300 150 300)", "(rect F.Cu -125 -300 125 300)")
|
||||||
|
)
|
||||||
|
exact, _scale, _ = route_dsn_board_exact(dsn, resolution=2)
|
||||||
|
vias = exact.result.vias[1]
|
||||||
|
assert len(vias) < 8, "no via is shared, so this board no longer tests sharing"
|
||||||
|
assert len(set(vias)) == len(vias), "a shared via written more than once"
|
||||||
|
|
||||||
|
|
||||||
|
def _router(dsn_text, via_drill_um=300):
|
||||||
|
from freeroute.board import build_board
|
||||||
|
from freeroute.route.grid_router import GridRouter
|
||||||
|
from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn
|
||||||
|
|
||||||
|
dsn = parse_dsn(dsn_text)
|
||||||
|
s = dsn.resolution.value
|
||||||
|
return GridRouter(
|
||||||
|
build_board(dsn), trace_width=round(_rule_width_dsn(dsn) * s),
|
||||||
|
clearance=round(_rule_clearance_dsn(dsn) * s), resolution=2, orthogonal=True,
|
||||||
|
via_drill=via_drill_um * s, hole_to_hole=250 * s,
|
||||||
|
), s
|
||||||
|
|
||||||
|
|
||||||
|
_THT = """(pcb tht (parser) (resolution um 10) (unit um)
|
||||||
|
(structure (layer F.Cu (type signal)) (layer B.Cu (type signal))
|
||||||
|
(boundary (path pcb 0 0 0 20000 0 20000 -20000 0 -20000 0 0))
|
||||||
|
(via "Via[0-1]_500:300_um") (rule (width 150) (clearance 150)))
|
||||||
|
(placement (component T (place J1 10000 -10000 front 0)))
|
||||||
|
(library (image T (pin tht 1 0 0))
|
||||||
|
(padstack tht (shape (circle F.Cu 1700)) (shape (circle B.Cu 1700)) (attach off))
|
||||||
|
(padstack "Via[0-1]_500:300_um" (shape (circle F.Cu 500)) (shape (circle B.Cu 500)) (attach off)))
|
||||||
|
(network (net SIG (pins J1-1))))"""
|
||||||
|
|
||||||
|
|
||||||
|
def test_no_via_goes_near_a_through_hole_pads_hole_even_of_its_own_net():
|
||||||
|
router, s = _router(_THT)
|
||||||
|
pin = router._cell_of(router.board.get_pins()[0].location)
|
||||||
|
assert not router._holes_clear(pin, 1) # own net, right on the pad
|
||||||
|
far = (pin[0] + 40, pin[1])
|
||||||
|
assert router._holes_clear(far, 1)
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_via_in_a_pad_keeps_hole_spacing_from_a_fixed_via():
|
||||||
|
from freeroute.geometry import IntPoint
|
||||||
|
|
||||||
|
text = _THT.replace("(network (net SIG (pins J1-1))))",
|
||||||
|
"(network (net SIG (pins J1-1)))\n"
|
||||||
|
" (wiring (via \"Via[0-1]_500:300_um\" 3000 -3000 (net SIG) (type route))))")
|
||||||
|
router, s = _router(text)
|
||||||
|
assert not router._hole_clear_at(IntPoint(3400 * s, -3000 * s)) # 0.4 mm < 0.55 mm
|
||||||
|
assert router._hole_clear_at(IntPoint(3600 * s, -3000 * s))
|
||||||
|
|
||||||
|
|
||||||
|
def test_hole_spacing_from_a_fixed_via_is_measured_from_where_it_really_is():
|
||||||
|
# a fixed via off the grid with its own 0.25 mm drill, and the router's
|
||||||
|
# via a smaller 0.2 mm one (the flight controller's case): a new via needs
|
||||||
|
# its centre 0.1 + 0.125 + 0.25 = 0.475 mm away, measured exactly, where
|
||||||
|
# one rule for all vias gave 0.2 + 0.25 = 0.45 from the cell centres
|
||||||
|
text = _THT.replace("(network (net SIG (pins J1-1))))",
|
||||||
|
"(network (net SIG (pins J1-1)) (net GND))\n"
|
||||||
|
" (wiring (via \"Via[0-1]_500:250_um\" 3030 -3030 (net GND) (type route))))")
|
||||||
|
text = text.replace(
|
||||||
|
'(attach off)))\n (network',
|
||||||
|
'(attach off))\n (padstack "Via[0-1]_500:250_um" (shape (circle F.Cu 500)) '
|
||||||
|
'(shape (circle B.Cu 500)) (attach off)))\n (network',
|
||||||
|
)
|
||||||
|
router, s = _router(text, via_drill_um=200)
|
||||||
|
via = next(v for v in router.board.get_items() if getattr(v, "drill", 0))
|
||||||
|
assert via.drill == 250 * s
|
||||||
|
loc = via.location
|
||||||
|
for cell in [(x, y) for x in range(router.cols) for y in range(router.rows)]:
|
||||||
|
c = router._cell_center(cell)
|
||||||
|
d = math.hypot(c.x - loc.x, c.y - loc.y)
|
||||||
|
if router.step * 1.5 < d < 470 * s:
|
||||||
|
assert not router._holes_clear(cell, 1), f"{d / s:.0f} um from the fixed via"
|
||||||
|
elif 560 * s < d < 700 * s and cell not in router._tht_block:
|
||||||
|
assert router._holes_clear(cell, 1)
|
||||||
|
|
||||||
|
|
||||||
|
def test_a_route_keeps_its_own_vias_apart():
|
||||||
|
# a route that changed layer at (10, 10) may not change layer again one
|
||||||
|
# cell away; the same cell is the same through via, and far is fine
|
||||||
|
router, _s = _router(_THT)
|
||||||
|
came_from = {(10, 10, 1): (10, 10, 0), (11, 10, 1): (10, 10, 1), (12, 10, 1): (11, 10, 1)}
|
||||||
|
assert router._near_path_via((12, 10, 1), (11, 10), came_from)
|
||||||
|
assert not router._near_path_via((12, 10, 1), (10, 10), came_from)
|
||||||
|
assert not router._near_path_via((12, 10, 1), (40, 10), came_from)
|
||||||
Reference in New Issue
Block a user