KiCad PCB EDA Suite
autorout.h File Reference

Go to the source code of this file.

Classes

struct  AUTOROUTER_CONTEXT
 
class  MATRIX_ROUTING_HEAD
 class MATRIX_ROUTING_HEAD handle the matrix routing that describes the actual board More...
 

Macros

#define TOP   0
 
#define BOTTOM   1
 
#define EMPTY   0
 
#define ILLEGAL   -1
 
#define MAX_ROUTING_LAYERS_COUNT   2
 
#define FORCE_PADS   1 /* Force placement of pads for any Netcode */
 
#define WRITE_CELL   0
 
#define WRITE_OR_CELL   1
 
#define WRITE_XOR_CELL   2
 
#define WRITE_AND_CELL   3
 
#define WRITE_ADD_CELL   4
 

Typedefs

typedef unsigned char MATRIX_CELL
 
typedef int DIST_CELL
 
typedef char DIR_CELL
 

Enumerations

enum  AUTOPLACEROUTE_OPTIONS {
  PLACE_ALL, PLACE_OUT_OF_BOARD, PLACE_INCREMENTAL, PLACE_1_MODULE,
  ROUTE_ALL, ROUTE_NET, ROUTE_MODULE, ROUTE_PAD
}
 

Functions

void PlacePad (D_PAD *pt_pad, int type, int marge, int op_logic)
 
void TraceSegmentPcb (TRACK *pt_segm, int type, int marge, int op_logic)
 
void TraceSegmentPcb (DRAWSEGMENT *pt_segm, int type, int marge, int op_logic)
 
void TraceFilledRectangle (int ux0, int uy0, int ux1, int uy1, LSET side, int color, int op_logic)
 
void TraceFilledRectangle (int ux0, int uy0, int ux1, int uy1, double angle, LSET masque_layer, int color, int op_logic)
 
void FreeQueue ()
 
void InitQueue ()
 
void GetQueue (int *, int *, int *, int *, int *)
 
bool SetQueue (int, int, int, int, int, int, int)
 
void ReSetQueue (int, int, int, int, int, int, int)
 
void InitWork ()
 
void ReInitWork ()
 
int SetWork (int, int, int, int, int, RATSNEST_ITEM *, int)
 
void GetWork (int *, int *, int *, int *, int *, RATSNEST_ITEM **)
 
void SortWork ()
 
int Build_Work (BOARD *Pcb)
 
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 set to HOLE is an obstacle for tracks and vias a cell set to VIA_IMPOSSIBLE is an obstacle for vias only. More...
 

Variables

int OpenNodes
 
int ClosNodes
 
int MoveNodes
 
int MaxNodes
 
MATRIX_ROUTING_HEAD RoutingMatrix
 

Macro Definition Documentation

#define EMPTY   0

Definition at line 51 of file autorout.h.

Referenced by MATRIX_ROUTING_HEAD::CalcDist().

#define FORCE_PADS   1 /* Force placement of pads for any Netcode */

Definition at line 71 of file autorout.h.

Referenced by PlaceCells().

#define ILLEGAL   -1

Definition at line 52 of file autorout.h.

Referenced by Autoroute_One_Track(), GetQueue(), GetWork(), Retrace(), and PCB_EDIT_FRAME::Solve().

#define MAX_ROUTING_LAYERS_COUNT   2

Definition at line 69 of file autorout.h.

Referenced by MATRIX_ROUTING_HEAD::UnInitRoutingMatrix().

#define WRITE_ADD_CELL   4

Definition at line 194 of file autorout.h.

Referenced by MATRIX_ROUTING_HEAD::SetCellOperation().

#define WRITE_AND_CELL   3

Definition at line 193 of file autorout.h.

Referenced by Autoroute_One_Track(), and MATRIX_ROUTING_HEAD::SetCellOperation().

#define WRITE_CELL   0
#define WRITE_OR_CELL   1
#define WRITE_XOR_CELL   2

Definition at line 192 of file autorout.h.

Referenced by MATRIX_ROUTING_HEAD::SetCellOperation().

Typedef Documentation

typedef char DIR_CELL

Definition at line 83 of file autorout.h.

typedef int DIST_CELL

Definition at line 82 of file autorout.h.

typedef unsigned char MATRIX_CELL

Definition at line 81 of file autorout.h.

Enumeration Type Documentation

Enumerator
PLACE_ALL 
PLACE_OUT_OF_BOARD 
PLACE_INCREMENTAL 
PLACE_1_MODULE 
ROUTE_ALL 
ROUTE_NET 
ROUTE_MODULE 
ROUTE_PAD 

Definition at line 56 of file autorout.h.

Function Documentation

int Build_Work ( BOARD Pcb)

Definition at line 329 of file routing_matrix.cpp.

References CH_ACTIF, CH_ROUTE_REQ, CH_UNROUTABLE, BOARD_CONNECTED_ITEM::GetNetCode(), D_PAD::GetPosition(), BOARD::GetRatsnestsCount(), EDA_RECT::GetX(), EDA_RECT::GetY(), InitWork(), MATRIX_ROUTING_HEAD::m_BrdBox, BOARD::m_FullRatsnest, MATRIX_ROUTING_HEAD::m_GridRouting, MATRIX_ROUTING_HEAD::m_Ncols, MATRIX_ROUTING_HEAD::m_Nrows, RATSNEST_ITEM::m_PadEnd, RATSNEST_ITEM::m_PadStart, RATSNEST_ITEM::m_Status, RoutingMatrix, SetWork(), SortWork(), wxPoint::x, and wxPoint::y.

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 }
#define CH_UNROUTABLE
Definition: class_netinfo.h:58
int SetWork(int, int, int, int, int, RATSNEST_ITEM *, int)
Definition: work.cpp:81
void SortWork()
Definition: work.cpp:135
#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
unsigned GetRatsnestsCount() const
Function GetNumRatsnests.
Definition: class_board.h:704
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
D_PAD * m_PadStart
Definition: class_netinfo.h:75
int GetNetCode() const
Function GetNetCode.
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
int GetX() const
int GetY() const
Class RATSNEST_ITEM describes a ratsnest line: a straight line connecting 2 pads. ...
Definition: class_netinfo.h:68
EDA_RECT m_BrdBox
Definition: autorout.h:115
void InitWork()
Definition: work.cpp:68
#define CH_ROUTE_REQ
Definition: class_netinfo.h:59
void FreeQueue ( )

Definition at line 60 of file queue.cpp.

References InitQueue(), and PcbQueue::Next.

61 {
62  struct PcbQueue* p;
63 
64  InitQueue();
65 
66  while( (p = Save) != NULL )
67  {
68  Save = p->Next;
69  delete p;
70  }
71 }
struct PcbQueue * Next
Definition: queue.cpp:45
void InitQueue()
Definition: queue.cpp:75
static struct PcbQueue * Save
Definition: queue.cpp:56
void GetQueue ( int *  ,
int *  ,
int *  ,
int *  ,
int *   
)

Definition at line 91 of file queue.cpp.

References PcbQueue::ApxDist, ClosNodes, PcbQueue::Col, PcbQueue::Dist, ILLEGAL, PcbQueue::Next, qlen, PcbQueue::Row, Save, and PcbQueue::Side.

Referenced by Autoroute_One_Track().

92 {
93  struct PcbQueue* p;
94 
95  if( (p = Head) != NULL ) /* return first item in list */
96  {
97  *r = p->Row; *c = p->Col;
98  *s = p->Side;
99  *d = p->Dist; *a = p->ApxDist;
100 
101  if( (Head = p->Next) == NULL )
102  Tail = NULL;
103 
104  /* put node on free list */
105  p->Next = Save; Save = p;
106  ClosNodes++; qlen--;
107  }
108  else /* empty list */
109  {
110  *r = *c = *s = *d = *a = ILLEGAL;
111  }
112 }
int Dist
Definition: queue.cpp:49
struct PcbQueue * Next
Definition: queue.cpp:45
int Col
Definition: queue.cpp:47
#define ILLEGAL
Definition: autorout.h:52
static struct PcbQueue * Save
Definition: queue.cpp:56
int Row
Definition: queue.cpp:46
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
static struct PcbQueue * Head
Definition: queue.cpp:54
int Side
Definition: queue.cpp:48
static long qlen
Definition: queue.cpp:53
int ApxDist
Definition: queue.cpp:50
void GetWork ( int *  ,
int *  ,
int *  ,
int *  ,
int *  ,
RATSNEST_ITEM **   
)

Definition at line 102 of file work.cpp.

References Current, ILLEGAL, and WorkList.

Referenced by PCB_EDIT_FRAME::Solve().

106 {
107  if( Current < WorkList.size() )
108  {
109  *r1 = WorkList[Current].m_FromRow;
110  *c1 = WorkList[Current].m_FromCol;
111  *n_c = WorkList[Current].m_NetCode;
112  *r2 = WorkList[Current].m_ToRow;
113  *c2 = WorkList[Current].m_ToCol;
114  *pt_ch = WorkList[Current].m_Ratsnest;
115  Current++;
116  }
117  else /* none left */
118  {
119  *r1 = *c1 = *r2 = *c2 = ILLEGAL;
120  *n_c = 0;
121  *pt_ch = NULL;
122  }
123 }
#define ILLEGAL
Definition: autorout.h:52
static unsigned Current
Definition: work.cpp:64
static std::vector< CWORK > WorkList
Definition: work.cpp:63
void InitQueue ( )

Definition at line 75 of file queue.cpp.

References ClosNodes, MaxNodes, MoveNodes, PcbQueue::Next, OpenNodes, qlen, and Save.

Referenced by Autoroute_One_Track(), and FreeQueue().

76 {
77  struct PcbQueue* p;
78 
79  while( (p = Head) != NULL )
80  {
81  Head = p->Next;
82  p->Next = Save; Save = p;
83  }
84 
85  Tail = NULL;
87 }
int OpenNodes
Definition: solve.cpp:85
struct PcbQueue * Next
Definition: queue.cpp:45
int MoveNodes
Definition: solve.cpp:87
static struct PcbQueue * Save
Definition: queue.cpp:56
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
int MaxNodes
Definition: solve.cpp:88
static struct PcbQueue * Head
Definition: queue.cpp:54
static long qlen
Definition: queue.cpp:53
void InitWork ( )

Definition at line 68 of file work.cpp.

References Current, and WorkList.

Referenced by Build_Work().

69 {
70  WorkList.clear();
71  Current = 0;
72 }
static unsigned Current
Definition: work.cpp:64
static std::vector< CWORK > WorkList
Definition: work.cpp:63
void PlaceCells ( BOARD aPcb,
int  net_code,
int  flag 
)

Function PlaceCells Initialize the matrix routing by setting obstacles for each occupied cell a cell set to HOLE is an obstacle for tracks and vias a cell set to VIA_IMPOSSIBLE is an obstacle for vias only.

a cell set to CELL_is_EDGE is a frontier. Tracks and vias having the same net code as net_code are skipped (htey do not are obstacles)

For single-sided Routing 1: BOTTOM side is used, and Route_Layer_BOTTOM = Route_Layer_TOP

If flag == FORCE_PADS: all pads will be put in matrix as obstacles.

Definition at line 196 of file routing_matrix.cpp.

References CELL_is_EDGE, Edge_Cuts, FORCE_PADS, BOARD_DESIGN_SETTINGS::GetDefault(), BOARD::GetDesignSettings(), EDA_RECT::GetHeight(), BOARD_ITEM::GetLayer(), BOARD_CONNECTED_ITEM::GetNetCode(), BOARD::GetPad(), BOARD::GetPadCount(), EDA_TEXT::GetText(), EDA_TEXT::GetTextAngle(), EDA_TEXT::GetTextBox(), EDA_RECT::GetWidth(), EDA_RECT::GetX(), EDA_RECT::GetY(), HOLE, BOARD::m_Drawings, BOARD::m_Modules, BOARD::m_Track, TRACK::Next(), MODULE::Next(), BOARD_ITEM::Next(), PCB_LINE_T, PCB_MODULE_EDGE_T, PCB_TEXT_T, PlacePad(), BOARD_ITEM::SetLayer(), TraceFilledRectangle(), TraceSegmentPcb(), UNDEFINED_LAYER, VIA_IMPOSSIBLE, WRITE_CELL, and WRITE_OR_CELL.

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 }
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
NETCLASSPTR GetDefault() const
Function GetDefault.
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
#define CELL_is_EDGE
Definition: cell.h:42
MODULE * Next() const
Definition: class_module.h:99
int GetHeight() const
class TEXTE_PCB, text on a layer
Definition: typeinfo.h:104
#define WRITE_CELL
Definition: autorout.h:190
class EDGE_MODULE, a footprint edge
Definition: typeinfo.h:106
double GetTextAngle() const
Definition: eda_text.h:164
BOARD_ITEM * Next() const
Class LSET is a set of PCB_LAYER_IDs.
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
const wxString & GetText() const
Function GetText returns the string associated with the text object.
Definition: eda_text.h:130
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings.
Definition: class_board.h:530
DLIST< BOARD_ITEM > m_Drawings
Definition: class_board.h:242
#define FORCE_PADS
Definition: autorout.h:71
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
int GetNetCode() const
Function GetNetCode.
PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
TRACK * Next() const
Definition: class_track.h:98
DLIST< MODULE > m_Modules
Definition: class_board.h:243
Class EDA_RECT handles the component boundary box.
int GetX() const
int GetWidth() const
int GetY() const
void PlacePad(D_PAD *pt_pad, int type, int marge, int op_logic)
Definition: graphpcb.cpp:87
void TraceSegmentPcb(TRACK *pt_segm, int type, int marge, int op_logic)
Definition: graphpcb.cpp:290
DLIST< TRACK > m_Track
Definition: class_board.h:244
class DRAWSEGMENT, a segment not on copper layers
Definition: typeinfo.h:103
#define HOLE
Definition: cell.h:40
textbox
Definition: base_struct.cpp:61
#define WRITE_OR_CELL
Definition: autorout.h:191
void PlacePad ( D_PAD pt_pad,
int  type,
int  marge,
int  op_logic 
)

Definition at line 87 of file graphpcb.cpp.

References abs, color, D_PAD::GetDelta(), D_PAD::GetLayerSet(), D_PAD::GetOrientation(), D_PAD::GetShape(), D_PAD::GetSize(), PAD_SHAPE_CIRCLE, PAD_SHAPE_TRAPEZOID, D_PAD::ShapePos(), TraceFilledCircle(), TraceFilledRectangle(), wxPoint::x, and wxPoint::y.

Referenced by Autoroute_One_Track(), genModuleOnRoutingMatrix(), and PlaceCells().

88 {
89  int dx, dy;
90  wxPoint shape_pos = aPad->ShapePos();
91 
92  dx = aPad->GetSize().x / 2;
93  dx += marge;
94 
95  if( aPad->GetShape() == PAD_SHAPE_CIRCLE )
96  {
97  TraceFilledCircle( shape_pos.x, shape_pos.y, dx,
98  aPad->GetLayerSet(), color, op_logic );
99  return;
100  }
101 
102  dy = aPad->GetSize().y / 2;
103  dy += marge;
104 
105  if( aPad->GetShape() == PAD_SHAPE_TRAPEZOID )
106  {
107  dx += abs( aPad->GetDelta().y ) / 2;
108  dy += abs( aPad->GetDelta().x ) / 2;
109  }
110 
111  // The pad is a rectangle ( horizontal or vertical )
112  if( int( aPad->GetOrientation() ) % 900 == 0 )
113  {
114  // Orientation turned 90 deg.
115  if( aPad->GetOrientation() == 900 || aPad->GetOrientation() == 2700 )
116  {
117  std::swap( dx, dy );
118  }
119 
120  TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
121  shape_pos.x + dx, shape_pos.y + dy,
122  aPad->GetLayerSet(), color, op_logic );
123  }
124  else
125  {
126  TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
127  shape_pos.x + dx, shape_pos.y + dy,
128  aPad->GetOrientation(),
129  aPad->GetLayerSet(), color, op_logic );
130  }
131 }
#define abs(a)
Definition: auxiliary.h:84
void TraceFilledRectangle(int ux0, int uy0, int ux1, int uy1, LSET aLayerMask, int color, int op_logic)
Definition: graphpcb.cpp:478
static void TraceFilledCircle(int cx, int cy, int radius, LSET aLayerMask, int color, int op_logic)
Definition: graphpcb.cpp:142
void ReInitWork ( )
void ReSetQueue ( int  ,
int  ,
int  ,
int  ,
int  ,
int  ,
int   
)

Definition at line 185 of file queue.cpp.

References ClosNodes, MoveNodes, PcbQueue::Next, OpenNodes, qlen, Save, and SetQueue().

Referenced by Autoroute_One_Track().

186 {
187  struct PcbQueue* p, * q;
188 
189  /* first, see if it is already in the list */
190  for( q = NULL, p = Head; p; q = p, p = p->Next )
191  {
192  if( p->Row == r && p->Col == c && p->Side == s )
193  {
194  /* old one to remove */
195  if( q )
196  {
197  if( ( q->Next = p->Next ) == NULL )
198  Tail = q;
199  }
200  else if( ( Head = p->Next ) == NULL )
201  {
202  Tail = NULL;
203  }
204 
205  p->Next = Save;
206  Save = p;
207  OpenNodes--;
208  MoveNodes++;
209  qlen--;
210  break;
211  }
212  }
213 
214  if( !p ) /* not found, it has already been closed once */
215  ClosNodes--; /* we will close it again, but just count once */
216 
217  /* if it was there, it's gone now; insert it at the proper position */
218  bool res = SetQueue( r, c, s, d, a, r2, c2 );
219  (void) res;
220 }
int OpenNodes
Definition: solve.cpp:85
struct PcbQueue * Next
Definition: queue.cpp:45
int MoveNodes
Definition: solve.cpp:87
static struct PcbQueue * Save
Definition: queue.cpp:56
bool SetQueue(int r, int c, int side, int d, int a, int r2, int c2)
Definition: queue.cpp:120
static struct PcbQueue * Tail
Definition: queue.cpp:55
int ClosNodes
Definition: solve.cpp:86
static struct PcbQueue * Head
Definition: queue.cpp:54
static long qlen
Definition: queue.cpp:53
bool SetQueue ( int  ,
int  ,
int  ,
int  ,
int  ,
int  ,
int   
)

Definition at line 120 of file queue.cpp.

References PcbQueue::ApxDist, PcbQueue::Col, PcbQueue::Dist, MaxNodes, PcbQueue::Next, OpenNodes, qlen, PcbQueue::Row, and PcbQueue::Side.

Referenced by Autoroute_One_Track(), and ReSetQueue().

121 {
122  struct PcbQueue* p, * q, * t;
123  int i, j;
124 
125  j = 0; // gcc warning fix
126 
127  if( (p = Save) != NULL ) /* try free list first */
128  {
129  Save = p->Next;
130  }
131  else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL )
132  {
133  return 0;
134  }
135 
136  p->Row = r;
137  p->Col = c;
138  p->Side = side;
139  i = (p->Dist = d) + (p->ApxDist = a);
140  p->Next = NULL;
141 
142  if( (q = Head) != NULL ) /* insert in proper position in list */
143  {
144  if( q->Dist + q->ApxDist > i ) /* insert at head */
145  {
146  p->Next = q; Head = p;
147  }
148  else /* search for proper position */
149  {
150  for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next )
151  ;
152 
153  if( q && i == j && q->Row == r2 && q->Col == c2 )
154  {
155  /* insert after q, which is a goal node */
156  if( ( p->Next = q->Next ) == NULL )
157  Tail = p;
158 
159  q->Next = p;
160  }
161  else /* insert in front of q */
162  {
163  if( ( p->Next = q ) == NULL )
164  Tail = p;
165 
166  t->Next = p;
167  }
168  }
169  }
170  else /* empty search list */
171  {
172  Head = Tail = p;
173  }
174 
175  OpenNodes++;
176 
177  if( ++qlen > MaxNodes )
178  MaxNodes = qlen;
179 
180  return 1;
181 }
int OpenNodes
Definition: solve.cpp:85
int Dist
Definition: queue.cpp:49
struct PcbQueue * Next
Definition: queue.cpp:45
int Col
Definition: queue.cpp:47
static struct PcbQueue * Save
Definition: queue.cpp:56
int Row
Definition: queue.cpp:46
static struct PcbQueue * Tail
Definition: queue.cpp:55
int MaxNodes
Definition: solve.cpp:88
static struct PcbQueue * Head
Definition: queue.cpp:54
int Side
Definition: queue.cpp:48
static long qlen
Definition: queue.cpp:53
int ApxDist
Definition: queue.cpp:50
int SetWork ( int  ,
int  ,
int  ,
int  ,
int  ,
RATSNEST_ITEM ,
int   
)

Definition at line 81 of file work.cpp.

References CWORK::CalculateCost(), MATRIX_ROUTING_HEAD::GetApxDist(), CWORK::m_ApxDist, CWORK::m_FromCol, CWORK::m_FromRow, CWORK::m_NetCode, CWORK::m_Priority, CWORK::m_Ratsnest, CWORK::m_ToCol, CWORK::m_ToRow, RoutingMatrix, and WorkList.

Referenced by Build_Work().

85 {
86  CWORK item;
87  item.m_FromRow = r1;
88  item.m_FromCol = c1;
89  item.m_NetCode = n_c;
90  item.m_ToRow = r2;
91  item.m_ToCol = c2;
92  item.m_Ratsnest = pt_ch;
93  item.m_ApxDist = RoutingMatrix.GetApxDist( r1, c1, r2, c2 );
94  item.CalculateCost();
95  item.m_Priority = pri;
96  WorkList.push_back( item );
97  return 1;
98 }
int m_FromRow
Definition: work.cpp:47
int m_ApxDist
Definition: work.cpp:53
int m_ToRow
Definition: work.cpp:49
int m_ToCol
Definition: work.cpp:50
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
int m_FromCol
Definition: work.cpp:48
Definition: work.cpp:44
int m_Priority
Definition: work.cpp:55
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
static std::vector< CWORK > WorkList
Definition: work.cpp:63
void CalculateCost()
Definition: work.cpp:145
RATSNEST_ITEM * m_Ratsnest
Definition: work.cpp:51
int m_NetCode
Definition: work.cpp:52
void SortWork ( )

