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