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 * 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_SHOVE_H 23 #define __PNS_SHOVE_H 24 25 #include <vector> 26 #include <stack> 27 28 #include <math/box2.h> 29 30 #include "pns_optimizer.h" 31 #include "pns_routing_settings.h" 32 #include "pns_algo_base.h" 33 #include "pns_logger.h" 34 #include "range.h" 35 36 namespace PNS { 37 38 class LINE; 39 class NODE; 40 class ROUTER; 41 42 /** 43 * The actual Push and Shove algorithm. 44 */ 45 class SHOVE : public ALGO_BASE 46 { 47 public: 48 49 enum SHOVE_STATUS 50 { 51 SH_OK = 0, 52 SH_NULL, 53 SH_INCOMPLETE, 54 SH_HEAD_MODIFIED, 55 SH_TRY_WALK 56 }; 57 58 SHOVE( NODE* aWorld, ROUTER* aRouter ); 59 ~SHOVE(); 60 Logger()61 virtual LOGGER* Logger() override 62 { 63 return &m_logger; 64 } 65 66 SHOVE_STATUS ShoveLines( const LINE& aCurrentHead ); 67 SHOVE_STATUS ShoveMultiLines( const ITEM_SET& aHeadSet ); 68 69 SHOVE_STATUS ShoveDraggingVia( const VIA_HANDLE aOldVia, const VECTOR2I& aWhere, 70 VIA_HANDLE& aNewVia ); 71 SHOVE_STATUS ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine, 72 LINE& aResultLine ); 73 ForceClearance(bool aEnabled,int aClearance)74 void ForceClearance ( bool aEnabled, int aClearance ) 75 { 76 if( aEnabled ) 77 m_forceClearance = aClearance; 78 else 79 m_forceClearance = -1; 80 } 81 82 NODE* CurrentNode(); 83 84 const LINE NewHead() const; 85 86 void SetInitialLine( LINE& aInitial ); 87 88 bool AddLockedSpringbackNode( NODE* aNode ); 89 void UnlockSpringbackNode( NODE* aNode ); 90 bool RewindSpringbackTo( NODE* aNode ); 91 bool RewindToLastLockedNode(); 92 void DisablePostShoveOptimizations( int aMask ); 93 void SetSpringbackDoNotTouchNode( NODE *aNode ); 94 95 private: 96 typedef std::vector<SHAPE_LINE_CHAIN> HULL_SET; 97 typedef OPT<LINE> OPT_LINE; 98 typedef std::pair<LINE, LINE> LINE_PAIR; 99 typedef std::vector<LINE_PAIR> LINE_PAIR_VEC; 100 101 struct SPRINGBACK_TAG 102 { SPRINGBACK_TAGSPRINGBACK_TAG103 SPRINGBACK_TAG() : 104 m_length( 0 ), 105 m_draggedVia(), 106 m_node( nullptr ), 107 m_seq( 0 ), 108 m_locked( false ) 109 {} 110 111 int64_t m_length; 112 VIA_HANDLE m_draggedVia; 113 VECTOR2I m_p; 114 NODE* m_node; 115 OPT_BOX2I m_affectedArea; 116 int m_seq; 117 bool m_locked; 118 }; 119 120 SHOVE_STATUS shoveLineToHullSet( const LINE& aCurLine, const LINE& aObstacleLine, 121 LINE& aResultLine, const HULL_SET& aHulls ); 122 123 NODE* reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia ); 124 125 bool pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia ); 126 127 SHOVE_STATUS shoveLineFromLoneVia( const LINE& aCurLine, const LINE& aObstacleLine, 128 LINE& aResultLine ); 129 bool checkShoveDirection( const LINE& aCurLine, const LINE& aObstacleLine, 130 const LINE& aShovedLine ) const; 131 132 SHOVE_STATUS onCollidingArc( LINE& aCurrent, ARC* aObstacleArc ); 133 SHOVE_STATUS onCollidingLine( LINE& aCurrent, LINE& aObstacle ); 134 SHOVE_STATUS onCollidingSegment( LINE& aCurrent, SEGMENT* aObstacleSeg ); 135 SHOVE_STATUS onCollidingSolid( LINE& aCurrent, ITEM* aObstacle ); 136 SHOVE_STATUS onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia ); 137 SHOVE_STATUS onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia ); 138 SHOVE_STATUS pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank ); 139 140 OPT_BOX2I totalAffectedArea() const; 141 142 void unwindLineStack( LINKED_ITEM* aSeg ); 143 void unwindLineStack( ITEM* aItem ); 144 145 void runOptimizer( NODE* aNode ); 146 147 bool pushLineStack( const LINE& aL, bool aKeepCurrentOnTop = false ); 148 void popLineStack(); 149 150 LINE assembleLine( const LINKED_ITEM* aSeg, int* aIndex = nullptr ); 151 152 void replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew ); 153 void replaceLine( LINE& aOld, LINE& aNew, bool aIncludeInChangedArea = true, 154 NODE *aNode = nullptr ); 155 156 LINE* findRootLine( LINE *aLine ); 157 158 OPT_BOX2I m_affectedArea; 159 160 SHOVE_STATUS shoveIteration( int aIter ); 161 SHOVE_STATUS shoveMainLoop(); 162 163 int getClearance( const ITEM* aA, const ITEM* aB ) const; 164 int getHoleClearance( const ITEM* aA, const ITEM* aB ) const; 165 166 void sanityCheck( LINE* aOld, LINE* aNew ); 167 168 std::vector<SPRINGBACK_TAG> m_nodeStack; 169 std::vector<LINE> m_lineStack; 170 std::vector<LINE> m_optimizerQueue; 171 std::unordered_map<const LINKED_ITEM*, LINE*> m_rootLineHistory; 172 173 NODE* m_root; 174 NODE* m_currentNode; 175 NODE* m_springbackDoNotTouchNode; 176 int m_restrictSpringbackTagId; 177 178 OPT_LINE m_newHead; 179 180 LOGGER m_logger; 181 VIA* m_draggedVia; 182 183 int m_iter; 184 int m_forceClearance; 185 bool m_multiLineMode; 186 187 int m_optFlagDisableMask; 188 }; 189 190 } 191 192 #endif // __PNS_SHOVE_H 193