Topo-geometric detour router

3. Convex hull path

This chapter focuses on the geometric (low) level of the router. It proivides an API that can calculate the geometry of a detour of a trace object and a network but does not decide which detours should be calculated.

3.1. Different detours

A conflict is always between two specific drawing primitives: a trace object (line or arc) of a two-net (N1) and any type of object of another two-net (N2). The detour is calculated so that the offending line or arc object of N1 is replaced by a series of arcs and lines going around all objects of N2.

There are 8 different ways a this can be done, depending on how existing objects are arranged in the current state of the board. The first choice is made by the caller: switch layer or stay on layer.

Figure 3/1. Decision tree for different possible detours.

In case of vias, there are three different possibilities, all three may be valid. In case of stay-on-layer, exactly one of the three possibilites is chosen, depending on how many endpoints of N1 is within the convex hull of N2, but some of the choices may result in two different potential paths in CW or CCW directions.

3.2. Clearance, spokes, convex hull

Trace objects are specified by their width and clearance. Vias are specified by their copper radius and clearance - which is equvalent to the specification of a zero length line or arc width and clearance. When the minimum distance of centerlines of two objects need to be calculated, the following formula is used:

D = W1/2 + W2/2 + max(C1, C2);

where D is the centerline distance, W1 and W2 are the width of object 1 and object 2 respectively and C1 and C2 are the clearances of those objects. The max function returns the larger of its two arguments.

Figure 3/2. Convex hull based detours. a. yellow dashed two-net line crosses the blue two-net; we expect the algorithm to come up with two possible detours D1 and D2; b. clearance spokes inserted on the corners of the blue net; c. convex hull (red) calculated from spokes and the two endpoints of the dashed yellow line

The possible detour paths are sections of the convex hull of carefully chosen points (Figure 3/2). Calculating the convex hull is normally done in 5 steps:

1. knowing the parameters of N1 and N2, calculate their mutual D (centerline distance) value (Note: D may be different for terminals, vias and lines of N2)
2. add spokes to each corner of N2 in 8 directions (n*45 degrees) of length D
3. use the endpoints of the spokes as input for a convex hull calculation; most of the time the endpoints of the offending N1 line needs to be used as well
4. most of the cases will requre endpoints of the offending N1 line, or other points added; these points will be the ones that will split the resulting convex hull into two halves (CW and CCW)
5. calculate the convex hull from these points

Corners are: endpoints of line objects, center of via, every vertex of polygon objects. TODO: arc.

A convex hull of two-net N2 [in context of offending object of N1] means: the convex hull of all spokes N2, where spoke lengths are calculated with D for N1.

A naked convex hull of two-net N2 is the convex hull calculated using only the centerlines of N2 objects, without considering widths or clearances.

3.3. Stay-on-layer cases: S1, S2, S3

First the naked convex hull of N3 is calculated so that the the decision for S1, S2 or S3 can be made.

3.3.1. S1: both ends outside

Both ends of the offending line object of N1 are outside of the naked convex hull of N3. The two possible detour paths are calculated as:

collect all spoke endpoints of N3, add the two endpoints of the offending trace line object of N1
calculate the convex hull
split the hull in two at the N1 offending line endpoints
replace the offending N1 line with either the CW or the CCW half of the hull

Figure 3/3. a. case S1 applied to a line segment of N1 already making a detour around N2 (the current S1 is trying to resolve an N1-N3 conflict); starting point of N1 is the top terminal; b. convex hull (red) calculated and split into D1 (CCW) and D2 (CW). c. new board state if the caller choose D1 (CCW)

Note: originally the endpoint of the offending line is the spoke endpoint on N2 marked with the little red circle. After resolving the conflict as of Figure 3/3 c., the detour takes the shortest path from the spokes calculated for N3 to the original endpoint of the offending line. This shortest path now gets too close to N2. This is not detected in this step. Instead it is detected in a subsequent cross detection step which will mark it as a new (weaker) conflict in the state decision tree, which will let the high level resolve it with a new detour between N1 and N2, with the offending object being the new, shorter, almost horizontal yellow line at the little red square mark.

N1 does not need to cross or even touch N3, it is enough if it gets closer than the requred clearance. However, this case can be resolved by the same algorithm, as shown on Figure 3/4.

Figure 3/4. a. the same example, expect N1 is not crossing or touching anything in N3 but getting too close to it; b., c.: same steps

3.3.2. S2: One end outside

One end of the offending line object of N1 is outside of the naked convex hull of N3, the other end is inside (Figure 3/5, marked P0). The two possible detour paths are calculated as:

calculate a convex hull of N3 with the offending line outside endpoint (P4) included
find a section of the convex hull of N3 that has a direct line of visibility from the offending object endpoint that is inside
the direct line of sight may not cross spokes of N3
split the hull in two:
- CW: P0-P1-P4
- CCW: P0-P2-P4
replace the offending N1 line with either the CW or the CCW path from the previous point

TODO: this path is suboptimal in two places: at P1/P2 and at P4. Maybe we could add an optimization pull step here.

Figure 3/5. a. the same example, modified so the starting endpoint of N1 is within the convex hull of N3; b. is the new convex hull (red) and line-of-sight probes (green); c. is the final detour path (yellow) and the possible other detour path (red).

3.3.3. S3: Both ends inside

Both ends of the offending line object of N1 is inside of the naked convex hull of N3 (Figure 3/6). There is only one possible detour path.

First collect the N3 corners that are contributing the violation:

if the offending N1 line crosses any N3 objects, the corners of those N3 objects that are between the two crossings are added (Figure 3/6, b) (TODO: this doesn't handle junctions, polygons and generally things that are hanging inside N3 from the wall!)
in such crossing, also add the crossing points (Figure 3/6, b)
if the offending N1 line is getting too close to any corner of N3, add those corners too (Figure 3/6, e)
always add both endponits of the offending N1 line

Figure 3/6. a. N1 inside N3, crossing edges; b. spokes and convex hull; c. path chosen; d. same case but no crossing; e. spokes and convex hull; f. path chosen;

Once those corners are collected, the path calculation is:

calculate a convex hull using the above corners and their N3-N1 spokes
split the hull in two at the offending line endpoints
one half will cross N3 - throw it away
the other half is the resulting path; replace the offending line with this path

TODO: However, this will break in the following case:

Figure 3/x. zig-zag example: if the vertical dashed line is intersected from both left and right by N3, the hull won't work! probably go "one-by-one"?

3.4. Switch-layer cases: V1, V2, V3

First exclude V1 or V2 depending on the existing objects on offending N1 line endpoints:

V1 is possible only if both ends of the offending N1 line is on existing vias or terminals that reach multiple layers.
V2 is possible only if one of the endpoints of the offending N1 line is already on a via or through-hole terminal.
V3 is always possible.

For V2 and V3, the via should be placed as close as possible to the offended two-net. (Rationale: the policy for state state search is that we are not going to insert new paths between two tightly packed paths but we will rather swap the order of routing for them). Close placement is achieved by calculating the intersection of the offending N1 line and the convex hull of the offended two-net, using N1 via geometry for spoke D value. The intersection point is the closest possible point for the via.

TODO: draw this!