KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_shove.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-2023 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 <deque>
23#include <cassert>
24#include <math/box2.h>
25
26#include <wx/log.h>
27
28#include "pns_arc.h"
29#include "pns_line.h"
30#include "pns_node.h"
31#include "pns_debug_decorator.h"
32#include "pns_walkaround.h"
33#include "pns_shove.h"
34#include "pns_solid.h"
35#include "pns_optimizer.h"
36#include "pns_via.h"
37#include "pns_utils.h"
38#include "pns_router.h"
39#include "pns_topology.h"
40
41#include "time_limit.h"
42
43// fixme - move all logger calls to debug decorator
44
46
47namespace PNS {
48
49void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
50{
51 OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
52
53 if( changed_area )
54 m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
55
56 m_currentNode->Replace( aOld, std::move( aNew ) );
57}
58
59
60void SHOVE::replaceLine( LINE& aOld, LINE& aNew, bool aIncludeInChangedArea, NODE* aNode )
61{
62 if( aIncludeInChangedArea )
63 {
64 OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
65
66 if( changed_area )
67 {
68 SHAPE_RECT r( *changed_area );
69 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "shove-changed-area" ) );
70
71 m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area )
72 : *changed_area;
73 }
74 }
75
76 bool foundPredecessor = false;
77 LINE* rootLine = nullptr;
78
79 // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
80 // of the affected tracks in a map. The optimizer can then query the pre-shove shape
81 // for each shoved line and perform additional constraint checks (i.e. prevent overzealous
82 // optimizations)
83
84 // Check if the shoved line already has an ancestor (e.g. line from a previous shove
85 // iteration/cursor movement)
86 for( LINKED_ITEM* link : aOld.Links() )
87 {
88 auto oldLineIter = m_rootLineHistory.find( link );
89
90 if( oldLineIter != m_rootLineHistory.end() )
91 {
92 rootLine = oldLineIter->second;
93 foundPredecessor = true;
94 break;
95 }
96 }
97
98 // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
99 if( !foundPredecessor )
100 {
101 for( LINKED_ITEM* link : aOld.Links() )
102 {
103 if( ! rootLine )
104 rootLine = aOld.Clone();
105
106 m_rootLineHistory[link] = rootLine;
107 }
108 }
109
110 // Now update the NODE (calling Replace invalidates the Links() in a LINE)
111 if( aNode )
112 aNode->Replace( aOld, aNew );
113 else
114 m_currentNode->Replace( aOld, aNew );
115
116 // point the Links() of the new line to its oldest ancestor
117 for( LINKED_ITEM* link : aNew.Links() )
118 m_rootLineHistory[ link ] = rootLine;
119}
120
121
122int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
123{
124 if( m_forceClearance >= 0 )
125 return m_forceClearance;
126
127 int clearance = m_currentNode->GetClearance( aA, aB, false );
128
129 if( aA->HasHole() )
130 clearance = std::max( clearance, m_currentNode->GetClearance( aA->Hole(), aB, false ) );
131
132 if( aB->HasHole() )
133 clearance = std::max( clearance, m_currentNode->GetClearance( aA, aB->Hole(), false ) );
134
135 return clearance;
136}
137
138
139void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
140{
141 assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
142 assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
143}
144
145
146SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
147 ALGO_BASE( aRouter )
148{
150 m_forceClearance = -1;
151 m_root = aWorld;
152 m_currentNode = aWorld;
154
155 // Initialize other temporary variables:
156 m_draggedVia = nullptr;
157 m_iter = 0;
158 m_multiLineMode = false;
161}
162
163
165{
166 std::unordered_set<LINE*> alreadyDeleted;
167
168 for( auto& it : m_rootLineHistory )
169 {
170 auto it2 = alreadyDeleted.find( it.second );
171
172 if( it2 == alreadyDeleted.end() )
173 {
174 alreadyDeleted.insert( it.second );
175 delete it.second;
176 }
177 }
178}
179
180
181LINE SHOVE::assembleLine( const LINKED_ITEM* aSeg, int* aIndex )
182{
183 return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
184}
185
186
187// A dumb function that checks if the shoved line is shoved the right way, e.g. visually
188// "outwards" of the line/via applying pressure on it. Unfortunately there's no mathematical
189// concept of orientation of an open curve, so we use some primitive heuristics: if the shoved
190// line wraps around the start of the "pusher", it's likely shoved in wrong direction.
191
192// Update: there's no concept of an orientation of an open curve, but nonetheless Tom's dumb
193// as.... (censored)
194// Two open curves put together make a closed polygon... Tom should learn high school geometry!
195bool SHOVE::checkShoveDirection( const LINE& aCurLine, const LINE& aObstacleLine,
196 const LINE& aShovedLine ) const
197{
198 SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
199 checker.AddPolyline( aObstacleLine.CLine() );
200 checker.AddPolyline( aShovedLine.CLine().Reverse() );
201
202 bool inside = checker.IsInside();
203
204 return !inside;
205}
206
207
208/*
209 * Push aObstacleLine away from aCurLine's via by the clearance distance, returning the result
210 * in aResultLine.
211 *
212 * Must be called only when aCurLine itself is on another layer (or has no segments) so that it
213 * can be ignored.
214 */
215SHOVE::SHOVE_STATUS SHOVE::shoveLineFromLoneVia( const LINE& aCurLine, const LINE& aObstacleLine,
216 LINE& aResultLine )
217{
218 // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
219
220 int obstacleLineWidth = aObstacleLine.Width();
221 const VIA& via = aCurLine.Via();
222 int clearance = getClearance( &via, &aObstacleLine );
223 HOLE* viaHole = via.Hole();
224 int holeClearance = getClearance( viaHole, &aObstacleLine );
225
226 if( holeClearance + via.Drill() / 2 > clearance + via.Diameter() / 2 )
227 clearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
228
229 SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
230 SHAPE_LINE_CHAIN path_cw;
231 SHAPE_LINE_CHAIN path_ccw;
232
233 if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
234 return SH_INCOMPLETE;
235
236 if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
237 return SH_INCOMPLETE;
238
239 const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
240
241 if( shortest.PointCount() < 2 )
242 return SH_INCOMPLETE;
243
244 if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
245 return SH_INCOMPLETE;
246
247 if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
248 return SH_INCOMPLETE;
249
250 aResultLine.SetShape( shortest );
251
252 if( aResultLine.Collide( &aCurLine, m_currentNode ) )
253 return SH_INCOMPLETE;
254
255 return SH_OK;
256}
257
258
259/*
260 * Re-walk aObstacleLine around the given set of hulls, returning the result in aResultLine.
261 */
262SHOVE::SHOVE_STATUS SHOVE::shoveLineToHullSet( const LINE& aCurLine, const LINE& aObstacleLine,
263 LINE& aResultLine, const HULL_SET& aHulls )
264{
265 const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
266
267 int attempt;
268
269 PNS_DBG( Dbg(), BeginGroup, "shove-details", 1 );
270
271 for( attempt = 0; attempt < 4; attempt++ )
272 {
273 bool invertTraversal = ( attempt >= 2 );
274 bool clockwise = attempt % 2;
275 int vFirst = -1, vLast = -1;
276
277 LINE l( aObstacleLine );
279
280 for( int i = 0; i < (int) aHulls.size(); i++ )
281 {
282 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
283
284 PNS_DBG( Dbg(), AddShape, &hull, YELLOW, 10000, wxString::Format( "hull[%d]", i ) );
285 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path[%d]", i ) );
286 PNS_DBG( Dbg(), AddShape, &obs, LIGHTGRAY, aObstacleLine.Width(), wxString::Format( "obs[%d]", i ) );
287
288 if( !l.Walkaround( hull, path, clockwise ) )
289 {
290 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "Fail-Walk %s %s %d\n" ),
291 hull.Format().c_str(),
292 l.CLine().Format().c_str(),
293 clockwise? 1 : 0) );
294
295 PNS_DBGN( Dbg(), EndGroup );
296 return SH_INCOMPLETE;
297 }
298
299 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path-presimp[%d]", i ) );
300
301 path.Simplify();
302
303 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path-postsimp[%d]", i ) );
304
305 l.SetShape( path );
306 }
307
308 for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
309 {
310 if( path.CPoint( i ) != obs.CPoint( i ) )
311 {
312 vFirst = i;
313 break;
314 }
315 }
316
317 int k = obs.PointCount() - 1;
318
319 for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
320 {
321 if( path.CPoint( i ) != obs.CPoint( k ) )
322 {
323 vLast = i;
324 break;
325 }
326 }
327
328 if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
329 {
330 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vfirst-last" ),
331 attempt ) );
332 continue;
333 }
334
335 if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
336 {
337 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vend-start\n" ),
338 attempt ) );
339 continue;
340 }
341
342 if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
343 {
344 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail direction-check" ),
345 attempt ) );
346 aResultLine.SetShape( l.CLine() );
347 continue;
348 }
349
350 if( path.SelfIntersecting() )
351 {
352 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail self-intersect" ),
353 attempt ) );
354 continue;
355 }
356
357 bool colliding = l.Collide( &aCurLine, m_currentNode );
358
359 if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
360 {
361 const JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
362
363 for( ITEM* item : jtStart->LinkList() )
364 {
365 if( item->Collide( &l, m_currentNode ) )
366 colliding = true;
367 }
368 }
369
370 if( colliding )
371 {
372 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail coll-check" ),
373 attempt ) );
374 continue;
375 }
376
377 aResultLine.SetShape( l.CLine() );
378
379 PNS_DBGN( Dbg(), EndGroup );
380
381 return SH_OK;
382 }
383
384 PNS_DBGN( Dbg(), EndGroup );
385
386 return SH_INCOMPLETE;
387}
388
389
390/*
391 * Push aObstacleLine line away from aCurLine by the clearance distance, and return the result in
392 * aResultLine.
393 */
394SHOVE::SHOVE_STATUS SHOVE::ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine,
395 LINE& aResultLine )
396{
397 aResultLine.ClearLinks();
398
399 bool obstacleIsHead = false;
400
401 for( LINKED_ITEM* s : aObstacleLine.Links() )
402 {
403 if( s->Marker() & MK_HEAD )
404 {
405 obstacleIsHead = true;
406 break;
407 }
408 }
409
410 SHOVE_STATUS rv;
411 bool viaOnEnd = aCurLine.EndsWithVia();
412
413 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: voe1 %d voe2 %d" ),
414 aCurLine.EndsWithVia()?1:0, aObstacleLine.EndsWithVia()?1:0 ) );
415
416
417 if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
418 {
419 // Shove aObstacleLine to the hull of aCurLine's via.
420
421 rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
422 }
423 else
424 {
425 // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
426 // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
427 // hull it will be at the appropriate clearance.
428
429 int obstacleLineWidth = aObstacleLine.Width();
430 int clearance = getClearance( &aCurLine, &aObstacleLine );
431 int currentLineSegmentCount = aCurLine.SegmentCount();
432 HULL_SET hulls;
433
434 hulls.reserve( currentLineSegmentCount + 1 );
435
436 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: cur net %d obs %d cl %d" ),
437 m_router->GetInterface()->GetNetCode( aCurLine.Net() ),
438 m_router->GetInterface()->GetNetCode( aObstacleLine.Net() ),
439 clearance ) );
440
441 for( int i = 0; i < currentLineSegmentCount; i++ )
442 {
443 SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
444
445 // Arcs need additional clearance to ensure the hulls are always bigger than the arc
446 if( aCurLine.CLine().IsArcSegment( i ) )
447 {
448 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove add-extra-clearance %d" ),
451 }
452
453 SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
454
455 hulls.push_back( hull );
456 }
457
458 if( viaOnEnd )
459 {
460 const VIA& via = aCurLine.Via();
461 int viaClearance = getClearance( &via, &aObstacleLine );
462 HOLE* viaHole = via.Hole();
463 int holeClearance = getClearance( viaHole, &aObstacleLine );
464
465 if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
466 viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
467
468 hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
469 }
470
471 rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
472 }
473
474 if( obstacleIsHead )
475 aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
476
477 return rv;
478}
479
480
481/*
482 * TODO describe....
483 */
485{
486 int segIndex;
487 LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
488 LINE shovedLine( obstacleLine );
489 SEGMENT tmp( *aObstacleSeg );
490
491 if( obstacleLine.HasLockedSegments() )
492 {
493 PNS_DBG(Dbg(), Message, "try walk (locked segments)");
494 return SH_TRY_WALK;
495 }
496
497 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
498
499 const double extensionWalkThreshold = 1.0;
500
501 double obsLen = obstacleLine.CLine().Length();
502 double shovedLen = shovedLine.CLine().Length();
503 double extensionFactor = 0.0;
504
505 if( obsLen != 0.0f )
506 extensionFactor = shovedLen / obsLen - 1.0;
507
508 if( extensionFactor > extensionWalkThreshold )
509 return SH_TRY_WALK;
510
511 assert( obstacleLine.LayersOverlap( &shovedLine ) );
512
513 if( Dbg() )
514 {
515 PNS_DBG( Dbg(), AddItem, aObstacleSeg, BLUE, 0, wxT( "shove-changed-area" ) );
516 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxString::Format( "current-line [l %d v %d]", aCurrent.Layer(), aCurrent.EndsWithVia() ) );
517 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxString::Format( "obstacle-line [l %d v %d]", obstacleLine.Layer(), obstacleLine.EndsWithVia() ) );
518 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
519 }
520
521 if( rv == SH_OK )
522 {
523 if( shovedLine.Marker() & MK_HEAD )
524 {
525 if( m_multiLineMode )
526 return SH_INCOMPLETE;
527
528 m_newHead = shovedLine;
529 }
530
531 int rank = aCurrent.Rank();
532 shovedLine.SetRank( rank - 1 );
533
534 sanityCheck( &obstacleLine, &shovedLine );
535 replaceLine( obstacleLine, shovedLine );
536
537 if( !pushLineStack( shovedLine ) )
538 rv = SH_INCOMPLETE;
539 }
540
541 return rv;
542}
543
544
545/*
546 * TODO describe....
547 */
549{
550 int segIndex;
551 LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
552 LINE shovedLine( obstacleLine );
553 ARC tmp( *aObstacleArc );
554
555 if( obstacleLine.HasLockedSegments() )
556 return SH_TRY_WALK;
557
558 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
559
560 const double extensionWalkThreshold = 1.0;
561
562 double obsLen = obstacleLine.CLine().Length();
563 double shovedLen = shovedLine.CLine().Length();
564 double extensionFactor = 0.0;
565
566 if( obsLen != 0.0f )
567 extensionFactor = shovedLen / obsLen - 1.0;
568
569 if( extensionFactor > extensionWalkThreshold )
570 return SH_TRY_WALK;
571
572 assert( obstacleLine.LayersOverlap( &shovedLine ) );
573
574 PNS_DBG( Dbg(), AddItem, &tmp, WHITE, 10000, wxT( "obstacle-arc" ) );
575 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
576 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxT( "obstacle-line" ) );
577 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
578
579 if( rv == SH_OK )
580 {
581 if( shovedLine.Marker() & MK_HEAD )
582 {
583 if( m_multiLineMode )
584 return SH_INCOMPLETE;
585
586 m_newHead = shovedLine;
587 }
588
589 int rank = aCurrent.Rank();
590 shovedLine.SetRank( rank - 1 );
591
592 sanityCheck( &obstacleLine, &shovedLine );
593 replaceLine( obstacleLine, shovedLine );
594
595 if( !pushLineStack( shovedLine ) )
596 rv = SH_INCOMPLETE;
597 }
598
599 return rv;
600}
601
602
603/*
604 * TODO describe....
605 */
607{
608 LINE shovedLine( aObstacle );
609
610 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
611
612 PNS_DBG( Dbg(), AddItem, &aObstacle, RED, 100000, wxT( "obstacle-line" ) );
613 PNS_DBG( Dbg(), AddItem, &aCurrent, GREEN, 150000, wxT( "current-line" ) );
614 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 200000, wxT( "shoved-line" ) );
615
616 if( rv == SH_OK )
617 {
618 if( shovedLine.Marker() & MK_HEAD )
619 {
620 if( m_multiLineMode )
621 return SH_INCOMPLETE;
622
623 m_newHead = shovedLine;
624 }
625
626 sanityCheck( &aObstacle, &shovedLine );
627 replaceLine( aObstacle, shovedLine );
628
629 int rank = aObstacle.Rank();
630 shovedLine.SetRank( rank - 1 );
631
632
633 if( !pushLineStack( shovedLine ) )
634 {
635 rv = SH_INCOMPLETE;
636 }
637 }
638
639 return rv;
640}
641
642
643/*
644 * TODO describe....
645 */
646SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle, OBSTACLE& aObstacleInfo )
647{
648 WALKAROUND walkaround( m_currentNode, Router() );
649 LINE walkaroundLine( aCurrent );
650
651 if( aCurrent.EndsWithVia() )
652 {
653 VIA vh = aCurrent.Via();
654 VIA* via = nullptr;
655 const JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
656
657 if( !jtStart )
658 return SH_INCOMPLETE;
659
660 for( ITEM* item : jtStart->LinkList() )
661 {
662 if( item->OfKind( ITEM::VIA_T ) )
663 {
664 via = (VIA*) item;
665 break;
666 }
667 }
668
669 if( via && via->Collide( aObstacle, m_currentNode ) )
670 return onCollidingVia( aObstacle, via, aObstacleInfo );
671 }
672
673 TOPOLOGY topo( m_currentNode );
674
675 std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
676
677
678 PNS_DBG( Dbg(), BeginGroup, "walk-cluster", 1 );
679
680 for( ITEM* item : cluster )
681 PNS_DBG( Dbg(), AddItem, item, RED, 10000, wxT( "cl-item" ) );
682
683 PNS_DBGN( Dbg(), EndGroup );
684
685
686 walkaround.SetDebugDecorator( Dbg() );
687 walkaround.SetSolidsOnly( false );
688 walkaround.RestrictToSet( true, cluster );
689 walkaround.SetIterationLimit( 16 ); // fixme: make configurable
690
691 int currentRank = aCurrent.Rank();
692 int nextRank;
693
694 bool success = false;
695
696 for( int attempt = 0; attempt < 2; attempt++ )
697 {
698 if( attempt == 1 || Settings().JumpOverObstacles() )
699 nextRank = currentRank - 1;
700 else
701 nextRank = currentRank + 10000;
702
703 WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
704
705 if( status != WALKAROUND::DONE )
706 continue;
707
708 walkaroundLine.ClearLinks();
709 walkaroundLine.Unmark();
710 walkaroundLine.Line().Simplify();
711
712 if( walkaroundLine.HasLoops() )
713 continue;
714
715 if( aCurrent.Marker() & MK_HEAD )
716 {
717 walkaroundLine.Mark( MK_HEAD );
718
719 if( m_multiLineMode )
720 continue;
721
722 m_newHead = walkaroundLine;
723 }
724
725 sanityCheck( &aCurrent, &walkaroundLine );
726
727 if( !m_lineStack.empty() )
728 {
729 LINE lastLine = m_lineStack.front();
730
731 if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
732 {
733 LINE dummy( lastLine );
734
735 if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
736 {
737 success = true;
738 break;
739 }
740 }
741 else
742 {
743 success = true;
744 break;
745 }
746 }
747 }
748
749 if(!success)
750 return SH_INCOMPLETE;
751
752 replaceLine( aCurrent, walkaroundLine );
753 walkaroundLine.SetRank( nextRank );
754
755 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
756 PNS_DBG( Dbg(), AddItem, &walkaroundLine, BLUE, 10000, wxT( "walk-line" ) );
757
758 popLineStack();
759
760 if( !pushLineStack( walkaroundLine ) )
761 return SH_INCOMPLETE;
762
763 return SH_OK;
764}
765
766
767/*
768 * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
769 * to the dragged via of the last unpopped state.
770 */
771NODE* SHOVE::reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia )
772{
773 while( !m_nodeStack.empty() )
774 {
775 SPRINGBACK_TAG& spTag = m_nodeStack.back();
776
777 // Prevent the springback algo from erasing NODEs that might contain items used by the ROUTER_TOOL/LINE_PLACER.
778 // I noticed this can happen for the endItem provided to LINE_PLACER::Move() and cause a nasty crash.
780 break;
781
782 std::optional<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
783
784 if( !obs && !spTag.m_locked )
785 {
786 aDraggedVia = spTag.m_draggedVia;
787 aDraggedVia.valid = true;
788
789 delete spTag.m_node;
790 m_nodeStack.pop_back();
791 }
792 else
793 {
794 break;
795 }
796 }
797
798 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
799}
800
801
802/*
803 * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
804 * (which will be restored in the event the stackframe is popped).
805 */
806bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia )
807{
809 OPT_BOX2I prev_area;
810
811 if( !m_nodeStack.empty() )
812 prev_area = m_nodeStack.back().m_affectedArea;
813
814 if( aDraggedVia )
815 {
816 st.m_draggedVia = aDraggedVia->MakeHandle();
817 }
818
819 st.m_node = aNode;
820
821 if( aAffectedArea )
822 {
823 if( prev_area )
824 st.m_affectedArea = prev_area->Merge( *aAffectedArea );
825 else
826 st.m_affectedArea = aAffectedArea;
827 }
828 else
829 {
830 st.m_affectedArea = prev_area;
831 }
832
833 st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
834 st.m_locked = false;
835
836 m_nodeStack.push_back( st );
837
838 return true;
839}
840
841
842/*
843 * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
844 * to keep it from landing on an existing joint.)
845 */
846SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank )
847{
848 LINE_PAIR_VEC draggedLines;
849 VECTOR2I p0( aVia->Pos() );
850 const JOINT* jt = m_currentNode->FindJoint( p0, aVia );
851 VECTOR2I p0_pushed( p0 + aForce );
852
853 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "via force [%d %d]\n" ), aForce.x, aForce.y ) );
854
855 // nothing to do...
856 if ( aForce.x == 0 && aForce.y == 0 )
857 return SH_OK;
858
859 if( !jt )
860 {
861 PNS_DBG( Dbg(), Message, wxT( "weird, can't find the center-of-via joint\n" ) );
862 return SH_INCOMPLETE;
863 }
864
865 if( Settings().ShoveVias() == false || aVia->IsLocked() )
866 return SH_TRY_WALK;
867
868 if( jt->IsLocked() )
869 return SH_INCOMPLETE;
870
871 // make sure pushed via does not overlap with any existing joint
872 while( true )
873 {
874 const JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
875
876 if( !jt_next )
877 break;
878
879 p0_pushed += aForce.Resize( 2 );
880 }
881
882 std::unique_ptr<VIA> pushedVia = Clone( *aVia );
883 pushedVia->SetPos( p0_pushed );
884 pushedVia->Mark( aVia->Marker() );
885
886 for( ITEM* item : jt->LinkList() )
887 {
888 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
889 {
890 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
891 LINE_PAIR lp;
892 int segIndex;
893
894 lp.first = assembleLine( li, &segIndex );
895
896 if( lp.first.HasLockedSegments() )
897 return SH_TRY_WALK;
898
899 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
900
901 if( segIndex == 0 )
902 lp.first.Reverse();
903
904 lp.second = lp.first;
905 lp.second.ClearLinks();
906 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
907 lp.second.AppendVia( *pushedVia );
908 draggedLines.push_back( lp );
909 }
910 }
911
912 pushedVia->SetRank( aCurrentRank - 1 );
913 PNS_DBG( Dbg(), Message, wxString::Format("PushViaRank %d\n", pushedVia->Rank() ) );
914
915 if( aVia->Marker() & MK_HEAD ) // push
916 {
917 m_draggedVia = pushedVia.get();
918 }
919 else
920 { // shove
921 if( jt->IsStitchingVia() )
922 pushLineStack( LINE( *pushedVia ) );
923 }
924
925 PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
926 PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
927
928 replaceItems( aVia, std::move( pushedVia ) );
929
930 for( LINE_PAIR lp : draggedLines )
931 {
932 if( lp.first.Marker() & MK_HEAD )
933 {
934 lp.second.Mark( MK_HEAD );
935
936 if( m_multiLineMode )
937 return SH_INCOMPLETE;
938
939 m_newHead = lp.second;
940 }
941
942 unwindLineStack( &lp.first );
943
944 if( lp.second.SegmentCount() )
945 {
946 replaceLine( lp.first, lp.second );
947 lp.second.SetRank( aCurrentRank - 1 );
948
949 PNS_DBG( Dbg(), Message, wxString::Format("PushViaF %p %d\n", &lp.second, lp.second.SegmentCount() ) );
950
951 if( !pushLineStack( lp.second, true ) )
952 return SH_INCOMPLETE;
953 }
954 else
955 {
956 m_currentNode->Remove( lp.first );
957 }
958
959 PNS_DBG( Dbg(), AddItem, &lp.first, LIGHTGREEN, 10000, wxT( "fan-pre" ) );
960 PNS_DBG( Dbg(), AddItem, &lp.second, LIGHTRED, 10000, wxT( "fan-post" ) );
961 }
962
963 return SH_OK;
964}
965
966
967/*
968 * Calculate the minimum translation vector required to resolve a collision with a via and
969 * shove the via by that distance.
970 */
971SHOVE::SHOVE_STATUS SHOVE::onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia, OBSTACLE& aObstacleInfo )
972{
973 assert( aObstacleVia );
974
975 int clearance = getClearance( aCurrent, aObstacleVia );
976 VECTOR2I mtv;
977 int rank = -1;
978
979 bool lineCollision = false;
980 bool viaCollision = false;
981 VECTOR2I mtvLine, mtvVia;
982
983 PNS_DBG( Dbg(), BeginGroup, "push-via-by-line", 1 );
984
985 if( aCurrent->OfKind( ITEM::LINE_T ) )
986 {
987 VIA vtmp ( *aObstacleVia );
988
989 if( aObstacleInfo.m_maxFanoutWidth > 0 && aObstacleInfo.m_maxFanoutWidth > aObstacleVia->Diameter() )
990 {
991 vtmp.SetDiameter( aObstacleInfo.m_maxFanoutWidth );
992 }
993
994 LINE* currentLine = (LINE*) aCurrent;
995
996 PNS_DBG( Dbg(), AddItem, currentLine, LIGHTRED, 10000, wxT( "current-line" ) );
997
998 if( currentLine->EndsWithVia() )
999 {
1000 PNS_DBG( Dbg(), AddItem, &currentLine->Via(), LIGHTRED, 10000, wxT( "current-line-via" ) );
1001 }
1002
1003 PNS_DBG( Dbg(), AddItem, &vtmp, LIGHTRED, 100000, wxT( "orig-via" ) );
1004
1005 lineCollision = vtmp.Shape()->Collide( currentLine->Shape(),
1006 clearance + currentLine->Width() / 2,
1007 &mtvLine );
1008
1009 // Check the via if present. Via takes priority.
1010 if( currentLine->EndsWithVia() )
1011 {
1012 const VIA& currentVia = currentLine->Via();
1013 int viaClearance = getClearance( &currentVia, &vtmp );
1014
1015 viaCollision = currentVia.Shape()->Collide( vtmp.Shape(), viaClearance, &mtvVia );
1016 }
1017 }
1018 else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1019 {
1020 // TODO: is this possible at all? We don't shove solids.
1021 return SH_INCOMPLETE;
1022 }
1023
1024 // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1025 if( viaCollision )
1026 mtv = -mtvVia;
1027 else if ( lineCollision )
1028 mtv = -mtvLine;
1029 else
1030 mtv = VECTOR2I(0, 0);
1031
1032 SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, aCurrent->Rank() );
1033 PNS_DBG( Dbg(), Message, wxString::Format("push-or-shove-via st %d", st ) );
1034
1035 PNS_DBGN( Dbg(), EndGroup );
1036
1037 return st;
1038}
1039
1040
1041/*
1042 * TODO describe....
1043 */
1045{
1046 int n = 0;
1047 LINE cur( aCurrent );
1048 cur.ClearLinks();
1049
1050 const JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1051 LINE shoved( aCurrent );
1052 shoved.ClearLinks();
1053
1054 cur.RemoveVia();
1055 unwindLineStack( &aCurrent );
1056
1057 for( ITEM* item : jt->LinkList() )
1058 {
1059 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1060 {
1061 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1062 LINE head = assembleLine( li );
1063
1064 head.AppendVia( *aObstacleVia );
1065
1066 SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1067
1068 if( st != SH_OK )
1069 {
1070 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via-fail-shove", m_iter );
1071 PNS_DBG( Dbg(), AddItem, aObstacleVia, LIGHTRED, 100000, wxT( "the-via" ) );
1072 PNS_DBG( Dbg(), AddItem, &aCurrent, LIGHTGREEN, 10000, wxT( "current-line" ) );
1073 PNS_DBG( Dbg(), AddItem, &shoved, LIGHTRED, 10000, wxT( "shoved-line" ) );
1074 PNS_DBGN( Dbg(), EndGroup );
1075
1076 return st;
1077 }
1078
1079 cur.SetShape( shoved.CLine() );
1080 n++;
1081 }
1082 }
1083
1084 if( !n )
1085 {
1086 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via-fail-lonevia", m_iter );
1087 PNS_DBG( Dbg(), AddItem, aObstacleVia, LIGHTRED, 100000, wxT( "the-via" ) );
1088 PNS_DBG( Dbg(), AddItem, &aCurrent, LIGHTGREEN, 10000, wxT( "current-line" ) );
1089 PNS_DBGN( Dbg(), EndGroup );
1090
1091 LINE head( aCurrent );
1092 head.Line().Clear();
1093 head.AppendVia( *aObstacleVia );
1094 head.ClearLinks();
1095
1096 SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1097
1098 if( st != SH_OK )
1099 return st;
1100
1101 cur.SetShape( shoved.CLine() );
1102 }
1103
1104 if( aCurrent.EndsWithVia() )
1105 shoved.AppendVia( aCurrent.Via() );
1106
1107 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via", m_iter );
1108 PNS_DBG( Dbg(), AddItem, aObstacleVia, YELLOW, 0, wxT( "rr-the-via" ) );
1109 PNS_DBG( Dbg(), AddItem, &aCurrent, BLUE, 0, wxT( "rr-current-line" ) );
1110 PNS_DBG( Dbg(), AddItem, &shoved, GREEN, 0, wxT( "rr-shoved-line" ) );
1111 PNS_DBGN( Dbg(), EndGroup );
1112
1113 int currentRank = aCurrent.Rank();
1114 replaceLine( aCurrent, shoved );
1115
1116 if( !pushLineStack( shoved ) )
1117 return SH_INCOMPLETE;
1118
1119 shoved.SetRank( currentRank );
1120
1121 return SH_OK;
1122}
1123
1124
1126{
1127 int d = 0;
1128
1129 for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1130 {
1131 if( i->ContainsLink( aSeg ) )
1132 {
1133 PNS_DBG(Dbg(), Message, wxString::Format("Unwind lc %d (depth %d/%d)", i->SegmentCount(), d, (int)m_lineStack.size() ) );
1134 i = m_lineStack.erase( i );
1135 }
1136 else
1137 {
1138 i++;
1139 }
1140
1141 d++;
1142 }
1143
1144 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1145 {
1146 if( i->ContainsLink( aSeg ) )
1147 i = m_optimizerQueue.erase( i );
1148 else
1149 i++;
1150 }
1151}
1152
1153
1154void SHOVE::unwindLineStack( const ITEM* aItem )
1155{
1156 if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1157 {
1158 unwindLineStack( static_cast<const LINKED_ITEM*>( aItem ) );
1159 }
1160 else if( aItem->OfKind( ITEM::LINE_T ) )
1161 {
1162 const LINE* l = static_cast<const LINE*>( aItem );
1163
1164 for( const LINKED_ITEM* seg : l->Links() )
1165 unwindLineStack( seg );
1166 }
1167}
1168
1169
1170bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1171{
1172 if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1173 {
1174 PNS_DBG( Dbg(), AddItem, &aL, BLUE, 10000, wxT( "push line stack failed" ) );
1175
1176 return false;
1177 }
1178
1179 if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1180 {
1181 m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1182 }
1183 else
1184 {
1185 m_lineStack.push_back( aL );
1186 }
1187
1188 m_optimizerQueue.push_back( aL );
1189
1190 return true;
1191}
1192
1193
1195{
1196 LINE& l = m_lineStack.back();
1197
1198 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1199 {
1200 bool found = false;
1201
1202 for( LINKED_ITEM* s : l.Links() )
1203 {
1204 if( i->ContainsLink( s ) )
1205 {
1206 i = m_optimizerQueue.erase( i );
1207 found = true;
1208 break;
1209 }
1210 }
1211
1212 if( !found )
1213 i++;
1214 }
1215
1216 m_lineStack.pop_back();
1217}
1218
1219
1220bool SHOVE::fixupViaCollisions( const LINE* aCurrent, OBSTACLE& obs )
1221{
1222 // if the current obstacle is a via, consider also the lines connected to it
1223 // if their widths are larger or equal than the via diameter, the shove algorithm
1224 // will very likely fail in the subsequent iterations (as our base assumption is track
1225 // ends can never move on their own, only dragged by force-propagated vias
1226
1227 // our colliding item is a via: just find the max width of the traces connected to it
1228 if( obs.m_item->OfKind( ITEM::VIA_T ) )
1229 {
1230 const VIA* v = static_cast<const VIA*>( obs.m_item );
1231 int maxw = 0;
1232 const JOINT* jv = m_currentNode->FindJoint( v->Pos(), v );
1233
1234 ITEM_SET links( jv->CLinks() );
1235
1236 for( ITEM* link : links )
1237 {
1238 if( link->OfKind( ITEM::SEGMENT_T ) ) // consider segments ...
1239 {
1240 const SEGMENT* seg = static_cast<const SEGMENT*>( link );
1241 maxw = std::max( seg->Width(), maxw );
1242 }
1243 else if( link->OfKind( ITEM::ARC_T ) ) // ... or arcs
1244 {
1245 const ARC* arc = static_cast<const ARC*>( link );
1246 maxw = std::max( arc->Width(), maxw );
1247 }
1248 }
1249
1250 obs.m_maxFanoutWidth = 0;
1251
1252 if( maxw > 0 && maxw >= v->Diameter() )
1253 {
1254 obs.m_maxFanoutWidth = maxw + 1;
1255 PNS_DBG( Dbg(), Message,
1256 wxString::Format( "Fixup via: new-w %d via-w %d", maxw, v->Diameter() ) );
1257
1258 return true;
1259 }
1260 return false;
1261 }
1262
1263
1264 // our colliding item is a segment. check if it has a via on either of the ends.
1265 if( !obs.m_item->OfKind( ITEM::SEGMENT_T ) )
1266 return false;
1267
1268 const SEGMENT* s = static_cast<const SEGMENT*>( obs.m_item );
1269
1270 const JOINT* ja = m_currentNode->FindJoint( s->Seg().A, s );
1271 const JOINT* jb = m_currentNode->FindJoint( s->Seg().B, s );
1272
1273 VIA* vias[] = { ja->Via(), jb->Via() };
1274
1275 for( int i = 0; i < 2; i++ )
1276 {
1277 VIA* v = vias[i];
1278
1279 // via diameter is larger than the segment width - cool, the force propagation algo
1280 // will be able to deal with it, no need to intervene
1281 if( !v || v->Diameter() > s->Width() )
1282 continue;
1283
1284 VIA vtest( *v );
1285 vtest.SetDiameter( s->Width() );
1286
1287 // enlarge the via to the width of the segment
1288 if( vtest.Collide( aCurrent, m_currentNode ) )
1289 {
1290 // if colliding, drop the segment in the shove iteration loop and force-propagate the via instead
1291 obs.m_item = v;
1292 obs.m_maxFanoutWidth = s->Width() + 1;
1293 return true;
1294 }
1295 }
1296 return false;
1297}
1298
1299/*
1300 * Resolve the next collision.
1301 */
1303{
1304 LINE currentLine = m_lineStack.back();
1305 NODE::OPT_OBSTACLE nearest;
1306 SHOVE_STATUS st = SH_NULL;
1307
1308 if( Dbg() )
1309 Dbg()->SetIteration( aIter );
1310
1311 PNS_DBG( Dbg(), AddItem, &currentLine, RED, currentLine.Width(),
1312 wxString::Format( wxT( "current-coll-chk rank %d" ), currentLine.Rank() ) );
1313
1315 {
1317 opts.m_kindMask = search_order;
1318
1319 nearest = m_currentNode->NearestObstacle( &currentLine, opts );
1320
1321 if( nearest )
1322 {
1323 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "nearest %p %s rank %d" ),
1324 nearest->m_item,
1325 nearest->m_item->KindStr(),
1326 nearest->m_item->Rank() ) );
1327
1328 PNS_DBG( Dbg(), AddShape, nearest->m_item->Shape(), YELLOW, 10000, wxT( "nearest" ) );
1329 }
1330
1331 if( nearest )
1332 break;
1333 }
1334
1335 if( !nearest )
1336 {
1337 m_lineStack.pop_back();
1338 PNS_DBG( Dbg(), Message, wxT( "no-nearest-item ") );
1339 return SH_OK;
1340 }
1341
1342 bool viaFixup = fixupViaCollisions( &currentLine, *nearest );
1343
1344 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "iter %d: VF %d" ), aIter, viaFixup?1:0 ) );
1345
1346
1347 ITEM* ni = nearest->m_item;
1348
1349 UNITS_PROVIDER up( pcbIUScale, EDA_UNITS::MILLIMETRES );
1350 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "NI: %s (%s)" ),
1351 ni->Format(),
1352 ni->Parent() ? ni->Parent()->GetItemDescription( &up )
1353 : wxString( wxT( "null" ) ) ) );
1354
1355 unwindLineStack( ni );
1356
1357 if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1358 {
1359 // Collision with a higher-ranking object (ie: one that we've already shoved)
1360 //
1361 switch( ni->Kind() )
1362 {
1363 case ITEM::VIA_T:
1364 {
1365 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-via" ), aIter ), 0 );
1366
1367 if( currentLine.EndsWithVia() && nearest->m_item->Collide( &currentLine.Via(), m_currentNode ) )
1368 {
1369 st = SH_INCOMPLETE;
1370 }
1371 else
1372 {
1373 st = onReverseCollidingVia( currentLine, (VIA*) ni );
1374 }
1375
1376 PNS_DBGN( Dbg(), EndGroup );
1377
1378 break;
1379 }
1380
1381 case ITEM::SEGMENT_T:
1382 {
1383 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-segment " ),
1384 aIter ), 0 );
1385 LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1386
1387 popLineStack();
1388 st = onCollidingLine( revLine, currentLine );
1389
1390
1391 if( !pushLineStack( revLine ) )
1392 {
1393 return SH_INCOMPLETE;
1394 }
1395
1396
1397 PNS_DBGN( Dbg(), EndGroup );
1398
1399 break;
1400 }
1401
1402 case ITEM::ARC_T:
1403 {
1404 //TODO(snh): Handle Arc shove separate from track
1405 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-arc " ), aIter ), 0 );
1406 LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1407
1408 popLineStack();
1409 st = onCollidingLine( revLine, currentLine );
1410
1411 PNS_DBGN( Dbg(), EndGroup );
1412
1413 if( !pushLineStack( revLine ) )
1414 return SH_INCOMPLETE;
1415
1416 break;
1417 }
1418
1419 default:
1420 assert( false );
1421 }
1422 }
1423 else
1424 {
1425 // Collision with a lower-ranking object or a solid
1426 //
1427 switch( ni->Kind() )
1428 {
1429 case ITEM::SEGMENT_T:
1430 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-segment " ), aIter ), 0 );
1431
1432 st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1433
1434 if( st == SH_TRY_WALK )
1435 st = onCollidingSolid( currentLine, ni, *nearest );
1436
1437 PNS_DBGN( Dbg(), EndGroup );
1438
1439 break;
1440
1441 //TODO(snh): Customize Arc collide
1442 case ITEM::ARC_T:
1443 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-arc " ), aIter ), 0 );
1444
1445 st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1446
1447 if( st == SH_TRY_WALK )
1448 st = onCollidingSolid( currentLine, ni, *nearest );
1449
1450 PNS_DBGN( Dbg(), EndGroup );
1451
1452 break;
1453
1454 case ITEM::VIA_T:
1455 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-via (fixup: %d)" ), aIter, 0 ), 0 );
1456 st = onCollidingVia( &currentLine, (VIA*) ni, *nearest );
1457
1458 if( st == SH_TRY_WALK )
1459 st = onCollidingSolid( currentLine, ni, *nearest );
1460
1461 PNS_DBGN( Dbg(), EndGroup );
1462
1463 break;
1464
1465 case ITEM::HOLE_T:
1466 case ITEM::SOLID_T:
1467 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: walk-solid " ), aIter ), 0);
1468 st = onCollidingSolid( currentLine, ni, *nearest );
1469
1470 PNS_DBGN( Dbg(), EndGroup );
1471
1472 break;
1473
1474 default:
1475 break;
1476 }
1477 }
1478
1479 return st;
1480}
1481
1482
1483/*
1484 * Resolve collisions.
1485 * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1486 * long as they propagate further collisions, or until the iteration timeout or max iteration
1487 * count is reached.
1488 */
1490{
1491 SHOVE_STATUS st = SH_OK;
1492
1494
1495 PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1496 m_root->JointCount(),
1498
1499 int iterLimit = Settings().ShoveIterationLimit();
1500 TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1501
1502 m_iter = 0;
1503
1504 timeLimit.Restart();
1505
1506 if( m_lineStack.empty() && m_draggedVia )
1507 {
1508 // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1509 // the stack.
1511 }
1512
1513 while( !m_lineStack.empty() )
1514 {
1515 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1516 m_currentNode, (int) m_lineStack.size() ) );
1517
1518 st = shoveIteration( m_iter );
1519
1520 m_iter++;
1521
1522 if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1523 {
1524 PNS_DBG( Dbg(), Message, wxString::Format( "Fail [time limit expired: %d iter %d iter limit %d",
1525 timeLimit.Expired()?1:0, m_iter, iterLimit ) );
1526 st = SH_INCOMPLETE;
1527 break;
1528 }
1529 }
1530
1531 return st;
1532}
1533
1534
1536{
1537 OPT_BOX2I area;
1538
1539 if( !m_nodeStack.empty() )
1540 area = m_nodeStack.back().m_affectedArea;
1541
1542 if( area && m_affectedArea)
1543 area->Merge( *m_affectedArea );
1544 else if( !area )
1545 area = m_affectedArea;
1546
1547 return area;
1548}
1549
1550
1552{
1553 SHOVE_STATUS st = SH_OK;
1554
1555 m_multiLineMode = false;
1556
1557 PNS_DBG( Dbg(), Message,
1558 wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) )
1559
1560 // empty head? nothing to shove...
1561 if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1562 return SH_INCOMPLETE;
1563
1564 LINE head( aCurrentHead );
1565 head.ClearLinks();
1566
1567 m_lineStack.clear();
1568 m_optimizerQueue.clear();
1569 m_newHead = OPT_LINE();
1570
1571 // Pop NODEs containing previous shoves which are no longer necessary
1572 //
1573 ITEM_SET headSet;
1574 headSet.Add( aCurrentHead );
1575
1576 VIA_HANDLE dummyVia;
1577
1578 NODE* parent = reduceSpringback( headSet, dummyVia );
1579
1580 // Create a new NODE to store this version of the world
1581 m_currentNode = parent->Branch();
1583 m_currentNode->Add( head );
1584
1585 m_currentNode->LockJoint( head.CPoint(0), &head, true );
1586
1587 if( !head.EndsWithVia() )
1588 m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1589
1590 head.Mark( MK_HEAD );
1591 head.SetRank( 100000 );
1592
1593 PNS_DBG( Dbg(), AddItem, &head, CYAN, 0, wxT( "head, after shove" ) );
1594
1595 if( head.EndsWithVia() )
1596 {
1597 std::unique_ptr< VIA >headVia = Clone( head.Via() );
1598 headVia->Mark( MK_HEAD );
1599 headVia->SetRank( 100000 );
1600 m_currentNode->Add( std::move( headVia ) );
1601 }
1602
1603 if( !pushLineStack( head ) )
1604 {
1605 delete m_currentNode;
1606 m_currentNode = parent;
1607
1608 return SH_INCOMPLETE;
1609 }
1610
1611 st = shoveMainLoop();
1612
1613 if( st == SH_OK )
1614 {
1616
1617 if( m_newHead )
1619 else
1621 }
1622
1624
1625 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1626 ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1627
1628 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1629 {
1631 }
1632 else
1633 {
1634 delete m_currentNode;
1635
1636 m_currentNode = parent;
1637 m_newHead = OPT_LINE();
1638 }
1639
1640 if( m_newHead )
1641 m_newHead->Unmark();
1642
1643 if( m_newHead && head.EndsWithVia() )
1644 {
1645 VIA v = head.Via();
1646 v.SetPos( m_newHead->CPoint( -1 ) );
1647 m_newHead->AppendVia(v);
1648 }
1649
1650 return st;
1651}
1652
1653
1655{
1656 SHOVE_STATUS st = SH_OK;
1657
1658 m_multiLineMode = true;
1659
1660 ITEM_SET headSet;
1661
1662 for( const ITEM* item : aHeadSet.CItems() )
1663 {
1664 const LINE* headOrig = static_cast<const LINE*>( item );
1665
1666 // empty head? nothing to shove...
1667 if( !headOrig->SegmentCount() )
1668 return SH_INCOMPLETE;
1669
1670 headSet.Add( *headOrig );
1671 }
1672
1673 m_lineStack.clear();
1674 m_optimizerQueue.clear();
1675
1676 VIA_HANDLE dummyVia;
1677
1678 NODE* parent = reduceSpringback( headSet, dummyVia );
1679
1680 m_currentNode = parent->Branch();
1682 int n = 0;
1683
1684 for( const ITEM* item : aHeadSet.CItems() )
1685 {
1686 const LINE* headOrig = static_cast<const LINE*>( item );
1687 LINE head( *headOrig );
1688 head.ClearLinks();
1689
1690 m_currentNode->Add( head );
1691
1692 head.Mark( MK_HEAD );
1693 head.SetRank( 100000 );
1694 n++;
1695
1696 if( !pushLineStack( head ) )
1697 return SH_INCOMPLETE;
1698
1699 if( head.EndsWithVia() )
1700 {
1701 std::unique_ptr< VIA > headVia = Clone( head.Via() );
1702 headVia->Mark( MK_HEAD );
1703 headVia->SetRank( 100000 );
1704 m_currentNode->Add( std::move( headVia ) );
1705 }
1706 }
1707
1708 st = shoveMainLoop();
1709
1710 if( st == SH_OK )
1712
1714
1715 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1716 ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1717
1718 if( st == SH_OK )
1719 {
1721 }
1722 else
1723 {
1724 delete m_currentNode;
1725 m_currentNode = parent;
1726 }
1727
1728 return st;
1729}
1730
1731
1732static VIA* findViaByHandle ( NODE *aNode, const VIA_HANDLE& handle )
1733{
1734 const JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1735
1736 if( !jt )
1737 return nullptr;
1738
1739 for( ITEM* item : jt->LinkList() )
1740 {
1741 if( item->OfKind( ITEM::VIA_T ) )
1742 {
1743 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1744 return static_cast<VIA*>( item );
1745 }
1746 }
1747
1748 return nullptr;
1749}
1750
1751
1753 VIA_HANDLE& aNewVia )
1754{
1755 SHOVE_STATUS st = SH_OK;
1756
1757 m_lineStack.clear();
1758 m_optimizerQueue.clear();
1759 m_newHead = OPT_LINE();
1760 m_draggedVia = nullptr;
1761
1762 VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1763
1764 if( !viaToDrag )
1765 return SH_INCOMPLETE;
1766
1767 // Pop NODEs containing previous shoves which are no longer necessary
1768 ITEM_SET headSet;
1769
1770 VIA headVia ( *viaToDrag );
1771 headVia.SetPos( aWhere );
1772 headSet.Add( &headVia, false ); // headVia is on stack
1773
1774 VIA_HANDLE prevViaHandle;
1775 NODE* parent = reduceSpringback( headSet, prevViaHandle );
1776
1777 if( prevViaHandle.valid )
1778 {
1779 aNewVia = prevViaHandle;
1780 viaToDrag = findViaByHandle( parent, prevViaHandle );
1781 }
1782
1783 // Create a new NODE to store this version of the world
1784 m_currentNode = parent->Branch();
1786
1787 viaToDrag->Mark( MK_HEAD );
1788 viaToDrag->SetRank( 100000 );
1789
1790 // Push the via to its new location
1791 st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1792
1793 // Shove any colliding objects out of the way
1794 if( st == SH_OK )
1795 st = shoveMainLoop();
1796
1797 if( st == SH_OK )
1798 {
1800
1801 // m_draggedVia will only be updated if pushOrShoveVia makes progress...
1802 // this should probably be refactored/cleaned up.
1803 PNS::VIA* viaCheck = m_draggedVia ? m_draggedVia : viaToDrag;
1804
1805 st = m_currentNode->CheckColliding( viaCheck ) ? SH_INCOMPLETE : SH_OK;
1806 }
1807
1808 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1809 {
1810 wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1811
1812 if( !m_draggedVia )
1813 m_draggedVia = viaToDrag;
1814
1815 aNewVia = m_draggedVia->MakeHandle();
1816
1818 }
1819 else
1820 {
1821 delete m_currentNode;
1822 m_currentNode = parent;
1823 }
1824
1825 return st;
1826}
1827
1828
1830{
1831 for( LINKED_ITEM* link : aLine->Links() )
1832 {
1833 if( SEGMENT* seg = dyn_cast<SEGMENT*>( link ) )
1834 {
1835 auto it = m_rootLineHistory.find( seg );
1836
1837 if( it != m_rootLineHistory.end() )
1838 return it->second;
1839 }
1840 }
1841
1842 return nullptr;
1843}
1844
1845
1847{
1848 OPTIMIZER optimizer( aNode );
1849 int optFlags = 0;
1850 int n_passes = 0;
1851
1853
1855
1856 int maxWidth = 0;
1857
1858 for( LINE& line : m_optimizerQueue )
1859 maxWidth = std::max( line.Width(), maxWidth );
1860
1861 if( area )
1862 {
1863 area->Inflate( maxWidth );
1864 area = area->Intersect( VisibleViewArea() );
1865 }
1866
1867 switch( effort )
1868 {
1869 case OE_LOW:
1870 optFlags |= OPTIMIZER::MERGE_OBTUSE;
1871 n_passes = 1;
1872 break;
1873
1874 case OE_MEDIUM:
1875 optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1876 n_passes = 2;
1877 break;
1878
1879 case OE_FULL:
1880 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1881 n_passes = 2;
1882 break;
1883
1884 default:
1885 break;
1886 }
1887
1889
1890 if( area )
1891 {
1892 SHAPE_RECT r( *area );
1893
1894 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "opt-area" ) );
1895
1896 optFlags |= OPTIMIZER::RESTRICT_AREA;
1897 optimizer.SetRestrictArea( *area, false );
1898 }
1899
1901
1902 // Smart Pads is incompatible with 90-degree mode for now
1903 if( Settings().SmartPads()
1904 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 ) )
1905 {
1906 optFlags |= OPTIMIZER::SMART_PADS;
1907 }
1908
1909
1910 optimizer.SetEffortLevel( optFlags & ~m_optFlagDisableMask );
1911 optimizer.SetCollisionMask( ITEM::ANY_T );
1912
1913 for( int pass = 0; pass < n_passes; pass++ )
1914 {
1915 std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1916
1917 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "optimize %d lines, pass %d"), (int)m_optimizerQueue.size(), (int)pass ) );
1918
1919 for( LINE& line : m_optimizerQueue)
1920 {
1921 if( !( line.Marker() & MK_HEAD ) )
1922 {
1923 LINE optimized;
1924 LINE* root = findRootLine( &line );
1925
1926 if( optimizer.Optimize( &line, &optimized, root ) )
1927 {
1928 PNS_DBG( Dbg(), AddShape, &line.CLine(), BLUE, 0, wxT( "shove-pre-opt" ) );
1929
1930 if( root )
1931 PNS_DBG( Dbg(), AddItem, root, RED, 0, wxT( "shove-root-opt" ) );
1932
1933 replaceLine( line, optimized, false, aNode );
1934 line = optimized; // keep links in the lines in the queue up to date
1935
1936 PNS_DBG( Dbg(), AddShape, &line.CLine(), GREEN, 0, wxT( "shove-post-opt" ) );
1937 }
1938 }
1939 }
1940 }
1941}
1942
1943
1945{
1946 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1947}
1948
1949
1951{
1952 assert( m_newHead );
1953
1954 return *m_newHead;
1955}
1956
1957
1959{
1960 m_root = m_root->Branch();
1961 m_root->Remove( aInitial );
1962}
1963
1964
1966{
1967 SPRINGBACK_TAG sp;
1968 sp.m_node = aNode;
1969 sp.m_locked = true;
1970
1971 m_nodeStack.push_back(sp);
1972 return true;
1973}
1974
1975
1977{
1978 bool found = false;
1979
1980 auto iter = m_nodeStack.begin();
1981
1982 while( iter != m_nodeStack.end() )
1983 {
1984 if ( iter->m_node == aNode )
1985 {
1986 found = true;
1987 break;
1988 }
1989
1990 iter++;
1991 }
1992
1993 if( !found )
1994 return false;
1995
1996 auto start = iter;
1997
1998 aNode->KillChildren();
1999 m_nodeStack.erase( start, m_nodeStack.end() );
2000
2001 return true;
2002}
2003
2004
2006{
2007 if( m_nodeStack.empty() )
2008 return false;
2009
2010 while( !m_nodeStack.back().m_locked && m_nodeStack.size() > 1 )
2011 m_nodeStack.pop_back();
2012
2013 return m_nodeStack.back().m_locked;
2014}
2015
2016
2018{
2019 auto iter = m_nodeStack.begin();
2020
2021 while( iter != m_nodeStack.end() )
2022 {
2023 if ( iter->m_node == aNode )
2024 {
2025 iter->m_locked = false;
2026 break;
2027 }
2028
2029 iter++;
2030 }
2031}
2032
2033
2035{
2036 m_optFlagDisableMask = aMask;
2037}
2038
2039
2041{
2043}
2044
2045}
2046
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:108
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:880
CORNER_MODE
Corner modes.
Definition: direction45.h:67
@ ROUNDED_45
H/V/45 with filleted corners.
Definition: direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition: direction45.h:68
virtual wxString GetItemDescription(UNITS_PROVIDER *aUnitsProvider) const
Return a user-visible description string of this item.
Definition: eda_item.cpp:108
int Start() const
Definition: pns_layerset.h:82
Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc....
Definition: pns_algo_base.h:43
const BOX2I & VisibleViewArea() const
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
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
int Width() const override
Definition: pns_arc.h:88
virtual void SetIteration(int iter)
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:97
BOARD_ITEM * Parent() const
Definition: pns_item.h:186
virtual const std::string Format() const
Definition: pns_item.cpp:305
virtual int Rank() const
Definition: pns_item.h:235
virtual NET_HANDLE Net() const
Definition: pns_item.h:194
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
virtual void SetRank(int aRank)
Definition: pns_item.h:234
virtual int Layer() const
Definition: pns_item.h:200
PnsKind
< Supported item types
Definition: pns_item.h:101
@ SEGMENT_T
Definition: pns_item.h:106
const LAYER_RANGE & Layers() const
Definition: pns_item.h:196
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:205
virtual HOLE * Hole() const
Definition: pns_item.h:273
bool Collide(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:273
virtual void Mark(int aMarker) const
Definition: pns_item.h:230
virtual bool HasHole() const
Definition: pns_item.h:272
bool IsLocked() const
Definition: pns_item.h:247
virtual int Marker() const
Definition: pns_item.h:232
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:274
VIA * Via() const
Definition: pns_joint.h:246
const ITEM_SET & CLinks() const
Definition: pns_joint.h:279
bool IsLocked() const
Definition: pns_joint.h:328
bool IsStitchingVia() const
Definition: pns_joint.h:172
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:119
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:144
const SHAPE * Shape() const override
Modifiable accessor to the underlying shape.
Definition: pns_line.h:132
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:125
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:109
void RemoveVia()
Definition: pns_line.cpp:1271
bool HasLoops() const
Definition: pns_line.cpp:1143
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:136
void SetRank(int aRank) override
Definition: pns_line.cpp:1064
bool HasLockedSegments() const
Definition: pns_line.cpp:1253
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:135
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:101
VIA & Via()
Definition: pns_line.h:193
int SegmentCount() const
Definition: pns_line.h:138
bool IsLinkedChecked() const
Assign a shape to the line (a polyline/line chain).
Definition: pns_line.h:119
virtual int Marker() const override
Definition: pns_line.cpp:128
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1051
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).
bool EndsWithVia() const
Definition: pns_line.h:188
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:145
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
int Rank() const override
Definition: pns_line.cpp:1074
Keep the router "world" - i.e.
Definition: pns_node.h:207
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:143
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1541
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
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:844
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
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1212
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:217
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:663
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:283
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1242
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:251
void KillChildren()
Definition: pns_node.cpp:1496
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1531
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:884
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1014
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:95
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
void SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
@ SMART_PADS
Reroute pad exits.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
virtual int GetNetCode(NET_HANDLE aNet) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:218
TIME_LIMIT ShoveTimeLimit() const
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
DIRECTION_45::CORNER_MODE GetCornerMode() const
const SEG & Seg() const
Definition: pns_segment.h:84
int Width() const override
Definition: pns_segment.h:79
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
Definition: pns_line.cpp:555
void SetSpringbackDoNotTouchNode(const NODE *aNode)
Definition: pns_shove.cpp:2040
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1302
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1489
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:91
int m_iter
Definition: pns_shove.h:176
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:93
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:153
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
void popLineStack()
Definition: pns_shove.cpp:1194
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1829
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:548
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:394
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:181
std::optional< LINE > OPT_LINE
Definition: pns_shove.h:92
NODE * m_currentNode
Definition: pns_shove.h:168
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1958
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:195
int m_forceClearance
Definition: pns_shove.h:177
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:846
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:484
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:146
void DisablePostShoveOptimizations(int aMask)
Definition: pns_shove.cpp:2034
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1551
bool RewindSpringbackTo(NODE *aNode)
Definition: pns_shove.cpp:1976
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1170
@ SH_INCOMPLETE
Definition: pns_shove.h:53
@ SH_HEAD_MODIFIED
Definition: pns_shove.h:54
@ SH_TRY_WALK
Definition: pns_shove.h:55
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1535
bool RewindToLastLockedNode()
Definition: pns_shove.cpp:2005
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:60
SHOVE_STATUS ShoveDraggingVia(const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
Definition: pns_shove.cpp:1752
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:139
int m_restrictSpringbackTagId
Definition: pns_shove.h:170
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:771
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1846
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:262
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:806
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:606
void UnlockSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:2017
NODE * m_root
Definition: pns_shove.h:167
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1965
OPT_LINE m_newHead
Definition: pns_shove.h:172
void unwindLineStack(const LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1125
NODE * CurrentNode()
Definition: pns_shove.cpp:1944
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:215
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:122
bool m_multiLineMode
Definition: pns_shove.h:178
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:1044
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:646
int m_optFlagDisableMask
Definition: pns_shove.h:180
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
Definition: pns_shove.cpp:1220
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:49
VIA * m_draggedVia
Definition: pns_shove.h:174
const NODE * m_springbackDoNotTouchNode
Definition: pns_shove.h:169
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:1654
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:165
const LINE NewHead() const
Definition: pns_shove.cpp:1950
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:94
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:971
bool Expired() const
Definition: time_limit.cpp:39
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
const VECTOR2I & Pos() const
Definition: pns_via.h:128
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_via.h:168
int Diameter() const
Definition: pns_via.h:142
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:193
void SetDiameter(int aDiameter)
Definition: pns_via.h:144
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:130
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:143
void SetIterationLimit(const int aIterLimit)
void SetSolidsOnly(bool aSolidsOnly)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:222
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const std::string Format(bool aCplusPlus=true) const override
bool IsArcSegment(size_t aSegment) const
long long int Length() const
Return length of the line chain in Euclidean metric.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:181
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition: vector2d.h:72
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:380
@ LIGHTGREEN
Definition: color4d.h:63
@ WHITE
Definition: color4d.h:48
@ BLUE
Definition: color4d.h:56
@ LIGHTGRAY
Definition: color4d.h:47
@ GREEN
Definition: color4d.h:57
@ CYAN
Definition: color4d.h:58
@ YELLOW
Definition: color4d.h:67
@ LIGHTRED
Definition: color4d.h:65
@ RED
Definition: color4d.h:59
Push and Shove diff pair dimensions (gap) settings dialog.
@ MK_HEAD
Definition: pns_item.h:42
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1732
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:368
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:309
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
VECTOR2I::extended_type ecoord
Definition: pns_shove.cpp:45
std::vector< FAB_LAYER_COLOR > dummy
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:87
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition: pns_node.h:94
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:89
VECTOR2I pos
Definition: pns_via.h:45
NET_HANDLE net
Definition: pns_via.h:47
LAYER_RANGE layers
Definition: pns_via.h:46
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:118
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:638