-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 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 @@ -28,12 +28,15 @@ 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. +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 the endpoint vertices through 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.
+TODO: img +
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 @@ -42,7 +45,7 @@
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 +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.
@@ -50,8 +53,8 @@
-The central data structure describes a crossings of a 2net and an edge.
-Each crossing is collected in two ordered linked lists:
+The central data structure describes a crossings of a 2net and an edge.
+Each crossing is collected in two ordered doubly linked lists:
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
+Each 2net is specified by a starting and an ending trinagulation
+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.
-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
+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:
+
+There are two reasons for excluding the next node from the A* search:
+
+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 or target vertex within the same triangle.
+
+TODO: passthru1
+
+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 is:
+
+TODO: image passthru1
+
+ Case 1:
+path (green) going out from a vertex of the current triangle does not
+change the result of the visibility test:
+
+TODO: image passthru2
+
+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 case 1, tracing CCW: because of 3b., the search reaches target edge after
+tracing S2's edge, vertex PB and the blue path.
+ Case 3: visibility blocked
+
+TODO: image passthru3
+
+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.
TRBD algorithm
+ TRBD algorithm: path finding
+
+
+
+
+ TRBD algorithm: query in-triangle visibility
+
+
+
+
+
+
+ TRBD algorithm: example cases
+