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 <convert_to_biu.h>
39 #include <confirm.h>
40 #include <pcb_edit_frame.h>
41 #include <board.h>
42 #include <footprint.h>
44 
46 {
47  int n; // Original index of this subrect, before sorting
48 
49  TSubRect() : TRect(),
50  n( 0 )
51  {
52  }
53 
54  TSubRect( int _w, int _h, int _n ) :
55  TRect( 0, 0, _w, _h ), n( _n ) { }
56 };
57 
58 typedef std::vector<TSubRect> CSubRectArray;
59 
60 // Use 0.01 mm units to calculate placement, to avoid long calculation time
61 const int scale = (int)(0.01 * IU_PER_MM);
62 
63 const int PADDING = (int)(1 * IU_PER_MM);
64 
65 // Populates a list of rectangles, from a list of footprints
66 void fillRectList( CSubRectArray& vecSubRects, std::vector <FOOTPRINT*>& aFootprintList )
67 {
68  vecSubRects.clear();
69 
70  for( unsigned ii = 0; ii < aFootprintList.size(); ii++ )
71  {
72  EDA_RECT fpBox = aFootprintList[ii]->GetBoundingBox( false, false );
73  TSubRect fpRect( ( fpBox.GetWidth() + PADDING ) / scale,
74  ( fpBox.GetHeight() + PADDING ) / scale, ii );
75  vecSubRects.push_back( fpRect );
76  }
77 }
78 
79 // Populates a list of rectangles, from a list of EDA_RECT
80 void fillRectList( CSubRectArray& vecSubRects, std::vector <EDA_RECT>& aRectList )
81 {
82  vecSubRects.clear();
83 
84  for( unsigned ii = 0; ii < aRectList.size(); ii++ )
85  {
86  EDA_RECT& rect = aRectList[ii];
87  TSubRect fpRect( rect.GetWidth()/scale, rect.GetHeight()/scale, ii );
88  vecSubRects.push_back( fpRect );
89  }
90 }
91 
92 
93 
94 // Spread a list of rectangles inside a placement area
95 void spreadRectangles( CRectPlacement& aPlacementArea,
96  CSubRectArray& vecSubRects,
97  int areaSizeX, int areaSizeY )
98 {
99  areaSizeX/= scale;
100  areaSizeY/= scale;
101 
102  // Sort the subRects based on dimensions, larger dimension goes first.
103  std::sort( vecSubRects.begin(), vecSubRects.end(), CRectPlacement::TRect::Greater );
104 
105  // gives the initial size to the area
106  aPlacementArea.Init( areaSizeX, areaSizeY );
107 
108  // Add all subrects
109  CSubRectArray::iterator it;
110 
111  for( it = vecSubRects.begin(); it != vecSubRects.end(); )
112  {
113  CRectPlacement::TRect r( 0, 0, it->w, it->h );
114 
115  bool bPlaced = aPlacementArea.AddAtEmptySpotAutoGrow( &r, areaSizeX, areaSizeY );
116 
117  if( !bPlaced ) // No room to place the rectangle: enlarge area and retry
118  {
119  bool retry = false;
120 
121  if( areaSizeX < INT_MAX/2 )
122  {
123  retry = true;
124  areaSizeX = areaSizeX * 1.2;
125  }
126 
127  if( areaSizeX < INT_MAX/2 )
128  {
129  retry = true;
130  areaSizeY = areaSizeY * 1.2;
131  }
132 
133  if( retry )
134  {
135  aPlacementArea.Init( areaSizeX, areaSizeY );
136  it = vecSubRects.begin();
137  continue;
138  }
139  }
140 
141  // When correctly placed in a placement area, the coords are returned in r.x and r.y
142  // Store them.
143  it->x = r.x;
144  it->y = r.y;
145 
146  it++;
147  }
148 }
149 
150 
151 void moveFootprintsInArea( CRectPlacement& aPlacementArea, std::vector <FOOTPRINT*>& aFootprintList,
152  EDA_RECT& aFreeArea, bool aFindAreaOnly )
153 {
154  CSubRectArray vecSubRects;
155 
156  fillRectList( vecSubRects, aFootprintList );
157  spreadRectangles( aPlacementArea, vecSubRects, aFreeArea.GetWidth(), aFreeArea.GetHeight() );
158 
159  if( aFindAreaOnly )
160  return;
161 
162  for( unsigned it = 0; it < vecSubRects.size(); ++it )
163  {
164  wxPoint pos( vecSubRects[it].x, vecSubRects[it].y );
165  pos.x *= scale;
166  pos.y *= scale;
167 
168  FOOTPRINT* footprint = aFootprintList[vecSubRects[it].n];
169 
170  EDA_RECT fpBBox = footprint->GetBoundingBox( false, false );
171  wxPoint mod_pos = pos + ( footprint->GetPosition() - fpBBox.GetOrigin() )
172  + aFreeArea.GetOrigin();
173 
174  footprint->Move( mod_pos - footprint->GetPosition() );
175  }
176 }
177 
178 static bool sortFootprintsbySheetPath( FOOTPRINT* ref, FOOTPRINT* compare );
179 
180 
189 void SpreadFootprints( std::vector<FOOTPRINT*>* aFootprints, wxPoint aSpreadAreaPosition )
190 {
191  // Build candidate list
192  // calculate also the area needed by these footprints
193  std::vector <FOOTPRINT*> footprintList;
194 
195  for( FOOTPRINT* footprint : *aFootprints )
196  {
197  if( footprint->IsLocked() )
198  continue;
199 
200  footprintList.push_back( footprint );
201  }
202 
203  if( footprintList.empty() )
204  return;
205 
206  // sort footprints by sheet path. we group them later by sheet
207  sort( footprintList.begin(), footprintList.end(), sortFootprintsbySheetPath );
208 
209  // Extract and place footprints by sheet
210  std::vector <FOOTPRINT*> footprintListBySheet;
211  std::vector <EDA_RECT> placementSheetAreas;
212  double subsurface;
213  double placementsurface = 0.0;
214 
215  // The placement uses 2 passes:
216  // the first pass creates the rectangular areas to place footprints
217  // each sheet in schematic creates one rectangular area.
218  // the second pass moves footprints inside these areas
219  for( int pass = 0; pass < 2; pass++ )
220  {
221  int subareaIdx = 0;
222  footprintListBySheet.clear();
223  subsurface = 0.0;
224 
225  int fp_max_width = 0;
226  int fp_max_height = 0;
227 
228  for( unsigned ii = 0; ii < footprintList.size(); ii++ )
229  {
230  FOOTPRINT* footprint = footprintList[ii];
231  bool islastItem = false;
232 
233  if( ii == footprintList.size() - 1 ||
234  ( footprintList[ii]->GetPath().AsString().BeforeLast( '/' ) !=
235  footprintList[ii+1]->GetPath().AsString().BeforeLast( '/' ) ) )
236  islastItem = true;
237 
238  footprintListBySheet.push_back( footprint );
239  subsurface += footprint->GetArea( PADDING );
240 
241  // Calculate min size of placement area:
242  EDA_RECT bbox = footprint->GetBoundingBox( false, false );
243  fp_max_width = std::max( fp_max_width, bbox.GetWidth() );
244  fp_max_height = std::max( fp_max_height, bbox.GetHeight() );
245 
246  if( islastItem )
247  {
248  // end of the footprint sublist relative to the same sheet path
249  // calculate placement of the current sublist
250  EDA_RECT freeArea;
251  int Xsize_allowed = (int) ( sqrt( subsurface ) * 4.0 / 3.0 );
252  Xsize_allowed = std::max( fp_max_width, Xsize_allowed );
253 
254  int Ysize_allowed = (int) ( subsurface / Xsize_allowed );
255  Ysize_allowed = std::max( fp_max_height, Ysize_allowed );
256 
257  freeArea.SetWidth( Xsize_allowed );
258  freeArea.SetHeight( Ysize_allowed );
259  CRectPlacement placementArea;
260 
261  if( pass == 1 )
262  {
263  wxPoint areapos = placementSheetAreas[subareaIdx].GetOrigin()
264  + aSpreadAreaPosition;
265  freeArea.SetOrigin( areapos );
266  }
267 
268  bool findAreaOnly = pass == 0;
269  moveFootprintsInArea( placementArea, footprintListBySheet, freeArea, findAreaOnly );
270 
271  if( pass == 0 )
272  {
273  // Populate sheet placement areas list
274  EDA_RECT sub_area;
275  sub_area.SetWidth( placementArea.GetW()*scale );
276  sub_area.SetHeight( placementArea.GetH()*scale );
277  // Add a margin around the sheet placement area:
278  sub_area.Inflate( Millimeter2iu( 1.5 ) );
279 
280  placementSheetAreas.push_back( sub_area );
281 
282  placementsurface += (double) sub_area.GetWidth()*
283  sub_area.GetHeight();
284  }
285 
286  // Prepare buffers for next sheet
287  subsurface = 0.0;
288  footprintListBySheet.clear();
289  subareaIdx++;
290  }
291  }
292 
293  // End of pass:
294  // At the end of the first pass, we have to find position of each sheet
295  // placement area
296  if( pass == 0 )
297  {
298  int Xsize_allowed = (int) ( sqrt( placementsurface ) * 4.0 / 3.0 );
299 
300  if( Xsize_allowed < 0 || Xsize_allowed > INT_MAX/2 )
301  Xsize_allowed = INT_MAX/2;
302 
303  int Ysize_allowed = (int) ( placementsurface / Xsize_allowed );
304 
305  if( Ysize_allowed < 0 || Ysize_allowed > INT_MAX/2 )
306  Ysize_allowed = INT_MAX/2;
307 
308  CRectPlacement placementArea;
309  CSubRectArray vecSubRects;
310  fillRectList( vecSubRects, placementSheetAreas );
311  spreadRectangles( placementArea, vecSubRects, Xsize_allowed, Ysize_allowed );
312 
313  for( unsigned it = 0; it < vecSubRects.size(); ++it )
314  {
315  TSubRect& srect = vecSubRects[it];
316  wxPoint pos( srect.x*scale, srect.y*scale );
317  wxSize size( srect.w*scale, srect.h*scale );
318 
319  // Avoid too large coordinates: Overlapping components
320  // are better than out of screen components
321  if( (uint64_t)pos.x + (uint64_t)size.x > INT_MAX/2 )
322  pos.x = 0;
323 
324  if( (uint64_t)pos.y + (uint64_t)size.y > INT_MAX/2 )
325  pos.y = 0;
326 
327  placementSheetAreas[srect.n].SetOrigin( pos );
328  placementSheetAreas[srect.n].SetSize( size );
329  }
330  }
331  } // End pass
332 }
333 
334 
335 // Sort function, used to group footprints by sheet.
336 // Footprints are sorted by their sheet path.
337 // (the full sheet path restricted to the time stamp of the sheet itself,
338 // without the time stamp of the footprint ).
339 static bool sortFootprintsbySheetPath( FOOTPRINT* ref, FOOTPRINT* compare )
340 {
341  return ref->GetPath() < compare->GetPath();
342 }
double GetArea(int aPadding=0) const
Definition: footprint.cpp:597
const KIID_PATH & GetPath() const
Definition: footprint.h:199
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.
void fillRectList(CSubRectArray &vecSubRects, std::vector< FOOTPRINT * > &aFootprintList)
static bool sortFootprintsbySheetPath(FOOTPRINT *ref, FOOTPRINT *compare)
int GetWidth() const
Definition: eda_rect.h:114
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:126
static bool Greater(const TRect &a, const TRect &b)
const int PADDING
void moveFootprintsInArea(CRectPlacement &aPlacementArea, std::vector< FOOTPRINT * > &aFootprintList, EDA_RECT &aFreeArea, bool aFindAreaOnly)
void SetHeight(int val)
Definition: eda_rect.h:181
const wxPoint GetOrigin() const
Definition: eda_rect.h:106
void Move(const wxPoint &aMoveVector) override
Move this object.
Definition: footprint.cpp:1334
int GetW() const
std::vector< TSubRect > CSubRectArray
void SetWidth(int val)
Definition: eda_rect.h:175
int GetHeight() const
Definition: eda_rect.h:115
TSubRect(int _w, int _h, int _n)
const int scale
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:630
Handle the component boundary box.
Definition: eda_rect.h:42
wxPoint GetPosition() const override
Definition: footprint.h:182
bool AddAtEmptySpotAutoGrow(TRect *pRect, int maxW, int maxH)
static constexpr int Millimeter2iu(double mm)
void SpreadFootprints(std::vector< FOOTPRINT * > *aFootprints, wxPoint aSpreadAreaPosition)
Footprints (after loaded by reading a netlist for instance) are moved to be in a small free area (out...
void spreadRectangles(CRectPlacement &aPlacementArea, CSubRectArray &vecSubRects, int areaSizeX, int areaSizeY)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:363
int GetH() const