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 along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <chrono>
23#include <advanced_config.h>
24#include <optional>
25
27
28#include "pns_walkaround.h"
29#include "pns_optimizer.h"
30#include "pns_router.h"
31#include "pns_debug_decorator.h"
32#include "pns_solid.h"
33
34
35namespace PNS {
36
37void WALKAROUND::start( const LINE& aInitialPath )
38{
39 m_iteration = 0;
40 for( int pol = 0 ; pol < MaxWalkPolicies; pol++)
41 {
43 m_currentResult.lines[ pol ] = aInitialPath;
45 }
46}
47
48
50{
52
54
55 if( ! m_restrictedSet.empty() )
56 {
57 opts.m_filter = [ this ] ( const ITEM* item ) -> bool
58 {
59 if( m_restrictedSet.find( item ) != m_restrictedSet.end() )
60 return true;
61 return false;
62 };
63 }
64
65 opts.m_useClearanceEpsilon = false;
66 return m_world->NearestObstacle( &aPath, opts );
67}
68
69
70void WALKAROUND::RestrictToCluster( bool aEnabled, const TOPOLOGY::CLUSTER& aCluster )
71{
73 m_restrictedSet.clear();
74
75 if( aEnabled )
76 {
77 for( ITEM* item : aCluster.m_items )
78 {
79 m_restrictedSet.insert( item );
80
81 if ( item->HasHole() )
82 m_restrictedSet.insert( item->Hole() );
83 }
84 }
85
86 for( ITEM* item : aCluster.m_items )
87 {
88 if( SOLID* solid = dyn_cast<SOLID*>( item ) )
89 m_restrictedVertices.push_back( solid->Anchor( 0 ) );
90 }
91}
92
93static wxString policy2string ( WALKAROUND::WALK_POLICY policy )
94{
95 switch(policy)
96 {
97 case WALKAROUND::WP_CCW: return wxT("ccw");
98 case WALKAROUND::WP_CW: return wxT("cw");
99 case WALKAROUND::WP_SHORTEST: return wxT("shortest");
100 }
101 return wxT("?");
102}
103
105{
106 TOPOLOGY topo( m_world );
107 TOPOLOGY::CLUSTER pendingClusters[MaxWalkPolicies];
108
109 for( int i = 0; i < MaxWalkPolicies; i++ )
110 {
111 if( !m_enabledPolicies[i] )
112 continue;
113
114 auto& line = m_currentResult.lines[ i ];
115 auto& status = m_currentResult.status[ i ];
116
117 PNS_DBG( Dbg(), AddItem, &line, WHITE, 10000, wxString::Format( "current (policy %d, stat %d)", i, status ) );
118
119 if( status != ST_IN_PROGRESS )
120 continue;
121
122 auto obstacle = nearestObstacle( line );
123
124 if( !obstacle )
125 {
126
128 PNS_DBG( Dbg(), Message, wxString::Format( "no-more-colls pol %d st %d", i, status ) );
129
130 continue;
131 }
132
133
134 pendingClusters[ i ] = topo.AssembleCluster( obstacle->m_item, line.Layer(), 0.0, line.Net() );
135 PNS_DBG( Dbg(), AddItem, obstacle->m_item, BLUE, 10000, wxString::Format( "col-item owner-depth %d cl-items=%d", static_cast<const NODE*>( obstacle->m_item->Owner() )->Depth(), (int) pendingClusters[i].m_items.size() ) );
136
137 }
138
140
141 auto processCluster = [ & ] ( TOPOLOGY::CLUSTER& aCluster, LINE& aLine, bool aCw ) -> bool
142 {
143 using namespace std::chrono;
144 auto start_time = steady_clock::now();
145
147
148 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "cluster-details [cw %d]", aCw?1:0 ), 1 );
149
150 for( auto& clItem : aCluster.m_items )
151 {
152 // Check for wallclock timeout
153 // Emprically, 100ms seems to be about where you're not going to find a valid path
154 // if you haven't found it by then. This allows the user to adjust their mouse position
155 // to get a better path without waiting too long.
156 auto now = steady_clock::now();
157 auto elapsed = duration_cast<milliseconds>( now - start_time ).count();
158
159 if( elapsed > timeout_ms )
160 {
161 PNS_DBG( Dbg(), Message, wxString::Format( "processCluster timeout after %d ms", timeout_ms ) );
162 PNS_DBGN( Dbg(), EndGroup );
163 return false;
164 }
165
166 int clearance = m_world->GetClearance( clItem, &aLine, false );
167 SHAPE_LINE_CHAIN hull = clItem->Hull( clearance + 1000, aLine.Width(), aLine.Layer() );
168
169 if( cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90 )
170 {
171 BOX2I bbox = hull.BBox();
172 hull.Clear();
173 hull.Append( bbox.GetLeft(), bbox.GetTop() );
174 hull.Append( bbox.GetRight(), bbox.GetTop() );
175 hull.Append( bbox.GetRight(), bbox.GetBottom() );
176 hull.Append( bbox.GetLeft(), bbox.GetBottom() );
177 }
178
179 LINE tmp( aLine );
180
181 bool stat = aLine.Walkaround( hull, tmp.Line(), aCw );
182
183 PNS_DBG( Dbg(), AddShape, &hull, YELLOW, 10000, wxString::Format( "hull stat %d", stat?1:0 ) );
184 PNS_DBG( Dbg(), AddItem, &tmp, RED, 10000, wxString::Format( "walk stat %d", stat?1:0 ) );
185 PNS_DBG( Dbg(), AddItem, clItem, WHITE, 10000, wxString::Format( "item stat %d", stat?1:0 ) );
186
187 if( !stat )
188 {
189 PNS_DBGN( Dbg(), EndGroup );
190 return false;
191 }
192
193 aLine.SetShape( tmp.CLine() );
194 }
195
196 PNS_DBGN( Dbg(), EndGroup );
197
198 return true;
199 };
200
202 {
203 bool stat = processCluster( pendingClusters[ WP_CW ], m_currentResult.lines[ WP_CW ], true );
204 if( !stat )
206 }
207
209 {
210 bool stat = processCluster( pendingClusters[ WP_CCW ], m_currentResult.lines[ WP_CCW ], false );
211 if( !stat )
213 }
214
216 {
218 LINE path_cw( line ), path_ccw( line );
219
220 auto st_cw = processCluster( pendingClusters[WP_SHORTEST], path_cw, true );
221 auto st_ccw = processCluster( pendingClusters[WP_SHORTEST], path_ccw, false );
222
223 bool cw_coll = st_cw ? m_world->CheckColliding( &path_cw ).has_value() : false;
224 bool ccw_coll = st_ccw ? m_world->CheckColliding( &path_ccw ).has_value() : false;
225
226 double lengthFactorCw = (double) path_cw.CLine().Length() / (double) m_initialLength;
227 double lengthFactorCcw = (double) path_ccw.CLine().Length() / (double) m_initialLength;
228
229 PNS_DBG( Dbg(), AddItem, &path_cw, RED, 10000, wxString::Format( "shortest-cw stat %d lf %.1f", st_cw?1:0, lengthFactorCw ) );
230 PNS_DBG( Dbg(), AddItem, &path_ccw, BLUE, 10000, wxString::Format( "shortest-ccw stat %d lf %.1f", st_ccw?1:0, lengthFactorCcw ) );
231
232
233 std::optional<LINE> shortest;
234 std::optional<LINE> shortest_alt;
235
236
237 if( st_cw && st_ccw )
238 {
239 if( !cw_coll && !ccw_coll || ( cw_coll && ccw_coll) )
240 {
241 if( path_cw.CLine().Length() > path_ccw.CLine().Length() )
242 {
243 shortest = path_ccw;
244 shortest_alt = path_cw;
245 }
246 else
247 {
248 shortest = path_cw;
249 shortest_alt = path_ccw;
250 }
251 }
252 else if( !cw_coll )
253 shortest = path_cw;
254 else if( !ccw_coll )
255 shortest = path_ccw;
256
257 }
258 else if( st_ccw )
259 shortest = path_ccw;
260 else if( st_cw )
261 shortest = path_cw;
262
263 bool anyColliding = false;
264
265 if( m_lastShortestCluster && shortest.has_value() )
266 {
267 for( auto& item : m_lastShortestCluster->m_items )
268 {
269 if( shortest->Collide( item, m_world, shortest->Layer() ) )
270 {
271 anyColliding = true;
272 break;
273 }
274 }
275
276 PNS_DBG( Dbg(), Message, wxString::Format("check-back cc %d items %d coll %d", (int) pendingClusters[ WP_SHORTEST ].m_items.size(), (int) m_lastShortestCluster->m_items.size(), anyColliding ? 1: 0 ) );
277 }
278
279 if ( anyColliding )
280 {
281 shortest = std::move( shortest_alt );
282 }
283
284 if( !shortest )
285 {
287 }
288 else
289 {
290 m_currentResult.lines[WP_SHORTEST] = *shortest;
291 }
292
293 m_lastShortestCluster = pendingClusters[ WP_SHORTEST ];
294 }
295
296 return ST_IN_PROGRESS;
297}
298
299
300const WALKAROUND::RESULT WALKAROUND::Route( const LINE& aInitialPath )
301{
302 RESULT result;
303
304 m_initialLength = aInitialPath.CLine().Length();
305
306 // special case for via-in-the-middle-of-track placement
307
308#if 0
309 if( aInitialPath.PointCount() <= 1 )
310 {
311 if( aInitialPath.EndsWithVia() && m_world->CheckColliding( &aInitialPath.Via(),
312 m_itemMask ) )
313 {
314 // fixme restult
315 }
316 //return RESULT( STUCK, STUCK );
317
318 return RESULT(); //( DONE, DONE, aInitialPath, aInitialPath );
319 }
320#endif
321
322 start( aInitialPath );
323
324 PNS_DBG( Dbg(), AddItem, &aInitialPath, WHITE, 10000, wxT( "initial-path" ) );
325
327 {
328 singleStep();
329
330 bool stillInProgress = false;
331
332 for( int pol = 0; pol < MaxWalkPolicies; pol++ )
333 {
334 if (!m_enabledPolicies[pol])
335 continue;
336
337 auto& st = m_currentResult.status[pol];
338 auto& ln = m_currentResult.lines[pol];
339 double lengthFactor = (double) ln.CLine().Length() / (double) aInitialPath.CLine().Length();
340 // In some situations, there isn't a trivial path (or even a path at all). Hitting the
341 // iteration limit causes lag, so we can exit out early if the walkaround path gets very long
342 // compared with the initial path. If the length exceeds the initial length times this factor,
343 // fail out.
344 if( m_lengthLimitOn )
345 {
346 if( st != ST_DONE && lengthFactor > m_lengthExpansionFactor )
347 st = ST_ALMOST_DONE;
348 }
349
350 PNS_DBG( Dbg(), Message, wxString::Format( "check-wp iter %d st %d i %d lf %.1f", m_iteration, st, pol, lengthFactor ) );
351
352 if ( st == ST_IN_PROGRESS )
353 stillInProgress = true;
354 }
355
356
357 if( !stillInProgress )
358 break;
359
360 m_iteration++;
361 }
362
363
364 for( int pol = 0; pol < MaxWalkPolicies; pol++ )
365 {
366 auto& st = m_currentResult.status[pol];
367 const auto& ln = m_currentResult.lines[pol].CLine();
368
370 if( st == ST_IN_PROGRESS )
371 st = ST_ALMOST_DONE;
372
373 if( ln.SegmentCount() < 1 || ln.CPoint( 0 ) != aInitialPath.CPoint( 0 ) )
374 {
375 st = ST_STUCK;
376 }
377
378 if( ln.PointCount() > 0 && ln.CLastPoint() != aInitialPath.CLastPoint() )
379 {
380 st = ST_ALMOST_DONE;
381
382 }
383 PNS_DBG( Dbg(), Message, wxString::Format( "stat=%d", st ) );
384
385 }
386
387
388 return m_currentResult;
389}
390
391void WALKAROUND::SetAllowedPolicies( std::vector<WALK_POLICY> aPolicies)
392{
393 for( int i = 0; i < MaxWalkPolicies; i++ )
394 m_enabledPolicies[i] = false;
395
396 for ( auto p : aPolicies )
397 m_enabledPolicies[p] = true;
398}
399
400}
401
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:228
constexpr coord_type GetRight() const
Definition: box2.h:217
constexpr coord_type GetTop() const
Definition: box2.h:229
constexpr coord_type GetBottom() const
Definition: box2.h:222
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 the logger object, allowing to dump geometry to a file.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Base class for PNS router board items.
Definition: pns_item.h:98
virtual HOLE * Hole() const
Definition: pns_item.h:304
virtual bool HasHole() const
Definition: pns_item.h:303
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
Definition: pns_line.h:146
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
const VECTOR2I & CLastPoint() const
Definition: pns_line.h:147
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
VIA & Via()
Definition: pns_line.h:199
int PointCount() const
Definition: pns_line.h:141
bool EndsWithVia() const
Definition: pns_line.h:191
Keep the router "world" - i.e.
Definition: pns_node.h:232
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:129
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:410
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:242
int Depth() const
Definition: pns_node.h:282
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:286
DIRECTION_45::CORNER_MODE GetCornerMode() const
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr)
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 SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies)
void start(const LINE &aInitialPath)
static constexpr int MaxWalkPolicies
std::optional< TOPOLOGY::CLUSTER > m_lastShortestCluster
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 Clear()
Remove all points from the line chain.
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:48
@ BLUE
Definition: color4d.h:56
@ YELLOW
Definition: color4d.h:67
@ RED
Definition: color4d.h:59
int m_PNSProcessClusterTimeout
Timeout for the PNS router's processCluster wallclock timeout, in milliseconds.
Push and Shove diff pair dimensions (gap) settings dialog.
static wxString policy2string(WALKAROUND::WALK_POLICY policy)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
std::function< bool(const ITEM *)> m_filter
Definition: pns_node.h:120
std::set< ITEM * > m_items
Definition: pns_topology.h:47
LINE lines[MaxWalkPolicies]
STATUS status[MaxWalkPolicies]
int clearance