Topo-geometric detour router
+ +4. Appendix
++This chapter contains material that is not part of the specification, +not required for understanding or implementing the topo-geometric detour +router but may help exploring the problem and practical aspects of the +implementation. + +
4.1. Examples
+ +4.1.1. Topology: passing by two obstacles
+ ++
+
Figure 4/1. a. initial state; b. adding N1-N2 CW; c. adding N1-N3 CCW +
+The decision tree starts from the initial state, with a single crossing, yielding +a number of child states. One of the childe states is drawn on Figure 4/1 b, +which introduces two new conflicts between N1 and N3. There can be multiple +reasons why the search prefers this over direct one-step solutions: +
+
-
+
- there is only one layer available +
- there are obstacles on other layers +
- going around in N1-N2 CCW results in a crossing too +
- weights for the cost function are set so that that the + detour length penalty of N1-N2 CCW or adding vias seems + more expensive than resolving two more conflicts +
+Once the decision is made by the decision tree search to explore this case, +the final solution is one step away: an N1-N3 CCW operation creates a state +that is a valid solution. + +
4.1.2. Topology: order of routes in the script
+ ++
+
Figure 4/2. a. initial state for two nets; b. and c. differs only in order of conflict resolution +d. initial state for three nets; e. and f. differs only in order of conflict resolution +
+The algorithm never needs to "push" existing copper objects, as it never +needs to insert a new track in between two existing tracks if there is not +enoguh room between them. The algorithm achieves the same result by trying +a different order of similar operations as shown on Figure 4/1 a, b and c. +if conflict #2 is resolved first, the new conflict for N1 is the detour of +N2, which results in the order shown on b. However, this resolution introduces +an extra conflict, which will probably make the tree search algorithm first try +c., where N1 is resolved first (removing one coflict) but then any try to +resolve conflict #2 on N1 within the layer will cause more conflicts, which +will eventually make b. more viable. +
+A vairant of the same idea applied to vias is demonstrated on d, e and f. +TODO: specify how vias are described in the script + +
4.1.3. Topo-geo: the three net conflict
++The solution for the classic three net crossing conflict, which a pure +geometric solver can not solve, is shown on Figure 4.3. It is assumed +that there are obstacles around the bounding box of the drawing, i.e. +the outline of the board fits tightly on the 4 outer terminal and only +one layer is available. Starting points of the two-nets are top or left. + +
+
+
Figure 4/3. a. initial state; b. resolving #1: N1-N2 CW; +c. resolving #2: N1-N3 CW; d. resolving #3: N2-N1 CW; e. resolving #4: N1-N2 CW +f. the reamining too-close conflict #5, could be resolved by: N3-N1 CW +
+The final script is: +
+N1-N2 CW +N1-N3 CW +N2-N1 CW +N1-N2 CW +N3-N1 CW ++
+The alternative paths, N1-N2 CCW in b. or N1-N3 CCW in c. are not available +because the detour path (drawn in red) would cross unmovable objects (board +edge). It may be that the search tries them but those branches of the tree +will die. +
+Both state c and d features the "N1 line is within the naked convex hull of +the offended two-net" case, that's why the seeminlgy non-convex hull. + + + +
4.1.4. Topo-geo: bottleneck
++A bottleneck situation can not always be resolved on a single layer. This +example demonstrates that any branch of the search tree that attempts to +resolve the problem by detours on the same layer will fail. This will +eventually force the tree search algorithm to explore possibilities with vias. +N3 is unmovable. +
+
+
Figure 4/4. a. initial state; b. resolving #1; c. resoving #2 after #1; +d. resolving new conflict after c will cause oscillation; +e. restart from a, attempt to resolve #2 first; f. resolution for #2 introduces +new N1-N2 conflict #3; g. resolution to #3 would cause N1 to cross unmovable +objects +
4.1.5. Topology: multiple conflicts
++
+
Figure 4/5. a. initial state; b. resolving #1 (N1-N2 CCW); c. resolving +#2 (N1-N3 CCW) also resolves #3; d. alternative resolution to c. is +N1-N3 CW; e. then N1-N4 CW f. but that introduces #4, where N1 is too close +to N3 so an N1-N3 CW is required, with the same result as c. +
+NOTE: this example did not employ the "resolve first conflict from start" +optimization. With that optimization, the script would be: +
+N1-N2 CCW +N1-N4 CCW +N1-N3 CCW ++
+and the result would be the same as c. and f. + + + +
4.1.5. Topo-geo: routing through zig-zag labyrinth
+Blu nets N2 and N3 are unmovable, there is only one layer +available and it is impossible to go around. Hence N1 is forced +to find its way bending at P1, P2, P3 and P4. N1 start is top. ++
+
Figure 4/6. a. initial state; b. N1-N2 CW; c. N1-N3 CCW; d. because +of changed line angles, first conflict is N1 getting to close to N2 at P1; +resolve that as N1-N2 CW. +
+The final script will include a few operations to resolve the crossings +and a few operations to resolve the new "going near" cases demonstrated on +Figure 4/6. d. The next step after d. would be to resolve the clearance +violation at P3, then resolving the last N1-N3 crossing on the bottom. +The final script is: + +
+N1-N2 CW +N1-N3 CCW +N1-N2 CW +N1-N2 CW +N1-N3 CCW ++ + + + + +
4.1.6. Topology: oscillation detection
++This is an optimization because the algorithm would work without this as +well: in case of oscillation, the script grows long which increases the +cost function which in turn will make other solutions more favorable. However +this would cause a lot of computation wasted on recalculating the oscillation +many times. + Index: trunk/doc/detour/img/ex_topo.lht =================================================================== --- trunk/doc/detour/img/ex_topo.lht (revision 900) +++ trunk/doc/detour/img/ex_topo.lht (revision 901) @@ -351,6 +351,27 @@ } rot = 0.000000 } + ha:text.864 { + string=N3; x=22.0mm; y=1.5mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.866 { + string=N3; x=51.75mm; y=1.5mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } + ha:text.867 { + string=N3; x=81.25mm; y=1.5mm; scale=100; fid=0; + ha:flags { + clearline=1 + } + rot = 0.000000 + } } color = {#104e8b} } Index: trunk/doc/detour/index.html =================================================================== --- trunk/doc/detour/index.html (revision 900) +++ trunk/doc/detour/index.html (revision 901) @@ -8,4 +8,5 @@