KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_optimizer.h
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
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
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
59 {}
60
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:
80};
81
82
95{
96public:
98 {
100 SMART_PADS = 0x02,
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 {
141 }
142
143 void SetRestrictVertexRange( int aStart, int aEnd )
144 {
145 m_restrictedVertexRange.first = aStart;
146 m_restrictedVertexRange.second = aEnd;
148 }
149
150 void SetRestrictArea( const BOX2I& aArea, bool aStrict = true )
151 {
152 m_restrictArea = aArea;
153 m_restrictAreaIsStrict = aStrict;
154 }
155
156private:
157 static const int MaxCachedItems = 256;
158
159 typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
160
161 struct CACHE_VISITOR;
162
164 {
167 };
168
169
170 void addConstraint ( OPT_CONSTRAINT *aConstraint );
171 bool mergeObtuse( LINE* aLine );
172 bool mergeFull( LINE* aLine );
173 bool mergeColinear( LINE* aLine );
174 bool runSmartPads( LINE* aLine );
175 bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
176 bool fanoutCleanup( LINE * aLine );
177 bool mergeDpSegments( DIFF_PAIR *aPair );
178 bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
179
180 bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
181 bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
182
183 void cacheAdd( ITEM* aItem, bool aIsStatic );
184 void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
185
186 bool checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
187 const SHAPE_LINE_CHAIN& aCurrentPath,
188 const SHAPE_LINE_CHAIN& aReplacement );
189
190 BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
191 BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
192 BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
193 BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
194
195 int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
196
197 ITEM* findPadOrVia( int aLayer, NET_HANDLE aNet, const VECTOR2I& aP ) const;
198
199private:
201 std::vector<OPT_CONSTRAINT*> m_constraints;
202 std::unordered_map<ITEM*, CACHED_ITEM> m_cacheTags;
203
207
209 std::pair<int, int> m_restrictedVertexRange;
212};
213
214
216{
217public:
218 OPT_CONSTRAINT( NODE* aWorld ) :
219 m_world( aWorld )
220 {
221 m_priority = 0;
222 };
223
225 {
226 };
227
228 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
229 const SHAPE_LINE_CHAIN& aCurrentPath,
230 const SHAPE_LINE_CHAIN& aReplacement ) = 0;
231
232 int GetPriority() const { return m_priority; }
233 void SetPriority( int aPriority ) { m_priority = aPriority; }
234
235protected:
238};
239
241{
242public:
243 ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) :
244 OPT_CONSTRAINT( aWorld ),
245 m_entryDirectionMask( aEntryDirectionMask ),
246 m_exitDirectionMask( aExitDirectionMask )
247 {
248
249 }
250
252
253 virtual bool Check ( int aVertex1, int aVertex2, const LINE* aOriginLine,
254 const SHAPE_LINE_CHAIN& aCurrentPath,
255 const SHAPE_LINE_CHAIN& aReplacement ) override;
256
257private:
260};
261
263{
264public:
265 AREA_CONSTRAINT( NODE* aWorld, const BOX2I& aAllowedArea, bool aAllowedAreaStrict ) :
266 OPT_CONSTRAINT( aWorld ),
267 m_allowedArea ( aAllowedArea ),
268 m_allowedAreaStrict ( aAllowedAreaStrict )
269 {
270 };
271
272 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
273 const SHAPE_LINE_CHAIN& aCurrentPath,
274 const SHAPE_LINE_CHAIN& aReplacement ) override;
275
276private:
279};
280
281
283{
284public:
286 OPT_CONSTRAINT( aWorld )
287 {
288 };
289
290 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
291 const SHAPE_LINE_CHAIN& aCurrentPath,
292 const SHAPE_LINE_CHAIN& aReplacement ) override;
293};
294
295
297{
298public:
300 OPT_CONSTRAINT( aWorld ),
301 m_v( aV )
302 {
303 };
304
305 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
306 const SHAPE_LINE_CHAIN& aCurrentPath,
307 const SHAPE_LINE_CHAIN& aReplacement ) override;
308private:
310};
311
312
314{
315public:
316 RESTRICT_VERTEX_RANGE_CONSTRAINT( NODE* aWorld, int aStart, int aEnd ) :
317 OPT_CONSTRAINT( aWorld ),
318 m_start( aStart ),
319 m_end( aEnd )
320 {
321 };
322
323 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
324 const SHAPE_LINE_CHAIN& aCurrentPath,
325 const SHAPE_LINE_CHAIN& aReplacement ) override;
326private:
328 int m_end;
329};
330
331
333{
334public:
335 CORNER_COUNT_LIMIT_CONSTRAINT( NODE* aWorld, int aMinCorners, int aMaxCorners,
336 int aAngleMask ) :
337 OPT_CONSTRAINT( aWorld ),
338 m_minCorners( aMinCorners ),
339 m_maxCorners( aMaxCorners ),
340 m_angleMask( aAngleMask )
341 {
342 };
343
344 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
345 const SHAPE_LINE_CHAIN& aCurrentPath,
346 const SHAPE_LINE_CHAIN& aReplacement ) override;
347
348private:
352};
353
354
355
356};
357
358#endif // __PNS_OPTIMIZER_H
Definition: line.h:36
ANGLE_CONSTRAINT_45(NODE *aWorld, int aEntryDirectionMask=-1, int aExitDirectionMask=-1)
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
AREA_CONSTRAINT(NODE *aWorld, const BOX2I &aAllowedArea, bool aAllowedAreaStrict)
CORNER_COUNT_LIMIT_CONSTRAINT(NODE *aWorld, int aMinCorners, int aMaxCorners, int aAngleMask)
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Calculate the cost of a given line, taking corner angles and total length into account.
Definition: pns_optimizer.h:49
void Replace(const LINE &aOldLine, const LINE &aNewLine)
void Remove(const LINE &aLine)
void Add(const LINE &aLine)
COST_ESTIMATOR(const COST_ESTIMATOR &aB)
Definition: pns_optimizer.h:56
double GetLengthCost() const
Definition: pns_optimizer.h:74
static int CornerCost(const SEG &aA, const SEG &aB)
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
double GetCornerCost() const
Definition: pns_optimizer.h:75
Basic class for a differential pair.
Base class for PNS router board items.
Definition: pns_item.h:97
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
KEEP_TOPOLOGY_CONSTRAINT(NODE *aWorld)
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:207
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:95
void SetPreserveVertex(const VECTOR2I &aV)
std::pair< int, int > m_restrictedVertexRange
std::vector< OPT_CONSTRAINT * > m_constraints
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
void SetWorld(NODE *aNode)
bool mergeColinear(LINE *aLine)
void cacheAdd(ITEM *aItem, bool aIsStatic)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
bool m_restrictAreaIsStrict
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
bool fanoutCleanup(LINE *aLine)
static const int MaxCachedItems
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
bool mergeFull(LINE *aLine)
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void SetRestrictVertexRange(int aStart, int aEnd)
void CacheRemove(ITEM *aItem)
bool mergeObtuse(LINE *aLine)
void SetCollisionMask(int aMask)
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
bool runSmartPads(LINE *aLine)
bool mergeDpSegments(DIFF_PAIR *aPair)
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
ITEM * findPadOrVia(int aLayer, NET_HANDLE aNet, const VECTOR2I &aP) const
void SetEffortLevel(int aEffort)
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
VECTOR2I m_preservedVertex
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void addConstraint(OPT_CONSTRAINT *aConstraint)
void ClearCache(bool aStaticOnly=false)
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
SHAPE_INDEX_LIST< ITEM * > m_cache
virtual ~OPT_CONSTRAINT()
OPT_CONSTRAINT(NODE *aWorld)
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)=0
void SetPriority(int aPriority)
int GetPriority() const
PRESERVE_VERTEX_CONSTRAINT(NODE *aWorld, const VECTOR2I &aV)
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
RESTRICT_VERTEX_RANGE_CONSTRAINT(NODE *aWorld, int aStart, int aEnd)
Definition: seg.h:42
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
An abstract shape on 2D plane.
Definition: shape.h:126
Push and Shove diff pair dimensions (gap) settings dialog.
void * NET_HANDLE
Definition: pns_item.h:54
@ DIFF_PAIR
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:691