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 namespace PNS {
34 
35 class NODE;
36 class ROUTER;
37 class LINE;
38 class DIFF_PAIR;
39 
46 {
47 public:
49  m_lengthCost( 0 ),
50  m_cornerCost( 0 )
51  {}
52 
56  {}
57 
59 
60  static int CornerCost( const SEG& aA, const SEG& aB );
61  static int CornerCost( const SHAPE_LINE_CHAIN& aLine );
62  static int CornerCost( const LINE& aLine );
63 
64  void Add( LINE& aLine );
65  void Remove( LINE& aLine );
66  void Replace( LINE& aOldLine, LINE& aNewLine );
67 
68  bool IsBetter( COST_ESTIMATOR& aOther, double aLengthTolerance,
69  double aCornerTollerace ) const;
70 
71  double GetLengthCost() const { return m_lengthCost; }
72  double GetCornerCost() const { return m_cornerCost; }
73 
74 private:
75  double m_lengthCost;
77 };
78 
90 class OPTIMIZER
91 {
92 public:
94  {
95  MERGE_SEGMENTS = 0x01,
96  SMART_PADS = 0x02,
97  MERGE_OBTUSE = 0x04,
98  FANOUT_CLEANUP = 0x08
99  };
100 
101  OPTIMIZER( NODE* aWorld );
102  ~OPTIMIZER();
103 
105  static bool Optimize( LINE* aLine, int aEffortLevel, NODE* aWorld);
106 
107  bool Optimize( LINE* aLine, LINE* aResult = NULL );
108  bool Optimize( DIFF_PAIR* aPair );
109 
110 
111  void SetWorld( NODE* aNode ) { m_world = aNode; }
112  void CacheStaticItem( ITEM* aItem );
113  void CacheRemove( ITEM* aItem );
114  void ClearCache( bool aStaticOnly = false );
115 
116  void SetCollisionMask( int aMask )
117  {
118  m_collisionKindMask = aMask;
119  }
120 
121  void SetEffortLevel( int aEffort )
122  {
123  m_effortLevel = aEffort;
124  }
125 
126 
127  void SetRestrictArea( const BOX2I& aArea )
128  {
129  m_restrictArea = aArea;
130  m_restrictAreaActive = true;
131  }
132 
133 private:
134  static const int MaxCachedItems = 256;
135 
136  typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
137 
138  struct CACHE_VISITOR;
139 
140  struct CACHED_ITEM
141  {
142  int m_hits;
144  };
145 
146  bool mergeObtuse( LINE* aLine );
147  bool mergeFull( LINE* aLine );
148  bool removeUglyCorners( LINE* aLine );
149  bool runSmartPads( LINE* aLine );
150  bool mergeStep( LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
151  bool fanoutCleanup( LINE * aLine );
152  bool mergeDpSegments( DIFF_PAIR *aPair );
153  bool mergeDpStep( DIFF_PAIR *aPair, bool aTryP, int step );
154 
155  bool checkColliding( ITEM* aItem, bool aUpdateCache = true );
156  bool checkColliding( LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
157 
158  void cacheAdd( ITEM* aItem, bool aIsStatic );
159  void removeCachedSegments( LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
160 
161  BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
162  BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
163  BREAKOUT_LIST ovalBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
164  BREAKOUT_LIST customBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
165  BREAKOUT_LIST computeBreakouts( int aWidth, const ITEM* aItem, bool aPermitDiagonal ) const;
166 
167  int smartPadsSingle( LINE* aLine, ITEM* aPad, bool aEnd, int aEndVertex );
168 
169  ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
170 
172 
173  typedef std::unordered_map<ITEM*, CACHED_ITEM> CachedItemTags;
174  CachedItemTags m_cacheTags;
179 
182 };
183 
184 }
185 
186 #endif
bool m_restrictAreaActive
Class ITEM.
Definition: pns_item.h:53
Class NODE.
Definition: pns_node.h:136
void Replace(LINE &aOldLine, LINE &aNewLine)
COST_ESTIMATOR(const COST_ESTIMATOR &aB)
Definition: pns_optimizer.h:53
void SetCollisionMask(int aMask)
void SetWorld(NODE *aNode)
Class SHAPE.
Definition: shape.h:58
bool IsBetter(COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
CachedItemTags m_cacheTags
Definition: seg.h:36
Class DIFF_PAIR.
Class SHAPE_LINE_CHAIN.
void Add(LINE &aLine)
double GetCornerCost() const
Definition: pns_optimizer.h:72
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
Class OPTIMIZER.
Definition: pns_optimizer.h:90
SHAPE_INDEX_LIST< ITEM * > m_cache
void SetEffortLevel(int aEffort)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
void SetRestrictArea(const BOX2I &aArea)
std::unordered_map< ITEM *, CACHED_ITEM > CachedItemTags
Class COST_ESTIMATOR.
Definition: pns_optimizer.h:45
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(LINE &aLine)
double GetLengthCost() const
Definition: pns_optimizer.h:71