Index: detour/2_topo.html
===================================================================
--- detour/2_topo.html (nonexistent)
+++ detour/2_topo.html (revision 884)
@@ -0,0 +1,153 @@
+
+
+
+ Topo-geometric detour router
+
+ 2. Detour search
+
+ 2.1. Board state
+
+The routing is driven by the detour search performed on possible
+board states. A board state is a specific render of the board, all
+two-nets realized with copper tracks. A board state does not need to be free
+of short-circuits. Each copper object is explicitly bound to a network.
+
+The initial board state is:
+
+ - all terminals and unmovable objects are placed
+
- all two-nets are connected with straight copper lines on the first layer
+
+
+The initial board state usually contains a high number of conflicts:
+short circuits caused by objects of different nets crossing, overlapping or
+getting too close.
+
+
2.2. Detours
+
+Each conflict, regarded as an isolated case, considering only the two
+two-nets participating needs to be resolved. One way of doing that is
+writing an ordered list of resolutions. Figure 2/1 shows the possible resolutions
+of a simple crossing.
+
+
+
+
Figure 2/1.
+a. Input: Two 2-nets, N1 and N2 are crossing at #1. Yellow lines are the initial
+two-nets, blue lines are final choices, grey lines are alternative choices.
+Possible resolutions:
+b. N1 goes around N2 on the left or on the right;
+c. N2 goes around N1 on the top or on the bottom;
+d. two vias are inserted in N1 so it can bypass N2 on another layer;
+e. if endpoint terminal of N1 is through-hole, one via can be saved;
+f. ... or even both vias can be saved;
+(Note: there are three more possibilities with vias where N1 goes to another
+layer, these would have been drawn as g., h. i.).
+
+
+
+To go from the initial state (a.) to any of the resolved states (b. to i.),
+we need to define an operation. For example the operation for b. is
+"N1-N2 CW" for the right-side solution and "N1-N2 CCW" for the left-side
+solution. "N1-N2 CW" means "on N1 at the first crossing of N2, N1 makes
+a detour to go around N2 clock-wise". To be able to determine which is the
+"first" crossing on N1, each two-net has one of its endpoint marked as the
+starting point.
+
+
+
+
2.3. Choosing between detour options
+
+It is possible to draw a tree of the possible solutions. Each node of
+the tree is a board state and each edge of the tree is an operation
+which transforms the parent state into the child state.
+
+The complete tree for the above example is shown on Figure 2/2.
+
+
+
+
Figure 2/2. The detour tree of Figure 2/1.
+
+
+
+Let us consider a slightly more complicated case with three 2-nets and
+two crossings (Figure 2/3).
+
+
+
+
Figure 2/3.
+a. Input: three 2-nets, N1, N2 and N3 are crossing at #1 and #2.
+Yellow lines are the initial two-nets, grey lines are final choices, blue lines
+are alternative choices. Steps b. and c. shows the search
+progress of a possible resolution.
+
+
+
+First step, b. tries an N1-N2 CW. This resolves #1. The next step, c.
+tries a N1-N3 CW, which resolves #2. So the final script is:
+
+N1-N2 CW
+N1-N3 CW
+
+
+An alternative solution in c., drawn with blue, is N3-N1 CWW;
+given there is enough space, between N2 and N3, this would also resolve
+#2. This would change the second line of the script from CW to CCW.
+Another alternative to step c. is leaving N1 as is and make a detour
+with N3: N3-N1 CCW. This is a valid solution to the problem and is
+drawn on Figure 2/3. d. and the corresponding script is:
+
+N1-N2 CW
+N3-N1 CCW
+
+
+
+Another alternative in c. would be to do an N3-N1 CW. This is a valid move,
+but introduces a new conflict, marked as #3 on Figure 2/3. e. Since there
+is a conflict, state e. is not a solution. However, with one more detour,
+N2-N3 CCW it can be a solution: Figure 2/3. e, or as a script:
+
+
+N1-N2 CW
+N3-N1 CW
+N2-N3 CCW
+
+
+
+The above part of the state tree is drawn on Figure 2/4.
+
+
+
+
Figure 2/4. The detour tree of Figure 2/3.
+
+
+
+(Note: the tree can grow deeper than the number of crossings, since an operation
+can introduce one or more new crossings.)
+
+The above example showed three different
+valid solutions (and omitted a lot more, including using a second layer).
+These solutions differ in cost, which is normally a function of total wire
+length and number of vias. If the goal is to find the board state for the
+least-cost solution, it is very likely that all possible solutions would need
+to be rendered. That is not feasible as the search space explodes
+with the number of two-nets growing.
+
+However, if it is enough to find a relatively good valid solution, it is
+possible consider only a part of the tree. For example it is possible to
+implement an A* search on the state tree using the following considerations:
+
+ - the target, when the search stops, is the first time the number of conflicts is zero
+
- the cost function combines total wire length and number of vias of a board state
+
- heuristics is the a function of the number and severity of conflicts of a board state
+
+
+Furthermore there are ways to reduce tree size early on:
+
+ - if a conflict arises between a two-net and a non-movable object, the state is invalid
+
- when considering a new state, if a two-net introduces a new conflict with another
+ two-net which it already had a conflict with in any parent state,
+ check if the same object in the other two-net is affected as in the
+ parent state; if so, this is likely an oscillation (TODO:
+ draw an ex_ for this and link it from here!); this state is invalid
+ and should be discarded
+
Index: detour/index.html
===================================================================
--- detour/index.html (revision 883)
+++ detour/index.html (revision 884)
@@ -6,6 +6,6 @@
- 1. Introduction
-
- 2. Detour search (topology aspect)
+
- 2. Detour search (the topological aspect)
- 3. Hull path (geometric aspect)