KiCad PCB EDA Suite
pns_walkaround.cpp
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-2020 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 #include <core/optional.h>
23 
25 
26 #include "pns_walkaround.h"
27 #include "pns_optimizer.h"
28 #include "pns_utils.h"
29 #include "pns_router.h"
30 #include "pns_debug_decorator.h"
31 
32 namespace PNS {
33 
34 void WALKAROUND::start( const LINE& aInitialPath )
35 {
36  m_iteration = 0;
37  m_iterationLimit = 50;
38 }
39 
40 
42 {
44 
45  if( m_restrictedSet.empty() )
46  return obs;
47 
48  else if( obs && m_restrictedSet.find ( obs->m_item ) != m_restrictedSet.end() )
49  return obs;
50 
51  return NODE::OPT_OBSTACLE();
52 }
53 
54 
56 {
57  OPT<OBSTACLE>& current_obs =
58  aWindingDirection ? m_currentObstacle[0] : m_currentObstacle[1];
59 
60  if( !current_obs )
61  return DONE;
62 
63  VECTOR2I initialLast = aPath.CPoint( -1 );
64 
65  SHAPE_LINE_CHAIN path_walk;
66 
67  bool s_cw = aPath.Walkaround( current_obs->m_hull, path_walk, aWindingDirection );
68 
69  PNS_DBG( Dbg(), BeginGroup, "hull/walk" );
70  char name[128];
71  snprintf(name, sizeof(name), "hull-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
72  PNS_DBG( Dbg(), AddLine, current_obs->m_hull, RED, 1, name);
73  snprintf(name, sizeof(name), "path-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
74  PNS_DBG( Dbg(), AddLine, aPath.CLine(), GREEN, 1, name );
75  snprintf(name, sizeof(name), "result-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
76  PNS_DBG( Dbg(), AddLine, path_walk, BLUE, 10000, name );
77  PNS_DBG( Dbg(), Message, wxString::Format( "Stat cw %d", !!s_cw ) );
78  PNS_DBGN( Dbg(), EndGroup );
79 
80  path_walk.Simplify();
81  aPath.SetShape( path_walk );
82 
83  // If the end of the line is inside an obstacle, additional walkaround iterations are not
84  // going to help. Exit now to prevent pegging the iteration limiter and causing lag.
85  if( current_obs && current_obs->m_hull.PointInside( initialLast ) &&
86  !current_obs->m_hull.PointOnEdge( initialLast ) )
87  {
88  return ALMOST_DONE;
89  }
90 
91  current_obs = nearestObstacle( LINE( aPath, path_walk ) );
92 
93  return IN_PROGRESS;
94 }
95 
96 
97 const WALKAROUND::RESULT WALKAROUND::Route( const LINE& aInitialPath )
98 {
99  LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
100  WALKAROUND_STATUS s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
101  SHAPE_LINE_CHAIN best_path;
102  RESULT result;
103 
104  // special case for via-in-the-middle-of-track placement
105  if( aInitialPath.PointCount() <= 1 )
106  {
107  if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(), m_itemMask ) )
108  return RESULT( STUCK, STUCK );
109 
110  return RESULT( DONE, DONE, aInitialPath, aInitialPath );
111  }
112 
113  start( aInitialPath );
114 
115  m_currentObstacle[0] = m_currentObstacle[1] = nearestObstacle( aInitialPath );
117 
118  result.lineCw = aInitialPath;
119  result.lineCcw = aInitialPath;
120 
121  if( m_forceWinding )
122  {
123  s_cw = m_forceCw ? IN_PROGRESS : STUCK;
124  s_ccw = m_forceCw ? STUCK : IN_PROGRESS;
125  m_forceSingleDirection = true;
126  } else {
127  m_forceSingleDirection = false;
128  }
129 
130  // In some situations, there isn't a trivial path (or even a path at all). Hitting the
131  // iteration limit causes lag, so we can exit out early if the walkaround path gets very long
132  // compared with the initial path. If the length exceeds the initial length times this factor,
133  // fail out.
134  const int maxWalkDistFactor = 10;
135  long long lengthLimit = aInitialPath.CLine().Length() * maxWalkDistFactor;
136 
137  while( m_iteration < m_iterationLimit )
138  {
139  if( s_cw != STUCK && s_cw != ALMOST_DONE )
140  s_cw = singleStep( path_cw, true );
141 
142  if( s_ccw != STUCK && s_ccw != ALMOST_DONE )
143  s_ccw = singleStep( path_ccw, false );
144 
145  if( s_cw != IN_PROGRESS )
146  {
147  result.lineCw = path_cw;
148  result.statusCw = s_cw;
149  }
150 
151  if( s_ccw != IN_PROGRESS )
152  {
153  result.lineCcw = path_ccw;
154  result.statusCcw = s_ccw;
155  }
156 
157  if( s_cw != IN_PROGRESS && s_ccw != IN_PROGRESS )
158  break;
159 
160  // Safety valve
161  if( path_cw.Line().Length() > lengthLimit && path_ccw.Line().Length() > lengthLimit )
162  break;
163 
164  m_iteration++;
165  }
166 
167  if( s_cw == IN_PROGRESS )
168  {
169  result.lineCw = path_cw;
170  result.statusCw = ALMOST_DONE;
171  }
172 
173  if( s_ccw == IN_PROGRESS )
174  {
175  result.lineCcw = path_ccw;
176  result.statusCcw = ALMOST_DONE;
177  }
178 
179  if( result.lineCw.SegmentCount() < 1 || result.lineCw.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
180  {
181  result.statusCw = STUCK;
182  }
183 
184  if( result.lineCw.PointCount() > 0 && result.lineCw.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
185  {
186  result.statusCw = ALMOST_DONE;
187  }
188 
189  if( result.lineCcw.SegmentCount() < 1 || result.lineCcw.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
190  {
191  result.statusCcw = STUCK;
192  }
193 
194  if( result.lineCcw.PointCount() > 0 && result.lineCcw.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
195  {
196  result.statusCcw = ALMOST_DONE;
197  }
198 
199  return result;
200 }
201 
202 
203 
205  LINE& aWalkPath, bool aOptimize )
206 {
207  LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
208  WALKAROUND_STATUS s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
209  SHAPE_LINE_CHAIN best_path;
210 
211  // special case for via-in-the-middle-of-track placement
212  if( aInitialPath.PointCount() <= 1 )
213  {
214  if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(), m_itemMask ) )
215  return STUCK;
216 
217  aWalkPath = aInitialPath;
218  return DONE;
219  }
220 
221  start( aInitialPath );
222 
223  m_currentObstacle[0] = m_currentObstacle[1] = nearestObstacle( aInitialPath );
225 
226  aWalkPath = aInitialPath;
227 
228  if( m_forceWinding )
229  {
230  s_cw = m_forceCw ? IN_PROGRESS : STUCK;
231  s_ccw = m_forceCw ? STUCK : IN_PROGRESS;
232  m_forceSingleDirection = true;
233  } else {
234  m_forceSingleDirection = false;
235  }
236 
237  while( m_iteration < m_iterationLimit )
238  {
239  if( s_cw != STUCK )
240  s_cw = singleStep( path_cw, true );
241 
242  if( s_ccw != STUCK )
243  s_ccw = singleStep( path_ccw, false );
244 
245  if( ( s_cw == DONE && s_ccw == DONE ) || ( s_cw == STUCK && s_ccw == STUCK ) )
246  {
247  int len_cw = path_cw.CLine().Length();
248  int len_ccw = path_ccw.CLine().Length();
249 
250  if( m_forceLongerPath )
251  aWalkPath = ( len_cw > len_ccw ? path_cw : path_ccw );
252  else
253  aWalkPath = ( len_cw < len_ccw ? path_cw : path_ccw );
254 
255  break;
256  }
257  else if( s_cw == DONE && !m_forceLongerPath )
258  {
259  aWalkPath = path_cw;
260  break;
261  }
262  else if( s_ccw == DONE && !m_forceLongerPath )
263  {
264  aWalkPath = path_ccw;
265  break;
266  }
267 
268  m_iteration++;
269  }
270 
272  {
273  int len_cw = path_cw.CLine().Length();
274  int len_ccw = path_ccw.CLine().Length();
275 
276  if( m_forceLongerPath )
277  aWalkPath = ( len_cw > len_ccw ? path_cw : path_ccw );
278  else
279  aWalkPath = ( len_cw < len_ccw ? path_cw : path_ccw );
280  }
281 
282  aWalkPath.Line().Simplify();
283 
284  if( aWalkPath.SegmentCount() < 1 )
285  return STUCK;
286  if( aWalkPath.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
287  return ALMOST_DONE;
288  if( aWalkPath.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
289  return STUCK;
290 
291  WALKAROUND_STATUS st = s_ccw == DONE || s_cw == DONE ? DONE : STUCK;
292 
293  if( st == DONE )
294  {
295  if( aOptimize )
297  }
298 
299  return st;
300 }
301 
302 }
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
#define PNS_DBGN(dbg, method)
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:281
long long int Length() const
Function Length()
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
WALKAROUND_STATUS statusCw
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
WALKAROUND_STATUS singleStep(LINE &aPath, bool aWindingDirection)
std::set< ITEM * > m_restrictedSet
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
int PointCount() const
Definition: pns_line.h:140
bool EndsWithVia() const
Definition: pns_line.h:191
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
NODE::OPT_OBSTACLE m_currentObstacle[2]
#define NULL
Definition: color4d.h:57
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void start(const LINE &aInitialPath)
Definition: color4d.h:59
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: color4d.h:56
NODE::OPT_OBSTACLE nearestObstacle(const LINE &aPath)
const char * name
Definition: DXF_plotter.cpp:59
Reduce corner cost by merging obtuse segments.
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:433
WALKAROUND_STATUS statusCcw
boost::optional< T > OPT
Definition: optional.h:7
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
const VIA & Via() const
Definition: pns_line.h:196
Push and Shove diff pair dimensions (gap) settings dialog.