KiCad PCB EDA Suite
routing_matrix.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
33 #include <fctsys.h>
34 #include <common.h>
35 
36 #include <pcbnew.h>
37 #include <cell.h>
38 #include <autorout.h>
39 
40 #include <class_eda_rect.h>
41 #include <class_board.h>
42 #include <class_module.h>
43 #include <class_track.h>
44 #include <class_drawsegment.h>
45 #include <class_edge_mod.h>
46 #include <class_pcb_text.h>
47 
48 
50 {
51  m_BoardSide[0] = m_BoardSide[1] = NULL;
52  m_DistSide[0] = m_DistSide[1] = NULL;
53  m_DirSide[0] = m_DirSide[1] = NULL;
54  m_opWriteCell = NULL;
55  m_InitMatrixDone = false;
56  m_Nrows = 0;
57  m_Ncols = 0;
58  m_MemSize = 0;
60  m_GridRouting = 0;
61  m_RouteCount = 0;
62 }
63 
64 
66 {
67 }
68 
69 
70 bool MATRIX_ROUTING_HEAD::ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly )
71 {
72  // The boundary box must have its start point on routing grid:
73  m_BrdBox = aUseBoardEdgesOnly ? aPcb->GetBoardEdgesBoundingBox() : aPcb->GetBoundingBox();
74 
77 
78  // The boundary box must have its end point on routing grid:
79  wxPoint end = m_BrdBox.GetEnd();
80 
81  end.x -= end.x % m_GridRouting;
82  end.x += m_GridRouting;
83 
84  end.y -= end.y % m_GridRouting;
85  end.y += m_GridRouting;
86 
87  m_BrdBox.SetEnd( end );
88 
91 
92  // gives a small margin
93  m_Ncols += 1;
94  m_Nrows += 1;
95 
96  return true;
97 }
98 
99 
101 {
102  if( m_Nrows <= 0 || m_Ncols <= 0 )
103  return 0;
104 
105  m_InitMatrixDone = true; // we have been called
106 
107  // give a small margin for memory allocation:
108  int ii = (RoutingMatrix.m_Nrows + 1) * (RoutingMatrix.m_Ncols + 1);
109 
110  int side = BOTTOM;
111  for( int jj = 0; jj < m_RoutingLayersCount; jj++ ) // m_RoutingLayersCount = 1 or 2
112  {
113  m_BoardSide[side] = NULL;
114  m_DistSide[side] = NULL;
115  m_DirSide[side] = NULL;
116 
117  // allocate matrix & initialize everything to empty
118  m_BoardSide[side] = (MATRIX_CELL*) operator new( ii * sizeof(MATRIX_CELL) );
119  memset( m_BoardSide[side], 0, ii * sizeof(MATRIX_CELL) );
120 
121  if( m_BoardSide[side] == NULL )
122  return -1;
123 
124  // allocate Distances
125  m_DistSide[side] = (DIST_CELL*) operator new( ii * sizeof(DIST_CELL) );
126  memset( m_DistSide[side], 0, ii * sizeof(DIST_CELL) );
127 
128  if( m_DistSide[side] == NULL )
129  return -1;
130 
131  // allocate Dir (chars)
132  m_DirSide[side] = (char*) operator new( ii );
133  memset( m_DirSide[side], 0, ii );
134 
135  if( m_DirSide[side] == NULL )
136  return -1;
137 
138  side = TOP;
139  }
140 
141  m_MemSize = m_RouteCount * ii * ( sizeof(MATRIX_CELL)
142  + sizeof(DIST_CELL) + sizeof(char) );
143 
144  return m_MemSize;
145 }
146 
147 
149 {
150  int ii;
151 
152  m_InitMatrixDone = false;
153 
154  for( ii = 0; ii < MAX_ROUTING_LAYERS_COUNT; ii++ )
155  {
156  // de-allocate Dir matrix
157  if( m_DirSide[ii] )
158  {
159  delete m_DirSide[ii];
160  m_DirSide[ii] = NULL;
161  }
162 
163  // de-allocate Distances matrix
164  if( m_DistSide[ii] )
165  {
166  delete m_DistSide[ii];
167  m_DistSide[ii] = NULL;
168  }
169 
170  // de-allocate cells matrix
171  if( m_BoardSide[ii] )
172  {
173  delete m_BoardSide[ii];
174  m_BoardSide[ii] = NULL;
175  }
176  }
177 
178  m_Nrows = m_Ncols = 0;
179 }
180 
181 
196 void PlaceCells( BOARD* aPcb, int net_code, int flag )
197 {
198  int ux0 = 0, uy0 = 0, ux1, uy1, dx, dy;
199  int marge, via_marge;
200  LSET layerMask;
201 
202  // use the default NETCLASS?
203  NETCLASSPTR nc = aPcb->GetDesignSettings().GetDefault();
204 
205  int trackWidth = nc->GetTrackWidth();
206  int clearance = nc->GetClearance();
207  int viaSize = nc->GetViaDiameter();
208 
209  marge = clearance + (trackWidth / 2);
210  via_marge = clearance + (viaSize / 2);
211 
212  // Place PADS on matrix routing:
213  for( unsigned i = 0; i < aPcb->GetPadCount(); ++i )
214  {
215  D_PAD* pad = aPcb->GetPad( i );
216 
217  if( net_code != pad->GetNetCode() || (flag & FORCE_PADS) )
218  {
219  ::PlacePad( pad, HOLE, marge, WRITE_CELL );
220  }
221 
222  ::PlacePad( pad, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
223  }
224 
225  // Place outlines of modules on matrix routing, if they are on a copper layer
226  // or on the edge layer
227 
228  for( MODULE* module = aPcb->m_Modules; module; module = module->Next() )
229  {
230  for( BOARD_ITEM* item = module->GraphicalItems(); item; item = item->Next() )
231  {
232  switch( item->Type() )
233  {
234  case PCB_MODULE_EDGE_T:
235  {
236  EDGE_MODULE* edge = (EDGE_MODULE*) item;
237  EDGE_MODULE tmpEdge( *edge );
238 
239  if( tmpEdge.GetLayer() == Edge_Cuts )
240  tmpEdge.SetLayer( UNDEFINED_LAYER );
241 
242  TraceSegmentPcb( &tmpEdge, HOLE, marge, WRITE_CELL );
243  TraceSegmentPcb( &tmpEdge, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
244  }
245  break;
246 
247  default:
248  break;
249  }
250  }
251  }
252 
253  // Place board outlines and texts on copper layers:
254  for( BOARD_ITEM* item = aPcb->m_Drawings; item; item = item->Next() )
255  {
256  switch( item->Type() )
257  {
258  case PCB_LINE_T:
259  {
260  DRAWSEGMENT* DrawSegm;
261 
262  int type_cell = HOLE;
263  DrawSegm = (DRAWSEGMENT*) item;
264  DRAWSEGMENT tmpSegm( DrawSegm );
265 
266  if( DrawSegm->GetLayer() == Edge_Cuts )
267  {
268  tmpSegm.SetLayer( UNDEFINED_LAYER );
269  type_cell |= CELL_is_EDGE;
270  }
271 
272  TraceSegmentPcb( &tmpSegm, type_cell, marge, WRITE_CELL );
273  }
274  break;
275 
276  case PCB_TEXT_T:
277  {
278  TEXTE_PCB* PtText = (TEXTE_PCB*) item;
279 
280  if( PtText->GetText().Length() == 0 )
281  break;
282 
283  EDA_RECT textbox = PtText->GetTextBox( -1 );
284  ux0 = textbox.GetX();
285  uy0 = textbox.GetY();
286  dx = textbox.GetWidth();
287  dy = textbox.GetHeight();
288 
289  // Put bounding box (rectangle) on matrix
290  dx /= 2;
291  dy /= 2;
292 
293  ux1 = ux0 + dx;
294  uy1 = uy0 + dy;
295 
296  ux0 -= dx;
297  uy0 -= dy;
298 
299  layerMask = LSET( PtText->GetLayer() );
300 
301  TraceFilledRectangle( ux0 - marge, uy0 - marge, ux1 + marge,
302  uy1 + marge, PtText->GetTextAngle(),
303  layerMask, HOLE, WRITE_CELL );
304 
305  TraceFilledRectangle( ux0 - via_marge, uy0 - via_marge,
306  ux1 + via_marge, uy1 + via_marge,
307  PtText->GetTextAngle(),
308  layerMask, VIA_IMPOSSIBLE, WRITE_OR_CELL );
309  }
310  break;
311 
312  default:
313  break;
314  }
315  }
316 
317  // Put tracks and vias on matrix
318  for( TRACK* track = aPcb->m_Track; track; track = track->Next() )
319  {
320  if( net_code == track->GetNetCode() )
321  continue;
322 
323  TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
324  TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
325  }
326 }
327 
328 
329 int Build_Work( BOARD* Pcb )
330 {
331  RATSNEST_ITEM* pt_rats;
332  D_PAD* pt_pad;
333  int r1, r2, c1, c2, current_net_code;
334  RATSNEST_ITEM* pt_ch;
335  int demi_pas = RoutingMatrix.m_GridRouting / 2;
336  wxString msg;
337 
338  InitWork(); // clear work list
339  int cellCount = 0;
340 
341  for( unsigned ii = 0; ii < Pcb->GetRatsnestsCount(); ii++ )
342  {
343  pt_rats = &Pcb->m_FullRatsnest[ii];
344 
345  /* We consider here only ratsnest that are active ( obviously not yet routed)
346  * and routables (that are not yet attempt to be routed and fail
347  */
348  if( (pt_rats->m_Status & CH_ACTIF) == 0 )
349  continue;
350 
351  if( pt_rats->m_Status & CH_UNROUTABLE )
352  continue;
353 
354  if( (pt_rats->m_Status & CH_ROUTE_REQ) == 0 )
355  continue;
356 
357  pt_pad = pt_rats->m_PadStart;
358 
359  current_net_code = pt_pad->GetNetCode();
360  pt_ch = pt_rats;
361 
362  r1 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY() + demi_pas )
364 
365  if( r1 < 0 || r1 >= RoutingMatrix.m_Nrows )
366  {
367  msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r1,
368  pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
369  wxMessageBox( msg );
370  return 0;
371  }
372 
373  c1 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas ) / RoutingMatrix.m_GridRouting;
374 
375  if( c1 < 0 || c1 >= RoutingMatrix.m_Ncols )
376  {
377  msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c1,
378  pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
379  wxMessageBox( msg );
380  return 0;
381  }
382 
383  pt_pad = pt_rats->m_PadEnd;
384 
385  r2 = ( pt_pad->GetPosition().y - RoutingMatrix.m_BrdBox.GetY()
386  + demi_pas ) / RoutingMatrix.m_GridRouting;
387 
388  if( r2 < 0 || r2 >= RoutingMatrix.m_Nrows )
389  {
390  msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r2,
391  pt_pad->GetPosition().y, RoutingMatrix.m_BrdBox.GetY() );
392  wxMessageBox( msg );
393  return 0;
394  }
395 
396  c2 = ( pt_pad->GetPosition().x - RoutingMatrix.m_BrdBox.GetX() + demi_pas )
398 
399  if( c2 < 0 || c2 >= RoutingMatrix.m_Ncols )
400  {
401  msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c2,
402  pt_pad->GetPosition().x, RoutingMatrix.m_BrdBox.GetX() );
403  wxMessageBox( msg );
404  return 0;
405  }
406 
407  SetWork( r1, c1, current_net_code, r2, c2, pt_ch, 0 );
408  cellCount++;
409  }
410 
411  SortWork();
412  return cellCount;
413 }
414 
415 // Initialize m_opWriteCell member to make the aLogicOp
417 {
418  switch( aLogicOp )
419  {
420  default:
421  case WRITE_CELL:
423  break;
424 
425  case WRITE_OR_CELL:
427  break;
428 
429  case WRITE_XOR_CELL:
431  break;
432 
433  case WRITE_AND_CELL:
435  break;
436 
437  case WRITE_ADD_CELL:
439  break;
440  }
441 }
442 
443 
444 /* return the value stored in a cell
445  */
446 MATRIX_CELL MATRIX_ROUTING_HEAD::GetCell( int aRow, int aCol, int aSide )
447 {
448  MATRIX_CELL* p;
449 
450  p = RoutingMatrix.m_BoardSide[aSide];
451  return p[aRow * m_Ncols + aCol];
452 }
453 
454 
455 /* basic cell operation : WRITE operation
456  */
457 void MATRIX_ROUTING_HEAD::SetCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
458 {
459  MATRIX_CELL* p;
460 
461  p = RoutingMatrix.m_BoardSide[aSide];
462  p[aRow * m_Ncols + aCol] = x;
463 }
464 
465 
466 /* basic cell operation : OR operation
467  */
468 void MATRIX_ROUTING_HEAD::OrCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
469 {
470  MATRIX_CELL* p;
471 
472  p = RoutingMatrix.m_BoardSide[aSide];
473  p[aRow * m_Ncols + aCol] |= x;
474 }
475 
476 
477 /* basic cell operation : XOR operation
478  */
479 void MATRIX_ROUTING_HEAD::XorCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
480 {
481  MATRIX_CELL* p;
482 
483  p = RoutingMatrix.m_BoardSide[aSide];
484  p[aRow * m_Ncols + aCol] ^= x;
485 }
486 
487 
488 /* basic cell operation : AND operation
489  */
490 void MATRIX_ROUTING_HEAD::AndCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
491 {
492  MATRIX_CELL* p;
493 
494  p = RoutingMatrix.m_BoardSide[aSide];
495  p[aRow * m_Ncols + aCol] &= x;
496 }
497 
498 
499 /* basic cell operation : ADD operation
500  */
501 void MATRIX_ROUTING_HEAD::AddCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
502 {
503  MATRIX_CELL* p;
504 
505  p = RoutingMatrix.m_BoardSide[aSide];
506  p[aRow * m_Ncols + aCol] += x;
507 }
508 
509 
510 // fetch distance cell
511 DIST_CELL MATRIX_ROUTING_HEAD::GetDist( int aRow, int aCol, int aSide ) // fetch distance cell
512 {
513  DIST_CELL* p;
514 
515  p = RoutingMatrix.m_DistSide[aSide];
516  return p[aRow * m_Ncols + aCol];
517 }
518 
519 
520 // store distance cell
521 void MATRIX_ROUTING_HEAD::SetDist( int aRow, int aCol, int aSide, DIST_CELL x )
522 {
523  DIST_CELL* p;
524 
525  p = RoutingMatrix.m_DistSide[aSide];
526  p[aRow * m_Ncols + aCol] = x;
527 }
528 
529 
530 // fetch direction cell
531 int MATRIX_ROUTING_HEAD::GetDir( int aRow, int aCol, int aSide )
532 {
533  DIR_CELL* p;
534 
535  p = RoutingMatrix.m_DirSide[aSide];
536  return (int) (p[aRow * m_Ncols + aCol]);
537 }
538 
539 
540 // store direction cell
541 void MATRIX_ROUTING_HEAD::SetDir( int aRow, int aCol, int aSide, int x )
542 {
543  DIR_CELL* p;
544 
545  p = RoutingMatrix.m_DirSide[aSide];
546  p[aRow * m_Ncols + aCol] = (char) x;
547 }
void AddCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
void TraceFilledRectangle(int ux0, int uy0, int ux1, int uy1, LSET side, int color, int op_logic)
Definition: graphpcb.cpp:478
#define VIA_IMPOSSIBLE
Definition: cell.h:48
DIR_CELL * m_DirSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:110
const EDA_RECT GetBoundingBox() const override
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes...
Definition: class_board.h:827
int Build_Work(BOARD *Pcb)
int InitRoutingMatrix()
Function InitBoard initializes the data structures.
NETCLASSPTR GetDefault() const
Function GetDefault.
TEXTE_PCB class definition.
#define CH_UNROUTABLE
Definition: class_netinfo.h:58
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
int SetWork(int, int, int, int, int, RATSNEST_ITEM *, int)
Definition: work.cpp:81
#define CELL_is_EDGE
Definition: cell.h:42
Class BOARD to handle a board.
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
virtual void SetLayer(LAYER_ID aLayer)
Function SetLayer sets the layer this item is on.
MODULE * Next() const
Definition: class_module.h:99
int GetHeight() const
class TEXTE_PCB, text on a layer
Definition: typeinfo.h:104
int GetDir(int aRow, int aCol, int aSide)
#define WRITE_CELL
Definition: autorout.h:190
LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
#define WRITE_XOR_CELL
Definition: autorout.h:192
class EDGE_MODULE, a footprint edge
Definition: typeinfo.h:106
#define WRITE_AND_CELL
Definition: autorout.h:193
double GetTextAngle() const
Definition: eda_text.h:164
Functions relatives to tracks, vias and segments used to fill zones.
void SortWork()
Definition: work.cpp:135
#define TOP
Definition: autorout.h:49
const EDA_RECT GetBoardEdgesBoundingBox() const
Function GetBoardEdgesBoundingBox Returns the board bounding box calculated using exclusively the boa...
Definition: class_board.h:839
BOARD_ITEM * Next() const
#define CH_ACTIF
Definition: class_netinfo.h:60
std::vector< RATSNEST_ITEM > m_FullRatsnest
Ratsnest list for the BOARD.
Definition: class_board.h:248
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
Class LSET is a set of LAYER_IDs.
unsigned GetRatsnestsCount() const
Function GetNumRatsnests.
Definition: class_board.h:704
EDA_RECT GetTextBox(int aLine=-1, int aThickness=-1, bool aInvertY=false) const
Function GetTextBox useful in multiline texts to calculate the full text or a line area (for zones fi...
Definition: eda_text.cpp:115
void XorCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
MATRIX_CELL * m_BoardSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:107
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
void SetEnd(int x, int y)
const wxString & GetText() const
Function GetText returns the string associated with the text object.
Definition: eda_text.h:130
DIST_CELL * m_DistSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:108
void PlaceCells(BOARD *aPcb, int net_code, int flag)
Function PlaceCells Initialize the matrix routing by setting obstacles for each occupied cell a cell ...
DIST_CELL GetDist(int aRow, int aCol, int aSide)
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings.
Definition: class_board.h:530
void(MATRIX_ROUTING_HEAD::* m_opWriteCell)(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: autorout.h:122
DLIST< BOARD_ITEM > m_Drawings
Definition: class_board.h:242
void SetX(int val)
unsigned char MATRIX_CELL
Definition: autorout.h:81
void SetDir(int aRow, int aCol, int aSide, int aDir)
#define FORCE_PADS
Definition: autorout.h:71
#define MAX_ROUTING_LAYERS_COUNT
Definition: autorout.h:69
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
void SetY(int val)
const wxPoint GetEnd() const
D_PAD * m_PadStart
Definition: class_netinfo.h:75
int GetNetCode() const
Function GetNetCode.
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
void SetCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
bool ComputeMatrixSize(BOARD *aPcb, bool aUseBoardEdgesOnly=false)
Function ComputeMatrixSize calculates the number of rows and columns of dimensions of aPcb for routin...
void OrCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
TRACK * Next() const
Definition: class_track.h:97
void SetDist(int aRow, int aCol, int aSide, DIST_CELL)
Class to handle a graphic segment.
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:166
DLIST< MODULE > m_Modules
Definition: class_board.h:243
Class EDA_RECT handles the component boundary box.
int GetX() const
The common library.
int GetWidth() const
void AndCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
char DIR_CELL
Definition: autorout.h:83
int GetY() const
void PlacePad(D_PAD *pt_pad, int type, int marge, int op_logic)
Definition: graphpcb.cpp:87
#define WRITE_ADD_CELL
Definition: autorout.h:194
#define BOTTOM
Definition: autorout.h:50
void TraceSegmentPcb(TRACK *pt_segm, int type, int marge, int op_logic)
Definition: graphpcb.cpp:290
Class RATSNEST_ITEM describes a ratsnest line: a straight line connecting 2 pads. ...
Definition: class_netinfo.h:68
DLIST< TRACK > m_Track
Definition: class_board.h:244
Module description (excepted pads)
EDGE_MODULE class definition.
class DRAWSEGMENT, a segment not on copper layers
Definition: typeinfo.h:103
EDA_RECT m_BrdBox
Definition: autorout.h:115
#define HOLE
Definition: cell.h:40
void SetCellOperation(int aLogicOp)
void InitWork()
Definition: work.cpp:68
#define CH_ROUTE_REQ
Definition: class_netinfo.h:59
textbox
Definition: base_struct.cpp:61
#define WRITE_OR_CELL
Definition: autorout.h:191
int DIST_CELL
Definition: autorout.h:82