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 <class_drawpanel.h>
30 #include <confirm.h>
31 #include <pcbnew.h>
32 #include <pcb_edit_frame.h>
33 #include <gr_basic.h>
34 #include <macros.h>
35 #include <msgpanel.h>
36 
37 #include <class_board.h>
38 #include <class_module.h>
39 #include <class_track.h>
40 #include <class_drawsegment.h>
41 #include <class_pad.h>
42 
43 #include <board_commit.h>
44 
46 #include <ratsnest_data.h>
47 
49 
50 #include "ar_matrix.h"
51 #include "ar_cell.h"
52 #include "ar_autoplacer.h"
53 
54 #define AR_GAIN 16
55 #define AR_KEEPOUT_MARGIN 500
56 #define AR_ABORT_PLACEMENT -1
57 
58 /* Penalty (cost) for CntRot90 and CntRot180:
59  * CntRot90 and CntRot180 are from 0 (rotation allowed) to 10 (rotation not allowed)
60  */
61 static const double OrientationPenalty[11] =
62 {
63  2.0, // CntRot = 0 rotation prohibited
64  1.9, // CntRot = 1
65  1.8, // CntRot = 2
66  1.7, // CntRot = 3
67  1.6, // CntRot = 4
68  1.5, // CntRot = 5
69  1.4, // CntRot = 5
70  1.3, // CntRot = 7
71  1.2, // CntRot = 8
72  1.1, // CntRot = 9
73  1.0 // CntRot = 10 rotation authorized, no penalty
74 };
75 
76 
78 {
79  m_board = aBoard;
80  m_connectivity.reset( new CONNECTIVITY_DATA );
81 
82  for( auto mod : m_board->Modules() )
83  m_connectivity->Add( mod );
84 
85  m_gridSize = Millimeter2iu( 0.5 );
86  m_progressReporter = nullptr;
87  m_refreshCallback = nullptr;
88 }
89 
90 
91 void AR_AUTOPLACER::placeModule( MODULE* aModule, bool aDoNotRecreateRatsnest, const wxPoint& aPos )
92 {
93  if( !aModule )
94  return;
95 
96  aModule->SetPosition( aPos );
97  m_connectivity->Update( aModule );
98 }
99 
100 
102 {
104 
106 
107  if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
108  {
109  //DisplayError( NULL, _( "No PCB edge found, unknown board size!" ) );
110  // fixme: no wx here
111  return 0;
112  }
113 
114  m_matrix.ComputeMatrixSize( bbox );
115  int nbCells = m_matrix.m_Ncols * m_matrix.m_Nrows;
116 
117  // Choose the number of board sides.
120 
122 
125 
127 
128  // Place the edge layer segments
129  TRACK tmp( NULL );
130 
131  tmp.SetLayer( UNDEFINED_LAYER );
132  tmp.SetNetCode( -1 );
133  tmp.SetWidth( m_matrix.m_GridRouting / 2 );
134 
135  for( auto drawing : m_board->Drawings() )
136  {
137  DRAWSEGMENT* DrawSegm;
138 
139  switch( drawing->Type() )
140  {
141  case PCB_LINE_T:
142  DrawSegm = (DRAWSEGMENT*) drawing;
143 
144  if( DrawSegm->GetLayer() != Edge_Cuts )
145  break;
146 
147 
148  //printf("addSeg %p grid %d\n", DrawSegm, m_matrix.m_GridRouting );
151  break;
152 
153  case PCB_TEXT_T:
154  default:
155  break;
156  }
157  }
158 
159  // Mark cells of the routing matrix to CELL_IS_ZONE
160  // (i.e. availlable cell to place a module )
161  // Init a starting point of attachment to the area.
164 
165  // find and mark all other availlable cells:
166  for( int ii = 1; ii != 0; )
167  ii = propagate();
168 
169  // Initialize top layer. to the same value as the bottom layer
172  nbCells * sizeof(AR_MATRIX::MATRIX_CELL) );
173 
174  return 1;
175 }
176 
177 
178 void AR_AUTOPLACER::rotateModule( MODULE* module, double angle, bool incremental )
179 {
180  if( module == NULL )
181  return;
182 
183  if( incremental )
184  module->SetOrientation( module->GetOrientation() + angle );
185  else
186  module->SetOrientation( angle );
187 
188 
189  m_board->GetConnectivity()->Update( module );
190 }
191 
192 
219 {
220  int row, col;
221  long current_cell, old_cell_H;
222  std::vector<int> pt_cell_V;
223  int nbpoints = 0;
224 
225  const uint32_t NO_CELL_ZONE = CELL_IS_HOLE | CELL_IS_EDGE | CELL_IS_ZONE;
226 
227  pt_cell_V.resize( std::max( m_matrix.m_Nrows, m_matrix.m_Ncols ), CELL_IS_EMPTY );
228 
229  // Search from left to right and top to bottom.
230  for( row = 0; row < m_matrix.m_Nrows; row++ )
231  {
232  old_cell_H = 0;
233 
234  for( col = 0; col < m_matrix.m_Ncols; col++ )
235  {
236  current_cell = m_matrix.GetCell( row, col, AR_SIDE_BOTTOM ) & NO_CELL_ZONE;
237 
238  if( current_cell == 0 ) // a free cell is found
239  {
240  if( (old_cell_H & CELL_IS_ZONE) || (pt_cell_V[col] & CELL_IS_ZONE) )
241  {
242  m_matrix.OrCell( row, col, AR_SIDE_BOTTOM, CELL_IS_ZONE );
243  current_cell = CELL_IS_ZONE;
244  nbpoints++;
245  }
246  }
247 
248  pt_cell_V[col] = old_cell_H = current_cell;
249  }
250  }
251 
252  // Search from right to left and top to bottom/
253  fill( pt_cell_V.begin(), pt_cell_V.end(), CELL_IS_EMPTY );
254 
255  for( row = 0; row < m_matrix.m_Nrows; row++ )
256  {
257  old_cell_H = 0;
258 
259  for( col = m_matrix.m_Ncols - 1; col >= 0; col-- )
260  {
261  current_cell = m_matrix.GetCell( row, col, AR_SIDE_BOTTOM ) & NO_CELL_ZONE;
262 
263  if( current_cell == 0 ) // a free cell is found
264  {
265  if( (old_cell_H & CELL_IS_ZONE) || (pt_cell_V[col] & CELL_IS_ZONE) )
266  {
267  m_matrix.OrCell( row, col, AR_SIDE_BOTTOM, CELL_IS_ZONE );
268  current_cell = CELL_IS_ZONE;
269  nbpoints++;
270  }
271  }
272 
273  pt_cell_V[col] = old_cell_H = current_cell;
274  }
275  }
276 
277  // Search from bottom to top and right to left.
278  fill( pt_cell_V.begin(), pt_cell_V.end(), CELL_IS_EMPTY );
279 
280  for( col = m_matrix.m_Ncols - 1; col >= 0; col-- )
281  {
282  old_cell_H = 0;
283 
284  for( row = m_matrix.m_Nrows - 1; row >= 0; row-- )
285  {
286  current_cell = m_matrix.GetCell( row, col, AR_SIDE_BOTTOM ) & NO_CELL_ZONE;
287 
288  if( current_cell == 0 ) // a free cell is found
289  {
290  if( (old_cell_H & CELL_IS_ZONE) || (pt_cell_V[row] & CELL_IS_ZONE) )
291  {
292  m_matrix.OrCell( row, col, AR_SIDE_BOTTOM, CELL_IS_ZONE );
293  current_cell = CELL_IS_ZONE;
294  nbpoints++;
295  }
296  }
297 
298  pt_cell_V[row] = old_cell_H = current_cell;
299  }
300  }
301 
302  // Search from bottom to top and left to right.
303  fill( pt_cell_V.begin(), pt_cell_V.end(), CELL_IS_EMPTY );
304 
305  for( col = 0; col < m_matrix.m_Ncols; col++ )
306  {
307  old_cell_H = 0;
308 
309  for( row = m_matrix.m_Nrows - 1; row >= 0; row-- )
310  {
311  current_cell = m_matrix.GetCell( row, col, AR_SIDE_BOTTOM ) & NO_CELL_ZONE;
312 
313  if( current_cell == 0 ) // a free cell is found
314  {
315  if( (old_cell_H & CELL_IS_ZONE) || (pt_cell_V[row] & CELL_IS_ZONE) )
316  {
317  m_matrix.OrCell( row, col, AR_SIDE_BOTTOM, CELL_IS_ZONE );
318  current_cell = CELL_IS_ZONE;
319  nbpoints++;
320  }
321  }
322 
323  pt_cell_V[row] = old_cell_H = current_cell;
324  }
325  }
326 
327  return nbpoints;
328 }
329 
330 
332 {
333  int ox, oy, fx, fy;
334  LSET layerMask;
335  EDA_RECT fpBBox = Module->GetBoundingBox();
336 
337  fpBBox.Inflate( m_matrix.m_GridRouting / 2 );
338  ox = fpBBox.GetX();
339  fx = fpBBox.GetRight();
340  oy = fpBBox.GetY();
341  fy = fpBBox.GetBottom();
342 
343  if( ox < m_matrix.m_BrdBox.GetX() )
344  ox = m_matrix.m_BrdBox.GetX();
345 
346  if( ox > m_matrix.m_BrdBox.GetRight() )
347  ox = m_matrix.m_BrdBox.GetRight();
348 
349  if( fx < m_matrix.m_BrdBox.GetX() )
350  fx = m_matrix.m_BrdBox.GetX();
351 
352  if( fx > m_matrix.m_BrdBox.GetRight() )
353  fx = m_matrix.m_BrdBox.GetRight();
354 
355  if( oy < m_matrix.m_BrdBox.GetY() )
356  oy = m_matrix.m_BrdBox.GetY();
357 
358  if( oy > m_matrix.m_BrdBox.GetBottom() )
359  oy = m_matrix.m_BrdBox.GetBottom();
360 
361  if( fy < m_matrix.m_BrdBox.GetY() )
362  fy = m_matrix.m_BrdBox.GetY();
363 
364  if( fy > m_matrix.m_BrdBox.GetBottom() )
365  fy = m_matrix.m_BrdBox.GetBottom();
366 
367  if( Module->GetLayer() == F_Cu )
368  layerMask.set( F_Cu );
369 
370  if( Module->GetLayer() == B_Cu )
371  layerMask.set( B_Cu );
372 
373  m_matrix.TraceFilledRectangle( ox, oy, fx, fy, layerMask,
375 
376  // Trace pads + clearance areas.
377  for( auto pad : Module->Pads() )
378  {
379  int margin = (m_matrix.m_GridRouting / 2) + pad->GetClearance();
381  }
382 
383  // Trace clearance.
384  int margin = ( m_matrix.m_GridRouting * Module->GetPadCount() ) / AR_GAIN;
385  m_matrix.CreateKeepOutRectangle( ox, oy, fx, fy, margin, AR_KEEPOUT_MARGIN , layerMask );
386 }
387 
388 
389 /* Test if the rectangular area (ux, ux .. y0, y1):
390  * - is a free zone (except OCCUPED_By_MODULE returns)
391  * - is on the working surface of the board (otherwise returns OUT_OF_BOARD)
392  *
393  * Returns OUT_OF_BOARD, or OCCUPED_By_MODULE or FREE_CELL if OK
394  */
395 int AR_AUTOPLACER::testRectangle( const EDA_RECT& aRect, int side )
396 {
397  EDA_RECT rect = aRect;
398 
399  rect.Inflate( m_matrix.m_GridRouting / 2 );
400 
401  wxPoint start = rect.GetOrigin();
402  wxPoint end = rect.GetEnd();
403 
404  start -= m_matrix.m_BrdBox.GetOrigin();
405  end -= m_matrix.m_BrdBox.GetOrigin();
406 
407  int row_min = start.y / m_matrix.m_GridRouting;
408  int row_max = end.y / m_matrix.m_GridRouting;
409  int col_min = start.x / m_matrix.m_GridRouting;
410  int col_max = end.x / m_matrix.m_GridRouting;
411 
412  if( start.y > row_min * m_matrix.m_GridRouting )
413  row_min++;
414 
415  if( start.x > col_min * m_matrix.m_GridRouting )
416  col_min++;
417 
418  if( row_min < 0 )
419  row_min = 0;
420 
421  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
422  row_max = m_matrix.m_Nrows - 1;
423 
424  if( col_min < 0 )
425  col_min = 0;
426 
427  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
428  col_max = m_matrix.m_Ncols - 1;
429 
430  for( int row = row_min; row <= row_max; row++ )
431  {
432  for( int col = col_min; col <= col_max; col++ )
433  {
434  unsigned int data = m_matrix.GetCell( row, col, side );
435 
436  if( ( data & CELL_IS_ZONE ) == 0 )
437  return AR_OUT_OF_BOARD;
438 
439  if( (data & CELL_IS_MODULE) )
440  return AR_OCCUIPED_BY_MODULE;
441  }
442  }
443 
444  return AR_FREE_CELL;
445 }
446 
447 
448 /* Calculates and returns the clearance area of the rectangular surface
449  * aRect):
450  * (Sum of cells in terms of distance)
451  */
452 unsigned int AR_AUTOPLACER::calculateKeepOutArea( const EDA_RECT& aRect, int side )
453 {
454  wxPoint start = aRect.GetOrigin();
455  wxPoint end = aRect.GetEnd();
456 
457  start -= m_matrix.m_BrdBox.GetOrigin();
458  end -= m_matrix.m_BrdBox.GetOrigin();
459 
460  int row_min = start.y / m_matrix.m_GridRouting;
461  int row_max = end.y / m_matrix.m_GridRouting;
462  int col_min = start.x / m_matrix.m_GridRouting;
463  int col_max = end.x / m_matrix.m_GridRouting;
464 
465  if( start.y > row_min * m_matrix.m_GridRouting )
466  row_min++;
467 
468  if( start.x > col_min * m_matrix.m_GridRouting )
469  col_min++;
470 
471  if( row_min < 0 )
472  row_min = 0;
473 
474  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
475  row_max = m_matrix.m_Nrows - 1;
476 
477  if( col_min < 0 )
478  col_min = 0;
479 
480  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
481  col_max = m_matrix.m_Ncols - 1;
482 
483  unsigned int keepOutCost = 0;
484 
485  for( int row = row_min; row <= row_max; row++ )
486  {
487  for( int col = col_min; col <= col_max; col++ )
488  {
489  // m_matrix.GetDist returns the "cost" of the cell
490  // at position (row, col)
491  // in autoplace this is the cost of the cell, if it is
492  // inside aRect
493  keepOutCost += m_matrix.GetDist( row, col, side );
494  }
495  }
496 
497  return keepOutCost;
498 }
499 
500 
501 /* Test if the module can be placed on the board.
502  * Returns the value TstRectangle().
503  * Module is known by its bounding box
504  */
505 int AR_AUTOPLACER::testModuleOnBoard( MODULE* aModule, bool TstOtherSide, const wxPoint& aOffset )
506 {
507  int side = AR_SIDE_TOP;
508  int otherside = AR_SIDE_BOTTOM;
509 
510  if( aModule->GetLayer() == B_Cu )
511  {
512  side = AR_SIDE_BOTTOM; otherside = AR_SIDE_TOP;
513  }
514 
515  EDA_RECT fpBBox = aModule->GetFootprintRect();
516  fpBBox.Move( -aOffset );
517 
518  int diag = testRectangle( fpBBox, side );
519 
520  if( diag != AR_FREE_CELL )
521  return diag;
522 
523  if( TstOtherSide )
524  {
525  diag = testRectangle( fpBBox, otherside );
526 
527  if( diag != AR_FREE_CELL )
528  return diag;
529  }
530 
531  int marge = ( m_matrix.m_GridRouting * aModule->GetPadCount() ) / AR_GAIN;
532 
533  fpBBox.Inflate( marge );
534  return calculateKeepOutArea( fpBBox, side );
535 }
536 
537 
539 {
540  int error = 1;
541  wxPoint LastPosOK;
542  double min_cost, curr_cost, Score;
543  bool TstOtherSide;
544 
545  aModule->CalculateBoundingBox();
546 
547  LastPosOK = m_matrix.m_BrdBox.GetOrigin();
548 
549  wxPoint mod_pos = aModule->GetPosition();
550  EDA_RECT fpBBox = aModule->GetFootprintRect();
551 
552  // Move fpBBox to have the footprint position at (0,0)
553  fpBBox.Move( -mod_pos );
554  wxPoint fpBBoxOrg = fpBBox.GetOrigin();
555 
556  // Calculate the limit of the footprint position, relative
557  // to the routing matrix area
558  wxPoint xylimit = m_matrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
559 
560  wxPoint initialPos = m_matrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
561 
562  // Stay on grid.
563  initialPos.x -= initialPos.x % m_matrix.m_GridRouting;
564  initialPos.y -= initialPos.y % m_matrix.m_GridRouting;
565 
566  m_curPosition = initialPos;
567  auto moduleOffset = mod_pos - m_curPosition;
568 
569  /* Examine pads, and set TstOtherSide to true if a footprint
570  * has at least 1 pad through.
571  */
572  TstOtherSide = false;
573 
575  {
576  LSET other( aModule->GetLayer() == B_Cu ? F_Cu : B_Cu );
577 
578  for( auto pad : aModule->Pads() )
579  {
580  if( !( pad->GetLayerSet() & other ).any() )
581  continue;
582 
583  TstOtherSide = true;
584  break;
585  }
586  }
587 
588  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
589 
590  min_cost = -1.0;
591 // m_frame->SetStatusText( wxT( "Score ??, pos ??" ) );
592 
593 
594  for( ; m_curPosition.x < xylimit.x; m_curPosition.x += m_matrix.m_GridRouting )
595  {
596  if ( m_refreshCallback )
597  {
599  return AR_ABORT_PLACEMENT;
600  }
601 
602  m_curPosition.y = initialPos.y;
603 
604  for( ; m_curPosition.y < xylimit.y; m_curPosition.y += m_matrix.m_GridRouting )
605  {
606 
607  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
608  moduleOffset = mod_pos - m_curPosition;
609  int keepOutCost = testModuleOnBoard( aModule, TstOtherSide, moduleOffset );
610 
611  if( keepOutCost >= 0 ) // i.e. if the module can be put here
612  {
613  error = 0;
614  // m_frame->build_ratsnest_module( aModule ); // fixme
615  curr_cost = computePlacementRatsnestCost( aModule, moduleOffset );
616  Score = curr_cost + keepOutCost;
617 
618  if( (min_cost >= Score ) || (min_cost < 0 ) )
619  {
620  LastPosOK = m_curPosition;
621  min_cost = Score;
622  wxString msg;
623 /* msg.Printf( wxT( "Score %g, pos %s, %s" ),
624  min_cost,
625  GetChars( ::CoordinateToString( LastPosOK.x ) ),
626  GetChars( ::CoordinateToString( LastPosOK.y ) ) );
627  m_frame->SetStatusText( msg );*/
628  }
629  }
630  }
631  }
632 
633  // Regeneration of the modified variable.
634  m_curPosition = LastPosOK;
635 
636  m_minCost = min_cost;
637  return error;
638 }
639 
640 
641 const D_PAD* AR_AUTOPLACER::nearestPad( MODULE *aRefModule, D_PAD* aRefPad, const wxPoint& aOffset)
642 {
643  const D_PAD* nearest = nullptr;
644  int64_t nearestDist = INT64_MAX;
645 
646  for ( auto mod : m_board->Modules() )
647  {
648  if ( mod == aRefModule )
649  continue;
650 
651  if( !m_matrix.m_BrdBox.Contains( mod->GetPosition() ) )
652  continue;
653 
654  for ( auto pad: mod->Pads() )
655  {
656  if ( pad->GetNetCode() != aRefPad->GetNetCode() || pad->GetNetCode() <= 0 )
657  continue;
658 
659  auto dist = (VECTOR2I( aRefPad->GetPosition() - aOffset ) - VECTOR2I( pad->GetPosition() ) ).EuclideanNorm();
660 
661  //printf("Dist %lld pad %p\n", dist, pad );
662 
663  if ( dist < nearestDist )
664  {
665  nearestDist = dist;
666  nearest = pad;
667  }
668  }
669  }
670 
671  return nearest;
672 }
673 
674 
676 {
677  double curr_cost;
678  VECTOR2I start; // start point of a ratsnest
679  VECTOR2I end; // end point of a ratsnest
680  int dx, dy;
681 
682  curr_cost = 0;
683 
684  for ( auto pad : aModule->Pads() )
685  {
686  auto nearest = nearestPad( aModule, pad, aOffset );
687 
688  if( !nearest )
689  continue;
690 
691  //printf("pad %s nearest %s\n", (const char *)aModule->GetReference().c_str(), (const char *)nearest->GetParent()->GetReference().c_str());
692 
693  start = VECTOR2I( pad->GetPosition() ) - VECTOR2I(aOffset);
694  end = VECTOR2I( nearest->GetPosition() );
695 
696  //m_overlay->SetIsStroke( true );
697  //m_overlay->SetStrokeColor( COLOR4D(0.0, 1.0, 0.0, 1.0) );
698  //m_overlay->Line( start, end );
699 
700  // Cost of the ratsnest.
701  dx = end.x - start.x;
702  dy = end.y - start.y;
703 
704  dx = abs( dx );
705  dy = abs( dy );
706 
707  // ttry to have always dx >= dy to calculate the cost of the rastsnet
708  if( dx < dy )
709  std::swap( dx, dy );
710 
711  // Cost of the connection = length + penalty due to the slope
712  // dx is the biggest length relative to the X or Y axis
713  // the penalty is max for 45 degrees ratsnests,
714  // and 0 for horizontal or vertical ratsnests.
715  // For Horizontal and Vertical ratsnests, dy = 0;
716  double conn_cost = hypot( dx, dy * 2.0 );
717  curr_cost += conn_cost; // Total cost = sum of costs of each connection
718  }
719 
720  return curr_cost;
721 }
722 
723 
724 // Sort routines
725 static bool sortFootprintsByComplexity( MODULE* ref, MODULE* compare )
726 {
727  double ff1, ff2;
728 
729  ff1 = ref->GetArea() * ref->GetPadCount();
730  ff2 = compare->GetArea() * compare->GetPadCount();
731 
732  return ff2 < ff1;
733 }
734 
735 
736 static bool sortFootprintsByRatsnestSize( MODULE* ref, MODULE* compare )
737 {
738  double ff1, ff2;
739 
740  ff1 = ref->GetArea() * ref->GetFlag();
741  ff2 = compare->GetArea() * compare->GetFlag();
742  return ff2 < ff1;
743 }
744 
745 
754 {
755  MODULE* module;
756  std::vector <MODULE*> moduleList;
757 
758 
759  for( auto m : m_board->Modules() )
760  {
762  moduleList.push_back( m );
763  }
764 
765  sort( moduleList.begin(), moduleList.end(), sortFootprintsByComplexity );
766 
767  for( unsigned kk = 0; kk < moduleList.size(); kk++ )
768  {
769  module = moduleList[kk];
770  module->SetFlag( 0 );
771 
772  if( !module->NeedsPlaced() )
773  continue;
774 
775  m_connectivity->Update( module );
776  }
777 
778  m_connectivity->RecalculateRatsnest();
779 
780  for( unsigned kk = 0; kk < moduleList.size(); kk++ )
781  {
782  module = moduleList[kk];
783 
784  auto edges = m_connectivity->GetRatsnestForComponent( module, true );
785 
786  module->SetFlag( edges.size() ) ;
787  }
788 
789  sort( moduleList.begin(), moduleList.end(), sortFootprintsByRatsnestSize );
790 
791  // Search for "best" module.
792  MODULE* bestModule = nullptr;
793  MODULE* altModule = nullptr;
794 
795  for( unsigned ii = 0; ii < moduleList.size(); ii++ )
796  {
797  module = moduleList[ii];
798 
799  if( !module->NeedsPlaced() )
800  continue;
801 
802  altModule = module;
803 
804  if( module->GetFlag() == 0 )
805  continue;
806 
807  bestModule = module;
808  break;
809  }
810 
811  if( bestModule )
812  return bestModule;
813  else
814  return altModule;
815 }
816 
817 
819 {
820  int ii, jj;
821  COLOR4D color;
822  int ox, oy;
823  AR_MATRIX::MATRIX_CELL top_state, bottom_state;
824 
825 
826  for( ii = 0; ii < m_matrix.m_Nrows; ii++ )
827  {
828  oy = m_matrix.m_BrdBox.GetY() + ( ii * m_matrix.m_GridRouting );
829 
830  for( jj = 0; jj < m_matrix.m_Ncols; jj++ )
831  {
832  ox = m_matrix.m_BrdBox.GetX() + (jj * m_matrix.m_GridRouting);
833  color = COLOR4D::BLACK;
834 
835  top_state = m_matrix.GetCell( ii, jj, AR_SIDE_TOP );
836  bottom_state = m_matrix.GetCell( ii, jj, AR_SIDE_BOTTOM );
837 
838  if(top_state || bottom_state)
839  {
840  // printf("[%d, %d] [%d, %d] TS %x BS %x\n",ii,jj, ox, oy, top_state, bottom_state );
841  }
842 
843  if( top_state & CELL_IS_ZONE )
844  color = COLOR4D( BLUE );
845 
846  // obstacles
847  if( ( top_state & CELL_IS_EDGE ) || ( bottom_state & CELL_IS_EDGE ) )
848  color = COLOR4D::WHITE;
849  else if( top_state & ( CELL_IS_HOLE | CELL_IS_MODULE ) )
850  color = COLOR4D( LIGHTRED );
851  else if( bottom_state & ( CELL_IS_HOLE | CELL_IS_MODULE) )
852  color = COLOR4D( LIGHTGREEN );
853  else // Display the filling and keep out regions.
854  {
855  if( m_matrix.GetDist( ii, jj, AR_SIDE_TOP )
856  || m_matrix.GetDist( ii, jj, AR_SIDE_BOTTOM ) )
857  color = DARKGRAY;
858  }
859 
860  m_overlay->SetIsFill(true);
861  m_overlay->SetFillColor( color );
862 
863  VECTOR2D p(ox, oy);
864  m_overlay->Circle(p, m_matrix.m_GridRouting/4 );
865  }
866  }
867 }
868 
869 AR_RESULT AR_AUTOPLACER::AutoplaceModules( std::vector<MODULE*> aModules, BOARD_COMMIT* aCommit, bool aPlaceOffboardModules )
870 {
871  wxPoint PosOK;
872  wxPoint memopos;
873  int error;
874  MODULE* module = nullptr;
875  bool cancelled = false;
876 
877  memopos = m_curPosition;
878 
879  //printf("set grid: %d\n", m_gridSize);
880 
881  m_matrix.m_GridRouting = m_gridSize; //(int) m_frame->GetScreen()->GetGridSize().x;
882 
883  // Ensure Board.m_GridRouting has a reasonable value:
884  if( m_matrix.m_GridRouting < Millimeter2iu( 0.25 ) )
885  m_matrix.m_GridRouting = Millimeter2iu( 0.25 );
886 
887  // Compute module parameters used in auto place
888  if( genPlacementRoutingMatrix( ) == 0 )
889  return AR_FAILURE;
890 
891  int moduleCount = 0;
892 
893  for ( auto m : m_board->Modules() )
894  {
895  m->SetNeedsPlaced( false );
896  }
897 
898  std::vector<MODULE *> offboardMods;
899 
900  if( aPlaceOffboardModules )
901  {
902  for ( auto m : m_board->Modules() )
903  {
904  if( !m_matrix.m_BrdBox.Contains( m->GetPosition() ) )
905  {
906  offboardMods.push_back( m );
907  }
908  }
909  }
910 
911  for ( auto m : aModules )
912  {
913  m->SetNeedsPlaced( true );
914  aCommit->Modify(m);
915  }
916 
917  for ( auto m : offboardMods )
918  {
919  m->SetNeedsPlaced( true );
920  aCommit->Modify(m);
921  }
922 
923  for ( auto m : m_board->Modules() )
924  {
925  if( m->NeedsPlaced() ) // Erase from screen
926  {
927  moduleCount++;
928  }
929  else
930  {
932  }
933  }
934 
936 
937  int cnt = 0;
938  wxString msg;
939 
940  if( m_progressReporter )
941  {
942  m_progressReporter->Report( _( "Autoplacing components..." ) );
943  m_progressReporter->SetMaxProgress( moduleCount );
944  }
945 
946  while( ( module = pickModule( ) ) != nullptr )
947  {
948  // Display some info about activity, module placement can take a while:
949  //printf( _( "Place footprint %d of %d [%s]\n" ), cnt, moduleCount, (const char *)module->GetReference().c_str() );
950  //m_frame->SetStatusText( msg );
951 
952  double initialOrient = module->GetOrientation();
953  // Display fill area of interest, barriers, penalties.
954  //drawPlacementRoutingMatrix( );
955 
956  error = getOptimalModulePlacement( module );
957  double bestScore = m_minCost;
958  double bestRotation = 0.0;
959  int rotAllowed;
960  PosOK = m_curPosition;
961 
962  if( error == AR_ABORT_PLACEMENT )
963  goto end_of_tst;
964 
965  // Try orientations 90, 180, 270 degrees from initial orientation
966  rotAllowed = module->GetPlacementCost180();
967 
968  //printf("rotAllowed %d\n", rotAllowed);
969 
970  if( rotAllowed != 0 )
971  {
972  rotateModule( module, 1800.0, true );
973  error = getOptimalModulePlacement( module );
974  m_minCost *= OrientationPenalty[rotAllowed];
975 
976  if( bestScore > m_minCost ) // This orientation is better.
977  {
978  PosOK = m_curPosition;
979  bestScore = m_minCost;
980  bestRotation = 1800.0;
981  }
982  else
983  {
984  rotateModule( module, initialOrient, false );
985  }
986 
987  if( error == AR_ABORT_PLACEMENT )
988  goto end_of_tst;
989  }
990 
991  // Determine if the best orientation of a module is 90.
992  rotAllowed = module->GetPlacementCost90();
993  if( rotAllowed != 0 )
994  {
995  rotateModule( module, 900.0, true );
996  error = getOptimalModulePlacement( module );
997  m_minCost *= OrientationPenalty[rotAllowed];
998 
999  if( bestScore > m_minCost ) // This orientation is better.
1000  {
1001  PosOK = m_curPosition;
1002  bestScore = m_minCost;
1003  bestRotation = 900.0;
1004  }
1005  else
1006  {
1007  rotateModule( module, initialOrient, false );
1008  }
1009 
1010  if( error == AR_ABORT_PLACEMENT )
1011  goto end_of_tst;
1012  }
1013 
1014  // Determine if the best orientation of a module is -90.
1015  if( rotAllowed != 0 )
1016  {
1017  rotateModule( module, 2700.0, true );
1018  error = getOptimalModulePlacement( module );
1019  m_minCost *= OrientationPenalty[rotAllowed];
1020 
1021  if( bestScore > m_minCost ) // This orientation is better.
1022  {
1023  PosOK = m_curPosition;
1024  bestScore = m_minCost;
1025  bestRotation = 2700.0;
1026  }
1027  else
1028  {
1029  rotateModule( module, initialOrient, false );
1030  }
1031 
1032  if( error == AR_ABORT_PLACEMENT )
1033  goto end_of_tst;
1034  }
1035 
1036 end_of_tst:
1037 
1038  if( error == AR_ABORT_PLACEMENT )
1039  break;
1040 
1041 
1042  bestRotation += initialOrient;
1043 
1044  if( bestRotation != module->GetOrientation() )
1045  {
1046  //printf("best rotation %d\n", bestRotation );
1047  rotateModule( module, bestRotation, false );
1048  }
1049 
1050  // Place module.
1051  placeModule( module, true, m_curPosition );
1052 
1053  module->CalculateBoundingBox();
1054  genModuleOnRoutingMatrix( module );
1055  module->SetIsPlaced( true );
1056  module->SetNeedsPlaced( false );
1057 
1058 
1059  if( m_progressReporter )
1060  {
1062  if ( !m_progressReporter->KeepRefreshing( false ) )
1063  {
1064  cancelled = true;
1065  break;
1066  }
1067  }
1068  cnt++;
1069  }
1070 
1071  m_curPosition = memopos;
1072 
1074 
1075  for ( auto m : m_board->Modules() )
1076  {
1077  m->CalculateBoundingBox();
1078  }
1079 
1080  return cancelled ? AR_CANCELLED : AR_COMPLETED;
1081 }
int GetFlag() const
Definition: class_module.h:231
Definition: colors.h:57
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:43
void rotateModule(MODULE *module, double angle, bool incremental)
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
void Move(const wxPoint &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
const wxPoint GetOrigin() const
Definition: eda_rect.h:112
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)
virtual void SetLayer(PCB_LAYER_ID aLayer)
Function SetLayer sets the layer this item is on.
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 propagate()
Function propagate Used only in autoplace calculations Uses the routing matrix to fill the cells with...
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
bool Contains(const wxPoint &aPoint) const
Function Contains.
void CalculateBoundingBox()
Function CalculateBoundingBox calculates the bounding box in board coordinates.
Class BOARD to handle a board.
int m_GridRouting
Definition: ar_matrix.h:63
Class that computes missing connections on a PCB.
int color
Definition: DXF_plotter.cpp:62
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
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:169
void SetNeedsPlaced(bool needsPlaced)
Definition: class_module.h:296
int GetHeight() const
Definition: eda_rect.h:118
void Report(const wxString &aMessage)
Display aMessage in the progress bar dialog.
class TEXTE_PCB, text on a layer
Definition: typeinfo.h:92
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
bool NeedsPlaced() const
Definition: class_module.h:295
void TraceSegmentPcb(DRAWSEGMENT *pt_segm, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:1085
int GetPlacementCost90() const
Definition: class_module.h:583
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
#define AR_GAIN
#define AR_KEEPOUT_MARGIN
#define abs(a)
Definition: auxiliary.h:84
Functions relatives to tracks, vias and segments used to fill zones.
This file contains miscellaneous commonly used macros and functions.
void SetWidth(int aWidth)
Definition: class_track.h:115
const D_PAD * nearestPad(MODULE *aRefModule, D_PAD *aRefPad, const wxPoint &aOffset)
void genModuleOnRoutingMatrix(MODULE *Module)
const EDA_RECT GetBoardEdgesBoundingBox() const
Function GetBoardEdgesBoundingBox Returns the board bounding box calculated using exclusively the boa...
Definition: class_board.h:804
AR_MATRIX m_matrix
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...
#define CELL_IS_EMPTY
Definition: ar_cell.h:35
Class LSET is a set of PCB_LAYER_IDs.
DLIST_ITERATOR_WRAPPER< MODULE > Modules()
Definition: class_board.h:254
int getOptimalModulePlacement(MODULE *aModule)
static bool sortFootprintsByComplexity(MODULE *ref, MODULE *compare)
double computePlacementRatsnestCost(MODULE *aModule, const wxPoint &aOffset)
double GetOrientation() const
Definition: class_module.h:189
int genPlacementRoutingMatrix()
static bool sortFootprintsByRatsnestSize(MODULE *ref, MODULE *compare)
EDA_RECT GetFootprintRect() const
Function GetFootprintRect() Returns the area of the module footprint excluding any text...
void OrCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: ar_matrix.cpp:216
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:194
#define CELL_IS_HOLE
Definition: ar_cell.h:36
#define AR_ABORT_PLACEMENT
int m_Nrows
Definition: ar_matrix.h:65
MODULE * pickModule()
Function Module find the "best" module place The criteria are:
bool SetNetCode(int aNetCode, bool aNoAssert=false)
Function SetNetCode sets net using a net code.
MATRIX_CELL * m_BoardSide[AR_MAX_ROUTING_LAYERS_COUNT]
Definition: ar_matrix.h:56
void SetIsPlaced(bool isPlaced)
Definition: class_module.h:287
AR_RESULT
Definition: ar_autoplacer.h:49
int GetBottom() const
Definition: eda_rect.h:122
void SetPosition(const wxPoint &aPos) override
unsigned int calculateKeepOutArea(const EDA_RECT &aRect, int side)
int testModuleOnBoard(MODULE *aModule, bool TstOtherSide, const wxPoint &aOffset)
int GetRight() const
Definition: eda_rect.h:119
Pad object description.
const wxPoint GetEnd() const
Definition: eda_rect.h:114
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
GetPadCount returns the number of pads.
int GetNetCode() const
Function GetNetCode.
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:140
int testRectangle(const EDA_RECT &aRect, int side)
AR_AUTOPLACER(BOARD *aBoard)
std::function< int()> m_refreshCallback
Class to handle a graphic segment.
#define max(a, b)
Definition: auxiliary.h:86
int m_RoutingLayersCount
Definition: ar_matrix.h:62
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:170
void SetOrientation(double newangle)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#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
int GetX() const
Definition: eda_rect.h:109
int GetWidth() const
Definition: eda_rect.h:117
static const double OrientationPenalty[11]
Definition: colors.h:49
int GetY() const
Definition: eda_rect.h:110
unsigned char MATRIX_CELL
Definition: ar_matrix.h:52
Module description (excepted pads)
Definition: colors.h:45
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
const wxPoint GetPosition() const override
Definition: class_pad.h:220
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.
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
int GetPlacementCost180() const
Definition: class_module.h:580
const wxPoint GetPosition() const override
Definition: class_module.h:184
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Function GetConnectivity() returns list of missing connections between components/tracks.
Definition: class_board.h:296
#define mod(a, n)
Definition: greymap.cpp:24
void SetFlag(int aFlag)
Definition: class_module.h:229
DLIST_ITERATOR_WRAPPER< BOARD_ITEM > Drawings()
Definition: class_board.h:255
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
Class COLOR4D is the color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:39
double GetArea(int aPadding=0) const
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity