Horizon
Loading...
Searching...
No Matches
pns_optimizer.h
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8 *
9 * This program is free software: you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation, either version 3 of the License, or (at your
12 * option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program. If not, see <http://www.gnu.org/licenses/>.
21 */
22
23#ifndef __PNS_OPTIMIZER_H
24#define __PNS_OPTIMIZER_H
25
26#include <unordered_map>
27#include <memory>
28
29#include <geometry/shape_index_list.h>
30#include <geometry/shape_line_chain.h>
31
32#include "range.h"
33
34
35namespace PNS {
36
37class NODE;
38class ROUTER;
39class LINE;
40class DIFF_PAIR;
41class ITEM;
42class JOINT;
43class OPT_CONSTRAINT;
44
49{
50public:
52 m_lengthCost( 0 ),
53 m_cornerCost( 0 )
54 {}
55
56 COST_ESTIMATOR( const COST_ESTIMATOR& aB ) :
57 m_lengthCost( aB.m_lengthCost ),
58 m_cornerCost( aB.m_cornerCost )
59 {}
60
61 ~COST_ESTIMATOR() {};
62
63 static int CornerCost( const SEG& aA, const SEG& aB );
64 static int CornerCost( const SHAPE_LINE_CHAIN& aLine );
65 static int CornerCost( const LINE& aLine );
66
67 void Add( const LINE& aLine );
68 void Remove( const LINE& aLine );
69 void Replace( const LINE& aOldLine, const LINE& aNewLine );
70
71 bool IsBetter( const COST_ESTIMATOR& aOther, double aLengthTolerance,
72 double aCornerTollerace ) const;
73
74 double GetLengthCost() const { return m_lengthCost; }
75 double GetCornerCost() const { return m_cornerCost; }
76
77private:
78 double m_lengthCost;
79 int m_cornerCost;
80};
81
82
95{
96public:
98 {
100 SMART_PADS = 0x02,
103 KEEP_TOPOLOGY = 0x10,
104 PRESERVE_VERTEX = 0x20,
105 RESTRICT_VERTEX_RANGE = 0x40,
107 RESTRICT_AREA = 0x100,
108 LIMIT_CORNER_COUNT = 0x200
110 };
111
112 OPTIMIZER( NODE* aWorld );
113 ~OPTIMIZER();
114
116 static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld,
117 const VECTOR2I& aV = VECTOR2I(0, 0) );
118
119 bool Optimize( LINE* aLine, LINE* aResult = nullptr, LINE* aRoot = nullptr );
120 bool Optimize( DIFF_PAIR* aPair );
121
122
123 void SetWorld( NODE* aNode ) { m_world = aNode; }
124 void CacheRemove( ITEM* aItem );
125 void ClearCache( bool aStaticOnly = false );
126
127 void SetCollisionMask( int aMask )
128 {
129 m_collisionKindMask = aMask;
130 }
131
132 void SetEffortLevel( int aEffort )
133 {
134 m_effortLevel = aEffort;
135 }
136
137 void SetPreserveVertex( const VECTOR2I& aV )
138 {
139 m_preservedVertex = aV;
140 m_effortLevel |= OPTIMIZER::PRESERVE_VERTEX;
141 }
142
143 void SetRestrictVertexRange( int aStart, int aEnd )
144 {
145 m_restrictedVertexRange.first = aStart;
146 m_restrictedVertexRange.second = aEnd;
147 m_effortLevel |= OPTIMIZER::RESTRICT_VERTEX_RANGE;
148 }
149
150 void SetRestrictArea( const BOX2I& aArea, bool aStrict = true )
151 {
152 m_restrictArea = aArea;
153 m_restrictAreaIsStrict = aStrict;
154 }
155
156 void ClearConstraints();
157 void AddConstraint ( OPT_CONSTRAINT *aConstraint );
158
159private:
160 static const int MaxCachedItems = 256;
161
162 typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
163
164 struct CACHE_VISITOR;
165
166 struct CACHED_ITEM
167 {
168 int m_hits;
169 bool m_isStatic;
170 };
171
172 bool mergeObtuse( LINE* aLine );
173 bool mergeFull( LINE* aLine );
174 bool mergeColinear( LINE* aLine );
175 bool runSmartPads( LINE* aLine );
176 bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
177 bool fanoutCleanup( LINE * aLine );
178 bool mergeDpSegments( DIFF_PAIR *aPair );
179 bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
180
181 bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
182 bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
183
184 void cacheAdd( ITEM* aItem, bool aIsStatic );
185 void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
186
187 bool checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
188 const SHAPE_LINE_CHAIN& aCurrentPath,
189 const SHAPE_LINE_CHAIN& aReplacement );
190
191 BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
192 BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
193 BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
194 BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
195
196 int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
197
198 ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
199
200private:
202 std::vector<OPT_CONSTRAINT*> m_constraints;
203 std::unordered_map<ITEM*, CACHED_ITEM> m_cacheTags;
204
205 NODE* m_world;
206 int m_collisionKindMask;
207 int m_effortLevel;
208
209 VECTOR2I m_preservedVertex;
210 std::pair<int, int> m_restrictedVertexRange;
211 BOX2I m_restrictArea;
212 bool m_restrictAreaIsStrict;
213};
214
215
217{
218public:
219 OPT_CONSTRAINT( NODE* aWorld ) :
220 m_world( aWorld )
221 {
222 m_priority = 0;
223 };
224
225 virtual ~OPT_CONSTRAINT()
226 {
227 };
228
229 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
230 const SHAPE_LINE_CHAIN& aCurrentPath,
231 const SHAPE_LINE_CHAIN& aReplacement ) = 0;
232
233 int GetPriority() const { return m_priority; }
234 void SetPriority( int aPriority ) { m_priority = aPriority; }
235
236protected:
237 NODE* m_world;
238 int m_priority;
239};
240
242{
243public:
244 ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) :
245 OPT_CONSTRAINT( aWorld ),
246 m_entryDirectionMask( aEntryDirectionMask ),
247 m_exitDirectionMask( aExitDirectionMask )
248 {
249
250 }
251
252 virtual ~ANGLE_CONSTRAINT_45() {};
253
254 virtual bool Check ( int aVertex1, int aVertex2, const LINE* aOriginLine,
255 const SHAPE_LINE_CHAIN& aCurrentPath,
256 const SHAPE_LINE_CHAIN& aReplacement ) override;
257
258private:
259 int m_entryDirectionMask;
260 int m_exitDirectionMask;
261};
262
264{
265public:
266 AREA_CONSTRAINT( NODE* aWorld, const BOX2I& aAllowedArea, bool aAllowedAreaStrict ) :
267 OPT_CONSTRAINT( aWorld ),
268 m_allowedArea ( aAllowedArea ),
269 m_allowedAreaStrict ( aAllowedAreaStrict )
270 {
271 };
272
273 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
274 const SHAPE_LINE_CHAIN& aCurrentPath,
275 const SHAPE_LINE_CHAIN& aReplacement ) override;
276
277private:
278 BOX2I m_allowedArea;
279 bool m_allowedAreaStrict;
280};
281
282
284{
285public:
286 KEEP_TOPOLOGY_CONSTRAINT( NODE* aWorld ) :
287 OPT_CONSTRAINT( aWorld )
288 {
289 };
290
291 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
292 const SHAPE_LINE_CHAIN& aCurrentPath,
293 const SHAPE_LINE_CHAIN& aReplacement ) override;
294};
295
296
298{
299public:
300 PRESERVE_VERTEX_CONSTRAINT( NODE* aWorld, const VECTOR2I& aV ) :
301 OPT_CONSTRAINT( aWorld ),
302 m_v( aV )
303 {
304 };
305
306 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
307 const SHAPE_LINE_CHAIN& aCurrentPath,
308 const SHAPE_LINE_CHAIN& aReplacement ) override;
309private:
310 VECTOR2I m_v;
311};
312
313
315{
316public:
317 RESTRICT_VERTEX_RANGE_CONSTRAINT( NODE* aWorld, int aStart, int aEnd ) :
318 OPT_CONSTRAINT( aWorld ),
319 m_start( aStart ),
320 m_end( aEnd )
321 {
322 };
323
324 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
325 const SHAPE_LINE_CHAIN& aCurrentPath,
326 const SHAPE_LINE_CHAIN& aReplacement ) override;
327private:
328 int m_start;
329 int m_end;
330};
331
332
334{
335public:
336 CORNER_COUNT_LIMIT_CONSTRAINT( NODE* aWorld, int aMinCorners, int aMaxCorners,
337 int aAngleMask ) :
338 OPT_CONSTRAINT( aWorld ),
339 m_minCorners( aMinCorners ),
340 m_maxCorners( aMaxCorners ),
341 m_angleMask( aAngleMask )
342 {
343 };
344
345 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
346 const SHAPE_LINE_CHAIN& aCurrentPath,
347 const SHAPE_LINE_CHAIN& aReplacement ) override;
348
349private:
350 int m_minCorners;
351 int m_maxCorners;
352 int m_angleMask;
353};
354
355
356
357};
358
359#endif // __PNS_OPTIMIZER_H
Definition pns_optimizer.h:242
Definition pns_optimizer.h:264
Definition pns_optimizer.h:334
Calculate the cost of a given line, taking corner angles and total length into account.
Definition pns_optimizer.h:49
Basic class for a differential pair.
Definition pns_diff_pair.h:235
Definition pns_optimizer.h:284
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:61
Keep the router "world" - i.e.
Definition pns_node.h:148
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition pns_optimizer.h:95
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
Definition pns_optimizer.cpp:121
OptimizationEffort
Definition pns_optimizer.h:98
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
Definition pns_optimizer.h:108
@ SMART_PADS
Reroute pad exits.
Definition pns_optimizer.h:100
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
Definition pns_optimizer.h:102
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
Definition pns_optimizer.h:106
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
Definition pns_optimizer.h:101
Definition pns_optimizer.h:217
Definition pns_optimizer.h:298
Definition pns_optimizer.h:315
Definition seg.h:41
Definition shape_index_list.h:43
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition shape_line_chain.h:81
An abstract shape on 2D plane.
Definition shape.h:117