1 /* 2 * KiRouter - a push-and-(sometimes-)shove PCB router 3 * 4 * Copyright (C) 2013-2017 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_LINE_PLACER_H 24 #define __PNS_LINE_PLACER_H 25 26 #include <math/vector2d.h> 27 28 #include <geometry/shape.h> 29 #include <geometry/shape_line_chain.h> 30 31 #include "pns_line.h" 32 #include "pns_mouse_trail_tracer.h" 33 #include "pns_node.h" 34 #include "pns_placement_algo.h" 35 #include "pns_sizes_settings.h" 36 #include "pns_via.h" 37 38 namespace PNS { 39 40 class ROUTER; 41 class SHOVE; 42 class OPTIMIZER; 43 class VIA; 44 class SIZES_SETTINGS; 45 class NODE; 46 47 class FIXED_TAIL 48 { 49 public: 50 FIXED_TAIL( int aLineCount = 1); 51 ~FIXED_TAIL(); 52 53 struct FIX_POINT 54 { 55 int layer; 56 bool placingVias; 57 VECTOR2I p; 58 DIRECTION_45 direction; 59 }; 60 61 struct STAGE 62 { 63 NODE* commit; 64 std::vector<FIX_POINT> pts; 65 }; 66 67 void Clear(); 68 void AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias, DIRECTION_45 direction, 69 NODE* aNode ); 70 bool PopStage( STAGE& aStage ); 71 int StageCount() const; 72 73 private: 74 std::vector<STAGE> m_stages; 75 }; 76 77 78 79 /** 80 * Single track placement algorithm. Interactively routes a track. 81 * Applies shove and walkaround algorithms when needed. 82 */ 83 84 class LINE_PLACER : public PLACEMENT_ALGO 85 { 86 public: 87 LINE_PLACER( ROUTER* aRouter ); 88 ~LINE_PLACER(); 89 90 /** 91 * Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL). 92 */ 93 bool Start( const VECTOR2I& aP, ITEM* aStartItem ) override; 94 95 /** 96 * Move the end of the currently routed trace to the point \a aP, taking \a aEndItem as 97 * anchor (if not NULL). 98 */ 99 bool Move( const VECTOR2I& aP, ITEM* aEndItem ) override; 100 101 /** 102 * Commit the currently routed track to the parent node taking \a aP as the final end point 103 * and \a aEndItem as the final anchor (if provided). 104 * 105 * @return true if route has been committed. May return false if the routing result is 106 * violating design rules. In such cases, the track is only committed if 107 * CanViolateDRC() is on. 108 */ 109 bool FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish ) override; 110 111 bool UnfixRoute() override; 112 113 bool CommitPlacement() override; 114 115 bool AbortPlacement() override; 116 117 bool HasPlacedAnything() const override; 118 119 /** 120 * Enable/disable a via at the end of currently routed trace. 121 */ 122 bool ToggleVia( bool aEnabled ) override; 123 124 /** 125 * Set the current routing layer. 126 */ 127 bool SetLayer( int aLayer ) override; 128 129 /** 130 * Return the "head" of the line being placed, that is the volatile part that has not been 131 * "fixed" yet. 132 */ Head()133 const LINE& Head() const { return m_head; } 134 135 /** 136 * Return the "tail" of the line being placed, the part which has already wrapped around 137 * and shoved some obstacles. 138 */ Tail()139 const LINE& Tail() const { return m_tail; } 140 141 /** 142 * Return the complete routed line. 143 */ 144 const LINE Trace() const; 145 146 /** 147 * Return the complete routed line, as a single-member ITEM_SET. 148 */ 149 const ITEM_SET Traces() override; 150 151 /** 152 * Return the current end of the line being placed. It may not be equal to the cursor 153 * position due to collisions. 154 */ CurrentEnd()155 const VECTOR2I& CurrentEnd() const override 156 { 157 return m_currentEnd; 158 } 159 160 /** 161 * Return the net code of currently routed track. 162 */ CurrentNets()163 const std::vector<int> CurrentNets() const override 164 { 165 return std::vector<int>( 1, m_currentNet ); 166 } 167 168 /** 169 * Return the layer of currently routed track. 170 */ CurrentLayer()171 int CurrentLayer() const override 172 { 173 return m_currentLayer; 174 } 175 176 /** 177 * Return the most recent world state. 178 */ 179 NODE* CurrentNode( bool aLoopsRemoved = false ) const override; 180 181 /** 182 * Toggle the current posture (straight/diagonal) of the trace head. 183 */ 184 void FlipPosture() override; 185 186 /** 187 * Perform on-the-fly update of the width, via diameter & drill size from a settings class. 188 * 189 * Performs on-the-fly update of the width, via diameter & drill size from a settings class. 190 * Used to dynamically change these parameters as the track is routed. 191 */ 192 void UpdateSizes( const SIZES_SETTINGS& aSizes ) override; 193 194 void SetOrthoMode( bool aOrthoMode ) override; 195 IsPlacingVia()196 bool IsPlacingVia() const override { return m_placingVia; } 197 198 void GetModifiedNets( std::vector<int>& aNets ) const override; 199 200 /** 201 * Check if point \a aP lies on segment \a aSeg. If so, splits the segment in two, forming a 202 * joint at \a aP and stores updated topology in node \a aNode. 203 */ 204 bool SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP ); 205 206 private: 207 /** 208 * Re-route the current track to point aP. Returns true, when routing has completed 209 * successfully (i.e. the trace end has reached point \a aP), and false if the trace was 210 * stuck somewhere on the way. May call routeStep() repetitively due to mouse smoothing. 211 * 212 * @param aP ending point of current route. 213 * @return true, if the routing is complete. 214 */ 215 bool route( const VECTOR2I& aP ); 216 217 /** 218 * Draw the "leading" rats nest line, which connects the end of currently routed track and 219 * the nearest yet unrouted item. If the routing for current net is complete, draws nothing. 220 */ 221 void updateLeadingRatLine(); 222 223 /** 224 * Set the board to route. 225 */ 226 void setWorld( NODE* aWorld ); 227 228 /** 229 * Initialize placement of a new line with given parameters. 230 */ 231 void initPlacement(); 232 233 /** 234 * Set preferred direction of the very first track segment to be laid. 235 * Used by posture switching mechanism. 236 */ 237 void setInitialDirection( const DIRECTION_45& aDirection ); 238 239 /** 240 * Searches aNode for traces concurrent to aLatest and removes them. Updated 241 * topology is stored in aNode. 242 */ 243 void removeLoops( NODE* aNode, LINE& aLatest ); 244 245 /** 246 * Assemble a line starting from segment or arc aLatest, removes collinear segments 247 * and redundant vertices. If a simplification has been found, replaces the old line 248 * with the simplified one in \a aNode. 249 */ 250 void simplifyNewLine( NODE* aNode, LINKED_ITEM* aLatest ); 251 252 /** 253 * Check if the head of the track intersects its tail. If so, cuts the tail up to the 254 * intersecting segment and fixes the head direction to match the last segment before 255 * the cut. 256 * 257 * @return true if the line has been changed. 258 */ 259 bool handleSelfIntersections(); 260 261 /** 262 * Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the 263 * current tail direction. 264 * 265 * @return true if the line has been changed. 266 */ 267 bool handlePullback(); 268 269 /** 270 * Moves "established" segments from the head to the tail if certain conditions are met. 271 * 272 * @return true, if the line has been changed. 273 */ 274 bool mergeHead(); 275 276 /** 277 * Attempt to reduce the number of segments in the tail by trying to replace a certain 278 * number of latest tail segments with a direct trace leading to \a aEnd that does not 279 * collide with anything. 280 * 281 * @param aEnd is the current routing destination point. 282 * @return true if the line has been changed. 283 */ 284 bool reduceTail( const VECTOR2I& aEnd ); 285 286 /** 287 * Try to reduce the corner count of the most recent part of tail/head by merging 288 * obtuse/collinear segments. 289 * 290 * @return true if the line has been changed. 291 */ 292 bool optimizeTailHeadTransition(); 293 294 /** 295 * Compute the head trace between the current start point (m_p_start) and point \a aP, 296 * starting with direction defined in m_direction. The trace walks around all 297 * colliding solid or non-movable items. Movable segments are ignored, as they'll be 298 * handled later by the shove algorithm. 299 */ 300 bool routeHead( const VECTOR2I& aP, LINE& aNewHead ); 301 302 /** 303 * Perform a single routing algorithm step, for the end point \a aP. 304 * 305 * @param aP is the ending point of current route. 306 * @return true if the line has been changed. 307 */ 308 void routeStep( const VECTOR2I& aP ); 309 310 ///< Route step walk around mode. 311 bool rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead ); 312 313 ///< Route step shove mode. 314 bool rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead ); 315 316 ///< Route step mark obstacles mode. 317 bool rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead ); 318 319 const VIA makeVia( const VECTOR2I& aP ); 320 321 bool buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia = false ); 322 323 324 DIRECTION_45 m_direction; ///< current routing direction 325 DIRECTION_45 m_initial_direction; ///< routing direction for new traces 326 327 LINE m_head; ///< the volatile part of the track from the previously 328 ///< analyzed point to the current routing destination 329 330 LINE m_last_head; ///< Most recent successful (non-colliding) head 331 332 LINE m_tail; ///< routing "tail": part of the track that has been already 333 ///< fixed due to collisions with obstacles 334 335 NODE* m_world; ///< pointer to world to search colliding items 336 VECTOR2I m_p_start; ///< current routing start (end of tail, beginning of head) 337 338 std::unique_ptr<SHOVE> m_shove; ///< The shove engine 339 340 NODE* m_currentNode; ///< Current world state 341 NODE* m_lastNode; ///< Postprocessed world state (including marked collisions & 342 ///< removed loops) 343 344 SIZES_SETTINGS m_sizes; 345 346 bool m_placingVia; 347 348 int m_currentNet; 349 int m_currentLayer; 350 351 VECTOR2I m_currentEnd; 352 VECTOR2I m_currentStart; 353 LINE m_currentTrace; 354 355 ITEM* m_startItem; 356 ITEM* m_endItem; 357 358 bool m_idle; 359 bool m_chainedPlacement; 360 bool m_orthoMode; 361 bool m_placementCorrect; 362 363 FIXED_TAIL m_fixedTail; 364 MOUSE_TRAIL_TRACER m_mouseTrailTracer; 365 }; 366 367 } 368 369 #endif // __PNS_LINE_PLACER_H 370