+
+
Figure 1: triangulation; grey lines are triangle edges; yellow lines + are three 2nets to route +
+
+
+
+
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. The triangulation +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 vertext through edge crossings until it -reaches the ending vertex (Figure 1). Path is abstract, topological: the exact +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 1: triangulation; grey lines are triangle edges; yellow lines - are three 2nets to route +
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
@@ -51,7 +60,7 @@ which case an alternate (longer) detour is searched or ultimately network ordering is changed.
-Finally, of the TRBS finished routing (Figure 2), the result is a list of topological edge +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 @@ -60,7 +69,7 @@
-
Figure 2: three networks (blue) routed by this algorithm; first the two horizontal ones then +
Figure 3: three networks (blue) routed by this algorithm; first the two horizontal ones then the vertical one
+
+
+
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 neighbour
+ 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:
-
Figure 4: edge-to-edge visibility in a triangle; annotations are +
Figure 6: edge-to-edge visibility in a triangle; annotations are drawn with red, existing paths (routed with this algorithm) are drawn with blue
-The algorithm for determining visibility (e.g. on Figure 4) is: +The algorithm for determining visibility (e.g. on Figure 6) is:
-
Figure 5: blue and green nets (routed by this algorithm) starting from triangle vertices, still +
Figure 7: blue and green nets (routed by this algorithm) starting from triangle vertices, still S2 finds its target edge point
-On Figure 5, a CW search from S2 first reaches vertex PA then will jump to the edge PA-PC, +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 5, tracing CCW from S2: because of 3b., the search reaches target edge after +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 @@ -218,10 +245,10 @@
-
Figure 6: target edge not visible from S2 because of an existing path +
Figure 8: target edge not visible from S2 because of an existing path
-On Figure 6, starting from S2, tracing CCW: trace S2's edge to PB, then switch edge +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.