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, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2020 KiCad Developers, see change_log.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 <track.h>
35 #include <pcb_shape.h>
36 #include <pad.h>
37 #include <board_commit.h>
40 
41 #include "ar_autoplacer.h"
42 #include "ar_matrix.h"
43 #include <memory>
44 #include <ratsnest/ratsnest_data.h>
45 
46 #define AR_GAIN 16
47 #define AR_KEEPOUT_MARGIN 500
48 #define AR_ABORT_PLACEMENT -1
49 
50 #define STEP_AR_MM 1.0
51 
52 /* Bits characterizing cell */
53 #define CELL_IS_EMPTY 0x00
54 #define CELL_IS_HOLE 0x01 /* a conducting hole or obstacle */
55 #define CELL_IS_MODULE 0x02 /* auto placement occupied by a footprint */
56 #define CELL_IS_EDGE 0x20 /* Area and auto-placement: limiting cell contour (Board, Zone) */
57 #define CELL_IS_FRIEND 0x40 /* Area and auto-placement: cell part of the net */
58 #define CELL_IS_ZONE 0x80 /* Area and auto-placement: cell available */
59 
60 
61 /* Penalty (cost) for CntRot90 and CntRot180:
62  * CntRot90 and CntRot180 are from 0 (rotation allowed) to 10 (rotation not allowed)
63  */
64 static const double OrientationPenalty[11] =
65 {
66  2.0, // CntRot = 0 rotation prohibited
67  1.9, // CntRot = 1
68  1.8, // CntRot = 2
69  1.7, // CntRot = 3
70  1.6, // CntRot = 4
71  1.5, // CntRot = 5
72  1.4, // CntRot = 5
73  1.3, // CntRot = 7
74  1.2, // CntRot = 8
75  1.1, // CntRot = 9
76  1.0 // CntRot = 10 rotation authorized, no penalty
77 };
78 
79 
81 {
82  m_board = aBoard;
83  m_connectivity = std::make_unique<CONNECTIVITY_DATA>( );
84 
85  for( FOOTPRINT* footprint : m_board->Footprints() )
86  m_connectivity->Add( footprint );
87 
89  m_progressReporter = nullptr;
90  m_refreshCallback = nullptr;
91  m_minCost = 0.0;
92 }
93 
94 
95 void AR_AUTOPLACER::placeFootprint( FOOTPRINT* aFootprint, bool aDoNotRecreateRatsnest,
96  const wxPoint& aPos )
97 {
98  if( !aFootprint )
99  return;
100 
101  aFootprint->SetPosition( aPos );
102  m_connectivity->Update( aFootprint );
103 }
104 
105 
107 {
109 
111 
112  if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
113  return 0;
114 
115  // Build the board shape
119 
120  m_matrix.ComputeMatrixSize( bbox );
121  int nbCells = m_matrix.m_Ncols * m_matrix.m_Nrows;
122 
123  // Choose the number of board sides.
128 
129  // Fill (mark) the cells inside the board:
130  fillMatrix();
131 
132  // Other obstacles can be added here:
133  for( auto drawing : m_board->Drawings() )
134  {
135  switch( drawing->Type() )
136  {
137  case PCB_SHAPE_T:
138  if( drawing->GetLayer() != Edge_Cuts )
139  {
142  }
143  break;
144 
145  default:
146  break;
147  }
148  }
149 
150  // Initialize top layer. to the same value as the bottom layer
153  nbCells * sizeof(AR_MATRIX::MATRIX_CELL) );
154 
155  return 1;
156 }
157 
158 
160 {
161  std::vector <int> x_coordinates;
162  bool success = true;
163  int step = m_matrix.m_GridRouting;
164  wxPoint coord_orgin = m_matrix.GetBrdCoordOrigin(); // Board coordinate of matruix cell (0,0)
165 
166  // Create a single board outline:
167  SHAPE_POLY_SET brd_shape = m_boardShape;
168  brd_shape.Fracture( SHAPE_POLY_SET::PM_FAST );
169  const SHAPE_LINE_CHAIN& outline = brd_shape.Outline(0);
170  const BOX2I& rect = outline.BBox();
171 
172  // Creates the horizontal segments
173  // Calculate the y limits of the area
174  for( int refy = rect.GetY(), endy = rect.GetBottom(); refy < endy; refy += step )
175  {
176  // The row index (vertical position) of current line scan inside the placement matrix
177  int idy = (refy - coord_orgin.y) / step;
178 
179  // Ensure we are still inside the placement matrix
180  if( idy >= m_matrix.m_Nrows )
181  break;
182 
183  // Ensure we are inside the placement matrix
184  if( idy <= 0 )
185  continue;
186 
187  // find all intersection points of an infinite line with polyline sides
188  x_coordinates.clear();
189 
190  for( int v = 0; v < outline.PointCount(); v++ )
191  {
192 
193  int seg_startX = outline.CPoint( v ).x;
194  int seg_startY = outline.CPoint( v ).y;
195  int seg_endX = outline.CPoint( v + 1 ).x;
196  int seg_endY = outline.CPoint( v + 1 ).y;
197 
198  /* Trivial cases: skip if ref above or below the segment to test */
199  if( ( seg_startY > refy ) && ( seg_endY > refy ) )
200  continue;
201 
202  // segment below ref point, or its Y end pos on Y coordinate ref point: skip
203  if( ( seg_startY <= refy ) && (seg_endY <= refy ) )
204  continue;
205 
206  /* at this point refy is between seg_startY and seg_endY
207  * see if an horizontal line at Y = refy is intersecting this segment
208  */
209  // calculate the x position of the intersection of this segment and the
210  // infinite line this is more easier if we move the X,Y axis origin to
211  // the segment start point:
212 
213  seg_endX -= seg_startX;
214  seg_endY -= seg_startY;
215  double newrefy = (double) ( refy - seg_startY );
216  double intersec_x;
217 
218  if ( seg_endY == 0 ) // horizontal segment on the same line: skip
219  continue;
220 
221  // Now calculate the x intersection coordinate of the horizontal line at
222  // y = newrefy and the segment from (0,0) to (seg_endX,seg_endY) with the
223  // horizontal line at the new refy position the line slope is:
224  // slope = seg_endY/seg_endX; and inv_slope = seg_endX/seg_endY
225  // and the x pos relative to the new origin is:
226  // intersec_x = refy/slope = refy * inv_slope
227  // Note: because horizontal segments are already tested and skipped, slope
228  // exists (seg_end_y not O)
229  double inv_slope = (double) seg_endX / seg_endY;
230  intersec_x = newrefy * inv_slope;
231  x_coordinates.push_back( (int) intersec_x + seg_startX );
232  }
233 
234  // A line scan is finished: build list of segments
235 
236  // Sort intersection points by increasing x value:
237  // So 2 consecutive points are the ends of a segment
238  std::sort( x_coordinates.begin(), x_coordinates.end() );
239 
240  // An even number of coordinates is expected, because a segment has 2 ends.
241  // An if this algorithm always works, it must always find an even count.
242  if( ( x_coordinates.size() & 1 ) != 0 )
243  {
244  success = false;
245  break;
246  }
247 
248  // Fill cells having the same Y coordinate
249  int iimax = x_coordinates.size() - 1;
250 
251  for( int ii = 0; ii < iimax; ii += 2 )
252  {
253  int seg_start_x = x_coordinates[ii] - coord_orgin.x;
254  int seg_end_x = x_coordinates[ii + 1] - coord_orgin.x;
255  // Fill cells at y coord = idy,
256  // and at x cood >= seg_start_x and <= seg_end_x
257 
258  for( int idx = seg_start_x / step; idx < m_matrix.m_Ncols; idx++ )
259  {
260  if( idx * step > seg_end_x )
261  break;
262 
263  if( idx * step >= seg_start_x )
265  }
266 
267  }
268  } // End examine segments in one area
269 
270  return success;
271 }
272 
273 
274 void AR_AUTOPLACER::rotateFootprint( FOOTPRINT* aFootprint, double angle, bool incremental )
275 {
276  if( aFootprint == NULL )
277  return;
278 
279  if( incremental )
280  aFootprint->SetOrientation( aFootprint->GetOrientation() + angle );
281  else
282  aFootprint->SetOrientation( angle );
283 
284 
285  m_board->GetConnectivity()->Update( aFootprint );
286 }
287 
288 
289 void AR_AUTOPLACER::addFpBody( wxPoint aStart, wxPoint aEnd, LSET aLayerMask )
290 {
291  // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
292  if( aLayerMask[ F_Cu ] )
293  {
295  m_fpAreaTop.Append( aStart.x, aStart.y );
296  m_fpAreaTop.Append( aEnd.x, aStart.y );
297  m_fpAreaTop.Append( aEnd.x, aEnd.y );
298  m_fpAreaTop.Append( aStart.x, aEnd.y );
299  }
300  if( aLayerMask[ B_Cu ] )
301  {
303  m_fpAreaBottom.Append( aStart.x, aStart.y );
304  m_fpAreaBottom.Append( aEnd.x, aStart.y );
305  m_fpAreaBottom.Append( aEnd.x, aEnd.y );
306  m_fpAreaBottom.Append( aStart.x, aEnd.y );
307  }
308 }
309 
310 void AR_AUTOPLACER::addPad( PAD* aPad, int aClearance )
311 {
312  // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
313  EDA_RECT bbox = aPad->GetBoundingBox();
314  bbox.Inflate( aClearance );
315 
316  if( aPad->IsOnLayer( F_Cu ) )
317  {
319  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetTop() );
320  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetTop() );
321  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetBottom() );
322  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetBottom() );
323  }
324  if( aPad->IsOnLayer( B_Cu ) )
325  {
327  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetTop() );
328  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetTop() );
329  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetBottom() );
330  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetBottom() );
331  }
332 }
333 
334 
335 void AR_AUTOPLACER::buildFpAreas( FOOTPRINT* aFootprint, int aFpClearance )
336 {
339 
340  aFootprint->BuildPolyCourtyards();
341  m_fpAreaTop = aFootprint->GetPolyCourtyardFront();
342  m_fpAreaBottom = aFootprint->GetPolyCourtyardBack();
343 
344  LSET layerMask;
345 
346  if( aFootprint->GetLayer() == F_Cu )
347  layerMask.set( F_Cu );
348 
349  if( aFootprint->GetLayer() == B_Cu )
350  layerMask.set( B_Cu );
351 
352  EDA_RECT fpBBox = aFootprint->GetBoundingBox();
353 
354  fpBBox.Inflate( ( m_matrix.m_GridRouting / 2 ) + aFpClearance );
355 
356  // Add a minimal area to the fp area:
357  addFpBody( fpBBox.GetOrigin(), fpBBox.GetEnd(), layerMask );
358 
359  // Trace pads + clearance areas.
360  for( PAD* pad : aFootprint->Pads() )
361  {
362  int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
363  addPad( pad, margin );
364  }
365 }
366 
367 
369 {
370  int ox, oy, fx, fy;
371  LSET layerMask;
372  EDA_RECT fpBBox = Module->GetBoundingBox();
373 
374  fpBBox.Inflate( m_matrix.m_GridRouting / 2 );
375  ox = fpBBox.GetX();
376  fx = fpBBox.GetRight();
377  oy = fpBBox.GetY();
378  fy = fpBBox.GetBottom();
379 
380  if( ox < m_matrix.m_BrdBox.GetX() )
381  ox = m_matrix.m_BrdBox.GetX();
382 
383  if( ox > m_matrix.m_BrdBox.GetRight() )
384  ox = m_matrix.m_BrdBox.GetRight();
385 
386  if( fx < m_matrix.m_BrdBox.GetX() )
387  fx = m_matrix.m_BrdBox.GetX();
388 
389  if( fx > m_matrix.m_BrdBox.GetRight() )
390  fx = m_matrix.m_BrdBox.GetRight();
391 
392  if( oy < m_matrix.m_BrdBox.GetY() )
393  oy = m_matrix.m_BrdBox.GetY();
394 
395  if( oy > m_matrix.m_BrdBox.GetBottom() )
396  oy = m_matrix.m_BrdBox.GetBottom();
397 
398  if( fy < m_matrix.m_BrdBox.GetY() )
399  fy = m_matrix.m_BrdBox.GetY();
400 
401  if( fy > m_matrix.m_BrdBox.GetBottom() )
402  fy = m_matrix.m_BrdBox.GetBottom();
403 
404  if( Module->GetLayer() == F_Cu )
405  layerMask.set( F_Cu );
406 
407  if( Module->GetLayer() == B_Cu )
408  layerMask.set( B_Cu );
409 
410  m_matrix.TraceFilledRectangle( ox, oy, fx, fy, layerMask,
412 
413  // Trace pads + clearance areas.
414  for( PAD* pad : Module->Pads() )
415  {
416  int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
418  }
419 
420  // Trace clearance.
421  int margin = ( m_matrix.m_GridRouting * Module->GetPadCount() ) / AR_GAIN;
422  m_matrix.CreateKeepOutRectangle( ox, oy, fx, fy, margin, AR_KEEPOUT_MARGIN , layerMask );
423 
424  // Build the footprint courtyard
425  buildFpAreas( Module, margin );
426 
427  // Substract the shape to free areas
430 }
431 
432 
433 /* Test if the rectangular area (ux, ux .. y0, y1):
434  * - is a free zone (except OCCUPED_By_MODULE returns)
435  * - is on the working surface of the board (otherwise returns OUT_OF_BOARD)
436  *
437  * Returns OUT_OF_BOARD, or OCCUPED_By_MODULE or FREE_CELL if OK
438  */
439 int AR_AUTOPLACER::testRectangle( const EDA_RECT& aRect, int side )
440 {
441  EDA_RECT rect = aRect;
442 
443  rect.Inflate( m_matrix.m_GridRouting / 2 );
444 
445  wxPoint start = rect.GetOrigin();
446  wxPoint end = rect.GetEnd();
447 
448  start -= m_matrix.m_BrdBox.GetOrigin();
449  end -= m_matrix.m_BrdBox.GetOrigin();
450 
451  int row_min = start.y / m_matrix.m_GridRouting;
452  int row_max = end.y / m_matrix.m_GridRouting;
453  int col_min = start.x / m_matrix.m_GridRouting;
454  int col_max = end.x / m_matrix.m_GridRouting;
455 
456  if( start.y > row_min * m_matrix.m_GridRouting )
457  row_min++;
458 
459  if( start.x > col_min * m_matrix.m_GridRouting )
460  col_min++;
461 
462  if( row_min < 0 )
463  row_min = 0;
464 
465  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
466  row_max = m_matrix.m_Nrows - 1;
467 
468  if( col_min < 0 )
469  col_min = 0;
470 
471  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
472  col_max = m_matrix.m_Ncols - 1;
473 
474  for( int row = row_min; row <= row_max; row++ )
475  {
476  for( int col = col_min; col <= col_max; col++ )
477  {
478  unsigned int data = m_matrix.GetCell( row, col, side );
479 
480  if( ( data & CELL_IS_ZONE ) == 0 )
481  return AR_OUT_OF_BOARD;
482 
483  if( (data & CELL_IS_MODULE) )
484  return AR_OCCUIPED_BY_MODULE;
485  }
486  }
487 
488  return AR_FREE_CELL;
489 }
490 
491 
492 /* Calculates and returns the clearance area of the rectangular surface
493  * aRect):
494  * (Sum of cells in terms of distance)
495  */
496 unsigned int AR_AUTOPLACER::calculateKeepOutArea( const EDA_RECT& aRect, int side )
497 {
498  wxPoint start = aRect.GetOrigin();
499  wxPoint end = aRect.GetEnd();
500 
501  start -= m_matrix.m_BrdBox.GetOrigin();
502  end -= m_matrix.m_BrdBox.GetOrigin();
503 
504  int row_min = start.y / m_matrix.m_GridRouting;
505  int row_max = end.y / m_matrix.m_GridRouting;
506  int col_min = start.x / m_matrix.m_GridRouting;
507  int col_max = end.x / m_matrix.m_GridRouting;
508 
509  if( start.y > row_min * m_matrix.m_GridRouting )
510  row_min++;
511 
512  if( start.x > col_min * m_matrix.m_GridRouting )
513  col_min++;
514 
515  if( row_min < 0 )
516  row_min = 0;
517 
518  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
519  row_max = m_matrix.m_Nrows - 1;
520 
521  if( col_min < 0 )
522  col_min = 0;
523 
524  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
525  col_max = m_matrix.m_Ncols - 1;
526 
527  unsigned int keepOutCost = 0;
528 
529  for( int row = row_min; row <= row_max; row++ )
530  {
531  for( int col = col_min; col <= col_max; col++ )
532  {
533  // m_matrix.GetDist returns the "cost" of the cell
534  // at position (row, col)
535  // in autoplace this is the cost of the cell, if it is
536  // inside aRect
537  keepOutCost += m_matrix.GetDist( row, col, side );
538  }
539  }
540 
541  return keepOutCost;
542 }
543 
544 
545 /* Test if the footprint can be placed on the board.
546  * Returns the value TstRectangle().
547  * Module is known by its bounding box
548  */
549 int AR_AUTOPLACER::testFootprintOnBoard( FOOTPRINT* aFootprint, bool TstOtherSide,
550  const wxPoint& aOffset )
551 {
552  int side = AR_SIDE_TOP;
553  int otherside = AR_SIDE_BOTTOM;
554 
555  if( aFootprint->GetLayer() == B_Cu )
556  {
557  side = AR_SIDE_BOTTOM; otherside = AR_SIDE_TOP;
558  }
559 
560  EDA_RECT fpBBox = aFootprint->GetBoundingBox( false, false );
561  fpBBox.Move( -aOffset );
562 
563  buildFpAreas( aFootprint, 0 );
564 
565  int diag = //testModuleByPolygon( aFootprint, side, aOffset );
566  testRectangle( fpBBox, side );
567 
568  if( diag != AR_FREE_CELL )
569  return diag;
570 
571  if( TstOtherSide )
572  {
573  diag = //testModuleByPolygon( aFootprint, otherside, aOffset );
574  testRectangle( fpBBox, otherside );
575 
576  if( diag != AR_FREE_CELL )
577  return diag;
578  }
579 
580  int marge = ( m_matrix.m_GridRouting * aFootprint->GetPadCount() ) / AR_GAIN;
581 
582  fpBBox.Inflate( marge );
583  return calculateKeepOutArea( fpBBox, side );
584 }
585 
586 
588 {
589  int error = 1;
590  wxPoint lastPosOK;
591  double min_cost, curr_cost, Score;
592  bool testOtherSide;
593 
594  lastPosOK = m_matrix.m_BrdBox.GetOrigin();
595 
596  wxPoint fpPos = aFootprint->GetPosition();
597  EDA_RECT fpBBox = aFootprint->GetBoundingBox( false, false );
598 
599  // Move fpBBox to have the footprint position at (0,0)
600  fpBBox.Move( -fpPos );
601  wxPoint fpBBoxOrg = fpBBox.GetOrigin();
602 
603  // Calculate the limit of the footprint position, relative to the routing matrix area
604  wxPoint xylimit = m_matrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
605 
606  wxPoint initialPos = m_matrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
607 
608  // Stay on grid.
609  initialPos.x -= initialPos.x % m_matrix.m_GridRouting;
610  initialPos.y -= initialPos.y % m_matrix.m_GridRouting;
611 
612  m_curPosition = initialPos;
613  wxPoint fpOffset = fpPos - m_curPosition;
614 
615  // Examine pads, and set testOtherSide to true if a footprint has at least 1 pad through.
616  testOtherSide = false;
617 
619  {
620  LSET other( aFootprint->GetLayer() == B_Cu ? F_Cu : B_Cu );
621 
622  for( PAD* pad : aFootprint->Pads() )
623  {
624  if( !( pad->GetLayerSet() & other ).any() )
625  continue;
626 
627  testOtherSide = true;
628  break;
629  }
630  }
631 
632  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
633 
634  min_cost = -1.0;
635 // m_frame->SetStatusText( wxT( "Score ??, pos ??" ) );
636 
637 
638  for( ; m_curPosition.x < xylimit.x; m_curPosition.x += m_matrix.m_GridRouting )
639  {
640  m_curPosition.y = initialPos.y;
641 
642  for( ; m_curPosition.y < xylimit.y; m_curPosition.y += m_matrix.m_GridRouting )
643  {
644 
645  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
646  fpOffset = fpPos - m_curPosition;
647  int keepOutCost = testFootprintOnBoard( aFootprint, testOtherSide, fpOffset );
648 
649  if( keepOutCost >= 0 ) // i.e. if the footprint can be put here
650  {
651  error = 0;
652  // m_frame->build_ratsnest_footprint( aFootprint ); // fixme
653  curr_cost = computePlacementRatsnestCost( aFootprint, fpOffset );
654  Score = curr_cost + keepOutCost;
655 
656  if( (min_cost >= Score ) || (min_cost < 0 ) )
657  {
658  lastPosOK = m_curPosition;
659  min_cost = Score;
660  wxString msg;
661 /* msg.Printf( wxT( "Score %g, pos %s, %s" ),
662  min_cost,
663  GetChars( ::CoordinateToString( LastPosOK.x ) ),
664  GetChars( ::CoordinateToString( LastPosOK.y ) ) );
665  m_frame->SetStatusText( msg );*/
666  }
667  }
668  }
669  }
670 
671  // Regeneration of the modified variable.
672  m_curPosition = lastPosOK;
673 
674  m_minCost = min_cost;
675  return error;
676 }
677 
678 
679 const PAD* AR_AUTOPLACER::nearestPad( FOOTPRINT *aRefFP, PAD* aRefPad, const wxPoint& aOffset)
680 {
681  const PAD* nearest = nullptr;
682  int64_t nearestDist = INT64_MAX;
683 
684  for( FOOTPRINT* footprint : m_board->Footprints() )
685  {
686  if ( footprint == aRefFP )
687  continue;
688 
689  if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
690  continue;
691 
692  for( PAD* pad: footprint->Pads() )
693  {
694  if( pad->GetNetCode() != aRefPad->GetNetCode() || pad->GetNetCode() <= 0 )
695  continue;
696 
697  auto dist = (VECTOR2I( aRefPad->GetPosition() - aOffset ) - VECTOR2I( pad->GetPosition() ) ).EuclideanNorm();
698 
699  if ( dist < nearestDist )
700  {
701  nearestDist = dist;
702  nearest = pad;
703  }
704  }
705  }
706 
707  return nearest;
708 }
709 
710 
711 double AR_AUTOPLACER::computePlacementRatsnestCost( FOOTPRINT *aFootprint, const wxPoint& aOffset )
712 {
713  double curr_cost;
714  VECTOR2I start; // start point of a ratsnest
715  VECTOR2I end; // end point of a ratsnest
716  int dx, dy;
717 
718  curr_cost = 0;
719 
720  for( PAD* pad : aFootprint->Pads() )
721  {
722  const PAD* nearest = nearestPad( aFootprint, pad, aOffset );
723 
724  if( !nearest )
725  continue;
726 
727  start = VECTOR2I( pad->GetPosition() ) - VECTOR2I(aOffset);
728  end = VECTOR2I( nearest->GetPosition() );
729 
730  //m_overlay->SetIsStroke( true );
731  //m_overlay->SetStrokeColor( COLOR4D(0.0, 1.0, 0.0, 1.0) );
732  //m_overlay->Line( start, end );
733 
734  // Cost of the ratsnest.
735  dx = end.x - start.x;
736  dy = end.y - start.y;
737 
738  dx = abs( dx );
739  dy = abs( dy );
740 
741  // ttry to have always dx >= dy to calculate the cost of the rastsnet
742  if( dx < dy )
743  std::swap( dx, dy );
744 
745  // Cost of the connection = length + penalty due to the slope
746  // dx is the biggest length relative to the X or Y axis
747  // the penalty is max for 45 degrees ratsnests,
748  // and 0 for horizontal or vertical ratsnests.
749  // For Horizontal and Vertical ratsnests, dy = 0;
750  double conn_cost = hypot( dx, dy * 2.0 );
751  curr_cost += conn_cost; // Total cost = sum of costs of each connection
752  }
753 
754  return curr_cost;
755 }
756 
757 
758 // Sort routines
759 static bool sortFootprintsByComplexity( FOOTPRINT* ref, FOOTPRINT* compare )
760 {
761  double ff1, ff2;
762 
763  ff1 = ref->GetArea() * ref->GetPadCount();
764  ff2 = compare->GetArea() * compare->GetPadCount();
765 
766  return ff2 < ff1;
767 }
768 
769 
770 static bool sortFootprintsByRatsnestSize( FOOTPRINT* ref, FOOTPRINT* compare )
771 {
772  double ff1, ff2;
773 
774  ff1 = ref->GetArea() * ref->GetFlag();
775  ff2 = compare->GetArea() * compare->GetFlag();
776  return ff2 < ff1;
777 }
778 
779 
781 {
782  std::vector<FOOTPRINT*> fpList;
783 
784 
785  for( FOOTPRINT* footprint : m_board->Footprints() )
786  fpList.push_back( footprint );
787 
788  sort( fpList.begin(), fpList.end(), sortFootprintsByComplexity );
789 
790  for( unsigned kk = 0; kk < fpList.size(); kk++ )
791  {
792  FOOTPRINT* footprint = fpList[kk];
793  footprint->SetFlag( 0 );
794 
795  if( !footprint->NeedsPlaced() )
796  continue;
797 
798  m_connectivity->Update( footprint );
799  }
800 
801  m_connectivity->RecalculateRatsnest();
802 
803  for( unsigned kk = 0; kk < fpList.size(); kk++ )
804  {
805  FOOTPRINT* footprint = fpList[kk];
806 
807  auto edges = m_connectivity->GetRatsnestForComponent( footprint, true );
808 
809  footprint->SetFlag( edges.size() ) ;
810  }
811 
812  sort( fpList.begin(), fpList.end(), sortFootprintsByRatsnestSize );
813 
814  // Search for "best" footprint.
815  FOOTPRINT* bestFootprint = nullptr;
816  FOOTPRINT* altFootprint = nullptr;
817 
818  for( unsigned ii = 0; ii < fpList.size(); ii++ )
819  {
820  FOOTPRINT* footprint = fpList[ii];
821 
822  if( !footprint->NeedsPlaced() )
823  continue;
824 
825  altFootprint = footprint;
826 
827  if( footprint->GetFlag() == 0 )
828  continue;
829 
830  bestFootprint = footprint;
831  break;
832  }
833 
834  if( bestFootprint )
835  return bestFootprint;
836  else
837  return altFootprint;
838 }
839 
840 
842 {
843  // Draw the board free area
844  m_overlay->Clear();
845  m_overlay->SetIsFill( true );
846  m_overlay->SetIsStroke( false );
847 
848  SHAPE_POLY_SET freeArea = m_topFreeArea;
849  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
850 
851  // Draw the free polygon areas, top side:
852  if( freeArea.OutlineCount() > 0 )
853  {
854  m_overlay->SetIsFill( true );
855  m_overlay->SetIsStroke( false );
856  m_overlay->SetFillColor( COLOR4D(0.7, 0.0, 0.1, 0.2) );
857  m_overlay->Polygon( freeArea );
858  }
859 
860  freeArea = m_bottomFreeArea;
861  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
862 
863  // Draw the free polygon areas, bottom side:
864  if( freeArea.OutlineCount() > 0 )
865  {
866  m_overlay->SetFillColor( COLOR4D(0.0, 0.7, 0.0, 0.2) );
867  m_overlay->Polygon( freeArea );
868  }
869 }
870 
871 
872 AR_RESULT AR_AUTOPLACER::AutoplaceFootprints( std::vector<FOOTPRINT*>& aFootprints,
873  BOARD_COMMIT* aCommit,
874  bool aPlaceOffboardModules )
875 {
876  wxPoint memopos;
877  int error;
878  bool cancelled = false;
879 
880  memopos = m_curPosition;
881 
882  m_matrix.m_GridRouting = m_gridSize; //(int) m_frame->GetScreen()->GetGridSize().x;
883 
884  // Ensure Board.m_GridRouting has a reasonable value:
885  if( m_matrix.m_GridRouting < Millimeter2iu( 0.25 ) )
887 
888  // Compute footprint parameters used in autoplace
889  if( genPlacementRoutingMatrix( ) == 0 )
890  return AR_FAILURE;
891 
892  int placedCount = 0;
893 
894  for( FOOTPRINT* footprint : m_board->Footprints() )
895  footprint->SetNeedsPlaced( false );
896 
897  std::vector<FOOTPRINT*> offboardMods;
898 
899  if( aPlaceOffboardModules )
900  {
901  for( FOOTPRINT* footprint : m_board->Footprints() )
902  {
903  if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
904  offboardMods.push_back( footprint );
905  }
906  }
907 
908  for( FOOTPRINT* footprint : aFootprints )
909  {
910  footprint->SetNeedsPlaced( true );
911  aCommit->Modify( footprint );
912  }
913 
914  for( FOOTPRINT* footprint : offboardMods )
915  {
916  footprint->SetNeedsPlaced( true );
917  aCommit->Modify( footprint );
918  }
919 
920  for( FOOTPRINT* footprint : m_board->Footprints() )
921  {
922  if( footprint->NeedsPlaced() ) // Erase from screen
923  placedCount++;
924  else
925  genModuleOnRoutingMatrix( footprint );
926  }
927 
928 
929  int cnt = 0;
930  wxString msg;
931 
932  if( m_progressReporter )
933  {
934  m_progressReporter->Report( _( "Autoplacing components..." ) );
935  m_progressReporter->SetMaxProgress( placedCount );
936  }
937 
939 
940  if( m_refreshCallback )
941  m_refreshCallback( nullptr );
942 
943  FOOTPRINT* footprint;
944 
945  while( ( footprint = pickFootprint() ) != nullptr )
946  {
947  // Display some info about activity, footprint placement can take a while:
948  //m_frame->SetStatusText( msg );
949 
950  if( m_progressReporter )
952  _( "Autoplacing %s" ), footprint->GetReference() ) );
953 
954  double initialOrient = footprint->GetOrientation();
955 
956  error = getOptimalFPPlacement( footprint );
957  double bestScore = m_minCost;
958  double bestRotation = 0.0;
959  int rotAllowed;
960 
961  if( error == AR_ABORT_PLACEMENT )
962  goto end_of_tst;
963 
964  // Try orientations 90, 180, 270 degrees from initial orientation
965  rotAllowed = footprint->GetPlacementCost180();
966 
967  if( rotAllowed != 0 )
968  {
969  rotateFootprint( footprint, 1800.0, true );
970  error = getOptimalFPPlacement( footprint );
971  m_minCost *= OrientationPenalty[rotAllowed];
972 
973  if( bestScore > m_minCost ) // This orientation is better.
974  {
975  bestScore = m_minCost;
976  bestRotation = 1800.0;
977  }
978  else
979  {
980  rotateFootprint( footprint, initialOrient, false );
981  }
982 
983  if( error == AR_ABORT_PLACEMENT )
984  goto end_of_tst;
985  }
986 
987  // Determine if the best orientation of a footprint is 90.
988  rotAllowed = footprint->GetPlacementCost90();
989 
990  if( rotAllowed != 0 )
991  {
992  rotateFootprint( footprint, 900.0, true );
993  error = getOptimalFPPlacement( footprint );
994  m_minCost *= OrientationPenalty[rotAllowed];
995 
996  if( bestScore > m_minCost ) // This orientation is better.
997  {
998  bestScore = m_minCost;
999  bestRotation = 900.0;
1000  }
1001  else
1002  {
1003  rotateFootprint( footprint, initialOrient, false );
1004  }
1005 
1006  if( error == AR_ABORT_PLACEMENT )
1007  goto end_of_tst;
1008  }
1009 
1010  // Determine if the best orientation of a footprint is -90.
1011  if( rotAllowed != 0 )
1012  {
1013  rotateFootprint( footprint, 2700.0, true );
1014  error = getOptimalFPPlacement( footprint );
1015  m_minCost *= OrientationPenalty[rotAllowed];
1016 
1017  if( bestScore > m_minCost ) // This orientation is better.
1018  {
1019  bestScore = m_minCost;
1020  bestRotation = 2700.0;
1021  }
1022  else
1023  {
1024  rotateFootprint( footprint, initialOrient, false );
1025  }
1026 
1027  if( error == AR_ABORT_PLACEMENT )
1028  goto end_of_tst;
1029  }
1030 
1031 end_of_tst:
1032 
1033  if( error == AR_ABORT_PLACEMENT )
1034  break;
1035 
1036 
1037  bestRotation += initialOrient;
1038 
1039  if( bestRotation != footprint->GetOrientation() )
1040  {
1041  rotateFootprint( footprint, bestRotation, false );
1042  }
1043 
1044  // Place footprint.
1045  placeFootprint( footprint, true, m_curPosition );
1046 
1047  genModuleOnRoutingMatrix( footprint );
1048  footprint->SetIsPlaced( true );
1049  footprint->SetNeedsPlaced( false );
1051 
1052  if( m_refreshCallback )
1053  m_refreshCallback( footprint );
1054 
1055  if( m_progressReporter )
1056  {
1058 
1059  if ( !m_progressReporter->KeepRefreshing( false ) )
1060  {
1061  cancelled = true;
1062  break;
1063  }
1064  }
1065  cnt++;
1066  }
1067 
1068  m_curPosition = memopos;
1069 
1071 
1072  return cancelled ? AR_CANCELLED : AR_COMPLETED;
1073 }
void BuildPolyCourtyards(OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
Build complex polygons of the courtyard areas from graphic items on the courtyard layers.
Definition: footprint.cpp:1931
SHAPE_POLY_SET m_topFreeArea
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:43
bool NeedsPlaced() const
Definition: footprint.h:309
double GetArea(int aPadding=0) const
Definition: footprint.cpp:598
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
int InitRoutingMatrix()
Function InitBoard initializes the data structures.
Definition: ar_matrix.cpp:91
const SHAPE_POLY_SET & GetPolyCourtyardFront() const
Used in DRC to test the courtyard area (a complex polygon).
Definition: footprint.h:651
void Move(const wxPoint &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: eda_rect.cpp:51
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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:1922
PROGRESS_REPORTER * m_progressReporter
void SetNeedsPlaced(bool needsPlaced)
Definition: footprint.h:310
#define CELL_IS_HOLE
void TraceSegmentPcb(PCB_SHAPE *pt_segm, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:765
#define AR_SIDE_TOP
Definition: ar_matrix.h:42
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
Return the number of pads.
Definition: footprint.cpp:1004
int getOptimalFPPlacement(FOOTPRINT *aFootprint)
This file is part of the common library.
int GetPlacementCost180() const
Definition: footprint.h:534
int m_Ncols
Definition: ar_matrix.h:61
int GetX() const
Definition: eda_rect.h:103
int GetTop() const
Definition: eda_rect.h:118
const EDA_RECT GetBoardEdgesBoundingBox() const
Returns the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:812
void SetIsPlaced(bool isPlaced)
Definition: footprint.h:301
int m_GridRouting
Definition: ar_matrix.h:59
int GetLeft() const
Definition: eda_rect.h:117
Class that computes missing connections on a PCB.
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:615
EDA_RECT m_BrdBox
Definition: ar_matrix.h:60
int GetWidth() const
Definition: eda_rect.h:114
double GetOrientation() const
Definition: footprint.h:186
virtual void Report(const wxString &aMessage)
Display aMessage in the progress bar dialog.
bool IsOnLayer(PCB_LAYER_ID aLayer) const override
Test to see if this object is on the given layer.
Definition: pad.h:567
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:126
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:808
coord_type GetBottom() const
Definition: box2.h:200
FOOTPRINT * pickFootprint()
Find the "best" footprint place.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
#define AR_GAIN
void placeFootprint(FOOTPRINT *aFootprint, bool aDoNotRecreateRatsnest, const wxPoint &aPos)
int PointCount() const
Function PointCount()
#define AR_KEEPOUT_MARGIN
bool Contains(const wxPoint &aPoint) const
Definition: eda_rect.cpp:57
PADS & Pads()
Definition: footprint.h:164
int GetBottom() const
Definition: eda_rect.h:119
void PlacePad(PAD *aPad, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:913
AR_MATRIX m_matrix
const VECTOR2I & CPoint(int aIndex) const
Function Point()
const wxPoint GetEnd() const
Definition: eda_rect.h:108
SHAPE_POLY_SET m_fpAreaBottom
void drawPlacementRoutingMatrix()
PCB_LAYER_ID m_routeLayerTop
Definition: ar_matrix.h:65
#define CELL_IS_EDGE
int GetFlag() const
Definition: footprint.h:236
LSET is a set of PCB_LAYER_IDs.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
#define NULL
SHAPE_POLY_SET m_boardShape
int genPlacementRoutingMatrix()
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
const wxPoint GetOrigin() const
Definition: eda_rect.h:106
void SetOrientation(double aNewAngle)
Definition: footprint.cpp:1557
FOOTPRINTS & Footprints()
Definition: board.h:305
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:169
int GetRight() const
Definition: eda_rect.h:116
#define STEP_AR_MM
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:416
#define AR_ABORT_PLACEMENT
int m_Nrows
Definition: ar_matrix.h:61
const EDA_RECT GetBoundingBox() const override
The bounding box is cached, so this will be efficient most of the time.
Definition: pad.cpp:517
const SHAPE_POLY_SET & GetPolyCourtyardBack() const
Definition: footprint.h:652
const wxString & GetReference() const
Definition: footprint.h:426
MATRIX_CELL * m_BoardSide[AR_MAX_ROUTING_LAYERS_COUNT]
Definition: ar_matrix.h:55
void SetCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: ar_matrix.cpp:180
const PAD * nearestPad(FOOTPRINT *aRefFP, PAD *aRefPad, const wxPoint &aOffset)
SHAPE_POLY_SET m_bottomFreeArea
AR_RESULT
Definition: ar_autoplacer.h:48
SHAPE_POLY_SET m_fpAreaTop
unsigned int calculateKeepOutArea(const EDA_RECT &aRect, int side)
void genModuleOnRoutingMatrix(FOOTPRINT *aFootprint)
void SetFlag(int aFlag)
Definition: footprint.h:234
static bool sortFootprintsByRatsnestSize(FOOTPRINT *ref, FOOTPRINT *compare)
int NewOutline()
Creates a new hole in a given outline.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int GetHeight() const
Definition: eda_rect.h:115
bool fillMatrix()
fills m_matrix cells from m_boardShape.
#define CELL_IS_ZONE
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
int testFootprintOnBoard(FOOTPRINT *aFootprint, bool TstOtherSide, const wxPoint &aOffset)
void rotateFootprint(FOOTPRINT *aFootprint, double angle, bool incremental)
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:128
coord_type GetY() const
Definition: box2.h:191
#define CELL_IS_MODULE
int testRectangle(const EDA_RECT &aRect, int side)
void addFpBody(wxPoint aStart, wxPoint aEnd, LSET aLayerMask)
AR_AUTOPLACER(BOARD *aBoard)
wxPoint GetPosition() const override
Definition: pad.h:177
int m_RoutingLayersCount
Definition: ar_matrix.h:58
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:190
#define _(s)
Definition: 3d_actions.cpp:33
SHAPE_LINE_CHAIN.
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:631
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: ar_matrix.h:95
bool KeepRefreshing(bool aWait=false)
Update the UI dialog.
void buildFpAreas(FOOTPRINT *aFootprint, int aFpClearance)
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:104
static const double OrientationPenalty[11]
wxPoint GetPosition() const override
Definition: footprint.h:182
static bool sortFootprintsByComplexity(FOOTPRINT *ref, FOOTPRINT *compare)
unsigned char MATRIX_CELL
Definition: ar_matrix.h:52
int GetPlacementCost90() const
Definition: footprint.h:537
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
wxPoint m_curPosition
bool ComputeMatrixSize(const EDA_RECT &aBoundingBox)
Function ComputeMatrixSize calculates the number of rows and columns of dimensions of aPcb for routin...
Definition: ar_matrix.cpp:61
Definition: pad.h:60
void SetPosition(const wxPoint &aPos) override
Definition: footprint.cpp:1438
void SetMaxProgress(int aMaxProgress)
Fix the value thar gives the 100 precent progress bar length (inside the current virtual zone)
Message panel definition file.
virtual void SetTitle(const wxString &aTitle)
change the title displayed on the window caption MUST only be called from the main thread.
DIST_CELL GetDist(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:234
void AdvanceProgress()
Increment the progress bar length (inside the current virtual zone)
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:90
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay
static constexpr int Millimeter2iu(double mm)
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:173
void addPad(PAD *aPad, int aClearance)
DRAWINGS & Drawings()
Definition: board.h:308
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:363
AR_RESULT AutoplaceFootprints(std::vector< FOOTPRINT * > &aFootprints, BOARD_COMMIT *aCommit, bool aPlaceOffboardModules=false)
PCB_LAYER_ID m_routeLayerBottom
Definition: ar_matrix.h:66
double computePlacementRatsnestCost(FOOTPRINT *aFootprint, const wxPoint &aOffset)
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...
A color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:98
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity