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