KiCad PCB EDA Suite
AR_AUTOPLACER Class Reference

#include <ar_autoplacer.h>

Public Member Functions

 AR_AUTOPLACER (BOARD *aBoard)
 
AR_RESULT AutoplaceModules (std::vector< MODULE * > aModules, BOARD_COMMIT *aCommit, bool aPlaceOffboardModules=false)
 
const std::vector< MODULE * > QueryOffboardModules ()
 
void SetPlacementGrid (int aGrid)
 
void SetOverlay (std::shared_ptr< KIGFX::VIEW_OVERLAY > aOverlay)
 Set a VIEW overlay to draw items during a autoplace session. More...
 
void SetRefreshCallback (std::function< int(MODULE *aModule)> aCallback)
 a callback function to redraw on screen the view after changes, for instance after moving a footprint More...
 
void SetProgressReporter (PROGRESS_REPORTER *aReporter)
 

Private Member Functions

void drawPlacementRoutingMatrix ()
 
void rotateModule (MODULE *module, double angle, bool incremental)
 
int genPlacementRoutingMatrix ()
 
bool fillMatrix ()
 fills m_matrix cells from m_boardShape. More...
 
void genModuleOnRoutingMatrix (MODULE *Module)
 
int testRectangle (const EDA_RECT &aRect, int side)
 
int testModuleByPolygon (MODULE *aModule, int aSide, const wxPoint &aOffset)
 
unsigned int calculateKeepOutArea (const EDA_RECT &aRect, int side)
 
int testModuleOnBoard (MODULE *aModule, bool TstOtherSide, const wxPoint &aOffset)
 
int getOptimalModulePlacement (MODULE *aModule)
 
double computePlacementRatsnestCost (MODULE *aModule, const wxPoint &aOffset)
 
MODULEpickModule ()
 Find the "best" module place. More...
 
void placeModule (MODULE *aModule, bool aDoNotRecreateRatsnest, const wxPoint &aPos)
 
const D_PADnearestPad (MODULE *aRefModule, D_PAD *aRefPad, const wxPoint &aOffset)
 
void addFpBody (wxPoint aStart, wxPoint aEnd, LSET aLayerMask)
 
void addPad (D_PAD *aPad, int aClearance)
 
void buildFpAreas (MODULE *aFootprint, int aFpClearance)
 

Private Attributes

AR_MATRIX m_matrix
 
SHAPE_POLY_SET m_topFreeArea
 
SHAPE_POLY_SET m_bottomFreeArea
 
SHAPE_POLY_SET m_boardShape
 
SHAPE_POLY_SET m_fpAreaTop
 
SHAPE_POLY_SET m_fpAreaBottom
 
BOARDm_board
 
wxPoint m_curPosition
 
wxPoint m_moduleOffset
 
double m_minCost
 
int m_gridSize
 
std::shared_ptr< KIGFX::VIEW_OVERLAYm_overlay
 
std::unique_ptr< CONNECTIVITY_DATAm_connectivity
 
std::function< int(MODULE *aModule)> m_refreshCallback
 
PROGRESS_REPORTERm_progressReporter
 

Detailed Description

Definition at line 58 of file ar_autoplacer.h.

Constructor & Destructor Documentation

◆ AR_AUTOPLACER()

AR_AUTOPLACER::AR_AUTOPLACER ( BOARD aBoard)

Definition at line 79 of file ar_autoplacer.cpp.

80 {
81  m_board = aBoard;
82  m_connectivity.reset( new CONNECTIVITY_DATA );
83 
84  for( auto mod : m_board->Modules() )
85  m_connectivity->Add( mod );
86 
87  m_gridSize = Millimeter2iu( STEP_AR_MM );
88  m_progressReporter = nullptr;
89  m_refreshCallback = nullptr;
90  m_minCost = 0.0;
91 }
PROGRESS_REPORTER * m_progressReporter
DLIST_ITERATOR_WRAPPER< MODULE > Modules()
Definition: class_board.h:252
#define STEP_AR_MM
std::function< int(MODULE *aModule)> m_refreshCallback
#define mod(a, n)
Definition: greymap.cpp:24
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References m_board, m_connectivity, m_gridSize, m_minCost, m_progressReporter, m_refreshCallback, mod, BOARD::Modules(), and STEP_AR_MM.

Member Function Documentation

◆ addFpBody()

void AR_AUTOPLACER::addFpBody ( wxPoint  aStart,
wxPoint  aEnd,
LSET  aLayerMask 
)
private

Definition at line 288 of file ar_autoplacer.cpp.

289 {
290  // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
291  if( aLayerMask[ F_Cu ] )
292  {
294  m_fpAreaTop.Append( aStart.x, aStart.y );
295  m_fpAreaTop.Append( aEnd.x, aStart.y );
296  m_fpAreaTop.Append( aEnd.x, aEnd.y );
297  m_fpAreaTop.Append( aStart.x, aEnd.y );
298  }
299  if( aLayerMask[ B_Cu ] )
300  {
302  m_fpAreaBottom.Append( aStart.x, aStart.y );
303  m_fpAreaBottom.Append( aEnd.x, aStart.y );
304  m_fpAreaBottom.Append( aEnd.x, aEnd.y );
305  m_fpAreaBottom.Append( aStart.x, aEnd.y );
306  }
307 }
SHAPE_POLY_SET m_fpAreaBottom
SHAPE_POLY_SET m_fpAreaTop
int NewOutline()
Creates a new empty polygon in the set and returns its index
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)

References SHAPE_POLY_SET::Append(), B_Cu, F_Cu, m_fpAreaBottom, m_fpAreaTop, and SHAPE_POLY_SET::NewOutline().

Referenced by buildFpAreas().

◆ addPad()

void AR_AUTOPLACER::addPad ( D_PAD aPad,
int  aClearance 
)
private

Definition at line 309 of file ar_autoplacer.cpp.

310 {
311  // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
312  EDA_RECT bbox = aPad->GetBoundingBox();
313  bbox.Inflate( aClearance );
314 
315  if( aPad->IsOnLayer( F_Cu ) )
316  {
318  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetTop() );
319  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetTop() );
320  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetBottom() );
321  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetBottom() );
322  }
323  if( aPad->IsOnLayer( B_Cu ) )
324  {
326  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetTop() );
327  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetTop() );
328  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetBottom() );
329  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetBottom() );
330  }
331 }
int GetTop() const
Definition: eda_rect.h:121
int GetLeft() const
Definition: eda_rect.h:120
int GetBottom() const
Definition: eda_rect.h:122
SHAPE_POLY_SET m_fpAreaBottom
int GetRight() const
Definition: eda_rect.h:119
SHAPE_POLY_SET m_fpAreaTop
int NewOutline()
Creates a new empty polygon in the set and returns its index
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
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:717
const EDA_RECT GetBoundingBox() const override
Function GetBoundingBox returns the orthogonal, bounding box of this object for display purposes.
Definition: class_pad.cpp:226
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
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)

References SHAPE_POLY_SET::Append(), B_Cu, F_Cu, EDA_RECT::GetBottom(), D_PAD::GetBoundingBox(), EDA_RECT::GetLeft(), EDA_RECT::GetRight(), EDA_RECT::GetTop(), EDA_RECT::Inflate(), D_PAD::IsOnLayer(), m_fpAreaBottom, m_fpAreaTop, and SHAPE_POLY_SET::NewOutline().

Referenced by buildFpAreas().

◆ AutoplaceModules()

AR_RESULT AR_AUTOPLACER::AutoplaceModules ( std::vector< MODULE * >  aModules,
BOARD_COMMIT aCommit,
bool  aPlaceOffboardModules = false 
)

Definition at line 899 of file ar_autoplacer.cpp.

901 {
902  wxPoint PosOK;
903  wxPoint memopos;
904  int error;
905  MODULE* module = nullptr;
906  bool cancelled = false;
907 
908  memopos = m_curPosition;
909 
910  //printf("set grid: %d\n", m_gridSize);
911 
912  m_matrix.m_GridRouting = m_gridSize; //(int) m_frame->GetScreen()->GetGridSize().x;
913 
914  // Ensure Board.m_GridRouting has a reasonable value:
915  if( m_matrix.m_GridRouting < Millimeter2iu( 0.25 ) )
916  m_matrix.m_GridRouting = Millimeter2iu( 0.25 );
917 
918  // Compute module parameters used in auto place
919  if( genPlacementRoutingMatrix( ) == 0 )
920  return AR_FAILURE;
921 
922  int moduleCount = 0;
923 
924  for ( auto m : m_board->Modules() )
925  {
926  m->SetNeedsPlaced( false );
927  }
928 
929  std::vector<MODULE *> offboardMods;
930 
931  if( aPlaceOffboardModules )
932  {
933  for ( auto m : m_board->Modules() )
934  {
935  if( !m_matrix.m_BrdBox.Contains( m->GetPosition() ) )
936  {
937  offboardMods.push_back( m );
938  }
939  }
940  }
941 
942  for ( auto m : aModules )
943  {
944  m->SetNeedsPlaced( true );
945  aCommit->Modify(m);
946  }
947 
948  for ( auto m : offboardMods )
949  {
950  m->SetNeedsPlaced( true );
951  aCommit->Modify(m);
952  }
953 
954  for ( auto m : m_board->Modules() )
955  {
956  if( m->NeedsPlaced() ) // Erase from screen
957  moduleCount++;
958  else
960  }
961 
962 
963  int cnt = 0;
964  wxString msg;
965 
966  if( m_progressReporter )
967  {
968  m_progressReporter->Report( _( "Autoplacing components..." ) );
969  m_progressReporter->SetMaxProgress( moduleCount );
970  }
971 
973 
974  if( m_refreshCallback )
975  m_refreshCallback( nullptr );
976 
977 
978  while( ( module = pickModule( ) ) != nullptr )
979  {
980  // Display some info about activity, module placement can take a while:
981  //m_frame->SetStatusText( msg );
982 
983  if( m_progressReporter )
985  _( "Autoplacing %s" ), module->GetReference() ) );
986 
987  double initialOrient = module->GetOrientation();
988 
989  error = getOptimalModulePlacement( module );
990  double bestScore = m_minCost;
991  double bestRotation = 0.0;
992  int rotAllowed;
993  PosOK = m_curPosition;
994 
995  if( error == AR_ABORT_PLACEMENT )
996  goto end_of_tst;
997 
998  // Try orientations 90, 180, 270 degrees from initial orientation
999  rotAllowed = module->GetPlacementCost180();
1000 
1001  //printf("rotAllowed %d\n", rotAllowed);
1002 
1003  if( rotAllowed != 0 )
1004  {
1005  rotateModule( module, 1800.0, true );
1006  error = getOptimalModulePlacement( module );
1007  m_minCost *= OrientationPenalty[rotAllowed];
1008 
1009  if( bestScore > m_minCost ) // This orientation is better.
1010  {
1011  PosOK = m_curPosition;
1012  bestScore = m_minCost;
1013  bestRotation = 1800.0;
1014  }
1015  else
1016  {
1017  rotateModule( module, initialOrient, false );
1018  }
1019 
1020  if( error == AR_ABORT_PLACEMENT )
1021  goto end_of_tst;
1022  }
1023 
1024  // Determine if the best orientation of a module is 90.
1025  rotAllowed = module->GetPlacementCost90();
1026 
1027  if( rotAllowed != 0 )
1028  {
1029  rotateModule( module, 900.0, true );
1030  error = getOptimalModulePlacement( module );
1031  m_minCost *= OrientationPenalty[rotAllowed];
1032 
1033  if( bestScore > m_minCost ) // This orientation is better.
1034  {
1035  PosOK = m_curPosition;
1036  bestScore = m_minCost;
1037  bestRotation = 900.0;
1038  }
1039  else
1040  {
1041  rotateModule( module, initialOrient, false );
1042  }
1043 
1044  if( error == AR_ABORT_PLACEMENT )
1045  goto end_of_tst;
1046  }
1047 
1048  // Determine if the best orientation of a module is -90.
1049  if( rotAllowed != 0 )
1050  {
1051  rotateModule( module, 2700.0, true );
1052  error = getOptimalModulePlacement( module );
1053  m_minCost *= OrientationPenalty[rotAllowed];
1054 
1055  if( bestScore > m_minCost ) // This orientation is better.
1056  {
1057  PosOK = m_curPosition;
1058  bestScore = m_minCost;
1059  bestRotation = 2700.0;
1060  }
1061  else
1062  {
1063  rotateModule( module, initialOrient, false );
1064  }
1065 
1066  if( error == AR_ABORT_PLACEMENT )
1067  goto end_of_tst;
1068  }
1069 
1070 end_of_tst:
1071 
1072  if( error == AR_ABORT_PLACEMENT )
1073  break;
1074 
1075 
1076  bestRotation += initialOrient;
1077 
1078  if( bestRotation != module->GetOrientation() )
1079  {
1080  //printf("best rotation %d\n", bestRotation );
1081  rotateModule( module, bestRotation, false );
1082  }
1083 
1084  // Place module.
1085  placeModule( module, true, m_curPosition );
1086 
1087  module->CalculateBoundingBox();
1088  genModuleOnRoutingMatrix( module );
1089  module->SetIsPlaced( true );
1090  module->SetNeedsPlaced( false );
1092 
1093  if( m_refreshCallback )
1094  m_refreshCallback( module );
1095 
1096 
1097  if( m_progressReporter )
1098  {
1100 
1101  if ( !m_progressReporter->KeepRefreshing( false ) )
1102  {
1103  cancelled = true;
1104  break;
1105  }
1106  }
1107  cnt++;
1108  }
1109 
1110  m_curPosition = memopos;
1111 
1113 
1114  for ( auto m : m_board->Modules() )
1115  {
1116  m->CalculateBoundingBox();
1117  }
1118 
1119  return cancelled ? AR_CANCELLED : AR_COMPLETED;
1120 }
void rotateModule(MODULE *module, double angle, bool incremental)
double GetOrientation() const
Definition: class_module.h:188
COMMIT & Modify(EDA_ITEM *aItem)
Modifies a given item in the model.
Definition: commit.h:103
int GetPlacementCost90() const
Definition: class_module.h:573
PROGRESS_REPORTER * m_progressReporter
void placeModule(MODULE *aModule, bool aDoNotRecreateRatsnest, const wxPoint &aPos)
void CalculateBoundingBox()
Function CalculateBoundingBox calculates the bounding box in board coordinates.
int m_GridRouting
Definition: ar_matrix.h:63
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
void SetNeedsPlaced(bool needsPlaced)
Definition: class_module.h:295
void Report(const wxString &aMessage)
Display aMessage in the progress bar dialog.
bool Contains(const wxPoint &aPoint) const
Function Contains.
const wxString GetReference() const
Function GetReference.
Definition: class_module.h:462
void genModuleOnRoutingMatrix(MODULE *Module)
AR_MATRIX m_matrix
void drawPlacementRoutingMatrix()
DLIST_ITERATOR_WRAPPER< MODULE > Modules()
Definition: class_board.h:252
int getOptimalModulePlacement(MODULE *aModule)
int genPlacementRoutingMatrix()
#define AR_ABORT_PLACEMENT
MODULE * pickModule()
Find the "best" module place.
void SetIsPlaced(bool isPlaced)
Definition: class_module.h:286
int GetPlacementCost180() const
Definition: class_module.h:570
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:140
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
bool KeepRefreshing(bool aWait=false)
Update the UI dialog.
std::function< int(MODULE *aModule)> m_refreshCallback
static const double OrientationPenalty[11]
wxPoint m_curPosition
void SetMaxProgress(int aMaxProgress)
Fix the value thar gives the 100 precent progress bar length (inside the current virtual zone)
virtual void SetTitle(const wxString &aTitle)
change the title displayed on the window caption MUST only be called from the main thread.
void AdvanceProgress()
Increment the progress bar length (inside the current virtual zone)

References PROGRESS_REPORTER::AdvanceProgress(), AR_ABORT_PLACEMENT, AR_CANCELLED, AR_COMPLETED, AR_FAILURE, MODULE::CalculateBoundingBox(), EDA_RECT::Contains(), drawPlacementRoutingMatrix(), Format(), genModuleOnRoutingMatrix(), genPlacementRoutingMatrix(), getOptimalModulePlacement(), MODULE::GetOrientation(), MODULE::GetPlacementCost180(), MODULE::GetPlacementCost90(), MODULE::GetReference(), PROGRESS_REPORTER::KeepRefreshing(), m_board, AR_MATRIX::m_BrdBox, m_curPosition, AR_MATRIX::m_GridRouting, m_gridSize, m_matrix, m_minCost, m_progressReporter, m_refreshCallback, COMMIT::Modify(), BOARD::Modules(), OrientationPenalty, pickModule(), placeModule(), PROGRESS_REPORTER::Report(), rotateModule(), MODULE::SetIsPlaced(), PROGRESS_REPORTER::SetMaxProgress(), MODULE::SetNeedsPlaced(), PROGRESS_REPORTER::SetTitle(), and AR_MATRIX::UnInitRoutingMatrix().

Referenced by AUTOPLACE_TOOL::autoplace().

◆ buildFpAreas()

void AR_AUTOPLACER::buildFpAreas ( MODULE aFootprint,
int  aFpClearance 
)
private

Definition at line 334 of file ar_autoplacer.cpp.

335 {
338 
339  if( aFootprint->BuildPolyCourtyard() )
340  {
341  m_fpAreaTop = aFootprint->GetPolyCourtyardFront();
342  m_fpAreaBottom = aFootprint->GetPolyCourtyardBack();
343  }
344 
345  LSET layerMask;
346 
347  if( aFootprint->GetLayer() == F_Cu )
348  layerMask.set( F_Cu );
349 
350  if( aFootprint->GetLayer() == B_Cu )
351  layerMask.set( B_Cu );
352 
353  EDA_RECT fpBBox = aFootprint->GetBoundingBox();
354 
355  fpBBox.Inflate( ( m_matrix.m_GridRouting / 2 ) + aFpClearance );
356 
357  // Add a minimal area to the fp area:
358  addFpBody( fpBBox.GetOrigin(), fpBBox.GetEnd(), layerMask );
359 
360  // Trace pads + clearance areas.
361  for( auto pad : aFootprint->Pads() )
362  {
363  int margin = (m_matrix.m_GridRouting / 2) + pad->GetClearance();
364  addPad( pad, margin );
365  }
366 }
SHAPE_POLY_SET & GetPolyCourtyardFront()
Used in DRC to test the courtyard area (a complex polygon)
Definition: class_module.h:702
bool BuildPolyCourtyard()
Used in DRC to build the courtyard area (a complex polygon) from graphic items put on the courtyard.
int m_GridRouting
Definition: ar_matrix.h:63
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:168
void addPad(D_PAD *aPad, int aClearance)
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:114
SHAPE_POLY_SET m_fpAreaBottom
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 wxPoint GetOrigin() const
Definition: eda_rect.h:112
SHAPE_POLY_SET m_fpAreaTop
void addFpBody(wxPoint aStart, wxPoint aEnd, LSET aLayerMask)
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
SHAPE_POLY_SET & GetPolyCourtyardBack()
Definition: class_module.h:703
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.

References addFpBody(), addPad(), B_Cu, MODULE::BuildPolyCourtyard(), F_Cu, MODULE::GetBoundingBox(), EDA_RECT::GetEnd(), BOARD_ITEM::GetLayer(), EDA_RECT::GetOrigin(), MODULE::GetPolyCourtyardBack(), MODULE::GetPolyCourtyardFront(), EDA_RECT::Inflate(), m_fpAreaBottom, m_fpAreaTop, AR_MATRIX::m_GridRouting, m_matrix, MODULE::Pads(), and SHAPE_POLY_SET::RemoveAllContours().

Referenced by genModuleOnRoutingMatrix(), and testModuleOnBoard().

◆ calculateKeepOutArea()

unsigned int AR_AUTOPLACER::calculateKeepOutArea ( const EDA_RECT aRect,
int  side 
)
private

Definition at line 513 of file ar_autoplacer.cpp.

514 {
515  wxPoint start = aRect.GetOrigin();
516  wxPoint end = aRect.GetEnd();
517 
518  start -= m_matrix.m_BrdBox.GetOrigin();
519  end -= m_matrix.m_BrdBox.GetOrigin();
520 
521  int row_min = start.y / m_matrix.m_GridRouting;
522  int row_max = end.y / m_matrix.m_GridRouting;
523  int col_min = start.x / m_matrix.m_GridRouting;
524  int col_max = end.x / m_matrix.m_GridRouting;
525 
526  if( start.y > row_min * m_matrix.m_GridRouting )
527  row_min++;
528 
529  if( start.x > col_min * m_matrix.m_GridRouting )
530  col_min++;
531 
532  if( row_min < 0 )
533  row_min = 0;
534 
535  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
536  row_max = m_matrix.m_Nrows - 1;
537 
538  if( col_min < 0 )
539  col_min = 0;
540 
541  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
542  col_max = m_matrix.m_Ncols - 1;
543 
544  unsigned int keepOutCost = 0;
545 
546  for( int row = row_min; row <= row_max; row++ )
547  {
548  for( int col = col_min; col <= col_max; col++ )
549  {
550  // m_matrix.GetDist returns the "cost" of the cell
551  // at position (row, col)
552  // in autoplace this is the cost of the cell, if it is
553  // inside aRect
554  keepOutCost += m_matrix.GetDist( row, col, side );
555  }
556  }
557 
558  return keepOutCost;
559 }
int m_Ncols
Definition: ar_matrix.h:65
int m_GridRouting
Definition: ar_matrix.h:63
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:114
const wxPoint GetOrigin() const
Definition: eda_rect.h:112
int m_Nrows
Definition: ar_matrix.h:65
DIST_CELL GetDist(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:259

References AR_MATRIX::GetDist(), EDA_RECT::GetEnd(), EDA_RECT::GetOrigin(), AR_MATRIX::m_BrdBox, AR_MATRIX::m_GridRouting, m_matrix, AR_MATRIX::m_Ncols, and AR_MATRIX::m_Nrows.

Referenced by testModuleOnBoard().

◆ computePlacementRatsnestCost()

double AR_AUTOPLACER::computePlacementRatsnestCost ( MODULE aModule,
const wxPoint &  aOffset 
)
private

Definition at line 732 of file ar_autoplacer.cpp.

733 {
734  double curr_cost;
735  VECTOR2I start; // start point of a ratsnest
736  VECTOR2I end; // end point of a ratsnest
737  int dx, dy;
738 
739  curr_cost = 0;
740 
741  for ( auto pad : aModule->Pads() )
742  {
743  auto nearest = nearestPad( aModule, pad, aOffset );
744 
745  if( !nearest )
746  continue;
747 
748  //printf("pad %s nearest %s\n", (const char *)aModule->GetReference().c_str(), (const char *)nearest->GetParent()->GetReference().c_str());
749 
750  start = VECTOR2I( pad->GetPosition() ) - VECTOR2I(aOffset);
751  end = VECTOR2I( nearest->GetPosition() );
752 
753  //m_overlay->SetIsStroke( true );
754  //m_overlay->SetStrokeColor( COLOR4D(0.0, 1.0, 0.0, 1.0) );
755  //m_overlay->Line( start, end );
756 
757  // Cost of the ratsnest.
758  dx = end.x - start.x;
759  dy = end.y - start.y;
760 
761  dx = abs( dx );
762  dy = abs( dy );
763 
764  // ttry to have always dx >= dy to calculate the cost of the rastsnet
765  if( dx < dy )
766  std::swap( dx, dy );
767 
768  // Cost of the connection = length + penalty due to the slope
769  // dx is the biggest length relative to the X or Y axis
770  // the penalty is max for 45 degrees ratsnests,
771  // and 0 for horizontal or vertical ratsnests.
772  // For Horizontal and Vertical ratsnests, dy = 0;
773  double conn_cost = hypot( dx, dy * 2.0 );
774  curr_cost += conn_cost; // Total cost = sum of costs of each connection
775  }
776 
777  return curr_cost;
778 }
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:168
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
#define abs(a)
Definition: auxiliary.h:84
const D_PAD * nearestPad(MODULE *aRefModule, D_PAD *aRefPad, const wxPoint &aOffset)

References abs, nearestPad(), MODULE::Pads(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by getOptimalModulePlacement().

◆ drawPlacementRoutingMatrix()

void AR_AUTOPLACER::drawPlacementRoutingMatrix ( )
private

Definition at line 868 of file ar_autoplacer.cpp.

869 {
870  // Draw the board free area
871  m_overlay->Clear();
872  m_overlay->SetIsFill( true );
873  m_overlay->SetIsStroke( false );
874 
875  SHAPE_POLY_SET freeArea = m_topFreeArea;
876  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
877 
878  // Draw the free polygon areas, top side:
879  if( freeArea.OutlineCount() > 0 )
880  {
881  m_overlay->SetIsFill( true );
882  m_overlay->SetIsStroke( false );
883  m_overlay->SetFillColor( COLOR4D(0.7, 0.0, 0.1, 0.2) );
884  m_overlay->Polygon( freeArea );
885  }
886 
887  freeArea = m_bottomFreeArea;
888  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
889 
890  // Draw the free polygon areas, bottom side:
891  if( freeArea.OutlineCount() > 0 )
892  {
893  m_overlay->SetFillColor( COLOR4D(0.0, 0.7, 0.0, 0.2) );
894  m_overlay->Polygon( freeArea );
895  }
896 }
SHAPE_POLY_SET m_topFreeArea
int OutlineCount() const
Returns the number of outlines in the set
Class SHAPE_POLY_SET.
SHAPE_POLY_SET m_bottomFreeArea
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay
Class COLOR4D is the color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:39

References SHAPE_POLY_SET::Fracture(), m_bottomFreeArea, m_overlay, m_topFreeArea, SHAPE_POLY_SET::OutlineCount(), and SHAPE_POLY_SET::PM_FAST.

Referenced by AutoplaceModules().

◆ fillMatrix()

bool AR_AUTOPLACER::fillMatrix ( )
private

fills m_matrix cells from m_boardShape.

cells inside m_boardShape are set to CELL_IS_ZONE

Definition at line 157 of file ar_autoplacer.cpp.

158 {
159  std::vector <int> x_coordinates;
160  bool success = true;
161  int step = m_matrix.m_GridRouting;
162  wxPoint coord_orgin = m_matrix.GetBrdCoordOrigin(); // Board coordinate of matruix cell (0,0)
163 
164  // Create a single board outline:
165  SHAPE_POLY_SET brd_shape = m_boardShape;
166  brd_shape.Fracture( SHAPE_POLY_SET::PM_FAST );
167  const SHAPE_LINE_CHAIN& outline = brd_shape.Outline(0);
168  const BOX2I& rect = outline.BBox();
169 
170  // Creates the horizontal segments
171  // Calculate the y limits of the area
172  for( int refy = rect.GetY(), endy = rect.GetBottom(); refy < endy; refy += step )
173  {
174  // The row index (vertical position) of current line scan inside the placement matrix
175  int idy = (refy - coord_orgin.y) / step;
176 
177  // Ensure we are still inside the placement matrix
178  if( idy >= m_matrix.m_Nrows )
179  break;
180 
181  // Ensure we are inside the placement matrix
182  if( idy <= 0 )
183  continue;
184 
185  // find all intersection points of an infinite line with polyline sides
186  x_coordinates.clear();
187 
188  for( int v = 0; v < outline.PointCount(); v++ )
189  {
190 
191  int seg_startX = outline.CPoint( v ).x;
192  int seg_startY = outline.CPoint( v ).y;
193  int seg_endX = outline.CPoint( v + 1 ).x;
194  int seg_endY = outline.CPoint( v + 1 ).y;
195 
196  /* Trivial cases: skip if ref above or below the segment to test */
197  if( ( seg_startY > refy ) && ( seg_endY > refy ) )
198  continue;
199 
200  // segment below ref point, or its Y end pos on Y coordinate ref point: skip
201  if( ( seg_startY <= refy ) && (seg_endY <= refy ) )
202  continue;
203 
204  /* at this point refy is between seg_startY and seg_endY
205  * see if an horizontal line at Y = refy is intersecting this segment
206  */
207  // calculate the x position of the intersection of this segment and the
208  // infinite line this is more easier if we move the X,Y axis origin to
209  // the segment start point:
210 
211  seg_endX -= seg_startX;
212  seg_endY -= seg_startY;
213  double newrefy = (double) ( refy - seg_startY );
214  double intersec_x;
215 
216  if ( seg_endY == 0 ) // horizontal segment on the same line: skip
217  continue;
218 
219  // Now calculate the x intersection coordinate of the horizontal line at
220  // y = newrefy and the segment from (0,0) to (seg_endX,seg_endY) with the
221  // horizontal line at the new refy position the line slope is:
222  // slope = seg_endY/seg_endX; and inv_slope = seg_endX/seg_endY
223  // and the x pos relative to the new origin is:
224  // intersec_x = refy/slope = refy * inv_slope
225  // Note: because horizontal segments are already tested and skipped, slope
226  // exists (seg_end_y not O)
227  double inv_slope = (double) seg_endX / seg_endY;
228  intersec_x = newrefy * inv_slope;
229  x_coordinates.push_back( (int) intersec_x + seg_startX );
230  }
231 
232  // A line scan is finished: build list of segments
233 
234  // Sort intersection points by increasing x value:
235  // So 2 consecutive points are the ends of a segment
236  std::sort( x_coordinates.begin(), x_coordinates.end() );
237 
238  // An even number of coordinates is expected, because a segment has 2 ends.
239  // An if this algorithm always works, it must always find an even count.
240  if( ( x_coordinates.size() & 1 ) != 0 )
241  {
242  success = false;
243  break;
244  }
245 
246  // Fill cells having the same Y coordinate
247  int iimax = x_coordinates.size() - 1;
248 
249  for( int ii = 0; ii < iimax; ii += 2 )
250  {
251  int seg_start_x = x_coordinates[ii] - coord_orgin.x;
252  int seg_end_x = x_coordinates[ii + 1] - coord_orgin.x;
253  // Fill cells at y coord = idy,
254  // and at x cood >= seg_start_x and <= seg_end_x
255 
256  for( int idx = seg_start_x / step; idx < m_matrix.m_Ncols; idx++ )
257  {
258  if( idx * step > seg_end_x )
259  break;
260 
261  if( idx * step >= seg_start_x )
263  }
264 
265  }
266  } // End examine segments in one area
267 
268  return success;
269 }
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:43
int m_Ncols
Definition: ar_matrix.h:65
int m_GridRouting
Definition: ar_matrix.h:63
#define CELL_IS_ZONE
Definition: ar_cell.h:40
coord_type GetBottom() const
Definition: box2.h:198
int PointCount() const
Function PointCount()
AR_MATRIX m_matrix
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
SHAPE_POLY_SET m_boardShape
Class SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
int m_Nrows
Definition: ar_matrix.h:65
void SetCell(int aRow, int aCol, int aSide, MATRIX_CELL aCell)
Definition: ar_matrix.cpp:205
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
coord_type GetY() const
Definition: box2.h:189
Class SHAPE_LINE_CHAIN.
wxPoint GetBrdCoordOrigin()
function GetBrdCoordOrigin
Definition: ar_matrix.h:99

References AR_SIDE_BOTTOM, SHAPE_LINE_CHAIN::BBox(), CELL_IS_ZONE, SHAPE_LINE_CHAIN::CPoint(), SHAPE_POLY_SET::Fracture(), BOX2< Vec >::GetBottom(), AR_MATRIX::GetBrdCoordOrigin(), BOX2< Vec >::GetY(), m_boardShape, AR_MATRIX::m_GridRouting, m_matrix, AR_MATRIX::m_Ncols, AR_MATRIX::m_Nrows, SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::PM_FAST, SHAPE_LINE_CHAIN::PointCount(), AR_MATRIX::SetCell(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by genPlacementRoutingMatrix().

◆ genModuleOnRoutingMatrix()

void AR_AUTOPLACER::genModuleOnRoutingMatrix ( MODULE Module)
private

Definition at line 369 of file ar_autoplacer.cpp.

370 {
371  int ox, oy, fx, fy;
372  LSET layerMask;
373  EDA_RECT fpBBox = Module->GetBoundingBox();
374 
375  fpBBox.Inflate( m_matrix.m_GridRouting / 2 );
376  ox = fpBBox.GetX();
377  fx = fpBBox.GetRight();
378  oy = fpBBox.GetY();
379  fy = fpBBox.GetBottom();
380 
381  if( ox < m_matrix.m_BrdBox.GetX() )
382  ox = m_matrix.m_BrdBox.GetX();
383 
384  if( ox > m_matrix.m_BrdBox.GetRight() )
385  ox = m_matrix.m_BrdBox.GetRight();
386 
387  if( fx < m_matrix.m_BrdBox.GetX() )
388  fx = m_matrix.m_BrdBox.GetX();
389 
390  if( fx > m_matrix.m_BrdBox.GetRight() )
391  fx = m_matrix.m_BrdBox.GetRight();
392 
393  if( oy < m_matrix.m_BrdBox.GetY() )
394  oy = m_matrix.m_BrdBox.GetY();
395 
396  if( oy > m_matrix.m_BrdBox.GetBottom() )
397  oy = m_matrix.m_BrdBox.GetBottom();
398 
399  if( fy < m_matrix.m_BrdBox.GetY() )
400  fy = m_matrix.m_BrdBox.GetY();
401 
402  if( fy > m_matrix.m_BrdBox.GetBottom() )
403  fy = m_matrix.m_BrdBox.GetBottom();
404 
405  if( Module->GetLayer() == F_Cu )
406  layerMask.set( F_Cu );
407 
408  if( Module->GetLayer() == B_Cu )
409  layerMask.set( B_Cu );
410 
411  m_matrix.TraceFilledRectangle( ox, oy, fx, fy, layerMask,
413 
414  // Trace pads + clearance areas.
415  for( auto pad : Module->Pads() )
416  {
417  int margin = (m_matrix.m_GridRouting / 2) + pad->GetClearance();
419  }
420 
421  // Trace clearance.
422  int margin = ( m_matrix.m_GridRouting * Module->GetPadCount() ) / AR_GAIN;
423  m_matrix.CreateKeepOutRectangle( ox, oy, fx, fy, margin, AR_KEEPOUT_MARGIN , layerMask );
424 
425  // Build the footprint courtyard
426  buildFpAreas( Module, margin );
427 
428  // Substract the shape to free areas
431 }
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
GetPadCount returns the number of pads.
SHAPE_POLY_SET m_topFreeArea
#define CELL_IS_MODULE
Definition: ar_cell.h:37
int GetX() const
Definition: eda_rect.h:109
int m_GridRouting
Definition: ar_matrix.h:63
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
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:168
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
void buildFpAreas(MODULE *aFootprint, int aFpClearance)
#define AR_GAIN
#define AR_KEEPOUT_MARGIN
int GetBottom() const
Definition: eda_rect.h:122
AR_MATRIX m_matrix
SHAPE_POLY_SET m_fpAreaBottom
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.
int GetRight() const
Definition: eda_rect.h:119
SHAPE_POLY_SET m_bottomFreeArea
SHAPE_POLY_SET m_fpAreaTop
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:110
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.

References AR_GAIN, AR_KEEPOUT_MARGIN, B_Cu, SHAPE_POLY_SET::BooleanSubtract(), buildFpAreas(), CELL_IS_MODULE, AR_MATRIX::CreateKeepOutRectangle(), F_Cu, EDA_RECT::GetBottom(), MODULE::GetBoundingBox(), BOARD_ITEM::GetLayer(), MODULE::GetPadCount(), EDA_RECT::GetRight(), EDA_RECT::GetX(), EDA_RECT::GetY(), EDA_RECT::Inflate(), m_bottomFreeArea, AR_MATRIX::m_BrdBox, m_fpAreaBottom, m_fpAreaTop, AR_MATRIX::m_GridRouting, m_matrix, m_topFreeArea, MODULE::Pads(), AR_MATRIX::PlacePad(), SHAPE_POLY_SET::PM_FAST, AR_MATRIX::TraceFilledRectangle(), and AR_MATRIX::WRITE_OR_CELL.

Referenced by AutoplaceModules().

◆ genPlacementRoutingMatrix()

int AR_AUTOPLACER::genPlacementRoutingMatrix ( )
private

Definition at line 104 of file ar_autoplacer.cpp.

105 {
107 
109 
110  if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
111  return 0;
112 
113  // Build the board shape
114  m_board->GetBoardPolygonOutlines( m_boardShape /*, aErrorText, aErrorLocation*/ );
117 
118  m_matrix.ComputeMatrixSize( bbox );
119  int nbCells = m_matrix.m_Ncols * m_matrix.m_Nrows;
120 
121  // Choose the number of board sides.
126 
127  // Fill (mark) the cells inside the board:
128  fillMatrix();
129 
130  // Other obstacles can be added here:
131  for( auto drawing : m_board->Drawings() )
132  {
133  switch( drawing->Type() )
134  {
135  case PCB_LINE_T:
136  if( drawing->GetLayer() != Edge_Cuts )
137  {
140  }
141  break;
142 
143  default:
144  break;
145  }
146  }
147 
148  // Initialize top layer. to the same value as the bottom layer
151  nbCells * sizeof(AR_MATRIX::MATRIX_CELL) );
152 
153  return 1;
154 }
SHAPE_POLY_SET m_topFreeArea
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:43
int InitRoutingMatrix()
Function InitBoard initializes the data structures.
Definition: ar_matrix.cpp:92
#define AR_SIDE_TOP
Definition: ar_matrix.h:42
int m_Ncols
Definition: ar_matrix.h:65
const EDA_RECT GetBoardEdgesBoundingBox() const
Function GetBoardEdgesBoundingBox Returns the board bounding box calculated using exclusively the boa...
Definition: class_board.h:802
int m_GridRouting
Definition: ar_matrix.h:63
int GetWidth() const
Definition: eda_rect.h:117
void TraceSegmentPcb(DRAWSEGMENT *pt_segm, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:1085
AR_MATRIX m_matrix
PCB_LAYER_ID m_routeLayerTop
Definition: ar_matrix.h:69
SHAPE_POLY_SET m_boardShape
#define CELL_IS_HOLE
Definition: ar_cell.h:36
int m_Nrows
Definition: ar_matrix.h:65
MATRIX_CELL * m_BoardSide[AR_MAX_ROUTING_LAYERS_COUNT]
Definition: ar_matrix.h:56
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
int GetHeight() const
Definition: eda_rect.h:118
bool fillMatrix()
fills m_matrix cells from m_boardShape.
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:140
int m_RoutingLayersCount
Definition: ar_matrix.h:62
#define CELL_IS_EDGE
Definition: ar_cell.h:38
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
unsigned char MATRIX_CELL
Definition: ar_matrix.h:52
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
class DRAWSEGMENT, a segment not on copper layers
Definition: typeinfo.h:91
DLIST_ITERATOR_WRAPPER< BOARD_ITEM > Drawings()
Definition: class_board.h:253
PCB_LAYER_ID m_routeLayerBottom
Definition: ar_matrix.h:70

References AR_SIDE_BOTTOM, AR_SIDE_TOP, B_Cu, CELL_IS_EDGE, CELL_IS_HOLE, AR_MATRIX::ComputeMatrixSize(), BOARD::Drawings(), Edge_Cuts, F_Cu, fillMatrix(), BOARD::GetBoardEdgesBoundingBox(), BOARD::GetBoardPolygonOutlines(), EDA_RECT::GetHeight(), EDA_RECT::GetWidth(), AR_MATRIX::InitRoutingMatrix(), m_board, m_boardShape, AR_MATRIX::m_BoardSide, m_bottomFreeArea, AR_MATRIX::m_GridRouting, m_matrix, AR_MATRIX::m_Ncols, AR_MATRIX::m_Nrows, AR_MATRIX::m_routeLayerBottom, AR_MATRIX::m_routeLayerTop, AR_MATRIX::m_RoutingLayersCount, m_topFreeArea, PCB_LINE_T, AR_MATRIX::TraceSegmentPcb(), AR_MATRIX::UnInitRoutingMatrix(), and AR_MATRIX::WRITE_CELL.

Referenced by AutoplaceModules().

◆ getOptimalModulePlacement()

int AR_AUTOPLACER::getOptimalModulePlacement ( MODULE aModule)
private

Definition at line 603 of file ar_autoplacer.cpp.

604 {
605  int error = 1;
606  wxPoint LastPosOK;
607  double min_cost, curr_cost, Score;
608  bool TstOtherSide;
609 
610  aModule->CalculateBoundingBox();
611 
612  LastPosOK = m_matrix.m_BrdBox.GetOrigin();
613 
614  wxPoint mod_pos = aModule->GetPosition();
615  EDA_RECT fpBBox = aModule->GetFootprintRect();
616 
617  // Move fpBBox to have the footprint position at (0,0)
618  fpBBox.Move( -mod_pos );
619  wxPoint fpBBoxOrg = fpBBox.GetOrigin();
620 
621  // Calculate the limit of the footprint position, relative
622  // to the routing matrix area
623  wxPoint xylimit = m_matrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
624 
625  wxPoint initialPos = m_matrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
626 
627  // Stay on grid.
628  initialPos.x -= initialPos.x % m_matrix.m_GridRouting;
629  initialPos.y -= initialPos.y % m_matrix.m_GridRouting;
630 
631  m_curPosition = initialPos;
632  auto moduleOffset = mod_pos - m_curPosition;
633 
634  /* Examine pads, and set TstOtherSide to true if a footprint
635  * has at least 1 pad through.
636  */
637  TstOtherSide = false;
638 
640  {
641  LSET other( aModule->GetLayer() == B_Cu ? F_Cu : B_Cu );
642 
643  for( auto pad : aModule->Pads() )
644  {
645  if( !( pad->GetLayerSet() & other ).any() )
646  continue;
647 
648  TstOtherSide = true;
649  break;
650  }
651  }
652 
653  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
654 
655  min_cost = -1.0;
656 // m_frame->SetStatusText( wxT( "Score ??, pos ??" ) );
657 
658 
659  for( ; m_curPosition.x < xylimit.x; m_curPosition.x += m_matrix.m_GridRouting )
660  {
661  m_curPosition.y = initialPos.y;
662 
663  for( ; m_curPosition.y < xylimit.y; m_curPosition.y += m_matrix.m_GridRouting )
664  {
665 
666  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
667  moduleOffset = mod_pos - m_curPosition;
668  int keepOutCost = testModuleOnBoard( aModule, TstOtherSide, moduleOffset );
669 
670  if( keepOutCost >= 0 ) // i.e. if the module can be put here
671  {
672  error = 0;
673  // m_frame->build_ratsnest_module( aModule ); // fixme
674  curr_cost = computePlacementRatsnestCost( aModule, moduleOffset );
675  Score = curr_cost + keepOutCost;
676 
677  if( (min_cost >= Score ) || (min_cost < 0 ) )
678  {
679  LastPosOK = m_curPosition;
680  min_cost = Score;
681  wxString msg;
682 /* msg.Printf( wxT( "Score %g, pos %s, %s" ),
683  min_cost,
684  GetChars( ::CoordinateToString( LastPosOK.x ) ),
685  GetChars( ::CoordinateToString( LastPosOK.y ) ) );
686  m_frame->SetStatusText( msg );*/
687  }
688  }
689  }
690  }
691 
692  // Regeneration of the modified variable.
693  m_curPosition = LastPosOK;
694 
695  m_minCost = min_cost;
696  return error;
697 }
void Move(const wxPoint &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
void CalculateBoundingBox()
Function CalculateBoundingBox calculates the bounding box in board coordinates.
int m_GridRouting
Definition: ar_matrix.h:63
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
DLIST_ITERATOR_WRAPPER< D_PAD > Pads()
Definition: class_module.h:168
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:124
EDA_RECT GetFootprintRect() const
Function GetFootprintRect() Returns the area of the module footprint excluding any text.
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:114
Class LSET is a set of PCB_LAYER_IDs.
double computePlacementRatsnestCost(MODULE *aModule, const wxPoint &aOffset)
const wxPoint GetOrigin() const
Definition: eda_rect.h:112
int testModuleOnBoard(MODULE *aModule, bool TstOtherSide, const wxPoint &aOffset)
int m_RoutingLayersCount
Definition: ar_matrix.h:62
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
wxPoint m_curPosition
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:183

References B_Cu, MODULE::CalculateBoundingBox(), computePlacementRatsnestCost(), F_Cu, EDA_RECT::GetEnd(), MODULE::GetFootprintRect(), BOARD_ITEM::GetLayer(), EDA_RECT::GetOrigin(), MODULE::GetPosition(), AR_MATRIX::m_BrdBox, m_curPosition, AR_MATRIX::m_GridRouting, m_matrix, m_minCost, AR_MATRIX::m_RoutingLayersCount, EDA_RECT::Move(), MODULE::Pads(), EDA_RECT::SetOrigin(), and testModuleOnBoard().

Referenced by AutoplaceModules().

◆ nearestPad()

const D_PAD * AR_AUTOPLACER::nearestPad ( MODULE aRefModule,
D_PAD aRefPad,
const wxPoint &  aOffset 
)
private

Definition at line 700 of file ar_autoplacer.cpp.

701 {
702  const D_PAD* nearest = nullptr;
703  int64_t nearestDist = INT64_MAX;
704 
705  for ( auto mod : m_board->Modules() )
706  {
707  if ( mod == aRefModule )
708  continue;
709 
710  if( !m_matrix.m_BrdBox.Contains( mod->GetPosition() ) )
711  continue;
712 
713  for ( auto pad: mod->Pads() )
714  {
715  if ( pad->GetNetCode() != aRefPad->GetNetCode() || pad->GetNetCode() <= 0 )
716  continue;
717 
718  auto dist = (VECTOR2I( aRefPad->GetPosition() - aOffset ) - VECTOR2I( pad->GetPosition() ) ).EuclideanNorm();
719 
720  if ( dist < nearestDist )
721  {
722  nearestDist = dist;
723  nearest = pad;
724  }
725  }
726  }
727 
728  return nearest;
729 }
int GetNetCode() const
Function GetNetCode.
static const int dist[10][10]
Definition: ar_matrix.cpp:320
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
bool Contains(const wxPoint &aPoint) const
Function Contains.
AR_MATRIX m_matrix
DLIST_ITERATOR_WRAPPER< MODULE > Modules()
Definition: class_board.h:252
const wxPoint GetPosition() const override
Definition: class_pad.h:222
#define mod(a, n)
Definition: greymap.cpp:24

References EDA_RECT::Contains(), dist, BOARD_CONNECTED_ITEM::GetNetCode(), D_PAD::GetPosition(), m_board, AR_MATRIX::m_BrdBox, m_matrix, mod, and BOARD::Modules().

Referenced by computePlacementRatsnestCost().

◆ pickModule()

MODULE * AR_AUTOPLACER::pickModule ( )
private

Find the "best" module place.

The criteria are:

  • Maximum ratsnest with modules already placed
  • Max size, and number of pads max

Definition at line 803 of file ar_autoplacer.cpp.

804 {
805  MODULE* module;
806  std::vector <MODULE*> moduleList;
807 
808 
809  for( auto m : m_board->Modules() )
810  {
812  moduleList.push_back( m );
813  }
814 
815  sort( moduleList.begin(), moduleList.end(), sortFootprintsByComplexity );
816 
817  for( unsigned kk = 0; kk < moduleList.size(); kk++ )
818  {
819  module = moduleList[kk];
820  module->SetFlag( 0 );
821 
822  if( !module->NeedsPlaced() )
823  continue;
824 
825  m_connectivity->Update( module );
826  }
827 
828  m_connectivity->RecalculateRatsnest();
829 
830  for( unsigned kk = 0; kk < moduleList.size(); kk++ )
831  {
832  module = moduleList[kk];
833 
834  auto edges = m_connectivity->GetRatsnestForComponent( module, true );
835 
836  module->SetFlag( edges.size() ) ;
837  }
838 
839  sort( moduleList.begin(), moduleList.end(), sortFootprintsByRatsnestSize );
840 
841  // Search for "best" module.
842  MODULE* bestModule = nullptr;
843  MODULE* altModule = nullptr;
844 
845  for( unsigned ii = 0; ii < moduleList.size(); ii++ )
846  {
847  module = moduleList[ii];
848 
849  if( !module->NeedsPlaced() )
850  continue;
851 
852  altModule = module;
853 
854  if( module->GetFlag() == 0 )
855  continue;
856 
857  bestModule = module;
858  break;
859  }
860 
861  if( bestModule )
862  return bestModule;
863  else
864  return altModule;
865 }
void CalculateBoundingBox()
Function CalculateBoundingBox calculates the bounding box in board coordinates.
DLIST_ITERATOR_WRAPPER< MODULE > Modules()
Definition: class_board.h:252
static bool sortFootprintsByComplexity(MODULE *ref, MODULE *compare)
static bool sortFootprintsByRatsnestSize(MODULE *ref, MODULE *compare)
bool NeedsPlaced() const
Definition: class_module.h:294
int GetFlag() const
Definition: class_module.h:230
void SetFlag(int aFlag)
Definition: class_module.h:228
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References MODULE::CalculateBoundingBox(), MODULE::GetFlag(), m_board, m_connectivity, BOARD::Modules(), MODULE::NeedsPlaced(), MODULE::SetFlag(), sortFootprintsByComplexity(), and sortFootprintsByRatsnestSize().

Referenced by AutoplaceModules().

◆ placeModule()

void AR_AUTOPLACER::placeModule ( MODULE aModule,
bool  aDoNotRecreateRatsnest,
const wxPoint &  aPos 
)
private

Definition at line 94 of file ar_autoplacer.cpp.

95 {
96  if( !aModule )
97  return;
98 
99  aModule->SetPosition( aPos );
100  m_connectivity->Update( aModule );
101 }
void SetPosition(const wxPoint &aPos) override
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References m_connectivity, and MODULE::SetPosition().

Referenced by AutoplaceModules().

◆ QueryOffboardModules()

const std::vector<MODULE*> AR_AUTOPLACER::QueryOffboardModules ( )

◆ rotateModule()

void AR_AUTOPLACER::rotateModule ( MODULE module,
double  angle,
bool  incremental 
)
private

Definition at line 273 of file ar_autoplacer.cpp.

274 {
275  if( module == NULL )
276  return;
277 
278  if( incremental )
279  module->SetOrientation( module->GetOrientation() + angle );
280  else
281  module->SetOrientation( angle );
282 
283 
284  m_board->GetConnectivity()->Update( module );
285 }
double GetOrientation() const
Definition: class_module.h:188
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Function GetConnectivity() returns list of missing connections between components/tracks.
Definition: class_board.h:292
void SetOrientation(double newangle)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

References PNS::angle(), BOARD::GetConnectivity(), MODULE::GetOrientation(), m_board, and MODULE::SetOrientation().

Referenced by AutoplaceModules().

◆ SetOverlay()

void AR_AUTOPLACER::SetOverlay ( std::shared_ptr< KIGFX::VIEW_OVERLAY aOverlay)
inline

Set a VIEW overlay to draw items during a autoplace session.

Definition at line 76 of file ar_autoplacer.h.

77  {
78  m_overlay = aOverlay;
79  }
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay

References m_overlay.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ SetPlacementGrid()

void AR_AUTOPLACER::SetPlacementGrid ( int  aGrid)
inline

Definition at line 68 of file ar_autoplacer.h.

69  {
70  m_gridSize = aGrid;
71  }

References m_gridSize.

◆ SetProgressReporter()

void AR_AUTOPLACER::SetProgressReporter ( PROGRESS_REPORTER aReporter)
inline

Definition at line 90 of file ar_autoplacer.h.

91  {
92  m_progressReporter = aReporter;
93  }
PROGRESS_REPORTER * m_progressReporter

References m_progressReporter.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ SetRefreshCallback()

void AR_AUTOPLACER::SetRefreshCallback ( std::function< int(MODULE *aModule)>  aCallback)
inline

a callback function to redraw on screen the view after changes, for instance after moving a footprint

Definition at line 85 of file ar_autoplacer.h.

86  {
87  m_refreshCallback = aCallback;
88  }
std::function< int(MODULE *aModule)> m_refreshCallback

References m_refreshCallback.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ testModuleByPolygon()

int AR_AUTOPLACER::testModuleByPolygon ( MODULE aModule,
int  aSide,
const wxPoint &  aOffset 
)
private

Definition at line 492 of file ar_autoplacer.cpp.

493 {
494  // Test for footprint out of board:
495  // If a footprint is not fully inside the board, substract board polygon
496  // to the footprint polygon gives a non null area.
497  SHAPE_POLY_SET fp_area = m_fpAreaTop;
498  fp_area.Move( -aOffset );
499  SHAPE_POLY_SET out_of_board_area;
500  out_of_board_area.BooleanSubtract( fp_area, m_topFreeArea, SHAPE_POLY_SET::PM_FAST );
501 
502  if( out_of_board_area.OutlineCount() )
503  return AR_OCCUIPED_BY_MODULE;
504 
505  return AR_FREE_CELL;
506 }
SHAPE_POLY_SET m_topFreeArea
int OutlineCount() const
Returns the number of outlines in the set
void Move(const VECTOR2I &aVector) override
Class SHAPE_POLY_SET.
SHAPE_POLY_SET m_fpAreaTop
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp

References AR_FREE_CELL, AR_OCCUIPED_BY_MODULE, SHAPE_POLY_SET::BooleanSubtract(), m_fpAreaTop, m_topFreeArea, SHAPE_POLY_SET::Move(), SHAPE_POLY_SET::OutlineCount(), and SHAPE_POLY_SET::PM_FAST.

◆ testModuleOnBoard()

int AR_AUTOPLACER::testModuleOnBoard ( MODULE aModule,
bool  TstOtherSide,
const wxPoint &  aOffset 
)
private

Definition at line 566 of file ar_autoplacer.cpp.

567 {
568  int side = AR_SIDE_TOP;
569  int otherside = AR_SIDE_BOTTOM;
570 
571  if( aModule->GetLayer() == B_Cu )
572  {
573  side = AR_SIDE_BOTTOM; otherside = AR_SIDE_TOP;
574  }
575 
576  EDA_RECT fpBBox = aModule->GetFootprintRect();
577  fpBBox.Move( -aOffset );
578 
579  buildFpAreas( aModule, 0 );
580 
581  int diag = //testModuleByPolygon( aModule, side, aOffset );
582  testRectangle( fpBBox, side );
583 //printf("test %p diag %d\n", aModule, diag);fflush(0);
584  if( diag != AR_FREE_CELL )
585  return diag;
586 
587  if( TstOtherSide )
588  {
589  diag = //testModuleByPolygon( aModule, otherside, aOffset );
590  testRectangle( fpBBox, otherside );
591 
592  if( diag != AR_FREE_CELL )
593  return diag;
594  }
595 
596  int marge = ( m_matrix.m_GridRouting * aModule->GetPadCount() ) / AR_GAIN;
597 
598  fpBBox.Inflate( marge );
599  return calculateKeepOutArea( fpBBox, side );
600 }
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
GetPadCount returns the number of pads.
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:43
void Move(const wxPoint &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
#define AR_SIDE_TOP
Definition: ar_matrix.h:42
int m_GridRouting
Definition: ar_matrix.h:63
EDA_RECT GetFootprintRect() const
Function GetFootprintRect() Returns the area of the module footprint excluding any text.
void buildFpAreas(MODULE *aFootprint, int aFpClearance)
#define AR_GAIN
AR_MATRIX m_matrix
unsigned int calculateKeepOutArea(const EDA_RECT &aRect, int side)
int testRectangle(const EDA_RECT &aRect, int side)
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
virtual PCB_LAYER_ID GetLayer() const
Function GetLayer returns the primary layer this item is on.
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.

References AR_FREE_CELL, AR_GAIN, AR_SIDE_BOTTOM, AR_SIDE_TOP, B_Cu, buildFpAreas(), calculateKeepOutArea(), MODULE::GetFootprintRect(), BOARD_ITEM::GetLayer(), MODULE::GetPadCount(), EDA_RECT::Inflate(), AR_MATRIX::m_GridRouting, m_matrix, EDA_RECT::Move(), and testRectangle().

Referenced by getOptimalModulePlacement().

◆ testRectangle()

int AR_AUTOPLACER::testRectangle ( const EDA_RECT aRect,
int  side 
)
private

Definition at line 440 of file ar_autoplacer.cpp.

441 {
442  EDA_RECT rect = aRect;
443 
444  rect.Inflate( m_matrix.m_GridRouting / 2 );
445 
446  wxPoint start = rect.GetOrigin();
447  wxPoint end = rect.GetEnd();
448 
449  start -= m_matrix.m_BrdBox.GetOrigin();
450  end -= m_matrix.m_BrdBox.GetOrigin();
451 
452  int row_min = start.y / m_matrix.m_GridRouting;
453  int row_max = end.y / m_matrix.m_GridRouting;
454  int col_min = start.x / m_matrix.m_GridRouting;
455  int col_max = end.x / m_matrix.m_GridRouting;
456 
457  if( start.y > row_min * m_matrix.m_GridRouting )
458  row_min++;
459 
460  if( start.x > col_min * m_matrix.m_GridRouting )
461  col_min++;
462 
463  if( row_min < 0 )
464  row_min = 0;
465 
466  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
467  row_max = m_matrix.m_Nrows - 1;
468 
469  if( col_min < 0 )
470  col_min = 0;
471 
472  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
473  col_max = m_matrix.m_Ncols - 1;
474 
475  for( int row = row_min; row <= row_max; row++ )
476  {
477  for( int col = col_min; col <= col_max; col++ )
478  {
479  unsigned int data = m_matrix.GetCell( row, col, side );
480 
481  if( ( data & CELL_IS_ZONE ) == 0 )
482  return AR_OUT_OF_BOARD;
483 
484  if( (data & CELL_IS_MODULE) )
485  return AR_OCCUIPED_BY_MODULE;
486  }
487  }
488 
489  return AR_FREE_CELL;
490 }
int m_Ncols
Definition: ar_matrix.h:65
#define CELL_IS_MODULE
Definition: ar_cell.h:37
int m_GridRouting
Definition: ar_matrix.h:63
#define CELL_IS_ZONE
Definition: ar_cell.h:40
EDA_RECT m_BrdBox
Definition: ar_matrix.h:64
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:114
const wxPoint GetOrigin() const
Definition: eda_rect.h:112
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:194
int m_Nrows
Definition: ar_matrix.h:65
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.

References AR_FREE_CELL, AR_OCCUIPED_BY_MODULE, AR_OUT_OF_BOARD, CELL_IS_MODULE, CELL_IS_ZONE, AR_MATRIX::GetCell(), EDA_RECT::GetEnd(), EDA_RECT::GetOrigin(), EDA_RECT::Inflate(), AR_MATRIX::m_BrdBox, AR_MATRIX::m_GridRouting, m_matrix, AR_MATRIX::m_Ncols, and AR_MATRIX::m_Nrows.

Referenced by testModuleOnBoard().

Member Data Documentation

◆ m_board

BOARD* AR_AUTOPLACER::m_board
private

◆ m_boardShape

SHAPE_POLY_SET AR_AUTOPLACER::m_boardShape
private

Definition at line 136 of file ar_autoplacer.h.

Referenced by fillMatrix(), and genPlacementRoutingMatrix().

◆ m_bottomFreeArea

SHAPE_POLY_SET AR_AUTOPLACER::m_bottomFreeArea
private

◆ m_connectivity

std::unique_ptr<CONNECTIVITY_DATA> AR_AUTOPLACER::m_connectivity
private

Definition at line 148 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), pickModule(), and placeModule().

◆ m_curPosition

wxPoint AR_AUTOPLACER::m_curPosition
private

Definition at line 142 of file ar_autoplacer.h.

Referenced by AutoplaceModules(), and getOptimalModulePlacement().

◆ m_fpAreaBottom

SHAPE_POLY_SET AR_AUTOPLACER::m_fpAreaBottom
private

Definition at line 138 of file ar_autoplacer.h.

Referenced by addFpBody(), addPad(), buildFpAreas(), and genModuleOnRoutingMatrix().

◆ m_fpAreaTop

SHAPE_POLY_SET AR_AUTOPLACER::m_fpAreaTop
private

◆ m_gridSize

int AR_AUTOPLACER::m_gridSize
private

Definition at line 145 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), AutoplaceModules(), and SetPlacementGrid().

◆ m_matrix

◆ m_minCost

double AR_AUTOPLACER::m_minCost
private

Definition at line 144 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), AutoplaceModules(), and getOptimalModulePlacement().

◆ m_moduleOffset

wxPoint AR_AUTOPLACER::m_moduleOffset
private

Definition at line 143 of file ar_autoplacer.h.

◆ m_overlay

std::shared_ptr<KIGFX::VIEW_OVERLAY> AR_AUTOPLACER::m_overlay
private

Definition at line 147 of file ar_autoplacer.h.

Referenced by drawPlacementRoutingMatrix(), and SetOverlay().

◆ m_progressReporter

PROGRESS_REPORTER* AR_AUTOPLACER::m_progressReporter
private

Definition at line 150 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), AutoplaceModules(), and SetProgressReporter().

◆ m_refreshCallback

std::function<int( MODULE* aModule )> AR_AUTOPLACER::m_refreshCallback
private

Definition at line 149 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), AutoplaceModules(), and SetRefreshCallback().

◆ m_topFreeArea

SHAPE_POLY_SET AR_AUTOPLACER::m_topFreeArea
private

The documentation for this class was generated from the following files: