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