+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 resovles 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 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 detorus trying to find the shortest. +If there is no route possible, the TRBS changes the net ordering and tries +again. +
+The TRBS performs these operations on a mixed model: it takes the input geometry +(vias, obstacles, board size) and triangulates it. Then 2nets are routed +between points and edges on this triangulation. However, this routing is +abstract, topological: the exact coordinates of the 2nets are not considered, +only the order of 2nets crossing trinagulation edges. +
+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, the result is a list of topological edge +crossing for each triangulation edge for each 2net on its way between its +start and end point. 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. +
+This document focuses on the TRBS step. + +
+The central data structure describes a crossings of a 2net and an edge.
+Each crossing is collected in two ordered 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 [TODO: drawing]. +
+Each 2net is specified by a starting and an ending trinagulation +point and an ordered linked list of crossings, from start to end. Which +terminal/via is the starting point and which terminal/via is the ending +point is an arbitrary choice of the LAA, but once the choice is made, it +is not changed. +
+Each triangulation edge is connected to two triangulation point, has +a known physical length and holds an orded lis of crossing from point 1 to +point 2. Which triangulation point is called 1 is an arbitrary choice made +during triangulation (and never changed later). + +