KiCad PCB EDA Suite
autorout.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) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
10  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
11  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
12  *
13  * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
14  *
15  * This program is free software; you can redistribute it and/or
16  * modify it under the terms of the GNU General Public License
17  * as published by the Free Software Foundation; either version 2
18  * of the License, or (at your option) any later version.
19  *
20  * This program is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with this program; if not, you may find one here:
27  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
28  * or you may search the http://www.gnu.org website for the version 2 license,
29  * or you may write to the Free Software Foundation, Inc.,
30  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
31  */
32 
33 #include <fctsys.h>
34 #include <class_drawpanel.h>
35 #include <wxPcbStruct.h>
36 #include <gr_basic.h>
37 #include <msgpanel.h>
38 
39 #include <pcbnew.h>
40 #include <cell.h>
41 #include <zones.h>
42 
43 #include <class_board.h>
44 #include <class_module.h>
45 #include <class_track.h>
46 #include <convert_to_biu.h>
47 
48 #include <autorout.h>
49 
50 
51 MATRIX_ROUTING_HEAD RoutingMatrix; // routing matrix (grid) to route 2-sided boards
52 
53 /* init board, route traces*/
54 void PCB_EDIT_FRAME::Autoroute( wxDC* DC, int mode )
55 {
56  int start, stop;
57  MODULE* Module = NULL;
58  D_PAD* Pad = NULL;
59  int autoroute_net_code = -1;
60  wxString msg;
61 
62  if( GetBoard()->GetCopperLayerCount() > 1 )
63  {
66  }
67  else
68  {
70  }
71 
72  switch( mode )
73  {
74  case ROUTE_NET:
75  if( GetScreen()->GetCurItem() )
76  {
77  switch( GetScreen()->GetCurItem()->Type() )
78  {
79  case PCB_PAD_T:
80  Pad = (D_PAD*) GetScreen()->GetCurItem();
81  autoroute_net_code = Pad->GetNetCode();
82  break;
83 
84  default:
85  break;
86  }
87  }
88  if( autoroute_net_code <= 0 )
89  {
90  wxMessageBox( _( "Net not selected" ) ); return;
91  }
92  break;
93 
94  case ROUTE_MODULE:
95  Module = (MODULE*) GetScreen()->GetCurItem();
96  if( (Module == NULL) || (Module->Type() != PCB_MODULE_T) )
97  {
98  wxMessageBox( _( "Footprint not selected" ) );
99  return;
100  }
101  break;
102 
103  case ROUTE_PAD:
104  Pad = (D_PAD*) GetScreen()->GetCurItem();
105 
106  if( (Pad == NULL) || (Pad->Type() != PCB_PAD_T) )
107  {
108  wxMessageBox( _( "Pad not selected" ) );
109  return;
110  }
111 
112  break;
113  }
114 
115  if( (GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK ) == 0 )
116  Compile_Ratsnest( DC, true );
117 
118  /* Set the flag on the ratsnest to CH_ROUTE_REQ. */
119  for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ )
120  {
121  RATSNEST_ITEM* ptmp = &GetBoard()->m_FullRatsnest[ii];
122  ptmp->m_Status &= ~CH_ROUTE_REQ;
123 
124  switch( mode )
125  {
126  case ROUTE_ALL:
127  ptmp->m_Status |= CH_ROUTE_REQ;
128  break;
129 
130  case ROUTE_NET:
131  if( autoroute_net_code == ptmp->GetNet() )
132  ptmp->m_Status |= CH_ROUTE_REQ;
133  break;
134 
135  case ROUTE_MODULE:
136  {
137  D_PAD* pt_pad = (D_PAD*) Module->Pads();
138  for( ; pt_pad != NULL; pt_pad = pt_pad->Next() )
139  {
140  if( ptmp->m_PadStart == pt_pad )
141  ptmp->m_Status |= CH_ROUTE_REQ;
142 
143  if( ptmp->m_PadEnd == pt_pad )
144  ptmp->m_Status |= CH_ROUTE_REQ;
145  }
146 
147  break;
148  }
149 
150  case ROUTE_PAD:
151  if( ( ptmp->m_PadStart == Pad ) || ( ptmp->m_PadEnd == Pad ) )
152  ptmp->m_Status |= CH_ROUTE_REQ;
153 
154  break;
155  }
156  }
157 
158  start = time( NULL );
159 
160  /* Calculation of no fixed routing to 5 mils and more. */
161  RoutingMatrix.m_GridRouting = (int)GetScreen()->GetGridSize().x;
162 
163  if( RoutingMatrix.m_GridRouting < (5*IU_PER_MILS) )
164  RoutingMatrix.m_GridRouting = 5*IU_PER_MILS;
165 
166 
167  /* Calculated ncol and nrow, matrix size for routing. */
168  RoutingMatrix.ComputeMatrixSize( GetBoard() );
169  AUTOROUTER_CONTEXT ctx = { this, GetBoard(), RoutingMatrix.m_BrdBox, DC };
170 
171  m_messagePanel->EraseMsgBox();
172 
173  /* Map the board */
174  RoutingMatrix.m_RoutingLayersCount = 1;
175 
177  RoutingMatrix.m_RoutingLayersCount = 2;
178 
179  if( RoutingMatrix.InitRoutingMatrix() < 0 )
180  {
181  wxMessageBox( _( "No memory for autorouting" ) );
182  RoutingMatrix.UnInitRoutingMatrix(); /* Free memory. */
183  return;
184  }
185 
186  SetStatusText( _( "Place Cells" ) );
187  PlaceCells( GetBoard(), -1, FORCE_PADS );
188 
189  /* Construction of the track list for router. */
190  RoutingMatrix.m_RouteCount = Build_Work( GetBoard() );
191 
192  // DisplayRoutingMatrix( m_canvas, DC );
193 
194  Solve( ctx, RoutingMatrix.m_RoutingLayersCount );
195 
196  /* Free memory. */
197  FreeQueue();
198  InitWork(); /* Free memory for the list of router connections. */
199  RoutingMatrix.UnInitRoutingMatrix();
200  stop = time( NULL ) - start;
201  msg.Printf( wxT( "time = %d second%s" ), stop, ( stop == 1 ) ? wxT( "" ) : wxT( "s" ) );
202  SetStatusText( msg );
203 }
204 
205 
206 /* Clear the flag CH_NOROUTABLE which is set to 1 by Solve(),
207  * when a track was not routed.
208  * (If this flag is 1 the corresponding track it is not rerouted)
209  */
211 {
212  if( ( GetBoard()->m_Status_Pcb & LISTE_RATSNEST_ITEM_OK )== 0 )
213  Compile_Ratsnest( DC, true );
214 
215  for( unsigned ii = 0; ii < GetBoard()->GetRatsnestsCount(); ii++ )
216  {
217  GetBoard()->m_FullRatsnest[ii].m_Status &= ~CH_UNROUTABLE;
218  }
219 }
220 
221 
222 /* DEBUG Function: displays the routing matrix */
223 void DisplayRoutingMatrix( EDA_DRAW_PANEL* panel, wxDC* DC )
224 {
225  int dcell0;
226  COLOR4D color;
227 
228  int maxi = 600 / RoutingMatrix.m_Ncols;
229  maxi = ( maxi * 3 ) / 4;
230 
231  if( !maxi )
232  maxi = 1;
233 
234  GRSetDrawMode( DC, GR_COPY );
235 
236  for( int col = 0; col < RoutingMatrix.m_Ncols; col++ )
237  {
238  for( int row = 0; row < RoutingMatrix.m_Nrows; row++ )
239  {
240  color = COLOR4D::BLACK;
241  dcell0 = RoutingMatrix.GetCell( row, col, BOTTOM );
242 
243  if( dcell0 & HOLE )
244  color = COLOR4D( GREEN );
245 
246 #if 0
247  int dcell1 = 0;
248 
249  if( RoutingMatrix.m_RoutingLayersCount )
250  dcell1 = GetCell( row, col, TOP );
251 
252  if( dcell1 & HOLE )
253  color = COLOR4D( RED );
254 
255  dcell0 |= dcell1;
256 #endif
257  if( ( color == COLOR4D::BLACK ) && ( dcell0 & VIA_IMPOSSIBLE ) )
258  color = COLOR4D( BLUE );
259 
260  if( dcell0 & CELL_is_EDGE )
261  color = COLOR4D( YELLOW );
262  else if( dcell0 & CELL_is_ZONE )
263  color = COLOR4D( YELLOW );
264 
265  #define DRAW_OFFSET_X -20
266  #define DRAW_OFFSET_Y 20
267 // if( color )
268  {
269  for( int i = 0; i < maxi; i++ )
270  for( int j = 0; j < maxi; j++ )
271  GRPutPixel( panel->GetClipBox(), DC,
272  ( col * maxi ) + i + DRAW_OFFSET_X,
273  ( row * maxi ) + j + DRAW_OFFSET_Y, color );
274 
275  }
276  }
277  }
278 }
Definition: colors.h:57
void DisplayRoutingMatrix(EDA_DRAW_PANEL *panel, wxDC *DC)
Definition: autorout.cpp:223
KICAD_T Type() const
Function Type()
Definition: base_struct.h:225
#define VIA_IMPOSSIBLE
Definition: cell.h:48
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:68
#define DRAW_OFFSET_X
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:69
int InitRoutingMatrix()
Function InitBoard initializes the data structures.
void PlaceCells(BOARD *Pcb, int net_code, int flag=0)
Function PlaceCells Initialize the matrix routing by setting obstacles for each occupied cell a cell ...
void GRSetDrawMode(wxDC *DC, GR_DRAWMODE draw_mode)
Definition: gr_basic.cpp:296
#define CH_UNROUTABLE
Definition: class_netinfo.h:58
#define CELL_is_EDGE
Definition: cell.h:42
Class BOARD to handle a board.
#define DRAW_OFFSET_Y
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:160
BOARD * GetBoard() const
class D_PAD, a pad in a footprint
Definition: typeinfo.h:90
Functions relatives to tracks, vias and segments used to fill zones.
#define TOP
Definition: autorout.h:49
class MATRIX_ROUTING_HEAD handle the matrix routing that describes the actual board ...
Definition: autorout.h:104
class MODULE, a footprint
Definition: typeinfo.h:89
BOARD_ITEM * GetCurItem() const
Function GetCurItem returns the currently selected BOARD_ITEM, overriding BASE_SCREEN::GetCurItem().
PCB_LAYER_ID m_Route_Layer_BOTTOM
EDA_RECT * GetClipBox()
int Build_Work(BOARD *Pcb)
Definition: colors.h:60
#define FORCE_PADS
Definition: autorout.h:71
void Reset_Noroutable(wxDC *DC)
Definition: autorout.cpp:210
void Autoroute(wxDC *DC, int mode)
Definition: autorout.cpp:54
void Compile_Ratsnest(wxDC *aDC, bool aDisplayStatus)
Function Compile_Ratsnest Create the entire board ratsnest.
Definition: ratsnest.cpp:56
void GRPutPixel(EDA_RECT *ClipBox, wxDC *DC, int x, int y, COLOR4D Color)
Definition: gr_basic.cpp:345
BOARD * GetBoard()
int GetNetCode() const
Function GetNetCode.
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
bool ComputeMatrixSize(BOARD *aPcb, bool aUseBoardEdgesOnly=false)
Function ComputeMatrixSize calculates the number of rows and columns of dimensions of aPcb for routin...
Definition: colors.h:58
PCB_SCREEN * GetScreen() const override
Function GetScreen returns a pointer to a BASE_SCREEN or one of its derivatives.
void FreeQueue()
Definition: queue.cpp:60
#define BOTTOM
Definition: autorout.h:50
Module description (excepted pads)
Definition: colors.h:45
Message panel definition file.
BOARD_ITEM * GetCurItem()
EDA_RECT m_BrdBox
Definition: autorout.h:115
Definition: colors.h:68
#define HOLE
Definition: cell.h:40
void InitWork()
Definition: work.cpp:68
#define CH_ROUTE_REQ
Definition: class_netinfo.h:59
PCB_LAYER_ID m_Route_Layer_TOP
#define CELL_is_ZONE
Definition: cell.h:44
Class COLOR4D is the color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:39