graphpcb.cpp 23.9 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 37
#include <fctsys.h>
#include <common.h>
#include <macros.h>
#include <trigo.h>
#include <pcbcommon.h>
38
#include <math_for_graphics.h>
39 40
#include <class_board.h>
#include <class_track.h>
41
#include <class_drawsegment.h>
42 43

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

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

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


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

61
static void TraceFilledCircle( int    cx, int cy, int radius,
62
                               LAYER_MSK aLayerMask,
63
                               int    color,
64 65
                               int    op_logic );

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

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

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

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

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

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

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

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

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


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

156
    if( aLayerMask & GetLayerMask( g_Route_Layer_BOTTOM ) )
157
        trace = 1;       // Trace on BOTTOM
158

159
    if( aLayerMask & GetLayerMask( g_Route_Layer_TOP ) )
160
        if( RoutingMatrix.m_RoutingLayersCount > 1 )
161
            trace |= 2;  // Trace on TOP
162 163 164 165

    if( trace == 0 )
        return;

166
    RoutingMatrix.SetCellOperation( op_logic );
167

168 169
    cx -= RoutingMatrix.GetBrdCoordOrigin().x;
    cy -= RoutingMatrix.GetBrdCoordOrigin().y;
170

171
    distmin = radius;
172

173
    // Calculate the bounding rectangle of the circle.
174 175 176 177
    ux0 = cx - radius;
    uy0 = cy - radius;
    ux1 = cx + radius;
    uy1 = cy + radius;
178

179
    // Calculate limit coordinates of cells belonging to the rectangle.
180 181 182 183
    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++;
184 185 186

    if( row_min < 0 )
        row_min = 0;
187

188 189
    if( row_max >= (RoutingMatrix.m_Nrows - 1) )
        row_max = RoutingMatrix.m_Nrows - 1;
190

191 192
    if( col_min < 0 )
        col_min = 0;
193

194 195
    if( col_max >= (RoutingMatrix.m_Ncols - 1) )
        col_max = RoutingMatrix.m_Ncols - 1;
196

197
    // Calculate coordinate limits of cell belonging to the rectangle.
198 199
    if( row_min > row_max )
        row_max = row_min;
200

201 202 203
    if( col_min > col_max )
        col_max = col_min;

204
    fdistmin = (double) distmin * distmin;
205 206 207

    for( row = row_min; row <= row_max; row++ )
    {
208
        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
209
        fdisty *= fdisty;
210

211 212
        for( col = col_min; col <= col_max; col++ )
        {
213
            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
214 215
            fdistx *= fdistx;

216
            if( fdistmin <= ( fdistx + fdisty ) )
217 218 219
                continue;

            if( trace & 1 )
220
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
221

222
            if( trace & 2 )
223
                RoutingMatrix.WriteCell( row, col, TOP, color );
224

225 226 227 228 229 230 231
            tstwrite = 1;
        }
    }

    if( tstwrite )
        return;

232 233 234
    /* 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) */
235 236
    distmin  = RoutingMatrix.m_GridRouting / 2 + 1;
    fdistmin = ( (double) distmin * distmin ) * 2; // Distance to center point diagonally
237 238 239

    for( row = row_min; row <= row_max; row++ )
    {
240
        fdisty  = (double) ( cy - ( row * RoutingMatrix.m_GridRouting ) );
241
        fdisty *= fdisty;
242

243 244
        for( col = col_min; col <= col_max; col++ )
        {
245
            fdistx  = (double) ( cx - ( col * RoutingMatrix.m_GridRouting ) );
246 247
            fdistx *= fdistx;

248
            if( fdistmin <= ( fdistx + fdisty ) )
249 250 251
                continue;

            if( trace & 1 )
252
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
253

254
            if( trace & 2 )
255
                RoutingMatrix.WriteCell( row, col, TOP, color );
256 257
        }
    }
258 259
}

260
void TraceSegmentPcb( DRAWSEGMENT* pt_segm, int color, int marge, int op_logic )
261
{
262
    int half_width = ( pt_segm->GetWidth() / 2 ) + marge;
263

264
    // Calculate the bounding rectangle of the segment (if H, V or Via)
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
    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;
    }
}
292

293 294 295 296 297 298
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 )
299
    {
300
        LAYER_MSK layer_mask = NO_LAYERS;
301

302
        if( aTrack->IsOnLayer( g_Route_Layer_BOTTOM ) )
303
            layer_mask = GetLayerMask( g_Route_Layer_BOTTOM );
304

305
        if( aTrack->IsOnLayer( g_Route_Layer_TOP ) )
306
        {
307 308
            if( layer_mask == 0 )
                layer_mask = GetLayerMask( g_Route_Layer_TOP );
309
            else
310
                layer_mask = FULL_LAYERS;
311 312 313
        }

        if( color == VIA_IMPOSSIBLE )
314
            layer_mask = FULL_LAYERS;
315

316
        if( layer_mask )
317
            TraceFilledCircle( aTrack->GetStart().x, aTrack->GetStart().y,
318
                               half_width, layer_mask, color, op_logic );
319
    }
320
    else
321
    {
322 323 324 325 326
        // 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;
327

328 329 330 331 332
        // Ordinary track
        LAYER_NUM layer = aTrack->GetLayer();

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

334
        DrawSegmentQcq( ux0, uy0, ux1, uy1, half_width, layer, color, op_logic );
335
    }
336 337 338
}


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

346
    RoutingMatrix.SetCellOperation( op_logic );
347

348
    if( x0 == x1 )  // Vertical.
349 350 351
    {
        if( y1 < y0 )
            EXCHG( y0, y1 );
352

353 354 355
        dy  = y0 / RoutingMatrix.m_GridRouting;
        lim = y1 / RoutingMatrix.m_GridRouting;
        dx  = x0 / RoutingMatrix.m_GridRouting;
356

357
        // Clipping limits of board.
358
        if( ( dx < 0 ) || ( dx >= RoutingMatrix.m_Ncols ) )
359
            return;
360

361 362
        if( dy < 0 )
            dy = 0;
363

364 365
        if( lim >= RoutingMatrix.m_Nrows )
            lim = RoutingMatrix.m_Nrows - 1;
366

367 368 369 370 371 372 373 374
        for( ; dy <= lim; dy++ )
        {
            OP_CELL( layer, dy, dx );
        }

        return;
    }

375
    if( y0 == y1 )  // Horizontal
376 377 378
    {
        if( x1 < x0 )
            EXCHG( x0, x1 );
379

380 381 382
        dx  = x0 / RoutingMatrix.m_GridRouting;
        lim = x1 / RoutingMatrix.m_GridRouting;
        dy  = y0 / RoutingMatrix.m_GridRouting;
383

384
        // Clipping limits of board.
385
        if( ( dy < 0 ) || ( dy >= RoutingMatrix.m_Nrows ) )
386
            return;
387

388 389
        if( dx < 0 )
            dx = 0;
390

391 392
        if( lim >= RoutingMatrix.m_Ncols )
            lim = RoutingMatrix.m_Ncols - 1;
393

394 395 396 397 398 399 400 401
        for( ; dx <= lim; dx++ )
        {
            OP_CELL( layer, dy, dx );
        }

        return;
    }

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

410 411 412
        dx  = x0 / RoutingMatrix.m_GridRouting;
        lim = x1 / RoutingMatrix.m_GridRouting;
        dy  = y0 / RoutingMatrix.m_GridRouting;
413 414 415
        inc = 1;

        if( y1 < y0 )
416
            inc = -1;
417

418
        il    = lim - dx; cumul = il / 2;
419
        delta = abs( y1 - y0 ) / RoutingMatrix.m_GridRouting;
420

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

            dx++;
            cumul += delta;

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

448 449 450
        dy  = y0 / RoutingMatrix.m_GridRouting;
        lim = y1 / RoutingMatrix.m_GridRouting;
        dx  = x0 / RoutingMatrix.m_GridRouting;
451
        inc = 1;
452

453
        if( x1 < x0 )
454
            inc = -1;
455

456 457 458
        il    = lim - dy;
        cumul = il / 2;
        delta = abs( x1 - x0 ) / RoutingMatrix.m_GridRouting;
459

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

            dy++;
            cumul += delta;

470 471
            if( cumul > il )
            {
472 473
                cumul -= il;
                dx    += inc;
474 475 476
            }
        }
    }
477 478
}

479

480
void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
481
                           int aLayerMask, int color, int op_logic )
482
{
483 484 485 486
    int  row, col;
    int  row_min, row_max, col_min, col_max;
    int  trace = 0;

487
    if( ( aLayerMask & GetLayerMask( g_Route_Layer_BOTTOM ) ) )
488
        trace = 1;     // Trace on BOTTOM
489

490
    if( ( aLayerMask & GetLayerMask( g_Route_Layer_TOP ) ) &&
491
        RoutingMatrix.m_RoutingLayersCount > 1 )
492
        trace |= 2;    // Trace on TOP
493 494 495 496

    if( trace == 0 )
        return;

497
    RoutingMatrix.SetCellOperation( op_logic );
498

499 500 501 502
    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
503

504
    // Calculating limits coord cells belonging to the rectangle.
505 506 507
    row_max = uy1 / RoutingMatrix.m_GridRouting;
    col_max = ux1 / RoutingMatrix.m_GridRouting;
    row_min = uy0 / RoutingMatrix.m_GridRouting;
508

509
    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
510
        row_min++;
511

512
    col_min = ux0 / RoutingMatrix.m_GridRouting;
513

514
    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
515 516 517 518
        col_min++;

    if( row_min < 0 )
        row_min = 0;
519

520 521
    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
522

523 524
    if( col_min < 0 )
        col_min = 0;
525

526 527
    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
528 529 530 531 532 533

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

536
            if( trace & 2 )
537
                RoutingMatrix.WriteCell( row, col, TOP, color );
538 539
        }
    }
540 541 542
}


543
void TraceFilledRectangle( int ux0, int uy0, int ux1, int uy1,
544
                           double angle, LAYER_MSK aLayerMask, int color, int op_logic )
545
{
546
    int  row, col;
547 548
    int  cx, cy;    // Center of rectangle
    int  radius;     // Radius of the circle
549 550 551 552
    int  row_min, row_max, col_min, col_max;
    int  rotrow, rotcol;
    int  trace = 0;

553
    if( aLayerMask & GetLayerMask( g_Route_Layer_BOTTOM ) )
554
        trace = 1;     // Trace on BOTTOM
555

556
    if( aLayerMask & GetLayerMask( g_Route_Layer_TOP ) )
557
    {
558
        if( RoutingMatrix.m_RoutingLayersCount > 1 )
559
            trace |= 2;  // Trace on TOP
560
    }
561 562 563 564

    if( trace == 0 )
        return;

565
    RoutingMatrix.SetCellOperation( op_logic );
566

567 568 569 570
    ux0 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy0 -= RoutingMatrix.GetBrdCoordOrigin().y;
    ux1 -= RoutingMatrix.GetBrdCoordOrigin().x;
    uy1 -= RoutingMatrix.GetBrdCoordOrigin().y;
571 572 573

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

576
    // Calculating coordinate limits belonging to the rectangle.
577 578 579
    row_max = ( cy + radius ) / RoutingMatrix.m_GridRouting;
    col_max = ( cx + radius ) / RoutingMatrix.m_GridRouting;
    row_min = ( cy - radius ) / RoutingMatrix.m_GridRouting;
580

581
    if( uy0 > row_min * RoutingMatrix.m_GridRouting )
582
        row_min++;
583

584
    col_min = ( cx - radius ) / RoutingMatrix.m_GridRouting;
585

586
    if( ux0 > col_min * RoutingMatrix.m_GridRouting )
587 588 589 590
        col_min++;

    if( row_min < 0 )
        row_min = 0;
591

592 593
    if( row_max >= ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
594

595 596
    if( col_min < 0 )
        col_min = 0;
597

598 599
    if( col_max >= ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
600 601 602 603 604

    for( row = row_min; row <= row_max; row++ )
    {
        for( col = col_min; col <= col_max; col++ )
        {
605 606
            rotrow = row * RoutingMatrix.m_GridRouting;
            rotcol = col * RoutingMatrix.m_GridRouting;
607
            RotatePoint( &rotcol, &rotrow, cx, cy, -angle );
608

609 610
            if( rotrow <= uy0 )
                continue;
611

612 613
            if( rotrow >= uy1 )
                continue;
614

615 616
            if( rotcol <= ux0 )
                continue;
617

618 619
            if( rotcol >= ux1 )
                continue;
620

621
            if( trace & 1 )
622
                RoutingMatrix.WriteCell( row, col, BOTTOM, color );
623

624
            if( trace & 2 )
625
                RoutingMatrix.WriteCell( row, col, TOP, color );
626 627
        }
    }
628 629 630
}


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

    int  cx, cy, dx, dy;

645
    RoutingMatrix.SetCellOperation( op_logic );
646

647
    // Make coordinate ux1 tj > ux0 to simplify calculations
648 649
    if( ux1 < ux0 )
    {
650 651
        EXCHG( ux1, ux0 );
        EXCHG( uy1, uy0 );
652 653
    }

654
    // Calculating the incrementing the Y axis
655
    inc = 1;
656

657
    if( uy1 < uy0 )
658 659
        inc = -1;

660
    demi_pas = RoutingMatrix.m_GridRouting / 2;
661

662
    col_min = ( ux0 - lg ) / RoutingMatrix.m_GridRouting;
663

664 665
    if( col_min < 0 )
        col_min = 0;
666

667
    col_max = ( ux1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
668

669 670
    if( col_max > ( RoutingMatrix.m_Ncols - 1 ) )
        col_max = RoutingMatrix.m_Ncols - 1;
671 672 673

    if( inc > 0 )
    {
674 675
        row_min = ( uy0 - lg ) / RoutingMatrix.m_GridRouting;
        row_max = ( uy1 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
676 677 678
    }
    else
    {
679 680
        row_min = ( uy1 - lg ) / RoutingMatrix.m_GridRouting;
        row_max = ( uy0 + lg + demi_pas ) / RoutingMatrix.m_GridRouting;
681 682 683 684
    }

    if( row_min < 0 )
        row_min = 0;
685

686 687
    if( row_min > ( RoutingMatrix.m_Nrows - 1 ) )
        row_min = RoutingMatrix.m_Nrows - 1;
688

689 690
    if( row_max < 0 )
        row_max = 0;
691

692 693
    if( row_max > ( RoutingMatrix.m_Nrows - 1 ) )
        row_max = RoutingMatrix.m_Nrows - 1;
694

695 696
    dx = ux1 - ux0;
    dy = uy1 - uy0;
697

698
    double angle;
699
    if( dx )
700
    {
701
        angle = ArcTangente( dy, dx );
702
    }
703 704
    else
    {
705
        angle = 900;
706

707
        if( dy < 0 )
708 709 710
            angle = -900;
    }

711
    RotatePoint( &dx, &dy, angle );   // dx = length, dy = 0
712

713 714 715
    for( col = col_min; col <= col_max; col++ )
    {
        int cxr;
716
        cxr = ( col * RoutingMatrix.m_GridRouting ) - ux0;
717

718
        for( row = row_min; row <= row_max; row++ )
719
        {
720
            cy = (row * RoutingMatrix.m_GridRouting) - uy0;
721 722
            cx = cxr;
            RotatePoint( &cx, &cy, angle );
723

724
            if( abs( cy ) > lg )
725
                continue;             // The point is too far on the Y axis.
726

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

736
            // Examination of extremities are rounded.
737
            if( ( cx < 0 ) && ( cx >= -lg ) )
738
            {
739
                if( ( ( cx * cx ) + ( cy * cy ) ) <= ( lg * lg ) )
740
                    OP_CELL( layer, row, col );
741

742 743
                continue;
            }
744

745
            if( ( cx > dx ) && ( cx <= ( dx + lg ) ) )
746
            {
747
                if( ( ( ( cx - dx ) * ( cx - dx ) ) + ( cy * cy ) ) <= ( lg * lg ) )
748
                    OP_CELL( layer, row, col );
749

750 751 752 753
                continue;
            }
        }
    }
754 755
}

756

757 758 759
/* 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.
760
 */
761
void TraceCircle( int ux0, int uy0, int ux1, int uy1, int lg, LAYER_NUM layer,
762
                  int color, int op_logic )
763
{
764
    int radius, nb_segm;
765 766
    int x0, y0,             // Starting point of the current segment trace.
        x1, y1;             // End point.
767 768 769
    int ii;
    int angle;

770
    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
771

772
    x0 = x1 = radius;
773
    y0 = y1 = 0;
774

775 776
    if( lg < 1 )
        lg = 1;
777

778
    nb_segm = ( 2 * radius ) / lg;
779

780 781
    if( nb_segm < 5 )
        nb_segm = 5;
782

783 784
    if( nb_segm > 100 )
        nb_segm = 100;
785

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

796
    DrawSegmentQcq( x1 + ux0, y1 + uy0, ux0 + radius, uy0, lg, layer, color, op_logic );
797 798
}

799

800 801 802 803
/* 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.
804
 */
805
void TraceArc( int ux0, int uy0, int ux1, int uy1, double ArcAngle, int lg,
806
               LAYER_NUM layer, int color, int op_logic )
807
{
808
    int radius, nb_segm;
809 810
    int x0, y0,             // Starting point of the current segment trace
        x1, y1;             // End point
811
    int ii;
812
    double angle, StAngle;
813 814


815
    radius = KiROUND( Distance( ux0, uy0, ux1, uy1 ) );
816

817 818
    x0 = ux1 - ux0;
    y0 = uy1 - uy0;
819
    StAngle = ArcTangente( uy1 - uy0, ux1 - ux0 );
820

821 822
    if( lg < 1 )
        lg = 1;
823

824
    nb_segm = ( 2 * radius ) / lg;
825
    nb_segm = ( nb_segm * std::abs( ArcAngle ) ) / 3600;
826

827 828
    if( nb_segm < 5 )
        nb_segm = 5;
829

830 831 832 833 834
    if( nb_segm > 100 )
        nb_segm = 100;

    for( ii = 1; ii <= nb_segm; ii++ )
    {
835
        angle  = ( ArcAngle * ii ) / nb_segm;
836 837
        angle += StAngle;

838
        NORMALIZE_ANGLE_POS( angle );
839

840 841
        x1 = KiROUND( cosdecideg( radius, angle ) );
        y1 = KiROUND( cosdecideg( radius, angle ) );
842
        DrawSegmentQcq( x0 + ux0, y0 + uy0, x1 + ux0, y1 + uy0, lg, layer, color, op_logic );
843 844
        x0 = x1;
        y0 = y1;
845
    }
846
}