Figure 1: triangulation; grey lines are triangle edges; yellow lines are three 2nets to route
Update: it turned out there is a case that TRBS can not handle so it can not be used for the toporouter.
netlist -> LAA -> NORD -> TRBS -> embed geometry
The Layer Assignment Algorithm (LAA) receives the netlist of the input board and breaks down the routing problem into independent, single layer routing problems by assigning network segments (2nets) to specific layers. All vias, with their final coordinates, are added in this step. By using multiple layers the LAA resolves many net-net crossings. For various reasons some of the crossings will be left in the output, and those crossings will need to be resolved by on-layer detours.
The output of the LAA, per layer, is an unordered list of 2nets. A 2net is described by its two fixed endpoints (vertices) in the 2d space. The Network Ordering (NORD) step orders the list so that networks with more direct, more straight-line connections (less detour) come first.
The next step, the Triangulated Rubber Band Sketch router (TRBS) will route 2nets one by one, in the exact order the NORD specified. If a 2net being routed would cross a 2net already routed, the current 2net needs to make detour. The TRBS considers multiple detours trying to find the shortest. If there is no route possible, the TRBS changes the net ordering and tries again.
Figure 1: triangulation; grey lines are triangle edges; yellow lines are three 2nets to route
The TRBS performs these operations on a mixed model: it takes the input geometry (vias, obstacles, board size) and triangulates it (Figure 1). The triangulation yields vertices (at obstacles) and edges that connect the vertices and triangles (defined by 3 vertices or 3 edges).
2nets are routed on a path from a starting vertex through edge crossings until it reaches the ending vertex (Figure 2). Paths are abstract, topological: the exact coordinates of the 2nets are not considered, only the order of 2net-edge crossings.
Figure 2: two possible paths (blue and green) connecting 2net starting vertex S with ending vertex T; path-edge crossings are indicated with red X marks
Furthermore each 2net has a required geometry (wire thickness and clearance), and edges have physical lengths. Local congestion is avoided by refusing routing a 2net across an edge if the edge ran out of capacity - in which case an alternate (longer) detour is searched or ultimately network ordering is changed.
Finally, of the TRBS finished routing (Figure 3), the result is a list of topological edge crossing for each triangulation edge for each 2net on its way between its start and end vertex. The last step is translating these crossings back to physical geometry, introducing new edges (spokes) and moving the 2net-edge crossing points on the edge without changing the order of them.
Figure 3: three networks (blue) routed by this algorithm; first the two horizontal ones then the vertical one
This document focuses on the TRBS step.
The central data structure describes a crossing of a 2net and an edge. Each crossing is collected in two ordered doubly linked lists:
There are no restrictions on the number of crossings: any number of 2nets may cross an edge (as long as the capacity of the edge can take the 2nets, i.e. length of the edge justifies the total space taken up by 2net wire thicknesses and clearances). Walking the path of a 2net, there can be any number of crossings, from zero up, but any time the 2net is crossing a triangulation edge, there must be a crossing created.
Note: multiple crossing points of the same 2net-edge can occur, as shown on Figure 3.
Figure 3: the blue net between A and B need to make detours around other (blue) nets. On the way, it crosses some edges (marked with red) twice, at different locations. Blue nets are routed by this algorithm
Each 2net is specified by a starting and an ending triangulation vertex and an ordered doubly linked list of crossings. Which terminal/via is the starting vertex and which terminal/via is the ending vertex is an arbitrary choice of the LAA, but once the choice is made, it is not changed.
In the triangulation each edge is connected to two vertices, has a known physical length and holds an ordered list of crossing from vertex 1 to vertex 2. Which triangulation vertex is called 1 is an arbitrary choice made during triangulation (and never changed later).
A 2net is always starting from a vertex, will cross zero or more edges (last edge being part of the triangle with the ending vertex), then will connect to the ending vertex. This path can be searched using the A* algorithm, on a graph formed by these rules:
Figure 5: path finding with A*;
a.: case S: start from vertex S, potential next graph nodes are the
vertices marked with red arrows (assuming T is not on any neighbor
vertex on this drawing)
b.: thick blue line is the path crossing the left edge of a triangle;
since the triangle contains the end vertex T, the only one next node
is T and the path is completed (thin blue line).
c.: thick blue line is the path crossing the left edge of a triangle;
since T is not in the triangle, there are two possible ways the path
could continue (thin blue lines); the two affected edges
(marked with red arrows) are the potential next nodes of the A* search graph
There are two reasons for excluding the next node from the A* search:
The cost function is path length assuming edge crossing points are located at where they result in the shortest path, ignoring wire widths and clearances. The heuristic function is the distance to the 2net's ending vertex.
The path is entering a triangle from a vertex or from a specific point on an edge. Point on an edge is in the topological sense, not in the geometrical sense: all points between two existing crossing or edge endpoint are the same. Main input is the enter point or vertex. Other input is a target edge (see Figure 5/c, marked with red arrows) or target vertex within the same triangle (see Figure 5/b, T).
Figure 6: edge-to-edge visibility in a triangle; annotations are drawn with red, existing paths (routed with this algorithm) are drawn with blue
In case of target edge, the output is a point on that edge (which topologically means the index on the edge's crossing list, where the new crossing is to be inserted between edge end vertices or existing crossings). In case of target vertex, the output is a boolean, whether that vertex is visible or not.
The algorithm for determining visibility (e.g. on Figure 6) is:
Case 1: path (green) going out from a vertex of the current triangle does not change the result of the visibility test:
Figure 7: blue and green nets (routed by this algorithm) starting from triangle vertices, still S2 finds its target edge point
On Figure 7, a CW search from S2 first reaches vertex PA then will jump to the edge PA-PC, which is the target edge.
Case 2: On Figure 7, tracing CCW from S2: because of 3b., the search reaches target edge after tracing S2's edge, vertex PB and the blue path.
Case 3: visibility blocked
Figure 8: target edge not visible from S2 because of an existing path
On Figure 8, starting from S2, tracing CCW: trace S2's edge to PB, then switch edge by 3c, bumping into the blue path by 4, tracing it to edge PA-PB; this edge is the edge S2 is on. By 5, return failure.