KiCad PCB EDA Suite
dist.cpp
Go to the documentation of this file.
1 
6 /*
7  * This program source code file is part of KiCad, a free EDA CAD application.
8  *
9  * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
10  *
11  * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
12  *
13  * This program is free software; you can redistribute it and/or
14  * modify it under the terms of the GNU General Public License
15  * as published by the Free Software Foundation; either version 2
16  * of the License, or (at your option) any later version.
17  *
18  * This program is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License
24  * along with this program; if not, you may find one here:
25  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
26  * or you may search the http://www.gnu.org website for the version 2 license,
27  * or you may write to the Free Software Foundation, Inc.,
28  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
29  */
30 #include <autorout.h>
31 #include <cell.h>
32 
33 
34 /* The tables of distances and keep out areas are established on the basis of a
35  * 50 units grid size (the pitch between the cells is 50 units).
36  * The actual distance could be computed by a scaling factor, but this is
37  * not needed, we can use only reduced values
38  */
39 
40  /* calculate approximate distance (manhattan distance)
41  */
42 int MATRIX_ROUTING_HEAD::GetApxDist( int r1, int c1, int r2, int c2 )
43 {
44  int d1, d2; /* row and column deltas */
45 
46  if( ( d1 = r1 - r2 ) < 0 ) /* get absolute row delta */
47  d1 = -d1;
48 
49  if( ( d2 = c1 - c2 ) < 0 ) /* get absolute column delta */
50  d2 = -d2;
51 
52  return ( d1+d2 ) * 50;
53 }
54 
55 
56 /* distance to go thru a cell (en mils) */
57 static const int dist[10][10] =
58 { /* OT=Otherside, OR=Origin (source) cell */
59 /*..........N, NE, E, SE, S, SW, W, NW, OT, OR */
60 /* N */ { 50, 60, 35, 60, 99, 60, 35, 60, 12, 12 },
61 /* NE */ { 60, 71, 60, 71, 60, 99, 60, 71, 23, 23 },
62 /* E */ { 35, 60, 50, 60, 35, 60, 99, 60, 12, 12 },
63 /* SE */ { 60, 71, 60, 71, 60, 71, 60, 99, 23, 23 },
64 /* S */ { 99, 60, 35, 60, 50, 60, 35, 60, 12, 12 },
65 /* SW */ { 60, 99, 60, 71, 60, 71, 60, 71, 23, 23 },
66 /* W */ { 35, 60, 99, 60, 35, 60, 50, 60, 12, 12 },
67 /* NW */ { 60, 71, 60, 99, 60, 71, 60, 71, 23, 23 },
68 
69 /* OT */ { 12, 23, 12, 23, 12, 23, 12, 23, 99, 99 },
70 /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }
71 };
72 
73 /* penalty for extraneous holes and corners, scaled by sharpness of turn */
74 static const int penalty[10][10] =
75 { /* OT=Otherside, OR=Origin (source) cell */
76 /*......... N, NE, E, SE, S, SW, W, NW, OT, OR */
77 /* N */ { 0, 5, 10, 15, 20, 15, 10, 5, 50, 0 },
78 /* NE */ { 5, 0, 5, 10, 15, 20, 15, 10, 50, 0 },
79 /* E */ { 10, 5, 0, 5, 10, 15, 20, 15, 50, 0 },
80 /* SE */ { 15, 10, 5, 0, 5, 10, 15, 20, 50, 0 },
81 /* S */ { 20, 15, 10, 5, 0, 5, 10, 15, 50, 0 },
82 /* SW */ { 15, 20, 15, 10, 5, 0, 5, 10, 50, 0 },
83 /* W */ { 10, 15, 20, 15, 10, 5, 0, 5, 50, 0 },
84 /* NW */ { 5, 10, 15, 20, 15, 10, 5, 0, 50, 0 },
85 
86 /* OT */ { 50, 50, 50, 50, 50, 50, 50, 50, 100, 0 },
87 /* OR */ { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
88 };
89 
90 /* penalty pour directions preferencielles */
91 #define PN 20
92 static const int dir_penalty_TOP[10][10] =
93 {
94 /* OT=Otherside, OR=Origin (source) cell */
95 /*......... N, NE, E, SE, S, SW, W, NW, OT, OR */
96 /* N */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
97 /* NE */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
98 /* E */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
99 /* SE */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
100 /* S */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
101 /* SW */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
102 /* W */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
103 /* NW */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
104 
105 /* OT */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 },
106 /* OR */ { PN, 0, 0, 0, PN, 0, 0, 0, 0, 0 }
107 };
108 
109 static int dir_penalty_BOTTOM[10][10] =
110 {
111 /* OT=Otherside, OR=Origin (source) cell */
112 /*......... N, NE, E, SE, S, SW, W, NW, OT, OR */
113 /* N */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
114 /* NE */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
115 /* E */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
116 /* SE */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
117 /* S */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
118 /* SW */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
119 /* W */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
120 /* NW */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
121 
122 /* OT */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 },
123 /* OR */ { 0, 0, PN, 0, 0, 0, PN, 0, 0, 0 }
124 };
125 
126 /*
127 ** x is the direction to enter the cell of interest.
128 ** y is the direction to exit the cell of interest.
129 ** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
130 **
131 ** return the distance of the trace through the cell of interest.
132 ** the calculation is driven by the tables above.
133 */
134 
135 
136 /* calculate distance (with penalty) of a trace through a cell
137 */
138 int MATRIX_ROUTING_HEAD::CalcDist(int x,int y,int z ,int side )
139 {
140  int adjust, ldist;
141 
142  adjust = 0; /* set if hole is encountered */
143 
144  if( x == EMPTY )
145  x = 10;
146 
147  if( y == EMPTY )
148  {
149  y = 10;
150  }
151  else if( y == FROM_OTHERSIDE )
152  {
153  if( z == EMPTY )
154  z = 10;
155 
156  adjust = penalty[x-1][z-1];
157  }
158 
159  ldist = dist[x-1][y-1] + penalty[x-1][y-1] + adjust;
160 
161  if( m_RouteCount > 1 )
162  {
163  if( side == BOTTOM )
164  ldist += dir_penalty_TOP[x-1][y-1];
165 
166  if( side == TOP )
167  ldist += dir_penalty_BOTTOM[x-1][y-1];
168  }
169 
170  return ldist * 10;
171 }
#define FROM_OTHERSIDE
Definition: cell.h:112
int CalcDist(int x, int y, int z, int side)
Definition: dist.cpp:138
static const int dist[10][10]
Definition: dist.cpp:57
static const int penalty[10][10]
Definition: dist.cpp:74
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
#define TOP
Definition: autorout.h:49
#define PN
Definition: dist.cpp:91
static const int dir_penalty_TOP[10][10]
Definition: dist.cpp:92
#define EMPTY
Definition: autorout.h:51
static int dir_penalty_BOTTOM[10][10]
Definition: dist.cpp:109
#define BOTTOM
Definition: autorout.h:50