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
/* Route all traces
265
 * :
266 267 268
 *  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 328 329 330
        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);
331 332

        /* Draw segment. */
333 334
        GRLine( m_canvas->GetClipBox(), DC,
                segm_oX, segm_oY, segm_fX, segm_fY,
335
                0, WHITE );
336 337
        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 );
338

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

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

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

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

        default:
            nbsucces++;
            break;
        }

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

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

        if( stop )
            break;
    }

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

381
    return SUCCESS;
382 383
}

384

385 386 387 388 389 390 391
/* 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
392
 *
393 394
 * Returns:
 * SUCCESS if routed
395
 * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed)
396 397 398
 * If failure NOSUCCESS
 * Escape STOP_FROM_ESC if demand
 * ERR_MEMORY if memory allocation failed.
399
 */
400 401 402 403 404 405 406
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,
407
                                RATSNEST_ITEM*  pt_rat )
408
{
409 410 411 412 413 414
    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;
415
    int          marge;
416 417
    int          padLayerMaskStart;    /* Mask layers belonging to the starting pad. */
    int          padLayerMaskEnd;      /* Mask layers belonging to the ending pad. */
418 419
    int          topLayerMask = GetLayerMask( g_Route_Layer_TOP );
    int          bottomLayerMask = GetLayerMask( g_Route_Layer_BOTTOM );
420 421
    int          routeLayerMask;       /* Mask two layers for routing. */
    int          tab_mask[2];       /* Enables the calculation of the mask layer being
422 423 424 425 426 427
                                     * tested. (side = TOP or BOTTOM) */
    int          start_mask_layer = 0;
    wxString     msg;

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

429 430
    result = NOSUCCESS;

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

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

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

    lastopen = lastclos = lastmove = 0;

442
    /* Set tab_masque[side] for final test of routing. */
443 444
    if( two_sides )
        tab_mask[TOP]    = topLayerMask;
445
    tab_mask[BOTTOM] = bottomLayerMask;
446

447
    /* Set active layers mask. */
448
    routeLayerMask = topLayerMask | bottomLayerMask;
449

450
    pt_cur_ch = pt_rat;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
451 452 453 454 455

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

651
        _self = 0;
652

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

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

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

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

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

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

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

682 683 684 685 686 687 688 689 690 691 692
            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]) )
693
            {
694
                continue;
695
            }
696 697 698 699 700

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

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

706 707 708
                if( buddy & HOLE )
                    continue;

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

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

716 717 718
                if( buddy & HOLE )
                    continue;

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

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

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

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

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

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

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

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

766 767 768 769 770
            /* 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];

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

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

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

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

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

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

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

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

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

828
    return result;
829 830
}

831

832 833 834
static long bit[8][9] =
{
    /* OT=Otherside */
835
    /* N, NE, E, SE, S, SW, W, NW, OT */
836
/* N */
837 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
    { 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 )
    }
931
};
932

933

934
/* work from target back to source, actually laying the traces
935 936 937 938 939 940
 *  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.
941
 *
942 943
 * Target_side = symbol (TOP / BOTTOM) of departure
 * = Mask_layer_source mask layers Arrival
944
 *
945 946 947
 * Returns:
 * 0 if error
 * > 0 if Ok
948
 */
949
static int Retrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC,
950 951 952
                    int row_source, int col_source,
                    int row_target, int col_target, int target_side,
                    int current_net_code )
953
{
954
    int  r0, c0, s0;
955 956
    int  r1, c1, s1;    /* row, col, starting side. */
    int  r2, c2, s2;    /* row, col, ending side. */
957 958 959 960 961 962 963 964
    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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1068
            OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, p_dir, current_net_code );
1069 1070 1071
        }
        else
        {
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081
            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 ) )
1082
            {
1083 1084
                OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, b, current_net_code );

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

1169
        g_CurrentTrackList.PushBack( newTrack );
1170

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

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

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

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

1189
        g_CurrentTrackList.PushBack( newTrack );
1190

1191
        g_CurrentTrackSegment->SetLayer( g_Route_Layer_BOTTOM );
1192

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1263

1264 1265 1266 1267
/* 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.
1268
 */
1269
static void AddNewTrace( PCB_EDIT_FRAME* pcbframe, wxDC* DC )
1270
{
1271 1272 1273 1274 1275
    if( g_FirstTrackSegment == NULL )
        return;

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

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

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

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

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

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

1301
        g_CurrentTrackList.PushBack( newTrack );
1302
    }
1303

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

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

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

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

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

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

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

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

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

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

1341
    screen->SetModify();
1342
}