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