Figure 4/1. a. initial state; b. adding N1-N2 CW; c. adding N1-N3 CCW
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.
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:
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.
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
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.
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
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.
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
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.
TODO: finalzie how to detect this.
Figure 4/7. a. initial state with a gap between N2 and N3 too narrow; b. resolve N1-N3 introducing a crossing on N1-N2; c. resolve the N1-N2 crossing causing and N1-N3 crossing.
When the new N1-N3 crossing is to be resolved, the state will be very similar to b and the solver could keep oscillating between b. and c. With the hull based detour calculation this is a bit worse, because not the whole bent network is moved, only the tiny veryical line segment in the middle between b and c so the drawing on c becomes something like d.
In case of the following spiral (blue net), the low level algorithm is unable to find the otherwise clearly available path for N1. The reason is that this is the "one endpoint in the hull, other endpoint outside of the hull" case, which means a clear sight of line is searched between the inner endpoint and the naked hull.
Figure 4/8. Spiral can block the low level hull based algorithm.
Note: the problem is not present if the blue net is split into two sections anywhere on the east or south wall (to the right from the conflict), because each section is searched separately. That is, the inner part of the spiral is in conflict first, which can be detoured through the second segment, then the second segment conflict is resolved without considering the first segment, then the first segment is conflicted again, etc. So the blocker is not that the final path is a spiral.