solve.cpp 41.7 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
#include <fctsys.h>
#include <class_drawpanel.h>
#include <confirm.h>
#include <wxPcbStruct.h>
#include <gr_basic.h>
#include <macros.h>
42

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

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

51

52 53 54 55 56 57 58
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,
59
                                RATSNEST_ITEM*  pt_rat );
60

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

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

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

79 80 81 82

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

86 87
static PICKED_ITEMS_LIST s_ItemsListPicker;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
88 89 90 91
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
92

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

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

111 112 113 114
/* 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.
 */
115
static const int delta[8][2] =
116
{
Dick Hollenbeck's avatar
Dick Hollenbeck committed
117 118 119 120 121 122 123 124
    {  1, -1 },     // northwest
    {  1, 0  },     // north
    {  1, 1  },     // northeast
    {  0, -1 },     // west
    {  0, 1  },     // east
    { -1, -1 },     // southwest
    { -1, 0  },     // south
    { -1, 1  }      // southeast
125
};
126

127
static const int ndir[8] =
128
{
Dick Hollenbeck's avatar
Dick Hollenbeck committed
129
    // for building paths back to source
130
    FROM_SOUTHEAST, FROM_SOUTH,     FROM_SOUTHWEST,
131
    FROM_EAST,      FROM_WEST,
132
    FROM_NORTHEAST, FROM_NORTH,     FROM_NORTHWEST
133
};
134

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

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
189
// blocking masks for diagonal traces
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
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
  } };
231

Dick Hollenbeck's avatar
Dick Hollenbeck committed
232
// mask for hole-related blocking effects
233 234 235 236
static struct
{
    long trace;
    int  present;
237 238 239 240 241 242 243 244 245 246
} 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 }
247
};
248

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


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

280
    m_canvas->SetAbortRequest( false );
281

282
    s_Clearance = GetBoard()->GetDesignSettings().GetDefault()->GetClearance();
283

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
287
    // go until no more work to do
288
    GetWork( &row_source, &col_source, &current_net_code,
289
             &row_target, &col_target, &pt_cur_ch ); // First net to route.
290 291

    for( ; row_source != ILLEGAL; GetWork( &row_source, &col_source,
292 293
                                           &current_net_code, &row_target,
                                           &col_target,
294
                                           &pt_cur_ch ) )
295
    {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
296
        // Test to stop routing ( escape key pressed )
297
        wxYield();
298

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

313 314
        EraseMsgBox();

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

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

326 327 328 329
        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);
330

Dick Hollenbeck's avatar
Dick Hollenbeck committed
331
        // Draw segment.
332 333
        GRLine( m_canvas->GetClipBox(), DC,
                segm_oX, segm_oY, segm_fX, segm_fY,
334
                0, WHITE );
335 336
        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 );
337

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

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

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

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

        default:
            nbsucces++;
            break;
        }

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
369
        // Delete routing from display.
370 371
        pt_cur_ch->m_PadStart->Draw( m_canvas, DC, GR_AND );
        pt_cur_ch->m_PadEnd->Draw( m_canvas, DC, GR_AND );
372 373 374 375 376

        if( stop )
            break;
    }

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

380
    return SUCCESS;
381 382
}

383

384 385 386 387 388 389 390
/* 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
391
 *
392 393
 * Returns:
 * SUCCESS if routed
394
 * TRIVIAL_SUCCESS if pads are connected by overlay (no track needed)
395 396 397
 * If failure NOSUCCESS
 * Escape STOP_FROM_ESC if demand
 * ERR_MEMORY if memory allocation failed.
398
 */
399 400 401 402 403 404 405
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,
406
                                RATSNEST_ITEM*  pt_rat )
407
{
408 409 410 411 412 413
    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;
414
    int          marge;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
415 416 417 418 419 420 421 422 423 424 425
    LSET         padLayerMaskStart;    // Mask layers belonging to the starting pad.
    LSET         padLayerMaskEnd;      // Mask layers belonging to the ending pad.

    LSET         topLayerMask( g_Route_Layer_TOP );

    LSET         bottomLayerMask( g_Route_Layer_BOTTOM );

    LSET         routeLayerMask;       // Mask two layers for routing.

    LSET         tab_mask[2];           // Enables the calculation of the mask layer being
                                        // tested. (side = TOP or BOTTOM)
426 427 428
    int          start_mask_layer = 0;
    wxString     msg;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
429 430 431
    // @todo this could be a bottle neck
    LSET all_cu = LSET::AllCuMask( pcbframe->GetBoard()->GetCopperLayerCount() );

432 433
    wxBusyCursor dummy_cursor;      // Set an hourglass cursor while routing a
                                    // track
434

435 436
    result = NOSUCCESS;

437
    marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
438

Dick Hollenbeck's avatar
Dick Hollenbeck committed
439
    // clear direction flags
440
    i = RoutingMatrix.m_Nrows * RoutingMatrix.m_Ncols * sizeof(DIR_CELL);
441 442 443

    if( two_sides )
        memset( RoutingMatrix.m_DirSide[TOP], FROM_NOWHERE, i );
444
    memset( RoutingMatrix.m_DirSide[BOTTOM], FROM_NOWHERE, i );
445 446 447

    lastopen = lastclos = lastmove = 0;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
448
    // Set tab_masque[side] for final test of routing.
449
    if( two_sides )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
450
        tab_mask[TOP] = topLayerMask;
451
    tab_mask[BOTTOM] = bottomLayerMask;
452

Dick Hollenbeck's avatar
Dick Hollenbeck committed
453
    // Set active layers mask.
454
    routeLayerMask = topLayerMask | bottomLayerMask;
455

456
    pt_cur_ch = pt_rat;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
457 458

    current_net_code  = pt_rat->GetNet();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
459
    padLayerMaskStart = pt_cur_ch->m_PadStart->GetLayerSet();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
460

Dick Hollenbeck's avatar
Dick Hollenbeck committed
461
    padLayerMaskEnd = pt_cur_ch->m_PadEnd->GetLayerSet();
462 463


464 465 466
    /* First Test if routing possible ie if the pads are accessible
     * on the routing layers.
     */
467
    if( ( routeLayerMask & padLayerMaskStart ) == 0 )
468
        goto end_of_route;
469 470

    if( ( routeLayerMask & padLayerMaskEnd ) == 0 )
471 472
        goto end_of_route;

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

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

489
        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
490 491
            goto end_of_route;

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

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

504
        if( ( abs( cX - px ) > dx ) || ( abs( cY - py ) > dy ) )
505 506 507
            goto end_of_route;
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
508 509 510
    // Test the trivial case: direct connection overlay pads.
    if( row_source == row_target  && col_source == col_target &&
            ( padLayerMaskEnd & padLayerMaskStart & all_cu ).any() )
511 512 513 514 515
    {
        result = TRIVIAL_SUCCESS;
        goto end_of_route;
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
516
    // Placing the bit to remove obstacles on 2 pads to a link.
517
    pcbframe->SetStatusText( wxT( "Gen Cells" ) );
518

519 520
    PlacePad( pt_cur_ch->m_PadStart, CURRENT_PAD, marge, WRITE_OR_CELL );
    PlacePad( pt_cur_ch->m_PadEnd, CURRENT_PAD, marge, WRITE_OR_CELL );
521

Dick Hollenbeck's avatar
Dick Hollenbeck committed
522 523
    // Regenerates the remaining barriers (which may encroach on the
    // placement bits precedent)
524
    i = pcbframe->GetBoard()->GetPadCount();
525

526
    for( unsigned ii = 0; ii < pcbframe->GetBoard()->GetPadCount(); ii++ )
527
    {
528
        D_PAD* ptr = pcbframe->GetBoard()->GetPad( ii );
529

530
        if( ( pt_cur_ch->m_PadStart != ptr ) && ( pt_cur_ch->m_PadEnd != ptr ) )
531
        {
532
            PlacePad( ptr, ~CURRENT_PAD, marge, WRITE_AND_CELL );
533 534 535
        }
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
536
    InitQueue(); // initialize the search queue
537
    apx_dist = RoutingMatrix.GetApxDist( row_source, col_source, row_target, col_target );
538

Dick Hollenbeck's avatar
Dick Hollenbeck committed
539 540
    // Initialize first search.
    if( two_sides )   // Preferred orientation.
541 542 543
    {
        if( abs( row_target - row_source ) > abs( col_target - col_source ) )
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
544
            if( ( padLayerMaskStart & topLayerMask ).any() )
545 546
            {
                start_mask_layer = 2;
547

548
                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
549
                              row_target, col_target ) == 0 )
550 551 552 553
                {
                    return ERR_MEMORY;
                }
            }
554

Dick Hollenbeck's avatar
Dick Hollenbeck committed
555
            if( ( padLayerMaskStart & bottomLayerMask ).any() )
556 557 558 559
            {
                start_mask_layer |= 1;

                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
560
                              row_target, col_target ) == 0 )
561 562 563 564 565 566 567
                {
                    return ERR_MEMORY;
                }
            }
        }
        else
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
568
            if( ( padLayerMaskStart & bottomLayerMask ).any() )
569 570
            {
                start_mask_layer = 1;
571

572
                if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist,
573
                              row_target, col_target ) == 0 )
574 575 576 577
                {
                    return ERR_MEMORY;
                }
            }
578

Dick Hollenbeck's avatar
Dick Hollenbeck committed
579
            if( ( padLayerMaskStart & topLayerMask ).any() )
580 581 582 583
            {
                start_mask_layer |= 2;

                if( SetQueue( row_source, col_source, TOP, 0, apx_dist,
584
                              row_target, col_target ) == 0 )
585 586 587 588 589 590
                {
                    return ERR_MEMORY;
                }
            }
        }
    }
Dick Hollenbeck's avatar
Dick Hollenbeck committed
591
    else if( ( padLayerMaskStart & bottomLayerMask ).any() )
592 593 594
    {
        start_mask_layer = 1;

595
        if( SetQueue( row_source, col_source, BOTTOM, 0, apx_dist, row_target, col_target ) == 0 )
596 597 598 599 600
        {
            return ERR_MEMORY;
        }
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
601
    // search until success or we exhaust all possibilities
602
    GetQueue( &r, &c, &side, &d, &apx_dist );
603

604 605
    for( ; r != ILLEGAL; GetQueue( &r, &c, &side, &d, &apx_dist ) )
    {
606
        curcell = RoutingMatrix.GetCell( r, c, side );
607

608 609
        if( curcell & CURRENT_PAD )
            curcell &= ~HOLE;
610

Dick Hollenbeck's avatar
Dick Hollenbeck committed
611 612
        if( (r == row_target) && (c == col_target)  // success if layer OK
           && (tab_mask[side] & padLayerMaskEnd).any() )
613
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
614
            // Remove link.
615
            GRSetDrawMode( DC, GR_XOR );
616
            GRLine( pcbframe->GetCanvas()->GetClipBox(),
617 618 619 620 621 622 623
                    DC,
                    segm_oX,
                    segm_oY,
                    segm_fX,
                    segm_fY,
                    0,
                    WHITE );
624

Dick Hollenbeck's avatar
Dick Hollenbeck committed
625
            // Generate trace.
626
            if( Retrace( pcbframe, DC, row_source, col_source,
627
                         row_target, col_target, side, current_net_code ) )
628
            {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
629
                result = SUCCESS;   // Success : Route OK
630
            }
631

Dick Hollenbeck's avatar
Dick Hollenbeck committed
632
            break;                  // Routing complete.
633 634
        }

635
        if( pcbframe->GetCanvas()->GetAbortRequest() )
636
        {
637 638
            result = STOP_FROM_ESC;
            break;
639 640
        }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
641
        // report every COUNT new nodes or so
charras's avatar
charras committed
642
        #define COUNT 20000
643

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

656
        _self = 0;
657

658 659 660
        if( curcell & HOLE )
        {
            _self = 5;
661

Dick Hollenbeck's avatar
Dick Hollenbeck committed
662
            // set 'present' bits
663 664 665
            for( i = 0; i < 8; i++ )
            {
                selfok2[i].present = 0;
666

667
                if( curcell & selfok2[i].trace )
668 669 670 671
                    selfok2[i].present = 1;
            }
        }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
672
        for( i = 0; i < 8; i++ ) // consider neighbors
673
        {
674 675
            nr = r + delta[i][0];
            nc = c + delta[i][1];
676

Dick Hollenbeck's avatar
Dick Hollenbeck committed
677
            // off the edge?
678 679
            if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
                nc < 0 || nc >= RoutingMatrix.m_Ncols )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
680
                continue;  // off the edge
681 682 683

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

685
            newcell = RoutingMatrix.GetCell( nr, nc, side );
686

687 688 689
            if( newcell & CURRENT_PAD )
                newcell &= ~HOLE;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
690
            // check for non-target hole
691 692 693 694 695
            if( newcell & HOLE )
            {
                if( nr != row_target || nc != col_target )
                    continue;
            }
Dick Hollenbeck's avatar
Dick Hollenbeck committed
696
            // check for traces
697
            else if( newcell & HOLE & ~(newmask[i]) )
698
            {
699
                continue;
700
            }
701

Dick Hollenbeck's avatar
Dick Hollenbeck committed
702
            // check blocking on corner neighbors
703 704
            if( delta[i][0] && delta[i][1] )
            {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
705
                // check first buddy
706
                buddy = RoutingMatrix.GetCell( r + blocking[i].r1, c + blocking[i].c1, side );
707

708 709
                if( buddy & CURRENT_PAD )
                    buddy &= ~HOLE;
710

711 712 713
                if( buddy & HOLE )
                    continue;

714
//              if (buddy & (blocking[i].b1)) continue;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
715
                // check second buddy
716
                buddy = RoutingMatrix.GetCell( r + blocking[i].r2, c + blocking[i].c2, side );
717

718 719
                if( buddy & CURRENT_PAD )
                    buddy &= ~HOLE;
720

721 722 723
                if( buddy & HOLE )
                    continue;

724
//              if (buddy & (blocking[i].b2)) continue;
725 726
            }

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
732 733
            // if (a) not visited yet, or (b) we have
            // found a better path, add it to queue
734
            if( !RoutingMatrix.GetDir( nr, nc, side ) )
735
            {
736 737
                RoutingMatrix.SetDir( nr, nc, side, ndir[i] );
                RoutingMatrix.SetDist( nr, nc, side, newdist );
738

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
756
        //* Test the other layer. *
757
        if( two_sides )
758
        {
759
            olddir = RoutingMatrix.GetDir( r, c, side );
760

761
            if( olddir == FROM_OTHERSIDE )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
762
                continue;   // useless move, so don't bother
763

Dick Hollenbeck's avatar
Dick Hollenbeck committed
764
            if( curcell )   // can't drill via if anything here
765
                continue;
766

Dick Hollenbeck's avatar
Dick Hollenbeck committed
767
            // check for holes or traces on other side
768
            if( ( newcell = RoutingMatrix.GetCell( r, c, 1 - side ) ) != 0 )
769
                continue;
770

Dick Hollenbeck's avatar
Dick Hollenbeck committed
771
            // check for nearby holes or traces on both sides
772 773 774 775
            for( skip = 0, i = 0; i < 8; i++ )
            {
                nr = r + delta[i][0]; nc = c + delta[i][1];

776 777
                if( nr < 0 || nr >= RoutingMatrix.m_Nrows ||
                    nc < 0 || nc >= RoutingMatrix.m_Ncols )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
778
                    continue;  // off the edge !!
779

Dick Hollenbeck's avatar
Dick Hollenbeck committed
780
                if( RoutingMatrix.GetCell( nr, nc, side ) /* & blocking2[i] */ )
781
                {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
782
                    skip = 1; // can't drill via here
783 784 785
                    break;
                }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
786
                if( RoutingMatrix.GetCell( nr, nc, 1 - side ) /* & blocking2[i] */ )
787
                {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
788
                    skip = 1; // can't drill via here
789 790 791 792
                    break;
                }
            }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
793 794
            if( skip )      // neighboring hole or trace?
                continue;   // yes, can't drill via here
795

796
            newdist = d + RoutingMatrix.CalcDist( FROM_OTHERSIDE, olddir, 0, side );
797 798 799 800

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

                if( SetQueue( r, c, 1 - side, newdist, apx_dist, row_target, col_target ) == 0 )
807 808 809 810
                {
                    return ERR_MEMORY;
                }
            }
811
            else if( newdist < RoutingMatrix.GetDist( r, c, 1 - side ) )
812
            {
813 814 815
                RoutingMatrix.SetDir( r, c, 1 - side, FROM_OTHERSIDE );
                RoutingMatrix.SetDist( r, c, 1 - side, newdist );
                ReSetQueue( r, c,
816 817 818 819 820
                            1 - side,
                            newdist,
                            apx_dist,
                            row_target,
                            col_target );
821
            }
Dick Hollenbeck's avatar
Dick Hollenbeck committed
822
        }     // Finished attempt to route on other layer.
823
    }
