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