KiCad PCB EDA Suite
autorout.h
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) 2012 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2012 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 
32 #ifndef AUTOROUT_H
33 #define AUTOROUT_H
34 
35 
36 #include <base_struct.h>
37 #include <class_eda_rect.h>
39 
40 
41 class BOARD;
42 class DRAWSEGMENT;
43 class TRACK;
44 class D_PAD;
45 class RATSNEST_ITEM;
46 class PCB_EDIT_FRAME;
47 
48 
49 #define TOP 0
50 #define BOTTOM 1
51 #define EMPTY 0
52 #define ILLEGAL -1
53 
54 
55 /* Autorouter commands. */
57 {
62 
67 };
68 
69 #define MAX_ROUTING_LAYERS_COUNT 2
70 
71 #define FORCE_PADS 1 /* Force placement of pads for any Netcode */
72 
73 /* search statistics */
74 extern int OpenNodes; /* total number of nodes opened */
75 extern int ClosNodes; /* total number of nodes closed */
76 extern int MoveNodes; /* total number of nodes moved */
77 extern int MaxNodes; /* maximum number of nodes opened at one time */
78 
79 
80 /* Structures useful to the generation of board as bitmap. */
81 typedef unsigned char MATRIX_CELL;
82 typedef int DIST_CELL;
83 typedef char DIR_CELL;
84 
86 {
89 
92 
94  const EDA_RECT bbox;
95 
97  wxDC* dc;
98 };
99 
105 {
106 public:
107  MATRIX_CELL* m_BoardSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides
108  DIST_CELL* m_DistSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides:
109  // distance to cells
110  DIR_CELL* m_DirSide[MAX_ROUTING_LAYERS_COUNT]; // the image map of 2 board sides:
111  // pointers back to source
113  int m_RoutingLayersCount; // Number of layers for autorouting (0 or 1)
114  int m_GridRouting; // Size of grid for autoplace/autoroute
115  EDA_RECT m_BrdBox; // Actual board bounding box
116  int m_Nrows, m_Ncols; // Matrix size
117  int m_MemSize; // Memory requirement, just for statistics
118  int m_RouteCount; // Number of routes
119 
120 private:
121  // a pointer to the current selected cell operation
122  void (MATRIX_ROUTING_HEAD::* m_opWriteCell)( int aRow, int aCol,
123  int aSide, MATRIX_CELL aCell);
124 
125 public:
128 
129  void WriteCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell)
130  {
131  (*this.*m_opWriteCell)( aRow, aCol, aSide, aCell );
132  }
133 
140  {
141  return m_BrdBox.GetOrigin();
142  }
143 
152  bool ComputeMatrixSize( BOARD* aPcb, bool aUseBoardEdgesOnly = false );
153 
160  int InitRoutingMatrix();
161 
162  void UnInitRoutingMatrix();
163 
164  // Initialize WriteCell to make the aLogicOp
165  void SetCellOperation( int aLogicOp );
166 
167  // functions to read/write one cell ( point on grid routing matrix:
168  MATRIX_CELL GetCell( int aRow, int aCol, int aSide);
169  void SetCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
170  void OrCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
171  void XorCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
172  void AndCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
173  void AddCell( int aRow, int aCol, int aSide, MATRIX_CELL aCell);
174  DIST_CELL GetDist( int aRow, int aCol, int aSide );
175  void SetDist( int aRow, int aCol, int aSide, DIST_CELL );
176  int GetDir( int aRow, int aCol, int aSide );
177  void SetDir( int aRow, int aCol, int aSide, int aDir);
178 
179  // calculate distance (with penalty) of a trace through a cell
180  int CalcDist(int x,int y,int z ,int side );
181 
182  // calculate approximate distance (manhattan distance)
183  int GetApxDist( int r1, int c1, int r2, int c2 );
184 };
185 
186 extern MATRIX_ROUTING_HEAD RoutingMatrix; /* 2-sided board */
187 
188 
189 /* Constants used to trace the cells on the BOARD */
190 #define WRITE_CELL 0
191 #define WRITE_OR_CELL 1
192 #define WRITE_XOR_CELL 2
193 #define WRITE_AND_CELL 3
194 #define WRITE_ADD_CELL 4
195 
196 // Functions:
197 
198 /* Initialize a color value, the cells included in the board edge of the
199  * pad surface by pt_pad, with the margin reserved for isolation and the
200  * half width of the runway
201  * Parameters:
202  * Pt_pad: pointer to the description of the pad
203  * color: mask write in cells
204  * margin: add a value to the radius or half the score pad
205  * op_logic: type of writing in the cell (WRITE, OR)
206  */
207 void PlacePad( D_PAD* pt_pad, int type, int marge, int op_logic );
208 
209 /* Draws a segment of track on the board. */
210 void TraceSegmentPcb( TRACK* pt_segm, int type, int marge, int op_logic );
211 void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int type, int marge, int op_logic );
212 
213 /* Uses the color value of all cells included in the board
214  * coord of the rectangle ux0, uy0 (top right corner)
215  * a ux1, uy1 (lower left corner) (coord PCB)
216  * the rectangle is horizontal (or vertical)
217  * masque_layer = mask layers;
218  * op_logic = WRITE_CELL, WRITE_OR_CELL, WRITE_XOR_CELL, WRITE_AND_CELL
219  */
220 void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
221  LSET side, int color, int op_logic);
222 
223 
224 /* Same as above, but the rectangle is inclined angle angle. */
225 void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
226  double angle, LSET masque_layer,
227  int color, int op_logic );
228 
229 /* QUEUE.CPP */
230 void FreeQueue();
231 void InitQueue();
232 void GetQueue( int *, int *, int *, int *, int * );
233 bool SetQueue( int, int, int, int, int, int, int );
234 void ReSetQueue( int, int, int, int, int, int, int );
235 
236 /* WORK.CPP */
237 void InitWork();
238 void ReInitWork();
239 int SetWork( int, int, int , int, int, RATSNEST_ITEM *, int );
240 void GetWork( int *, int *, int *, int *, int *, RATSNEST_ITEM ** );
241 void SortWork(); /* order the work items; shortest first */
242 
243 /* routing_matrix.cpp */
244 int Build_Work( BOARD * Pcb );
245 void PlaceCells( BOARD * Pcb, int net_code, int flag = 0 );
246 
247 
248 #endif // AUTOROUT_H
BOARD * board
Board to be routed
Definition: autorout.h:91
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
DIR_CELL * m_DirSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:110
int CalcDist(int x, int y, int z, int side)
Definition: dist.cpp:138
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 ...
int OpenNodes
Definition: solve.cpp:85
int SetWork(int, int, int, int, int, RATSNEST_ITEM *, int)
Definition: work.cpp:81
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
AUTOPLACEROUTE_OPTIONS
Definition: autorout.h:56
int GetDir(int aRow, int aCol, int aSide)
void ReSetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:185
int MoveNodes
Definition: solve.cpp:87
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
void SortWork()
Definition: work.cpp:135
void InitQueue()
Definition: queue.cpp:75
void GetQueue(int *, int *, int *, int *, int *)
Definition: queue.cpp:91
class MATRIX_ROUTING_HEAD handle the matrix routing that describes the actual board ...
Definition: autorout.h:104
const wxPoint & GetOrigin() const
Class LSET is a set of LAYER_IDs.
void XorCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
MATRIX_CELL * m_BoardSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:107
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: autorout.h:139
DIST_CELL * m_DistSide[MAX_ROUTING_LAYERS_COUNT]
Definition: autorout.h:108
DIST_CELL GetDist(int aRow, int aCol, int aSide)
void(MATRIX_ROUTING_HEAD::* m_opWriteCell)(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: autorout.h:122
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
int Build_Work(BOARD *Pcb)
unsigned char MATRIX_CELL
Definition: autorout.h:81
void SetDir(int aRow, int aCol, int aSide, int aDir)
#define MAX_ROUTING_LAYERS_COUNT
Definition: autorout.h:69
wxDC * dc
Drawing context
Definition: autorout.h:97
int ClosNodes
Definition: solve.cpp:86
const EDA_RECT bbox
Cached board bounding box
Definition: autorout.h:94
PCB_EDIT_FRAME * pcbframe
Parent frame
Definition: autorout.h:88
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 GetWork(int *, int *, int *, int *, int *, RATSNEST_ITEM **)
Definition: work.cpp:102
void OrCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
void SetDist(int aRow, int aCol, int aSide, DIST_CELL)
Board layer functions and definitions.
void ReInitWork()
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:166
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
Class EDA_RECT handles the component boundary box.
void AndCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
char DIR_CELL
Definition: autorout.h:83
void PlacePad(D_PAD *pt_pad, int type, int marge, int op_logic)
Definition: graphpcb.cpp:87
void FreeQueue()
Definition: queue.cpp:60
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
int MaxNodes
Definition: solve.cpp:88
bool SetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:120
Basic classes for most KiCad items.
EDA_RECT m_BrdBox
Definition: autorout.h:115
void SetCellOperation(int aLogicOp)
void InitWork()
Definition: work.cpp:68
int DIST_CELL
Definition: autorout.h:82
void WriteCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: autorout.h:129