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 The 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
20 * along with this program. If not, see <https://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
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:
114
115 OPTIMIZER( NODE* aWorld );
116 ~OPTIMIZER();
117
119 static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld,
120 const VECTOR2I& aV = VECTOR2I(0, 0) );
121
122 bool Optimize( const LINE* aLine, LINE* aResult = nullptr, LINE* aRoot = nullptr );
123 bool Optimize( DIFF_PAIR* aPair );
124
125
126 void SetWorld( NODE* aNode ) { m_world = aNode; }
127 void CacheRemove( ITEM* aItem );
128 void ClearCache( bool aStaticOnly = false );
129
130 void SetCollisionMask( int aMask )
131 {
132 m_collisionKindMask = aMask;
133 }
134
135 void SetEffortLevel( int aEffort )
136 {
137 m_effortLevel = aEffort;
138 }
139
140 void SetPreserveSegments( const std::vector<SEG>& aSegs )
141 {
142 m_preservedSegments = aSegs;
144 }
145
151
152 void SetRestrictVertexRange( int aStart, int aEnd )
153 {
154 m_restrictedVertexRange.first = aStart;
155 m_restrictedVertexRange.second = aEnd;
157 }
158
159 void SetRestrictArea( const BOX2I& aArea, bool aStrict = true )
160 {
161 m_restrictArea = aArea;
162 m_restrictAreaIsStrict = aStrict;
164 }
165
166private:
167 static const int MaxCachedItems = 256;
168
169 typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
170
171 struct CACHE_VISITOR;
172
174 {
177 };
178
179
180 void addConstraint ( OPT_CONSTRAINT *aConstraint );
181 bool mergeObtuse( LINE* aLine );
182 bool mergeFull( LINE* aLine );
183 bool mergeColinear( LINE* aLine );
184 bool runSmartPads( LINE* aLine );
185 bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
186 bool fanoutCleanup( LINE * aLine );
187 bool dragFixCorners( LINE* aLine );
188 bool dragFixCorner( LINE* aLine, int aVIdx );
189 bool mergeDpSegments( DIFF_PAIR *aPair );
190 bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
191
192 bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
193 bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
194
195 void cacheAdd( ITEM* aItem, bool aIsStatic );
196 void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
197
198 bool checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
199 const SHAPE_LINE_CHAIN& aCurrentPath,
200 const SHAPE_LINE_CHAIN& aReplacement );
201
202 BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
203 BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
204 BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
205 BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
206
207 int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
208
209 ITEM* findPadOrVia( int aLayer, NET_HANDLE aNet, const VECTOR2I& aP ) const;
210
211private:
213 std::vector<OPT_CONSTRAINT*> m_constraints;
214 std::unordered_map<ITEM*, CACHED_ITEM> m_cacheTags;
215
219
221 std::vector<SEG> m_preservedSegments;
222 std::pair<int, int> m_restrictedVertexRange;
225};
226
227
229{
230public:
231 OPT_CONSTRAINT( NODE* aWorld ) :
232 m_world( aWorld )
233 {
234 m_priority = 0;
235 };
236
238 {
239 };
240
241 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
242 const SHAPE_LINE_CHAIN& aCurrentPath,
243 const SHAPE_LINE_CHAIN& aReplacement ) = 0;
244
245 int GetPriority() const { return m_priority; }
246 void SetPriority( int aPriority ) { m_priority = aPriority; }
247
248protected:
251};
252
254{
255public:
256 ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) :
257 OPT_CONSTRAINT( aWorld ),
258 m_entryDirectionMask( aEntryDirectionMask ),
259 m_exitDirectionMask( aExitDirectionMask )
260 {
261
262 }
263
265
266 virtual bool Check ( int aVertex1, int aVertex2, const LINE* aOriginLine,
267 const SHAPE_LINE_CHAIN& aCurrentPath,
268 const SHAPE_LINE_CHAIN& aReplacement ) override;
269
270private:
273};
274
276{
277public:
278 AREA_CONSTRAINT( NODE* aWorld, const BOX2I& aAllowedArea, bool aAllowedAreaStrict ) :
279 OPT_CONSTRAINT( aWorld ),
280 m_allowedArea ( aAllowedArea )
281 {
282 };
283
284 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
285 const SHAPE_LINE_CHAIN& aCurrentPath,
286 const SHAPE_LINE_CHAIN& aReplacement ) override;
287
288private:
290};
291
292
294{
295public:
297 OPT_CONSTRAINT( aWorld )
298 {
299 };
300
301 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
302 const SHAPE_LINE_CHAIN& aCurrentPath,
303 const SHAPE_LINE_CHAIN& aReplacement ) override;
304};
305
306
308{
309public:
311 OPT_CONSTRAINT( aWorld ),
312 m_v( aV )
313 {
314 };
315
316 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
317 const SHAPE_LINE_CHAIN& aCurrentPath,
318 const SHAPE_LINE_CHAIN& aReplacement ) override;
319private:
321};
322
323
325{
326public:
327 PRESERVE_SEGMENTS_CONSTRAINT( NODE* aWorld, const std::vector<SEG>& aSegs ) :
328 OPT_CONSTRAINT( aWorld ),
329 m_segs( aSegs )
330 {
331 };
332
333 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
334 const SHAPE_LINE_CHAIN& aCurrentPath,
335 const SHAPE_LINE_CHAIN& aReplacement ) override;
336private:
337 std::vector<SEG> m_segs;
338};
339
340
342{
343public:
344 RESTRICT_VERTEX_RANGE_CONSTRAINT( NODE* aWorld, int aStart, int aEnd ) :
345 OPT_CONSTRAINT( aWorld )
346 {
347 };
348
349 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
350 const SHAPE_LINE_CHAIN& aCurrentPath,
351 const SHAPE_LINE_CHAIN& aReplacement ) override;
352};
353
354
356{
357public:
358 CORNER_COUNT_LIMIT_CONSTRAINT( NODE* aWorld, int aMinCorners, int aMaxCorners,
359 int aAngleMask ) :
360 OPT_CONSTRAINT( aWorld ),
361 m_minCorners( aMinCorners ),
362 m_angleMask( aAngleMask )
363 {
364 };
365
366 virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
367 const SHAPE_LINE_CHAIN& aCurrentPath,
368 const SHAPE_LINE_CHAIN& aReplacement ) override;
369
370private:
373};
374
375
377{
378public:
380 OPT_CONSTRAINT( aWorld )
381 {
382 }
383
384 bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
385 const SHAPE_LINE_CHAIN& aCurrentPath,
386 const SHAPE_LINE_CHAIN& aReplacement ) override;
387};
388
389
390
391};
392
393#endif // __PNS_OPTIMIZER_H
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
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.
void Replace(const LINE &aOldLine, const LINE &aNewLine)
void Remove(const LINE &aLine)
void Add(const LINE &aLine)
COST_ESTIMATOR(const COST_ESTIMATOR &aB)
double GetLengthCost() const
static int CornerCost(const SEG &aA, const SEG &aB)
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
double GetCornerCost() const
Basic class for a differential pair.
Base class for PNS router board items.
Definition pns_item.h:98
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition pns_joint.h:43
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
Keep the router "world" - i.e.
Definition pns_node.h:274
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
OBTUSE_ONLY_CONSTRAINT(NODE *aWorld)
std::vector< SEG > m_preservedSegments
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)
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
bool dragFixCorners(LINE *aLine)
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
void SetPreserveSegments(const std::vector< SEG > &aSegs)
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)
OPTIMIZER(NODE *aWorld)
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)
bool dragFixCorner(LINE *aLine, int aVIdx)
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))
A quick shortcut to optimize a line without creating and setting up an optimizer.
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.
@ MERGE_COLINEAR
Merge co-linear segments.
@ PRESERVE_SEGMENTS
do not remove segments from a restricted set
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
@ DP_PAD_EXITS
fit coupled gateways for pad/via diff pair connections
@ REQUIRE_OBTUSE_ANGLES
Try to prevent 90-degree or acute corners in a drag.
SHAPE_INDEX_LIST< ITEM * > m_cache
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
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
PRESERVE_SEGMENTS_CONSTRAINT(NODE *aWorld, const std::vector< SEG > &aSegs)
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:38
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:124
Push and Shove diff pair dimensions (gap) settings dialog.
void * NET_HANDLE
Definition pns_item.h:55
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708