KiCad PCB EDA Suite
spread_footprints.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2019 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2013 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2013 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2019 KiCad Developers, see AUTHORS.txt for contributors.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
37 #include <algorithm>
38 #include <fctsys.h>
39 #include <convert_to_biu.h>
40 #include <confirm.h>
41 #include <pcb_edit_frame.h>
42 #include <class_board.h>
43 #include <class_module.h>
45 
47 {
48  int n; // Original index of this subrect, before sorting
49 
50  TSubRect() : TRect(),
51  n( 0 )
52  {
53  }
54 
55  TSubRect( int _w, int _h, int _n ) :
56  TRect( 0, 0, _w, _h ), n( _n ) { }
57 };
58 
59 typedef std::vector<TSubRect> CSubRectArray;
60 
61 // Use 0.01 mm units to calculate placement, to avoid long calculation time
62 const int scale = (int)(0.01 * IU_PER_MM);
63 
64 const int PADDING = (int)(1 * IU_PER_MM);
65 
66 // Populates a list of rectangles, from a list of modules
67 void fillRectList( CSubRectArray& vecSubRects, std::vector <MODULE*>& aModuleList )
68 {
69  vecSubRects.clear();
70 
71  for( unsigned ii = 0; ii < aModuleList.size(); ii++ )
72  {
73  EDA_RECT fpBox = aModuleList[ii]->GetFootprintRect();
74  TSubRect fpRect( ( fpBox.GetWidth() + PADDING ) / scale,
75  ( fpBox.GetHeight() + PADDING ) / scale, ii );
76  vecSubRects.push_back( fpRect );
77  }
78 }
79 
80 // Populates a list of rectangles, from a list of EDA_RECT
81 void fillRectList( CSubRectArray& vecSubRects, std::vector <EDA_RECT>& aRectList )
82 {
83  vecSubRects.clear();
84 
85  for( unsigned ii = 0; ii < aRectList.size(); ii++ )
86  {
87  EDA_RECT& rect = aRectList[ii];
88  TSubRect fpRect( rect.GetWidth()/scale, rect.GetHeight()/scale, ii );
89  vecSubRects.push_back( fpRect );
90  }
91 }
92 
93 
94 
95 // Spread a list of rectangles inside a placement area
96 void spreadRectangles( CRectPlacement& aPlacementArea,
97  CSubRectArray& vecSubRects,
98  int areaSizeX, int areaSizeY )
99 {
100  areaSizeX/= scale;
101  areaSizeY/= scale;
102 
103  // Sort the subRects based on dimensions, larger dimension goes first.
104  std::sort( vecSubRects.begin(), vecSubRects.end(), CRectPlacement::TRect::Greater );
105 
106  // gives the initial size to the area
107  aPlacementArea.Init( areaSizeX, areaSizeY );
108 
109  // Add all subrects
110  CSubRectArray::iterator it;
111 
112  for( it = vecSubRects.begin(); it != vecSubRects.end(); )
113  {
114  CRectPlacement::TRect r( 0, 0, it->w, it->h );
115 
116  bool bPlaced = aPlacementArea.AddAtEmptySpotAutoGrow( &r, areaSizeX, areaSizeY );
117 
118  if( !bPlaced ) // No room to place the rectangle: enlarge area and retry
119  {
120  bool retry = false;
121 
122  if( areaSizeX < INT_MAX/2 )
123  {
124  retry = true;
125  areaSizeX = areaSizeX * 1.2;
126  }
127 
128  if( areaSizeX < INT_MAX/2 )
129  {
130  retry = true;
131  areaSizeY = areaSizeY * 1.2;
132  }
133 
134  if( retry )
135  {
136  aPlacementArea.Init( areaSizeX, areaSizeY );
137  it = vecSubRects.begin();
138  continue;
139  }
140  }
141 
142  // When correctly placed in a placement area, the coords are returned in r.x and r.y
143  // Store them.
144  it->x = r.x;
145  it->y = r.y;
146 
147  it++;
148  }
149 }
150 
151 
152 void moveFootprintsInArea( CRectPlacement& aPlacementArea,
153  std::vector <MODULE*>& aModuleList,
154  EDA_RECT& aFreeArea,
155  bool aFindAreaOnly )
156 {
157  CSubRectArray vecSubRects;
158 
159  fillRectList( vecSubRects, aModuleList );
160  spreadRectangles( aPlacementArea, vecSubRects,
161  aFreeArea.GetWidth(), aFreeArea.GetHeight() );
162 
163  if( aFindAreaOnly )
164  return;
165 
166  for( unsigned it = 0; it < vecSubRects.size(); ++it )
167  {
168  wxPoint pos( vecSubRects[it].x, vecSubRects[it].y );
169  pos.x *= scale;
170  pos.y *= scale;
171 
172  MODULE * module = aModuleList[vecSubRects[it].n];
173 
174  EDA_RECT fpBBox = module->GetFootprintRect();
175  wxPoint mod_pos = pos + ( module->GetPosition() - fpBBox.GetOrigin() )
176  + aFreeArea.GetOrigin();
177 
178  module->Move( mod_pos - module->GetPosition() );
179  }
180 }
181 
182 static bool sortFootprintsbySheetPath( MODULE* ref, MODULE* compare );
183 
184 
193 void SpreadFootprints( std::vector<MODULE*>* aFootprints,
194  wxPoint aSpreadAreaPosition )
195 {
196  // Build candidate list
197  // calculate also the area needed by these footprints
198  std::vector <MODULE*> footprintList;
199 
200  for( MODULE* footprint : *aFootprints )
201  {
202  if( footprint->IsLocked() )
203  continue;
204 
205  footprint->CalculateBoundingBox();
206  footprintList.push_back( footprint );
207  }
208 
209  if( footprintList.empty() )
210  return;
211 
212  // sort footprints by sheet path. we group them later by sheet
213  sort( footprintList.begin(), footprintList.end(), sortFootprintsbySheetPath );
214 
215  // Extract and place footprints by sheet
216  std::vector <MODULE*> footprintListBySheet;
217  std::vector <EDA_RECT> placementSheetAreas;
218  double subsurface;
219  double placementsurface = 0.0;
220 
221  // The placement uses 2 passes:
222  // the first pass creates the rectangular areas to place footprints
223  // each sheet in schematic creates one rectangular area.
224  // the second pass moves footprints inside these areas
225  for( int pass = 0; pass < 2; pass++ )
226  {
227  int subareaIdx = 0;
228  footprintListBySheet.clear();
229  subsurface = 0.0;
230 
231  int fp_max_width = 0;
232  int fp_max_height = 0;
233 
234  for( unsigned ii = 0; ii < footprintList.size(); ii++ )
235  {
236  MODULE* footprint = footprintList[ii];
237  bool islastItem = false;
238 
239  if( ii == footprintList.size() - 1 ||
240  ( footprintList[ii]->GetPath().AsString().BeforeLast( '/' ) !=
241  footprintList[ii+1]->GetPath().AsString().BeforeLast( '/' ) ) )
242  islastItem = true;
243 
244  footprintListBySheet.push_back( footprint );
245  subsurface += footprint->GetArea( PADDING );
246 
247  // Calculate min size of placement area:
248  EDA_RECT bbox = footprint->GetFootprintRect();
249  fp_max_width = std::max( fp_max_width, bbox.GetWidth() );
250  fp_max_height = std::max( fp_max_height, bbox.GetHeight() );
251 
252  if( islastItem )
253  {
254  // end of the footprint sublist relative to the same sheet path
255  // calculate placement of the current sublist
256  EDA_RECT freeArea;
257  int Xsize_allowed = (int) ( sqrt( subsurface ) * 4.0 / 3.0 );
258  Xsize_allowed = std::max( fp_max_width, Xsize_allowed );
259 
260  int Ysize_allowed = (int) ( subsurface / Xsize_allowed );
261  Ysize_allowed = std::max( fp_max_height, Ysize_allowed );
262 
263  freeArea.SetWidth( Xsize_allowed );
264  freeArea.SetHeight( Ysize_allowed );
265  CRectPlacement placementArea;
266 
267  if( pass == 1 )
268  {
269  wxPoint areapos = placementSheetAreas[subareaIdx].GetOrigin()
270  + aSpreadAreaPosition;
271  freeArea.SetOrigin( areapos );
272  }
273 
274  bool findAreaOnly = pass == 0;
275  moveFootprintsInArea( placementArea, footprintListBySheet,
276  freeArea, findAreaOnly );
277 
278  if( pass == 0 )
279  {
280  // Populate sheet placement areas list
281  EDA_RECT sub_area;
282  sub_area.SetWidth( placementArea.GetW()*scale );
283  sub_area.SetHeight( placementArea.GetH()*scale );
284  // Add a margin around the sheet placement area:
285  sub_area.Inflate( Millimeter2iu( 1.5 ) );
286 
287  placementSheetAreas.push_back( sub_area );
288 
289  placementsurface += (double) sub_area.GetWidth()*
290  sub_area.GetHeight();
291  }
292 
293  // Prepare buffers for next sheet
294  subsurface = 0.0;
295  footprintListBySheet.clear();
296  subareaIdx++;
297  }
298  }
299 
300  // End of pass:
301  // At the end of the first pass, we have to find position of each sheet
302  // placement area
303  if( pass == 0 )
304  {
305  int Xsize_allowed = (int) ( sqrt( placementsurface ) * 4.0 / 3.0 );
306 
307  if( Xsize_allowed < 0 || Xsize_allowed > INT_MAX/2 )
308  Xsize_allowed = INT_MAX/2;
309 
310  int Ysize_allowed = (int) ( placementsurface / Xsize_allowed );
311 
312  if( Ysize_allowed < 0 || Ysize_allowed > INT_MAX/2 )
313  Ysize_allowed = INT_MAX/2;
314 
315  CRectPlacement placementArea;
316  CSubRectArray vecSubRects;
317  fillRectList( vecSubRects, placementSheetAreas );
318  spreadRectangles( placementArea, vecSubRects, Xsize_allowed, Ysize_allowed );
319 
320  for( unsigned it = 0; it < vecSubRects.size(); ++it )
321  {
322  TSubRect& srect = vecSubRects[it];
323  wxPoint pos( srect.x*scale, srect.y*scale );
324  wxSize size( srect.w*scale, srect.h*scale );
325 
326  // Avoid too large coordinates: Overlapping components
327  // are better than out of screen components
328  if( (uint64_t)pos.x + (uint64_t)size.x > INT_MAX/2 )
329  pos.x = 0;
330 
331  if( (uint64_t)pos.y + (uint64_t)size.y > INT_MAX/2 )
332  pos.y = 0;
333 
334  placementSheetAreas[srect.n].SetOrigin( pos );
335  placementSheetAreas[srect.n].SetSize( size );
336  }
337  }
338  } // End pass
339 }
340 
341 
342 // Sort function, used to group footprints by sheet.
343 // Footprints are sorted by their sheet path.
344 // (the full sheet path restricted to the time stamp of the sheet itself,
345 // without the time stamp of the footprint ).
346 static bool sortFootprintsbySheetPath( MODULE* ref, MODULE* compare )
347 {
348  return ref->GetPath() < compare->GetPath();
349 }
double GetArea(int aPadding=0) const
void Init(int w=1, int h=1)
This file is part of the common library.
static constexpr double IU_PER_MM
Mock up a conversion function.
int GetWidth() const
Definition: eda_rect.h:119
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:131
EDA_RECT GetFootprintRect() const
Function GetFootprintRect() Returns the area of the module footprint excluding any text.
void fillRectList(CSubRectArray &vecSubRects, std::vector< MODULE * > &aModuleList)
const KIID_PATH & GetPath() const
Definition: class_module.h:234
static bool Greater(const TRect &a, const TRect &b)
const int PADDING
void SetHeight(int val)
Definition: eda_rect.h:186
const wxPoint GetOrigin() const
Definition: eda_rect.h:114
int GetW() const
static bool sortFootprintsbySheetPath(MODULE *ref, MODULE *compare)
std::vector< TSubRect > CSubRectArray
void SetWidth(int val)
Definition: eda_rect.h:180
int GetHeight() const
Definition: eda_rect.h:120
TSubRect(int _w, int _h, int _n)
const int scale
void Move(const wxPoint &aMoveVector) override
Function Move move this object.
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
void SpreadFootprints(std::vector< MODULE * > *aFootprints, wxPoint aSpreadAreaPosition)
Footprints (after loaded by reading a netlist for instance) are moved to be in a small free area (out...
bool AddAtEmptySpotAutoGrow(TRect *pRect, int maxW, int maxH)
wxPoint GetPosition() const override
Definition: class_module.h:216
static constexpr int Millimeter2iu(double mm)
void moveFootprintsInArea(CRectPlacement &aPlacementArea, std::vector< MODULE * > &aModuleList, EDA_RECT &aFreeArea, bool aFindAreaOnly)
void spreadRectangles(CRectPlacement &aPlacementArea, CSubRectArray &vecSubRects, int areaSizeX, int areaSizeY)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
int GetH() const