KiCad PCB EDA Suite
AR_AUTOPLACER Class Reference

#include <ar_autoplacer.h>

Public Member Functions

 AR_AUTOPLACER (BOARD *aBoard)
 
AR_RESULT AutoplaceFootprints (std::vector< FOOTPRINT * > &aFootprints, BOARD_COMMIT *aCommit, bool aPlaceOffboardModules=false)
 
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(FOOTPRINT *aFootprint)> aCallback)
 Callback 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 rotateFootprint (FOOTPRINT *aFootprint, double angle, bool incremental)
 
int genPlacementRoutingMatrix ()
 
bool fillMatrix ()
 Fill m_matrix cells from m_boardShape. More...
 
void genModuleOnRoutingMatrix (FOOTPRINT *aFootprint)
 
int testRectangle (const EDA_RECT &aRect, int side)
 
unsigned int calculateKeepOutArea (const EDA_RECT &aRect, int side)
 
int testFootprintOnBoard (FOOTPRINT *aFootprint, bool TstOtherSide, const wxPoint &aOffset)
 
int getOptimalFPPlacement (FOOTPRINT *aFootprint)
 
double computePlacementRatsnestCost (FOOTPRINT *aFootprint, const wxPoint &aOffset)
 
FOOTPRINTpickFootprint ()
 Find the "best" footprint place. More...
 
void placeFootprint (FOOTPRINT *aFootprint, bool aDoNotRecreateRatsnest, const wxPoint &aPos)
 
const PADnearestPad (FOOTPRINT *aRefFP, PAD *aRefPad, const wxPoint &aOffset)
 
void addFpBody (const wxPoint &aStart, const wxPoint &aEnd, LSET aLayerMask)
 
void addPad (PAD *aPad, int aClearance)
 
void buildFpAreas (FOOTPRINT *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
 
double m_minCost
 
int m_gridSize
 
std::shared_ptr< KIGFX::VIEW_OVERLAYm_overlay
 
std::unique_ptr< CONNECTIVITY_DATAm_connectivity
 
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback
 
PROGRESS_REPORTERm_progressReporter
 

Detailed Description

Definition at line 57 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 = std::make_unique<CONNECTIVITY_DATA>( );
83 
84  for( FOOTPRINT* footprint : m_board->Footprints() )
85  m_connectivity->Add( footprint );
86 
88  m_progressReporter = nullptr;
89  m_refreshCallback = nullptr;
90  m_minCost = 0.0;
91 }
PROGRESS_REPORTER * m_progressReporter
FOOTPRINTS & Footprints()
Definition: board.h:233
#define STEP_AR_MM
static constexpr int Millimeter2iu(double mm)
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References BOARD::Footprints(), m_board, m_connectivity, m_gridSize, m_minCost, m_progressReporter, m_refreshCallback, Millimeter2iu(), and STEP_AR_MM.

Member Function Documentation

◆ addFpBody()

void AR_AUTOPLACER::addFpBody ( const wxPoint &  aStart,
const 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 
300  if( aLayerMask[ B_Cu ] )
301  {
303  m_fpAreaBottom.Append( aStart.x, aStart.y );
304  m_fpAreaBottom.Append( aEnd.x, aStart.y );
305  m_fpAreaBottom.Append( aEnd.x, aEnd.y );
306  m_fpAreaBottom.Append( aStart.x, aEnd.y );
307  }
308 }
SHAPE_POLY_SET m_fpAreaBottom
SHAPE_POLY_SET m_fpAreaTop
int NewOutline()
Creates a new hole in a given outline.
Definition: layer_ids.h:71
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

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 ( PAD aPad,
int  aClearance 
)
private

Definition at line 311 of file ar_autoplacer.cpp.

312 {
313  // Add a polygonal shape (rectangle) to m_fpAreaFront and/or m_fpAreaBack
314  EDA_RECT bbox = aPad->GetBoundingBox();
315  bbox.Inflate( aClearance );
316 
317  if( aPad->IsOnLayer( F_Cu ) )
318  {
320  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetTop() );
321  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetTop() );
322  m_fpAreaTop.Append( bbox.GetRight(), bbox.GetBottom() );
323  m_fpAreaTop.Append( bbox.GetLeft(), bbox.GetBottom() );
324  }
325 
326  if( aPad->IsOnLayer( B_Cu ) )
327  {
329  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetTop() );
330  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetTop() );
331  m_fpAreaBottom.Append( bbox.GetRight(), bbox.GetBottom() );
332  m_fpAreaBottom.Append( bbox.GetLeft(), bbox.GetBottom() );
333  }
334 }
int GetTop() const
Definition: eda_rect.h:113
int GetLeft() const
Definition: eda_rect.h:112
bool IsOnLayer(PCB_LAYER_ID aLayer) const override
Test to see if this object is on the given layer.
Definition: pad.h:567
int GetBottom() const
Definition: eda_rect.h:114
SHAPE_POLY_SET m_fpAreaBottom
int GetRight() const
Definition: eda_rect.h:111
const EDA_RECT GetBoundingBox() const override
The bounding box is cached, so this will be efficient most of the time.
Definition: pad.cpp:534
SHAPE_POLY_SET m_fpAreaTop
int NewOutline()
Creates a new hole in a given outline.
Definition: layer_ids.h:71
Handle the component boundary box.
Definition: eda_rect.h:42
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...

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

Referenced by buildFpAreas().

◆ AutoplaceFootprints()

AR_RESULT AR_AUTOPLACER::AutoplaceFootprints ( std::vector< FOOTPRINT * > &  aFootprints,
BOARD_COMMIT aCommit,
bool  aPlaceOffboardModules = false 
)

Definition at line 861 of file ar_autoplacer.cpp.

864 {
865  wxPoint memopos;
866  int error;
867  bool cancelled = false;
868 
869  memopos = m_curPosition;
870 
871  m_matrix.m_GridRouting = m_gridSize; //(int) m_frame->GetScreen()->GetGridSize().x;
872 
873  // Ensure Board.m_GridRouting has a reasonable value:
874  if( m_matrix.m_GridRouting < Millimeter2iu( 0.25 ) )
876 
877  // Compute footprint parameters used in autoplace
878  if( genPlacementRoutingMatrix( ) == 0 )
879  return AR_FAILURE;
880 
881  int placedCount = 0;
882 
883  for( FOOTPRINT* footprint : m_board->Footprints() )
884  footprint->SetNeedsPlaced( false );
885 
886  std::vector<FOOTPRINT*> offboardMods;
887 
888  if( aPlaceOffboardModules )
889  {
890  for( FOOTPRINT* footprint : m_board->Footprints() )
891  {
892  if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
893  offboardMods.push_back( footprint );
894  }
895  }
896 
897  for( FOOTPRINT* footprint : aFootprints )
898  {
899  footprint->SetNeedsPlaced( true );
900  aCommit->Modify( footprint );
901  }
902 
903  for( FOOTPRINT* footprint : offboardMods )
904  {
905  footprint->SetNeedsPlaced( true );
906  aCommit->Modify( footprint );
907  }
908 
909  for( FOOTPRINT* footprint : m_board->Footprints() )
910  {
911  if( footprint->NeedsPlaced() ) // Erase from screen
912  placedCount++;
913  else
914  genModuleOnRoutingMatrix( footprint );
915  }
916 
917 
918  int cnt = 0;
919  wxString msg;
920 
921  if( m_progressReporter )
922  {
923  m_progressReporter->Report( _( "Autoplacing components..." ) );
924  m_progressReporter->SetMaxProgress( placedCount );
925  }
926 
928 
929  if( m_refreshCallback )
930  m_refreshCallback( nullptr );
931 
932  FOOTPRINT* footprint;
933 
934  while( ( footprint = pickFootprint() ) != nullptr )
935  {
936  // Display some info about activity, footprint placement can take a while:
937  //m_frame->SetStatusText( msg );
938 
939  if( m_progressReporter )
940  m_progressReporter->SetTitle( wxString::Format( _( "Autoplacing %s" ),
941  footprint->GetReference() ) );
942 
943  double initialOrient = footprint->GetOrientation();
944 
945  error = getOptimalFPPlacement( footprint );
946  double bestScore = m_minCost;
947  double bestRotation = 0.0;
948  int rotAllowed;
949 
950  if( error == AR_ABORT_PLACEMENT )
951  goto end_of_tst;
952 
953  // Try orientations 90, 180, 270 degrees from initial orientation
954  rotAllowed = footprint->GetPlacementCost180();
955 
956  if( rotAllowed != 0 )
957  {
958  rotateFootprint( footprint, 1800.0, true );
959  error = getOptimalFPPlacement( footprint );
960  m_minCost *= OrientationPenalty[rotAllowed];
961 
962  if( bestScore > m_minCost ) // This orientation is better.
963  {
964  bestScore = m_minCost;
965  bestRotation = 1800.0;
966  }
967  else
968  {
969  rotateFootprint( footprint, initialOrient, false );
970  }
971 
972  if( error == AR_ABORT_PLACEMENT )
973  goto end_of_tst;
974  }
975 
976  // Determine if the best orientation of a footprint is 90.
977  rotAllowed = footprint->GetPlacementCost90();
978 
979  if( rotAllowed != 0 )
980  {
981  rotateFootprint( footprint, 900.0, true );
982  error = getOptimalFPPlacement( footprint );
983  m_minCost *= OrientationPenalty[rotAllowed];
984 
985  if( bestScore > m_minCost ) // This orientation is better.
986  {
987  bestScore = m_minCost;
988  bestRotation = 900.0;
989  }
990  else
991  {
992  rotateFootprint( footprint, initialOrient, false );
993  }
994 
995  if( error == AR_ABORT_PLACEMENT )
996  goto end_of_tst;
997  }
998 
999  // Determine if the best orientation of a footprint is -90.
1000  if( rotAllowed != 0 )
1001  {
1002  rotateFootprint( footprint, 2700.0, true );
1003  error = getOptimalFPPlacement( footprint );
1004  m_minCost *= OrientationPenalty[rotAllowed];
1005 
1006  if( bestScore > m_minCost ) // This orientation is better.
1007  {
1008  bestScore = m_minCost;
1009  bestRotation = 2700.0;
1010  }
1011  else
1012  {
1013  rotateFootprint( footprint, initialOrient, false );
1014  }
1015 
1016  if( error == AR_ABORT_PLACEMENT )
1017  goto end_of_tst;
1018  }
1019 
1020 end_of_tst:
1021 
1022  if( error == AR_ABORT_PLACEMENT )
1023  break;
1024 
1025  bestRotation += initialOrient;
1026 
1027  if( bestRotation != footprint->GetOrientation() )
1028  {
1029  rotateFootprint( footprint, bestRotation, false );
1030  }
1031 
1032  // Place footprint.
1033  placeFootprint( footprint, true, m_curPosition );
1034 
1035  genModuleOnRoutingMatrix( footprint );
1036  footprint->SetIsPlaced( true );
1037  footprint->SetNeedsPlaced( false );
1039 
1040  if( m_refreshCallback )
1041  m_refreshCallback( footprint );
1042 
1043  if( m_progressReporter )
1044  {
1046 
1047  if ( !m_progressReporter->KeepRefreshing( false ) )
1048  {
1049  cancelled = true;
1050  break;
1051  }
1052  }
1053 
1054  cnt++;
1055  }
1056 
1057  m_curPosition = memopos;
1058 
1060 
1061  return cancelled ? AR_CANCELLED : AR_COMPLETED;
1062 }
COMMIT & Modify(EDA_ITEM *aItem)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
virtual void SetMaxProgress(int aMaxProgress)=0
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).
virtual void Report(const wxString &aMessage)=0
Display aMessage in the progress bar dialog.
PROGRESS_REPORTER * m_progressReporter
void SetNeedsPlaced(bool needsPlaced)
Definition: footprint.h:321
int getOptimalFPPlacement(FOOTPRINT *aFootprint)
int GetPlacementCost180() const
Definition: footprint.h:578
void SetIsPlaced(bool isPlaced)
Definition: footprint.h:312
int m_GridRouting
Definition: ar_matrix.h:142
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
double GetOrientation() const
Definition: footprint.h:190
FOOTPRINT * pickFootprint()
Find the "best" footprint place.
void placeFootprint(FOOTPRINT *aFootprint, bool aDoNotRecreateRatsnest, const wxPoint &aPos)
virtual void AdvanceProgress()=0
Increment the progress bar length (inside the current virtual zone).
virtual void SetTitle(const wxString &aTitle)=0
Change the title displayed on the window caption.
bool Contains(const wxPoint &aPoint) const
Definition: eda_rect.cpp:57
AR_MATRIX m_matrix
void drawPlacementRoutingMatrix()
int genPlacementRoutingMatrix()
FOOTPRINTS & Footprints()
Definition: board.h:233
#define AR_ABORT_PLACEMENT
const wxString & GetReference() const
Definition: footprint.h:463
#define _(s)
void genModuleOnRoutingMatrix(FOOTPRINT *aFootprint)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
void rotateFootprint(FOOTPRINT *aFootprint, double angle, bool incremental)
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:128
static const double OrientationPenalty[11]
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
int GetPlacementCost90() const
Definition: footprint.h:581
wxPoint m_curPosition
static constexpr int Millimeter2iu(double mm)
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback

References _, PROGRESS_REPORTER::AdvanceProgress(), AR_ABORT_PLACEMENT, AR_CANCELLED, AR_COMPLETED, AR_FAILURE, EDA_RECT::Contains(), drawPlacementRoutingMatrix(), BOARD::Footprints(), Format(), genModuleOnRoutingMatrix(), genPlacementRoutingMatrix(), getOptimalFPPlacement(), FOOTPRINT::GetOrientation(), FOOTPRINT::GetPlacementCost180(), FOOTPRINT::GetPlacementCost90(), FOOTPRINT::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, Millimeter2iu(), COMMIT::Modify(), OrientationPenalty, pickFootprint(), placeFootprint(), PROGRESS_REPORTER::Report(), rotateFootprint(), FOOTPRINT::SetIsPlaced(), PROGRESS_REPORTER::SetMaxProgress(), FOOTPRINT::SetNeedsPlaced(), PROGRESS_REPORTER::SetTitle(), and AR_MATRIX::UnInitRoutingMatrix().

Referenced by AUTOPLACE_TOOL::autoplace().

◆ buildFpAreas()

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

Definition at line 337 of file ar_autoplacer.cpp.

338 {
341 
342  aFootprint->BuildPolyCourtyards();
343  m_fpAreaTop = aFootprint->GetPolyCourtyard( F_CrtYd );
344  m_fpAreaBottom = aFootprint->GetPolyCourtyard( B_CrtYd );
345 
346  LSET layerMask;
347 
348  if( aFootprint->GetLayer() == F_Cu )
349  layerMask.set( F_Cu );
350 
351  if( aFootprint->GetLayer() == B_Cu )
352  layerMask.set( B_Cu );
353 
354  EDA_RECT fpBBox = aFootprint->GetBoundingBox();
355 
356  fpBBox.Inflate( ( m_matrix.m_GridRouting / 2 ) + aFpClearance );
357 
358  // Add a minimal area to the fp area:
359  addFpBody( fpBBox.GetOrigin(), fpBBox.GetEnd(), layerMask );
360 
361  // Trace pads + clearance areas.
362  for( PAD* pad : aFootprint->Pads() )
363  {
364  int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
365  addPad( pad, margin );
366  }
367 }
void BuildPolyCourtyards(OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
Build complex polygons of the courtyard areas from graphic items on the courtyard layers.
Definition: footprint.cpp:2022
int m_GridRouting
Definition: ar_matrix.h:142
PADS & Pads()
Definition: footprint.h:168
AR_MATRIX m_matrix
void addFpBody(const wxPoint &aStart, const wxPoint &aEnd, LSET aLayerMask)
const wxPoint GetEnd() const
Definition: eda_rect.h:103
SHAPE_POLY_SET m_fpAreaBottom
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:504
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
const SHAPE_POLY_SET & GetPolyCourtyard(PCB_LAYER_ID aLayer) const
Used in DRC to test the courtyard area (a complex polygon).
Definition: footprint.h:695
SHAPE_POLY_SET m_fpAreaTop
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:718
Definition: layer_ids.h:71
Handle the component boundary box.
Definition: eda_rect.h:42
Definition: pad.h:57
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:140
void addPad(PAD *aPad, int aClearance)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

References addFpBody(), addPad(), B_CrtYd, B_Cu, FOOTPRINT::BuildPolyCourtyards(), F_CrtYd, F_Cu, FOOTPRINT::GetBoundingBox(), EDA_RECT::GetEnd(), BOARD_ITEM::GetLayer(), EDA_RECT::GetOrigin(), FOOTPRINT::GetPolyCourtyard(), EDA_RECT::Inflate(), m_fpAreaBottom, m_fpAreaTop, AR_MATRIX::m_GridRouting, m_matrix, pad, FOOTPRINT::Pads(), and SHAPE_POLY_SET::RemoveAllContours().

Referenced by genModuleOnRoutingMatrix(), and testFootprintOnBoard().

◆ calculateKeepOutArea()

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

Definition at line 488 of file ar_autoplacer.cpp.

489 {
490  wxPoint start = aRect.GetOrigin();
491  wxPoint end = aRect.GetEnd();
492 
493  start -= m_matrix.m_BrdBox.GetOrigin();
494  end -= m_matrix.m_BrdBox.GetOrigin();
495 
496  int row_min = start.y / m_matrix.m_GridRouting;
497  int row_max = end.y / m_matrix.m_GridRouting;
498  int col_min = start.x / m_matrix.m_GridRouting;
499  int col_max = end.x / m_matrix.m_GridRouting;
500 
501  if( start.y > row_min * m_matrix.m_GridRouting )
502  row_min++;
503 
504  if( start.x > col_min * m_matrix.m_GridRouting )
505  col_min++;
506 
507  if( row_min < 0 )
508  row_min = 0;
509 
510  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
511  row_max = m_matrix.m_Nrows - 1;
512 
513  if( col_min < 0 )
514  col_min = 0;
515 
516  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
517  col_max = m_matrix.m_Ncols - 1;
518 
519  unsigned int keepOutCost = 0;
520 
521  for( int row = row_min; row <= row_max; row++ )
522  {
523  for( int col = col_min; col <= col_max; col++ )
524  {
525  // m_matrix.GetDist returns the "cost" of the cell
526  // at position (row, col)
527  // in autoplace this is the cost of the cell, if it is
528  // inside aRect
529  keepOutCost += m_matrix.GetDist( row, col, side );
530  }
531  }
532 
533  return keepOutCost;
534 }
int m_Ncols
Definition: ar_matrix.h:144
int m_GridRouting
Definition: ar_matrix.h:142
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:103
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
int m_Nrows
Definition: ar_matrix.h:144
DIST_CELL GetDist(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:234

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 testFootprintOnBoard().

◆ computePlacementRatsnestCost()

double AR_AUTOPLACER::computePlacementRatsnestCost ( FOOTPRINT aFootprint,
const wxPoint &  aOffset 
)
private

Definition at line 700 of file ar_autoplacer.cpp.

701 {
702  double curr_cost;
703  VECTOR2I start; // start point of a ratsnest
704  VECTOR2I end; // end point of a ratsnest
705  int dx, dy;
706 
707  curr_cost = 0;
708 
709  for( PAD* pad : aFootprint->Pads() )
710  {
711  const PAD* nearest = nearestPad( aFootprint, pad, aOffset );
712 
713  if( !nearest )
714  continue;
715 
716  start = VECTOR2I( pad->GetPosition() ) - VECTOR2I(aOffset);
717  end = VECTOR2I( nearest->GetPosition() );
718 
719  //m_overlay->SetIsStroke( true );
720  //m_overlay->SetStrokeColor( COLOR4D(0.0, 1.0, 0.0, 1.0) );
721  //m_overlay->Line( start, end );
722 
723  // Cost of the ratsnest.
724  dx = end.x - start.x;
725  dy = end.y - start.y;
726 
727  dx = abs( dx );
728  dy = abs( dy );
729 
730  // ttry to have always dx >= dy to calculate the cost of the ratsnest
731  if( dx < dy )
732  std::swap( dx, dy );
733 
734  // Cost of the connection = length + penalty due to the slope
735  // dx is the biggest length relative to the X or Y axis
736  // the penalty is max for 45 degrees ratsnests,
737  // and 0 for horizontal or vertical ratsnests.
738  // For Horizontal and Vertical ratsnests, dy = 0;
739  double conn_cost = hypot( dx, dy * 2.0 );
740  curr_cost += conn_cost; // Total cost = sum of costs of each connection
741  }
742 
743  return curr_cost;
744 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
PADS & Pads()
Definition: footprint.h:168
const PAD * nearestPad(FOOTPRINT *aRefFP, PAD *aRefPad, const wxPoint &aOffset)
wxPoint GetPosition() const override
Definition: pad.h:178
Definition: pad.h:57

References PAD::GetPosition(), nearestPad(), pad, FOOTPRINT::Pads(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by getOptimalFPPlacement().

◆ drawPlacementRoutingMatrix()

void AR_AUTOPLACER::drawPlacementRoutingMatrix ( )
private

Definition at line 830 of file ar_autoplacer.cpp.

831 {
832  // Draw the board free area
833  m_overlay->Clear();
834  m_overlay->SetIsFill( true );
835  m_overlay->SetIsStroke( false );
836 
837  SHAPE_POLY_SET freeArea = m_topFreeArea;
838  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
839 
840  // Draw the free polygon areas, top side:
841  if( freeArea.OutlineCount() > 0 )
842  {
843  m_overlay->SetIsFill( true );
844  m_overlay->SetIsStroke( false );
845  m_overlay->SetFillColor( COLOR4D(0.7, 0.0, 0.1, 0.2) );
846  m_overlay->Polygon( freeArea );
847  }
848 
849  freeArea = m_bottomFreeArea;
850  freeArea.Fracture( SHAPE_POLY_SET::PM_FAST );
851 
852  // Draw the free polygon areas, bottom side:
853  if( freeArea.OutlineCount() > 0 )
854  {
855  m_overlay->SetFillColor( COLOR4D(0.0, 0.7, 0.0, 0.2) );
856  m_overlay->Polygon( freeArea );
857  }
858 }
SHAPE_POLY_SET m_topFreeArea
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Represent a set of closed polygons.
SHAPE_POLY_SET m_bottomFreeArea
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay
A color representation with 4 components: red, green, blue, alpha.
Definition: color4d.h:103

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

Referenced by AutoplaceFootprints().

◆ fillMatrix()

bool AR_AUTOPLACER::fillMatrix ( )
private

Fill m_matrix cells from m_boardShape.

Cells inside m_boardShape are set to CELL_IS_ZONE.

Definition at line 159 of file ar_autoplacer.cpp.

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

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 ( FOOTPRINT aFootprint)
private

Definition at line 370 of file ar_autoplacer.cpp.

371 {
372  int ox, oy, fx, fy;
373  LSET layerMask;
374  EDA_RECT fpBBox = Module->GetBoundingBox();
375 
376  fpBBox.Inflate( m_matrix.m_GridRouting / 2 );
377  ox = fpBBox.GetX();
378  fx = fpBBox.GetRight();
379  oy = fpBBox.GetY();
380  fy = fpBBox.GetBottom();
381 
382  if( ox < m_matrix.m_BrdBox.GetX() )
383  ox = m_matrix.m_BrdBox.GetX();
384 
385  if( ox > m_matrix.m_BrdBox.GetRight() )
386  ox = m_matrix.m_BrdBox.GetRight();
387 
388  if( fx < m_matrix.m_BrdBox.GetX() )
389  fx = m_matrix.m_BrdBox.GetX();
390 
391  if( fx > m_matrix.m_BrdBox.GetRight() )
392  fx = m_matrix.m_BrdBox.GetRight();
393 
394  if( oy < m_matrix.m_BrdBox.GetY() )
395  oy = m_matrix.m_BrdBox.GetY();
396 
397  if( oy > m_matrix.m_BrdBox.GetBottom() )
398  oy = m_matrix.m_BrdBox.GetBottom();
399 
400  if( fy < m_matrix.m_BrdBox.GetY() )
401  fy = m_matrix.m_BrdBox.GetY();
402 
403  if( fy > m_matrix.m_BrdBox.GetBottom() )
404  fy = m_matrix.m_BrdBox.GetBottom();
405 
406  if( Module->GetLayer() == F_Cu )
407  layerMask.set( F_Cu );
408 
409  if( Module->GetLayer() == B_Cu )
410  layerMask.set( B_Cu );
411 
412  m_matrix.TraceFilledRectangle( ox, oy, fx, fy, layerMask,
414 
415  // Trace pads + clearance areas.
416  for( PAD* pad : Module->Pads() )
417  {
418  int margin = (m_matrix.m_GridRouting / 2) + pad->GetOwnClearance( pad->GetLayer() );
420  }
421 
422  // Trace clearance.
423  int margin = ( m_matrix.m_GridRouting * Module->GetPadCount() ) / AR_GAIN;
424  m_matrix.CreateKeepOutRectangle( ox, oy, fx, fy, margin, AR_KEEPOUT_MARGIN , layerMask );
425 
426  // Build the footprint courtyard
427  buildFpAreas( Module, margin );
428 
429  // Substract the shape to free areas
432 }
SHAPE_POLY_SET m_topFreeArea
int GetX() const
Definition: eda_rect.h:98
int m_GridRouting
Definition: ar_matrix.h:142
void TraceFilledRectangle(int ux0, int uy0, int ux1, int uy1, double angle, LSET aLayerMask, int color, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:615
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
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:807
#define AR_GAIN
#define AR_KEEPOUT_MARGIN
int GetBottom() const
Definition: eda_rect.h:114
void PlacePad(PAD *aPad, int color, int marge, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:912
AR_MATRIX m_matrix
SHAPE_POLY_SET m_fpAreaBottom
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:504
int GetRight() const
Definition: eda_rect.h:111
SHAPE_POLY_SET m_bottomFreeArea
SHAPE_POLY_SET m_fpAreaTop
#define CELL_IS_MODULE
Definition: layer_ids.h:71
void buildFpAreas(FOOTPRINT *aFootprint, int aFpClearance)
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:99
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
Definition: pad.h:57
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

References AR_GAIN, AR_KEEPOUT_MARGIN, B_Cu, SHAPE_POLY_SET::BooleanSubtract(), buildFpAreas(), CELL_IS_MODULE, AR_MATRIX::CreateKeepOutRectangle(), F_Cu, EDA_RECT::GetBottom(), FOOTPRINT::GetBoundingBox(), BOARD_ITEM::GetLayer(), FOOTPRINT::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, pad, FOOTPRINT::Pads(), AR_MATRIX::PlacePad(), SHAPE_POLY_SET::PM_FAST, AR_MATRIX::TraceFilledRectangle(), and AR_MATRIX::WRITE_OR_CELL.

Referenced by AutoplaceFootprints().

◆ genPlacementRoutingMatrix()

int AR_AUTOPLACER::genPlacementRoutingMatrix ( )
private

Definition at line 105 of file ar_autoplacer.cpp.

106 {
108 
110 
111  if( bbox.GetWidth() == 0 || bbox.GetHeight() == 0 )
112  return 0;
113 
114  // Build the board shape
118 
119  m_matrix.ComputeMatrixSize( bbox );
120  int nbCells = m_matrix.m_Ncols * m_matrix.m_Nrows;
121 
122  // Choose the number of board sides.
127 
128  // Fill (mark) the cells inside the board:
129  fillMatrix();
130 
131  // Other obstacles can be added here:
132  for( auto drawing : m_board->Drawings() )
133  {
134  switch( drawing->Type() )
135  {
136  case PCB_SHAPE_T:
137  if( drawing->GetLayer() != Edge_Cuts )
138  {
141  }
142 
143  break;
144 
145  default:
146  break;
147  }
148  }
149 
150  // Initialize top layer. to the same value as the bottom layer
153  nbCells * sizeof(AR_MATRIX::MATRIX_CELL) );
154 
155  return 1;
156 }
SHAPE_POLY_SET m_topFreeArea
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:42
int InitRoutingMatrix()
Initialize the data structures.
Definition: ar_matrix.cpp:91
bool GetBoardPolygonOutlines(SHAPE_POLY_SET &aOutlines, OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
Extract the board outlines and build a closed polygon from lines, arcs and circle items on edge cut l...
Definition: board.cpp:1880
#define CELL_IS_HOLE
#define AR_SIDE_TOP
Definition: ar_matrix.h:41
int m_Ncols
Definition: ar_matrix.h:144
const EDA_RECT GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:737
int m_GridRouting
Definition: ar_matrix.h:142
int GetWidth() const
Definition: eda_rect.h:109
AR_MATRIX m_matrix
PCB_LAYER_ID m_routeLayerTop
Definition: ar_matrix.h:148
#define CELL_IS_EDGE
SHAPE_POLY_SET m_boardShape
int m_Nrows
Definition: ar_matrix.h:144
MATRIX_CELL * m_BoardSide[AR_MAX_ROUTING_LAYERS_COUNT]
Definition: ar_matrix.h:138
void TraceSegmentPcb(PCB_SHAPE *aShape, int aColor, int aMargin, AR_MATRIX::CELL_OP op_logic)
Definition: ar_matrix.cpp:765
SHAPE_POLY_SET m_bottomFreeArea
int GetHeight() const
Definition: eda_rect.h:110
bool fillMatrix()
Fill m_matrix cells from m_boardShape.
void UnInitRoutingMatrix()
Definition: ar_matrix.cpp:128
int m_RoutingLayersCount
Definition: ar_matrix.h:141
Definition: layer_ids.h:71
Handle the component boundary box.
Definition: eda_rect.h:42
unsigned char MATRIX_CELL
Definition: ar_matrix.h:50
bool ComputeMatrixSize(const EDA_RECT &aBoundingBox)
Calculate the number of rows and columns of dimensions of aPcb for routing and automatic calculation ...
Definition: ar_matrix.cpp:61
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:90
DRAWINGS & Drawings()
Definition: board.h:236
PCB_LAYER_ID m_routeLayerBottom
Definition: ar_matrix.h:149

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_SHAPE_T, AR_MATRIX::TraceSegmentPcb(), AR_MATRIX::UnInitRoutingMatrix(), and AR_MATRIX::WRITE_CELL.

Referenced by AutoplaceFootprints().

◆ getOptimalFPPlacement()

int AR_AUTOPLACER::getOptimalFPPlacement ( FOOTPRINT aFootprint)
private

Definition at line 575 of file ar_autoplacer.cpp.

576 {
577  int error = 1;
578  wxPoint lastPosOK;
579  double min_cost, curr_cost, Score;
580  bool testOtherSide;
581 
582  lastPosOK = m_matrix.m_BrdBox.GetOrigin();
583 
584  wxPoint fpPos = aFootprint->GetPosition();
585  EDA_RECT fpBBox = aFootprint->GetBoundingBox( false, false );
586 
587  // Move fpBBox to have the footprint position at (0,0)
588  fpBBox.Move( -fpPos );
589  wxPoint fpBBoxOrg = fpBBox.GetOrigin();
590 
591  // Calculate the limit of the footprint position, relative to the routing matrix area
592  wxPoint xylimit = m_matrix.m_BrdBox.GetEnd() - fpBBox.GetEnd();
593 
594  wxPoint initialPos = m_matrix.m_BrdBox.GetOrigin() - fpBBoxOrg;
595 
596  // Stay on grid.
597  initialPos.x -= initialPos.x % m_matrix.m_GridRouting;
598  initialPos.y -= initialPos.y % m_matrix.m_GridRouting;
599 
600  m_curPosition = initialPos;
601  wxPoint fpOffset = fpPos - m_curPosition;
602 
603  // Examine pads, and set testOtherSide to true if a footprint has at least 1 pad through.
604  testOtherSide = false;
605 
607  {
608  LSET other( aFootprint->GetLayer() == B_Cu ? F_Cu : B_Cu );
609 
610  for( PAD* pad : aFootprint->Pads() )
611  {
612  if( !( pad->GetLayerSet() & other ).any() )
613  continue;
614 
615  testOtherSide = true;
616  break;
617  }
618  }
619 
620  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
621 
622  min_cost = -1.0;
623 // m_frame->SetStatusText( wxT( "Score ??, pos ??" ) );
624 
625 
626  for( ; m_curPosition.x < xylimit.x; m_curPosition.x += m_matrix.m_GridRouting )
627  {
628  m_curPosition.y = initialPos.y;
629 
630  for( ; m_curPosition.y < xylimit.y; m_curPosition.y += m_matrix.m_GridRouting )
631  {
632 
633  fpBBox.SetOrigin( fpBBoxOrg + m_curPosition );
634  fpOffset = fpPos - m_curPosition;
635  int keepOutCost = testFootprintOnBoard( aFootprint, testOtherSide, fpOffset );
636 
637  if( keepOutCost >= 0 ) // i.e. if the footprint can be put here
638  {
639  error = 0;
640  // m_frame->build_ratsnest_footprint( aFootprint ); // fixme
641  curr_cost = computePlacementRatsnestCost( aFootprint, fpOffset );
642  Score = curr_cost + keepOutCost;
643 
644  if( (min_cost >= Score ) || (min_cost < 0 ) )
645  {
646  lastPosOK = m_curPosition;
647  min_cost = Score;
648  wxString msg;
649 /* msg.Printf( wxT( "Score %g, pos %s, %s" ),
650  min_cost,
651  GetChars( ::CoordinateToString( LastPosOK.x ) ),
652  GetChars( ::CoordinateToString( LastPosOK.y ) ) );
653  m_frame->SetStatusText( msg );*/
654  }
655  }
656  }
657  }
658 
659  // Regeneration of the modified variable.
660  m_curPosition = lastPosOK;
661 
662  m_minCost = min_cost;
663  return error;
664 }
void Move(const wxPoint &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: eda_rect.cpp:51
int m_GridRouting
Definition: ar_matrix.h:142
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:121
PADS & Pads()
Definition: footprint.h:168
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:103
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:504
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
int testFootprintOnBoard(FOOTPRINT *aFootprint, bool TstOtherSide, const wxPoint &aOffset)
int m_RoutingLayersCount
Definition: ar_matrix.h:141
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:718
Definition: layer_ids.h:71
Handle the component boundary box.
Definition: eda_rect.h:42
wxPoint GetPosition() const override
Definition: footprint.h:186
wxPoint m_curPosition
Definition: pad.h:57
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:140
double computePlacementRatsnestCost(FOOTPRINT *aFootprint, const wxPoint &aOffset)

References B_Cu, computePlacementRatsnestCost(), F_Cu, FOOTPRINT::GetBoundingBox(), EDA_RECT::GetEnd(), BOARD_ITEM::GetLayer(), EDA_RECT::GetOrigin(), FOOTPRINT::GetPosition(), AR_MATRIX::m_BrdBox, m_curPosition, AR_MATRIX::m_GridRouting, m_matrix, m_minCost, AR_MATRIX::m_RoutingLayersCount, EDA_RECT::Move(), pad, FOOTPRINT::Pads(), EDA_RECT::SetOrigin(), and testFootprintOnBoard().

Referenced by AutoplaceFootprints().

◆ nearestPad()

const PAD * AR_AUTOPLACER::nearestPad ( FOOTPRINT aRefFP,
PAD aRefPad,
const wxPoint &  aOffset 
)
private

Definition at line 667 of file ar_autoplacer.cpp.

668 {
669  const PAD* nearest = nullptr;
670  int64_t nearestDist = INT64_MAX;
671 
672  for( FOOTPRINT* footprint : m_board->Footprints() )
673  {
674  if ( footprint == aRefFP )
675  continue;
676 
677  if( !m_matrix.m_BrdBox.Contains( footprint->GetPosition() ) )
678  continue;
679 
680  for( PAD* pad: footprint->Pads() )
681  {
682  if( pad->GetNetCode() != aRefPad->GetNetCode() || pad->GetNetCode() <= 0 )
683  continue;
684 
685  auto dist = ( VECTOR2I( aRefPad->GetPosition() - aOffset ) -
686  VECTOR2I( pad->GetPosition() ) ).EuclideanNorm();
687 
688  if ( dist < nearestDist )
689  {
690  nearestDist = dist;
691  nearest = pad;
692  }
693  }
694  }
695 
696  return nearest;
697 }
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
bool Contains(const wxPoint &aPoint) const
Definition: eda_rect.cpp:57
AR_MATRIX m_matrix
FOOTPRINTS & Footprints()
Definition: board.h:233
wxPoint GetPosition() const override
Definition: pad.h:178
Definition: pad.h:57

References EDA_RECT::Contains(), BOARD::Footprints(), BOARD_CONNECTED_ITEM::GetNetCode(), PAD::GetPosition(), m_board, AR_MATRIX::m_BrdBox, m_matrix, and pad.

Referenced by computePlacementRatsnestCost().

◆ pickFootprint()

FOOTPRINT * AR_AUTOPLACER::pickFootprint ( )
private

Find the "best" footprint place.

The criteria are:

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

Definition at line 769 of file ar_autoplacer.cpp.

770 {
771  std::vector<FOOTPRINT*> fpList;
772 
773 
774  for( FOOTPRINT* footprint : m_board->Footprints() )
775  fpList.push_back( footprint );
776 
777  sort( fpList.begin(), fpList.end(), sortFootprintsByComplexity );
778 
779  for( unsigned kk = 0; kk < fpList.size(); kk++ )
780  {
781  FOOTPRINT* footprint = fpList[kk];
782  footprint->SetFlag( 0 );
783 
784  if( !footprint->NeedsPlaced() )
785  continue;
786 
787  m_connectivity->Update( footprint );
788  }
789 
790  m_connectivity->RecalculateRatsnest();
791 
792  for( unsigned kk = 0; kk < fpList.size(); kk++ )
793  {
794  FOOTPRINT* footprint = fpList[kk];
795 
796  auto edges = m_connectivity->GetRatsnestForComponent( footprint, true );
797 
798  footprint->SetFlag( edges.size() ) ;
799  }
800 
801  sort( fpList.begin(), fpList.end(), sortFootprintsByRatsnestSize );
802 
803  // Search for "best" footprint.
804  FOOTPRINT* bestFootprint = nullptr;
805  FOOTPRINT* altFootprint = nullptr;
806 
807  for( unsigned ii = 0; ii < fpList.size(); ii++ )
808  {
809  FOOTPRINT* footprint = fpList[ii];
810 
811  if( !footprint->NeedsPlaced() )
812  continue;
813 
814  altFootprint = footprint;
815 
816  if( footprint->GetFlag() == 0 )
817  continue;
818 
819  bestFootprint = footprint;
820  break;
821  }
822 
823  if( bestFootprint )
824  return bestFootprint;
825  else
826  return altFootprint;
827 }
bool NeedsPlaced() const
Definition: footprint.h:320
int GetFlag() const
Definition: footprint.h:240
FOOTPRINTS & Footprints()
Definition: board.h:233
void SetFlag(int aFlag)
Definition: footprint.h:238
static bool sortFootprintsByRatsnestSize(FOOTPRINT *ref, FOOTPRINT *compare)
static bool sortFootprintsByComplexity(FOOTPRINT *ref, FOOTPRINT *compare)
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References BOARD::Footprints(), FOOTPRINT::GetFlag(), m_board, m_connectivity, FOOTPRINT::NeedsPlaced(), FOOTPRINT::SetFlag(), sortFootprintsByComplexity(), and sortFootprintsByRatsnestSize().

Referenced by AutoplaceFootprints().

◆ placeFootprint()

void AR_AUTOPLACER::placeFootprint ( FOOTPRINT aFootprint,
bool  aDoNotRecreateRatsnest,
const wxPoint &  aPos 
)
private

Definition at line 94 of file ar_autoplacer.cpp.

96 {
97  if( !aFootprint )
98  return;
99 
100  aFootprint->SetPosition( aPos );
101  m_connectivity->Update( aFootprint );
102 }
void SetPosition(const wxPoint &aPos) override
Definition: footprint.cpp:1543
std::unique_ptr< CONNECTIVITY_DATA > m_connectivity

References m_connectivity, and FOOTPRINT::SetPosition().

Referenced by AutoplaceFootprints().

◆ rotateFootprint()

void AR_AUTOPLACER::rotateFootprint ( FOOTPRINT aFootprint,
double  angle,
bool  incremental 
)
private

Definition at line 273 of file ar_autoplacer.cpp.

274 {
275  if( aFootprint == nullptr )
276  return;
277 
278  if( incremental )
279  aFootprint->SetOrientation( aFootprint->GetOrientation() + angle );
280  else
281  aFootprint->SetOrientation( angle );
282 
283 
284  m_board->GetConnectivity()->Update( aFootprint );
285 }
double GetOrientation() const
Definition: footprint.h:190
void SetOrientation(double aNewAngle)
Definition: footprint.cpp:1662
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:344
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)

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

Referenced by AutoplaceFootprints().

◆ 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 68 of file ar_autoplacer.h.

69  {
70  m_overlay = aOverlay;
71  }
std::shared_ptr< KIGFX::VIEW_OVERLAY > m_overlay

References m_overlay.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ SetProgressReporter()

void AR_AUTOPLACER::SetProgressReporter ( PROGRESS_REPORTER aReporter)
inline

Definition at line 81 of file ar_autoplacer.h.

82  {
83  m_progressReporter = aReporter;
84  }
PROGRESS_REPORTER * m_progressReporter

References m_progressReporter.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ SetRefreshCallback()

void AR_AUTOPLACER::SetRefreshCallback ( std::function< int(FOOTPRINT *aFootprint)>  aCallback)
inline

Callback to redraw on screen the view after changes, for instance after moving a footprint.

Definition at line 76 of file ar_autoplacer.h.

77  {
78  m_refreshCallback = aCallback;
79  }
std::function< int(FOOTPRINT *aFootprint)> m_refreshCallback

References m_refreshCallback.

Referenced by AUTOPLACE_TOOL::autoplace().

◆ testFootprintOnBoard()

int AR_AUTOPLACER::testFootprintOnBoard ( FOOTPRINT aFootprint,
bool  TstOtherSide,
const wxPoint &  aOffset 
)
private

Definition at line 537 of file ar_autoplacer.cpp.

539 {
540  int side = AR_SIDE_TOP;
541  int otherside = AR_SIDE_BOTTOM;
542 
543  if( aFootprint->GetLayer() == B_Cu )
544  {
545  side = AR_SIDE_BOTTOM; otherside = AR_SIDE_TOP;
546  }
547 
548  EDA_RECT fpBBox = aFootprint->GetBoundingBox( false, false );
549  fpBBox.Move( -aOffset );
550 
551  buildFpAreas( aFootprint, 0 );
552 
553  int diag = //testModuleByPolygon( aFootprint, side, aOffset );
554  testRectangle( fpBBox, side );
555 
556  if( diag != AR_FREE_CELL )
557  return diag;
558 
559  if( TstOtherSide )
560  {
561  diag = //testModuleByPolygon( aFootprint, otherside, aOffset );
562  testRectangle( fpBBox, otherside );
563 
564  if( diag != AR_FREE_CELL )
565  return diag;
566  }
567 
568  int marge = ( m_matrix.m_GridRouting * aFootprint->GetPadCount() ) / AR_GAIN;
569 
570  fpBBox.Inflate( marge );
571  return calculateKeepOutArea( fpBBox, side );
572 }
#define AR_SIDE_BOTTOM
Definition: ar_matrix.h:42
void Move(const wxPoint &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: eda_rect.cpp:51
#define AR_SIDE_TOP
Definition: ar_matrix.h:41
unsigned GetPadCount(INCLUDE_NPTH_T aIncludeNPTH=INCLUDE_NPTH_T(INCLUDE_NPTH)) const
Return the number of pads.
Definition: footprint.cpp:1111
int m_GridRouting
Definition: ar_matrix.h:142
#define AR_GAIN
AR_MATRIX m_matrix
unsigned int calculateKeepOutArea(const EDA_RECT &aRect, int side)
int testRectangle(const EDA_RECT &aRect, int side)
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:718
void buildFpAreas(FOOTPRINT *aFootprint, int aFpClearance)
Handle the component boundary box.
Definition: eda_rect.h:42
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:140
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

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

Referenced by getOptimalFPPlacement().

◆ testRectangle()

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

Definition at line 435 of file ar_autoplacer.cpp.

436 {
437  EDA_RECT rect = aRect;
438 
439  rect.Inflate( m_matrix.m_GridRouting / 2 );
440 
441  wxPoint start = rect.GetOrigin();
442  wxPoint end = rect.GetEnd();
443 
444  start -= m_matrix.m_BrdBox.GetOrigin();
445  end -= m_matrix.m_BrdBox.GetOrigin();
446 
447  int row_min = start.y / m_matrix.m_GridRouting;
448  int row_max = end.y / m_matrix.m_GridRouting;
449  int col_min = start.x / m_matrix.m_GridRouting;
450  int col_max = end.x / m_matrix.m_GridRouting;
451 
452  if( start.y > row_min * m_matrix.m_GridRouting )
453  row_min++;
454 
455  if( start.x > col_min * m_matrix.m_GridRouting )
456  col_min++;
457 
458  if( row_min < 0 )
459  row_min = 0;
460 
461  if( row_max >= ( m_matrix.m_Nrows - 1 ) )
462  row_max = m_matrix.m_Nrows - 1;
463 
464  if( col_min < 0 )
465  col_min = 0;
466 
467  if( col_max >= ( m_matrix.m_Ncols - 1 ) )
468  col_max = m_matrix.m_Ncols - 1;
469 
470  for( int row = row_min; row <= row_max; row++ )
471  {
472  for( int col = col_min; col <= col_max; col++ )
473  {
474  unsigned int data = m_matrix.GetCell( row, col, side );
475 
476  if( ( data & CELL_IS_ZONE ) == 0 )
477  return AR_OUT_OF_BOARD;
478 
479  if( (data & CELL_IS_MODULE) )
480  return AR_OCCUIPED_BY_MODULE;
481  }
482  }
483 
484  return AR_FREE_CELL;
485 }
int m_Ncols
Definition: ar_matrix.h:144
int m_GridRouting
Definition: ar_matrix.h:142
EDA_RECT m_BrdBox
Definition: ar_matrix.h:143
AR_MATRIX m_matrix
const wxPoint GetEnd() const
Definition: eda_rect.h:103
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
MATRIX_CELL GetCell(int aRow, int aCol, int aSide)
Definition: ar_matrix.cpp:169
int m_Nrows
Definition: ar_matrix.h:144
#define CELL_IS_ZONE
#define CELL_IS_MODULE
Handle the component boundary box.
Definition: eda_rect.h:42
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364

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 testFootprintOnBoard().

Member Data Documentation

◆ m_board

BOARD* AR_AUTOPLACER::m_board
private

◆ m_boardShape

SHAPE_POLY_SET AR_AUTOPLACER::m_boardShape
private

Definition at line 129 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 142 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), pickFootprint(), and placeFootprint().

◆ m_curPosition

wxPoint AR_AUTOPLACER::m_curPosition
private

Definition at line 137 of file ar_autoplacer.h.

Referenced by AutoplaceFootprints(), and getOptimalFPPlacement().

◆ m_fpAreaBottom

SHAPE_POLY_SET AR_AUTOPLACER::m_fpAreaBottom
private

Definition at line 132 of file ar_autoplacer.h.

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

◆ m_fpAreaTop

SHAPE_POLY_SET AR_AUTOPLACER::m_fpAreaTop
private

Definition at line 130 of file ar_autoplacer.h.

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

◆ m_gridSize

int AR_AUTOPLACER::m_gridSize
private

Definition at line 139 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), and AutoplaceFootprints().

◆ m_matrix

◆ m_minCost

double AR_AUTOPLACER::m_minCost
private

Definition at line 138 of file ar_autoplacer.h.

Referenced by AR_AUTOPLACER(), AutoplaceFootprints(), and getOptimalFPPlacement().

◆ m_overlay

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

Definition at line 141 of file ar_autoplacer.h.

Referenced by drawPlacementRoutingMatrix(), and SetOverlay().

◆ m_progressReporter

PROGRESS_REPORTER* AR_AUTOPLACER::m_progressReporter
private

Definition at line 144 of file ar_autoplacer.h.

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

◆ m_refreshCallback

std::function<int( FOOTPRINT* aFootprint )> AR_AUTOPLACER::m_refreshCallback
private

Definition at line 143 of file ar_autoplacer.h.

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

◆ m_topFreeArea

SHAPE_POLY_SET AR_AUTOPLACER::m_topFreeArea
private

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