KiCad PCB EDA Suite
solve.cpp File Reference
#include <fctsys.h>
#include <class_drawpanel.h>
#include <confirm.h>
#include <wxPcbStruct.h>
#include <gr_basic.h>
#include <macros.h>
#include <class_board.h>
#include <class_track.h>
#include <pcbnew.h>
#include <protos.h>
#include <autorout.h>
#include <cell.h>

Go to the source code of this file.

Classes

struct  block
 

Macros

#define NOSUCCESS   0
 
#define STOP_FROM_ESC   -1
 
#define ERR_MEMORY   -2
 
#define SUCCESS   1
 
#define TRIVIAL_SUCCESS   2
 
#define BLOCK_NORTHEAST
 
#define BLOCK_SOUTHEAST
 
#define BLOCK_SOUTHWEST
 
#define BLOCK_NORTHWEST
 
#define BLOCK_NORTH
 
#define BLOCK_EAST
 
#define BLOCK_SOUTH
 
#define BLOCK_WEST
 
#define COUNT   20000
 

Functions

static int Autoroute_One_Track (AUTOROUTER_CONTEXT &ctx, int two_sides, int row_source, int col_source, int row_target, int col_target, RATSNEST_ITEM *pt_rat)
 
static int Retrace (AUTOROUTER_CONTEXT &ctx, int, int, int, int, int, int net_code)
 
static void OrCell_Trace (AUTOROUTER_CONTEXT &ctx, int col, int row, int side, int orient, int current_net_code)
 
static void AddNewTrace (AUTOROUTER_CONTEXT &ctx)
 

Variables

static int segm_oX
 
static int segm_oY
 
static int segm_fX
 
static int segm_fY
 
static RATSNEST_ITEMpt_cur_ch
 
static int s_Clearance
 
static PICKED_ITEMS_LIST s_ItemsListPicker
 
int OpenNodes
 
int ClosNodes
 
int MoveNodes
 
int MaxNodes
 
static const int delta [8][2]
 
static const int ndir [8]
 
static struct block blocking [8]
 
struct {
   long   trace
 
   int   present
 
selfok2 [8]
 
static long newmask [8]
 
static long bit [8][9]
 

Macro Definition Documentation

#define BLOCK_EAST
Value:
#define SHARP_EtoSE
Definition: cell.h:95
#define BENT_EtoSW
Definition: cell.h:79
#define BENT_WtoSE
Definition: cell.h:84
#define SHARP_NtoNE
Definition: cell.h:93
#define ANGLE_SEtoSW
Definition: cell.h:88
#define ANGLE_NWtoNE
Definition: cell.h:90
#define SHARP_EtoNE
Definition: cell.h:94
#define DIAG_NEtoSW
Definition: cell.h:73
#define BENT_NtoSE
Definition: cell.h:77
#define BENT_StoNE
Definition: cell.h:82
#define CORNER_SOUTHEAST
Definition: cell.h:68
#define SHARP_StoSE
Definition: cell.h:96
#define ANGLE_NEtoSE
Definition: cell.h:87
#define CORNER_NORTHEAST
Definition: cell.h:67
#define BENT_EtoNW
Definition: cell.h:80
#define DIAG_SEtoNW
Definition: cell.h:74
#define LINE_HORIZONTAL
Definition: cell.h:63
#define HOLE
Definition: cell.h:40
#define BENT_WtoNE
Definition: cell.h:83

Definition at line 153 of file solve.cpp.

#define BLOCK_NORTH
Value:
#define ANGLE_SWtoNW
Definition: cell.h:89
#define SHARP_NtoNE
Definition: cell.h:93
#define CORNER_NORTHWEST
Definition: cell.h:70
#define ANGLE_NWtoNE
Definition: cell.h:90
#define SHARP_EtoNE
Definition: cell.h:94
#define BENT_NtoSW
Definition: cell.h:78
#define BENT_StoNW
Definition: cell.h:81
#define DIAG_NEtoSW
Definition: cell.h:73
#define BENT_NtoSE
Definition: cell.h:77
#define BENT_StoNE
Definition: cell.h:82
#define SHARP_WtoNW
Definition: cell.h:99
#define ANGLE_NEtoSE
Definition: cell.h:87
#define LINE_VERTICAL
Definition: cell.h:64
#define CORNER_NORTHEAST
Definition: cell.h:67
#define BENT_EtoNW
Definition: cell.h:80
#define DIAG_SEtoNW
Definition: cell.h:74
#define HOLE
Definition: cell.h:40
#define BENT_WtoNE
Definition: cell.h:83
#define SHARP_NtoNW
Definition: cell.h:100

Definition at line 145 of file solve.cpp.

#define BLOCK_NORTHEAST
Value:
#define SHARP_NtoNE
Definition: cell.h:93
#define ANGLE_NWtoNE
Definition: cell.h:90
#define SHARP_EtoNE
Definition: cell.h:94
#define DIAG_NEtoSW
Definition: cell.h:73
#define BENT_StoNE
Definition: cell.h:82
#define ANGLE_NEtoSE
Definition: cell.h:87
#define HOLE
Definition: cell.h:40
#define BENT_WtoNE
Definition: cell.h:83

Definition at line 133 of file solve.cpp.

#define BLOCK_NORTHWEST
Value:
#define ANGLE_SWtoNW
Definition: cell.h:89
#define ANGLE_NWtoNE
Definition: cell.h:90
#define BENT_StoNW
Definition: cell.h:81
#define SHARP_WtoNW
Definition: cell.h:99
#define BENT_EtoNW
Definition: cell.h:80
#define DIAG_SEtoNW
Definition: cell.h:74
#define HOLE
Definition: cell.h:40
#define SHARP_NtoNW
Definition: cell.h:100

Definition at line 142 of file solve.cpp.

#define BLOCK_SOUTH
Value:
#define SHARP_EtoSE
Definition: cell.h:95
#define BENT_EtoSW
Definition: cell.h:79
#define BENT_WtoSE
Definition: cell.h:84
#define ANGLE_SWtoNW
Definition: cell.h:89
#define ANGLE_SEtoSW
Definition: cell.h:88
#define SHARP_WtoSW
Definition: cell.h:98
#define BENT_NtoSW
Definition: cell.h:78
#define BENT_StoNW
Definition: cell.h:81
#define DIAG_NEtoSW
Definition: cell.h:73
#define BENT_NtoSE
Definition: cell.h:77
#define BENT_StoNE
Definition: cell.h:82
#define CORNER_SOUTHEAST
Definition: cell.h:68
#define CORNER_SOUTHWEST
Definition: cell.h:69
#define SHARP_StoSE
Definition: cell.h:96
#define ANGLE_NEtoSE
Definition: cell.h:87
#define LINE_VERTICAL
Definition: cell.h:64
#define DIAG_SEtoNW
Definition: cell.h:74
#define HOLE
Definition: cell.h:40
#define SHARP_StoSW
Definition: cell.h:97

Definition at line 161 of file solve.cpp.

#define BLOCK_SOUTHEAST
Value:
#define SHARP_EtoSE
Definition: cell.h:95
#define BENT_WtoSE
Definition: cell.h:84
#define ANGLE_SEtoSW
Definition: cell.h:88
#define BENT_NtoSE
Definition: cell.h:77
#define SHARP_StoSE
Definition: cell.h:96
#define ANGLE_NEtoSE
Definition: cell.h:87
#define DIAG_SEtoNW
Definition: cell.h:74
#define HOLE
Definition: cell.h:40

Definition at line 136 of file solve.cpp.

#define BLOCK_SOUTHWEST
Value:
#define BENT_EtoSW
Definition: cell.h:79
#define ANGLE_SWtoNW
Definition: cell.h:89
#define ANGLE_SEtoSW
Definition: cell.h:88
#define SHARP_WtoSW
Definition: cell.h:98
#define BENT_NtoSW
Definition: cell.h:78
#define DIAG_NEtoSW
Definition: cell.h:73
#define HOLE
Definition: cell.h:40
#define SHARP_StoSW
Definition: cell.h:97

Definition at line 139 of file solve.cpp.

#define BLOCK_WEST
Value:
#define BENT_EtoSW
Definition: cell.h:79
#define BENT_WtoSE
Definition: cell.h:84
#define ANGLE_SWtoNW
Definition: cell.h:89
#define ANGLE_SEtoSW
Definition: cell.h:88
#define CORNER_NORTHWEST
Definition: cell.h:70
#define ANGLE_NWtoNE
Definition: cell.h:90
#define SHARP_WtoSW
Definition: cell.h:98
#define BENT_NtoSW
Definition: cell.h:78
#define BENT_StoNW
Definition: cell.h:81
#define DIAG_NEtoSW
Definition: cell.h:73
#define CORNER_SOUTHWEST
Definition: cell.h:69
#define SHARP_WtoNW
Definition: cell.h:99
#define BENT_EtoNW
Definition: cell.h:80
#define DIAG_SEtoNW
Definition: cell.h:74
#define LINE_HORIZONTAL
Definition: cell.h:63
#define HOLE
Definition: cell.h:40
#define BENT_WtoNE
Definition: cell.h:83
#define SHARP_NtoNW
Definition: cell.h:100
#define SHARP_StoSW
Definition: cell.h:97

Definition at line 169 of file solve.cpp.

#define COUNT   20000

Referenced by Autoroute_One_Track().

#define ERR_MEMORY   -2

Definition at line 92 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

#define NOSUCCESS   0

Definition at line 90 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

#define STOP_FROM_ESC   -1

Definition at line 91 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

#define SUCCESS   1

Definition at line 93 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

#define TRIVIAL_SUCCESS   2

Definition at line 94 of file solve.cpp.

Referenced by Autoroute_One_Track().

Function Documentation

static void AddNewTrace ( AUTOROUTER_CONTEXT ctx)
static

Definition at line 1257 of file solve.cpp.

References abs, BEGIN_ONPAD, AUTOROUTER_CONTEXT::board, AUTOROUTER_CONTEXT::dc, DrawTraces(), END_ONPAD, ENDPOINT_END, ENDPOINT_START, g_CurrentTrackList, g_CurrentTrackSegment, g_FirstTrackSegment, EDA_DRAW_FRAME::GetCanvas(), DHEAD::GetCount(), BOARD_DESIGN_SETTINGS::GetCurrentTrackWidth(), BOARD_DESIGN_SETTINGS::GetCurrentViaSize(), PCB_BASE_FRAME::GetDesignSettings(), BOARD::GetPad(), D_PAD::GetPosition(), PCB_BASE_FRAME::GetScreen(), GR_OR, HOLE, DLIST< T >::Insert(), RATSNEST_ITEM::m_PadStart, BOARD::m_Track, AUTOROUTER_CONTEXT::pcbframe, DLIST< T >::PopFront(), DLIST< T >::PushBack(), PICKED_ITEMS_LIST::PushItem(), s_Clearance, TRACK::SetEnd(), BASE_SCREEN::SetModify(), TRACK::SetStart(), PCB_BASE_FRAME::TestNetConnection(), TraceSegmentPcb(), UR_NEW, VIA_IMPOSSIBLE, WRITE_CELL, WRITE_OR_CELL, wxPoint::x, and wxPoint::y.

Referenced by Retrace().

1258 {
1259  if( g_FirstTrackSegment == NULL )
1260  return;
1261 
1262  int dx0, dy0, dx1, dy1;
1263  int marge, via_marge;
1264  EDA_DRAW_PANEL* panel = ctx.pcbframe->GetCanvas();
1265  PCB_SCREEN* screen = ctx.pcbframe->GetScreen();
1266 
1267  marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
1268  via_marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentViaSize() / 2 );
1269 
1270  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1271  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1272 
1273  // Place on center of pad if off grid.
1274  dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
1275  dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1276 
1277  // If aligned, change the origin point.
1278  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1279  {
1281  }
1282  else
1283  {
1284  TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1285 
1286  newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
1287  newTrack->SetStart( g_CurrentTrackSegment->GetEnd() );
1288 
1289  g_CurrentTrackList.PushBack( newTrack );
1290  }
1291 
1293  ENDPOINT_START );
1294 
1295  if( g_FirstTrackSegment->start )
1296  g_FirstTrackSegment->SetState( BEGIN_ONPAD, true );
1297 
1299  ENDPOINT_END );
1300 
1301  if( g_CurrentTrackSegment->end )
1302  g_CurrentTrackSegment->SetState( END_ONPAD, true );
1303 
1304  // Out the new track on the matrix board
1305  for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() )
1306  {
1307  TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
1308  TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
1309  }
1310 
1311  // Insert new segments in real board
1312  int netcode = g_FirstTrackSegment->GetNetCode();
1313  TRACK* firstTrack = g_FirstTrackSegment;
1314  int newCount = g_CurrentTrackList.GetCount();
1315 
1316  // Put entire new current segment list in BOARD
1317  TRACK* track;
1318  TRACK* insertBeforeMe = g_CurrentTrackSegment->GetBestInsertPoint( ctx.board );
1319 
1320  while( ( track = g_CurrentTrackList.PopFront() ) != NULL )
1321  {
1322  ITEM_PICKER picker( track, UR_NEW );
1323  s_ItemsListPicker.PushItem( picker );
1324  ctx.board->m_Track.Insert( track, insertBeforeMe );
1325  }
1326 
1327  DrawTraces( panel, ctx.dc, firstTrack, newCount, GR_OR );
1328 
1329  ctx.pcbframe->TestNetConnection( ctx.dc, netcode );
1330 
1331  screen->SetModify();
1332 }
BOARD * board
Board to be routed
Definition: autorout.h:91
#define g_FirstTrackSegment
first segment created
Definition: pcbnew.h:102
#define g_CurrentTrackSegment
most recently created segment
Definition: pcbnew.h:101
#define VIA_IMPOSSIBLE
Definition: cell.h:48
#define END_ONPAD
Pcbnew: flag set for track segment ending on a pad.
Definition: base_struct.h:133
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:117
DLIST< TRACK > g_CurrentTrackList
Definition: pcbnew.cpp:98
EDA_DRAW_PANEL * GetCanvas()
Definition: draw_frame.h:299
void TestNetConnection(wxDC *aDC, int aNetCode)
Function TestNetConnection tests the connections relative to aNetCode.
Definition: connect.cpp:786
void PushItem(const ITEM_PICKER &aItem)
Function PushItem pushes aItem to the top of the list.
#define WRITE_CELL
Definition: autorout.h:190
#define BEGIN_ONPAD
Pcbnew: flag set for track segment starting on a pad.
Definition: base_struct.h:132
int GetCurrentViaSize() const
Function GetCurrentViaSize.
#define abs(a)
Definition: auxiliary.h:84
void PushBack(T *aNewElement)
Function PushBack puts aNewElement at the end of the list sequence.
Definition: dlist.h:250
static RATSNEST_ITEM * pt_cur_ch
Definition: solve.cpp:80
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
virtual BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings returns the BOARD_DESIGN_SETTINGS for the BOARD owned by this frame...
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
wxDC * dc
Drawing context
Definition: autorout.h:97
D_PAD * m_PadStart
Definition: class_netinfo.h:75
Definition: gr_basic.h:42
static int s_Clearance
Definition: solve.cpp:81
PCB_EDIT_FRAME * pcbframe
Parent frame
Definition: autorout.h:88
PCB_SCREEN * GetScreen() const override
Function GetScreen returns a pointer to a BASE_SCREEN or one of its derivatives.
unsigned GetCount() const
Function GetCount returns the number of elements in the list.
Definition: dlist.h:126
static PICKED_ITEMS_LIST s_ItemsListPicker
Definition: solve.cpp:83
void SetStart(const wxPoint &aStart)
Definition: class_track.h:120
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
void DrawTraces(EDA_DRAW_PANEL *panel, wxDC *DC, TRACK *aStartTrace, int nbsegment, GR_DRAWMODE mode_color)
Function DrawTraces Draws n consecutive track segments in list.
Definition: tr_modif.cpp:48
int GetCurrentTrackWidth() const
Function GetCurrentTrackWidth.
#define HOLE
Definition: cell.h:40
void Insert(T *aNewElement, T *aElementAfterMe)
Function Insert puts aNewElement just in front of aElementAfterMe in the list sequence.
Definition: dlist.h:200
T * PopFront()
Definition: dlist.h:221
#define WRITE_OR_CELL
Definition: autorout.h:191
static int Autoroute_One_Track ( AUTOROUTER_CONTEXT ctx,
int  two_sides,
int  row_source,
int  col_source,
int  row_target,
int  col_target,
RATSNEST_ITEM pt_rat 
)
static

Definition at line 395 of file solve.cpp.

References abs, LSET::AllCuMask(), AUTOROUTER_CONTEXT::bbox, AUTOROUTER_CONTEXT::board, BOTTOM, block::c1, block::c2, MATRIX_ROUTING_HEAD::CalcDist(), ClosNodes, COUNT, CURRENT_PAD, AUTOROUTER_CONTEXT::dc, delta, ERR_MEMORY, FROM_NOWHERE, FROM_OTHERSIDE, g_Route_Layer_BOTTOM, g_Route_Layer_TOP, EDA_DRAW_PANEL::GetAbortRequest(), MATRIX_ROUTING_HEAD::GetApxDist(), EDA_DRAW_FRAME::GetCanvas(), MATRIX_ROUTING_HEAD::GetCell(), EDA_DRAW_PANEL::GetClipBox(), BOARD::GetCopperLayerCount(), BOARD_DESIGN_SETTINGS::GetCurrentTrackWidth(), PCB_BASE_FRAME::GetDesignSettings(), MATRIX_ROUTING_HEAD::GetDir(), MATRIX_ROUTING_HEAD::GetDist(), D_PAD::GetLayerSet(), RATSNEST_ITEM::GetNet(), D_PAD::GetOrientation(), BOARD::GetPad(), BOARD::GetPadCount(), D_PAD::GetPosition(), GetQueue(), D_PAD::GetSize(), EDA_RECT::GetX(), EDA_RECT::GetY(), GR_XOR, GRLine(), GRSetDrawMode(), HOLE, ILLEGAL, InitQueue(), MATRIX_ROUTING_HEAD::m_DirSide, MATRIX_ROUTING_HEAD::m_GridRouting, MATRIX_ROUTING_HEAD::m_Ncols, MATRIX_ROUTING_HEAD::m_Nrows, RATSNEST_ITEM::m_PadEnd, RATSNEST_ITEM::m_PadStart, MoveNodes, ndir, newmask, NOSUCCESS, OpenNodes, AUTOROUTER_CONTEXT::pcbframe, PlacePad(), present, block::r1, block::r2, ReSetQueue(), Retrace(), RoutingMatrix, s_Clearance, segm_fX, segm_fY, segm_oX, segm_oY, selfok2, MATRIX_ROUTING_HEAD::SetDir(), MATRIX_ROUTING_HEAD::SetDist(), SetQueue(), STOP_FROM_ESC, SUCCESS, TOP, trace, TRIVIAL_SUCCESS, WHITE, WRITE_AND_CELL, WRITE_OR_CELL, wxPoint::x, and wxPoint::y.

Referenced by PCB_EDIT_FRAME::Solve().

402 {
403  int r, c, side, d, apx_dist, nr, nc;
404  int result, skip;
405  int i;
406  long curcell, newcell, buddy, lastopen, lastclos, lastmove;
407  int newdist, olddir, _self;
408  int current_net_code;
409  int marge;
410  LSET padLayerMaskStart; // Mask layers belonging to the starting pad.
411  LSET padLayerMaskEnd; // Mask layers belonging to the ending pad.
412 
413  LSET topLayerMask( g_Route_Layer_TOP );
414 
415  LSET bottomLayerMask( g_Route_Layer_BOTTOM );
416 
417  LSET routeLayerMask; // Mask two layers for routing.
418 
419  LSET tab_mask[2]; // Enables the calculation of the mask layer being
420  // tested. (side = TOP or BOTTOM)
421  int start_mask_layer = 0;
422  wxString msg;
423 
424  // @todo this could be a bottle neck
425  LSET all_cu = LSET::AllCuMask( ctx.board->GetCopperLayerCount() );
426 
427  wxBusyCursor dummy_cursor; // Set an hourglass cursor while routing a
428  // track
429 
430  result = NOSUCCESS;
431 
432  marge = s_Clearance + ( ctx.pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
433 
434  // clear direction flags
436 
437  if( two_sides )
438  memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i );
440 
441  lastopen = lastclos = lastmove = 0;
442 
443  // Set tab_masque[side] for final test of routing.
444  if( two_sides )
445  tab_mask[TOP] = topLayerMask;
446  tab_mask[BOTTOM] = bottomLayerMask;
447 
448  // Set active layers mask.
449  routeLayerMask = topLayerMask | bottomLayerMask;
450 
451  pt_cur_ch = pt_rat;
452 
453  current_net_code = pt_rat->GetNet();
454  padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerSet();
455 
456  padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerSet();
457 
458 
459  /* First Test if routing possible ie if the pads are accessible
460  * on the routing layers.
461  */
462  if( ( routeLayerMask & padLayerMaskStart ) == 0 )
463  goto end_of_route;
464 
465  if( ( routeLayerMask & padLayerMaskEnd ) == 0 )
466  goto end_of_route;
467 
468  /* Then test if routing possible ie if the pads are accessible
469  * On the routing grid (1 grid point must be in the pad)
470  */
471  {
472  int cX = ( RoutingMatrix.m_GridRouting * col_source ) + ctx.bbox.GetX();
473  int cY = ( RoutingMatrix.m_GridRouting * row_source ) + ctx.bbox.GetY();
474  int dx = pt_cur_ch->m_PadStart->GetSize().x / 2;
475  int dy = pt_cur_ch->m_PadStart->GetSize().y / 2;
476  int px = pt_cur_ch->m_PadStart->GetPosition().x;
477  int py = pt_cur_ch->m_PadStart->GetPosition().y;
478 
479  if( ( ( int( pt_cur_ch->m_PadStart->GetOrientation() ) / 900 ) & 1 ) != 0 )
480  std::swap( dx, dy );
481 
482  if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
483  goto end_of_route;
484 
485  cX = ( RoutingMatrix.m_GridRouting * col_target ) + ctx.bbox.GetX();
486  cY = ( RoutingMatrix.m_GridRouting * row_target ) + ctx.bbox.GetY();
487  dx = pt_cur_ch->m_PadEnd->GetSize().x / 2;
488  dy = pt_cur_ch->m_PadEnd->GetSize().y / 2;
489  px = pt_cur_ch->m_PadEnd->GetPosition().x;
490  py = pt_cur_ch->m_PadEnd->GetPosition().y;
491 
492  if( ( ( int( pt_cur_ch->m_PadEnd->GetOrientation() ) / 900) & 1 ) != 0 )
493  std::swap( dx, dy );
494 
495  if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
496  goto end_of_route;
497  }
498 
499  // Test the trivial case: direct connection overlay pads.
500  if( row_source == row_target && col_source == col_target &&
501  ( padLayerMaskEnd & padLayerMaskStart & all_cu ).any() )
502  {
503  result = TRIVIAL_SUCCESS;
504  goto end_of_route;
505  }
506 
507  // Placing the bit to remove obstacles on 2 pads to a link.
508  ctx.pcbframe->SetStatusText( wxT( "Gen Cells" ) );
509 
512 
513  // Regenerates the remaining barriers (which may encroach on the
514  // placement bits precedent)
515  i = ctx.board->GetPadCount();
516 
517  for( unsigned ii = 0; ii < ctx.board->GetPadCount(); ii++ )
518  {
519  D_PAD* ptr = ctx.board->GetPad( ii );
520 
521  if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) )
522  {
523  PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL );
524  }
525  }
526 
527  InitQueue(); // initialize the search queue
528  apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target );
529 
530  // Initialize first search.
531  if( two_sides ) // Preferred orientation.
532  {
533  if( abs( row_target - row_source ) > abs( col_target - col_source ) )
534  {
535  if( ( padLayerMaskStart & topLayerMask ).any() )
536  {
537  start_mask_layer = 2;
538 
539  if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
540  row_target, col_target ) == 0 )
541  {
542  return ERR_MEMORY;
543  }
544  }
545 
546  if( ( padLayerMaskStart & bottomLayerMask ).any() )
547  {
548  start_mask_layer |= 1;
549 
550  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
551  row_target, col_target ) == 0 )
552  {
553  return ERR_MEMORY;
554  }
555  }
556  }
557  else
558  {
559  if( ( padLayerMaskStart & bottomLayerMask ).any() )
560  {
561  start_mask_layer = 1;
562 
563  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
564  row_target, col_target ) == 0 )
565  {
566  return ERR_MEMORY;
567  }
568  }
569 
570  if( ( padLayerMaskStart & topLayerMask ).any() )
571  {
572  start_mask_layer |= 2;
573 
574  if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
575  row_target, col_target ) == 0 )
576  {
577  return ERR_MEMORY;
578  }
579  }
580  }
581  }
582  else if( ( padLayerMaskStart & bottomLayerMask ).any() )
583  {
584  start_mask_layer = 1;
585 
586  if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 )
587  {
588  return ERR_MEMORY;
589  }
590  }
591 
592  // search until success or we exhaust all possibilities
593  GetQueue( &r, &c, &side, &d, &apx_dist );
594 
595  for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) )
596  {
597  curcell = RoutingMatrix.GetCell( r, c, side );
598 
599  if( curcell & CURRENT_PAD )
600  curcell &= ~HOLE;
601 
602  if( (r == row_target) && (c == col_target) // success if layer OK
603  && (tab_mask[side] & padLayerMaskEnd).any() )
604  {
605  // Remove link.
606  GRSetDrawMode( ctx.dc, GR_XOR );
607  GRLine( ctx.pcbframe->GetCanvas()->GetClipBox(),
608  ctx.dc,
609  segm_oX, segm_oY,
610  segm_fX, segm_fY,
611  0,
612  WHITE );
613 
614  // Generate trace.
615  if( Retrace( ctx, row_source, col_source,
616  row_target, col_target, side, current_net_code ) )
617  {
618  result = SUCCESS; // Success : Route OK
619  }
620 
621  break; // Routing complete.
622  }
623 
624  if( ctx.pcbframe->GetCanvas()->GetAbortRequest() )
625  {
626  result = STOP_FROM_ESC;
627  break;
628  }
629 
630  // report every COUNT new nodes or so
631  #define COUNT 20000
632 
633  if( ( OpenNodes - lastopen > COUNT )
634  || ( ClosNodes - lastclos > COUNT )
635  || ( MoveNodes - lastmove > COUNT ) )
636  {
637  lastopen = OpenNodes;
638  lastclos = ClosNodes;
639  lastmove = MoveNodes;
640  msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d" ),
642  ctx.pcbframe->SetStatusText( msg );
643  }
644 
645  _self = 0;
646 
647  if( curcell & HOLE )
648  {
649  _self = 5;
650 
651  // set 'present' bits
652  for( i = 0; i < 8; i++ )
653  {
654  selfok2[i].present = 0;
655 
656  if( curcell & selfok2[i].trace )
657  selfok2[i].present = 1;
658  }
659  }
660 
661  for( i = 0; i < 8; i++ ) // consider neighbors
662  {
663  nr = r + delta[i][0];
664  nc = c + delta[i][1];
665 
666  // off the edge?
667  if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
668  nc < 0 || nc >= RoutingMatrix.m_Ncols )
669  continue; // off the edge
670 
671  if( _self == 5 && selfok2[i].present )
672  continue;
673 
674  newcell = RoutingMatrix.GetCell( nr, nc, side );
675 
676  if( newcell & CURRENT_PAD )
677  newcell &= ~HOLE;
678 
679  // check for non-target hole
680  if( newcell & HOLE )
681  {
682  if( nr != row_target || nc != col_target )
683  continue;
684  }
685  // check for traces
686  else if( newcell & HOLE & ~(newmask[i]) )
687  {
688  continue;
689  }
690 
691  // check blocking on corner neighbors
692  if( delta[i][0] && delta[i][1] )
693  {
694  // check first buddy
695  buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side );
696 
697  if( buddy & CURRENT_PAD )
698  buddy &= ~HOLE;
699 
700  if( buddy & HOLE )
701  continue;
702 
703 // if (buddy & (blocking[i].b1)) continue;
704  // check second buddy
705  buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side );
706 
707  if( buddy & CURRENT_PAD )
708  buddy &= ~HOLE;
709 
710  if( buddy & HOLE )
711  continue;
712 
713 // if (buddy & (blocking[i].b2)) continue;
714  }
715 
716  olddir = RoutingMatrix.GetDir( r, c, side );
717  newdist = d + RoutingMatrix.CalcDist( ndir[i], olddir,
718  ( olddir == FROM_OTHERSIDE ) ?
719  RoutingMatrix.GetDir( r, c, 1 - side ) : 0, side );
720 
721  // if (a) not visited yet, or (b) we have
722  // found a better path, add it to queue
723  if( !RoutingMatrix.GetDir( nr, nc, side ) )
724  {
725  RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
726  RoutingMatrix.SetDist( nr, nc, side, newdist );
727 
728  if( SetQueue( nr, nc, side, newdist,
729  RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
730  row_target, col_target ) == 0 )
731  {
732  return ERR_MEMORY;
733  }
734  }
735  else if( newdist < RoutingMatrix.GetDist( nr, nc, side ) )
736  {
737  RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
738  RoutingMatrix.SetDist( nr, nc, side, newdist );
739  ReSetQueue( nr, nc, side, newdist,
740  RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
741  row_target, col_target );
742  }
743  }
744 
745  //* Test the other layer. *
746  if( two_sides )
747  {
748  olddir = RoutingMatrix.GetDir( r, c, side );
749 
750  if( olddir == FROM_OTHERSIDE )
751  continue; // useless move, so don't bother
752 
753  if( curcell ) // can't drill via if anything here
754  continue;
755 
756  // check for holes or traces on other side
757  if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 )
758  continue;
759 
760  // check for nearby holes or traces on both sides
761  for( skip = 0, i = 0; i < 8; i++ )
762  {
763  nr = r + delta[i][0]; nc = c + delta[i][1];
764 
765  if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
766  nc < 0 || nc >= RoutingMatrix.m_Ncols )
767  continue; // off the edge !!
768 
769  if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i] */ )
770  {
771  skip = 1; // can't drill via here
772  break;
773  }
774 
775  if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i] */ )
776  {
777  skip = 1; // can't drill via here
778  break;
779  }
780  }
781 
782  if( skip ) // neighboring hole or trace?
783  continue; // yes, can't drill via here
784 
785  newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side );
786 
787  /* if (a) not visited yet,
788  * or (b) we have found a better path,
789  * add it to queue */
790  if( !RoutingMatrix.GetDir( r, c, 1 - side ) )
791  {
792  RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
793  RoutingMatrix.SetDist( r, c, 1 - side, newdist );
794 
795  if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 )
796  {
797  return ERR_MEMORY;
798  }
799  }
800  else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) )
801  {
802  RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
803  RoutingMatrix.SetDist( r, c, 1 - side, newdist );
804  ReSetQueue( r, c,
805  1 - side,
806  newdist,
807  apx_dist,
808  row_target,
809  col_target );
810  }
811  } // Finished attempt to route on other layer.
812  }
813 
814 end_of_route:
815  PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL );
816  PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL );
817 
818  msg.Printf( wxT( "Activity: Open %d Closed %d Moved %d"),
820  ctx.pcbframe->SetStatusText( msg );
821 
822  return result;
823 }
#define FROM_OTHERSIDE
Definition: cell.h:112
BOARD * board
Board to be routed
Definition: autorout.h:91
static LSET AllCuMask(int aCuLayerCount=MAX_CU_LAYERS)
Function AllCuMask returns a mask holding the requested number of Cu PCB_LAYER_IDs.
Definition: lset.cpp:639
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
#define CURRENT_PAD
Definition: cell.h:49
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
#define SUCCESS
Definition: solve.cpp:93
long trace
Definition: solve.cpp:232
int present
Definition: solve.cpp:233
void GRSetDrawMode(wxDC *DC, GR_DRAWMODE draw_mode)
Definition: gr_basic.cpp:290
EDA_DRAW_PANEL * GetCanvas()
Definition: draw_frame.h:299
static const int ndir[8]
Definition: solve.cpp:124
int OpenNodes
Definition: solve.cpp:85
void GRLine(EDA_RECT *ClipBox, wxDC *DC, int x1, int y1, int x2, int y2, int width, COLOR4D Color)
Definition: gr_basic.cpp:352
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
int GetCopperLayerCount() const
Function GetCopperLayerCount.
int GetDir(int aRow, int aCol, int aSide)
#define FROM_NOWHERE
Definition: cell.h:103
#define ILLEGAL
Definition: autorout.h:52
#define TRIVIAL_SUCCESS
Definition: solve.cpp:94
void ReSetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:185
#define STOP_FROM_ESC
Definition: solve.cpp:91
static struct @0 selfok2[8]
#define abs(a)
Definition: auxiliary.h:84
static const int delta[8][2]
Definition: solve.cpp:112
#define WRITE_AND_CELL
Definition: autorout.h:193
int GetApxDist(int r1, int c1, int r2, int c2)
Definition: dist.cpp:42
#define NOSUCCESS
Definition: solve.cpp:90
#define TOP
Definition: autorout.h:49
void InitQueue()
Definition: queue.cpp:75
void GetQueue(int *, int *, int *, int *, int *)
Definition: queue.cpp:91
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
static RATSNEST_ITEM * pt_cur_ch
Definition: solve.cpp:80
static int segm_fX
Definition: solve.cpp:78
Class LSET is a set of PCB_LAYER_IDs.
static struct block blocking[8]
Definition: solve.cpp:187
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
LSET GetLayerSet() const override
Function GetLayerSet returns a "layer mask", which is a bitmap of all layers on which the TRACK segme...
Definition: class_pad.h:235
#define ERR_MEMORY
Definition: solve.cpp:92
DIST_CELL GetDist(int aRow, int aCol, int aSide)
const wxSize & GetSize() const
Definition: class_pad.h:182
EDA_RECT * GetClipBox()
virtual BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings returns the BOARD_DESIGN_SETTINGS for the BOARD owned by this frame...
int GetNet() const
Function GetNet.
Definition: class_netinfo.h:85
void SetDir(int aRow, int aCol, int aSide, int aDir)
D_PAD * GetPad(unsigned aIndex) const
Function GetPad.
Definition: class_board.h:750
static long newmask[8]
Definition: solve.cpp:246
wxDC * dc
Drawing context
Definition: autorout.h:97
unsigned GetPadCount() const
Function GetPadCount.
Definition: class_board.h:741
int ClosNodes
Definition: solve.cpp:86
D_PAD * m_PadStart
Definition: class_netinfo.h:75
int MoveNodes
Definition: solve.cpp:87
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
static int s_Clearance
Definition: solve.cpp:81
const EDA_RECT bbox
Cached board bounding box
Definition: autorout.h:94
PCB_EDIT_FRAME * pcbframe
Parent frame
Definition: autorout.h:88
bool GetAbortRequest() const
void SetDist(int aRow, int aCol, int aSide, DIST_CELL)
static int segm_fY
Definition: solve.cpp:78
double GetOrientation() const
Function GetOrientation returns the rotation angle of the pad in tenths of degrees, but soon degrees.
Definition: class_pad.h:214
int GetX() const
#define COUNT
char DIR_CELL
Definition: autorout.h:83
Definition: colors.h:49
int GetY() const
void PlacePad(D_PAD *pt_pad, int type, int marge, int op_logic)
Definition: graphpcb.cpp:87
static int segm_oY
Definition: solve.cpp:77
#define BOTTOM
Definition: autorout.h:50
bool SetQueue(int, int, int, int, int, int, int)
Definition: queue.cpp:120
int GetCurrentTrackWidth() const
Function GetCurrentTrackWidth.
#define HOLE
Definition: cell.h:40
static int segm_oX
Definition: solve.cpp:77
#define WRITE_OR_CELL
Definition: autorout.h:191
static int Retrace(AUTOROUTER_CONTEXT &ctx, int, int, int, int, int, int net_code)
Definition: solve.cpp:943
static void OrCell_Trace ( AUTOROUTER_CONTEXT ctx,
int  col,
int  row,
int  side,
int  orient,
int  current_net_code 
)
static

Definition at line 1153 of file solve.cpp.

References abs, AUTOROUTER_CONTEXT::bbox, AUTOROUTER_CONTEXT::board, F_Cu, g_CurrentTrackList, g_CurrentTrackSegment, g_Route_Layer_BOTTOM, g_Route_Layer_TOP, BOARD_DESIGN_SETTINGS::GetCurrentTrackWidth(), BOARD_DESIGN_SETTINGS::GetCurrentViaSize(), BOARD::GetDesignSettings(), TRACK::GetEnd(), D_PAD::GetPosition(), TRACK::GetStart(), EDA_RECT::GetX(), EDA_RECT::GetY(), HOLE, BOARD_DESIGN_SETTINGS::m_CurrentViaType, MATRIX_ROUTING_HEAD::m_GridRouting, RATSNEST_ITEM::m_PadEnd, PCB_VIA_T, DLIST< T >::PopBack(), DLIST< T >::PushBack(), RoutingMatrix, segm_fX, segm_fY, TRACK::SetEnd(), TRACK::SetStart(), VIA::SetViaType(), TOP, TRACK_AR, EDA_ITEM::Type(), VIA, wxPoint::x, and wxPoint::y.

Referenced by Retrace().

1155 {
1156  if( orient == HOLE ) // placement of a via
1157  {
1158  VIA* newVia = new VIA( ctx.board );
1159 
1160  g_CurrentTrackList.PushBack( newVia );
1161 
1162  g_CurrentTrackSegment->SetState( TRACK_AR, true );
1163  g_CurrentTrackSegment->SetLayer( F_Cu );
1164 
1166  ctx.bbox.GetY() + RoutingMatrix.m_GridRouting * col ) );
1167  g_CurrentTrackSegment->SetEnd( g_CurrentTrackSegment->GetStart() );
1168 
1171 
1172  g_CurrentTrackSegment->SetNetCode( current_net_code );
1173  }
1174  else // placement of a standard segment
1175  {
1176  TRACK* newTrack = new TRACK( ctx.board );
1177  int dx0, dy0, dx1, dy1;
1178 
1179  g_CurrentTrackList.PushBack( newTrack );
1180 
1182 
1183  if( side == TOP )
1185 
1186  g_CurrentTrackSegment->SetState( TRACK_AR, true );
1188  ctx.bbox.GetY() + RoutingMatrix.m_GridRouting * col ) );
1189  g_CurrentTrackSegment->SetNetCode( current_net_code );
1190 
1191  if( g_CurrentTrackSegment->Back() == NULL ) // Start trace.
1192  {
1193  g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) );
1194 
1195  // Placement on the center of the pad if outside grid.
1196  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1197  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1198 
1199  dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
1200  dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1201 
1202  // If aligned, change the origin point.
1203  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1204  {
1206  }
1207  else // Creation of a supplemental segment
1208  {
1210 
1211  newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1212  newTrack->SetStart( g_CurrentTrackSegment->GetEnd());
1213 
1214  g_CurrentTrackList.PushBack( newTrack );
1215  }
1216  }
1217  else
1218  {
1219  if( g_CurrentTrackSegment->Back() )
1220  {
1221  g_CurrentTrackSegment->SetStart( g_CurrentTrackSegment->Back()->GetEnd() );
1222  }
1223  }
1224 
1226 
1227  if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() )
1228  {
1229  // Reduce aligned segments by one.
1230  TRACK* oldTrack = g_CurrentTrackSegment->Back();
1231 
1232  if( oldTrack && oldTrack->Type() != PCB_VIA_T )
1233  {
1234  dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
1235  dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1236 
1237  dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x;
1238  dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y;
1239 
1240  if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1241  {
1242  oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() );
1243 
1244  delete g_CurrentTrackList.PopBack();
1245  }
1246  }
1247  }
1248  }
1249 }
BOARD * board
Board to be routed
Definition: autorout.h:91
#define g_CurrentTrackSegment
most recently created segment
Definition: pcbnew.h:101
KICAD_T Type() const
Function Type()
Definition: base_struct.h:198
PCB_LAYER_ID g_Route_Layer_TOP
Definition: pcbnew.cpp:78
PCB_LAYER_ID g_Route_Layer_BOTTOM
Definition: pcbnew.cpp:79
VIATYPE_T m_CurrentViaType
via type (VIA_BLIND_BURIED, VIA_THROUGH VIA_MICROVIA)
void SetViaType(VIATYPE_T aViaType)
Definition: class_track.h:447
void SetEnd(const wxPoint &aEnd)
Definition: class_track.h:117
DLIST< TRACK > g_CurrentTrackList
Definition: pcbnew.cpp:98
int GetCurrentViaSize() const
Function GetCurrentViaSize.
#define abs(a)
Definition: auxiliary.h:84
const wxPoint & GetEnd() const
Definition: class_track.h:118
void PushBack(T *aNewElement)
Function PushBack puts aNewElement at the end of the list sequence.
Definition: dlist.h:250
#define TOP
Definition: autorout.h:49
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
static RATSNEST_ITEM * pt_cur_ch
Definition: solve.cpp:80
static int segm_fX
Definition: solve.cpp:78
const wxPoint & GetStart() const
Definition: class_track.h:121
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
BOARD_DESIGN_SETTINGS & GetDesignSettings() const
Function GetDesignSettings.
Definition: class_board.h:530
#define TRACK_AR
Pcbnew: autorouted track.
Definition: base_struct.h:129
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
const EDA_RECT bbox
Cached board bounding box
Definition: autorout.h:94
T * PopBack()
Definition: dlist.h:228
static int segm_fY
Definition: solve.cpp:78
int GetX() const
int GetY() const
void SetStart(const wxPoint &aStart)
Definition: class_track.h:120
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:108
int GetCurrentTrackWidth() const
Function GetCurrentTrackWidth.
#define HOLE
Definition: cell.h:40
static int Retrace ( AUTOROUTER_CONTEXT ctx,
int  row_source,
int  col_source,
int  row_target,
int  col_target,
int  target_side,
int  net_code 
)
static

Definition at line 943 of file solve.cpp.

References AddNewTrace(), bit, block::c1, block::c2, DisplayError(), FROM_EAST, FROM_NORTH, FROM_NORTHEAST, FROM_NORTHWEST, FROM_OTHERSIDE, FROM_SOUTH, FROM_SOUTHEAST, FROM_SOUTHWEST, FROM_WEST, g_CurrentTrackList, DHEAD::GetCount(), MATRIX_ROUTING_HEAD::GetDir(), HOLE, HOLE_EAST, HOLE_NORTH, HOLE_NORTHEAST, HOLE_NORTHWEST, HOLE_SOUTH, HOLE_SOUTHEAST, HOLE_SOUTHWEST, HOLE_WEST, ILLEGAL, OrCell_Trace(), AUTOROUTER_CONTEXT::pcbframe, block::r1, block::r2, and RoutingMatrix.

Referenced by Autoroute_One_Track().

947 {
948  int r0, c0, s0;
949  int r1, c1, s1; // row, col, starting side.
950  int r2, c2, s2; // row, col, ending side.
951  int x, y = -1;
952  long b;
953 
954  r1 = row_target;
955  c1 = col_target; // start point is target ( end point is source )
956  s1 = target_side;
957  r0 = c0 = s0 = ILLEGAL;
958 
959  wxASSERT( g_CurrentTrackList.GetCount() == 0 );
960 
961  do
962  {
963  // find where we came from to get here
964  r2 = r1; c2 = c1; s2 = s1;
965  x = RoutingMatrix.GetDir( r1, c1, s1 );
966 
967  switch( x )
968  {
969  case FROM_NORTH:
970  r2++;
971  break;
972 
973  case FROM_EAST:
974  c2++;
975  break;
976 
977  case FROM_SOUTH:
978  r2--;
979  break;
980 
981  case FROM_WEST:
982  c2--;
983  break;
984 
985  case FROM_NORTHEAST:
986  r2++;
987  c2++;
988  break;
989 
990  case FROM_SOUTHEAST:
991  r2--;
992  c2++;
993  break;
994 
995  case FROM_SOUTHWEST:
996  r2--;
997  c2--;
998  break;
999 
1000  case FROM_NORTHWEST:
1001  r2++;
1002  c2--;
1003  break;
1004 
1005  case FROM_OTHERSIDE:
1006  s2 = 1 - s2;
1007  break;
1008 
1009  default:
1010  wxMessageBox( wxT( "Retrace: internal error: no way back" ) );
1011  return 0;
1012  }
1013 
1014  if( r0 != ILLEGAL )
1015  y = RoutingMatrix.GetDir( r0, c0, s0 );
1016 
1017  // see if target or hole
1018  if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) )
1019  {
1020  int p_dir;
1021 
1022  switch( x )
1023  {
1024  case FROM_NORTH:
1025  p_dir = HOLE_NORTH;
1026  break;
1027 
1028  case FROM_EAST:
1029  p_dir = HOLE_EAST;
1030  break;
1031 
1032  case FROM_SOUTH:
1033  p_dir = HOLE_SOUTH;
1034  break;
1035 
1036  case FROM_WEST:
1037  p_dir = HOLE_WEST;
1038  break;
1039 
1040  case FROM_NORTHEAST:
1041  p_dir = HOLE_NORTHEAST;
1042  break;
1043 
1044  case FROM_SOUTHEAST:
1045  p_dir = HOLE_SOUTHEAST;
1046  break;
1047 
1048  case FROM_SOUTHWEST:
1049  p_dir = HOLE_SOUTHWEST;
1050  break;
1051 
1052  case FROM_NORTHWEST:
1053  p_dir = HOLE_NORTHWEST;
1054  break;
1055 
1056  case FROM_OTHERSIDE:
1057  default:
1058  DisplayError( ctx.pcbframe, wxT( "Retrace: error 1" ) );
1059  return 0;
1060  }
1061 
1062  OrCell_Trace( ctx, r1, c1, s1, p_dir, current_net_code );
1063  }
1064  else
1065  {
1066  if( ( y == FROM_NORTH || y == FROM_NORTHEAST
1067  || y == FROM_EAST || y == FROM_SOUTHEAST
1068  || y == FROM_SOUTH || y == FROM_SOUTHWEST
1069  || y == FROM_WEST || y == FROM_NORTHWEST )
1070  && ( x == FROM_NORTH || x == FROM_NORTHEAST
1071  || x == FROM_EAST || x == FROM_SOUTHEAST
1072  || x == FROM_SOUTH || x == FROM_SOUTHWEST
1073  || x == FROM_WEST || x == FROM_NORTHWEST
1074  || x == FROM_OTHERSIDE )
1075  && ( ( b = bit[y - 1][x - 1] ) != 0 ) )
1076  {
1077  OrCell_Trace( ctx, r1, c1, s1, b, current_net_code );
1078 
1079  if( b & HOLE )
1080  OrCell_Trace( ctx, r2, c2, s2, HOLE, current_net_code );
1081  }
1082  else
1083  {
1084  wxMessageBox( wxT( "Retrace: error 2" ) );
1085  return 0;
1086  }
1087  }
1088 
1089  if( ( r2 == row_source ) && ( c2 == col_source ) ) // see if source
1090  {
1091  int p_dir;
1092 
1093  switch( x )
1094  {
1095  case FROM_NORTH:
1096  p_dir = HOLE_SOUTH;
1097  break;
1098 
1099  case FROM_EAST:
1100  p_dir = HOLE_WEST;
1101  break;
1102 
1103  case FROM_SOUTH:
1104  p_dir = HOLE_NORTH;
1105  break;
1106 
1107  case FROM_WEST:
1108  p_dir = HOLE_EAST;
1109  break;
1110 
1111  case FROM_NORTHEAST:
1112  p_dir = HOLE_SOUTHWEST;
1113  break;
1114 
1115  case FROM_SOUTHEAST:
1116  p_dir = HOLE_NORTHWEST;
1117  break;
1118 
1119  case FROM_SOUTHWEST:
1120  p_dir = HOLE_NORTHEAST;
1121  break;
1122 
1123  case FROM_NORTHWEST:
1124  p_dir = HOLE_SOUTHEAST;
1125  break;
1126 
1127  case FROM_OTHERSIDE:
1128  default:
1129  wxMessageBox( wxT( "Retrace: error 3" ) );
1130  return 0;
1131  }
1132 
1133  OrCell_Trace( ctx, r2, c2, s2, p_dir, current_net_code );
1134  }
1135 
1136  // move to next cell
1137  r0 = r1;
1138  c0 = c1;
1139  s0 = s1;
1140  r1 = r2;
1141  c1 = c2;
1142  s1 = s2;
1143  } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) );
1144 
1145  AddNewTrace( ctx );
1146  return 1;
1147 }
#define FROM_NORTHWEST
Definition: cell.h:111
#define FROM_OTHERSIDE
Definition: cell.h:112
#define FROM_NORTHEAST
Definition: cell.h:105
#define HOLE_NORTHWEST
Definition: cell.h:60
DLIST< TRACK > g_CurrentTrackList
Definition: pcbnew.cpp:98
#define FROM_SOUTH
Definition: cell.h:108
int GetDir(int aRow, int aCol, int aSide)
#define FROM_NORTH
Definition: cell.h:104
#define FROM_EAST
Definition: cell.h:106
#define ILLEGAL
Definition: autorout.h:52
#define HOLE_SOUTH
Definition: cell.h:57
#define HOLE_EAST
Definition: cell.h:55
static void AddNewTrace(AUTOROUTER_CONTEXT &ctx)
Definition: solve.cpp:1257
#define HOLE_NORTH
Definition: cell.h:53
#define FROM_SOUTHWEST
Definition: cell.h:109
#define HOLE_NORTHEAST
Definition: cell.h:54
static void OrCell_Trace(AUTOROUTER_CONTEXT &ctx, int col, int row, int side, int orient, int current_net_code)
Definition: solve.cpp:1153
MATRIX_ROUTING_HEAD RoutingMatrix
Definition: autorout.cpp:51
#define HOLE_SOUTHWEST
Definition: cell.h:58
PCB_EDIT_FRAME * pcbframe
Parent frame
Definition: autorout.h:88
#define HOLE_SOUTHEAST
Definition: cell.h:56
static long bit[8][9]
Definition: solve.cpp:826
unsigned GetCount() const
Function GetCount returns the number of elements in the list.
Definition: dlist.h:126
#define FROM_SOUTHEAST
Definition: cell.h:107
void DisplayError(wxWindow *parent, const wxString &text, int displaytime)
Function DisplayError displays an error or warning message box with aMessage.
Definition: confirm.cpp:69
#define HOLE
Definition: cell.h:40
#define FROM_WEST
Definition: cell.h:110
#define HOLE_WEST
Definition: cell.h:59

Variable Documentation

long bit[8][9]
static
struct block blocking[8]
static

Definition at line 187 of file solve.cpp.

int ClosNodes

Definition at line 86 of file solve.cpp.

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

const int delta[8][2]
static
Initial value:
=
{
{ 1, -1 },
{ 1, 0 },
{ 1, 1 },
{ 0, -1 },
{ 0, 1 },
{ -1, -1 },
{ -1, 0 },
{ -1, 1 }
}

Definition at line 112 of file solve.cpp.

Referenced by EC_SNAPLINE::Apply(), PNS::ApproximateSegmentAsRect(), PLOTTER::Arc(), PDF_PLOTTER::Arc(), Autoroute_One_Track(), PL_EDITOR_FRAME::Block_Move(), GERBVIEW_FRAME::Block_Move(), BuildDimension(), D_PAD::BuildPadPolygon(), D_PAD::BuildSegmentFromOvalShape(), Collect_TrackSegmentsToDrag(), CONNECTIONS::CollectItemsNearTo(), Collide(), SHAPE_POLY_SET::CollideVertex(), GERBER_DRAW_ITEM::ConvertSegmentToPolygon(), AM_PRIMITIVE::ConvertShapeToPolygon(), D_CODE::ConvertShapeToPolygon(), PNS::coupledBypass(), EXCELLON_WRITER::createDrillFile(), BOARD::CreateLockPoint(), CreateThermalReliefPadPolygon(), PCBNEW_CONTROL::CursorControl(), DRC::doTrackDrc(), SCH_NO_CONNECT::Draw(), DRAWING_TOOL::DrawDimension(), D_CODE::DrawFlashedShape(), GBR_LAYOUT::DrawItemsDCodeID(), fillArcGBRITEM(), SCH_EDIT_FRAME::FindComponentAndItem(), PSLIKE_PLOTTER::FlashPadOval(), GERBER_PLOTTER::FlashPadOval(), C3D_RENDER_OGL_LEGACY::generate_new_3DGrid(), C3D_RENDER_OGL_LEGACY::generate_ring_contour(), DIMENSION::GetAngle(), SCH_NO_CONNECT::GetBoundingBox(), BOARD::GetPad(), SCH_NO_CONNECT::HitTest(), D_PAD::HitTest(), CPolyLine::HitTestForCorner(), CVCYLINDER::Intersect(), CVCYLINDER::IntersectP(), Move_Segment(), OGL_draw_half_open_cylinder(), KIGFX::WX_VIEW_CONTROLS::onMotion(), KIGFX::WX_VIEW_CONTROLS::onWheel(), PCB_PARSER::parseD_PAD(), GPCB_FPL_CACHE::parseMODULE(), DRAWING_TOOL::PlaceDXF(), SCH_NO_CONNECT::Plot(), PlotStandardLayer(), EDA_DRAW_PANEL_GAL::Refresh(), render_curveto(), CONNECTIONS::SearchConnectedTracks(), CONNECTIONS::searchEntryPointInCandidatesList(), MODULE::SetPosition(), KIGFX::VIEW::SetScale(), WIZARD_3DSHAPE_LIBS_DOWNLOADER::setupReview(), PNS_KICAD_IFACE::syncPad(), DRC::testTexts(), DRC::testTracks(), KIGFX::COLOR4D::ToHSV(), TracePcbLine(), DIALOG_PAD_PROPERTIES::transferDataToPad(), TransformArcToPolygon(), CINFO3D_VISU::TransformArcToSegments(), TransformCircleToPolygon(), TransformRingToPolygon(), and TransformRoundedEndsSegmentToPolygon().

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().

const int ndir[8]
static
Initial value:
=
{
}
#define FROM_NORTHWEST
Definition: cell.h:111
#define FROM_NORTHEAST
Definition: cell.h:105
#define FROM_SOUTH
Definition: cell.h:108
#define FROM_NORTH
Definition: cell.h:104
#define FROM_EAST
Definition: cell.h:106
#define FROM_SOUTHWEST
Definition: cell.h:109
#define FROM_SOUTHEAST
Definition: cell.h:107
#define FROM_WEST
Definition: cell.h:110

Definition at line 124 of file solve.cpp.

Referenced by Autoroute_One_Track().

long newmask[8]
static
Initial value:
=
{
0,
0,
0,
0
}
#define CORNER_NORTHWEST
Definition: cell.h:70
#define CORNER_SOUTHEAST
Definition: cell.h:68
#define CORNER_SOUTHWEST
Definition: cell.h:69
#define CORNER_NORTHEAST
Definition: cell.h:67

Definition at line 246 of file solve.cpp.

Referenced by Autoroute_One_Track().

int OpenNodes

Definition at line 85 of file solve.cpp.

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

int present

Definition at line 233 of file solve.cpp.

Referenced by Autoroute_One_Track().

RATSNEST_ITEM* pt_cur_ch
static

Definition at line 80 of file solve.cpp.

int s_Clearance
static

Definition at line 81 of file solve.cpp.

Referenced by AddNewTrace(), Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

PICKED_ITEMS_LIST s_ItemsListPicker
static

Definition at line 83 of file solve.cpp.

int segm_fX
static

Definition at line 78 of file solve.cpp.

Referenced by Autoroute_One_Track(), OrCell_Trace(), and PCB_EDIT_FRAME::Solve().

int segm_fY
static

Definition at line 78 of file solve.cpp.

Referenced by Autoroute_One_Track(), OrCell_Trace(), and PCB_EDIT_FRAME::Solve().

int segm_oX
static

Definition at line 77 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

int segm_oY
static

Definition at line 77 of file solve.cpp.

Referenced by Autoroute_One_Track(), and PCB_EDIT_FRAME::Solve().

struct { ... } selfok2[8]
Initial value:
=
{
{ HOLE_NORTH, 0 },
{ HOLE_WEST, 0 },
{ HOLE_EAST, 0 },
{ HOLE_SOUTH, 0 },
}
#define HOLE_NORTHWEST
Definition: cell.h:60
#define HOLE_SOUTH
Definition: cell.h:57
#define HOLE_EAST
Definition: cell.h:55
#define HOLE_NORTH
Definition: cell.h:53
#define HOLE_NORTHEAST
Definition: cell.h:54
#define HOLE_SOUTHWEST
Definition: cell.h:58
#define HOLE_SOUTHEAST
Definition: cell.h:56
#define HOLE_WEST
Definition: cell.h:59

Referenced by Autoroute_One_Track().