+
Figure 3/1. Decision tree for different possible detours. +
+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. + +
+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; this is made by the caller. +
+ +
+
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. + +
+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: +
+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. + +
+The convex hull of N3 (D set for N1) is calculated so that the the decision +for S1, S2 or S3 can be made. + +
+Both ends of the offending line object of N1 are outside of the convex hull +of N3. The two possible detour paths are calculated as: +
+
+
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 +
+One end of the offending line object of N1 is outside of the convex hull +of N3, the other end is inside (Figure 3/5, marked P0). The two possible +detour paths are calculated as: +
+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). +
+Both ends of the offending line object of N1 is inside of the convex hull +of N3 (Figure 3/6). There is only one possible detour path. +
+First collect the N3 corners that are contributing the violation: +
+Once those corners are collected, the path calculation is: +
+First exclude V1 or V2 depending on the existing objects on offending N1 +line endpoints: +
+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!