Horizon
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 
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:
51  COST_ESTIMATOR() :
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 
77 private:
78  double m_lengthCost;
79  int m_cornerCost;
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,
103  KEEP_TOPOLOGY = 0x10,
104  PRESERVE_VERTEX = 0x20,
105  RESTRICT_VERTEX_RANGE = 0x40,
106  MERGE_COLINEAR = 0x80,
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 
159 private:
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 
200 private:
201  SHAPE_INDEX_LIST<ITEM*> m_cache;
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 {
218 public:
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 
236 protected:
237  NODE* m_world;
238  int m_priority;
239 };
240 
242 {
243 public:
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 
258 private:
259  int m_entryDirectionMask;
260  int m_exitDirectionMask;
261 };
262 
264 {
265 public:
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 
277 private:
278  BOX2I m_allowedArea;
279  bool m_allowedAreaStrict;
280 };
281 
282 
284 {
285 public:
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 {
299 public:
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;
309 private:
310  VECTOR2I m_v;
311 };
312 
313 
315 {
316 public:
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;
327 private:
328  int m_start;
329  int m_end;
330 };
331 
332 
334 {
335 public:
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 
349 private:
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