solve.cpp 41.9 KB
Newer Older
1 2 3
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
4 5 6 7 8 9
 * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
 *
 * Copyright (C) 1992-2012 KiCad Developers, see change_log.txt for contributors.
 *
 * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

29 30 31
/* see "Autorouting With the A* Algorithm" (Dr.Dobbs journal)
*/

32 33 34
/**
 * @file solve.cpp
 */
35

36 37 38 39 40 41 42
#include <fctsys.h>
#include <class_drawpanel.h>
#include <confirm.h>
#include <wxPcbStruct.h>
#include <gr_basic.h>
#include <macros.h>
#include <pcbcommon.h>
43

44 45
#include <class_board.h>
#include <class_track.h>
46

47 48
#include <pcbnew.h>
#include <protos.h>
49
#include <autorout.h>
50
#include <cell.h>
51

52

53 54 55 56 57 58 59
static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe,
                                wxDC*           DC,
                                int             two_sides,
                                int             row_source,
                                int             col_source,
                                int             row_target,
                                int             col_target,
60
                                RATSNEST_ITEM*  pt_rat );
61

62 63
static int Retrace( PCB_EDIT_FRAME* pcbframe,
                    wxDC*           DC,
64 65 66 67 68 69
                    int,
                    int,
                    int,
                    int,
                    int,
                    int              net_code );
70

71 72 73 74 75 76
static void OrCell_Trace( BOARD* pcb,
                          int    col,
                          int    row,
                          int    side,
                          int    orient,
                          int    current_net_code );
77 78

static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC );
79

80 81 82 83

static int            segm_oX, segm_oY;
static int            segm_fX, segm_fY; /* Origin and position of the current
                                         * trace segment. */
84
static RATSNEST_ITEM* pt_cur_ch;
85
static int            s_Clearance;  // Clearance value used in autorouter
86

87 88
static PICKED_ITEMS_LIST s_ItemsListPicker;

89 90 91 92
int OpenNodes;       /* total number of nodes opened */
int ClosNodes;       /* total number of nodes closed */
int MoveNodes;       /* total number of nodes moved */
int MaxNodes;        /* maximum number of nodes opened at one time */
93

94 95 96 97
#define NOSUCCESS       0
#define STOP_FROM_ESC   -1
#define ERR_MEMORY      -2
#define SUCCESS         1
98 99 100 101 102
#define TRIVIAL_SUCCESS 2

/*
** visit neighboring cells like this (where [9] is on the other side):
**
103 104 105 106 107 108 109
**  +---+---+---+
**  | 1 | 2 | 3 |
**  +---+---+---+
**  | 4 |[9]| 5 |
**  +---+---+---+
**  | 6 | 7 | 8 |
**  +---+---+---+
110 111
*/

112 113 114 115
/* for visiting neighbors on the same side: increments/decrements coord of
 * [] [0] = row [] (1] = col was added to the coord of the midpoint for
 * Get the coord of the 8 neighboring points.
 */
116
static const int delta[8][2] =
117
{
118 119 120 121 122 123 124 125
    {  1, -1 },     /* northwest    */
    {  1, 0  },     /* north        */
    {  1, 1  },     /* northeast    */
    {  0, -1 },     /* west     */
    {  0, 1  },     /* east     */
    { -1, -1 },     /* southwest    */
    { -1, 0  },     /* south        */
    { -1, 1  }      /* southeast    */
126
};
127

128
static const int ndir[8] =
129 130
{
    /* for building paths back to source */
131
    FROM_SOUTHEAST, FROM_SOUTH,     FROM_SOUTHWEST,
132
    FROM_EAST,      FROM_WEST,
133
    FROM_NORTHEAST, FROM_NORTH,     FROM_NORTHWEST
134
};
135 136

/* blocking masks for neighboring cells */
137
#define BLOCK_NORTHEAST ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
138
                          | ANGLE_NEtoSE | ANGLE_NWtoNE         \
139 140
                          | SHARP_NtoNE | SHARP_EtoNE | HOLE )
#define BLOCK_SOUTHEAST ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
141
                          | ANGLE_NEtoSE | ANGLE_SEtoSW         \
142 143
                          | SHARP_EtoSE | SHARP_StoSE | HOLE )
#define BLOCK_SOUTHWEST ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
144
                          | ANGLE_SEtoSW | ANGLE_SWtoNW         \
145 146
                          | SHARP_StoSW | SHARP_WtoSW | HOLE )
#define BLOCK_NORTHWEST ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
147
                          | ANGLE_SWtoNW | ANGLE_NWtoNE         \
148
                          | SHARP_WtoNW | SHARP_NtoNW | HOLE )
149 150 151 152
#define BLOCK_NORTH     ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW      \
                          | BENT_EtoNW | BENT_WtoNE                    \
                          | BENT_StoNE | BENT_StoNW                    \
                          | CORNER_NORTHEAST | CORNER_NORTHWEST        \
153
                          | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
154 155
                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
                          | SHARP_NtoNE | SHARP_NtoNW                  \
156
                          | SHARP_EtoNE | SHARP_WtoNW | HOLE )
157 158 159 160
#define BLOCK_EAST      ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW    \
                          | BENT_NtoSE | BENT_StoNE                    \
                          | BENT_WtoNE | BENT_WtoSE                    \
                          | CORNER_NORTHEAST | CORNER_SOUTHEAST        \
161
                          | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
162 163
                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
                          | SHARP_EtoNE | SHARP_EtoSE                  \
164
                          | SHARP_NtoNE | SHARP_StoSE | HOLE )
165 166 167 168
#define BLOCK_SOUTH     ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW      \
                          | BENT_EtoSW | BENT_WtoSE                    \
                          | BENT_NtoSE | BENT_NtoSW                    \
                          | CORNER_SOUTHEAST | CORNER_SOUTHWEST        \
