legalize.hpp File Reference

Gridless legalisation of routed copper (doc 05 §41.3, D104). More...

#include <cstdint>
#include <vector>
#include "geom/point.hpp"
#include "model/board.hpp"
#include "model/rules.hpp"
#include "route/router.hpp"

Go to the source code of this file.

Classes
struct	tmk::route::LegalizeOptions
struct	tmk::route::LegalizeResult

Namespaces
namespace	tmk
namespace	tmk::route

Functions
LegalizeResult	tmk::route::legalize_routes (const model::Board &board, const model::DesignRules &rules, std::vector< ConnRoute > &routes, const LegalizeOptions &opt={})
	Moves the vertices of routes (tracks and vias of the connections) so that the clearances of rules hold between nets, to the pads of board and to its fixed tracks and vias.

Detailed Description

Gridless legalisation of routed copper (doc 05 §41.3, D104).

The lattice router places every track on a lattice point and cannot move one it has committed, so a solution found under looser rules (smaller clearances) usually has room to spare that the lattice cannot use. This module takes such routes and moves the vertices of their tracks and vias (the topology, layers and order along every channel stay as they are) until every clearance of the board's real rules holds, or as many as it can: a vertex is pushed along the normal of each pair of copper items that are too close, by Gauss-Seidel sweeps over the pairs (position-based dynamics, Müller, Heidelberger, Hennix and Ratcliff, J. Vis. Commun. Image Represent. 18(2), 2007). A prototype that solved the same problem by sequential linear programming (HiGHS, minimum total movement) did about as well (6 stuck srj20 boards, 0.06 mm solutions to 0.10 mm: LP 3 legal and 3-11 pairs left on the others, projection 2 legal and 2-9 left). What remains violated is dropped and routed again by the caller, and every route that is kept passes the router's exact check, so the heuristic can lose work but never legality.

Definition in file legalize.hpp.