graphpcb.cpp 23.6 KB
Newer Older
1 2 3 4
/**
 * @file graphpcb.cpp
 * @brief PCB editor autorouting and "graphics" routines.
 */
5

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2012 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
 * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
 *
 * Copyright (C) 1992-2012 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
 */

33 34 35 36
#include <fctsys.h>
#include <common.h>
#include <macros.h>
#include <trigo.h>
37
#include <math_for_graphics.h>
38 39
#include <class_board.h>
#include <class_track.h>
40
#include <class_drawsegment.h>
41 42

#include <pcbnew.h>
43
#include <autorout.h>
44
#include <cell.h>
45

46
void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color );
47

48 49
void TraceArc( int ux0, int uy0,
               int ux1, int uy1,
50
               double ArcAngle,
51
               int lg, LAYER_NUM layer, int color,
52
               int op_logic );
53 54


55 56
static void DrawSegmentQcq( int ux0, int uy0,
                            int ux1, int uy1,
57
                            int lg, LAYER_NUM layer, int color,
58
                            int op_logic );
59

60
static void TraceFilledCircle( int    cx, int cy, int radius,
Dick Hollenbeck's avatar
Dick Hollenbeck committed
61
                               LSET aLayerMask,
62
                               int    color,
63 64
                               int    op_logic );

65
static void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
66
                         int color, int op_logic );
67

68
// Macro call to update cell.
69 70
#define OP_CELL( layer, dy, dx )                                        \
    {                                                                   \
71
        if( layer == UNDEFINED_LAYER )                                  \
72
        {                                                               \
73
            RoutingMatrix.WriteCell( dy, dx, BOTTOM, color );           \
74 75
            if( RoutingMatrix.m_RoutingLayersCount > 1 )                \
                RoutingMatrix.WriteCell( dy, dx, TOP, color );          \
76 77 78
        }                                                               \
        else                                                            \
        {                                                               \
79
            if( layer == g_Route_Layer_BOTTOM )                         \
80
                RoutingMatrix.WriteCell( dy, dx, BOTTOM, color );       \
81
            if( RoutingMatrix.m_RoutingLayersCount > 1 )                \
82
                if( layer == g_Route_Layer_TOP )                        \
83
                    RoutingMatrix.WriteCell( dy, dx, TOP, color );      \
84 85 86
        }                                                               \
    }

87
void PlacePad( D_PAD* aPad, int color, int marge, int op_logic )
88
{
89
    int     dx, dy;
90
    wxPoint shape_pos = aPad->ShapePos();
91

Dick Hollenbeck's avatar
Dick Hollenbeck committed
92
    dx = aPad->GetSize().x / 2;
93
    dx += marge;
94

Dick Hollenbeck's avatar
Dick Hollenbeck committed
95
    if( aPad->GetShape() == PAD_CIRCLE )
96
    {
97
        TraceFilledCircle( shape_pos.x, shape_pos.y, dx,
Dick Hollenbeck's avatar
Dick Hollenbeck committed
98
                           aPad->GetLayerSet(), color, op_logic );
99 100 101
        return;
    }

Dick Hollenbeck's avatar
Dick Hollenbeck committed
102
    dy = aPad->GetSize().y / 2;
103
    dy += marge;
104

Dick Hollenbeck's avatar
Dick Hollenbeck committed
105
    if( aPad->GetShape() == PAD_TRAPEZOID )
106
    {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
107 108
        dx += abs( aPad->GetDelta().y ) / 2;
        dy += abs( aPad->GetDelta().x ) / 2;
109 110
    }

111
    // The pad is a rectangle ( horizontal or vertical )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
112
    if( int( aPad->GetOrientation() ) % 900 == 0 )
113
    {
114
        // Orientation turned 90 deg.
Dick Hollenbeck's avatar
Dick Hollenbeck committed
115
        if( aPad->GetOrientation() == 900  ||  aPad->GetOrientation() == 2700 )
116
        {
117 118 119
            EXCHG( dx, dy );
        }

120
        TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
121
                              shape_pos.x + dx, shape_pos.y + dy,
Dick Hollenbeck's avatar
Dick Hollenbeck committed
122
                              aPad->GetLayerSet(), color, op_logic );
123 124 125
    }
    else
    {
126
        TraceFilledRectangle( shape_pos.x - dx, shape_pos.y - dy,
127
                              shape_pos.x + dx, shape_pos.y + dy,
128
                              aPad->GetOrientation(),
Dick Hollenbeck's avatar
Dick Hollenbeck committed
129
                              aPad->GetLayerSet(), color, op_logic );
130
    }
131 132 133
}


134
/* Set to color the cells included in the circle
135
 * Parameters:
136
 * center: cx, cy.
137
 * radius: a value add to the radius or half the score pad
138
 * aLayerMask: layer occupied
139
 * color: mask write in cells
140
 * op_logic: type of writing in the cell (WRITE, OR)
141
 */
Dick Hollenbeck's avatar
Dick Hollenbeck committed
142 143
void TraceFilledCircle( int cx, int cy, int radius,
        LSET aLayerMask,  int color,  int op_logic )
144
{
145 146 147 148
    int   row, col;
    int   ux0, uy0, ux1, uy1;
    int   row_max, col_max, row_min, col_min;
    int   trace = 0;
149
    double fdistmin, fdistx, fdisty;
150 151 152
    int   tstwrite = 0;
    int   distmin;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
153
    if( aLayerMask[g_Route_Layer_BOTTOM] )
154
        trace = 1;       // Trace on BOTTOM
155

Dick Hollenbeck's avatar
Dick Hollenbeck committed
156
    if( aLayerMask[g_Route_Layer_TOP] )
157
        if( RoutingMatrix.m_RoutingLayersCount > 1 )
158
            trace |= 2;  // Trace on TOP
159 160 161 162

    if( trace == 0 )
        return;

163
    RoutingMatrix.SetCellOperation( op_logic );
164

165 166
    cx -= RoutingMatrix.GetBrdCoordOrigin().x;
    cy -= RoutingMatrix.GetBrdCoordOrigin().y;
167

168
    distmin = radius;
169

170
    // Calculate the bounding rectangle of the circle.
171 172 173 174
    ux0 = cx - radius;
    uy0 = cy - radius;
    ux1 = cx + radius;
    uy1 = cy + radius;
175

176
    // Calculate limit coordinates of cells belonging to the rectangle.
177 178 179 180
    row_max = uy1 / RoutingMatrix.m_GridRouting;
    col_max = ux1 / RoutingMatrix.m_GridRouting;
    row_min = uy0 / RoutingMatrix.m_GridRouting;  // if (uy0 > row_min*Board.m_GridRouting) row_min++;
    col_min = ux0 / RoutingMatrix.m_GridRouting;  // if (ux0 > col_min*Board.m_GridRouting) col_min++;
181 182 183

    if( row_min < 0 )
        row_min = 0;
184

185 186
    if( row_max >= (RoutingMatrix.m_Nrows - 1) )
        row_max = RoutingMatrix.m_Nrows - 1;
187

188 189
    if( col_min < 0 )
        col_min = 0;
190

191 192
    if( col_max >= (RoutingMatrix.m_Ncols - 1) )
        col_max = RoutingMatrix.m_Ncols - 1;
193

194
    // Calculate coordinate limits of cell belonging to the rectangle.
195 196
    if( row_min > row_max )
        row_max = row_min;
197

198 199 200
    if( col_min > col_max )
        col_max = col_min;

201
    fdistmin = (double) distmin * distmin;
202 203 204

    for( row = row_min; row <= row_max; row++ )
    {
205
        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
206
        fdisty *= fdisty;
207

208 209
        for( col = col_min; col <= col_max; col++ )
        {
210
            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
211 212
            fdistx *= fdistx;

213
            if( fdistmin <= ( fdistx + fdisty ) )
214 215 216
                continue;

            if( trace & 1 )
217
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
218

219
            if( trace & 2 )
220
                RoutingMatrix.WriteCell( row, col, TOP, color );
221

222 223 224 225 226 227 228
            tstwrite = 1;
        }
    }

    if( tstwrite )
        return;

229 230 231
    /* If no cell has been written, it affects the 4 neighboring diagonal
     * (Adverse event: pad off grid in the center of the 4 neighboring
     * diagonal) */
232 233
    distmin  = RoutingMatrix.m_GridRouting / 2 + 1;
    fdistmin = ( (double) distmin * distmin ) * 2; // Distance to center point diagonally
234 235 236

    for( row = row_min; row <= row_max; row++ )
    {
237
        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
238
        fdisty *= fdisty;
239

240 241
        for( col = col_min; col <= col_max; col++ )
        {
242
            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
243 244
            fdistx *= fdistx;

245
            if( fdistmin <= ( fdistx + fdisty ) )
246 247 248
                continue;

            if( trace & 1 )
249
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
250

251
            if( trace & 2 )
252
                RoutingMatrix.WriteCell( row, col, TOP, color );
253 254
        }
    }
255 256
}

257
void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int color, int marge, int op_logic )
258
{
259
    int half_width = ( pt_segm->GetWidth() / 2 ) + marge;
260

261
    // Calculate the bounding rectangle of the segment (if H, V or Via)
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
    int ux0 = pt_segm->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
    int uy0 = pt_segm->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
    int ux1 = pt_segm->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
    int uy1 = pt_segm->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;

    LAYER_NUM layer = pt_segm->GetLayer();

    if( color == VIA_IMPOSSIBLE )
        layer = UNDEFINED_LAYER;

    switch( pt_segm->GetShape() )
    {
    // The segment is here a straight line or a circle or an arc.:
    case S_CIRCLE:
        TraceCircle( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
        break;

    case S_ARC:
        TraceArc( ux0, uy0, ux1, uy1, pt_segm->GetAngle(), half_width, layer, color, op_logic );
        break;

    // The segment is here a line segment.
    default:
        DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
        break;
    }
}
289

290 291 292 293 294 295
void TraceSegmentPcb( TRACK* aTrack, int color, int marge, int op_logic )
{
    int half_width = ( aTrack->GetWidth() / 2 ) + marge;

    // Test if VIA (filled circle need to be drawn)
    if( aTrack->Type() == PCB_VIA_T )
296
    {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
297
        LSET layer_mask;
298

299
        if( aTrack->IsOnLayer( g_Route_Layer_BOTTOM ) )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
300
            layer_mask.set( g_Route_Layer_BOTTOM );
301

302
        if( aTrack->IsOnLayer( g_Route_Layer_TOP ) )
303
        {
Dick Hollenbeck's avatar
Dick Hollenbeck committed
304 305
            if( !layer_mask.any() )
                layer_mask = LSET( g_Route_Layer_TOP );
306
            else
Dick Hollenbeck's avatar
Dick Hollenbeck committed
307
                layer_mask.set();
308 309 310
        }

        if( color == VIA_IMPOSSIBLE )
Dick Hollenbeck's avatar
Dick Hollenbeck committed
311
            layer_mask.set();
312

Dick Hollenbeck's avatar
Dick Hollenbeck committed
313
        if( layer_mask.any() )
314
            TraceFilledCircle( aTrack->GetStart().x, aTrack->GetStart().y,
315
                               half_width, layer_mask, color, op_logic );
316
    }
317
    else
318
    {
319 320 321 322 323
        // Calculate the bounding rectangle of the segment
        int ux0 = aTrack->GetStart().x - RoutingMatrix.GetBrdCoordOrigin().x;
        int uy0 = aTrack->GetStart().y - RoutingMatrix.GetBrdCoordOrigin().y;
        int ux1 = aTrack->GetEnd().x - RoutingMatrix.GetBrdCoordOrigin().x;
        int uy1 = aTrack->GetEnd().y - RoutingMatrix.GetBrdCoordOrigin().y;
324

325
        // Ordinary track
Dick Hollenbeck's avatar
Dick Hollenbeck committed
326
        LAYER_ID layer = aTrack->GetLayer();
327 328 329

        if( color == VIA_IMPOSSIBLE )
            layer = UNDEFINED_LAYER;
330

331
        DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
332
    }
333 334 335
}


336
/* Draws a line, if layer = -1 on all layers
337
 */
338
void TracePcbLine( int x0, int y0, int x1, int y1, LAYER_NUM layer, int color, int op_logic  )
339
{
340 341 342
    int  dx, dy, lim;
    int  cumul, inc, il, delta;

343
    RoutingMatrix.SetCellOperation( op_logic );
344

345
    if( x0 == x1 )  // Vertical.
346 347 348
    {
        if( y1 < y0 )
            EXCHG( y0, y1 );
349

350 351 352
        dy  = y0 / RoutingMatrix.m_GridRouting;
        lim = y1 / RoutingMatrix.m_GridRouting;
        dx  = x0 / RoutingMatrix.m_GridRouting;
353

354
        // Clipping limits of board.
355
        if( ( dx < 0 ) || ( dx >= RoutingMatrix.m_Ncols ) )
356
            return;
357

358 359
        if( dy < 0 )
            dy = 0;
360

361 362
        if( lim >= RoutingMatrix.m_Nrows )
            lim = RoutingMatrix.m_Nrows - 1;
363

364 365 366 367 368 369 370 371
        for( ; dy <= lim; dy++ )
        {
            OP_CELL( layer, dy, dx );
        }

        return;
    }

372
    if( y0 == y1 )  // Horizontal
373 374 375
    {
        if( x1 < x0 )
            EXCHG( x0, x1 );
376

377 378 379
        dx  = x0 / RoutingMatrix.m_GridRouting;
        lim = x1 / RoutingMatrix.m_GridRouting;
        dy  = y0 / RoutingMatrix.m_GridRouting;
380

381
        // Clipping limits of board.
382
        if( ( dy < 0 ) || ( dy >= RoutingMatrix.m_Nrows ) )
383
            return;
384

385 386
        if( dx < 0 )
            dx = 0;
387

388 389
        if( lim >= RoutingMatrix.m_Ncols )
            lim = RoutingMatrix.m_Ncols - 1;
390

391 392 393 394 395 396 397 398
        for( ; dx <= lim; dx++ )
        {
            OP_CELL( layer, dy, dx );
        }

        return;
    }

399 400
    // Here is some perspective: using the algorithm LUCAS.
    if( abs( x1 - x0 ) >= abs( y1 - y0 ) ) // segment slightly inclined/
401 402 403 404 405 406
    {
        if( x1 < x0 )
        {
            EXCHG( x1, x0 ); EXCHG( y1, y0 );
        }

407 408 409
        dx  = x0 / RoutingMatrix.m_GridRouting;
        lim = x1 / RoutingMatrix.m_GridRouting;
        dy  = y0 / RoutingMatrix.m_GridRouting;
410 411 412
        inc = 1;

        if( y1 < y0 )
413
            inc = -1;
414

415
        il    = lim - dx; cumul = il / 2;
416
        delta = abs( y1 - y0 ) / RoutingMatrix.m_GridRouting;
417

418 419
        for( ; dx <= lim; )
        {
420 421 422
            if( ( dx >= 0 ) && ( dy >= 0 ) &&
                ( dx < RoutingMatrix.m_Ncols ) &&
                ( dy < RoutingMatrix.m_Nrows ) )
423 424 425
            {
                OP_CELL( layer, dy, dx );
            }
426 427 428 429

            dx++;
            cumul += delta;

430 431
            if( cumul > il )
            {
432 433
                cumul -= il;
                dy    += inc;
434 435 436 437 438 439 440
            }
        }
    }
    else
    {
        if( y1 < y0 )
        {
441 442
            EXCHG( x1, x0 );
            EXCHG( y1, y0 );
443 444
        }

445 446 447
        dy  = y0 / RoutingMatrix.m_GridRouting;
        lim = y1 / RoutingMatrix.m_GridRouting;
        dx  = x0 / RoutingMatrix.m_GridRouting;
448
        inc = 1;
449

450
        if( x1 < x0 )
451
            inc = -1;
452

453 454 455
        il    = lim - dy;
        cumul = il / 2;
        delta = abs( x1 - x0 ) / RoutingMatrix.m_GridRouting;
456

457 458
        for( ; dy <= lim; )
        {
459
            if( ( dx >= 0 ) && ( dy >= 0 ) && ( dx < RoutingMatrix.m_Ncols ) && ( dy < RoutingMatrix.m_Nrows ) )
460 461 462
            {
                OP_CELL( layer, dy, dx );
            }
463 464 465 466

            dy++;
            cumul += delta;

467 468
            if( cumul > il )
            {
469 470
                cumul -= il;
                dx    += inc;
471 472 473
            }
        }
    }
474 475
}

476

477
void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
Dick Hollenbeck's avatar
Dick Hollenbeck committed
478
                           LSET aLayerMask, int color, int op_logic )
479
{
480 481 482 483
    int  row, col;
    int  row_min, row_max, col_min, col_max;
    int  trace = 0;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
484
    if( aLayerMask[g_Route_Layer_BOTTOM] )
485
        trace = 1;     // Trace on BOTTOM
486

Dick Hollenbeck's avatar
Dick Hollenbeck committed
487
    if( aLayerMask[g_Route_Layer_TOP] && RoutingMatrix.m_RoutingLayersCount > 1 )
488
        trace |= 2;    // Trace on TOP
489 490 491 492

    if( trace == 0 )
        return;

493
    RoutingMatrix.SetCellOperation( op_logic );
494

495 496 497 498
    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
499

500
    // Calculating limits coord cells belonging to the rectangle.
501 502 503
    row_max = uy1 / RoutingMatrix.m_GridRouting;
    col_max = ux1 / RoutingMatrix.m_GridRouting;
    row_min = uy0 / RoutingMatrix.m_GridRouting;
504

505
    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
506
        row_min++;
507

508
    col_min = ux0 / RoutingMatrix.m_GridRouting;
509

510
    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
511 512 513 514
        col_min++;

    if( row_min < 0 )
        row_min = 0;
515

516 517
    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
518

519 520
    if( col_min < 0 )
        col_min = 0;
521

522 523
    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
524 525 526 527 528 529

    for( row = row_min; row <= row_max; row++ )
    {
        for( col = col_min; col <= col_max; col++ )
        {
            if( trace & 1 )
530
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
531

532
            if( trace & 2 )
533
                RoutingMatrix.WriteCell( row, col, TOP, color );
534 535
        }
    }
536 537 538
}


539
void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
Dick Hollenbeck's avatar
Dick Hollenbeck committed
540
                           double angle, LSET aLayerMask, int color, int op_logic )
541
{
542
    int  row, col;
543 544
    int  cx, cy;    // Center of rectangle
    int  radius;     // Radius of the circle
545 546 547 548
    int  row_min, row_max, col_min, col_max;
    int  rotrow, rotcol;
    int  trace = 0;

Dick Hollenbeck's avatar
Dick Hollenbeck committed
549
    if( aLayerMask[g_Route_Layer_BOTTOM] )
550
        trace = 1;     // Trace on BOTTOM
551

Dick Hollenbeck's avatar
Dick Hollenbeck committed
552
    if( aLayerMask[g_Route_Layer_TOP] )
553
    {
554
        if( RoutingMatrix.m_RoutingLayersCount > 1 )
555
            trace |= 2;  // Trace on TOP
556
    }
557 558 559 560

    if( trace == 0 )
        return;

561
    RoutingMatrix.SetCellOperation( op_logic );
562

563 564 565 566
    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
567 568 569

    cx    = (ux0 + ux1) / 2;
    cy    = (uy0 + uy1) / 2;
570
    radius = KiROUND( Distance( ux0, uy0, cx, cy ) );
571

572
    // Calculating coordinate limits belonging to the rectangle.
573 574 575
    row_max = ( cy + radius ) / RoutingMatrix.m_GridRouting;
    col_max = ( cx + radius ) / RoutingMatrix.m_GridRouting;
    row_min = ( cy - radius ) / RoutingMatrix.m_GridRouting;
576

577
    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
578
        row_min++;
579

580
    col_min = ( cx - radius ) / RoutingMatrix.m_GridRouting;
581

582
    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
583 584 585 586
        col_min++;

    if( row_min < 0 )
        row_min = 0;
587

588 589
    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
590

591 592
    if( col_min < 0 )
        col_min = 0;
593

594 595
    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
596 597 598 599 600

    for( row = row_min; row <= row_max; row++ )
    {
        for( col = col_min; col <= col_max; col++ )
        {
601 602
            rotrow = row * RoutingMatrix.m_GridRouting;
            rotcol = col * RoutingMatrix.m_GridRouting;
603
            RotatePoint( &rotcol, &rotrow, cx, cy, -angle );
604

605 606
            if( rotrow <= uy0 )
                continue;
607

608 609
            if( rotrow >= uy1 )
                continue;
610

611 612
            if( rotcol <= ux0 )
                continue;
613

614 615
            if( rotcol >= ux1 )
                continue;
616

617
            if( trace & 1 )
618
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
619

620
            if( trace & 2 )
621
                RoutingMatrix.WriteCell( row, col, TOP, color );
622 623
        }
    }
624 625 626
}


627
/* Fills all cells inside a segment
628 629
 * half-width = lg, org = ux0,uy0 end = ux1,uy1
 * coordinates are in PCB units
630
 */
631
void DrawSegmentQcq( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
632
                     int color, int op_logic )
633
{
634 635 636 637 638 639 640
    int  row, col;
    int  inc;
    int  row_max, col_max, row_min, col_min;
    int  demi_pas;

    int  cx, cy, dx, dy;

641
    RoutingMatrix.SetCellOperation( op_logic );
642

643
    // Make coordinate ux1 tj > ux0 to simplify calculations
644 645
    if( ux1 < ux0 )
    {
646 647
        EXCHG( ux1, ux0 );
        EXCHG( uy1, uy0 );
648 649
    }

650
    // Calculating the incrementing the Y axis
651
    inc = 1;
652

653
    if( uy1 < uy0 )
654 655
        inc = -1;

656
    demi_pas = RoutingMatrix.m_GridRouting / 2;
657

658
    col_min = ( ux0 - lg ) / RoutingMatrix.m_GridRouting;
659

660 661
    if( col_min < 0 )
        col_min = 0;
662

663
    col_max = ( ux1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
664

665 666
    if( col_max > ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
667 668 669

    if( inc > 0 )
    {
670 671
        row_min = ( uy0 - lg ) / RoutingMatrix.m_GridRouting;
        row_max = ( uy1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
672 673 674
    }
    else
    {
675 676
        row_min = ( uy1 - lg ) / RoutingMatrix.m_GridRouting;
        row_max = ( uy0 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
677 678 679 680
    }

    if( row_min < 0 )
        row_min = 0;
681

682 683
    if( row_min > ( RoutingMatrix.m_Nrows - 1 ) )
        row_min = RoutingMatrix.m_Nrows - 1;
684

685 686
    if( row_max < 0 )
        row_max = 0;
687

688 689
    if( row_max > ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
690

691 692
    dx = ux1 - ux0;
    dy = uy1 - uy0;
693

694
    double angle;
695
    if( dx )
696
    {
697
        angle = ArcTangente( dy, dx );
698
    }
699 700
    else
    {
701
        angle = 900;
702

703
        if( dy < 0 )
704 705 706
            angle = -900;
    }

707
    RotatePoint( &dx, &dy, angle );   // dx = length, dy = 0
708

709 710 711
    for( col = col_min; col <= col_max; col++ )
    {
        int cxr;
712
        cxr = ( col * RoutingMatrix.m_GridRouting ) - ux0;
713

714
        for( row = row_min; row <= row_max; row++ )
715
        {
716
            cy = (row * RoutingMatrix.m_GridRouting) - uy0;
717 718
            cx = cxr;
            RotatePoint( &cx, &cy, angle );
719

720
            if( abs( cy ) > lg )
721
                continue;             // The point is too far on the Y axis.
722

723 724 725 726
            /* This point a test is close to the segment: the position
             * along the X axis must be tested.
             */
            if( ( cx >= 0 ) && ( cx <= dx ) )
727 728 729 730
            {
                OP_CELL( layer, row, col );
                continue;
            }
731

732
            // Examination of extremities are rounded.
733
            if( ( cx < 0 ) && ( cx >= -lg ) )
734
            {
735
                if( ( ( cx * cx ) + ( cy * cy ) ) <= ( lg * lg ) )
736
                    OP_CELL( layer, row, col );
737

738 739
                continue;
            }
740

741
            if( ( cx > dx ) && ( cx <= ( dx + lg ) ) )
742
            {
743
                if( ( ( ( cx - dx ) * ( cx - dx ) ) + ( cy * cy ) ) <= ( lg * lg ) )
744
                    OP_CELL( layer, row, col );
745

746 747 748 749
                continue;
            }
        }
    }
750 751
}

752

753 754 755
/* Fills all cells of the routing matrix contained in the circle
 * half-width = lg, center = ux0, uy0, ux1,uy1 is a point on the circle.
 * coord are in PCB units.
756
 */
757
void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
758
                  int color, int op_logic )
759
{
760
    int radius, nb_segm;
761 762
    int x0, y0,             // Starting point of the current segment trace.
        x1, y1;             // End point.
763 764 765
    int ii;
    int angle;

766
    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
767

768
    x0 = x1 = radius;
769
    y0 = y1 = 0;
770

771 772
    if( lg < 1 )
        lg = 1;
773

774
    nb_segm = ( 2 * radius ) / lg;
775

776 777
    if( nb_segm < 5 )
        nb_segm = 5;
778

779 780
    if( nb_segm > 100 )
        nb_segm = 100;
781

782 783 784
    for( ii = 1; ii < nb_segm; ii++ )
    {
        angle = (3600 * ii) / nb_segm;
785 786
        x1    = KiROUND( cosdecideg( radius, angle ) );
        y1    = KiROUND( sindecideg( radius, angle ) );
787
        DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic );
788 789
        x0 = x1;
        y0 = y1;
790 791
    }

792
    DrawSegmentQcq( x1 + ux0, y1 + uy0, ux0 + radius, uy0, lg, layer, color, op_logic );
793 794
}

795

796 797 798 799
/* Fills all routing matrix cells contained in the arc
 * angle = ArcAngle, half-width lg
 * center = ux0,uy0, starting at ux1, uy1.  Coordinates are in
 * PCB units.
800
 */
801
void TraceArc( int ux0, int uy0, int ux1, int uy1, double ArcAngle, int lg,
802
               LAYER_NUM layer, int color, int op_logic )
803
{
804
    int radius, nb_segm;
805 806
    int x0, y0,             // Starting point of the current segment trace
        x1, y1;             // End point
807
    int ii;
808
    double angle, StAngle;
809 810


811
    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
812

813 814
    x0 = ux1 - ux0;
    y0 = uy1 - uy0;
815
    StAngle = ArcTangente( uy1 - uy0, ux1 - ux0 );
816

817 818
    if( lg < 1 )
        lg = 1;
819

820
    nb_segm = ( 2 * radius ) / lg;
821
    nb_segm = ( nb_segm * std::abs( ArcAngle ) ) / 3600;
822

823 824
    if( nb_segm < 5 )
        nb_segm = 5;
825

826 827 828 829 830
    if( nb_segm > 100 )
        nb_segm = 100;

    for( ii = 1; ii <= nb_segm; ii++ )
    {
831
        angle  = ( ArcAngle * ii ) / nb_segm;
832 833
        angle += StAngle;

834
        NORMALIZE_ANGLE_POS( angle );
835

836 837
        x1 = KiROUND( cosdecideg( radius, angle ) );
        y1 = KiROUND( cosdecideg( radius, angle ) );
838
        DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic );
839 840
        x0 = x1;
        y0 = y1;
841
    }
842
}