824 825

end_of_route:
826 827
    PlacePad( pt_cur_ch->m_PadStart, ~CURRENT_PAD, marge, WRITE_AND_CELL );
    PlacePad( pt_cur_ch->m_PadEnd, ~CURRENT_PAD, marge, WRITE_AND_CELL );
828

829 830
    msg.Printf( wxT( "Activity: Open %d   Closed %d   Moved %d"),
                OpenNodes, ClosNodes, MoveNodes );
831
    pcbframe->SetStatusText( msg );
charras's avatar
charras committed
832

833
    return result;
834 835
}

836

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

938

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

    r1 = row_target;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
966
    c1 = col_target;    // start point is target ( end point is source )
967 968 969
    s1 = target_side;
    r0 = c0 = s0 = ILLEGAL;

970
    wxASSERT( g_CurrentTrackList.GetCount() == 0 );
971

972 973
    do
    {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
974
        // find where we came from to get here
975
        r2 = r1; c2 = c1; s2 = s1;
976
        x  = RoutingMatrix.GetDir( r1, c1, s1 );
977 978 979 980

        switch( x )
        {
        case FROM_NORTH:
981 982
            r2++;
            break;
983 984

        case FROM_EAST:
985 986
            c2++;
            break;
987 988

        case FROM_SOUTH:
989 990
            r2--;
            break;
991 992

        case FROM_WEST:
993 994
            c2--;
            break;
995 996

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

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

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

        case FROM_NORTHWEST:
1012 1013 1014
            r2++;
            c2--;
            break;
1015 1016

        case FROM_OTHERSIDE:
1017 1018
            s2 = 1 - s2;
            break;
1019 1020

        default:
1021
            wxMessageBox( wxT( "Retrace: internal error: no way back" ) );
1022 1023 1024 1025
            return 0;
        }

        if( r0 != ILLEGAL )
1026
            y = RoutingMatrix.GetDir( r0, c0, s0 );
1027

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1028
        // see if target or hole
1029
        if( ( ( r1 == row_target ) && ( c1 == col_target ) ) || ( s1 != s0 ) )
1030 1031 1032 1033 1034 1035
        {
            int p_dir;

            switch( x )
            {
            case FROM_NORTH:
1036 1037
                p_dir = HOLE_NORTH;
                break;
1038 1039

            case FROM_EAST:
1040 1041
                p_dir = HOLE_EAST;
                break;
1042 1043

            case FROM_SOUTH:
1044 1045
                p_dir = HOLE_SOUTH;
                break;
1046 1047

            case FROM_WEST:
1048 1049
                p_dir = HOLE_WEST;
                break;
1050 1051

            case FROM_NORTHEAST:
1052 1053
                p_dir = HOLE_NORTHEAST;
                break;
1054 1055

            case FROM_SOUTHEAST:
1056 1057
                p_dir = HOLE_SOUTHEAST;
                break;
1058 1059

            case FROM_SOUTHWEST:
1060 1061
                p_dir = HOLE_SOUTHWEST;
                break;
1062 1063

            case FROM_NORTHWEST:
1064 1065
                p_dir = HOLE_NORTHWEST;
                break;
1066 1067 1068 1069 1070 1071 1072

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

1073
            OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, p_dir, current_net_code );
1074 1075 1076
        }
        else
        {
1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
            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 ) )
