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 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7  *
8  * This program is free software: you can redistribute it and/or modify it
9  * under the terms of the GNU General Public License as published by the
10  * Free Software Foundation, either version 3 of the License, or (at your
11  * option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful, but
14  * WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License along
19  * with this program. If not, see <http://www.gnu.org/licenses/>.
20  */
21 
22 #ifndef __PNS_OPTIMIZER_H
23 #define __PNS_OPTIMIZER_H
24 
25 #include <unordered_map>
26 #include <memory>
27 
30 
31 #include "range.h"
32 
33 
34 namespace PNS {
35 
36 class NODE;
37 class ROUTER;
38 class LINE;
39 class DIFF_PAIR;
40 class ITEM;
41 class JOINT;
42 
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( LINE& aLine );
68  void Remove( LINE& aLine );
69  void Replace( LINE& aOldLine, LINE& aNewLine );
70 
71  bool IsBetter( 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 class OPT_CONSTRAINT;
83 
95 class OPTIMIZER
96 {
97 public:
99  {
101  SMART_PADS = 0x02,
102  MERGE_OBTUSE = 0x04,
106  };
107 
108  OPTIMIZER( NODE* aWorld );
109  ~OPTIMIZER();
110 
112  static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld, const VECTOR2I aV = VECTOR2I(0, 0) );
113 
114  bool Optimize( LINE* aLine, LINE* aResult = NULL );
115  bool Optimize( DIFF_PAIR* aPair );
116 
117 
118  void SetWorld( NODE* aNode ) { m_world = aNode; }
119  void CacheStaticItem( ITEM* aItem );
120  void CacheRemove( ITEM* aItem );
121  void ClearCache( bool aStaticOnly = false );
122 
123  void SetCollisionMask( int aMask )
124  {
125  m_collisionKindMask = aMask;
126  }
127 
128  void SetEffortLevel( int aEffort )
129  {
130  m_effortLevel = aEffort;
131  }
132 
133 
134  void SetRestrictArea( const BOX2I& aArea )
135  {
136  m_restrictArea = aArea;
137  m_restrictAreaActive = true;
138  }
139 
140  void ClearConstraints();
141  void AddConstraint ( OPT_CONSTRAINT *aConstraint );
142 
143  bool extractPadGrids( std::vector<JOINT*>& aPadJoints );
144  void BuildPadGrids();
145 
146 private:
147  static const int MaxCachedItems = 256;
148 
149  typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
150 
151  struct CACHE_VISITOR;
152 
153  struct CACHED_ITEM
154  {
155  int m_hits;
157  };
158 
159  bool mergeObtuse( LINE* aLine );
160  bool mergeFull( LINE* aLine );
161  bool removeUglyCorners( LINE* aLine );
162  bool runSmartPads( LINE* aLine );
163  bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
164  bool fanoutCleanup( LINE * aLine );
165  bool mergeDpSegments( DIFF_PAIR *aPair );
166  bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
167 
168  bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
169  bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
170 
171  void cacheAdd( ITEM* aItem, bool aIsStatic );
172  void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
173 
174  bool checkConstraints( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement );
175 
176 
177 
178  BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
179  BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
180  BREAKOUT_LIST ovalBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
181  BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
182  BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
183 
184  int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
185 
186  ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
187 
189 
190  std::vector<OPT_CONSTRAINT*> m_constraints;
191  typedef std::unordered_map<ITEM*, CACHED_ITEM> CachedItemTags;
197 
200 };
201 
203 {
204 public:
205  OPT_CONSTRAINT( NODE* aWorld ) :
206  m_world( aWorld )
207  {
208  m_priority = 0;
209  };
210 
211  virtual ~OPT_CONSTRAINT() {};
212 
213  virtual bool Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) = 0;
214 
215  int GetPriority() const
216  {
217  return m_priority;
218  }
219 
220  void SetPriority( int aPriority )
221  {
222  m_priority = aPriority;
223  }
224 
225 protected:
228 };
229 
231 {
232 public:
233  ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) :
234  OPT_CONSTRAINT( aWorld ),
235  m_entryDirectionMask( aEntryDirectionMask ),
236  m_exitDirectionMask( aExitDirectionMask )
237  {
238 
239  }
240 
241  virtual ~ANGLE_CONSTRAINT_45() {};
242 
243  virtual bool Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) override;
244 
245 private:
248 };
249 
251 {
252 public:
253  AREA_CONSTRAINT( NODE* aWorld, const BOX2I& aAllowedArea ) :
254  OPT_CONSTRAINT( aWorld ),
255  m_allowedArea ( aAllowedArea ) {};
256 
257  virtual bool Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) override;
258 
259 private:
261 
262 };
263 
265 {
266 public:
268  OPT_CONSTRAINT( aWorld )
269  {};
270 
271  virtual bool Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) override;
272 };
273 
275 {
276 public:
277  PRESERVE_VERTEX_CONSTRAINT( NODE* aWorld, const VECTOR2I& aV ) :
278  OPT_CONSTRAINT( aWorld ),
279  m_v( aV )
280  {};
281 
282  virtual bool Check ( int aVertex1, int aVertex2, LINE* aOriginLine, const SHAPE_LINE_CHAIN& aCurrentPath, const SHAPE_LINE_CHAIN& aReplacement ) override;
283 private:
284 
286 };
287 
288 
289 };
290 
291 #endif
bool m_restrictAreaActive
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
ITEM.
Definition: pns_item.h:53
virtual ~OPT_CONSTRAINT()
void CacheStaticItem(ITEM *aItem)
int GetPriority() const
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
AREA_CONSTRAINT(NODE *aWorld, const BOX2I &aAllowedArea)
NODE.
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)
bool removeUglyCorners(LINE *aLine)
void Replace(LINE &aOldLine, LINE &aNewLine)
COST_ESTIMATOR(const COST_ESTIMATOR &aB)
Definition: pns_optimizer.h:56
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)=0
BREAKOUT_LIST ovalBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
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:594
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
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, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
#define NULL
void SetWorld(NODE *aNode)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
a quick shortcut to optmize a line without creating and setting up an optimizer
bool mergeDpSegments(DIFF_PAIR *aPair)
bool mergeObtuse(LINE *aLine)
SHAPE.
Definition: shape.h:60
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
CachedItemTags m_cacheTags
std::vector< OPT_CONSTRAINT * > m_constraints
void BuildPadGrids()
static const int MaxCachedItems
Definition: seg.h:39
OPTIMIZER(NODE *aWorld)
Optimizer.
DIFF_PAIR.
void cacheAdd(ITEM *aItem, bool aIsStatic)
double GetLengthCost() const
Definition: pns_optimizer.h:74
void SetPriority(int aPriority)
bool extractPadGrids(std::vector< JOINT * > &aPadJoints)
bool fanoutCleanup(LINE *aLine)
SHAPE_LINE_CHAIN.
PRESERVE_VERTEX_CONSTRAINT(NODE *aWorld, const VECTOR2I &aV)
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
void Add(LINE &aLine)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
OPTIMIZER.
Definition: pns_optimizer.h:95
SHAPE_INDEX_LIST< ITEM * > m_cache
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
void SetEffortLevel(int aEffort)
virtual bool Check(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement) override
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void SetRestrictArea(const BOX2I &aArea)
std::unordered_map< ITEM *, CACHED_ITEM > CachedItemTags
COST_ESTIMATOR.
Definition: pns_optimizer.h:48
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(LINE &aLine)
void ClearCache(bool aStaticOnly=false)
bool IsBetter(COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
OPT_CONSTRAINT(NODE *aWorld)