+
Figure 3/1. Decision tree for different possible detours. +
+Note: if there are more than 2 layers, each new layer adds 6 more possible +states using vias. -
It is possible to draw a tree of the possible solutions. Each node of Index: trunk/doc/detour/3_hull.html =================================================================== --- trunk/doc/detour/3_hull.html (nonexistent) +++ trunk/doc/detour/3_hull.html (revision 894) @@ -0,0 +1,208 @@ + +
+ ++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! Index: trunk/doc/detour/img/geo_cases.dot =================================================================== --- trunk/doc/detour/img/geo_cases.dot (revision 893) +++ trunk/doc/detour/img/geo_cases.dot (revision 894) @@ -12,8 +12,8 @@ in1 [label="one end\noutside" shape=square] in2 [label="both ends\ninside" shape=square] - cross0 [label="S1\ncrossing\nor too\nclose to\nobstacle\n"] - cross1 [label="S2\ncrossing\nobstacle"] + cross0 [label="S1\ncrossing\nor too\nclose to\nobstacle\nCW or CCW"] + cross1 [label="S2\ncrossing\nobstacle\nCW or CCW"] cross2 [label="S3\ncrossing\nor too\nclose to\nobstacle\n"] Index: trunk/doc/detour/img/geo_cases.png =================================================================== Cannot display: file marked as a binary type. svn:mime-type = application/octet-stream Index: trunk/doc/detour/img/geo_hpierce.lht =================================================================== --- trunk/doc/detour/img/geo_hpierce.lht (revision 893) +++ trunk/doc/detour/img/geo_hpierce.lht (revision 894) @@ -253,6 +253,60 @@ clearline=1 } } + ha:line.4869 { + x1=55.5mm; y1=14.25mm; x2=58.0mm; y2=14.25mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4942 { + x1=76.25mm; y1=0.75mm; x2=76.25mm; y2=5.75mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4945 { + x1=74.5mm; y1=1.5mm; x2=78.0mm; y2=5.0mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4948 { + x1=74.5mm; y1=5.0mm; x2=77.75mm; y2=1.75mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4951 { + x1=73.75mm; y1=3.25mm; x2=78.5mm; y2=3.25mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5020 { + x1=71.5mm; y1=9.5mm; x2=71.5mm; y2=14.5mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5023 { + x1=69.75mm; y1=10.25mm; x2=73.25mm; y2=13.75mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5026 { + x1=69.75mm; y1=13.75mm; x2=73.0mm; y2=10.5mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5029 { + x1=69.0mm; y1=12.0mm; x2=73.75mm; y2=12.0mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } ha:arc.4684 { x=2.0mm; y=19.5mm; width=0.6mm; height=0.6mm; astart=0.000000; adelta=360.000000; thickness=0.8mm; clearance=50.0mil; ha:flags { @@ -466,12 +520,18 @@ clearline=1 } } - ha:line.3737 { - x1=88.0mm; y1=12.75mm; x2=78.25mm; y2=6.5mm; thickness=0.35mm; clearance=50.0mil; + ha:line.5053 { + x1=85.0mm; y1=9.5mm; x2=88.0mm; y2=12.75mm; thickness=0.35mm; clearance=50.0mil; ha:flags { clearline=1 } } + ha:line.5056 { + x1=78.25mm; y1=6.5mm; x2=85.0mm; y2=9.5mm; thickness=0.35mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } ha:text.2044 { string=N1; x=16.5mm; y=8.75mm; scale=100; fid=0; ha:flags { @@ -678,30 +738,66 @@ clearline=1 } } - ha:line.3725 { - x1=78.25mm; y1=6.5mm; x2=83.25mm; y2=14.25mm; thickness=0.15mm; clearance=50.0mil; + ha:line.4978 { + x1=81.75mm; y1=16.75mm; x2=86.0mm; y2=17.75mm; thickness=0.15mm; clearance=50.0mil; ha:flags { clearline=1 } } - ha:line.3728 { - x1=83.25mm; y1=14.25mm; x2=85.0mm; y2=15.75mm; thickness=0.15mm; clearance=50.0mil; + ha:line.4981 { + x1=74.5mm; y1=1.5mm; x2=69.75mm; y2=10.25mm; thickness=0.15mm; clearance=50.0mil; ha:flags { clearline=1 } } - ha:line.3731 { - x1=85.0mm; y1=15.75mm; x2=86.5mm; y2=16.75mm; thickness=0.15mm; clearance=50.0mil; + ha:line.4984 { + x1=69.75mm; y1=10.25mm; x2=69.0mm; y2=12.0mm; thickness=0.15mm; clearance=50.0mil; ha:flags { clearline=1 } } - ha:line.3734 { - x1=86.5mm; y1=16.75mm; x2=88.25mm; y2=16.0mm; thickness=0.15mm; clearance=50.0mil; + ha:line.4987 { + x1=69.0mm; y1=12.0mm; x2=69.75mm; y2=13.75mm; thickness=0.15mm; clearance=50.0mil; ha:flags { clearline=1 } } + ha:line.4990 { + x1=69.75mm; y1=13.75mm; x2=71.5mm; y2=14.5mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4993 { + x1=71.5mm; y1=14.5mm; x2=81.75mm; y2=16.75mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4996 { + x1=76.25mm; y1=0.75mm; x2=74.5mm; y2=1.5mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.4999 { + x1=77.75mm; y1=1.75mm; x2=76.25mm; y2=0.75mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5047 { + x1=77.75mm; y1=1.75mm; x2=79.2mm; y2=3.3mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } + ha:line.5050 { + x1=79.2mm; y1=3.3mm; x2=78.25mm; y2=6.5mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } ha:arc.1856 { x=55.0mm; y=17.75mm; width=0.5mm; height=0.5mm; astart=0.000000; adelta=360.000000; thickness=0.15mm; clearance=50.0mil; ha:flags { @@ -736,6 +832,12 @@ clearline=1 } } + ha:line.5032 { + x1=47.25mm; y1=6.5mm; x2=48.2mm; y2=3.3mm; thickness=0.15mm; clearance=50.0mil; + ha:flags { + clearline=1 + } + } ha:text.3177 { string=TODO!!; x=52.25mm; y=4.75mm; scale=100; fid=0; ha:flags { @@ -743,6 +845,62 @@ } rot = 0.000000 } + ha:text.4864 { + string=P1; x=54.85mm; y=8.85mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.4865 { + string=P2; x=48.65mm; y=1.85mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.4873 { + string=P1; x=85.75mm; y=8.25mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.4926 { + string=P2; x=79.75mm; y=2.25mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.5060 { + string=P0; x=45.15mm; y=7.6mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.5062 { + string=P0; x=76.4mm; y=7.6mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.5064 { + string=P4; x=2.2007874in; y=17.1mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.5066 { + string=P4; x=86.9mm; y=17.1mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } } color = {#548b54} } @@ -823,10 +981,10 @@ ha:design { text_font_id = 0 text_scale = 100 - via_thickness = 275.60 mil + via_thickness = 137.80 mil via_drilling_hole = 47.24 mil text_thickness = 0 - line_thickness = 150.00 um + line_thickness = 350.00 um clearance = 25.00 mil } ha:editor {