169
                          | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
170 171
                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
                          | SHARP_StoSE | SHARP_StoSW                  \
172
                          | SHARP_EtoSE | SHARP_WtoSW | HOLE )
173 174 175 176
#define BLOCK_WEST      ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE    \
                          | BENT_NtoSW | BENT_StoNW                    \
                          | BENT_EtoSW | BENT_EtoNW                    \
                          | CORNER_SOUTHWEST | CORNER_NORTHWEST        \
177
                          | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
178 179
                          | DIAG_NEtoSW | DIAG_SEtoNW                  \
                          | SHARP_WtoSW | SHARP_WtoNW                  \
180
                          | SHARP_NtoNW | SHARP_StoSW | HOLE )
181 182 183 184 185 186 187 188 189

struct block
{
    int  r1, c1;
    long b1;
    int  r2, c2;
    long b2;
};

190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
/* blocking masks for diagonal traces */
static struct block blocking[8] =
{ {
      0, -1,
      BLOCK_NORTHEAST,
      1, 0,
      BLOCK_SOUTHWEST
  },
  {
      0, 0, 0,
      0, 0, 0
  },
  {
      1, 0,
      BLOCK_SOUTHEAST,
      0, 1,
      BLOCK_NORTHWEST
  },
  {
      0, 0, 0,
      0, 0, 0
  },
  {
      0, 0, 0,
      0, 0, 0
  },
  {
      0, -1,
      BLOCK_SOUTHEAST,
      -1, 0,
      BLOCK_NORTHWEST
  },
  {
      0, 0, 0,
      0, 0, 0
  },
  {
      -1, 0,
      BLOCK_NORTHEAST,
      0, 1,
      BLOCK_SOUTHWEST
  } };
232 233

/* mask for hole-related blocking effects */
234 235 236 237
static struct
{
    long trace;
    int  present;
238 239 240 241 242 243 244 245 246 247
} selfok2[8] =
{
    { HOLE_NORTHWEST, 0 },
    { HOLE_NORTH,     0 },
    { HOLE_NORTHEAST, 0 },
    { HOLE_WEST,      0 },
    { HOLE_EAST,      0 },
    { HOLE_SOUTHWEST, 0 },
    { HOLE_SOUTH,     0 },
    { HOLE_SOUTHEAST, 0 }
248
};
249

250 251 252 253 254
static long newmask[8] =
{
    /* patterns to mask out in neighbor cells */
    0,
    CORNER_NORTHWEST | CORNER_NORTHEAST,
255
    0,
256 257 258 259
    CORNER_NORTHWEST | CORNER_SOUTHWEST,
    CORNER_NORTHEAST | CORNER_SOUTHEAST,
    0,
    CORNER_SOUTHWEST | CORNER_SOUTHEAST,
260
    0
261
};
262 263


264 265 266 267 268
/* Route all traces
 * Return:
 *  1 if OK
 * -1 if escape (stop being routed) request
 * -2 if default memory allocation
269
 */
270
int PCB_EDIT_FRAME::Solve( wxDC* DC, int aLayersCount )
271
{
272 273 274
    int           current_net_code;
    int           row_source, col_source, row_target, col_target;
    int           success, nbsucces = 0, nbunsucces = 0;
275
    NETINFO_ITEM* net;
276
    bool          stop = false;
277
    wxString      msg;
278
    int           routedCount = 0;      // routed ratsnest count
279
    bool          two_sides = aLayersCount == 2;
280

281
    m_canvas->SetAbortRequest( false );
282

283 284
    s_Clearance = GetBoard()->m_NetClasses.GetDefault()->GetClearance();

285 286 287
    // Prepare the undo command info
    s_ItemsListPicker.ClearListAndDeleteItems();  // Should not be necessary, but...

288 289
    /* go until no more work to do */
    GetWork( &row_source, &col_source, &current_net_code,
290
             &row_target, &col_target, &pt_cur_ch ); // First net to route.
291 292

    for( ; row_source != ILLEGAL; GetWork( &row_source, &col_source,
293 294
                                           &current_net_code, &row_target,
                                           &col_target,
295
                                           &pt_cur_ch ) )
296
    {
297
        /* Test to stop routing ( escape key pressed ) */
298
        wxYield();
299

300
        if( m_canvas->GetAbortRequest() )
301 302 303 304
        {
            if( IsOK( this, _( "Abort routing?" ) ) )
            {
                success = STOP_FROM_ESC;
305
                stop    = true;
306 307 308
                break;
            }
            else
309
            {
310
                m_canvas->SetAbortRequest( false );
311
            }
312 313
        }

314 315
        EraseMsgBox();

316
        routedCount++;
317
        net = GetBoard()->FindNet( current_net_code );
318

319
        if( net )
320
        {
321
            msg.Printf( wxT( "[%8.8s]" ), GetChars( net->GetNetname() ) );
322
            AppendMsgPanel( wxT( "Net route" ), msg, BROWN );
323
            msg.Printf( wxT( "%d / %d" ), routedCount, RoutingMatrix.m_RouteCount );
324
            AppendMsgPanel( wxT( "Activity" ), msg, BROWN );
325 326 327
        }

        pt_cur_ch = pt_cur_ch;
328 329 330 331
        segm_oX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_source);
        segm_oY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_source);
        segm_fX = GetBoard()->GetBoundingBox().GetX() + (RoutingMatrix.m_GridRouting * col_target);
        segm_fY = GetBoard()->GetBoundingBox().GetY() + (RoutingMatrix.m_GridRouting * row_target);
332 333

        /* Draw segment. */
334 335
        GRLine( m_canvas->GetClipBox(), DC,
                segm_oX, segm_oY, segm_fX, segm_fY,
336
                0, WHITE );
337 338
        pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT );
        pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_OR | GR_HIGHLIGHT );
339

340 341 342
        success = Autoroute_One_Track( this, DC,
                                       two_sides, row_source, col_source,
                                       row_target, col_target, pt_cur_ch );
343 344 345 346

        switch( success )
        {
        case NOSUCCESS:
347
            pt_cur_ch->m_Status |= CH_UNROUTABLE;
348 349 350 351
            nbunsucces++;
            break;

        case STOP_FROM_ESC:
352
            stop = true;
353 354 355
            break;

        case ERR_MEMORY:
356
            stop = true;
357 358 359 360 361 362 363
            break;

        default:
            nbsucces++;
            break;
        }

364
        msg.Printf( wxT( "%d" ), nbsucces );
365
        AppendMsgPanel( wxT( "OK" ), msg, GREEN );
366 367
        msg.Printf( wxT( "%d" ), nbunsucces );
        AppendMsgPanel( wxT( "Fail" ), msg, RED );
368
        msg.Printf( wxT( "  %d" ), GetBoard()->GetUnconnectedNetCount() );
369
        AppendMsgPanel( wxT( "Not Connected" ), msg, CYAN );
370

371
        /* Delete routing from display. */
372 373
        pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_AND );
        pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_AND );
374 375 376 377 378

        if( stop )
            break;
    }

379 380 381
    SaveCopyInUndoList( s_ItemsListPicker, UR_UNSPECIFIED );
    s_ItemsListPicker.ClearItemsList(); // s_ItemsListPicker is no more owner of picked items

382
    return SUCCESS;
383 384
}

385

386 387 388 389 390 391 392
/* Route a trace on the BOARD.
 * Parameters:
 * 1 side / 2 sides (0 / 1)
 * Coord source (row, col)
 * Coord destination (row, col)
 * Net_code
 * Pointer to the ratsnest reference
393
 *
394 395
 * Returns:
 * SUCCESS if routed
396
 * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed)
397 398 399
 * If failure NOSUCCESS
 * Escape STOP_FROM_ESC if demand
 * ERR_MEMORY if memory allocation failed.
400
 */
401 402 403 404 405 406 407
static int Autoroute_One_Track( PCB_EDIT_FRAME* pcbframe,
                                wxDC*           DC,
                                int             two_sides,
                                int             row_source,
                                int             col_source,
                                int             row_target,
                                int             col_target,
408
                                RATSNEST_ITEM*  pt_rat )
409
{
410 411 412 413 414 415
    int          r, c, side, d, apx_dist, nr, nc;
    int          result, skip;
    int          i;
    long         curcell, newcell, buddy, lastopen, lastclos, lastmove;
    int          newdist, olddir, _self;
    int          current_net_code;
416
    int          marge;
417 418
    int          padLayerMaskStart;    /* Mask layers belonging to the starting pad. */
    int          padLayerMaskEnd;      /* Mask layers belonging to the ending pad. */
419 420
    int          topLayerMask = GetLayerMask( g_Route_Layer_TOP );
    int          bottomLayerMask = GetLayerMask( g_Route_Layer_BOTTOM );
421 422
    int          routeLayerMask;       /* Mask two layers for routing. */
    int          tab_mask[2];       /* Enables the calculation of the mask layer being
423 424 425 426 427 428
                                     * tested. (side = TOP or BOTTOM) */
    int          start_mask_layer = 0;
    wxString     msg;

    wxBusyCursor dummy_cursor;      // Set an hourglass cursor while routing a
                                    // track
429

430 431
    result = NOSUCCESS;

432
    marge = s_Clearance + ( pcbframe->GetBoard()->GetCurrentTrackWidth() / 2 );
433 434

    /* clear direction flags */
435
    i = RoutingMatrix.m_Nrows * RoutingMatrix.m_Ncols * sizeof(DIR_CELL);
436 437 438

    if( two_sides )
        memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i );
439
    memset( RoutingMatrix.m_DirSide[BOTTOM], FROM_NOWHERE, i );
440 441 442

    lastopen = lastclos = lastmove = 0;

443
    /* Set tab_masque[side] for final test of routing. */
444 445
    if( two_sides )
        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;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
452 453 454 455 456

    current_net_code  = pt_rat->GetNet();
    padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerMask();

    padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerMask();
457 458


459 460 461
    /* First Test if routing possible ie if the pads are accessible
     * on the routing layers.
     */
462
    if( ( routeLayerMask & padLayerMaskStart ) == 0 )
463
        goto end_of_route;
464 465

    if( ( routeLayerMask & padLayerMaskEnd ) == 0 )
466 467
        goto end_of_route;

468 469 470
    /* Then test if routing possible ie if the pads are accessible
     * On the routing grid (1 grid point must be in the pad)
     */
