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 45 /** 46 * Calculate the cost of a given line, taking corner angles and total length into account. 47 */ 48 class COST_ESTIMATOR 49 { 50 public: COST_ESTIMATOR()51 COST_ESTIMATOR() : 52 m_lengthCost( 0 ), 53 m_cornerCost( 0 ) 54 {} 55 COST_ESTIMATOR(const COST_ESTIMATOR & aB)56 COST_ESTIMATOR( const COST_ESTIMATOR& aB ) : 57 m_lengthCost( aB.m_lengthCost ), 58 m_cornerCost( aB.m_cornerCost ) 59 {} 60 ~COST_ESTIMATOR()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 GetLengthCost()74 double GetLengthCost() const { return m_lengthCost; } GetCornerCost()75 double GetCornerCost() const { return m_cornerCost; } 76 77 private: 78 double m_lengthCost; 79 int m_cornerCost; 80 }; 81 82 83 /** 84 * Perform various optimizations of the lines being routed, attempting to make the lines shorter 85 * and less cornery. 86 * 87 * There are 3 kinds of optimizations so far: 88 * - Merging obtuse segments (MERGE_OBTUSE): tries to join together as many obtuse segments 89 * as possible without causing collisions. 90 * - Rerouting path between pair of line corners with a 2-segment "\__" line and iteratively 91 * repeating the procedure as long as the total cost of the line keeps decreasing. 92 * - "Smart Pads" - that is, rerouting pad/via exits to make them look nice (SMART_PADS). 93 */ 94 class OPTIMIZER 95 { 96 public: 97 enum OptimizationEffort 98 { 99 MERGE_SEGMENTS = 0x01, ///< Reduce corner cost iteratively 100 SMART_PADS = 0x02, ///< Reroute pad exits 101 MERGE_OBTUSE = 0x04, ///< Reduce corner cost by merging obtuse segments 102 FANOUT_CLEANUP = 0x08, ///< Simplify pad-pad and pad-via connections if possible 103 KEEP_TOPOLOGY = 0x10, 104 PRESERVE_VERTEX = 0x20, 105 RESTRICT_VERTEX_RANGE = 0x40, 106 MERGE_COLINEAR = 0x80, ///< Merge co-linear segments 107 RESTRICT_AREA = 0x100, 108 LIMIT_CORNER_COUNT = 0x200 ///< Do not attempt to optimize if the resulting line's 109 ///< corner count is outside the predefined range 110 }; 111 112 OPTIMIZER( NODE* aWorld ); 113 ~OPTIMIZER(); 114 115 ///< A quick shortcut to optimize a line without creating and setting up an optimizer. 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 SetWorld(NODE * aNode)123 void SetWorld( NODE* aNode ) { m_world = aNode; } 124 void CacheRemove( ITEM* aItem ); 125 void ClearCache( bool aStaticOnly = false ); 126 SetCollisionMask(int aMask)127 void SetCollisionMask( int aMask ) 128 { 129 m_collisionKindMask = aMask; 130 } 131 SetEffortLevel(int aEffort)132 void SetEffortLevel( int aEffort ) 133 { 134 m_effortLevel = aEffort; 135 } 136 SetPreserveVertex(const VECTOR2I & aV)137 void SetPreserveVertex( const VECTOR2I& aV ) 138 { 139 m_preservedVertex = aV; 140 m_effortLevel |= OPTIMIZER::PRESERVE_VERTEX; 141 } 142 SetRestrictVertexRange(int aStart,int aEnd)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 216 class OPT_CONSTRAINT 217 { 218 public: OPT_CONSTRAINT(NODE * aWorld)219 OPT_CONSTRAINT( NODE* aWorld ) : 220 m_world( aWorld ) 221 { 222 m_priority = 0; 223 }; 224 ~OPT_CONSTRAINT()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 GetPriority()233 int GetPriority() const { return m_priority; } SetPriority(int aPriority)234 void SetPriority( int aPriority ) { m_priority = aPriority; } 235 236 protected: 237 NODE* m_world; 238 int m_priority; 239 }; 240 241 class ANGLE_CONSTRAINT_45: public OPT_CONSTRAINT 242 { 243 public: 244 ANGLE_CONSTRAINT_45( NODE* aWorld, int aEntryDirectionMask = -1, int aExitDirectionMask = -1 ) : OPT_CONSTRAINT(aWorld)245 OPT_CONSTRAINT( aWorld ), 246 m_entryDirectionMask( aEntryDirectionMask ), 247 m_exitDirectionMask( aExitDirectionMask ) 248 { 249 250 } 251 ~ANGLE_CONSTRAINT_45()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 263 class AREA_CONSTRAINT : public OPT_CONSTRAINT 264 { 265 public: AREA_CONSTRAINT(NODE * aWorld,const BOX2I & aAllowedArea,bool aAllowedAreaStrict)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 283 class KEEP_TOPOLOGY_CONSTRAINT: public OPT_CONSTRAINT 284 { 285 public: KEEP_TOPOLOGY_CONSTRAINT(NODE * aWorld)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 297 class PRESERVE_VERTEX_CONSTRAINT: public OPT_CONSTRAINT 298 { 299 public: PRESERVE_VERTEX_CONSTRAINT(NODE * aWorld,const VECTOR2I & aV)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 314 class RESTRICT_VERTEX_RANGE_CONSTRAINT: public OPT_CONSTRAINT 315 { 316 public: RESTRICT_VERTEX_RANGE_CONSTRAINT(NODE * aWorld,int aStart,int aEnd)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 333 class CORNER_COUNT_LIMIT_CONSTRAINT: public OPT_CONSTRAINT 334 { 335 public: CORNER_COUNT_LIMIT_CONSTRAINT(NODE * aWorld,int aMinCorners,int aMaxCorners,int aAngleMask)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 360