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 if( viaOnEnd && ( !aCurLine.Via().LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
425 {
426 // Shove aObstacleLine to the hull of aCurLine's via.
427
428 rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
429 }
430 else
431 {
432 // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
433 // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
434 // hull it will be at the appropriate clearance.
435
436 int obstacleLineWidth = aObstacleLine.Width();
437 int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
438 int currentLineSegmentCount = aCurLine.SegmentCount();
439 HULL_SET hulls;
440
441 hulls.reserve( currentLineSegmentCount + 1 );
442
443 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: cur net %d obs %d cl %d" ),
444 aCurLine.Net(), aObstacleLine.Net(), clearance ) );
445
446 for( int i = 0; i < currentLineSegmentCount; i++ )
447 {
448 SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
449 int extra = 0;
450
451 // Arcs need additional clearance to ensure the hulls are always bigger than the arc
452 if( aCurLine.CLine().IsArcSegment( i ) )
454
455 if( extra > 0 )
456 {
457 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove add-extra-clearance %d" ),
458 extra ) );
459 }
460
461 SHAPE_LINE_CHAIN hull =
462 seg.Hull( clearance + extra, obstacleLineWidth, aObstacleLine.Layer() );
463
464 hulls.push_back( hull );
465 }
466
467 if( viaOnEnd )
468 {
469 const VIA& via = aCurLine.Via();
470 int viaClearance = getClearance( &via, &aObstacleLine );
471 /*int holeClearance = getHoleClearance( &via, &aObstacleLine );
472
473 if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
474 viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;*/
475
476 hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
477 }
478
479 rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
480 }
481
482 if( obstacleIsHead )
483 aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
484
485 return rv;
486}
487
488
489/*
490 * TODO describe....
491 */
493{
494 int segIndex;
495 LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
496 LINE shovedLine( obstacleLine );
497 SEGMENT tmp( *aObstacleSeg );
498
499 if( obstacleLine.HasLockedSegments() )
500 {
501 PNS_DBG(Dbg(), Message, "try walk (locked segments)");
502 return SH_TRY_WALK;
503 }
504
505 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
506
507 const double extensionWalkThreshold = 1.0;
508
509 double obsLen = obstacleLine.CLine().Length();
510 double shovedLen = shovedLine.CLine().Length();
511 double extensionFactor = 0.0;
512
513 if( obsLen != 0.0f )
514 extensionFactor = shovedLen / obsLen - 1.0;
515
516 if( extensionFactor > extensionWalkThreshold )
517 return SH_TRY_WALK;
518
519 assert( obstacleLine.LayersOverlap( &shovedLine ) );
520
521 if( Dbg() )
522 {
523 PNS_DBG( Dbg(), AddItem, aObstacleSeg, BLUE, 0, wxT( "shove-changed-area" ) );
524 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
525 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxT( "obstacle-line" ) );
526 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
527 }
528
529 if( rv == SH_OK )
530 {
531 if( shovedLine.Marker() & MK_HEAD )
532 {
533 if( m_multiLineMode )
534 return SH_INCOMPLETE;
535
536 m_newHead = shovedLine;
537 }
538
539 int rank = aCurrent.Rank();
540 shovedLine.SetRank( rank - 1 );
541
542 sanityCheck( &obstacleLine, &shovedLine );
543 replaceLine( obstacleLine, shovedLine );
544
545 if( !pushLineStack( shovedLine ) )
546 rv = SH_INCOMPLETE;
547 }
548
549 return rv;
550}
551
552
553/*
554 * TODO describe....
555 */
557{
558 int segIndex;
559 LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
560 LINE shovedLine( obstacleLine );
561 ARC tmp( *aObstacleArc );
562
563 if( obstacleLine.HasLockedSegments() )
564 return SH_TRY_WALK;
565
566 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
567
568 const double extensionWalkThreshold = 1.0;
569
570 double obsLen = obstacleLine.CLine().Length();
571 double shovedLen = shovedLine.CLine().Length();
572 double extensionFactor = 0.0;
573
574 if( obsLen != 0.0f )
575 extensionFactor = shovedLen / obsLen - 1.0;
576
577 if( extensionFactor > extensionWalkThreshold )
578 return SH_TRY_WALK;
579
580 assert( obstacleLine.LayersOverlap( &shovedLine ) );
581
582 PNS_DBG( Dbg(), AddItem, &tmp, WHITE, 10000, wxT( "obstacle-arc" ) );
583 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
584 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxT( "obstacle-line" ) );
585 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
586
587 if( rv == SH_OK )
588 {
589 if( shovedLine.Marker() & MK_HEAD )
590 {
591 if( m_multiLineMode )
592 return SH_INCOMPLETE;
593
594 m_newHead = shovedLine;
595 }
596
597 int rank = aCurrent.Rank();
598 shovedLine.SetRank( rank - 1 );
599
600 sanityCheck( &obstacleLine, &shovedLine );
601 replaceLine( obstacleLine, shovedLine );
602
603 if( !pushLineStack( shovedLine ) )
604 rv = SH_INCOMPLETE;
605 }
606
607 return rv;
608}
609
610
611/*
612 * TODO describe....
613 */
615{
616 LINE shovedLine( aObstacle );
617
618 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
619
620 PNS_DBG( Dbg(), AddItem, &aObstacle, RED, 100000, wxT( "obstacle-line" ) );
621 PNS_DBG( Dbg(), AddItem, &aCurrent, GREEN, 150000, wxT( "current-line" ) );
622 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 200000, wxT( "shoved-line" ) );
623
624 if( rv == SH_OK )
625 {
626 if( shovedLine.Marker() & MK_HEAD )
627 {
628 if( m_multiLineMode )
629 return SH_INCOMPLETE;
630
631 m_newHead = shovedLine;
632 }
633
634 sanityCheck( &aObstacle, &shovedLine );
635 replaceLine( aObstacle, shovedLine );
636
637 int rank = aObstacle.Rank();
638 shovedLine.SetRank( rank - 1 );
639
640
641 if( !pushLineStack( shovedLine ) )
642 {
643 rv = SH_INCOMPLETE;
644 }
645 }
646
647 return rv;
648}
649
650
651/*
652 * TODO describe....
653 */
654SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle, OBSTACLE& aObstacleInfo )
655{
656 WALKAROUND walkaround( m_currentNode, Router() );
657 LINE walkaroundLine( aCurrent );
658
659 if( aCurrent.EndsWithVia() )
660 {
661 VIA vh = aCurrent.Via();
662 VIA* via = nullptr;
663 JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
664
665 if( !jtStart )
666 return SH_INCOMPLETE;
667
668 for( ITEM* item : jtStart->LinkList() )
669 {
670 if( item->OfKind( ITEM::VIA_T ) )
671 {
672 via = (VIA*) item;
673 break;
674 }
675 }
676
677 if( via && via->Collide( aObstacle, m_currentNode ) )
678 return onCollidingVia( aObstacle, via, aObstacleInfo );
679 }
680
681 TOPOLOGY topo( m_currentNode );
682
683 std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
684
685
686
687 PNS_DBG( Dbg(), BeginGroup, "walk-cluster", 1 );
688
689 for( auto item : cluster )
690 {
691 PNS_DBG( Dbg(), AddItem, item, RED, 10000, wxT( "cl-item" ) );
692 }
693
694 PNS_DBGN( Dbg(), EndGroup );
695
696
697 walkaround.SetDebugDecorator( Dbg() );
698 walkaround.SetSolidsOnly( false );
699 walkaround.RestrictToSet( true, cluster );
700 walkaround.SetIterationLimit( 16 ); // fixme: make configurable
701
702 int currentRank = aCurrent.Rank();
703 int nextRank;
704
705 bool success = false;
706
707 for( int attempt = 0; attempt < 2; attempt++ )
708 {
709 if( attempt == 1 || Settings().JumpOverObstacles() )
710 {
711
712 nextRank = currentRank - 1;
713 }
714 else
715 {
716 nextRank = currentRank + 10000;
717 }
718
719
720 WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
721
722 if( status != WALKAROUND::DONE )
723 continue;
724
725 walkaroundLine.ClearLinks();
726 walkaroundLine.Unmark();
727 walkaroundLine.Line().Simplify();
728
729 if( walkaroundLine.HasLoops() )
730 continue;
731
732 if( aCurrent.Marker() & MK_HEAD )
733 {
734 walkaroundLine.Mark( MK_HEAD );
735
736 if( m_multiLineMode )
737 continue;
738
739 m_newHead = walkaroundLine;
740 }
741
742 sanityCheck( &aCurrent, &walkaroundLine );
743
744 if( !m_lineStack.empty() )
745 {
746 LINE lastLine = m_lineStack.front();
747
748 if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
749 {
750 LINE dummy( lastLine );
751
752 if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
753 {
754 success = true;
755 break;
756 }
757 }
758 else
759 {
760 success = true;
761 break;
762 }
763 }
764 }
765
766 if(!success)
767 return SH_INCOMPLETE;
768
769 replaceLine( aCurrent, walkaroundLine );
770 walkaroundLine.SetRank( nextRank );
771
772 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
773 PNS_DBG( Dbg(), AddItem, &walkaroundLine, BLUE, 10000, wxT( "walk-line" ) );
774
775 popLineStack();
776
777 if( !pushLineStack( walkaroundLine ) )
778 return SH_INCOMPLETE;
779
780 return SH_OK;
781}
782
783
784/*
785 * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
786 * to the dragged via of the last unpopped state.
787 */
788NODE* SHOVE::reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia )
789{
790 while( !m_nodeStack.empty() )
791 {
792 SPRINGBACK_TAG& spTag = m_nodeStack.back();
793
794 // Prevent the springback algo from erasing NODEs that might contain items used by the ROUTER_TOOL/LINE_PLACER.
795 // I noticed this can happen for the endItem provided to LINE_PLACER::Move() and cause a nasty crash.
797 break;
798
799 std::optional<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
800
801 if( !obs && !spTag.m_locked )
802 {
803 aDraggedVia = spTag.m_draggedVia;
804 aDraggedVia.valid = true;
805
806 delete spTag.m_node;
807 m_nodeStack.pop_back();
808 }
809 else
810 {
811 break;
812 }
813 }
814
815 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
816}
817
818
819/*
820 * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
821 * (which will be restored in the event the stackframe is popped).
822 */
823bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia )
824{
826 OPT_BOX2I prev_area;
827
828 if( !m_nodeStack.empty() )
829 prev_area = m_nodeStack.back().m_affectedArea;
830
831 if( aDraggedVia )
832 {
833 st.m_draggedVia = aDraggedVia->MakeHandle();
834 }
835
836 st.m_node = aNode;
837
838 if( aAffectedArea )
839 {
840 if( prev_area )
841 st.m_affectedArea = prev_area->Merge( *aAffectedArea );
842 else
843 st.m_affectedArea = aAffectedArea;
844 }
845 else
846 {
847 st.m_affectedArea = prev_area;
848 }
849
850 st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
851 st.m_locked = false;
852
853 m_nodeStack.push_back( st );
854
855 return true;
856}
857
858
859/*
860 * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
861 * to keep it from landing on an existing joint.)
862 */
863SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank )
864{
865 LINE_PAIR_VEC draggedLines;
866 VECTOR2I p0( aVia->Pos() );
867 JOINT* jt = m_currentNode->FindJoint( p0, aVia );
868 VECTOR2I p0_pushed( p0 + aForce );
869
870 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "via force [%d %d]\n" ), aForce.x, aForce.y ) );
871
872 // nothing to do...
873 if ( aForce.x == 0 && aForce.y == 0 )
874 return SH_OK;
875
876 if( !jt )
877 {
878 PNS_DBG( Dbg(), Message,
879 wxString::Format( wxT( "weird, can't find the center-of-via joint\n" ) ) );
880 return SH_INCOMPLETE;
881 }
882
883 if( Settings().ShoveVias() == false || aVia->IsLocked() )
884 return SH_TRY_WALK;
885
886 if( jt->IsLocked() )
887 return SH_INCOMPLETE;
888
889 // make sure pushed via does not overlap with any existing joint
890 while( true )
891 {
892 JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
893
894 if( !jt_next )
895 break;
896
897 p0_pushed += aForce.Resize( 2 );
898 }
899
900 std::unique_ptr<VIA> pushedVia = Clone( *aVia );
901 pushedVia->SetPos( p0_pushed );
902 pushedVia->Mark( aVia->Marker() );
903
904 for( ITEM* item : jt->LinkList() )
905 {
906 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
907 {
908 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
909 LINE_PAIR lp;
910 int segIndex;
911
912 lp.first = assembleLine( li, &segIndex );
913
914 if( lp.first.HasLockedSegments() )
915 return SH_TRY_WALK;
916
917 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
918
919 if( segIndex == 0 )
920 lp.first.Reverse();
921
922 lp.second = lp.first;
923 lp.second.ClearLinks();
924 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
925 lp.second.AppendVia( *pushedVia );
926 draggedLines.push_back( lp );
927 }
928 }
929
930 pushedVia->SetRank( aCurrentRank - 1 );
931 PNS_DBG( Dbg(), Message, wxString::Format("PushViaRank %d\n", pushedVia->Rank() ) );
932
933 if( aVia->Marker() & MK_HEAD ) // push
934 {
935 m_draggedVia = pushedVia.get();
936 }
937 else
938 { // shove
939 if( jt->IsStitchingVia() )
940 pushLineStack( LINE( *pushedVia ) );
941 }
942
943 PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
944 PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
945
946 replaceItems( aVia, std::move( pushedVia ) );
947
948 for( LINE_PAIR lp : draggedLines )
949 {
950 if( lp.first.Marker() & MK_HEAD )
951 {
952 lp.second.Mark( MK_HEAD );
953
954 if( m_multiLineMode )
955 return SH_INCOMPLETE;
956
957 m_newHead = lp.second;
958 }
959
960 unwindLineStack( &lp.first );
961
962 if( lp.second.SegmentCount() )
963 {
964 replaceLine( lp.first, lp.second );
965 lp.second.SetRank( aCurrentRank - 1 );
966
967
968 PNS_DBG( Dbg(), Message, wxString::Format("PushViaF %p %d\n", &lp.second, lp.second.SegmentCount() ) );
969
970 if( !pushLineStack( lp.second, true ) )
971 return SH_INCOMPLETE;
972 }
973 else
974 {
975 m_currentNode->Remove( lp.first );
976 }
977
978 PNS_DBG( Dbg(), AddItem, &lp.first, LIGHTGREEN, 10000, wxT( "fan-pre" ) );
979 PNS_DBG( Dbg(), AddItem, &lp.second, LIGHTRED, 10000, wxT( "fan-post" ) );
980 }
981
982 return SH_OK;
983}
984
985
986/*
987 * Calculate the minimum translation vector required to resolve a collision with a via and
988 * shove the via by that distance.
989 */
990SHOVE::SHOVE_STATUS SHOVE::onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia, OBSTACLE& aObstacleInfo )
991{
992 assert( aObstacleVia );
993
994 int clearance = getClearance( aCurrent, aObstacleVia );
995 VECTOR2I mtv;
996 int rank = -1;
997
998 bool lineCollision = false;
999 bool viaCollision = false;
1000 VECTOR2I mtvLine, mtvVia;
1001
1002 PNS_DBG( Dbg(), BeginGroup, "push-via-by-line", 1 );
1003
1004 if( aCurrent->OfKind( ITEM::LINE_T ) )
1005 {
1006 VIA vtmp ( *aObstacleVia );
1007
1008 if( aObstacleInfo.m_maxFanoutWidth > 0 && aObstacleInfo.m_maxFanoutWidth > aObstacleVia->Diameter() )
1009 {
1010 vtmp.SetDiameter( aObstacleInfo.m_maxFanoutWidth );
1011 }
1012
1013 LINE* currentLine = (LINE*) aCurrent;
1014
1015 PNS_DBG( Dbg(), AddItem, currentLine, LIGHTRED, 10000, wxT( "current-line" ) );
1016
1017 if( currentLine->EndsWithVia() )
1018 {
1019 PNS_DBG( Dbg(), AddItem, &currentLine->Via(), LIGHTRED, 10000, wxT( "current-line-via" ) );
1020 }
1021
1022 PNS_DBG( Dbg(), AddItem, &vtmp, LIGHTRED, 100000, wxT( "orig-via" ) );
1023
1024 lineCollision = vtmp.Shape()->Collide( currentLine->Shape(),
1025 clearance + currentLine->Width() / 2,
1026 &mtvLine );
1027
1028 // Check the via if present. Via takes priority.
1029 if( currentLine->EndsWithVia() )
1030 {
1031 const VIA& currentVia = currentLine->Via();
1032 int viaClearance = getClearance( &currentVia, &vtmp );
1033
1034 viaCollision = currentVia.Shape()->Collide( vtmp.Shape(), viaClearance, &mtvVia );
1035 }
1036 }
1037 else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1038 {
1039 // TODO: is this possible at all? We don't shove solids.
1040 return SH_INCOMPLETE;
1041 }
1042
1043 // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1044 if( viaCollision )
1045 mtv = -mtvVia;
1046 else if ( lineCollision )
1047 mtv = -mtvLine;
1048 else
1049 mtv = VECTOR2I(0, 0);
1050
1051 SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, aCurrent->Rank() );
1052 PNS_DBG(Dbg(), Message, wxString::Format("push-or-shove-via st %d", st ) );
1053
1054 PNS_DBGN( Dbg(), EndGroup );
1055
1056 return st;
1057}
1058
1059
1060/*
1061 * TODO describe....
1062 */
1064{
1065 int n = 0;
1066 LINE cur( aCurrent );
1067 cur.ClearLinks();
1068
1069 JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1070 LINE shoved( aCurrent );
1071 shoved.ClearLinks();
1072
1073 cur.RemoveVia();
1074 unwindLineStack( &aCurrent );
1075
1076 for( ITEM* item : jt->LinkList() )
1077 {
1078 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1079 {
1080 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1081 LINE head = assembleLine( li );
1082
1083 head.AppendVia( *aObstacleVia );
1084
1085 SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1086
1087 if( st != SH_OK )
1088 {
1089#if 0
1090 m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1091 m_logger.Log( aObstacleVia, 0, "the-via" );
1092 m_logger.Log( &aCurrent, 1, "current-line" );
1093 m_logger.Log( &shoved, 3, "shoved-line" );
1094#endif
1095
1096 return st;
1097 }
1098
1099 cur.SetShape( shoved.CLine() );
1100 n++;
1101 }
1102 }
1103
1104 if( !n )
1105 {
1106#if 0
1107 m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1108 m_logger.Log( aObstacleVia, 0, "the-via" );
1109 m_logger.Log( &aCurrent, 1, "current-line" );
1110#endif
1111
1112 LINE head( aCurrent );
1113 head.Line().Clear();
1114 head.AppendVia( *aObstacleVia );
1115 head.ClearLinks();
1116
1117 SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1118
1119 if( st != SH_OK )
1120 return st;
1121
1122 cur.SetShape( shoved.CLine() );
1123 }
1124
1125 if( aCurrent.EndsWithVia() )
1126 shoved.AppendVia( aCurrent.Via() );
1127
1128#if 0
1129 m_logger.NewGroup( "on-reverse-via", m_iter );
1130 m_logger.Log( aObstacleVia, 0, "the-via" );
1131 m_logger.Log( &aCurrent, 1, "current-line" );
1132 m_logger.Log( &shoved, 3, "shoved-line" );
1133#endif
1134
1135 PNS_DBG( Dbg(), AddItem, aObstacleVia, YELLOW, 0, wxT( "rr-the-via" ) );
1136 PNS_DBG( Dbg(), AddItem, &aCurrent, BLUE, 0, wxT( "rr-current-line" ) );
1137 PNS_DBG( Dbg(), AddItem, &shoved, GREEN, 0, wxT( "rr-shoved-line" ) );
1138
1139 int currentRank = aCurrent.Rank();
1140 replaceLine( aCurrent, shoved );
1141
1142 if( !pushLineStack( shoved ) )
1143 return SH_INCOMPLETE;
1144
1145 shoved.SetRank( currentRank );
1146
1147 return SH_OK;
1148}
1149
1150
1152{
1153 int d = 0;
1154
1155 for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1156 {
1157 if( i->ContainsLink( aSeg ) )
1158 {
1159 PNS_DBG(Dbg(), Message, wxString::Format("Unwind lc %d (depth %d/%d)", i->SegmentCount(), d, (int)m_lineStack.size() ) );
1160 i = m_lineStack.erase( i );
1161 }
1162 else
1163 i++;
1164
1165 d++;
1166 }
1167
1168 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1169 {
1170 if( i->ContainsLink( aSeg ) )
1171 i = m_optimizerQueue.erase( i );
1172 else
1173 i++;
1174 }
1175}
1176
1177
1179{
1180 if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1181 unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1182 else if( aItem->OfKind( ITEM::LINE_T ) )
1183 {
1184 LINE* l = static_cast<LINE*>( aItem );
1185
1186 for( LINKED_ITEM* seg : l->Links() )
1187 unwindLineStack( seg );
1188 }
1189}
1190
1191
1192bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1193{
1194 if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1195 {
1196 PNS_DBG( Dbg(), AddItem, &aL, BLUE, 10000, wxT( "push line stack failed" ) );
1197
1198 return false;
1199 }
1200
1201 if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1202 {
1203 m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1204 }
1205 else
1206 {
1207 m_lineStack.push_back( aL );
1208 }
1209
1210 m_optimizerQueue.push_back( aL );
1211
1212 return true;
1213}
1214
1215
1217{
1218 LINE& l = m_lineStack.back();
1219
1220 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1221 {
1222 bool found = false;
1223
1224 for( LINKED_ITEM* s : l.Links() )
1225 {
1226 if( i->ContainsLink( s ) )
1227 {
1228 i = m_optimizerQueue.erase( i );
1229 found = true;
1230 break;
1231 }
1232 }
1233
1234 if( !found )
1235 i++;
1236 }
1237
1238 m_lineStack.pop_back();
1239}
1240
1241
1242bool SHOVE::fixupViaCollisions( const LINE* aCurrent, OBSTACLE& obs )
1243{
1244 // if the current obstacle is a via, consider also the lines connected to it
1245 // if their widths are larger or equal than the via diameter, the shove algorithm
1246 // will very likely fail in the subsequent iterations (as our base assumption is track
1247 // ends can never move on their own, only dragged by force-propagated vias
1248
1249 // our colliding item is a via: just find the max width of the traces connected to it
1250 if( obs.m_item->OfKind( ITEM::VIA_T ) )
1251 {
1252 VIA* v = static_cast<VIA*>( obs.m_item );
1253 int maxw = 0;
1254 JOINT* jv = m_currentNode->FindJoint( v->Pos(), v );
1255
1256 for( auto link : jv->Links() )
1257 {
1258 if( link.item->OfKind( ITEM::SEGMENT_T ) ) // consider segments ...
1259 {
1260 auto seg = static_cast<SEGMENT*>( link.item );
1261 maxw = std::max( seg->Width(), maxw );
1262 }
1263 else if( link.item->OfKind( ITEM::ARC_T ) ) // ... or arcs
1264 {
1265 auto arc = static_cast<ARC*>( link.item );
1266 maxw = std::max( arc->Width(), maxw );
1267 }
1268 }
1269
1270 obs.m_maxFanoutWidth = 0;
1271
1272 if( maxw > 0 && maxw >= v->Diameter() )
1273 {
1274 obs.m_maxFanoutWidth = maxw + 1;
1275 PNS_DBG( Dbg(), Message,
1276 wxString::Format( "Fixup via: new-w %d via-w %d", maxw, v->Diameter() ) );
1277
1278 return true;
1279 }
1280 return false;
1281 }
1282
1283
1284 // our colliding item is a segment. check if it has a via on either of the ends.
1285 if( !obs.m_item->OfKind( ITEM::SEGMENT_T ) )
1286 return false;
1287
1288 auto s = static_cast<SEGMENT*>( obs.m_item );
1289
1290 JOINT* ja = m_currentNode->FindJoint( s->Seg().A, s );
1291 JOINT* jb = m_currentNode->FindJoint( s->Seg().B, s );
1292
1293 VIA* vias[] = { ja->Via(), jb->Via() };
1294
1295 for( int i = 0; i < 2; i++ )
1296 {
1297 VIA* v = vias[i];
1298
1299 // via diameter is larger than the segment width - cool, the force propagation algo
1300 // will be able to deal with it, no need to intervene
1301 if( !v || v->Diameter() > s->Width() )
1302 continue;
1303
1304 VIA vtest( *v );
1305 vtest.SetDiameter( s->Width() );
1306
1307 // enlarge the via to the width of the segment
1308 if( vtest.Collide( aCurrent, m_currentNode ) )
1309 {
1310 // if colliding, drop the segment in the shove iteration loop and force-propagate the via instead
1311 obs.m_item = v;
1312 obs.m_maxFanoutWidth = s->Width() + 1;
1313 return true;
1314 }
1315 }
1316 return false;
1317}
1318
1319/*
1320 * Resolve the next collision.
1321 */
1323{
1324 LINE currentLine = m_lineStack.back();
1325 NODE::OPT_OBSTACLE nearest;
1326 SHOVE_STATUS st = SH_NULL;
1327
1328 if( Dbg() )
1329 {
1330 Dbg()->SetIteration( aIter );
1331 }
1332
1333 PNS_DBG( Dbg(), AddItem, &currentLine, RED, currentLine.Width(), wxString::Format( "current-coll-chk rank %d", currentLine.Rank() ) );
1334
1335 for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1336 {
1337 nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1338
1339 if( nearest )
1340 {
1341 PNS_DBG( Dbg(), Message,
1342 wxString::Format( wxT( "nearest %p %s rank %d" ), nearest->m_item,
1343 nearest->m_item->KindStr(), nearest->m_item->Rank() ) );
1344
1345 PNS_DBG( Dbg(), AddShape, nearest->m_item->Shape(), YELLOW, 10000, wxT("nearest") );
1346 }
1347
1348 if( nearest )
1349 break;
1350 }
1351
1352 if( !nearest )
1353 {
1354 m_lineStack.pop_back();
1355 PNS_DBG( Dbg(), Message, "no-nearest-item ");
1356 return SH_OK;
1357 }
1358
1359 bool viaFixup = fixupViaCollisions( &currentLine, *nearest );
1360
1361 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: VF %d", aIter, viaFixup?1:0 ) );
1362
1363
1364 ITEM* ni = nearest->m_item;
1365
1366 unwindLineStack( ni );
1367
1368 if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1369 {
1370 // Collision with a higher-ranking object (ie: one that we've already shoved)
1371 //
1372 switch( ni->Kind() )
1373 {
1374 case ITEM::VIA_T:
1375 {
1376 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-via", aIter ).ToStdString(), 0 );
1377
1378 if( currentLine.EndsWithVia() )
1379 {
1380 st = SH_INCOMPLETE;
1381 }
1382 else
1383 {
1384 st = onReverseCollidingVia( currentLine, (VIA*) ni );
1385 }
1386
1387 PNS_DBGN( Dbg(), EndGroup );
1388
1389 break;
1390 }
1391
1392 case ITEM::SEGMENT_T:
1393 {
1394 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-segment ",
1395 aIter ).ToStdString(), 0 );
1396 LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1397
1398 popLineStack();
1399 st = onCollidingLine( revLine, currentLine );
1400
1401
1402 if( !pushLineStack( revLine ) )
1403 {
1404 return SH_INCOMPLETE;
1405 }
1406
1407
1408 PNS_DBGN( Dbg(), EndGroup );
1409
1410 break;
1411 }
1412
1413 case ITEM::ARC_T:
1414 {
1415 //TODO(snh): Handle Arc shove separate from track
1416 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-arc ", aIter ).ToStdString(), 0 );
1417 LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1418
1419 popLineStack();
1420 st = onCollidingLine( revLine, currentLine );
1421
1422 PNS_DBGN( Dbg(), EndGroup );
1423
1424 if( !pushLineStack( revLine ) )
1425 return SH_INCOMPLETE;
1426
1427 break;
1428 }
1429
1430 default:
1431 assert( false );
1432 }
1433 }
1434 else
1435 {
1436 // Collision with a lower-ranking object or a solid
1437 //
1438 switch( ni->Kind() )
1439 {
1440 case ITEM::SEGMENT_T:
1441 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-segment ", aIter ), 0 );
1442
1443 st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1444
1445 if( st == SH_TRY_WALK )
1446 st = onCollidingSolid( currentLine, ni, *nearest );
1447
1448 PNS_DBGN( Dbg(), EndGroup );
1449
1450 break;
1451
1452 //TODO(snh): Customize Arc collide
1453 case ITEM::ARC_T:
1454 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-arc ", aIter ), 0 );
1455
1456 st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
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::VIA_T:
1466 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-via (fixup: %d)", aIter, 0 ), 0 );
1467 st = onCollidingVia( &currentLine, (VIA*) ni, *nearest );
1468
1469 if( st == SH_TRY_WALK )
1470 st = onCollidingSolid( currentLine, ni, *nearest );
1471
1472 PNS_DBGN( Dbg(), EndGroup );
1473
1474 break;
1475
1476 case ITEM::SOLID_T:
1477 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: walk-solid ", aIter ), 0);
1478 st = onCollidingSolid( currentLine, (SOLID*) ni, *nearest );
1479
1480 PNS_DBGN( Dbg(), EndGroup );
1481
1482 break;
1483
1484 default:
1485 break;
1486 }
1487 }
1488
1489 return st;
1490}
1491
1492
1493/*
1494 * Resolve collisions.
1495 * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1496 * long as they propagate further collisions, or until the iteration timeout or max iteration
1497 * count is reached.
1498 */
1500{
1501 SHOVE_STATUS st = SH_OK;
1502
1504
1505 PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1506 m_root->JointCount(),
1508
1509 int iterLimit = Settings().ShoveIterationLimit();
1510 TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1511
1512 m_iter = 0;
1513
1514 timeLimit.Restart();
1515
1516 if( m_lineStack.empty() && m_draggedVia )
1517 {
1518 // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1519 // the stack.
1521 }
1522
1523 while( !m_lineStack.empty() )
1524 {
1525 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1526 m_currentNode, (int) m_lineStack.size() ) );
1527
1528 st = shoveIteration( m_iter );
1529
1530 m_iter++;
1531
1532 if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1533 {
1534 PNS_DBG( Dbg(), Message, wxString::Format( "Fail [time limit expired: %d iter %d iter limit %d",
1535 timeLimit.Expired()?1:0, m_iter, iterLimit ) );
1536 st = SH_INCOMPLETE;
1537 break;
1538 }
1539 }
1540
1541 return st;
1542}
1543
1544
1546{
1547 OPT_BOX2I area;
1548
1549 if( !m_nodeStack.empty() )
1550 area = m_nodeStack.back().m_affectedArea;
1551
1552 if( area && m_affectedArea)
1553 area->Merge( *m_affectedArea );
1554 else if( !area )
1555 area = m_affectedArea;
1556
1557 return area;
1558}
1559
1560
1562{
1563 SHOVE_STATUS st = SH_OK;
1564
1565 m_multiLineMode = false;
1566
1567 PNS_DBG( Dbg(), Message,
1568 wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) )
1569
1570 // empty head? nothing to shove...
1571 if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1572 return SH_INCOMPLETE;
1573
1574 LINE head( aCurrentHead );
1575 head.ClearLinks();
1576
1577 m_lineStack.clear();
1578 m_optimizerQueue.clear();
1579 m_newHead = OPT_LINE();
1580
1581#if 0
1582 m_logger.Clear();
1583#endif
1584
1585 // Pop NODEs containing previous shoves which are no longer necessary
1586 //
1587 ITEM_SET headSet;
1588 headSet.Add( aCurrentHead );
1589
1590 VIA_HANDLE dummyVia;
1591
1592 NODE* parent = reduceSpringback( headSet, dummyVia );
1593
1594 // Create a new NODE to store this version of the world
1595 m_currentNode = parent->Branch();
1597 m_currentNode->Add( head );
1598
1599 m_currentNode->LockJoint( head.CPoint(0), &head, true );
1600
1601 if( !head.EndsWithVia() )
1602 m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1603
1604 head.Mark( MK_HEAD );
1605 head.SetRank( 100000 );
1606
1607 PNS_DBG( Dbg(), AddItem, &head, CYAN, 0, wxT( "head, after shove" ) );
1608
1609 if( head.EndsWithVia() )
1610 {
1611 std::unique_ptr< VIA >headVia = Clone( head.Via() );
1612 headVia->Mark( MK_HEAD );
1613 headVia->SetRank( 100000 );
1614 m_currentNode->Add( std::move( headVia ) );
1615 }
1616
1617 if( !pushLineStack( head ) )
1618 {
1619 delete m_currentNode;
1620 m_currentNode = parent;
1621
1622 return SH_INCOMPLETE;
1623 }
1624
1625 st = shoveMainLoop();
1626
1627 if( st == SH_OK )
1628 {
1630
1631 if( m_newHead )
1633 else
1635 }
1636
1638
1639 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1640 ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1641
1642 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1643 {
1645 }
1646 else
1647 {
1648 delete m_currentNode;
1649
1650 m_currentNode = parent;
1651 m_newHead = OPT_LINE();
1652 }
1653
1654 if(m_newHead)
1655 m_newHead->Unmark();
1656
1657 if( m_newHead && head.EndsWithVia() )
1658 {
1659 VIA v = head.Via();
1660 v.SetPos( m_newHead->CPoint( -1 ) );
1661 m_newHead->AppendVia(v);
1662 }
1663
1664 return st;
1665}
1666
1667
1669{
1670 SHOVE_STATUS st = SH_OK;
1671
1672 m_multiLineMode = true;
1673
1674 ITEM_SET headSet;
1675
1676 for( const ITEM* item : aHeadSet.CItems() )
1677 {
1678 const LINE* headOrig = static_cast<const LINE*>( item );
1679
1680 // empty head? nothing to shove...
1681 if( !headOrig->SegmentCount() )
1682 return SH_INCOMPLETE;
1683
1684 headSet.Add( *headOrig );
1685 }
1686
1687 m_lineStack.clear();
1688 m_optimizerQueue.clear();
1689
1690#if 0
1691 m_logger.Clear();
1692#endif
1693
1694 VIA_HANDLE dummyVia;
1695
1696 NODE* parent = reduceSpringback( headSet, dummyVia );
1697
1698 m_currentNode = parent->Branch();
1700 int n = 0;
1701
1702 for( const ITEM* item : aHeadSet.CItems() )
1703 {
1704 const LINE* headOrig = static_cast<const LINE*>( item );
1705 LINE head( *headOrig );
1706 head.ClearLinks();
1707
1708 m_currentNode->Add( head );
1709
1710 head.Mark( MK_HEAD );
1711 head.SetRank( 100000 );
1712 n++;
1713
1714 if( !pushLineStack( head ) )
1715 return SH_INCOMPLETE;
1716
1717 if( head.EndsWithVia() )
1718 {
1719 std::unique_ptr< VIA > headVia = Clone( head.Via() );
1720 headVia->Mark( MK_HEAD );
1721 headVia->SetRank( 100000 );
1722 m_currentNode->Add( std::move( headVia ) );
1723 }
1724 }
1725
1726 st = shoveMainLoop();
1727
1728 if( st == SH_OK )
1730
1732
1733 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1734 ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1735
1736 if( st == SH_OK )
1737 {
1739 }
1740 else
1741 {
1742 delete m_currentNode;
1743 m_currentNode = parent;
1744 }
1745
1746 return st;
1747}
1748
1749
1750static VIA* findViaByHandle ( NODE *aNode, const VIA_HANDLE& handle )
1751{
1752 JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1753
1754 if( !jt )
1755 return nullptr;
1756
1757 for( ITEM* item : jt->LinkList() )
1758 {
1759 if( item->OfKind( ITEM::VIA_T ) )
1760 {
1761 if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1762 return static_cast<VIA*>( item );
1763 }
1764 }
1765
1766 return nullptr;
1767}
1768
1769
1771 VIA_HANDLE& aNewVia )
1772{
1773 SHOVE_STATUS st = SH_OK;
1774
1775 m_lineStack.clear();
1776 m_optimizerQueue.clear();
1777 m_newHead = OPT_LINE();
1778 m_draggedVia = nullptr;
1779
1780 VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1781
1782 if( !viaToDrag )
1783 return SH_INCOMPLETE;
1784
1785 // Pop NODEs containing previous shoves which are no longer necessary
1786 ITEM_SET headSet;
1787
1788 VIA headVia ( *viaToDrag );
1789 headVia.SetPos( aWhere );
1790 headSet.Add( headVia );
1791 VIA_HANDLE prevViaHandle;
1792 NODE* parent = reduceSpringback( headSet, prevViaHandle );
1793
1794 if( prevViaHandle.valid )
1795 {
1796 aNewVia = prevViaHandle;
1797 viaToDrag = findViaByHandle( parent, prevViaHandle );
1798 }
1799
1800 // Create a new NODE to store this version of the world
1801 m_currentNode = parent->Branch();
1803
1804 viaToDrag->Mark( MK_HEAD );
1805 viaToDrag->SetRank( 100000 );
1806
1807 // Push the via to its new location
1808 st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1809
1810 // Shove any colliding objects out of the way
1811 if( st == SH_OK )
1812 st = shoveMainLoop();
1813
1814 if( st == SH_OK )
1816
1817 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1818 {
1819 wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1820
1821 if (!m_draggedVia)
1822 m_draggedVia = viaToDrag;
1823
1824 aNewVia = m_draggedVia->MakeHandle();
1825
1827 }
1828 else
1829 {
1830 delete m_currentNode;
1831 m_currentNode = parent;
1832 }
1833
1834 return st;
1835}
1836
1837
1839{
1840 for( auto link : aLine->Links() )
1841 {
1842 if( auto seg = dyn_cast<SEGMENT*>( link ) )
1843 {
1844 auto it = m_rootLineHistory.find( seg );
1845
1846 if( it != m_rootLineHistory.end() )
1847 return it->second;
1848 }
1849 }
1850
1851 return nullptr;
1852}
1853
1854
1856{
1857 OPTIMIZER optimizer( aNode );
1858 int optFlags = 0;
1859 int n_passes = 0;
1860
1862
1864
1865 int maxWidth = 0;
1866
1867 for( LINE& line : m_optimizerQueue )
1868 maxWidth = std::max( line.Width(), maxWidth );
1869
1870 if( area )
1871 {
1872 area->Inflate( maxWidth );
1873 area = area->Intersect( VisibleViewArea() );
1874 }
1875
1876 switch( effort )
1877 {
1878 case OE_LOW:
1879 optFlags |= OPTIMIZER::MERGE_OBTUSE;
1880 n_passes = 1;
1881 break;
1882
1883 case OE_MEDIUM:
1884 optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1885
1886 n_passes = 2;
1887 break;
1888
1889 case OE_FULL:
1890 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1891 n_passes = 2;
1892 break;
1893
1894 default:
1895 break;
1896 }
1897
1899
1900 if( area )
1901 {
1902 SHAPE_RECT r( *area );
1903
1904 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "opt-area" ) );
1905
1906 optFlags |= OPTIMIZER::RESTRICT_AREA;
1907 optimizer.SetRestrictArea( *area, false );
1908 }
1909
1910 if( Settings().SmartPads() )
1911 optFlags |= OPTIMIZER::SMART_PADS;
1912
1913
1914 optimizer.SetEffortLevel( optFlags & ~m_optFlagDisableMask );
1915 optimizer.SetCollisionMask( ITEM::ANY_T );
1916
1917 for( int pass = 0; pass < n_passes; pass++ )
1918 {
1919 std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1920
1921 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "optimize %d lines, pass %d"), (int)m_optimizerQueue.size(), (int)pass ) );
1922
1923 for( LINE& line : m_optimizerQueue)
1924 {
1925 if( !( line.Marker() & MK_HEAD ) )
1926 {
1927 LINE optimized;
1928 LINE* root = findRootLine( &line );
1929
1930 if( optimizer.Optimize( &line, &optimized, root ) )
1931 {
1932 PNS_DBG( Dbg(), AddShape, &line.CLine(), BLUE, 0, wxT( "shove-pre-opt" ) );
1933 if( root )
1934 {
1935 PNS_DBG( Dbg(), AddItem, root, RED, 0, wxT( "shove-root-opt" ) );
1936 }
1937 replaceLine( line, optimized, false, aNode );
1938 line = optimized; // keep links in the lines in the queue up to date
1939
1940 PNS_DBG( Dbg(), AddShape, &line.CLine(), GREEN, 0, wxT( "shove-post-opt" ) );
1941 }
1942 }
1943 }
1944 }
1945}
1946
1947
1949{
1950 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1951}
1952
1953
1955{
1956 assert( m_newHead );
1957
1958 return *m_newHead;
1959}
1960
1961
1963{
1964 m_root = m_root->Branch();
1965 m_root->Remove( aInitial );
1966}
1967
1968
1970{
1971 SPRINGBACK_TAG sp;
1972 sp.m_node = aNode;
1973 sp.m_locked = true;
1974
1975 m_nodeStack.push_back(sp);
1976 return true;
1977}
1978
1979
1981{
1982 bool found = false;
1983
1984 auto iter = m_nodeStack.begin();
1985
1986 while( iter != m_nodeStack.end() )
1987 {
1988 if ( iter->m_node == aNode )
1989 {
1990 found = true;
1991 break;
1992 }
1993
1994 iter++;
1995 }
1996
1997 if( !found )
1998 return false;
1999
2000 auto start = iter;
2001
2002 aNode->KillChildren();
2003 m_nodeStack.erase( start, m_nodeStack.end() );
2004
2005 return true;
2006}
2007
2008
2010{
2011 if( m_nodeStack.empty() )
2012 return false;
2013
2014 while( !m_nodeStack.back().m_locked && m_nodeStack.size() > 1 )
2015 m_nodeStack.pop_back();
2016
2017 return m_nodeStack.back().m_locked;
2018}
2019
2020
2022{
2023 auto iter = m_nodeStack.begin();
2024
2025 while( iter != m_nodeStack.end() )
2026 {
2027 if ( iter->m_node == aNode )
2028 {
2029 iter->m_locked = false;
2030 break;
2031 }
2032
2033 iter++;
2034 }
2035}
2036
2037
2039{
2040 m_optFlagDisableMask = aMask;
2041}
2042
2043
2045{
2047}
2048
2049}
2050
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:1504
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:846
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:472
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:166
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1494
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:664
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1219
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:301
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:115
void KillChildren()
Definition: pns_node.cpp:1459
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:1189
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:881
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:991
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:211
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:1322
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1499
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:1216
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1838
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:168
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:556
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:1962
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:863
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:492
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:157
void DisablePostShoveOptimizations(int aMask)
Definition: pns_shove.cpp:2038
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1561
bool RewindSpringbackTo(NODE *aNode)
Definition: pns_shove.cpp:1980
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1192
@ 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:1545
bool RewindToLastLockedNode()
Definition: pns_shove.cpp:2009
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:1770
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:788
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1855
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:823
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:614
void UnlockSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:2021
NODE * m_root
Definition: pns_shove.h:173
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1969
OPT_LINE m_newHead
Definition: pns_shove.h:178
NODE * m_springbackDoNotTouchNode
Definition: pns_shove.h:175
NODE * CurrentNode()
Definition: pns_shove.cpp:1948
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:1063
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:170
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:654
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1151
int m_optFlagDisableMask
Definition: pns_shove.h:187
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
Definition: pns_shove.cpp:1242
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:1668
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:171
const LINE NewHead() const
Definition: pns_shove.cpp:1954
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:2044
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:990
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:178
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378
@ 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
E_SERIE r
Definition: eserie.cpp:41
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:1750
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:353
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:618