471
    {
472
        int cX = ( RoutingMatrix.m_GridRouting * col_source )
473
                 + pcbframe->GetBoard()->GetBoundingBox().GetX();
474
        int cY = ( RoutingMatrix.m_GridRouting * row_source )
475
                 + pcbframe->GetBoard()->GetBoundingBox().GetY();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
476 477
        int dx = pt_cur_ch->m_PadStart->GetSize().x / 2;
        int dy = pt_cur_ch->m_PadStart->GetSize().y / 2;
478 479
        int px = pt_cur_ch->m_PadStart->GetPosition().x;
        int py = pt_cur_ch->m_PadStart->GetPosition().y;
480

Dick Hollenbeck's avatar
Dick Hollenbeck committed
481
        if( ( ( int( pt_cur_ch->m_PadStart->GetOrientation() ) / 900 ) & 1 ) != 0 )
482
            EXCHG( dx, dy );
483

484
        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
485 486
            goto end_of_route;

487
        cX = ( RoutingMatrix.m_GridRouting * col_target )
488
             + pcbframe->GetBoard()->GetBoundingBox().GetX();
489
        cY = ( RoutingMatrix.m_GridRouting * row_target )
490
             + pcbframe->GetBoard()->GetBoundingBox().GetY();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
491 492
        dx = pt_cur_ch->m_PadEnd->GetSize().x / 2;
        dy = pt_cur_ch->m_PadEnd->GetSize().y / 2;
493 494
        px = pt_cur_ch->m_PadEnd->GetPosition().x;
        py = pt_cur_ch->m_PadEnd->GetPosition().y;
495

Dick Hollenbeck's avatar
Dick Hollenbeck committed
496
        if( ( ( int( pt_cur_ch->m_PadEnd->GetOrientation() ) / 900) & 1 ) != 0 )
497 498
            EXCHG( dx, dy );

499
        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
500 501 502
            goto end_of_route;
    }

503 504
    /* Test the trivial case: direct connection overlay pads. */
    if( ( row_source == row_target ) && ( col_source == col_target )
505
       && ( padLayerMaskEnd & padLayerMaskStart &
506
            g_TabAllCopperLayerMask[pcbframe->GetBoard()->GetCopperLayerCount() - 1] ) )
507 508 509 510 511
    {
        result = TRIVIAL_SUCCESS;
        goto end_of_route;
    }

512
    /* Placing the bit to remove obstacles on 2 pads to a link. */
513
    pcbframe->SetStatusText( wxT( "Gen Cells" ) );
514

515 516
    PlacePad( pt_cur_ch->m_PadStart, CURRENT_PAD, marge, WRITE_OR_CELL );
    PlacePad( pt_cur_ch->m_PadEnd, CURRENT_PAD, marge, WRITE_OR_CELL );
517

518
    /* Regenerates the remaining barriers (which may encroach on the placement bits precedent)
519
     */
520
    i = pcbframe->GetBoard()->GetPadCount();
521

522
    for( unsigned ii = 0; ii < pcbframe->GetBoard()->GetPadCount(); ii++ )
523
    {
524
        D_PAD* ptr = pcbframe->GetBoard()->GetPad( ii );
525

526
        if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) )
527
        {
528
            PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL );
529 530 531 532
        }
    }

    InitQueue(); /* initialize the search queue */
533
    apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target );
534

535 536
    /* Initialize first search. */
    if( two_sides )   /* Preferred orientation. */
537 538 539
    {
        if( abs( row_target - row_source ) > abs( col_target - col_source ) )
        {
540
            if( padLayerMaskStart & topLayerMask )
541 542
            {
                start_mask_layer = 2;
543

544
                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
545
                              row_target, col_target ) == 0 )
546 547 548 549
                {
                    return ERR_MEMORY;
                }
            }
550 551

            if( padLayerMaskStart & bottomLayerMask )
552 553 554 555
            {
                start_mask_layer |= 1;

                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
556
                              row_target, col_target ) == 0 )
557 558 559 560 561 562 563
                {
                    return ERR_MEMORY;
                }
            }
        }
        else
        {
564
            if( padLayerMaskStart & bottomLayerMask )
565 566
            {
                start_mask_layer = 1;
567

568
                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
569
                              row_target, col_target ) == 0 )
570 571 572 573
                {
                    return ERR_MEMORY;
                }
            }
574 575

            if( padLayerMaskStart & topLayerMask )
576 577 578 579
            {
                start_mask_layer |= 2;

                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
580
                              row_target, col_target ) == 0 )
581 582 583 584 585 586
                {
                    return ERR_MEMORY;
                }
            }
        }
    }
587
    else if( padLayerMaskStart & bottomLayerMask )
588 589 590
    {
        start_mask_layer = 1;

591
        if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 )
592 593 594 595 596 597 598
        {
            return ERR_MEMORY;
        }
    }

    /* search until success or we exhaust all possibilities */
    GetQueue( &r, &c, &side, &d, &apx_dist );
599

600 601
    for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) )
    {
602
        curcell = RoutingMatrix.GetCell( r, c, side );
603

604 605
        if( curcell & CURRENT_PAD )
            curcell &= ~HOLE;
606

607
        if( (r == row_target) && (c == col_target)  /* success if layer OK */
608
           && ( tab_mask[side] & padLayerMaskEnd) )
609
        {
610
            /* Remove link. */
611
            GRSetDrawMode( DC, GR_XOR );
612
            GRLine( pcbframe->GetCanvas()->GetClipBox(),
613 614 615 616 617 618 619
                    DC,
                    segm_oX,
                    segm_oY,
                    segm_fX,
                    segm_fY,
                    0,
                    WHITE );
620

621
            /* Generate trace. */
622
            if( Retrace( pcbframe, DC, row_source, col_source,
623
                         row_target, col_target, side, current_net_code ) )
624 625 626
            {
                result = SUCCESS;   /* Success : Route OK */
            }
627

628
            break;                  /* Routing complete. */
629 630
        }

631
        if( pcbframe->GetCanvas()->GetAbortRequest() )
632
        {
633 634
            result = STOP_FROM_ESC;
            break;
635 636
        }

637
        /* report every COUNT new nodes or so */
charras's avatar
charras committed
638
        #define COUNT 20000
639

640 641 642
        if( ( OpenNodes - lastopen > COUNT )
           || ( ClosNodes - lastclos > COUNT )
           || ( MoveNodes - lastmove > COUNT ) )
643 644
        {
            lastopen = OpenNodes;
charras's avatar
charras committed
645
            lastclos = ClosNodes;
646
            lastmove = MoveNodes;
647 648
            msg.Printf( wxT( "Activity: Open %d   Closed %d   Moved %d" ),
                        OpenNodes, ClosNodes, MoveNodes );
649
            pcbframe->SetStatusText( msg );
650
        }
charras's avatar
charras committed
651

652
        _self = 0;
653

654 655 656
        if( curcell & HOLE )
        {
            _self = 5;
657

658 659 660 661
            /* set 'present' bits */
            for( i = 0; i < 8; i++ )
            {
                selfok2[i].present = 0;
662

663
                if( curcell & selfok2[i].trace )
664 665 666 667 668 669
                    selfok2[i].present = 1;
            }
        }

        for( i = 0; i < 8; i++ ) /* consider neighbors */
        {
670 671
            nr = r + delta[i][0];
            nc = c + delta[i][1];
672 673

            /* off the edge? */
674 675
            if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
                nc < 0 || nc >= RoutingMatrix.m_Ncols )
676
                continue;  /* off the edge */
677 678 679

            if( _self == 5 && selfok2[i].present )
                continue;
680

681
            newcell = RoutingMatrix.GetCell( nr, nc, side );
682

683 684 685 686 687 688 689 690 691 692 693
            if( newcell & CURRENT_PAD )
                newcell &= ~HOLE;

            /* check for non-target hole */
            if( newcell & HOLE )
            {
                if( nr != row_target || nc != col_target )
                    continue;
            }
            /* check for traces */
            else if( newcell & HOLE & ~(newmask[i]) )
694
            {
695
                continue;
696
            }
697 698 699 700 701

            /* check blocking on corner neighbors */
            if( delta[i][0] && delta[i][1] )
            {
                /* check first buddy */
702
                buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side );
703

704 705
                if( buddy & CURRENT_PAD )
                    buddy &= ~HOLE;
706

707 708 709
                if( buddy & HOLE )
                    continue;

710
//              if (buddy & (blocking[i].b1)) continue;
711
                /* check second buddy */
712
                buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side );
713

714 715
                if( buddy & CURRENT_PAD )
                    buddy &= ~HOLE;
716

717 718 719
                if( buddy & HOLE )
                    continue;

720
//              if (buddy & (blocking[i].b2)) continue;
721 722
            }

723
            olddir  = RoutingMatrix.GetDir( r, c, side );
724
            newdist = d + RoutingMatrix.CalcDist( ndir[i], olddir,
725
                                    ( olddir == FROM_OTHERSIDE ) ?
726
                                    RoutingMatrix.GetDir( r, c, 1 - side ) : 0, side );
727 728 729

            /* if (a) not visited yet, or (b) we have */
            /* found a better path, add it to queue */
730
            if( !RoutingMatrix.GetDir( nr, nc, side ) )
731
            {
732 733
                RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
                RoutingMatrix.SetDist( nr, nc, side, newdist );
734

735
                if( SetQueue( nr, nc, side, newdist,
736
                              RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
737
                              row_target, col_target ) == 0 )
738 739 740 741
                {
                    return ERR_MEMORY;
                }
            }
742
            else if( newdist < RoutingMatrix.GetDist( nr, nc, side ) )
743
            {
744 745
                RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
                RoutingMatrix.SetDist( nr, nc, side, newdist );
746
                ReSetQueue( nr, nc, side, newdist,
747
                            RoutingMatrix.GetApxDist( nr, nc, row_target, col_target ),
748
                            row_target, col_target );
749 750 751
            }
        }

752
        /** Test the other layer. **/
753
        if( two_sides )
754
        {
755
            olddir = RoutingMatrix.GetDir( r, c, side );
756

757 758
            if( olddir == FROM_OTHERSIDE )
                continue;   /* useless move, so don't bother */
759

760 761
            if( curcell )   /* can't drill via if anything here */
                continue;
762

763
            /* check for holes or traces on other side */
764
            if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 )
765
                continue;
766

767 768 769 770 771
            /* check for nearby holes or traces on both sides */
            for( skip = 0, i = 0; i < 8; i++ )
            {
                nr = r + delta[i][0]; nc = c + delta[i][1];

772 773
                if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
                    nc < 0 || nc >= RoutingMatrix.m_Ncols )
774
                    continue;  /* off the edge !! */
775

776
                if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i]*/ )
777 778 779 780 781
                {
                    skip = 1; /* can't drill via here */
                    break;
                }

782
                if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i]*/ )
783 784 785 786 787 788 789 790 791
                {
                    skip = 1; /* can't drill via here */
                    break;
                }
            }

            if( skip )      /* neighboring hole or trace? */
                continue;   /* yes, can't drill via here */

792
            newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side );
793 794 795 796

            /*  if (a) not visited yet,
             *  or (b) we have found a better path,
             *  add it to queue */
797
            if( !RoutingMatrix.GetDir( r, c, 1 - side ) )
798
            {
799 800
                RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
                RoutingMatrix.SetDist( r, c, 1 - side, newdist );
801 802

                if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 )
803 804 805 806
                {
                    return ERR_MEMORY;
                }
            }
807
            else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) )
808
            {
809 810 811
                RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
                RoutingMatrix.SetDist( r, c, 1 - side, newdist );
                ReSetQueue( r, c,
812 813 814 815 816
                            1 - side,
                            newdist,
                            apx_dist,
                            row_target,
                            col_target );
817
            }
818
        }     /* Finished attempt to route on other layer. */
819
    }
820 821

end_of_route:
822 823
    PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL );
    PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL );
824

825 826
    msg.Printf( wxT( "Activity: Open %d   Closed %d   Moved %d"),
                OpenNodes, ClosNodes, MoveNodes );
827
    pcbframe->SetStatusText( msg );
charras's avatar
charras committed
828

829
    return result;
830 831
}

832

833 834 835
static long bit[8][9] =
{
    /* OT=Otherside */
836
    /* N, NE, E, SE, S, SW, W, NW, OT */
837
/* N */
838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
    { LINE_VERTICAL,
      BENT_StoNE,
      CORNER_SOUTHEAST,
      SHARP_StoSE,
      0,
      SHARP_StoSW,
      CORNER_SOUTHWEST,
      BENT_StoNW,
      ( HOLE | HOLE_SOUTH )
    },
/* NE */
    {
        BENT_NtoSW,
        DIAG_NEtoSW,
        BENT_EtoSW,
        ANGLE_SEtoSW,
        SHARP_StoSW,
        0,
        SHARP_WtoSW,
        ANGLE_SWtoNW,
        ( HOLE | HOLE_SOUTHWEST )
    },
/* E */
    {
        CORNER_NORTHWEST,
        BENT_WtoNE,
        LINE_HORIZONTAL,
        BENT_WtoSE,
        CORNER_SOUTHWEST,
        SHARP_WtoSW,
        0,
        SHARP_WtoNW,
        ( HOLE | HOLE_WEST )
    },
/* SE */
    {
        SHARP_NtoNW,
        ANGLE_NWtoNE,
        BENT_EtoNW,
        DIAG_SEtoNW,
        BENT_StoNW,
        ANGLE_SWtoNW,
        SHARP_WtoNW,
        0,
        ( HOLE | HOLE_NORTHWEST )
    },
/* S */
    {
        0,
        SHARP_NtoNE,
        CORNER_NORTHEAST,
        BENT_NtoSE,
        LINE_VERTICAL,
        BENT_NtoSW,
        CORNER_NORTHWEST,
        SHARP_NtoNW,
        ( HOLE | HOLE_NORTH )
    },
/* SW */
    {
        SHARP_NtoNE,
        0,
        SHARP_EtoNE,
        ANGLE_NEtoSE,
        BENT_StoNE,
        DIAG_NEtoSW,
        BENT_WtoNE,
        ANGLE_NWtoNE,
        ( HOLE | HOLE_NORTHEAST )
    },
/* W */
    {
        CORNER_NORTHEAST,
        SHARP_EtoNE,
        0,
        SHARP_EtoSE,
        CORNER_SOUTHEAST,
        BENT_EtoSW,
        LINE_HORIZONTAL,
        BENT_EtoNW,
        ( HOLE | HOLE_EAST )
    },
/* NW */
    {
        BENT_NtoSE,
        ANGLE_NEtoSE,
        SHARP_EtoSE,
        0,
        SHARP_StoSE,
        ANGLE_SEtoSW,
        BENT_WtoSE,
        DIAG_SEtoNW,
        ( HOLE | HOLE_SOUTHEAST )
    }
932
};
933

934

935
/* work from target back to source, actually laying the traces
936 937 938 939 940 941
 *  Parameters:
 *      start on side target_side, of coordinates row_target, col_target.
 *      arrive on side masque_layer_start, coordinate row_source, col_source
 * The search is done in reverse routing, the point of arrival (target) to
 * the starting point (source)
 * The router.
942
 *
943 944
 * Target_side = symbol (TOP / BOTTOM) of departure
 * = Mask_layer_source mask layers Arrival
945
 *
946 947 948
 * Returns:
 * 0 if error
 * > 0 if Ok
949
 */
950
static int Retrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC,
951 952 953
                    int row_source, int col_source,
                    int row_target, int col_target, int target_side,
                    int current_net_code )
954
{
955
    int  r0, c0, s0;
956 957
    int  r1, c1, s1;    /* row, col, starting side. */
    int  r2, c2, s2;    /* row, col, ending side. */
958 959 960 961 962 963 964 965
    int  x, y = -1;
    long b;

    r1 = row_target;
    c1 = col_target;    /* start point is target ( end point is source )*/
    s1 = target_side;
    r0 = c0 = s0 = ILLEGAL;

966
    wxASSERT( g_CurrentTrackList.GetCount() == 0 );
967

968 969
    do
    {
970 971
        /* find where we came from to get here */
        r2 = r1; c2 = c1; s2 = s1;
972
        x  = RoutingMatrix.GetDir( r1, c1, s1 );
973 974 975 976

        switch( x )
        {
        case FROM_NORTH:
977 978
            r2++;
            break;
979 980

        case FROM_EAST:
981 982
            c2++;
            break;
983 984

        case FROM_SOUTH:
985 986
            r2--;
            break;
987 988

        case FROM_WEST:
989 990
            c2--;
            break;
991 992

        case FROM_NORTHEAST:
993 994 995
            r2++;
            c2++;
            break;
996 997

        case FROM_SOUTHEAST:
998 999 1000
            r2--;
            c2++;
            break;
1001 1002

        case FROM_SOUTHWEST:
1003 1004 1005
            r2--;
            c2--;
            break;
1006 1007

        case FROM_NORTHWEST:
1008 1009 1010
            r2++;
            c2--;
            break;
1011 1012

        case FROM_OTHERSIDE:
1013 1014
            s2 = 1 - s2;
            break;
1015 1016

        default:
1017
            wxMessageBox( wxT( "Retrace: internal error: no way back" ) );
1018 1019 1020 1021
            return 0;
        }

        if( r0 != ILLEGAL )
1022
            y = RoutingMatrix.GetDir( r0, c0, s0 );
1023 1024

        /* see if target or hole */
1025
        if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) )
