KiCad PCB EDA Suite
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-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 
31 
32 #include "range.h"
33 
34 
35 namespace PNS {
36 
37 class NODE;
38 class ROUTER;
39 class LINE;
40 class DIFF_PAIR;
41 class ITEM;
42 class JOINT;
43 class OPT_CONSTRAINT;
44 
49 {
50 public:
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 
77 private:
78  double m_lengthCost;
80 };
81 
82 
94 class OPTIMIZER
95 {
96 public:
98  {
99  MERGE_SEGMENTS = 0x01,
100  SMART_PADS = 0x02,
101  MERGE_OBTUSE = 0x04,
102  FANOUT_CLEANUP = 0x08,
106  MERGE_COLINEAR = 0x80,
108  };
109 
110  OPTIMIZER( NODE* aWorld );
111  ~OPTIMIZER();
112 
114  static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld,
115  const VECTOR2I aV = VECTOR2I(0, 0) );
116 
117  bool Optimize( LINE* aLine, LINE* aResult = NULL );
118  bool Optimize( DIFF_PAIR* aPair );
119 
120 
121  void SetWorld( NODE* aNode ) { m_world = aNode; }
122  void CacheRemove( ITEM* aItem );
123  void ClearCache( bool aStaticOnly = false );
124 
125  void SetCollisionMask( int aMask )
126  {
127  m_collisionKindMask = aMask;
128  }
129 
130  void SetEffortLevel( int aEffort )
131  {
132  m_effortLevel = aEffort;
133  }
134 
135  void SetPreserveVertex( const VECTOR2I& aV )
136  {
137  m_preservedVertex = aV;
139  }
140 
141  void SetRestrictVertexRange( int aStart, int aEnd )
142  {
143  m_restrictedVertexRange.first = aStart;
144  m_restrictedVertexRange.second = aEnd;
146  }
147 
148  void SetRestrictArea( const BOX2I& aArea, bool aStrict = true )
149  {
150  m_restrictArea = aArea;
151  m_restrictAreaIsStrict = aStrict;
152  }
153 
154  void ClearConstraints();
155  void AddConstraint ( OPT_CONSTRAINT *aConstraint );
156 
157 private:
158  static const int MaxCachedItems = 256;
159 
160  typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
161 
162  struct CACHE_VISITOR;
163 
164  struct CACHED_ITEM
165  {
166  int m_hits;
168  };
169 
170  bool mergeObtuse( LINE* aLine );
171  bool mergeFull( LINE* aLine );
172  bool mergeColinear( LINE* aLine );
173  bool runSmartPads( LINE* aLine );
174  bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
175  bool fanoutCleanup( LINE * aLine );
176  bool mergeDpSegments( DIFF_PAIR *aPair );
177  bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
178 
179  bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
180  bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
181 
182  void cacheAdd( ITEM* aItem, bool aIsStatic );
183  void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
184 
185  bool checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine,
186  const SHAPE_LINE_CHAIN& aCurrentPath,
187  const SHAPE_LINE_CHAIN& aReplacement );
188 
189  BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
190  BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
191  BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
192  BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
193 
194  int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
195 
196  ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
197 
198 private:
200  std::vector<OPT_CONSTRAINT*> m_constraints;
201  std::unordered_map<ITEM*, CACHED_ITEM> m_cacheTags;
202 
206 
208  std::pair<int, int> m_restrictedVertexRange;
211 };
212 
213 
215 {
216 public:
217  OPT_CONSTRAINT( NODE* aWorld ) :
218  m_world( aWorld )
219  {
220  m_priority = 0;
221  };
222 
223  virtual ~OPT_CONSTRAINT()
224  {
225  };
226 
227  virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
228  const SHAPE_LINE_CHAIN& aCurrentPath,
229  const SHAPE_LINE_CHAIN& aReplacement ) = 0;
230 
231  int GetPriority() const { return m_priority; }
232  void SetPriority( int aPriority ) { m_priority = aPriority; }
233 
234 protected:
237 };
238 
240 {
241 public:
242  ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) :
243  OPT_CONSTRAINT( aWorld ),
244  m_entryDirectionMask( aEntryDirectionMask ),
245  m_exitDirectionMask( aExitDirectionMask )
246  {
247 
248  }
249 
250  virtual ~ANGLE_CONSTRAINT_45() {};
251 
252  virtual bool Check ( int aVertex1, int aVertex2, const LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) override;
253 
254 private:
257 };
258 
260 {
261 public:
262  AREA_CONSTRAINT( NODE* aWorld, const BOX2I& aAllowedArea, bool aAllowedAreaStrict ) :
263  OPT_CONSTRAINT( aWorld ),
264  m_allowedArea ( aAllowedArea ),
265  m_allowedAreaStrict ( aAllowedAreaStrict )
266  {
267  };
268 
269  bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
270  const SHAPE_LINE_CHAIN& aCurrentPath,
271  const SHAPE_LINE_CHAIN& aReplacement ) override;
272 
273 private:
276 };
277 
278 
280 {
281 public:
283  OPT_CONSTRAINT( aWorld )
284  {
285  };
286 
287  bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
288  const SHAPE_LINE_CHAIN& aCurrentPath,
289  const SHAPE_LINE_CHAIN& aReplacement ) override;
290 };
291 
292 
294 {
295 public:
296  PRESERVE_VERTEX_CONSTRAINT( NODE* aWorld, const VECTOR2I& aV ) :
297  OPT_CONSTRAINT( aWorld ),
298  m_v( aV )
299  {
300  };
301 
302  bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
303  const SHAPE_LINE_CHAIN& aCurrentPath,
304  const SHAPE_LINE_CHAIN& aReplacement ) override;
305 private:
307 };
308 
309 
311 {
312 public:
313  RESTRICT_VERTEX_RANGE_CONSTRAINT( NODE* aWorld, int aStart, int aEnd ) :
314  OPT_CONSTRAINT( aWorld ),
315  m_start( aStart ),
316  m_end( aEnd )
317  {
318  };
319 
320  virtual bool Check( int aVertex1, int aVertex2, const LINE* aOriginLine,
321  const SHAPE_LINE_CHAIN& aCurrentPath,
322  const SHAPE_LINE_CHAIN& aReplacement ) override;
323 private:
324  int m_start;
325  int m_end;
326 };
327 
328 
329 };
330 
331 #endif // __PNS_OPTIMIZER_H
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
Base class for PNS router board items.
Definition: pns_item.h:55
virtual ~OPT_CONSTRAINT()
int GetPriority() const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
void SetRestrictVertexRange(int aStart, int aEnd)
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
Keep the router "world" - i.e.
Definition: pns_node.h:145
void CacheRemove(ITEM *aItem)
ANGLE_CONSTRAINT_45(NODE *aWorld, int aEntryDirectionMask=-1, int aExitDirectionMask=-1)
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
COST_ESTIMATOR(const COST_ESTIMATOR &aB)
Definition: pns_optimizer.h:56
~OPTIMIZER()
A quick shortcut to optimize a line without creating and setting up an optimizer.
Simplify pad-pad and pad-via connections if possible.
AREA_CONSTRAINT(NODE *aWorld, const BOX2I &aAllowedArea, bool aAllowedAreaStrict)
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
Define a general 2D-vector/point.
Definition: vector2d.h:61
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
void Add(const LINE &aLine)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
bool runSmartPads(LINE *aLine)
KEEP_TOPOLOGY_CONSTRAINT(NODE *aWorld)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
bool mergeFull(LINE *aLine)
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
double GetCornerCost() const
Definition: pns_optimizer.h:75
bool m_restrictAreaIsStrict
void SetCollisionMask(int aMask)
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
void AddConstraint(OPT_CONSTRAINT *aConstraint)
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
#define NULL
void SetWorld(NODE *aNode)
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)=0
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
bool mergeDpSegments(DIFF_PAIR *aPair)
void SetPreserveVertex(const VECTOR2I &aV)
bool mergeObtuse(LINE *aLine)
An abstract shape on 2D plane.
Definition: shape.h:116
void Remove(const LINE &aLine)
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
std::vector< OPT_CONSTRAINT * > m_constraints
static const int MaxCachedItems
Definition: seg.h:41
OPTIMIZER(NODE *aWorld)
Optimizer.
VECTOR2I m_preservedVertex
DIFF_PAIR.
void cacheAdd(ITEM *aItem, bool aIsStatic)
double GetLengthCost() const
Definition: pns_optimizer.h:74
RESTRICT_VERTEX_RANGE_CONSTRAINT(NODE *aWorld, int aStart, int aEnd)
bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
void SetPriority(int aPriority)
Reduce corner cost by merging obtuse segments.
bool IsBetter(const COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
bool fanoutCleanup(LINE *aLine)
SHAPE_LINE_CHAIN.
bool mergeColinear(LINE *aLine)
PRESERVE_VERTEX_CONSTRAINT(NODE *aWorld, const VECTOR2I &aV)
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
virtual bool Check(int aVertex1, int aVertex2, const LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
void Replace(const LINE &aOldLine, const LINE &aNewLine)
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
Merge co-linear segments.
SHAPE_INDEX_LIST< ITEM * > m_cache
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
void SetEffortLevel(int aEffort)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
Calculate the cost of a given line, taking corner angles and total length into account.
Definition: pns_optimizer.h:48
Push and Shove diff pair dimensions (gap) settings dialog.
std::pair< int, int > m_restrictedVertexRange
void ClearCache(bool aStaticOnly=false)
Reroute pad exits.
OPT_CONSTRAINT(NODE *aWorld)