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-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 #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  &aPath, m_itemMask, m_restrictedSet.empty() ? nullptr : &m_restrictedSet );
45 
46  if( m_restrictedSet.empty() )
47  return obs;
48 
49  else if( obs && m_restrictedSet.find ( obs->m_item ) != m_restrictedSet.end() )
50  return obs;
51 
52  return NODE::OPT_OBSTACLE();
53 }
54 
55 
57 {
58  OPT<OBSTACLE>& current_obs =
59  aWindingDirection ? m_currentObstacle[0] : m_currentObstacle[1];
60 
61  if( !current_obs )
62  return DONE;
63 
64  VECTOR2I initialLast = aPath.CPoint( -1 );
65 
66  SHAPE_LINE_CHAIN path_walk;
67 
68  bool s_cw = aPath.Walkaround( current_obs->m_hull, path_walk, aWindingDirection );
69 
70  PNS_DBG( Dbg(), BeginGroup, "hull/walk" );
71  char name[128];
72  snprintf( name, sizeof( name ), "hull-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
73  PNS_DBG( Dbg(), AddLine, current_obs->m_hull, RED, 1, name );
74  snprintf( name, sizeof( name ), "path-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
75  PNS_DBG( Dbg(), AddLine, aPath.CLine(), GREEN, 1, name );
76  snprintf( name, sizeof( name ), "result-%s-%d", aWindingDirection ? "cw" : "ccw", m_iteration );
77  PNS_DBG( Dbg(), AddLine, path_walk, BLUE, 10000, name );
78  PNS_DBG( Dbg(), Message, wxString::Format( "Stat cw %d", !!s_cw ) );
79  PNS_DBGN( Dbg(), EndGroup );
80 
81  path_walk.Simplify();
82  aPath.SetShape( path_walk );
83 
84  // If the end of the line is inside an obstacle, additional walkaround iterations are not
85  // going to help. Exit now to prevent pegging the iteration limiter and causing lag.
86  if( current_obs && current_obs->m_hull.PointInside( initialLast ) &&
87  !current_obs->m_hull.PointOnEdge( initialLast ) )
88  {
89  return ALMOST_DONE;
90  }
91 
92  current_obs = nearestObstacle( LINE( aPath, path_walk ) );
93 
94  return IN_PROGRESS;
95 }
96 
97 
98 const WALKAROUND::RESULT WALKAROUND::Route( const LINE& aInitialPath )
99 {
100  LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
101  WALKAROUND_STATUS s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
102  SHAPE_LINE_CHAIN best_path;
103  RESULT result;
104 
105  // special case for via-in-the-middle-of-track placement
106  if( aInitialPath.PointCount() <= 1 )
107  {
108  if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(),
109  m_itemMask ) )
110  return RESULT( STUCK, STUCK );
111 
112  return RESULT( DONE, DONE, aInitialPath, aInitialPath );
113  }
114 
115  start( aInitialPath );
116 
117  m_currentObstacle[0] = m_currentObstacle[1] = nearestObstacle( aInitialPath );
119 
120  result.lineCw = aInitialPath;
121  result.lineCcw = aInitialPath;
122 
123  if( m_forceWinding )
124  {
125  s_cw = m_forceCw ? IN_PROGRESS : STUCK;
126  s_ccw = m_forceCw ? STUCK : IN_PROGRESS;
127  m_forceSingleDirection = true;
128  }
129  else
130  {
131  m_forceSingleDirection = false;
132  }
133 
134  // In some situations, there isn't a trivial path (or even a path at all). Hitting the
135  // iteration limit causes lag, so we can exit out early if the walkaround path gets very long
136  // compared with the initial path. If the length exceeds the initial length times this factor,
137  // fail out.
138  const int maxWalkDistFactor = 10;
139  long long lengthLimit = aInitialPath.CLine().Length() * maxWalkDistFactor;
140 
141  while( m_iteration < m_iterationLimit )
142  {
143  if( s_cw != STUCK && s_cw != ALMOST_DONE )
144  s_cw = singleStep( path_cw, true );
145 
146  if( s_ccw != STUCK && s_ccw != ALMOST_DONE )
147  s_ccw = singleStep( path_ccw, false );
148 
149  if( s_cw != IN_PROGRESS )
150  {
151  result.lineCw = path_cw;
152  result.statusCw = s_cw;
153  }
154 
155  if( s_ccw != IN_PROGRESS )
156  {
157  result.lineCcw = path_ccw;
158  result.statusCcw = s_ccw;
159  }
160 
161  if( s_cw != IN_PROGRESS && s_ccw != IN_PROGRESS )
162  break;
163 
164  // Safety valve
165  if( path_cw.Line().Length() > lengthLimit && path_ccw.Line().Length() > lengthLimit )
166  break;
167 
168  m_iteration++;
169  }
170 
171  if( s_cw == IN_PROGRESS )
172  {
173  result.lineCw = path_cw;
174  result.statusCw = ALMOST_DONE;
175  }
176 
177  if( s_ccw == IN_PROGRESS )
178  {
179  result.lineCcw = path_ccw;
180  result.statusCcw = ALMOST_DONE;
181  }
182 
183  if( result.lineCw.SegmentCount() < 1 || result.lineCw.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
184  {
185  result.statusCw = STUCK;
186  }
187 
188  if( result.lineCw.PointCount() > 0 && result.lineCw.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
189  {
190  result.statusCw = ALMOST_DONE;
191  }
192 
193  if( result.lineCcw.SegmentCount() < 1 ||
194  result.lineCcw.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
195  {
196  result.statusCcw = STUCK;
197  }
198 
199  if( result.lineCcw.PointCount() > 0 &&
200  result.lineCcw.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
201  {
202  result.statusCcw = ALMOST_DONE;
203  }
204 
205  return result;
206 }
207 
208 
209 WALKAROUND::WALKAROUND_STATUS WALKAROUND::Route( const LINE& aInitialPath, LINE& aWalkPath,
210  bool aOptimize )
211 {
212  LINE path_cw( aInitialPath ), path_ccw( aInitialPath );
213  WALKAROUND_STATUS s_cw = IN_PROGRESS, s_ccw = IN_PROGRESS;
214  SHAPE_LINE_CHAIN best_path;
215 
216  // special case for via-in-the-middle-of-track placement
217  if( aInitialPath.PointCount() <= 1 )
218  {
219  if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(),
220  m_itemMask ) )
221  return STUCK;
222 
223  aWalkPath = aInitialPath;
224  return DONE;
225  }
226 
227  start( aInitialPath );
228 
229  m_currentObstacle[0] = m_currentObstacle[1] = nearestObstacle( aInitialPath );
231 
232  aWalkPath = aInitialPath;
233 
234  if( m_forceWinding )
235  {
236  s_cw = m_forceCw ? IN_PROGRESS : STUCK;
237  s_ccw = m_forceCw ? STUCK : IN_PROGRESS;
238  m_forceSingleDirection = true;
239  }
240  else
241  {
242  m_forceSingleDirection = false;
243  }
244 
245  while( m_iteration < m_iterationLimit )
246  {
247  if( path_cw.PointCount() == 0 )
248  s_cw = STUCK; // cw path is empty, can't continue
249 
250  if( path_ccw.PointCount() == 0 )
251  s_ccw = STUCK; // ccw path is empty, can't continue
252 
253  if( s_cw != STUCK )
254  s_cw = singleStep( path_cw, true );
255 
256  if( s_ccw != STUCK )
257  s_ccw = singleStep( path_ccw, false );
258 
259  if( ( s_cw == DONE && s_ccw == DONE ) || ( s_cw == STUCK && s_ccw == STUCK ) )
260  {
261  int len_cw = path_cw.CLine().Length();
262  int len_ccw = path_ccw.CLine().Length();
263 
264  if( m_forceLongerPath )
265  aWalkPath = ( len_cw > len_ccw ? path_cw : path_ccw );
266  else
267  aWalkPath = ( len_cw < len_ccw ? path_cw : path_ccw );
268 
269  break;
270  }
271  else if( s_cw == DONE && !m_forceLongerPath )
272  {
273  aWalkPath = path_cw;
274  break;
275  }
276  else if( s_ccw == DONE && !m_forceLongerPath )
277  {
278  aWalkPath = path_ccw;
279  break;
280  }
281 
282  m_iteration++;
283  }
284 
286  {
287  int len_cw = path_cw.CLine().Length();
288  int len_ccw = path_ccw.CLine().Length();
289 
290  if( m_forceLongerPath )
291  aWalkPath = ( len_cw > len_ccw ? path_cw : path_ccw );
292  else
293  aWalkPath = ( len_cw < len_ccw ? path_cw : path_ccw );
294  }
295 
296  aWalkPath.Line().Simplify();
297 
298  if( aWalkPath.SegmentCount() < 1 )
299  return STUCK;
300 
301  if( aWalkPath.CPoint( -1 ) != aInitialPath.CPoint( -1 ) )
302  return ALMOST_DONE;
303 
304  if( aWalkPath.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
305  return STUCK;
306 
307  WALKAROUND_STATUS st = s_ccw == DONE || s_cw == DONE ? DONE : STUCK;
308 
309  if( st == DONE )
310  {
311  if( aOptimize )
313  }
314 
315  return st;
316 }
317 }
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
#define PNS_DBGN(dbg, method)
long long int Length() const
Return length of the line chain in Euclidean metric.
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)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
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]
Definition: color4d.h:57
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void start(const LINE &aInitialPath)
Definition: color4d.h:59
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:296
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:56
Reduce corner cost by merging obtuse segments.
Represent a polyline (an zero-thickness chain of connected line segments).
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:450
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.