KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
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
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22#include <chrono>
23#include <optional>
24
25#include <advanced_config.h>
26#include <core/typeinfo.h>
28
29#include "pns_walkaround.h"
30#include "pns_optimizer.h"
31#include "pns_router.h"
32#include "pns_debug_decorator.h"
33#include "pns_solid.h"
34
35
36namespace PNS {
37
42
43void WALKAROUND::start( const LINE& aInitialPath )
44{
45 m_iteration = 0;
46 for( int pol = 0 ; pol < MaxWalkPolicies; pol++)
47 {
48 m_currentResult.status[ pol ] = ST_IN_PROGRESS;
49 m_currentResult.lines[ pol ] = aInitialPath;
50 m_currentResult.lines[ pol ].ClearLinks();
51 }
52}
53
54
56{
58
60
61 if( ! m_restrictedSet.empty() )
62 {
63 opts.m_filter = [ this ] ( const ITEM* item, const ITEM* aRef ) -> bool
64 {
65 if( m_restrictedSet.find( item ) != m_restrictedSet.end() )
66 return true;
67 return false;
68 };
69 }
70 else
71 {
74 }
75
76 opts.m_useClearanceEpsilon = false;
77
78 return m_world->NearestObstacle( &aPath, opts );
79}
80
81
82void WALKAROUND::RestrictToCluster( bool aEnabled, const TOPOLOGY::CLUSTER& aCluster )
83{
85 m_restrictedSet.clear();
86
87 if( aEnabled )
88 {
89 for( ITEM* item : aCluster.m_items )
90 {
91 m_restrictedSet.insert( item );
92
93 if ( item->HasHole() )
94 m_restrictedSet.insert( item->Hole() );
95 }
96 }
97
98 for( ITEM* item : aCluster.m_items )
99 {
100 if( SOLID* solid = dyn_cast<SOLID*>( item ) )
101 m_restrictedVertices.push_back( solid->Anchor( 0 ) );
102 }
103}
104
105/*
106static wxString policy2string ( WALKAROUND::WALK_POLICY policy )
107{
108 switch(policy)
109 {
110 case WALKAROUND::WP_CCW: return wxT("ccw");
111 case WALKAROUND::WP_CW: return wxT("cw");
112 case WALKAROUND::WP_SHORTEST: return wxT("shortest");
113 }
114 return wxT("?");
115}
116*/
117
119{
120 TOPOLOGY topo( m_world );
121 TOPOLOGY::CLUSTER pendingClusters[MaxWalkPolicies];
123
125
126 for( int i = 0; i < MaxWalkPolicies; i++ )
127 {
128 if( !m_enabledPolicies[i] )
129 continue;
130
131 auto& line = m_currentResult.lines[ i ];
132 auto& status = m_currentResult.status[ i ];
133
134 PNS_DBG( Dbg(), AddItem, &line, WHITE, 10000, wxString::Format( "current (policy %d, stat %d)", i, status ) );
135
136 if( status != ST_IN_PROGRESS )
137 continue;
138
139 auto obstacle = nearestObstacle( line );
140
141 if( !obstacle )
142 {
143
144 m_currentResult.status[ i ] = ST_DONE;
145 PNS_DBG( Dbg(), Message, wxString::Format( "no-more-colls pol %d st %d", i, status ) );
146
147 continue;
148 }
149
150
151 int clusterMargin = 2 * obstacle->m_clearance + line.Width() ;
152
153 if( m_useClustering )
154 {
155 pendingClusters[ i ] = topo.AssembleCluster( obstacle->m_item, line.Layer(), 0.0, line.Net(), clusterMargin );
156 }
157 else
158 {
159 pendingClusters[ i ].m_key = nullptr;
160 pendingClusters[ i ].m_items = { obstacle->m_item };
161 }
162
163 PNS_DBG( Dbg(), AddItem, obstacle->m_item, BLUE, 10000, wxString::Format( "col-item owner-depth %d cl-items=%d cl-margin=%d", static_cast<const NODE*>( obstacle->m_item->Owner() )->Depth(), (int) pendingClusters[i].m_items.size(), clusterMargin ) );
164
165 }
166
168
169 auto processCluster = [ & ] ( TOPOLOGY::CLUSTER& aCluster, LINE& aLine, bool aCw ) -> bool
170 {
171 using namespace std::chrono;
172 auto start_time = steady_clock::now();
173
175
176 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "cluster-details [cw %d]", aCw?1:0 ), 1 );
177
178 for( auto& clItem : aCluster.m_items )
179 {
180 // Check for wallclock timeout
181 // Emprically, 100ms seems to be about where you're not going to find a valid path
182 // if you haven't found it by then. This allows the user to adjust their mouse position
183 // to get a better path without waiting too long.
184 auto now = steady_clock::now();
185 auto elapsed = duration_cast<milliseconds>( now - start_time ).count();
186
187 if( elapsed > timeout_ms )
188 {
189 PNS_DBG( Dbg(), Message, wxString::Format( "processCluster timeout after %d ms", timeout_ms ) );
190 PNS_DBGN( Dbg(), EndGroup );
191 return false;
192 }
193
194 int clearance = m_world->GetClearance( clItem, &aLine, false, opts );
195 const SHAPE_LINE_CHAIN& cachedHull = m_world->GetRuleResolver()->HullCache(
196 clItem, clearance, aLine.Width(), aLine.Layer() );
197
198 SHAPE_LINE_CHAIN hull;
199
200 if( cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90 )
201 {
202 BOX2I bbox = cachedHull.BBox();
203 hull.Append( bbox.GetLeft(), bbox.GetTop() );
204 hull.Append( bbox.GetRight(), bbox.GetTop() );
205 hull.Append( bbox.GetRight(), bbox.GetBottom() );
206 hull.Append( bbox.GetLeft(), bbox.GetBottom() );
207 hull.SetClosed( true );
208 }
209 else
210 {
211 hull = cachedHull;
212 }
213
214 LINE tmp( aLine );
215
216 aLine.Line().Simplify2();
217
218 bool stat = aLine.Walkaround( hull, tmp.Line(), aCw );
219
220 PNS_DBG( Dbg(), AddShape, &hull, YELLOW, 10000, wxString::Format( "hull stat %d", stat?1:0 ) );
221 PNS_DBG( Dbg(), AddItem, &tmp, RED, 10000, wxString::Format( "walk stat %d", stat?1:0 ) );
222 PNS_DBG( Dbg(), AddItem, clItem, WHITE, 10000, wxString::Format( "item stat %d", stat?1:0 ) );
223
224 if( !stat )
225 {
226 PNS_DBGN( Dbg(), EndGroup );
227 return false;
228 }
229
230 aLine.SetShape( tmp.CLine() );
231 }
232
233 PNS_DBGN( Dbg(), EndGroup );
234
235 return true;
236 };
237
239 {
240 bool stat = processCluster( pendingClusters[ WP_CW ], m_currentResult.lines[ WP_CW ], true );
241 if( !stat )
242 m_currentResult.status[ WP_CW ] = ST_STUCK;
243 }
244
246 {
247 bool stat = processCluster( pendingClusters[ WP_CCW ], m_currentResult.lines[ WP_CCW ], false );
248 if( !stat )
249 m_currentResult.status[ WP_CCW ] = ST_STUCK;
250 }
251
253 {
254 LINE& line = m_currentResult.lines[WP_SHORTEST];
255 LINE path_cw( line ), path_ccw( line );
256
257 auto st_cw = processCluster( pendingClusters[WP_SHORTEST], path_cw, true );
258 auto st_ccw = processCluster( pendingClusters[WP_SHORTEST], path_ccw, false );
259
261
262 bool cw_coll = st_cw ? m_world->CheckColliding( &path_cw, opts ).has_value() : false;
263 bool ccw_coll = st_ccw ? m_world->CheckColliding( &path_ccw, opts ).has_value() : false;
264
265 double lengthFactorCw = (double) path_cw.CLine().Length() / (double) m_initialLength;
266 double lengthFactorCcw = (double) path_ccw.CLine().Length() / (double) m_initialLength;
267
268 PNS_DBG( Dbg(), AddItem, &path_cw, RED, 10000, wxString::Format( "shortest-cw stat %d lf %.1f", st_cw?1:0, lengthFactorCw ) );
269 PNS_DBG( Dbg(), AddItem, &path_ccw, BLUE, 10000, wxString::Format( "shortest-ccw stat %d lf %.1f", st_ccw?1:0, lengthFactorCcw ) );
270
271
272 std::optional<LINE> shortest;
273 std::optional<LINE> shortest_alt;
274
275
276 if( st_cw && st_ccw )
277 {
278 if( ( !cw_coll && !ccw_coll ) || ( cw_coll && ccw_coll ) )
279 {
280 if( path_cw.CLine().Length() > path_ccw.CLine().Length() )
281 {
282 shortest = path_ccw;
283 shortest_alt = path_cw;
284 }
285 else
286 {
287 shortest = path_cw;
288 shortest_alt = path_ccw;
289 }
290 }
291 else if( !cw_coll )
292 shortest = path_cw;
293 else if( !ccw_coll )
294 shortest = path_ccw;
295
296 }
297 else if( st_ccw )
298 shortest = path_ccw;
299 else if( st_cw )
300 shortest = path_cw;
301
302 bool anyColliding = false;
303
304 if( shortest.has_value() )
305 {
306 PNS_DBG( Dbg(), AddItem, &shortest.value(), RED, 10000, wxString::Format( "shortest-l" ) );
307
308 for( auto& item : m_processedItems )
309 {
310 std::set<PNS::OBSTACLE> obstacles;
311 PNS::COLLISION_SEARCH_CONTEXT ctx( obstacles, opts );
312 if( shortest->Collide( item, m_world, shortest->Layer(), &ctx ) )
313 {
314 anyColliding = true;
315 break;
316 }
317 }
318
319 PNS_DBG( Dbg(), Message, wxString::Format("check-back cc %d items %d coll %d", (int) pendingClusters[ WP_SHORTEST ].m_items.size(), (int) m_processedItems.size(), anyColliding ? 1: 0 ) );
320 }
321
322 if ( anyColliding )
323 {
324 shortest = std::move( shortest_alt );
325 }
326
327 if( !shortest )
328 {
330 }
331 else
332 {
333 m_currentResult.lines[WP_SHORTEST] = *shortest;
334 }
335
336 for( auto item : pendingClusters[ WP_SHORTEST ].m_items )
337 m_processedItems.insert( item );
338 }
339
340 return ST_IN_PROGRESS;
341}
342
343
344const WALKAROUND::RESULT WALKAROUND::Route( const LINE& aInitialPath )
345{
347
348 m_initialLength = aInitialPath.CLine().Length();
349
350 // special case for via-in-the-middle-of-track placement
351
352#if 0
353 if( aInitialPath.PointCount() <= 1 )
354 {
355 if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(),
356 m_itemMask ) )
357 {
358 // fixme restult
359 }
360 //return RESULT( STUCK, STUCK );
361
362 return RESULT(); //( DONE, DONE, aInitialPath, aInitialPath );
363 }
364#endif
365
366 start( aInitialPath );
367
368 m_processedItems.clear();
369
370 PNS_DBG( Dbg(), AddItem, &aInitialPath, WHITE, 10000, wxT( "initial-path" ) );
371
373 {
374 bool finished = false;
375 singleStep();
376
377 bool stillInProgress = false;
378
379 for( int pol = 0; pol < MaxWalkPolicies; pol++ )
380 {
381 if (!m_enabledPolicies[pol])
382 continue;
383
384 auto& st = m_currentResult.status[pol];
385 auto& ln = m_currentResult.lines[pol];
386
388 {
389 finished = true;
390 break;
391 }
392
393 double lengthFactor = (double) ln.CLine().Length() / (double) aInitialPath.CLine().Length();
394 // In some situations, there isn't a trivial path (or even a path at all). Hitting the
395 // iteration limit causes lag, so we can exit out early if the walkaround path gets very long
396 // compared with the initial path. If the length exceeds the initial length times this factor,
397 // fail out.
398 if( m_lengthLimitOn )
399 {
400 if( st != ST_DONE && lengthFactor > m_lengthExpansionFactor )
401 st = ST_ALMOST_DONE;
402 }
403
404 PNS_DBG( Dbg(), Message, wxString::Format( "check-wp iter %d st %d i %d lf %.1f", m_iteration, st, pol, lengthFactor ) );
405
406 if ( st == ST_IN_PROGRESS )
407 stillInProgress = true;
408 }
409
410 if( !stillInProgress || finished )
411 break;
412
413 m_iteration++;
414 }
415
416
417 for( int pol = 0; pol < MaxWalkPolicies; pol++ )
418 {
419 auto& st = m_currentResult.status[pol];
420 const auto& ln = m_currentResult.lines[pol].CLine();
421
422 m_currentResult.lines[pol].ClearLinks();
423 if( st == ST_IN_PROGRESS )
424 st = ST_ALMOST_DONE;
425
426 if( ln.SegmentCount() < 1 || ln.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
427 {
428 st = ST_STUCK;
429 }
430
431 if( ln.PointCount() > 0 && ln.CLastPoint() != aInitialPath.CLastPoint() )
432 {
433 st = ST_ALMOST_DONE;
434
435 }
436 PNS_DBG( Dbg(), Message, wxString::Format( "stat=%d", st ) );
437
438 }
439
440
441 return m_currentResult;
442}
443
444void WALKAROUND::SetAllowedPolicies( std::vector<WALK_POLICY> aPolicies, bool aAnyCompletePolicyIsSuccess )
445{
446 for( int i = 0; i < MaxWalkPolicies; i++ )
447 m_enabledPolicies[i] = false;
448
449 for ( auto p : aPolicies )
450 m_enabledPolicies[p] = true;
451
452 m_anyCompletePolicyIsSuccess = aAnyCompletePolicyIsSuccess;
453}
454
459
460
461}
462
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
constexpr coord_type GetLeft() const
Definition box2.h:231
constexpr coord_type GetRight() const
Definition box2.h:220
constexpr coord_type GetTop() const
Definition box2.h:232
constexpr coord_type GetBottom() const
Definition box2.h:225
CORNER_MODE
Corner modes.
Definition direction45.h:67
@ ROUNDED_90
H/V with filleted corners.
Definition direction45.h:71
@ MITERED_90
H/V only (90-degree corners)
Definition direction45.h:70
ROUTING_SETTINGS & Settings() const
Return current router settings.
DEBUG_DECORATOR * Dbg() const
Base class for PNS router board items.
Definition pns_item.h:98
virtual HOLE * Hole() const
Definition pns_item.h:308
virtual bool HasHole() const
Definition pns_item.h:307
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
const VECTOR2I & CPoint(int aIdx) const
Return the aIdx-th point of the line.
Definition pns_line.h:157
const SHAPE_LINE_CHAIN & CLine() const
Definition pns_line.h:149
const VECTOR2I & CLastPoint() const
Definition pns_line.h:158
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape.
Definition pns_line.h:148
VIA & Via()
Definition pns_line.h:212
int PointCount() const
Definition pns_line.h:152
bool EndsWithVia() const
Definition pns_line.h:204
Keep the router "world" - i.e.
Definition pns_node.h:274
std::optional< OBSTACLE > OPT_OBSTACLE
Definition pns_node.h:284
int Depth() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition pns_node.h:335
DIRECTION_45::CORNER_MODE GetCornerMode() const
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr, int aOverrideClearance=0)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies, bool aAnyCompletePolicyIsSuccess=false)
void RestrictToCluster(bool aEnabled, const TOPOLOGY::CLUSTER &aCluster)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
bool m_enabledPolicies[MaxWalkPolicies]
NODE::OPT_OBSTACLE nearestObstacle(const LINE &aPath)
std::vector< VECTOR2I > m_restrictedVertices
void SetClearanceOverride(CLEARANCE_OVERRIDE_FUNC aFunc)
void SetCollisionFilter(COLLISION_FILTER_FUNC aFilter)
COLLISION_FILTER_FUNC m_collisionFilter
void start(const LINE &aInitialPath)
static constexpr int MaxWalkPolicies
CLEARANCE_OVERRIDE_FUNC m_overrideClearance
bool m_anyCompletePolicyIsSuccess
std::set< ITEM * > m_processedItems
double m_lengthExpansionFactor
std::set< const ITEM * > m_restrictedSet
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
@ WHITE
Definition color4d.h:44
@ BLUE
Definition color4d.h:52
@ YELLOW
Definition color4d.h:63
@ RED
Definition color4d.h:55
int m_PNSProcessClusterTimeout
Timeout for the PNS router's processCluster wallclock timeout, in milliseconds.
Push and Shove diff pair dimensions (gap) settings dialog.
std::function< int(const ITEM *, const ITEM *, CLEARANCE_ASPECT)> CLEARANCE_OVERRIDE_FUNC
Definition pns_node.h:123
std::function< bool(const ITEM *, const ITEM *)> COLLISION_FILTER_FUNC
Definition pns_node.h:122
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
COLLISION_FILTER_FUNC m_filter
Definition pns_node.h:139
CLEARANCE_OVERRIDE_FUNC m_overrideClearance
Definition pns_node.h:140
std::vector< ITEM * > m_items
int clearance
wxString result
Test unit parsing edge cases and error handling.
Casted dyn_cast(From aObject)
A lightweight dynamic downcast.
Definition typeinfo.h:55