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  {
96  SMART_PADS = 0x02,
97  MERGE_OBTUSE = 0x04,
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 convexBreakouts( int aWidth, const SHAPE* aShape, 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
void CacheStaticItem(ITEM *aItem)
Class NODE.
Definition: pns_node.h:137
void CacheRemove(ITEM *aItem)
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:53
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
bool runSmartPads(LINE *aLine)
bool mergeFull(LINE *aLine)
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
void SetCollisionMask(int aMask)
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)
BREAKOUT_LIST convexBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
void SetWorld(NODE *aNode)
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
bool mergeDpSegments(DIFF_PAIR *aPair)
bool mergeObtuse(LINE *aLine)
Class SHAPE.
Definition: shape.h:57
bool IsBetter(COST_ESTIMATOR &aOther, double aLengthTolerance, double aCornerTollerace) const
CachedItemTags m_cacheTags
static const int MaxCachedItems
Definition: seg.h:36
OPTIMIZER(NODE *aWorld)
Optimizer.
Class DIFF_PAIR.
void cacheAdd(ITEM *aItem, bool aIsStatic)
BREAKOUT_LIST ovalBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
bool fanoutCleanup(LINE *aLine)
Class SHAPE_LINE_CHAIN.
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
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
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
void SetEffortLevel(int aEffort)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
void SetRestrictArea(const BOX2I &aArea)
std::unordered_map< ITEM *, CACHED_ITEM > CachedItemTags
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld)
a quick shortcut to optmize a line without creating and setting up an optimizer
Class COST_ESTIMATOR.
Definition: pns_optimizer.h:45
Push and Shove diff pair dimensions (gap) settings dialog.
void Remove(LINE &aLine)
void ClearCache(bool aStaticOnly=false)
double GetLengthCost() const
Definition: pns_optimizer.h:71