1087
            {
1088 1089
                OrCell_Trace( pcbframe->GetBoard(), r1, c1, s1, b, current_net_code );

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

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1100
        if( ( r2 == row_source ) && ( c2 == col_source ) ) // see if source
1101
        {
1102 1103 1104 1105 1106
            int p_dir;

            switch( x )
            {
            case FROM_NORTH:
1107 1108
                p_dir = HOLE_SOUTH;
                break;
1109 1110

            case FROM_EAST:
1111 1112
                p_dir = HOLE_WEST;
                break;
1113 1114

            case FROM_SOUTH:
1115 1116
                p_dir = HOLE_NORTH;
                break;
1117 1118

            case FROM_WEST:
1119 1120
                p_dir = HOLE_EAST;
                break;
1121 1122

            case FROM_NORTHEAST:
1123 1124
                p_dir = HOLE_SOUTHWEST;
                break;
1125 1126

            case FROM_SOUTHEAST:
1127 1128
                p_dir = HOLE_NORTHWEST;
                break;
1129 1130

            case FROM_SOUTHWEST:
1131 1132
                p_dir = HOLE_NORTHEAST;
                break;
1133 1134

            case FROM_NORTHWEST:
1135 1136
                p_dir = HOLE_SOUTHEAST;
                break;
1137 1138 1139

            case FROM_OTHERSIDE:
            default:
1140
                wxMessageBox( wxT( "Retrace: error 3" ) );
1141 1142 1143
                return 0;
            }

1144
            OrCell_Trace( pcbframe->GetBoard(), r2, c2, s2, p_dir, current_net_code );
1145
        }
1146

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1147
        // move to next cell
1148 1149 1150 1151 1152 1153 1154
        r0 = r1;
        c0 = c1;
        s0 = s1;
        r1 = r2;
        c1 = c2;
        s1 = s2;
    } while( !( ( r2 == row_source ) && ( c2 == col_source ) ) );
1155

1156
    AddNewTrace( pcbframe, DC );
1157
    return 1;
1158 1159 1160
}


1161 1162 1163
/* This function is used by Retrace and read the autorouting matrix data cells to create
 * the real track on the physical board
 */
1164 1165
static void OrCell_Trace( BOARD* pcb, int col, int row,
                          int side, int orient, int current_net_code )
1166
{
1167
    if( orient == HOLE )  // placement of a via
1168
    {
1169
        VIA *newVia = new VIA( pcb );
1170

1171
        g_CurrentTrackList.PushBack( newVia );
1172

1173
        g_CurrentTrackSegment->SetState( TRACK_AR, true );
Dick Hollenbeck's avatar
Dick Hollenbeck committed
1174
        g_CurrentTrackSegment->SetLayer( F_Cu );
1175

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

1182
        g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentViaSize() );
1183
        newVia->SetViaType( pcb->GetDesignSettings().m_CurrentViaType );
1184

1185
        g_CurrentTrackSegment->SetNetCode( current_net_code );
1186
    }
1187
    else    // placement of a standard segment
1188
    {
1189 1190 1191
        TRACK *newTrack = new TRACK( pcb );
        int    dx0, dy0, dx1, dy1;

1192

1193
        g_CurrentTrackList.PushBack( newTrack );
1194

1195
        g_CurrentTrackSegment->SetLayer( g_Route_Layer_BOTTOM );
1196

1197
        if( side == TOP )
1198
            g_CurrentTrackSegment->SetLayer( g_Route_Layer_TOP );
1199

1200
        g_CurrentTrackSegment->SetState( TRACK_AR, true );
1201 1202 1203 1204
        g_CurrentTrackSegment->SetEnd( wxPoint( pcb->GetBoundingBox().GetX() +
                                         ( RoutingMatrix.m_GridRouting * row ),
                                         pcb->GetBoundingBox().GetY() +
                                         ( RoutingMatrix.m_GridRouting * col )));
1205
        g_CurrentTrackSegment->SetNetCode( current_net_code );
1206

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1207
        if( g_CurrentTrackSegment->Back() == NULL ) // Start trace.
1208
        {
1209
            g_CurrentTrackSegment->SetStart( wxPoint( segm_fX, segm_fY ) );
1210

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1211
            // Placement on the center of the pad if outside grid.
1212 1213
            dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
            dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1214

1215 1216
            dx0 = pt_cur_ch->m_PadEnd->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
            dy0 = pt_cur_ch->m_PadEnd->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1217

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1218
            // If aligned, change the origin point.
1219
            if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1220
            {
1221
                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1222
            }
1223
            else    // Creation of a supplemental segment
1224
            {
1225
                g_CurrentTrackSegment->SetStart( pt_cur_ch->m_PadEnd->GetPosition() );
1226

1227
                newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1228
                newTrack->SetStart( g_CurrentTrackSegment->GetEnd());
1229

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

1241
        g_CurrentTrackSegment->SetWidth( pcb->GetDesignSettings().GetCurrentTrackWidth() );
1242

1243
        if( g_CurrentTrackSegment->GetStart() != g_CurrentTrackSegment->GetEnd() )
1244
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
1245
            // Reduce aligned segments by one.
1246
            TRACK* oldTrack = g_CurrentTrackSegment->Back();
1247

1248
            if( oldTrack &&  oldTrack->Type() != PCB_VIA_T )
1249
            {
1250 1251
                dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
                dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1252

1253 1254
                dx0 = oldTrack->GetEnd().x - oldTrack->GetStart().x;
                dy0 = oldTrack->GetEnd().y - oldTrack->GetStart().y;
1255

1256
                if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1257
                {
1258
                    oldTrack->SetEnd( g_CurrentTrackSegment->GetEnd() );
1259 1260

                    delete g_CurrentTrackList.PopBack();
1261 1262 1263 1264
                }
            }
        }
    }
1265 1266
}

1267

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

    int dx0, dy0, dx1, dy1;
    int marge, via_marge;
1280
    EDA_DRAW_PANEL* panel = pcbframe->GetCanvas();
1281
    PCB_SCREEN* screen = pcbframe->GetScreen();
1282

1283 1284
    marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentTrackWidth() / 2 );
    via_marge = s_Clearance + ( pcbframe->GetDesignSettings().GetCurrentViaSize() / 2 );
1285

1286 1287
    dx1 = g_CurrentTrackSegment->GetEnd().x - g_CurrentTrackSegment->GetStart().x;
    dy1 = g_CurrentTrackSegment->GetEnd().y - g_CurrentTrackSegment->GetStart().y;
1288

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1289
    // Place on center of pad if off grid.
1290 1291
    dx0 = pt_cur_ch->m_PadStart->GetPosition().x - g_CurrentTrackSegment->GetStart().x;
    dy0 = pt_cur_ch->m_PadStart->GetPosition().y - g_CurrentTrackSegment->GetStart().y;
1292

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1293
    // If aligned, change the origin point.
1294
    if( abs( dx0 * dy1 ) == abs( dx1 * dy0 ) )
1295
    {
1296
        g_CurrentTrackSegment->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
1297
    }
1298
    else
1299
    {
1300
        TRACK* newTrack = (TRACK*)g_CurrentTrackSegment->Clone();
1301

1302 1303
        newTrack->SetEnd( pt_cur_ch->m_PadStart->GetPosition() );
        newTrack->SetStart( g_CurrentTrackSegment->GetEnd() );
1304

1305
        g_CurrentTrackList.PushBack( newTrack );
1306
    }
1307

1308 1309
    g_FirstTrackSegment->start = pcbframe->GetBoard()->GetPad( g_FirstTrackSegment,
            ENDPOINT_START );
1310

1311
    if( g_FirstTrackSegment->start )
1312
        g_FirstTrackSegment->SetState( BEGIN_ONPAD, true );
1313

1314 1315
    g_CurrentTrackSegment->end = pcbframe->GetBoard()->GetPad( g_CurrentTrackSegment,
            ENDPOINT_END );
1316

1317
    if( g_CurrentTrackSegment->end )
1318
        g_CurrentTrackSegment->SetState( END_ONPAD, true );
1319

Dick Hollenbeck's avatar
Dick Hollenbeck committed
1320
    // Out the new track on the matrix board
1321
    for( TRACK* track = g_FirstTrackSegment; track; track = track->Next() )
1322
    {
1323 1324
        TraceSegmentPcb( track, HOLE, marge, WRITE_CELL );
        TraceSegmentPcb( track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
1325
    }
1326

1327
    // Insert new segments in  real board
1328
    int    netcode    = g_FirstTrackSegment->GetNetCode();
1329 1330 1331 1332 1333
    TRACK* firstTrack = g_FirstTrackSegment;
    int    newCount   = g_CurrentTrackList.GetCount();

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

1336 1337
    while( ( track = g_CurrentTrackList.PopFront() ) != NULL )
    {
1338 1339
        ITEM_PICKER picker( track, UR_NEW );
        s_ItemsListPicker.PushItem( picker );
1340 1341 1342
        pcbframe->GetBoard()->m_Track.Insert( track, insertBeforeMe );
    }

1343
    DrawTraces( panel, DC, firstTrack, newCount, GR_OR );
1344

1345
    pcbframe->TestNetConnection( DC, netcode );
1346

1347
    screen->SetModify();
1348
}