Definition at line 135 of file work.cpp.

References sort_by_cost(), and WorkList.

Referenced by Build_Work().

136 {
137  sort( WorkList.begin(), WorkList.end(), sort_by_cost );
138 }
bool sort_by_cost(const CWORK &ref, const CWORK &item)
Definition: work.cpp:127
static std::vector< CWORK > WorkList
Definition: work.cpp:63
void TraceFilledRectangle ( int  ux0,
int  uy0,
int  ux1,
int  uy1,
LSET  side,
int  color,
int  op_logic 
)

Definition at line 478 of file graphpcb.cpp.

References BOTTOM, g_Route_Layer_BOTTOM, g_Route_Layer_TOP, MATRIX_ROUTING_HEAD::GetBrdCoordOrigin(), MATRIX_ROUTING_HEAD::m_GridRouting, MATRIX_ROUTING_HEAD::m_Ncols, MATRIX_ROUTING_HEAD::m_Nrows, MATRIX_ROUTING_HEAD::m_RoutingLayersCount, RoutingMatrix, MATRIX_ROUTING_HEAD::SetCellOperation(), TOP, trace, MATRIX_ROUTING_HEAD::WriteCell(), wxPoint::x, and wxPoint::y.

Referenced by genModuleOnRoutingMatrix(), PlaceCells(), and PlacePad().

480 {
481  int row, col;
482  int row_min, row_max, col_min, col_max;
483  int trace = 0;
484 
485  if( aLayerMask[g_Route_Layer_BOTTOM] )
486  trace = 1; // Trace on BOTTOM
487 
488  if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount > 1 )
489  trace |= 2; // Trace on TOP
490 
491  if( trace == 0 )
492  return;
493 
494  RoutingMatrix.SetCellOperation( op_logic );
495 
500 
501  // Calculating limits coord cells belonging to the rectangle.
502  row_max = uy1 / RoutingMatrix.m_GridRouting;
503  col_max = ux1 / RoutingMatrix.m_GridRouting;
504  row_min = uy0 / RoutingMatrix.m_GridRouting;
505 
506  if( uy0 > row_min * RoutingMatrix.m_GridRouting )
507  row_min++;
508 
509  col_min = ux0 / RoutingMatrix.m_GridRouting;
510 
511  if( ux0 > col_min * RoutingMatrix.m_GridRouting )
512  col_min++;
513 
514  if( row_min < 0 )
515  row_min = 0;
516 
517  if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
518  row_max = RoutingMatrix.m_Nrows - 1;
519 
520  if( col_min < 0 )
521  col_min = 0;
522 
523  if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
524  col_max = RoutingMatrix.m_Ncols - 1;
525 
526  for( row = row_min; row <= row_max; row++ )
527  {
528  for( col = col_min; col <= col_max; col++ )
529  {
530  if( trace & 1 )
531  RoutingMatrix.WriteCell( row, col, BOTTOM, color );
532 
533  if( trace & 2 )
534  RoutingMatrix.WriteCell( row, col, TOP, color );
535  }
536  }
537 }
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
long trace
Definition: solve.cpp:232
#define TOP
Definition: autorout.h:49
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: autorout.h:139
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
#define BOTTOM
Definition: autorout.h:50
void SetCellOperation(int aLogicOp)
void WriteCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: autorout.h:129
void TraceFilledRectangle ( int  ux0,
int  uy0,
int  ux1,
int  uy1,
double  angle,
LSET  masque_layer,
int  color,
int  op_logic 
)

Definition at line 540 of file graphpcb.cpp.

References BOTTOM, Distance(), g_Route_Layer_BOTTOM, g_Route_Layer_TOP, MATRIX_ROUTING_HEAD::GetBrdCoordOrigin(), KiROUND(), MATRIX_ROUTING_HEAD::m_GridRouting, MATRIX_ROUTING_HEAD::m_Ncols, MATRIX_ROUTING_HEAD::m_Nrows, MATRIX_ROUTING_HEAD::m_RoutingLayersCount, RotatePoint(), RoutingMatrix, MATRIX_ROUTING_HEAD::SetCellOperation(), TOP, trace, MATRIX_ROUTING_HEAD::WriteCell(), wxPoint::x, and wxPoint::y.

542 {
543  int row, col;
544  int cx, cy; // Center of rectangle
545  int radius; // Radius of the circle
546  int row_min, row_max, col_min, col_max;
547  int rotrow, rotcol;
548  int trace = 0;
549 
550  if( aLayerMask[g_Route_Layer_BOTTOM] )
551  trace = 1; // Trace on BOTTOM
552 
553  if( aLayerMask[g_Route_Layer_TOP] )
554  {
556  trace |= 2; // Trace on TOP
557  }
558 
559  if( trace == 0 )
560  return;
561 
562  RoutingMatrix.SetCellOperation( op_logic );
563 
568 
569  cx = (ux0 + ux1) / 2;
570  cy = (uy0 + uy1) / 2;
571  radius = KiROUND( Distance( ux0, uy0, cx, cy ) );
572 
573  // Calculating coordinate limits belonging to the rectangle.
574  row_max = ( cy + radius ) / RoutingMatrix.m_GridRouting;
575  col_max = ( cx + radius ) / RoutingMatrix.m_GridRouting;
576  row_min = ( cy - radius ) / RoutingMatrix.m_GridRouting;
577 
578  if( uy0 > row_min * RoutingMatrix.m_GridRouting )
579  row_min++;
580 
581  col_min = ( cx - radius ) / RoutingMatrix.m_GridRouting;
582 
583  if( ux0 > col_min * RoutingMatrix.m_GridRouting )
584  col_min++;
585 
586  if( row_min < 0 )
587  row_min = 0;
588 
589  if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
590  row_max = RoutingMatrix.m_Nrows - 1;
591 
592  if( col_min < 0 )
593  col_min = 0;
594 
595  if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
596  col_max = RoutingMatrix.m_Ncols - 1;
597 
598  for( row = row_min; row <= row_max; row++ )
599  {
600  for( col = col_min; col <= col_max; col++ )
601  {
602  rotrow = row * RoutingMatrix.m_GridRouting;
603  rotcol = col * RoutingMatrix.m_GridRouting;
604  RotatePoint( &rotcol, &rotrow, cx, cy, -angle );
605 
606  if( rotrow <= uy0 )
607  continue;
608 
609  if( rotrow >= uy1 )
610  continue;
611 
612  if( rotcol <= ux0 )
613  continue;
614 
615  if( rotcol >= ux1 )
616  continue;
617 
618  if( trace & 1 )
619  RoutingMatrix.WriteCell( row, col, BOTTOM, color );
620 
621  if( trace & 2 )
622  RoutingMatrix.WriteCell( row, col, TOP, color );
623  }
624  }
625 }
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
long trace
Definition: solve.cpp:232
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:317
#define TOP
Definition: autorout.h:49
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: autorout.h:139
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#define BOTTOM
Definition: autorout.h:50
double Distance(double x1, double y1, double x2, double y2)
void SetCellOperation(int aLogicOp)
void WriteCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: autorout.h:129
void TraceSegmentPcb ( TRACK pt_segm,
int  type,
int  marge,
int  op_logic 
)

Definition at line 290 of file graphpcb.cpp.

References color, DrawSegmentQcq(), g_Route_Layer_BOTTOM, g_Route_Layer_TOP, MATRIX_ROUTING_HEAD::GetBrdCoordOrigin(), TRACK::GetEnd(), BOARD_ITEM::GetLayer(), TRACK::GetStart(), TRACK::GetWidth(), BOARD_ITEM::IsOnLayer(), PCB_VIA_T, RoutingMatrix, TraceFilledCircle(), EDA_ITEM::Type(), UNDEFINED_LAYER, VIA_IMPOSSIBLE, wxPoint::x, and wxPoint::y.

Referenced by AddNewTrace(), genPlacementRoutingMatrix(), and PlaceCells().

291 {
292  int half_width = ( aTrack->GetWidth() / 2 ) + marge;
293 
294  // Test if VIA (filled circle need to be drawn)
295  if( aTrack->Type() == PCB_VIA_T )
296  {
297  LSET layer_mask;
298 
299  if( aTrack->IsOnLayer( g_Route_Layer_BOTTOM ) )
300  layer_mask.set( g_Route_Layer_BOTTOM );
301 
302  if( aTrack->IsOnLayer( g_Route_Layer_TOP ) )
303  {
304  if( !layer_mask.any() )
305  layer_mask = LSET( g_Route_Layer_TOP );
306  else
307  layer_mask.set();
308  }
309 
310  if( color == VIA_IMPOSSIBLE )
311  layer_mask.set();
312 
313  if( layer_mask.any() )
314  TraceFilledCircle( aTrack->GetStart().x, aTrack->GetStart().y,
315  half_width, layer_mask, color, op_logic );
316  }
317  else
318  {
319  // Calculate the bounding rectangle of the segment
320  int ux0 = aTrack->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
321  int uy0 = aTrack->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
322  int ux1 = aTrack->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
323  int uy1 = aTrack->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;
324 
325  // Ordinary track
326  PCB_LAYER_ID layer = aTrack->GetLayer();
327 
328  if( color == VIA_IMPOSSIBLE )
329  layer = UNDEFINED_LAYER;
330 
331  DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
332  }
333 }
#define VIA_IMPOSSIBLE
Definition: cell.h:48
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
PCB_LAYER_ID
A quick note on layer IDs:
Class LSET is a set of PCB_LAYER_IDs.
static void DrawSegmentQcq(int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, int color, int op_logic)
Definition: graphpcb.cpp:632
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: autorout.h:139
static void TraceFilledCircle(int cx, int cy, int radius, LSET aLayerMask, int color, int op_logic)
Definition: graphpcb.cpp:142
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
void TraceSegmentPcb ( DRAWSEGMENT pt_segm,
int  type,
int  marge,
int  op_logic 
)

Definition at line 257 of file graphpcb.cpp.

References color, DrawSegmentQcq(), DRAWSEGMENT::GetAngle(), MATRIX_ROUTING_HEAD::GetBrdCoordOrigin(), DRAWSEGMENT::GetEnd(), BOARD_ITEM::GetLayer(), DRAWSEGMENT::GetShape(), DRAWSEGMENT::GetStart(), DRAWSEGMENT::GetWidth(), RoutingMatrix, S_ARC, S_CIRCLE, TraceArc(), TraceCircle(), UNDEFINED_LAYER, VIA_IMPOSSIBLE, wxPoint::x, and wxPoint::y.

258 {
259  int half_width = ( pt_segm->GetWidth() / 2 ) + marge;
260 
261  // Calculate the bounding rectangle of the segment (if H, V or Via)
262  int ux0 = pt_segm->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
263  int uy0 = pt_segm->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
264  int ux1 = pt_segm->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
265  int uy1 = pt_segm->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;
266 
267  LAYER_NUM layer = pt_segm->GetLayer();
268 
269  if( color == VIA_IMPOSSIBLE )
270  layer = UNDEFINED_LAYER;
271 
272  switch( pt_segm->GetShape() )
273  {
274  // The segment is here a straight line or a circle or an arc.:
275  case S_CIRCLE:
276  TraceCircle( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
277  break;
278 
279  case S_ARC:
280  TraceArc( ux0, uy0, ux1, uy1, pt_segm->GetAngle(), half_width, layer, color, op_logic );
281  break;
282 
283  // The segment is here a line segment.
284  default:
285  DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
286  break;
287  }
288 }
#define VIA_IMPOSSIBLE
Definition: cell.h:48
void TraceArc(int ux0, int uy0, int ux1, int uy1, double ArcAngle, int lg, LAYER_NUM layer, int color, int op_logic)
Definition: graphpcb.cpp:802
STROKE_T GetShape() const
const wxPoint & GetEnd() const
Function GetEnd returns the ending point of the graphic.
static void DrawSegmentQcq(int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, int color, int op_logic)
Definition: graphpcb.cpp:632
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: autorout.h:139
Arcs (with rounded ends)
int LAYER_NUM
Type LAYER_NUM can be replaced with int and removed.
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
double GetAngle() const
int GetWidth() const
const wxPoint & GetStart() const
Function GetStart returns the starting point of the graphic.
static void TraceCircle(int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer, int color, int op_logic)
Definition: graphpcb.cpp:758

Variable Documentation

int ClosNodes

Definition at line 86 of file solve.cpp.

Referenced by Autoroute_One_Track(), GetQueue(), InitQueue(), and ReSetQueue().

int MaxNodes

Definition at line 88 of file solve.cpp.

Referenced by InitQueue(), and SetQueue().

int MoveNodes

Definition at line 87 of file solve.cpp.

Referenced by Autoroute_One_Track(), InitQueue(), and ReSetQueue().

int OpenNodes

Definition at line 85 of file solve.cpp.

Referenced by Autoroute_One_Track(), InitQueue(), ReSetQueue(), and SetQueue().