board.cpp 13.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2004 Jean-Pierre Charras, jaen-pierre.charras@gipsa-lab.inpg.com
 * Copyright (C) 2008-2011 Wayne Stambaugh <stambaughw@verizon.net>
 * Copyright (C) 2004-2011 KiCad Developers, see change_log.txt for contributors.
 *
 * 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
 */

26 27 28 29
/**
 * @file board.cpp
 * @brief Functions for autorouting
 */
30

31 32 33 34 35 36 37 38 39 40 41 42 43 44
#include <fctsys.h>
#include <common.h>
#include <pcbcommon.h>

#include <pcbnew.h>
#include <cell.h>
#include <ar_protos.h>

#include <class_board.h>
#include <class_module.h>
#include <class_track.h>
#include <class_drawsegment.h>
#include <class_edge_mod.h>
#include <class_pcb_text.h>
45

dickelbeck's avatar
dickelbeck committed
46

47
bool MATRIX_ROUTING_HEAD::ComputeMatrixSize( BOARD* aPcb )
48
{
49
    aPcb->ComputeBoundingBox();
dickelbeck's avatar
dickelbeck committed
50

Dick Hollenbeck's avatar
Dick Hollenbeck committed
51 52
    // The boundary box must have its start point on routing grid:
    m_BrdBox = aPcb->GetBoundingBox();
53

54
    m_BrdBox.Offset( -(m_BrdBox.GetX() % m_GridRouting), -(m_BrdBox.GetY() % m_GridRouting) );
Dick Hollenbeck's avatar
Dick Hollenbeck committed
55 56

    // The boundary box must have its end point on routing grid:
57
    wxPoint end = m_BrdBox.GetEnd();
Dick Hollenbeck's avatar
Dick Hollenbeck committed
58

59 60
    end.x -= end.x % m_GridRouting;
    end.x += m_GridRouting;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
61

62 63
    end.y -= end.y % m_GridRouting;
    end.y += m_GridRouting;
Dick Hollenbeck's avatar
Dick Hollenbeck committed
64

65
    m_BrdBox.SetEnd( end );
66

Dick Hollenbeck's avatar
Dick Hollenbeck committed
67 68
    aPcb->SetBoundingBox( m_BrdBox );

69 70
    m_Nrows = Nrows = m_BrdBox.GetHeight() / m_GridRouting;
    m_Ncols = Ncols = m_BrdBox.GetWidth() / m_GridRouting;
71

dickelbeck's avatar
dickelbeck committed
72
    /* get a small margin for memory allocation: */
73 74
    Ncols += 1;
    Nrows += 1;
dickelbeck's avatar
dickelbeck committed
75

76
    return true;
77 78 79
}


80
MATRIX_ROUTING_HEAD::MATRIX_ROUTING_HEAD()
81
{
dickelbeck's avatar
dickelbeck committed
82 83 84
    m_BoardSide[0]  = m_BoardSide[1] = NULL;
    m_DistSide[0]   = m_DistSide[1] = NULL;
    m_DirSide[0]    = m_DirSide[1] = NULL;
85
    m_InitBoardDone = false;
86
    m_Layers  = MAX_SIDES_COUNT;
dickelbeck's avatar
dickelbeck committed
87 88
    m_Nrows   = m_Ncols = 0;
    m_MemSize = 0;
89 90
}

dickelbeck's avatar
dickelbeck committed
91

92
MATRIX_ROUTING_HEAD::~MATRIX_ROUTING_HEAD()
93 94 95
{
}

dickelbeck's avatar
dickelbeck committed
96

97
int MATRIX_ROUTING_HEAD::InitBoard()
98
{
dickelbeck's avatar
dickelbeck committed
99
    int ii, kk;
100

dickelbeck's avatar
dickelbeck committed
101 102 103 104
    if( Nrows <= 0 || Ncols <= 0 )
        return 0;
    m_Nrows = Nrows;
    m_Ncols = Ncols;
105

106
    m_InitBoardDone = true; /* we have been called */
107

dickelbeck's avatar
dickelbeck committed
108
    ii = (Nrows + 1) * (Ncols + 1);
109

dickelbeck's avatar
dickelbeck committed
110 111 112 113 114
    for( kk = 0; kk < m_Layers; kk++ )
    {
        m_BoardSide[kk] = NULL;
        m_DistSide[kk]  = NULL;
        m_DirSide[kk]   = NULL;
115

dickelbeck's avatar
dickelbeck committed
116
        /* allocate Board & initialize everything to empty */
117
        m_BoardSide[kk] = (MATRIX_CELL*) operator new( ii * sizeof(MATRIX_CELL) );
118
        memset( m_BoardSide[kk], 0, ii * sizeof(MATRIX_CELL) );
119

dickelbeck's avatar
dickelbeck committed
120 121
        if( m_BoardSide[kk] == NULL )
            return -1;
122

dickelbeck's avatar
dickelbeck committed
123
        /***** allocate Distances *****/
124
        m_DistSide[kk] = (DIST_CELL*) operator new( ii * sizeof(DIST_CELL) );
125
        memset( m_DistSide[kk], 0, ii * sizeof(DIST_CELL) );
126

dickelbeck's avatar
dickelbeck committed
127 128
        if( m_DistSide[kk] == NULL )
            return -1;
129

dickelbeck's avatar
dickelbeck committed
130
        /***** allocate Dir (chars) *****/
131
        m_DirSide[kk] = (char*) operator new( ii );
132
        memset( m_DirSide[kk], 0, ii );
133

dickelbeck's avatar
dickelbeck committed
134 135 136
        if( m_DirSide[kk] == NULL )
            return -1;
    }
137

138
    m_MemSize = m_Layers * ii * ( sizeof(MATRIX_CELL) + sizeof(DIST_CELL) + sizeof(char) );
139

dickelbeck's avatar
dickelbeck committed
140
    return m_MemSize;
141 142
}

dickelbeck's avatar
dickelbeck committed
143

144
void MATRIX_ROUTING_HEAD::UnInitBoard()
145
{
dickelbeck's avatar
dickelbeck committed
146 147
    int ii;

148
    m_InitBoardDone = false;
dickelbeck's avatar
dickelbeck committed
149

150
    for( ii = 0; ii < MAX_SIDES_COUNT; ii++ )
dickelbeck's avatar
dickelbeck committed
151
    {
152
        /***** de-allocate Dir matrix *****/
dickelbeck's avatar
dickelbeck committed
153 154
        if( m_DirSide[ii] )
        {
155
            delete m_DirSide[ii];
156
            m_DirSide[ii] = NULL;
dickelbeck's avatar
dickelbeck committed
157 158
        }

159
        /***** de-allocate Distances matrix *****/
dickelbeck's avatar
dickelbeck committed
160 161
        if( m_DistSide[ii] )
        {
162
            delete m_DistSide[ii];
163
            m_DistSide[ii] = NULL;
dickelbeck's avatar
dickelbeck committed
164 165
        }

166
        /**** de-allocate cells matrix *****/
dickelbeck's avatar
dickelbeck committed
167 168
        if( m_BoardSide[ii] )
        {
169
            delete m_BoardSide[ii];
170
            m_BoardSide[ii] = NULL;
dickelbeck's avatar
dickelbeck committed
171 172 173 174
        }
    }

    m_Nrows = m_Ncols = 0;
175 176 177
}


178 179 180 181 182
/**
 * Function PlaceCells
 * initializes the cell board is set and VIA_IMPOSSIBLE HOLE according to the setbacks.
 * The elements of net_code = net_code will not be occupied as places but only
 * VIA_IMPOSSIBLE
stambaughw's avatar
stambaughw committed
183 184
 * For single-sided Routing 1:
 * BOTTOM side is used and Route_Layer_BOTTOM = Route_Layer_TOP
185
 *
stambaughw's avatar
stambaughw committed
186 187
 * According to the bits = 1 parameter flag:
 * If FORCE_PADS: all pads will be placed even those same net_code.
dickelbeck's avatar
dickelbeck committed
188
 */
