KiCad PCB EDA Suite
pns_shove.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_SHOVE_H
23 #define __PNS_SHOVE_H
24 
25 #include <vector>
26 #include <stack>
27 
28 #include "pns_optimizer.h"
29 #include "pns_routing_settings.h"
30 #include "pns_algo_base.h"
31 #include "pns_logger.h"
32 #include "range.h"
33 
34 namespace PNS {
35 
36 class LINE;
37 class NODE;
38 class ROUTER;
39 
46 class SHOVE : public ALGO_BASE
47 {
48 public:
49 
51  {
52  SH_OK = 0,
57  };
58 
59  SHOVE( NODE* aWorld, ROUTER* aRouter );
60  ~SHOVE();
61 
62  virtual LOGGER* Logger() override
63  {
64  return &m_logger;
65  }
66 
67  SHOVE_STATUS ShoveLines( const LINE& aCurrentHead );
68  SHOVE_STATUS ShoveMultiLines( const ITEM_SET& aHeadSet );
69 
70  SHOVE_STATUS ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere, VIA** aNewVia );
71  SHOVE_STATUS ProcessSingleLine( LINE& aCurrent, LINE& aObstacle,
72  LINE& aShoved );
73 
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 private:
89  typedef std::vector<SHAPE_LINE_CHAIN> HULL_SET;
91  typedef std::pair<LINE, LINE> LINE_PAIR;
92  typedef std::vector<LINE_PAIR> LINE_PAIR_VEC;
93 
95  {
96  int64_t m_length;
103  };
104 
105  SHOVE_STATUS processHullSet( LINE& aCurrent, LINE& aObstacle,
106  LINE& aShoved, const HULL_SET& hulls );
107 
108  bool reduceSpringback( const ITEM_SET& aHeadItems );
109  bool pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
110  const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea );
111 
112  SHOVE_STATUS walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle, LINE& aShoved );
113  bool checkBumpDirection( const LINE& aCurrent, const LINE& aShoved ) const;
114 
115  SHOVE_STATUS onCollidingLine( LINE& aCurrent, LINE& aObstacle );
116  SHOVE_STATUS onCollidingSegment( LINE& aCurrent, SEGMENT* aObstacleSeg );
117  SHOVE_STATUS onCollidingSolid( LINE& aCurrent, ITEM* aObstacle );
118  SHOVE_STATUS onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia );
119  SHOVE_STATUS onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia );
120  SHOVE_STATUS pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun = false );
121 
123 
124  void unwindStack( SEGMENT* aSeg );
125  void unwindStack( ITEM* aItem );
126 
127  void runOptimizer( NODE* aNode );
128 
129  bool pushLine( const LINE& aL, bool aKeepCurrentOnTop = false );
130  void popLine();
131 
132  LINE assembleLine( const SEGMENT* aSeg, int* aIndex = NULL );
133 
134  void replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew );
135  void replaceLine( LINE& aOld, LINE& aNew );
136 
138 
139  SHOVE_STATUS shoveIteration( int aIter );
141 
142  int getClearance( const ITEM* aA, const ITEM* aB ) const;
143 
144  std::vector<SPRINGBACK_TAG> m_nodeStack;
145  std::vector<LINE> m_lineStack;
146  std::vector<LINE> m_optimizerQueue;
147 
150 
151  OPT_LINE m_newHead;
152 
156 
157  int m_iter;
160  void sanityCheck( LINE* aOld, LINE* aNew );
161 };
162 
163 }
164 
165 #endif // __PNS_SHOVE_H
Class ITEM.
Definition: pns_item.h:53
COST_ESTIMATOR m_cost
Definition: pns_shove.h:101
bool reduceSpringback(const ITEM_SET &aHeadItems)
Definition: pns_shove.cpp:541
Class NODE.
Definition: pns_node.h:137
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:412
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
Class SHOVE.
Definition: pns_shove.h:46
ITEM_SET m_draggedViaHeadSet
Definition: pns_shove.h:155
Class ALGO_BASE.
Definition: pns_algo_base.h:39
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:161
NODE * m_root
Definition: pns_shove.h:148
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:91
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:845
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:72
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:92
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:373
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:762
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:89
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1078
bool checkBumpDirection(const LINE &aCurrent, const LINE &aShoved) const
Definition: pns_shove.cpp:116
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:713
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1315
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:81
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1061
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:924
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:88
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:315
SHOVE_STATUS ShoveDraggingVia(VIA *aVia, const VECTOR2I &aWhere, VIA **aNewVia)
Definition: pns_shove.cpp:1262
const LINE NewHead() const
Definition: pns_shove.cpp:1399
bool pushSpringback(NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:564
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
VIA * m_draggedVia
Definition: pns_shove.h:154
void ForceClearance(bool aEnabled, int aClearance)
Definition: pns_shove.h:74
void popLine()
Definition: pns_shove.cpp:898
virtual LOGGER * Logger() override
Returns the logger object, allowing to dump geometry to a file.
Definition: pns_shove.h:62
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1028
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1407
SHOVE_STATUS pushVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank, bool aDryRun=false)
Definition: pns_shove.cpp:592
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:48
bool m_multiLineMode
Definition: pns_shove.h:159
boost::optional< LINE > OPT_LINE
Definition: pns_shove.h:90
OPT_LINE m_newHead
Definition: pns_shove.h:151
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:1179
NODE * m_currentNode
Definition: pns_shove.h:149
Class COST_ESTIMATOR.
Definition: pns_optimizer.h:45
Push and Shove diff pair dimensions (gap) settings dialog.
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:131
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
NODE * CurrentNode()
Definition: pns_shove.cpp:1393
int m_forceClearance
Definition: pns_shove.h:158