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, [email protected]
5 * Copyright (C) 2013 SoftPLC Corporation, Dick Hollenbeck <[email protected]>
6 * Copyright (C) 2013 Wayne Stambaugh <[email protected]>
7 *
8 * Copyright (C) 1992-2022 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 <spread_footprints.h>
38#include <algorithm>
39#include <refdes_utils.h>
40#include <string_utils.h>
41#include <confirm.h>
42#include <pcb_edit_frame.h>
43#include <board.h>
44#include <rectpack2d/finders_interface.h>
45
46
47constexpr bool allow_flip = true;
48
49using spaces_type = rectpack2D::empty_spaces<allow_flip, rectpack2D::default_empty_spaces>;
50using rect_type = rectpack2D::output_rect_t<spaces_type>;
52using rect_vector = std::vector<rect_type>;
53
54// Use 0.01 mm units to calculate placement, to avoid long calculation time
55const int scale = (int) ( 0.01 * pcbIUScale.IU_PER_MM );
56
57
58static bool compareFootprintsbyRef( FOOTPRINT* ref, FOOTPRINT* compare )
59{
60 const wxString& refPrefix = UTIL::GetRefDesPrefix( ref->GetReference() );
61 const wxString& cmpPrefix = UTIL::GetRefDesPrefix( compare->GetReference() );
62
63 if( refPrefix != cmpPrefix )
64 {
65 return refPrefix < cmpPrefix;
66 }
67 else
68 {
69 const int refInt = GetTrailingInt( ref->GetReference() );
70 const int cmpInt = GetTrailingInt( compare->GetReference() );
71
72 return refInt < cmpInt;
73 }
74
75 return false;
76}
77
78
79// Spread a list of rectangles inside a placement area
80rectpack2D::rect_wh spreadRectangles( rect_vector& vecSubRects, int areaSizeX, int areaSizeY )
81{
82 areaSizeX /= scale;
83 areaSizeY /= scale;
84
85 rectpack2D::rect_wh result;
86
87 int max_side = std::max( areaSizeX, areaSizeY );
88
89 while( true )
90 {
91 bool anyUnsuccessful = false;
92 const int discard_step = 1;
93
94 auto report_successful = [&]( rect_type& )
95 {
96 return rectpack2D::callback_result::CONTINUE_PACKING;
97 };
98
99 auto report_unsuccessful = [&]( rect_type& r )
100 {
101 anyUnsuccessful = true;
102 return rectpack2D::callback_result::ABORT_PACKING;
103 };
104
105 result = rectpack2D::find_best_packing<spaces_type>(
106 vecSubRects,
107 make_finder_input( max_side, discard_step, report_successful, report_unsuccessful,
108 rectpack2D::flipping_option::DISABLED ) );
109
110 if( anyUnsuccessful )
111 {
112 max_side = (int) ( max_side * 1.2 );
113 continue;
114 }
115
116 break;
117 }
118
119 return result;
120}
121
122
123void SpreadFootprints( std::vector<FOOTPRINT*>* aFootprints, VECTOR2I aTargetBoxPosition,
124 bool aGroupBySheet, int aComponentGap, int aGroupGap )
125{
126 using FpBBoxToFootprintsPair = std::pair<BOX2I, std::vector<FOOTPRINT*>>;
127 using SheetBBoxToFootprintsMapPair =
128 std::pair<BOX2I, std::map<VECTOR2I, FpBBoxToFootprintsPair>>;
129
130 std::map<wxString, SheetBBoxToFootprintsMapPair> sheetsMap;
131 std::vector<BOX2I> blockMap;
132
133 // Fill in the maps
134 for( FOOTPRINT* footprint : *aFootprints )
135 {
136 wxString path =
137 aGroupBySheet ? footprint->GetPath().AsString().BeforeLast( '/' ) : wxS( "" );
138
139 VECTOR2I size = footprint->GetBoundingBox( false, false ).GetSize();
140 size.x += aComponentGap;
141 size.y += aComponentGap;
142
143 sheetsMap[path].second[size].second.push_back( footprint );
144 }
145
146 for( auto& [sheetPath, sheetPair] : sheetsMap )
147 {
148 auto& [sheet_bbox, sizeToFpMap] = sheetPair;
149
150 for( auto& [fpSize, fpPair] : sizeToFpMap )
151 {
152 auto& [block_bbox, footprints] = fpPair;
153
154 // Find optimal arrangement of same-size footprints
155
156 double blockEstimateArea = (double) fpSize.x * fpSize.y * footprints.size();
157 double initialSide = std::sqrt( blockEstimateArea );
158 bool vertical = fpSize.x >= fpSize.y;
159
160 int initialCountPerLine = footprints.size();
161
162 const int singleLineRatio = 5;
163
164 // Wrap the line if the ratio is not satisfied
165 if( vertical )
166 {
167 if( ( fpSize.y * footprints.size() / fpSize.x ) > singleLineRatio )
168 initialCountPerLine = initialSide / fpSize.y;
169 }
170 else
171 {
172 if( ( fpSize.x * footprints.size() / fpSize.y ) > singleLineRatio )
173 initialCountPerLine = initialSide / fpSize.x;
174 }
175
176 int optimalCountPerLine = initialCountPerLine;
177 int optimalRemainder = footprints.size() % optimalCountPerLine;
178
179 if( optimalRemainder != 0 )
180 {
181 for( int i = std::max( 2, initialCountPerLine - 2 );
182 i <= std::min( (int) footprints.size() - 2, initialCountPerLine + 2 ); i++ )
183 {
184 int r = footprints.size() % i;
185
186 if( r == 0 || r >= optimalRemainder )
187 {
188 optimalCountPerLine = i;
189 optimalRemainder = r;
190 }
191 }
192 }
193
194 std::sort( footprints.begin(), footprints.end(), compareFootprintsbyRef );
195
196 // Arrange footprints in rows or columns (blocks)
197 for( unsigned i = 0; i < footprints.size(); i++ )
198 {
199 FOOTPRINT* footprint = footprints[i];
200
201 VECTOR2I position = fpSize / 2;
202
203 if( vertical )
204 {
205 position.x += fpSize.x * ( i / optimalCountPerLine );
206 position.y += fpSize.y * ( i % optimalCountPerLine );
207 }
208 else
209 {
210 position.x += fpSize.x * ( i % optimalCountPerLine );
211 position.y += fpSize.y * ( i / optimalCountPerLine );
212 }
213
214 BOX2I old_fp_bbox = footprint->GetBoundingBox( false, false );
215 footprint->Move( position - old_fp_bbox.GetOrigin() );
216
217 BOX2I new_fp_bbox = footprint->GetBoundingBox( false, false );
218 new_fp_bbox.Inflate( aComponentGap / 2 );
219 block_bbox.Merge( new_fp_bbox );
220 }
221 }
222
223 rect_vector vecSubRects;
224 long long blocksArea = 0;
225
226 // Fill in arrays for packing of blocks
227 for( auto& [fpSize, fpPair] : sizeToFpMap )
228 {
229 auto& [block_bbox, footprints] = fpPair;
230
231 vecSubRects.emplace_back( 0, 0, block_bbox.GetWidth() / scale,
232 block_bbox.GetHeight() / scale, false );
233
234 blocksArea += block_bbox.GetArea();
235 }
236
237 // Pack the blocks
238 int areaSide = std::sqrt( blocksArea );
239 spreadRectangles( vecSubRects, areaSide, areaSide );
240
241 unsigned block_i = 0;
242
243 // Move footprints to the new block locations
244 for( auto& [fpSize, pair] : sizeToFpMap )
245 {
246 auto& [src_bbox, footprints] = pair;
247
248 rect_type srect = vecSubRects[block_i];
249
250 VECTOR2I target_pos( srect.x * scale, srect.y * scale );
251 VECTOR2I target_size( srect.w * scale, srect.h * scale );
252
253 // Avoid too large coordinates: Overlapping components
254 // are better than out of screen components
255 if( (uint64_t) target_pos.x + (uint64_t) target_size.x > INT_MAX / 2 )
256 target_pos.x -= INT_MAX / 2;
257
258 if( (uint64_t) target_pos.y + (uint64_t) target_size.y > INT_MAX / 2 )
259 target_pos.y -= INT_MAX / 2;
260
261 for( FOOTPRINT* footprint : footprints )
262 {
263 footprint->Move( target_pos - src_bbox.GetPosition() );
264 sheet_bbox.Merge( footprint->GetBoundingBox( false, false ) );
265 }
266
267 block_i++;
268 }
269 }
270
271 rect_vector vecSubRects;
272 long long sheetsArea = 0;
273
274 // Fill in arrays for packing of hierarchical sheet groups
275 for( auto& [sheetPath, sheetPair] : sheetsMap )
276 {
277 auto& [sheet_bbox, sizeToFpMap] = sheetPair;
278 BOX2I rect = sheet_bbox;
279
280 // Add a margin around the sheet placement area:
281 rect.Inflate( aGroupGap );
282
283 vecSubRects.emplace_back( 0, 0, rect.GetWidth() / scale, rect.GetHeight() / scale, false );
284
285 sheetsArea += sheet_bbox.GetArea();
286 }
287
288 // Pack the hierarchical sheet groups
289 int areaSide = std::sqrt( sheetsArea );
290 spreadRectangles( vecSubRects, areaSide, areaSide );
291
292 unsigned srect_i = 0;
293
294 // Move footprints to the new hierarchical sheet group locations
295 for( auto& [sheetPath, sheetPair] : sheetsMap )
296 {
297 auto& [src_bbox, sizeToFpMap] = sheetPair;
298
299 rect_type srect = vecSubRects[srect_i];
300
301 VECTOR2I target_pos( srect.x * scale + aTargetBoxPosition.x,
302 srect.y * scale + aTargetBoxPosition.y );
303 VECTOR2I target_size( srect.w * scale, srect.h * scale );
304
305 // Avoid too large coordinates: Overlapping components
306 // are better than out of screen components
307 if( (uint64_t) target_pos.x + (uint64_t) target_size.x > INT_MAX / 2 )
308 target_pos.x -= INT_MAX / 2;
309
310 if( (uint64_t) target_pos.y + (uint64_t) target_size.y > INT_MAX / 2 )
311 target_pos.y -= INT_MAX / 2;
312
313 for( auto& [fpSize, fpPair] : sizeToFpMap )
314 {
315 auto& [block_bbox, footprints] = fpPair;
316 for( FOOTPRINT* footprint : footprints )
317 {
318 footprint->Move( target_pos - src_bbox.GetPosition() );
319 }
320 }
321
322 srect_i++;
323 }
324}
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
ecoord_type GetArea() const
Return the area of the rectangle.
Definition: box2.h:701
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
void Move(const VECTOR2I &aMoveVector) override
Move this object.
Definition: footprint.cpp:1532
const wxString & GetReference() const
Definition: footprint.h:519
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:794
This file is part of the common library.
E_SERIE r
Definition: eserie.cpp:41
wxString GetRefDesPrefix(const wxString &aRefDes)
Get the (non-numeric) prefix from a refdes - e.g.
Collection of utility functions for component reference designators (refdes)
rectpack2D::empty_spaces< allow_flip, rectpack2D::default_empty_spaces > spaces_type
void SpreadFootprints(std::vector< FOOTPRINT * > *aFootprints, VECTOR2I aTargetBoxPosition, bool aGroupBySheet, int aComponentGap, int aGroupGap)
Footprints (after loaded by reading a netlist for instance) are moved to be in a small free area (out...
std::vector< rect_type > rect_vector
rectpack2D::rect_wh spreadRectangles(rect_vector &vecSubRects, int areaSizeX, int areaSizeY)
const int scale
rectpack2D::output_rect_t< spaces_type > rect_type
rect_type * rect_ptr
static bool compareFootprintsbyRef(FOOTPRINT *ref, FOOTPRINT *compare)
constexpr bool allow_flip
int GetTrailingInt(const wxString &aStr)
Gets the trailing int, if any, from a string.
const double IU_PER_MM
Definition: base_units.h:77