1026 1027 1028 1029 1030 1031
        {
            int p_dir;

            switch( x )
            {
            case FROM_NORTH:
1032 1033
                p_dir = HOLE_NORTH;
                break;
1034 1035

            case FROM_EAST:
1036 1037
                p_dir = HOLE_EAST;
                break;
1038 1039

            case FROM_SOUTH:
1040 1041
                p_dir = HOLE_SOUTH;
                break;
1042 1043

            case FROM_WEST:
1044 1045
                p_dir = HOLE_WEST;
                break;
1046 1047

            case FROM_NORTHEAST:
1048 1049
                p_dir = HOLE_NORTHEAST;
                break;
1050 1051

            case FROM_SOUTHEAST:
1052 1053
                p_dir = HOLE_SOUTHEAST;
                break;
1054 1055

            case FROM_SOUTHWEST:
1056 1057
                p_dir = HOLE_SOUTHWEST;
                break;
1058 1059

            case FROM_NORTHWEST:
1060 1061
                p_dir = HOLE_NORTHWEST;
                break;
1062 1063 1064 1065 1066 1067 1068

            case FROM_OTHERSIDE:
            default:
                DisplayError( pcbframe, wxT( "Retrace: error 1" ) );
                return 0;
            }

1069
            OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, p_dir, current_net_code );
1070 1071 1072
        }
        else
        {
1073 1074 1075 1076 1077 1078 1079 1080 1081 1082
            if( ( y == FROM_NORTH || y == FROM_NORTHEAST
                  || y == FROM_EAST || y == FROM_SOUTHEAST
                  || y == FROM_SOUTH || y == FROM_SOUTHWEST
                  || y == FROM_WEST || y == FROM_NORTHWEST )
               && ( x == FROM_NORTH || x == FROM_NORTHEAST
                    || x == FROM_EAST || x == FROM_SOUTHEAST
                    || x == FROM_SOUTH || x == FROM_SOUTHWEST
                    || x == FROM_WEST || x == FROM_NORTHWEST
                    || x == FROM_OTHERSIDE )
               && ( ( b = bit[y - 1][x - 1] ) != 0 ) )
1083
            {
1084 1085
                OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, b, current_net_code );

1086
                if( b & HOLE )
1087
                    OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, HOLE, current_net_code );
1088 1089 1090
            }
            else
            {
1091
                wxMessageBox( wxT( "Retrace: error 2" ) );
1092 1093 1094 1095
                return 0;
            }
        }

1096 1097
        if( ( r2 == row_source ) && ( c2 == col_source ) ) /* see if source */
        {
1098 1099 1100 1101 1102
            int p_dir;

            switch( x )
            {
            case FROM_NORTH:
1103 1104
                p_dir = HOLE_SOUTH;
                break;
1105 1106

            case FROM_EAST:
1107 1108
                p_dir = HOLE_WEST;
                break;
1109 1110

            case FROM_SOUTH:
1111 1112
                p_dir = HOLE_NORTH;
                break;
1113 1114

            case FROM_WEST:
1115 1116
                p_dir = HOLE_EAST;
                break;
1117 1118

            case FROM_NORTHEAST:
1119 1120
                p_dir = HOLE_SOUTHWEST;
                break;
1121 1122

            case FROM_SOUTHEAST:
1123 1124
                p_dir = HOLE_NORTHWEST;
                break;
1125 1126

            case FROM_SOUTHWEST:
1127 1128
                p_dir = HOLE_NORTHEAST;
                break;
1129 1130

            case FROM_NORTHWEST:
1131 1132
                p_dir = HOLE_SOUTHEAST;
                break;
1133 1134 1135

            case FROM_OTHERSIDE:
            default:
1136
                wxMessageBox( wxT( "Retrace: error 3" ) );
1137 1138 1139
                return 0;
            }

1140
            OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, p_dir, current_net_code );
1141
        }
1142

1143
        /* move to next cell */
1144 1145 1146 1147 1148 1149 1150
        r0 = r1;
        c0 = c1;
        s0 = s1;
        r1 = r2;
        c1 = c2;
        s1 = s2;
    } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) );
1151

1152
    AddNewTrace( pcbframe, DC );
1153
    return 1;
1154 1155 1156
}


1157 1158 1159
/* This function is used by Retrace and read the autorouting matrix data cells to create
 * the real track on the physical board
 */
1160 1161
static void OrCell_Trace( BOARD* pcb, int col, int row,
                          int side, int orient, int current_net_code )
1162
{
1163
    int    dx0, dy0, dx1, dy1;
1164
    TRACK* newTrack;
1165

1166
    if( orient == HOLE )  // placement of a via
1167
    {
1168
        newTrack = new SEGVIA( pcb );
1169

1170
        g_CurrentTrackList.PushBack( newTrack );
1171

1172
        g_CurrentTrackSegment->SetState( TRACK_AR, true );
1173
        g_CurrentTrackSegment->SetLayer( 0x0F );
1174

1175
        g_CurrentTrackSegment->SetStart(wxPoint( pcb->GetBoundingBox().GetX() +
1176
                                                ( RoutingMatrix.m_GridRouting * row ),
1177 1178 1179
                                                pcb->GetBoundingBox().GetY() +
                                                ( RoutingMatrix.m_GridRouting * col )));
        g_CurrentTrackSegment->SetEnd( g_CurrentTrackSegment->GetStart() );
1180

1181 1182
        g_CurrentTrackSegment->SetWidth( pcb->GetCurrentViaSize() );
        g_CurrentTrackSegment->SetShape( pcb->GetDesignSettings().m_CurrentViaType );
1183

1184
        g_CurrentTrackSegment->SetNet( current_net_code );
1185
    }
1186
    else    // placement of a standard segment
1187
    {
1188
        newTrack = new TRACK( pcb );
1189

1190
        g_CurrentTrackList.PushBack( newTrack );
1191

1192
        g_CurrentTrackSegment->SetLayer( g_Route_Layer_BOTTOM );
1193

1194
        if( side == TOP )
1195
            g_CurrentTrackSegment->SetLayer( g_Route_Layer_TOP );
1196

1197
        g_CurrentTrackSegment->SetState( TRACK_AR, true );
1198 1199 1200 1201
        g_CurrentTrackSegment->SetEnd( wxPoint( pcb->GetBoundingBox().GetX() +
                                         ( RoutingMatrix.m_GridRouting * row ),
                                         pcb->GetBoundingBox().GetY() +
                                         ( RoutingMatrix.m_GridRouting * col )));
1202
        g_CurrentTrackSegment->SetNet( current_net_code );
1203

1204
        if( g_CurrentTrackSegment->Back() == NULL ) /* Start trace. */
1205
        {
1206
            g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) );
1207

1208
            /* Placement on the center of the pad if outside grid. */
1209 1210
            dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
            dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1211

1212 1213
            dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
            dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1214

1215 1216
            /* If aligned, change the origin point. */
            if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1217
            {
1218
                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1219
            }
1220
            else    // Creation of a supplemental segment
1221
            {
1222
                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1223

1224
                newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1225
                newTrack->SetStart( g_CurrentTrackSegment->GetEnd());
1226

1227
                g_CurrentTrackList.PushBack( newTrack );
1228 1229 1230 1231
            }
        }
        else
        {
1232
            if( g_CurrentTrackSegment->Back() )
1233
            {
1234
                g_CurrentTrackSegment->SetStart( g_CurrentTrackSegment->Back()->GetEnd() );
1235 1236
            }
        }
1237

1238
        g_CurrentTrackSegment->SetWidth( pcb->GetCurrentTrackWidth() );
1239

1240
        if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() )
1241
        {
1242
            /* Reduce aligned segments by one. */
1243
            TRACK* oldTrack = g_CurrentTrackSegment->Back();
1244

1245
            if( oldTrack &&  oldTrack->Type() != PCB_VIA_T )
1246
            {
1247 1248
                dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
                dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1249

1250 1251
                dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x;
                dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y;
1252

1253
                if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1254
                {
1255
                    oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() );
1256 1257

                    delete g_CurrentTrackList.PopBack();
1258 1259 1260 1261
                }
            }
        }
    }
1262 1263
}

1264

1265 1266 1267 1268
/* Insert the new track created in the list of tracks.
 * amend the points of beginning and end of the track so that they are
 * connected
 * Center on pads even if they are off grid.
1269
 */
1270
static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC )
1271
{
1272 1273 1274 1275 1276
    if( g_FirstTrackSegment == NULL )
        return;

    int dx0, dy0, dx1, dy1;
    int marge, via_marge;
1277
    EDA_DRAW_PANEL* panel = pcbframe->GetCanvas();
1278
    PCB_SCREEN* screen = pcbframe->GetScreen();
1279

1280
    marge = s_Clearance + ( pcbframe->GetBoard()->GetCurrentTrackWidth() / 2 );
1281
    via_marge = s_Clearance + ( pcbframe->GetBoard()->GetCurrentViaSize() / 2 );
1282

1283 1284
    dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
    dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1285

1286
    /* Place on center of pad if off grid. */
1287 1288
    dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
    dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1289

1290 1291
    /* If aligned, change the origin point. */
    if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1292
    {
1293
        g_CurrentTrackSegment->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
1294
    }
1295
    else
1296
    {
1297
        TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1298

1299 1300
        newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
        newTrack->SetStart( g_CurrentTrackSegment->GetEnd() );
1301

1302
        g_CurrentTrackList.PushBack( newTrack );
1303
    }
1304

1305
    g_FirstTrackSegment->start = pcbframe->GetBoard()->GetPad( g_FirstTrackSegment, FLG_START );
1306

1307
    if( g_FirstTrackSegment->start )
1308
        g_FirstTrackSegment->SetState( BEGIN_ONPAD, true );
1309

1310
    g_CurrentTrackSegment->end = pcbframe->GetBoard()->GetPad( g_CurrentTrackSegment, FLG_END );
1311

1312
    if( g_CurrentTrackSegment->end )
1313
        g_CurrentTrackSegment->SetState( END_ONPAD, true );
1314

1315
    /* Out the new track on the matrix board */
1316
    for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() )
1317
    {
1318 1319
        TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
        TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
1320
    }
1321

1322 1323 1324 1325 1326 1327 1328
    // Insert new segments in  real board
    int    netcode    = g_FirstTrackSegment->GetNet();
    TRACK* firstTrack = g_FirstTrackSegment;
    int    newCount   = g_CurrentTrackList.GetCount();

    // Put entire new current segment list in BOARD
    TRACK* track;
1329
    TRACK* insertBeforeMe = g_CurrentTrackSegment->GetBestInsertPoint( pcbframe->GetBoard() );
1330

1331 1332
    while( ( track = g_CurrentTrackList.PopFront() ) != NULL )
    {
1333 1334
        ITEM_PICKER picker( track, UR_NEW );
        s_ItemsListPicker.PushItem( picker );
1335 1336 1337
        pcbframe->GetBoard()->m_Track.Insert( track, insertBeforeMe );
    }

1338
    DrawTraces( panel, DC, firstTrack, newCount, GR_OR );
1339

1340
    pcbframe->TestNetConnection( DC, netcode );
1341

1342
    screen->SetModify();
1343
}