stambaughw's avatar
stambaughw committed
189
void PlaceCells( BOARD* aPcb, int net_code, int flag )
190
{
191 192
    int       ux0 = 0, uy0 = 0, ux1, uy1, dx, dy;
    int       marge, via_marge;
193
    int       layerMask;
dickelbeck's avatar
dickelbeck committed
194

195
    // use the default NETCLASS?
196
    NETCLASS* nc = aPcb->m_NetClasses.GetDefault();
197

198 199 200
    int       trackWidth = nc->GetTrackWidth();
    int       clearance  = nc->GetClearance();
    int       viaSize    = nc->GetViaDiameter();
201 202 203

    marge     = clearance + (trackWidth / 2);
    via_marge = clearance + (viaSize / 2);
dickelbeck's avatar
dickelbeck committed
204

205
    // Place PADS on matrix routing:
206
    for( unsigned i = 0; i < aPcb->GetPadCount(); ++i )
dickelbeck's avatar
dickelbeck committed
207
    {
208
        D_PAD* pad = aPcb->GetPad( i );
209 210

        if( net_code != pad->GetNet() || (flag & FORCE_PADS) )
dickelbeck's avatar
dickelbeck committed
211
        {
212
            ::PlacePad( aPcb, pad, HOLE, marge, WRITE_CELL );
dickelbeck's avatar
dickelbeck committed
213
        }
214

215
        ::PlacePad( aPcb, pad, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
dickelbeck's avatar
dickelbeck committed
216 217
    }

218 219 220
    // Place outlines of modules on matrix routing, if they are on a copper layer
    // or on the edge layer
    TRACK tmpSegm( NULL );  // A dummy track used to create segments.
221

222
    for( MODULE* module = aPcb->m_Modules; module; module = module->Next() )
dickelbeck's avatar
dickelbeck committed
223
    {
224
        for( BOARD_ITEM* item = module->m_Drawings; item; item = item->Next() )
dickelbeck's avatar
dickelbeck committed
225
        {
226
            switch( item->Type() )
dickelbeck's avatar
dickelbeck committed
227
            {
228
            case PCB_MODULE_EDGE_T:
229 230 231 232
            {
                EDGE_MODULE* edge = (EDGE_MODULE*) item;

                tmpSegm.SetLayer( edge->GetLayer() );
233

234 235 236
                if( tmpSegm.GetLayer() == EDGE_N )
                    tmpSegm.SetLayer( -1 );

Dick Hollenbeck's avatar
Dick Hollenbeck committed
237 238 239 240 241
                tmpSegm.SetStart( edge->GetStart() );
                tmpSegm.SetEnd(   edge->GetEnd() );
                tmpSegm.SetShape( edge->GetShape() );
                tmpSegm.SetWidth( edge->GetWidth() );
                tmpSegm.m_Param = edge->GetAngle();
242 243 244
                tmpSegm.SetNet( -1 );

                TraceSegmentPcb( aPcb, &tmpSegm, HOLE, marge, WRITE_CELL );
245
                TraceSegmentPcb( aPcb, &tmpSegm, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
246 247
            }
            break;
dickelbeck's avatar
dickelbeck committed
248 249 250 251 252 253 254

            default:
                break;
            }
        }
    }

255
    // Place board outlines and texts on copper layers:
stambaughw's avatar
stambaughw committed
256
    for( BOARD_ITEM* item = aPcb->m_Drawings; item; item = item->Next() )
dickelbeck's avatar
dickelbeck committed
257
    {
258
        switch( item->Type() )
dickelbeck's avatar
dickelbeck committed
259
        {
260
        case PCB_LINE_T:
261 262 263 264 265 266
        {
            DRAWSEGMENT* DrawSegm;

            int          type_cell = HOLE;
            DrawSegm = (DRAWSEGMENT*) item;
            tmpSegm.SetLayer( DrawSegm->GetLayer() );
267

268
            if( DrawSegm->GetLayer() == EDGE_N )
dickelbeck's avatar
dickelbeck committed
269
            {
270 271
                tmpSegm.SetLayer( -1 );
                type_cell |= CELL_is_EDGE;
272
            }
273

Dick Hollenbeck's avatar
Dick Hollenbeck committed
274 275 276 277 278
            tmpSegm.SetStart( DrawSegm->GetStart() );
            tmpSegm.SetEnd(   DrawSegm->GetEnd() );
            tmpSegm.SetShape( DrawSegm->GetShape() );
            tmpSegm.SetWidth( DrawSegm->GetWidth() );
            tmpSegm.m_Param = DrawSegm->GetAngle();
279 280 281 282 283
            tmpSegm.SetNet( -1 );

            TraceSegmentPcb( aPcb, &tmpSegm, type_cell, marge, WRITE_CELL );
        }
        break;
dickelbeck's avatar
dickelbeck committed
284

285
        case PCB_TEXT_T:
286
        {
287
            TEXTE_PCB* PtText;
288 289
            PtText = (TEXTE_PCB*) item;

dickelbeck's avatar
dickelbeck committed
290 291
            if( PtText->GetLength() == 0 )
                break;
292

293
            EDA_RECT textbox = PtText->GetTextBox( -1 );
294 295
            ux0 = textbox.GetX();
            uy0 = textbox.GetY();
296 297
            dx  = textbox.GetWidth();
            dy  = textbox.GetHeight();
dickelbeck's avatar
dickelbeck committed
298

299
            /* Put bounding box (rectangle) on matrix */
300
            dx /= 2;
stambaughw's avatar
stambaughw committed
301
            dy /= 2;
302 303 304 305 306 307

            ux1 = ux0 + dx;
            uy1 = uy0 + dy;

            ux0 -= dx;
            uy0 -= dy;
dickelbeck's avatar
dickelbeck committed
308

309
            layerMask = GetLayerMask( PtText->GetLayer() );
dickelbeck's avatar
dickelbeck committed
310

stambaughw's avatar
stambaughw committed
311 312
            TraceFilledRectangle( aPcb, ux0 - marge, uy0 - marge, ux1 + marge,
                                  uy1 + marge, (int) (PtText->m_Orient),
313
                                  layerMask, HOLE, WRITE_CELL );
314 315

            TraceFilledRectangle( aPcb, ux0 - via_marge, uy0 - via_marge,
dickelbeck's avatar
dickelbeck committed
316 317
                                  ux1 + via_marge, uy1 + via_marge,
                                  (int) (PtText->m_Orient),
318
                                  layerMask, VIA_IMPOSSIBLE, WRITE_OR_CELL );
319
        }
320
        break;
dickelbeck's avatar
dickelbeck committed
321 322 323 324 325 326

        default:
            break;
        }
    }

327
    /* Put tracks and vias on matrix */
328
    for( TRACK* track = aPcb->m_Track; track; track = track->Next() )
dickelbeck's avatar
dickelbeck committed
329
    {
330
        if( net_code == track->GetNet() )
dickelbeck's avatar
dickelbeck committed
331
            continue;
332

333 334
        TraceSegmentPcb( aPcb, track, HOLE, marge, WRITE_CELL );
        TraceSegmentPcb( aPcb, track, VIA_IMPOSSIBLE, via_marge, WRITE_OR_CELL );
dickelbeck's avatar
dickelbeck committed
335
    }
336 337
}

dickelbeck's avatar
dickelbeck committed
338

339
int Build_Work( BOARD* Pcb )
340
{
Dick Hollenbeck's avatar
Dick Hollenbeck committed
341 342 343 344 345 346 347 348
    RATSNEST_ITEM*  pt_rats;
    D_PAD*          pt_pad;
    int             r1, r2, c1, c2, current_net_code;
    RATSNEST_ITEM*  pt_ch;
    int             demi_pas = Board.m_GridRouting / 2;
    wxString        msg;

    EDA_RECT        bbbox = Pcb->GetBoundingBox();
dickelbeck's avatar
dickelbeck committed
349 350 351

    InitWork(); /* clear work list */
    Ntotal = 0;
352

faa's avatar
faa committed
353
    for( unsigned ii = 0; ii < Pcb->GetRatsnestsCount(); ii++ )
dickelbeck's avatar
dickelbeck committed
354
    {
355
        pt_rats = &Pcb->m_FullRatsnest[ii];
356

357
        /* We consider her only ratsnest that are active ( obviously not yet routed)
charras's avatar
charras committed
358 359
         * and routables (that are not yet attempt to be routed and fail
         */
360
        if( (pt_rats->m_Status & CH_ACTIF) == 0 )
dickelbeck's avatar
dickelbeck committed
361
            continue;
362

363
        if( pt_rats->m_Status & CH_UNROUTABLE )
dickelbeck's avatar
dickelbeck committed
364
            continue;
365

366
        if( (pt_rats->m_Status & CH_ROUTE_REQ) == 0 )
dickelbeck's avatar
dickelbeck committed
367
            continue;
368

369
        pt_pad = pt_rats->m_PadStart;
dickelbeck's avatar
dickelbeck committed
370

371
        current_net_code = pt_pad->GetNet();
dickelbeck's avatar
dickelbeck committed
372 373
        pt_ch = pt_rats;

374
        r1 = ( pt_pad->GetPosition().y - bbbox.GetY() + demi_pas ) / Board.m_GridRouting;
375

dickelbeck's avatar
dickelbeck committed
376 377
        if( r1 < 0 || r1 >= Nrows )
        {
stambaughw's avatar
stambaughw committed
378
            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r1,
379
                        pt_pad->GetPosition().y, bbbox.GetY() );
380
            wxMessageBox( msg );
dickelbeck's avatar
dickelbeck committed
381 382
            return 0;
        }
383

384
        c1 = ( pt_pad->GetPosition().x - bbbox.GetX() + demi_pas ) / Board.m_GridRouting;
385

dickelbeck's avatar
dickelbeck committed
386 387
        if( c1 < 0 || c1 >= Ncols )
        {
stambaughw's avatar
stambaughw committed
388
            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c1,
389
                        pt_pad->GetPosition().x, bbbox.GetX() );
390
            wxMessageBox( msg );
dickelbeck's avatar
dickelbeck committed
391 392 393
            return 0;
        }

394
        pt_pad = pt_rats->m_PadEnd;
dickelbeck's avatar
dickelbeck committed
395

396
        r2 = ( pt_pad->GetPosition().y - bbbox.GetY()
397
               + demi_pas ) / Board.m_GridRouting;
398

dickelbeck's avatar
dickelbeck committed
399 400
        if( r2 < 0 || r2 >= Nrows )
        {
stambaughw's avatar
stambaughw committed
401
            msg.Printf( wxT( "error : row = %d ( padY %d pcbY %d) " ), r2,
402
                        pt_pad->GetPosition().y, bbbox.GetY() );
403
            wxMessageBox( msg );
dickelbeck's avatar
dickelbeck committed
404 405
            return 0;
        }
406

407
        c2 = ( pt_pad->GetPosition().x - bbbox.GetX() + demi_pas ) / Board.m_GridRouting;
408

dickelbeck's avatar
dickelbeck committed
409 410
        if( c2 < 0 || c2 >= Ncols )
        {
stambaughw's avatar
stambaughw committed
411
            msg.Printf( wxT( "error : col = %d ( padX %d pcbX %d) " ), c2,
412
                        pt_pad->GetPosition().x, bbbox.GetX() );
413
            wxMessageBox( msg );
dickelbeck's avatar
dickelbeck committed
414 415 416
            return 0;
        }

faa's avatar
faa committed
417 418
        SetWork( r1, c1, current_net_code, r2, c2, pt_ch, 0 );
        Ntotal++;
dickelbeck's avatar
dickelbeck committed
419 420 421 422
    }

    SortWork();
    return Ntotal;
423 424 425
}


426
/* return the value stored in a cell
427
 */
428
MATRIX_CELL GetCell( int aRow, int aCol, int aSide )
429
{
430
    MATRIX_CELL* p;
431

432 433
    p = Board.m_BoardSide[aSide];
    return p[aRow * Ncols + aCol];
434 435 436
}


437
/* basic cell operation : WRITE operation
438
 */
439
void SetCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
440
{
441
    MATRIX_CELL* p;
442

443 444
    p = Board.m_BoardSide[aSide];
    p[aRow * Ncols + aCol] = x;
445 446 447
}


448
/* basic cell operation : OR operation
449
 */
450
void OrCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
451
{
452
    MATRIX_CELL* p;
453

454 455
    p = Board.m_BoardSide[aSide];
    p[aRow * Ncols + aCol] |= x;
456 457 458
}


459
/* basic cell operation : XOR operation
460
 */
461
void XorCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
462
{
463
    MATRIX_CELL* p;
464

465 466
    p = Board.m_BoardSide[aSide];
    p[aRow * Ncols + aCol] ^= x;
467 468 469
}


470
/* basic cell operation : AND operation
471
 */
472
void AndCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
473
{
474
    MATRIX_CELL* p;
475

476 477
    p = Board.m_BoardSide[aSide];
    p[aRow * Ncols + aCol] &= x;
478 479 480
}


481
/* basic cell operation : ADD operation
482
 */
483
void AddCell( int aRow, int aCol, int aSide, MATRIX_CELL x )
484
{
485
    MATRIX_CELL* p;
486

487 488
    p = Board.m_BoardSide[aSide];
    p[aRow * Ncols + aCol] += x;
489 490 491 492
}


/* fetch distance cell */
493
DIST_CELL GetDist( int aRow, int aCol, int aSide ) /* fetch distance cell */
494
{
495
    DIST_CELL* p;
496

497 498
    p = Board.m_DistSide[aSide];
    return p[aRow * Ncols + aCol];
499 500 501 502
}


/* store distance cell */
503
void SetDist( int aRow, int aCol, int aSide, DIST_CELL x )
504
{
505
    DIST_CELL* p;
506

507 508
    p = Board.m_DistSide[aSide];
    p[aRow * Ncols + aCol] = x;
509 510 511 512
}


/* fetch direction cell */
513
int GetDir( int aRow, int aCol, int aSide )
514
{
515
    DIR_CELL* p;
516

517 518
    p = Board.m_DirSide[aSide];
    return (int) (p[aRow * Ncols + aCol]);
519 520 521 522
}


/* store direction cell */
523
void SetDir( int aRow, int aCol, int aSide, int x )
524
{
525
    DIR_CELL* p;
526

527 528
    p = Board.m_DirSide[aSide];
    p[aRow * Ncols + aCol] = (char) x;
529
}