KiCad PCB EDA Suite
ar_autoplacer.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2012 Jean-Pierre Charras, [email protected]
5 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <[email protected]>
6 * Copyright (C) 2011 Wayne Stambaugh <[email protected]>
7 *
8 * Copyright (C) 1992-2021 KiCad Developers, see AUTHORS.txt for contributors.
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28#include <confirm.h>
29#include <pcbnew.h>
30#include <pcb_edit_frame.h>
31#include <widgets/msgpanel.h>
32#include <board.h>
33#include <footprint.h>
34#include <pcb_shape.h>
35#include <pad.h>
36#include <board_commit.h>
38#include <progress_reporter.h>
39
40#include "ar_autoplacer.h"
41#include "ar_matrix.h"
42#include <memory>
44
45#define AR_GAIN 16
46#define AR_KEEPOUT_MARGIN 500
47#define AR_ABORT_PLACEMENT -1
48
49#define STEP_AR_MM 1.0
50
51/* Bits characterizing cell */
52#define CELL_IS_EMPTY 0x00
53#define CELL_IS_HOLE 0x01 /* a conducting hole or obstacle */
54#define CELL_IS_MODULE 0x02 /* auto placement occupied by a footprint */
55#define CELL_IS_EDGE 0x20 /* Area and auto-placement: limiting cell contour (Board, Zone) */
56#define CELL_IS_FRIEND 0x40 /* Area and auto-placement: cell part of the net */
57#define CELL_IS_ZONE 0x80 /* Area and auto-placement: cell available */
58
59
61{
62 m_board = aBoard;
63 m_connectivity = std::make_unique<CONNECTIVITY_DATA>( );
64
65 for( FOOTPRINT* footprint : m_board->Footprints() )
66 m_connectivity->Add( footprint );
67
69 m_progressReporter = nullptr;
70 m_refreshCallback = nullptr;
71 m_minCost = 0.0;
72}
73
74
75void AR_AUTOPLACER::placeFootprint( FOOTPRINT* aFootprint, bool aDoNotRecreateRatsnest,
76 const VECTOR2I& aPos )
77{
78 if( !aFootprint )
79 return;
80
81 aFootprint->SetPosition( aPos );
82 m_connectivity->Update( aFootprint );
83}
84
85
87{
89
91
92 if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
93 return 0;
94
95 // Build the board shape
99
101 int nbCells = m_matrix.m_Ncols * m_matrix.m_Nrows;
102
103 // Choose the number of board sides.
108
109 // Fill (mark) the cells inside the board:
110 fillMatrix();
111
112 // Other obstacles can be added here:
113 for( auto drawing : m_board->Drawings() )
114 {
115 switch( drawing->Type() )
116 {
117 case PCB_SHAPE_T:
118 if( drawing->GetLayer() != Edge_Cuts )
119 {
122 }
123
124 break;
125
126 default:
127 break;
128 }
129 }
130
131 // Initialize top layer. to the same value as the bottom layer
134 nbCells * sizeof(AR_MATRIX::MATRIX_CELL) );
135
136 return 1;
137}
138
139
141{
142 std::vector <int> x_coordinates;
143 bool success = true;
144 int step = m_matrix.m_GridRouting;
145 VECTOR2I coord_orgin = m_matrix.GetBrdCoordOrigin(); // Board coordinate of matruix cell (0,0)
146
147 // Create a single board outline:
150 const SHAPE_LINE_CHAIN& outline = brd_shape.Outline(0);
151 const BOX2I& rect = outline.BBox();
152
153 // Creates the horizontal segments
154 // Calculate the y limits of the area
155 for( int refy = rect.GetY(), endy = rect.GetBottom(); refy < endy; refy += step )
156 {
157 // The row index (vertical position) of current line scan inside the placement matrix
158 int idy = (refy - coord_orgin.y) / step;
159
160 // Ensure we are still inside the placement matrix
161 if( idy >= m_matrix.m_Nrows )
162 break;
163
164 // Ensure we are inside the placement matrix
165 if( idy <= 0 )
166 continue;
167
168 // find all intersection points of an infinite line with polyline sides
169 x_coordinates.clear();
170
171 for( int v = 0; v < outline.PointCount(); v++ )
172 {
173 int seg_startX = outline.CPoint( v ).x;
174 int seg_startY = outline.CPoint( v ).y;
175 int seg_endX = outline.CPoint( v + 1 ).x;
176 int seg_endY = outline.CPoint( v + 1 ).y;
177
178 /* Trivial cases: skip if ref above or below the segment to test */
179 if( ( seg_startY > refy ) && ( seg_endY > refy ) )
180 continue;
181
182 // segment below ref point, or its Y end pos on Y coordinate ref point: skip
183 if( ( seg_startY <= refy ) && (seg_endY <= refy ) )
184 continue;
185
186 /* at this point refy is between seg_startY and seg_endY
187 * see if an horizontal line at Y = refy is intersecting this segment
188 */
189 // calculate the x position of the intersection of this segment and the
190 // infinite line this is more easier if we move the X,Y axis origin to
191 // the segment start point:
192
193 seg_endX -= seg_startX;
194 seg_endY -= seg_startY;
195 double newrefy = (double) ( refy - seg_startY );
196 double intersec_x;
197
198 if ( seg_endY == 0 ) // horizontal segment on the same line: skip
199 continue;
200
201 // Now calculate the x intersection coordinate of the horizontal line at
202 // y = newrefy and the segment from (0,0) to (seg_endX,seg_endY) with the
203 // horizontal line at the new refy position the line slope is:
204 // slope = seg_endY/seg_endX; and inv_slope = seg_endX/seg_endY
205 // and the x pos relative to the new origin is:
206 // intersec_x = refy/slope = refy * inv_slope
207 // Note: because horizontal segments are already tested and skipped, slope
208 // exists (seg_end_y not O)
209 double inv_slope = (double) seg_endX / seg_endY;
210 intersec_x = newrefy * inv_slope;
211 x_coordinates.push_back( (int) intersec_x + seg_startX );
212 }
213
214 // A line scan is finished: build list of segments
215
216 // Sort intersection points by increasing x value:
217 // So 2 consecutive points are the ends of a segment
218 std::sort( x_coordinates.begin(), x_coordinates.end() );
219
220 // An even number of coordinates is expected, because a segment has 2 ends.
221 // An if this algorithm always works, it must always find an even count.
222 if( ( x_coordinates.size() & 1 ) != 0 )
223 {
224 success = false;
225 break;
226 }
227
228 // Fill cells having the same Y coordinate
229 int iimax = x_coordinates.size() - 1;
230
231 for( int ii = 0; ii < iimax; ii += 2 )
232 {
233 int seg_start_x = x_coordinates[ii] - coord_orgin.x;
234 int seg_end_x = x_coordinates[ii + 1] - coord_orgin.x;
235
236 // Fill cells at y coord = idy,
237 // and at x cood >= seg_start_x and <= seg_end_x
238
239 for( int idx = seg_start_x / step; idx < m_matrix.m_Ncols; idx++ )
240 {
241 if( idx * step > seg_end_x )
242 break;
243
244 if( idx * step >= seg_start_x )
246 }
247 }
248 } // End examine segments in one area
249
250 return success;
251}
252
253
254void AR_AUTOPLACER::addFpBody( const VECTOR2I& aStart, const VECTOR2I& aEnd, LSET aLayerMask )
255{
256 // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
257 if( aLayerMask[ F_Cu ] )
258 {
260 m_fpAreaTop.Append( aStart.x, aStart.y );
261 m_fpAreaTop.Append( aEnd.x, aStart.y );
262 m_fpAreaTop.Append( aEnd.x, aEnd.y );
263 m_fpAreaTop.Append( aStart.x, aEnd.y );
264 }
265
266 if( aLayerMask[ B_Cu ] )
267 {
269 m_fpAreaBottom.Append( aStart.x, aStart.y );
270 m_fpAreaBottom.Append( aEnd.x, aStart.y );
271 m_fpAreaBottom.Append( aEnd.x, aEnd.y );
272 m_fpAreaBottom.Append( aStart.x, aEnd.y );
273 }
274}
275
276
277void AR_AUTOPLACER::addPad( PAD* aPad, int aClearance )
278{
279 // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
280 BOX2I bbox = aPad->GetBoundingBox();
281 bbox.Inflate( aClearance );
282
283 if( aPad->IsOnLayer( F_Cu ) )
284 {
286 m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetTop() );
287 m_fpAreaTop.Append( bbox.GetRight(), bbox.GetTop() );
288 m_fpAreaTop.Append( bbox.GetRight(), bbox.GetBottom() );
289 m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetBottom() );
290 }
291
292 if( aPad->IsOnLayer( B_Cu ) )
293 {
295 m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetTop() );
296 m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetTop() );
297 m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetBottom() );
298 m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetBottom() );
299 }
300}
301
302
303void AR_AUTOPLACER::buildFpAreas( FOOTPRINT* aFootprint, int aFpClearance )
304{
307
308 aFootprint->BuildCourtyardCaches();
309 m_fpAreaTop = aFootprint->GetCourtyard( F_CrtYd );
310 m_fpAreaBottom = aFootprint->GetCourtyard( B_CrtYd );
311
312 LSET layerMask;
313
314 if( aFootprint->GetLayer() == F_Cu )
315 layerMask.set( F_Cu );
316
317 if( aFootprint->GetLayer() == B_Cu )
318 layerMask.set( B_Cu );
319
320 BOX2I fpBBox = aFootprint->GetBoundingBox();
321
322 fpBBox.Inflate( ( m_matrix.m_GridRouting / 2 ) + aFpClearance );
323
324 // Add a minimal area to the fp area:
325 addFpBody( fpBBox.GetOrigin(), fpBBox.GetEnd(), layerMask );
326
327 // Trace pads + clearance areas.
328 for( PAD* pad : aFootprint->Pads() )
329 {
330 int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
331 addPad( pad, margin );
332 }
333}
334
335
337{
338 int ox, oy, fx, fy;
339 LSET layerMask;
340 BOX2I fpBBox = Module->GetBoundingBox();
341
342 fpBBox.Inflate( m_matrix.m_GridRouting / 2 );
343 ox = fpBBox.GetX();
344 fx = fpBBox.GetRight();
345 oy = fpBBox.GetY();
346 fy = fpBBox.GetBottom();
347
348 if( ox < m_matrix.m_BrdBox.GetX() )
349 ox = m_matrix.m_BrdBox.GetX();
350
351 if( ox > m_matrix.m_BrdBox.GetRight() )
353
354 if( fx < m_matrix.m_BrdBox.GetX() )
355 fx = m_matrix.m_BrdBox.GetX();
356
357 if( fx > m_matrix.m_BrdBox.GetRight() )
359
360 if( oy < m_matrix.m_BrdBox.GetY() )
361 oy = m_matrix.m_BrdBox.GetY();
362
363 if( oy > m_matrix.m_BrdBox.GetBottom() )
365
366 if( fy < m_matrix.m_BrdBox.GetY() )
367 fy = m_matrix.m_BrdBox.GetY();
368
369 if( fy > m_matrix.m_BrdBox.GetBottom() )
371
372 if( Module->GetLayer() == F_Cu )
373 layerMask.set( F_Cu );
374
375 if( Module->GetLayer() == B_Cu )
376 layerMask.set( B_Cu );
377
378 m_matrix.TraceFilledRectangle( ox, oy, fx, fy, layerMask,
380
381 // Trace pads + clearance areas.
382 for( PAD* pad : Module->Pads() )
383 {
384 int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
386 }
387
388 // Trace clearance.
389 int margin = ( m_matrix.m_GridRouting * Module->GetPadCount() ) / AR_GAIN;
390 m_matrix.CreateKeepOutRectangle( ox, oy, fx, fy, margin, AR_KEEPOUT_MARGIN , layerMask );
391
392 // Build the footprint courtyard
393 buildFpAreas( Module, margin );
394
395 // Substract the shape to free areas
398}
399
400
401int AR_AUTOPLACER::testRectangle( const BOX2I& aRect, int side )
402{
403 BOX2I rect = aRect;
404
405 rect.Inflate( m_matrix.m_GridRouting / 2 );
406
407 VECTOR2I start = rect.GetOrigin();
408 VECTOR2I end = rect.GetEnd();
409
410 start -= m_matrix.m_BrdBox.GetOrigin();
411 end -= m_matrix.m_BrdBox.GetOrigin();
412
413 int row_min = start.y / m_matrix.m_GridRouting;
414 int row_max = end.y / m_matrix.m_GridRouting;
415 int col_min = start.x / m_matrix.m_GridRouting;
416 int col_max = end.x / m_matrix.m_GridRouting;
417
418 if( start.y > row_min * m_matrix.m_GridRouting )
419 row_min++;
420
421 if( start.x > col_min * m_matrix.m_GridRouting )
422 col_min++;
423
424 if( row_min < 0 )
425 row_min = 0;
426
427 if( row_max >= ( m_matrix.m_Nrows - 1 ) )
428 row_max = m_matrix.m_Nrows - 1;
429
430 if( col_min < 0 )
431 col_min = 0;
432
433 if( col_max >= ( m_matrix.m_Ncols - 1 ) )
434 col_max = m_matrix.m_Ncols - 1;
435
436 for( int row = row_min; row <= row_max; row++ )
437 {
438 for( int col = col_min; col <= col_max; col++ )
439 {
440 unsigned int data = m_matrix.GetCell( row, col, side );
441
442 if( ( data & CELL_IS_ZONE ) == 0 )
443 return AR_OUT_OF_BOARD;
444
445 if( (data & CELL_IS_MODULE) )
447 }
448 }
449
450 return AR_FREE_CELL;
451}
452
453
454unsigned int AR_AUTOPLACER::calculateKeepOutArea( const BOX2I& aRect, int side )
455{
456 VECTOR2I start = aRect.GetOrigin();
457 VECTOR2I end = aRect.GetEnd();
458
459 start -= m_matrix.m_BrdBox.GetOrigin();
460 end -= m_matrix.m_BrdBox.GetOrigin();
461
462 int row_min = start.y / m_matrix.m_GridRouting;
463 int row_max = end.y / m_matrix.m_GridRouting;
464 int col_min = start.x / m_matrix.m_GridRouting;
465 int col_max = end.x / m_matrix.m_GridRouting;
466
467 if( start.y > row_min * m_matrix.m_GridRouting )
468 row_min++;
469
470 if( start.x > col_min * m_matrix.m_GridRouting )
471 col_min++;
472
473 if( row_min < 0 )
474 row_min = 0;
475
476 if( row_max >= ( m_matrix.m_Nrows - 1 ) )
477 row_max = m_matrix.m_Nrows - 1;
478
479 if( col_min < 0 )
480 col_min = 0;
481
482 if( col_max >= ( m_matrix.m_Ncols - 1 ) )
483 col_max = m_matrix.m_Ncols - 1;
484
485 unsigned int keepOutCost = 0;
486
487 for( int row = row_min; row <= row_max; row++ )
488 {
489 for( int col = col_min; col <= col_max; col++ )
490 {
491 // m_matrix.GetDist returns the "cost" of the cell
492 // at position (row, col)
493 // in autoplace this is the cost of the cell, if it is
494 // inside aRect
495 keepOutCost += m_matrix.GetDist( row, col, side );
496 }
497 }
498
499 return keepOutCost;
500}
501
502
503int AR_AUTOPLACER::testFootprintOnBoard( FOOTPRINT* aFootprint, bool TstOtherSide,
504 const VECTOR2I& aOffset )
505{
506 int side = AR_SIDE_TOP;
507 int otherside = AR_SIDE_BOTTOM;
508
509 if( aFootprint->GetLayer() == B_Cu )
510 {
511 side = AR_SIDE_BOTTOM; otherside = AR_SIDE_TOP;
512 }
513
514 BOX2I fpBBox = aFootprint->GetBoundingBox( false, false );
515 fpBBox.Move( -1*aOffset );
516
517 buildFpAreas( aFootprint, 0 );
518
519 int diag = //testModuleByPolygon( aFootprint, side, aOffset );
520 testRectangle( fpBBox, side );
521
522 if( diag != AR_FREE_CELL )
523 return diag;
524
525 if( TstOtherSide )
526 {
527 diag = //testModuleByPolygon( aFootprint, otherside, aOffset );
528 testRectangle( fpBBox, otherside );
529
530 if( diag != AR_FREE_CELL )
531 return diag;
532 }
533
534 int marge = ( m_matrix.m_GridRouting * aFootprint->GetPadCount() ) / AR_GAIN;
535
536 fpBBox.Inflate( marge );
537 return calculateKeepOutArea( fpBBox, side );
538}
539
540
542{
543 int error = 1;
544 VECTOR2I lastPosOK;
545 double min_cost, curr_cost, Score;
546 bool testOtherSide;
547
548 lastPosOK = m_matrix.m_BrdBox.GetOrigin();
549
550 VECTOR2I fpPos = aFootprint->GetPosition();
551 BOX2I fpBBox = aFootprint->GetBoundingBox( false, false );
552
553 // Move fpBBox to have the footprint position at (0,0)
554 fpBBox.Move( -fpPos );
555 VECTOR2I fpBBoxOrg = fpBBox.GetOrigin();
556
557 // Calculate the limit of the footprint position, relative to the routing matrix area
558 VECTOR2I xylimit = m_matrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
559
560 VECTOR2I initialPos = m_matrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
561
562 // Stay on grid.
563 initialPos.x -= initialPos.x % m_matrix.m_GridRouting;
564 initialPos.y -= initialPos.y % m_matrix.m_GridRouting;
565
566 m_curPosition = initialPos;
567 VECTOR2I fpOffset = fpPos - m_curPosition;
568
569 // Examine pads, and set testOtherSide to true if a footprint has at least 1 pad through.
570 testOtherSide = false;
571
573 {
574 LSET other( aFootprint->GetLayer() == B_Cu ? F_Cu : B_Cu );
575
576 for( PAD* pad : aFootprint->Pads() )
577 {
578 if( !( pad->GetLayerSet() & other ).any() )
579 continue;
580
581 testOtherSide = true;
582 break;
583 }
584 }
585
586 fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
587
588 min_cost = -1.0;
589// m_frame->SetStatusText( wxT( "Score ??, pos ??" ) );
590
591
592 for( ; m_curPosition.x < xylimit.x; m_curPosition.x += m_matrix.m_GridRouting )
593 {
594 m_curPosition.y = initialPos.y;
595
596 for( ; m_curPosition.y < xylimit.y; m_curPosition.y += m_matrix.m_GridRouting )
597 {
598
599 fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
600 fpOffset = fpPos - m_curPosition;
601 int keepOutCost = testFootprintOnBoard( aFootprint, testOtherSide, fpOffset );
602
603 if( keepOutCost >= 0 ) // i.e. if the footprint can be put here
604 {
605 error = 0;
606 // m_frame->build_ratsnest_footprint( aFootprint ); // fixme
607 curr_cost = computePlacementRatsnestCost( aFootprint, fpOffset );
608 Score = curr_cost + keepOutCost;
609
610 if( (min_cost >= Score ) || (min_cost < 0 ) )
611 {
612 lastPosOK = m_curPosition;
613 min_cost = Score;
614/*
615 wxString msg;
616 msg.Printf( wxT( "Score %g, pos %s, %s" ),
617 min_cost,
618 ::CoordinateToString( LastPosOK.x ),
619 ::CoordinateToString( LastPosOK.y ) );
620 m_frame->SetStatusText( msg );*/
621 }
622 }
623 }
624 }
625
626 // Regeneration of the modified variable.
627 m_curPosition = lastPosOK;
628
629 m_minCost = min_cost;
630 return error;
631}
632
633
634const PAD* AR_AUTOPLACER::nearestPad( FOOTPRINT* aRefFP, PAD* aRefPad, const VECTOR2I& aOffset )
635{
636 const PAD* nearest = nullptr;
637 int64_t nearestDist = INT64_MAX;
638
639 for( FOOTPRINT* footprint : m_board->Footprints() )
640 {
641 if ( footprint == aRefFP )
642 continue;
643
644 if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
645 continue;
646
647 for( PAD* pad: footprint->Pads() )
648 {
649 if( pad->GetNetCode() != aRefPad->GetNetCode() || pad->GetNetCode() <= 0 )
650 continue;
651
652 auto dist = ( VECTOR2I( aRefPad->GetPosition() - aOffset ) -
653 VECTOR2I( pad->GetPosition() ) ).EuclideanNorm();
654
655 if ( dist < nearestDist )
656 {
657 nearestDist = dist;
658 nearest = pad;
659 }
660 }
661 }
662
663 return nearest;
664}
665
666
668{
669 double curr_cost;
670 VECTOR2I start; // start point of a ratsnest
671 VECTOR2I end; // end point of a ratsnest
672 int dx, dy;
673
674 curr_cost = 0;
675
676 for( PAD* pad : aFootprint->Pads() )
677 {
678 const PAD* nearest = nearestPad( aFootprint, pad, aOffset );
679
680 if( !nearest )
681 continue;
682
683 start = VECTOR2I( pad->GetPosition() ) - VECTOR2I(aOffset);
684 end = VECTOR2I( nearest->GetPosition() );
685
686 //m_overlay->SetIsStroke( true );
687 //m_overlay->SetStrokeColor( COLOR4D(0.0, 1.0, 0.0, 1.0) );
688 //m_overlay->Line( start, end );
689
690 // Cost of the ratsnest.
691 dx = end.x - start.x;
692 dy = end.y - start.y;
693
694 dx = abs( dx );
695 dy = abs( dy );
696
697 // ttry to have always dx >= dy to calculate the cost of the ratsnest
698 if( dx < dy )
699 std::swap( dx, dy );
700
701 // Cost of the connection = length + penalty due to the slope
702 // dx is the biggest length relative to the X or Y axis
703 // the penalty is max for 45 degrees ratsnests,
704 // and 0 for horizontal or vertical ratsnests.
705 // For Horizontal and Vertical ratsnests, dy = 0;
706 double conn_cost = hypot( dx, dy * 2.0 );
707 curr_cost += conn_cost; // Total cost = sum of costs of each connection
708 }
709
710 return curr_cost;
711}
712
713
714// Sort routines
715static bool sortFootprintsByComplexity( FOOTPRINT* ref, FOOTPRINT* compare )
716{
717 double ff1, ff2;
718
719 ff1 = ref->GetArea() * ref->GetPadCount();
720 ff2 = compare->GetArea() * compare->GetPadCount();
721
722 return ff2 < ff1;
723}
724
725
727{
728 double ff1, ff2;
729
730 ff1 = ref->GetArea() * ref->GetFlag();
731 ff2 = compare->GetArea() * compare->GetFlag();
732 return ff2 < ff1;
733}
734
735
737{
738 std::vector<FOOTPRINT*> fpList;
739
740
741 for( FOOTPRINT* footprint : m_board->Footprints() )
742 fpList.push_back( footprint );
743
744 sort( fpList.begin(), fpList.end(), sortFootprintsByComplexity );
745
746 for( unsigned kk = 0; kk < fpList.size(); kk++ )
747 {
748 FOOTPRINT* footprint = fpList[kk];
749 footprint->SetFlag( 0 );
750
751 if( !footprint->NeedsPlaced() )
752 continue;
753
754 m_connectivity->Update( footprint );
755 }
756
757 m_connectivity->RecalculateRatsnest();
758
759 for( unsigned kk = 0; kk < fpList.size(); kk++ )
760 {
761 FOOTPRINT* footprint = fpList[kk];
762
763 auto edges = m_connectivity->GetRatsnestForComponent( footprint, true );
764
765 footprint->SetFlag( edges.size() ) ;
766 }
767
768 sort( fpList.begin(), fpList.end(), sortFootprintsByRatsnestSize );
769
770 // Search for "best" footprint.
771 FOOTPRINT* bestFootprint = nullptr;
772 FOOTPRINT* altFootprint = nullptr;
773
774 for( unsigned ii = 0; ii < fpList.size(); ii++ )
775 {
776 FOOTPRINT* footprint = fpList[ii];
777
778 if( !footprint->NeedsPlaced() )
779 continue;
780
781 altFootprint = footprint;
782
783 if( footprint->GetFlag() == 0 )
784 continue;
785
786 bestFootprint = footprint;
787 break;
788 }
789
790 if( bestFootprint )
791 return bestFootprint;
792 else
793 return altFootprint;
794}
795
796
798{
799 // Draw the board free area
800 m_overlay->Clear();
801 m_overlay->SetIsFill( true );
802 m_overlay->SetIsStroke( false );
803
806
807 // Draw the free polygon areas, top side:
808 if( freeArea.OutlineCount() > 0 )
809 {
810 m_overlay->SetIsFill( true );
811 m_overlay->SetIsStroke( false );
812 m_overlay->SetFillColor( COLOR4D(0.7, 0.0, 0.1, 0.2) );
813 m_overlay->Polygon( freeArea );
814 }
815
816 freeArea = m_bottomFreeArea;
818
819 // Draw the free polygon areas, bottom side:
820 if( freeArea.OutlineCount() > 0 )
821 {
822 m_overlay->SetFillColor( COLOR4D(0.0, 0.7, 0.0, 0.2) );
823 m_overlay->Polygon( freeArea );
824 }
825}
826
827
828AR_RESULT AR_AUTOPLACER::AutoplaceFootprints( std::vector<FOOTPRINT*>& aFootprints,
829 BOARD_COMMIT* aCommit,
830 bool aPlaceOffboardModules )
831{
832 VECTOR2I memopos;
833 int error;
834 bool cancelled = false;
835
836 memopos = m_curPosition;
837
838 m_matrix.m_GridRouting = m_gridSize; //(int) m_frame->GetScreen()->GetGridSize().x;
839
840 // Ensure Board.m_GridRouting has a reasonable value:
843
844 // Compute footprint parameters used in autoplace
845 if( genPlacementRoutingMatrix( ) == 0 )
846 return AR_FAILURE;
847
848 int placedCount = 0;
849
850 for( FOOTPRINT* footprint : m_board->Footprints() )
851 footprint->SetNeedsPlaced( false );
852
853 std::vector<FOOTPRINT*> offboardMods;
854
855 if( aPlaceOffboardModules )
856 {
857 for( FOOTPRINT* footprint : m_board->Footprints() )
858 {
859 if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
860 offboardMods.push_back( footprint );
861 }
862 }
863
864 for( FOOTPRINT* footprint : aFootprints )
865 {
866 footprint->SetNeedsPlaced( true );
867 aCommit->Modify( footprint );
868 }
869
870 for( FOOTPRINT* footprint : offboardMods )
871 {
872 footprint->SetNeedsPlaced( true );
873 aCommit->Modify( footprint );
874 }
875
876 for( FOOTPRINT* footprint : m_board->Footprints() )
877 {
878 if( footprint->NeedsPlaced() ) // Erase from screen
879 placedCount++;
880 else
881 genModuleOnRoutingMatrix( footprint );
882 }
883
884
885 int cnt = 0;
886
888 {
889 m_progressReporter->Report( _( "Autoplacing components..." ) );
890 m_progressReporter->SetMaxProgress( placedCount );
891 }
892
894
896 m_refreshCallback( nullptr );
897
898 FOOTPRINT* footprint;
899
900 while( ( footprint = pickFootprint() ) != nullptr )
901 {
902 // Display some info about activity, footprint placement can take a while:
903
905 m_progressReporter->SetTitle( wxString::Format( _( "Autoplacing %s" ),
906 footprint->GetReference() ) );
907
908 error = getOptimalFPPlacement( footprint );
909
910 if( error == AR_ABORT_PLACEMENT )
911 break;
912
913 // Place footprint.
914 placeFootprint( footprint, true, m_curPosition );
915
916 genModuleOnRoutingMatrix( footprint );
917 footprint->SetIsPlaced( true );
918 footprint->SetNeedsPlaced( false );
920
922 m_refreshCallback( footprint );
923
925 {
927
928 if ( !m_progressReporter->KeepRefreshing( false ) )
929 {
930 cancelled = true;
931 break;
932 }
933 }
934
935 cnt++;
936 }
937
938 m_curPosition = memopos;
939
941
942 return cancelled ? AR_CANCELLED : AR_COMPLETED;
943}
#define CELL_IS_MODULE
#define STEP_AR_MM
#define AR_KEEPOUT_MARGIN
#define AR_GAIN
#define CELL_IS_ZONE
#define CELL_IS_EDGE
static bool sortFootprintsByRatsnestSize(FOOTPRINT *ref, FOOTPRINT *compare)
#define AR_ABORT_PLACEMENT
#define CELL_IS_HOLE
static bool sortFootprintsByComplexity(FOOTPRINT *ref, FOOTPRINT *compare)
AR_RESULT
Definition: ar_autoplacer.h:49
@ AR_COMPLETED
Definition: ar_autoplacer.h:50
@ AR_FAILURE
Definition: ar_autoplacer.h:52
@ AR_CANCELLED
Definition: ar_autoplacer.h:51
@ AR_FREE_CELL
Definition: ar_autoplacer.h:45
@ AR_OCCUIPED_BY_MODULE
Definition: ar_autoplacer.h:44
@ AR_OUT_OF_BOARD
Definition: ar_autoplacer.h:43
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:42
#define AR_SIDE_TOP
Definition: ar_matrix.h:41
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity
void drawPlacementRoutingMatrix()
int getOptimalFPPlacement(FOOTPRINT *aFootprint)
AR_RESULT AutoplaceFootprints(std::vector< FOOTPRINT * > &aFootprints, BOARD_COMMIT *aCommit, bool aPlaceOffboardModules=false)
int testRectangle(const BOX2I &aRect, int side)
SHAPE_POLY_SET m_fpAreaTop
bool fillMatrix()
Fill m_matrix cells from m_boardShape.
AR_AUTOPLACER(BOARD *aBoard)
PROGRESS_REPORTER * m_progressReporter
const PAD * nearestPad(FOOTPRINT *aRefFP, PAD *aRefPad, const VECTOR2I &aOffset)
void buildFpAreas(FOOTPRINT *aFootprint, int aFpClearance)
unsigned int calculateKeepOutArea(const BOX2I &aRect, int side)
void placeFootprint(FOOTPRINT *aFootprint, bool aDoNotRecreateRatsnest, const VECTOR2I &aPos)
FOOTPRINT * pickFootprint()
Find the "best" footprint place.
void genModuleOnRoutingMatrix(FOOTPRINT *aFootprint)
SHAPE_POLY_SET m_topFreeArea
void addPad(PAD *aPad, int aClearance)
int testFootprintOnBoard(FOOTPRINT *aFootprint, bool TstOtherSide, const VECTOR2I &aOffset)
AR_MATRIX m_matrix
SHAPE_POLY_SET m_fpAreaBottom
double computePlacementRatsnestCost(FOOTPRINT *aFootprint, const VECTOR2I &aOffset)
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay
SHAPE_POLY_SET m_boardShape
VECTOR2I m_curPosition
int genPlacementRoutingMatrix()
SHAPE_POLY_SET m_bottomFreeArea
void addFpBody(const VECTOR2I &aStart, const VECTOR2I &aEnd, LSET aLayerMask)
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:129
int m_Nrows
Definition: ar_matrix.h:144
unsigned char MATRIX_CELL
Definition: ar_matrix.h:50
BOX2I m_BrdBox
Definition: ar_matrix.h:143
void TraceSegmentPcb(PCB_SHAPE *aShape, int aColor, int aMargin, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:753
int m_RoutingLayersCount
Definition: ar_matrix.h:141
void SetCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: ar_matrix.cpp:181
@ WRITE_OR_CELL
Definition: ar_matrix.h:56
@ WRITE_CELL
Definition: ar_matrix.h:55
PCB_LAYER_ID m_routeLayerBottom
Definition: ar_matrix.h:149
int InitRoutingMatrix()
Initialize the data structures.
Definition: ar_matrix.cpp:92
MATRIX_CELL * m_BoardSide[AR_MAX_ROUTING_LAYERS_COUNT]
Definition: ar_matrix.h:138
bool ComputeMatrixSize(const BOX2I &aBoundingBox)
Calculate the number of rows and columns of dimensions of aPcb for routing and automatic calculation ...
Definition: ar_matrix.cpp:62
int m_GridRouting
Definition: ar_matrix.h:142
DIST_CELL GetDist(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:235
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:170
VECTOR2I GetBrdCoordOrigin()
Definition: ar_matrix.h:74
int m_Ncols
Definition: ar_matrix.h:144
void TraceFilledRectangle(int ux0, int uy0, int ux1, int uy1, double angle, LSET aLayerMask, int color, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:603
void CreateKeepOutRectangle(int ux0, int uy0, int ux1, int uy1, int marge, int aKeepOut, LSET aLayerMask)
Function CreateKeepOutRectangle builds the cost map: Cells ( in Dist map ) inside the rect x0,...
Definition: ar_matrix.cpp:795
void PlacePad(PAD *aPad, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:900
PCB_LAYER_ID m_routeLayerTop
Definition: ar_matrix.h:148
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:265
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:823
bool GetBoardPolygonOutlines(SHAPE_POLY_SET &aOutlines, OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
Extract the board outlines and build a closed polygon from lines, arcs and circle items on edge cut l...
Definition: board.cpp:1911
FOOTPRINTS & Footprints()
Definition: board.h:307
DRAWINGS & Drawings()
Definition: board.h:310
void SetOrigin(const Vec &pos)
Definition: box2.h:202
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetTop() const
Definition: box2.h:194
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetY() const
Definition: box2.h:181
coord_type GetWidth() const
Definition: box2.h:187
const Vec GetEnd() const
Definition: box2.h:185
void Move(const Vec &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: box2.h:111
bool Contains(const Vec &aPoint) const
Definition: box2.h:141
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetLeft() const
Definition: box2.h:193
coord_type GetBottom() const
Definition: box2.h:190
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
void SetPosition(const VECTOR2I &aPos) override
Definition: footprint.cpp:1658
void SetIsPlaced(bool isPlaced)
Definition: footprint.h:364
void SetFlag(int aFlag)
Definition: footprint.h:253
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
Return the number of pads.
Definition: footprint.cpp:1198
PCB_LAYER_ID GetLayer() const override
Return the primary layer this item is on.
Definition: footprint.h:200
PADS & Pads()
Definition: footprint.h:170
bool NeedsPlaced() const
Definition: footprint.h:372
void BuildCourtyardCaches(OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
Build complex polygons of the courtyard areas from graphic items on the courtyard layers.
Definition: footprint.cpp:2215
double GetArea(int aPadding=0) const
Definition: footprint.cpp:703
void SetNeedsPlaced(bool needsPlaced)
Definition: footprint.h:373
const wxString & GetReference() const
Definition: footprint.h:519
const SHAPE_POLY_SET & GetCourtyard(PCB_LAYER_ID aLayer) const
Used in DRC to test the courtyard area (a complex polygon).
Definition: footprint.cpp:2203
int GetFlag() const
Definition: footprint.h:255
VECTOR2I GetPosition() const override
Definition: footprint.h:188
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:794
A color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:104
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:530
Definition: pad.h:59
const BOX2I GetBoundingBox() const override
The bounding box is cached, so this will be efficient most of the time.
Definition: pad.cpp:622
bool IsOnLayer(PCB_LAYER_ID aLayer) const override
Test to see if this object is on the given layer.
Definition: pad.h:625
VECTOR2I GetPosition() const override
Definition: pad.h:197
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
virtual void Report(const wxString &aMessage)=0
Display aMessage in the progress bar dialog.
virtual void SetTitle(const wxString &aTitle)=0
Change the title displayed on the window caption.
virtual void AdvanceProgress()=0
Increment the progress bar length (inside the current virtual zone).
virtual void SetMaxProgress(int aMaxProgress)=0
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Represent a set of closed polygons.
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
SHAPE_LINE_CHAIN & Outline(int aIndex)
int NewOutline()
Creates a new hole in a given outline.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SHAPE_POLY_SET CloneDropTriangulation() const
Creates a new empty polygon in the set and returns its index.
This file is part of the common library.
#define _(s)
@ F_CrtYd
Definition: layer_ids.h:117
@ Edge_Cuts
Definition: layer_ids.h:113
@ B_Cu
Definition: layer_ids.h:95
@ B_CrtYd
Definition: layer_ids.h:116
@ F_Cu
Definition: layer_ids.h:64
Message panel definition file.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Class that computes missing connections on a PCB.
constexpr int mmToIU(double mm) const
Definition: base_units.h:89
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:88
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618