Index: TRBS/trbs.html =================================================================== --- TRBS/trbs.html (revision 532) +++ TRBS/trbs.html (revision 533) @@ -12,7 +12,7 @@ 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 +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.

@@ -24,7 +24,7 @@ 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. +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.

@@ -33,7 +33,7 @@ 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. +crossing triangulation edges.

TODO: img

@@ -51,7 +51,7 @@

This document focuses on the TRBS step. -

TRBD data model

+

TRBS data model

The central data structure describes a crossings of a 2net and an edge. Each crossing is collected in two ordered doubly linked lists: @@ -71,7 +71,7 @@

Note: multiple crossing points of the same 2net-edge can occur [TODO: drawing].

-Each 2net is specified by a starting and an ending trinagulation +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 @@ -82,16 +82,16 @@ vertex 2. Which triangulation vertex is called 1 is an arbitrary choice made during triangulation (and never changed later). -

TRBD algorithm: path finding

+

TRBS algorithm: path finding

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:

-

TRBD algorithm: query in-triangle visibility

+

TRBS algorithm: query in-triangle visibility

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 @@ -129,7 +129,7 @@ TODO: image passthru1

-

TRBD algorithm: example cases

+

TRBS algorithm: example cases

Case 1: path (green) going out from a vertex of the current triangle does not change the result of the visibility test: