KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_shove.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <deque>
23#include <cassert>
24#include <math/box2.h>
25
26#include <wx/log.h>
27
28#include "pns_arc.h"
29#include "pns_line.h"
30#include "pns_node.h"
31#include "pns_debug_decorator.h"
32#include "pns_walkaround.h"
33#include "pns_shove.h"
34#include "pns_solid.h"
35#include "pns_optimizer.h"
36#include "pns_via.h"
37#include "pns_utils.h"
38#include "pns_router.h"
39#include "pns_topology.h"
40
41#include "time_limit.h"
42
43// fixme - move all logger calls to debug decorator
44
46
47namespace PNS {
48
49void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
50{
51 OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
52
53 if( changed_area )
54 m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
55
56 ROOT_LINE_ENTRY *re = nullptr;
58
59 if( aOld->OfKind( ITEM::VIA_T ) )
60 {
61 VIA* vold = static_cast<VIA*>( aOld );
62 VIA* vnew = static_cast<VIA*>( aNew.get() );
63 re = touchRootLine( vold );
64 re->newVia = vnew;
65 newId = static_cast<VIA*>( aNew.get() )->Uid();
66
67 PNS_DBG( Dbg(), Message,
68 wxString::Format( "replace-via node=%p vold=%p [%d %d]-> vnew=%p [%d %d] nid %llu", m_currentNode, aOld,
69 vold->Pos().x, vold->Pos().y, aNew.get(), vnew->Pos().x,
70 vnew->Pos().y, newId ) );
71 }
72
73 m_currentNode->Replace( aOld, std::move( aNew ) );
74
75 if( re )
76 m_rootLineHistory[ newId ] = re;
77}
78
79
80SHOVE::ROOT_LINE_ENTRY* SHOVE::replaceLine( LINE& aOld, LINE& aNew, bool aIncludeInChangedArea, bool aAllowRedundantSegments, NODE* aNode )
81{
82 if( aIncludeInChangedArea )
83 {
84 OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
85
86 if( changed_area )
87 {
88 SHAPE_RECT r( *changed_area );
89 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "shove-changed-area" ) );
90
91 m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area )
92 : *changed_area;
93 }
94 }
95
96 int old_sc = aOld.SegmentCount();
97 int old_lc = aOld.LinkCount();
98
99 if( aOld.EndsWithVia() )
100 {
101 for( LINKED_ITEM* lnk : aOld.Links() )
102 {
103 if( lnk->OfKind( ITEM::VIA_T ) )
104 {
105 aOld.Unlink( lnk );
106 }
107 }
108 }
109
110
111 bool foundPredecessor = false;
112 ROOT_LINE_ENTRY *rootEntry = nullptr;
113
114 // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
115 // of the affected tracks in a map. The optimizer can then query the pre-shove shape
116 // for each shoved line and perform additional constraint checks (i.e. prevent overzealous
117 // optimizations)
118
119 // Check if the shoved line already has an ancestor (e.g. line from a previous shove
120 // iteration/cursor movement)
121 for( LINKED_ITEM* link : aOld.Links() )
122 {
123 auto oldLineIter = m_rootLineHistory.find( link->Uid() );
124
125 if( oldLineIter != m_rootLineHistory.end() )
126 {
127 rootEntry = oldLineIter->second;
128 foundPredecessor = true;
129 break;
130 }
131 }
132
133 // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
134 if( !foundPredecessor )
135 {
136 if( ! rootEntry )
137 {
138 rootEntry = new ROOT_LINE_ENTRY( aOld.Clone() );
139 }
140
141 for( LINKED_ITEM* link : aOld.Links() )
142 {
143 m_rootLineHistory[link->Uid()] = rootEntry;
144 }
145 }
146
147 // Now update the NODE (calling Replace invalidates the Links() in a LINE)
148 if( aNode )
149 aNode->Replace( aOld, aNew, aAllowRedundantSegments );
150 else
151 m_currentNode->Replace( aOld, aNew, aAllowRedundantSegments );
152
153
154 // point the Links() of the new line to its oldest ancestor
155 for( LINKED_ITEM* link : aNew.Links() )
156 {
157 m_rootLineHistory[ link->Uid() ] = rootEntry;
158 }
159
160 rootEntry->newLine = aNew;
161
162 return rootEntry;
163}
164
165
166int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
167{
168 if( m_forceClearance >= 0 )
169 return m_forceClearance;
170
171 int clearance = m_currentNode->GetClearance( aA, aB, false );
172
173 if( aA->HasHole() )
174 clearance = std::max( clearance, m_currentNode->GetClearance( aA->Hole(), aB, false ) );
175
176 if( aB->HasHole() )
177 clearance = std::max( clearance, m_currentNode->GetClearance( aA, aB->Hole(), false ) );
178
179 return clearance;
180}
181
182
183void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
184{
185 assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
186 assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
187}
188
189
190SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
191 ALGO_BASE( aRouter )
192{
194 m_forceClearance = -1;
195 m_root = aWorld;
196 m_currentNode = aWorld;
198
199 // Initialize other temporary variables:
200 m_draggedVia = nullptr;
201 m_iter = 0;
202 m_multiLineMode = false;
203 m_headsModified = false;
207}
208
209
211{
212}
213
214
215LINE SHOVE::assembleLine( const LINKED_ITEM* aSeg, int* aIndex, bool aPreCleanup )
216{
217 LINE cur = m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
218
219 if( aPreCleanup )
220 {
221 LINE cleaned;
222 if (preShoveCleanup( &cur, &cleaned ) )
223 return cleaned;
224 }
225
226 return cur;
227}
228
229
230// A dumb function that checks if the shoved line is shoved the right way, e.g. visually
231// "outwards" of the line/via applying pressure on it. Unfortunately there's no mathematical
232// concept of orientation of an open curve, so we use some primitive heuristics: if the shoved
233// line wraps around the start of the "pusher", it's likely shoved in wrong direction.
234
235// Update: there's no concept of an orientation of an open curve, but nonetheless Tom's dumb
236// as.... (censored)
237// Two open curves put together make a closed polygon... Tom should learn high school geometry!
238bool SHOVE::checkShoveDirection( const LINE& aCurLine, const LINE& aObstacleLine,
239 const LINE& aShovedLine ) const
240{
241 SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
242 checker.AddPolyline( aObstacleLine.CLine() );
243 checker.AddPolyline( aShovedLine.CLine().Reverse() );
244
245 bool inside = checker.IsInside();
246
247 return !inside;
248}
249
250
251/*
252 * Push aObstacleLine away from aCurLine's via by the clearance distance, returning the result
253 * in aResultLine.
254 *
255 * Must be called only when aCurLine itself is on another layer (or has no segments) so that it
256 * can be ignored.
257 */
258bool SHOVE::shoveLineFromLoneVia( const LINE& aCurLine, const LINE& aObstacleLine,
259 LINE& aResultLine )
260{
261 // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
262
263 int obstacleLineWidth = aObstacleLine.Width();
264 const VIA& via = aCurLine.Via();
265 int clearance = getClearance( &via, &aObstacleLine );
266 HOLE* viaHole = via.Hole();
267 int holeClearance = getClearance( viaHole, &aObstacleLine );
268
269 if( holeClearance + via.Drill() / 2 > clearance + via.Diameter( aObstacleLine.Layer() ) / 2 )
270 clearance = holeClearance + via.Drill() / 2 - via.Diameter( aObstacleLine.Layer() ) / 2;
271
272 SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
273 SHAPE_LINE_CHAIN path_cw;
274 SHAPE_LINE_CHAIN path_ccw;
275
276 if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
277 return false;
278
279 if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
280 return false;
281
282 const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
283
284 if( shortest.PointCount() < 2 )
285 return false;
286
287 if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
288 return false;
289
290 if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
291 return false;
292
293 aResultLine.SetShape( shortest );
294
295 if( aResultLine.Collide( &aCurLine, m_currentNode, aResultLine.Layer() ) )
296 return false;
297
298 return true;
299}
300
301
302/*
303 * Re-walk aObstacleLine around the given set of hulls, returning the result in aResultLine.
304 */
305bool SHOVE::shoveLineToHullSet( const LINE& aCurLine, const LINE& aObstacleLine,
306 LINE& aResultLine, const HULL_SET& aHulls, bool aPermitAdjustingEndpoints )
307{
308 const int c_ENDPOINT_ON_HULL_THRESHOLD = 10000;
309 int attempt;
310
311 PNS_DBG( Dbg(), BeginGroup, "shove-details", 1 );
312
313 for( attempt = 0; attempt < 4; attempt++ )
314 {
315 bool invertTraversal = ( attempt >= 2 );
316 bool clockwise = attempt % 2;
317 int vFirst = -1, vLast = -1;
318 SHAPE_LINE_CHAIN obs = aObstacleLine.CLine();
319 LINE l( aObstacleLine );
321
322 if( aPermitAdjustingEndpoints )
323 {
324 auto minDistP = [&]( VECTOR2I pref, int& mdist, int& minhull ) -> VECTOR2I
325 {
326 int min_dist = std::numeric_limits<int>::max();
327 VECTOR2I nearestP;
328
329 for( int i = 0; i < (int) aHulls.size(); i++ )
330 {
331 const SHAPE_LINE_CHAIN& hull =
332 aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
333 int dist;
334 const VECTOR2I p = hull.NearestPoint( pref, true );
335
336 if( hull.PointInside( pref ) )
337 dist = 0;
338 else
339 dist = ( p - pref ).EuclideanNorm();
340
341 if( dist < c_ENDPOINT_ON_HULL_THRESHOLD && dist < min_dist )
342 {
343 bool reject = false;
344
345 /*for( int j = 0; j < (int) aHulls.size(); j++ )
346 {
347 if ( i != j && aHulls[j].PointInside( p ) )
348 {
349 reject = true;
350 break;
351 }
352 }*/
353
354 if( !reject )
355 {
356 min_dist = dist;
357 nearestP = p;
358 minhull = invertTraversal ? aHulls.size() - 1 - i : i;
359 }
360 }
361 }
362 mdist = min_dist;
363 return nearestP;
364 };
365
366 int minDist0, minDist1, minhull0, minhull1 ;
367 VECTOR2I p0 = minDistP( l.CPoint( 0 ), minDist0, minhull0 );
368 VECTOR2I p1 = minDistP( l.CPoint( -1 ), minDist1, minhull1 );
369
370 PNS_DBG( Dbg(), Message, wxString::Format( "mindists : %d %d hulls %d %d\n", minDist0, minDist1, minhull0, minhull1 ) );
371
372 if( minDist1 < c_ENDPOINT_ON_HULL_THRESHOLD )
373 {
374 l.Line().SetPoint( -1, p1 );
375 obs = l.CLine();
376 path = l.CLine();
377 }
378
379 if( minDist0 < c_ENDPOINT_ON_HULL_THRESHOLD )
380 {
381 l.Line().SetPoint( 0, p0 );
382 obs = l.CLine();
383 path = l.CLine();
384 }
385 }
386
387
388 bool failWalk = false;
389
390 for( int i = 0; i < (int) aHulls.size(); i++ )
391 {
392 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
393
394 PNS_DBG( Dbg(), AddShape, &hull, YELLOW, 10000, wxString::Format( "hull[%d]", i ) );
395 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path[%d]", i ) );
396 PNS_DBG( Dbg(), AddShape, &obs, LIGHTGRAY, aObstacleLine.Width(), wxString::Format( "obs[%d]", i ) );
397
398 if( !l.Walkaround( hull, path, clockwise ) )
399 {
400 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "Fail-Walk %s %s %d\n" ),
401 hull.Format().c_str(),
402 l.CLine().Format().c_str(),
403 clockwise? 1 : 0) );
404
405 failWalk = true;
406 break;
407 }
408
409 path.Simplify2();
410 l.SetShape( path );
411 }
412
413 if( failWalk )
414 continue;
415
416 for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
417 {
418 if( path.CPoint( i ) != obs.CPoint( i ) )
419 {
420 vFirst = i;
421 break;
422 }
423 }
424
425 int k = obs.PointCount() - 1;
426
427 for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
428 {
429 if( path.CPoint( i ) != obs.CPoint( k ) )
430 {
431 vLast = i;
432 break;
433 }
434 }
435
436 if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( obs ) )
437 {
438 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vfirst-last" ),
439 attempt ) );
440 continue;
441 }
442
443 if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
444 {
445 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vend-start\n" ),
446 attempt ) );
447 continue;
448 }
449
450 if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
451 {
452 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail direction-check" ),
453 attempt ) );
454 aResultLine.SetShape( l.CLine() );
455 continue;
456 }
457
458 if( path.SelfIntersecting() )
459 {
460 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail self-intersect" ),
461 attempt ) );
462 continue;
463 }
464
465 bool colliding = l.Collide( &aCurLine, m_currentNode, l.Layer() );
466
467 #if 0
468 if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
469 {
470 const JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
471
472 for( ITEM* item : jtStart->LinkList() )
473 {
474 if( item->Collide( &l, m_currentNode, l.Layer() ) )
475 colliding = true;
476 }
477 }
478 #endif
479
480 if( colliding )
481 {
482 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail coll-check" ),
483 attempt ) );
484 continue;
485 }
486
487 aResultLine.SetShape( l.CLine() );
488
489 PNS_DBGN( Dbg(), EndGroup );
490
491 return true;
492 }
493
494 PNS_DBGN( Dbg(), EndGroup );
495
496 return false;
497}
498
499
500/*
501 * Push aObstacleLine line away from aCurLine by the clearance distance, and return the result in
502 * aResultLine.
503 */
504bool SHOVE::ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine,
505 LINE& aResultLine )
506{
507 const int cHullFailureExpansionFactor = 1000;
508 int extraHullExpansion = 0;
509
510
511 aResultLine.ClearLinks();
512 bool viaOnEnd = aCurLine.EndsWithVia();
513
514 LINE obstacleLine( aObstacleLine );
515 std::optional<VIA> obsVia;
516
517 if( obstacleLine.EndsWithVia() )
518 {
519 obsVia = aObstacleLine.Via();
520 obstacleLine.RemoveVia();
521 }
522
523 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: voe-cur %d voe-obs %d" ),
524 aCurLine.EndsWithVia()?1:0, aObstacleLine.EndsWithVia()?1:0 ) );
525
526
527 if( viaOnEnd && ( !aCurLine.LayersOverlap( &obstacleLine ) || aCurLine.SegmentCount() == 0 ) )
528 {
529 // Shove obstacleLine to the hull of aCurLine's via.
530 return shoveLineFromLoneVia( aCurLine, obstacleLine, aResultLine );
531 }
532 else
533 {
534 // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
535 // distance + obstacleLine's linewidth so that when re-walking obstacleLine along the
536 // hull it will be at the appropriate clearance.
537
538 int obstacleLineWidth = obstacleLine.Width();
539 int clearance = getClearance( &aCurLine, &obstacleLine );
540 int currentLineSegmentCount = aCurLine.SegmentCount();
541
542 /*PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: cur net %d obs %d cl %d" ),
543 m_router->GetInterface()->GetNetCode( aCurLine.Net() ),
544 m_router->GetInterface()->GetNetCode( obstacleLine.Net() ),
545 clearance ) );*/
546
547 for( int attempt = 0; attempt < 3; attempt++ )
548 {
549 HULL_SET hulls;
550
551 hulls.reserve( currentLineSegmentCount + 1 );
552
553 for( int i = 0; i < currentLineSegmentCount; i++ )
554 {
555 SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
556
557 // Arcs need additional clearance to ensure the hulls are always bigger than the arc
558 if( aCurLine.CLine().IsArcSegment( i ) )
559 {
560 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove add-extra-clearance %d" ),
563 }
564
565 SHAPE_LINE_CHAIN hull = seg.Hull( clearance + extraHullExpansion, obstacleLineWidth, obstacleLine.Layer() );
566
567 hulls.push_back( hull );
568 }
569
570 if( viaOnEnd )
571 {
572 const VIA& via = aCurLine.Via();
573 int viaClearance = getClearance( &via, &obstacleLine );
574 HOLE* viaHole = via.Hole();
575 int holeClearance = getClearance( viaHole, &obstacleLine );
576 int layer = aObstacleLine.Layer();
577
578 if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter( layer ) / 2 )
579 {
580 viaClearance = holeClearance + via.Drill() / 2 - via.Diameter( layer ) / 2;
581 }
582
583 hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth, layer ) );
584 }
585
586 bool permitMovingEndpoints = (attempt >= 2);
587
588 if (shoveLineToHullSet( aCurLine, obstacleLine, aResultLine, hulls, permitMovingEndpoints ) )
589 {
590 if( obsVia )
591 aResultLine.AppendVia( *obsVia );
592
593 return true;
594 }
595
596 extraHullExpansion += cHullFailureExpansionFactor;
597 }
598 }
599
600 return false;
601}
602
603
604/*
605 * TODO describe....
606 */
608{
609 int segIndex;
610
611 LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex, true );
612 LINE shovedLine( obstacleLine );
613 SEGMENT tmp( *aObstacleSeg );
614
615 if( obstacleLine.HasLockedSegments() )
616 {
617 PNS_DBG(Dbg(), Message, "try walk (locked segments)");
618 return SH_TRY_WALK;
619 }
620
621 bool shoveOK = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
622
623 const double extensionWalkThreshold = 1.0;
624
625 double obsLen = obstacleLine.CLine().Length();
626 double shovedLen = shovedLine.CLine().Length();
627 double extensionFactor = 0.0;
628
629 if( obsLen != 0.0f )
630 extensionFactor = shovedLen / obsLen - 1.0;
631
632 //if( extensionFactor > extensionWalkThreshold )
633 // return SH_TRY_WALK;
634
635 assert( obstacleLine.LayersOverlap( &shovedLine ) );
636
637 if( Dbg() )
638 {
639 PNS_DBG( Dbg(), AddItem, aObstacleSeg, BLUE, 0, wxT( "colliding-segment" ) );
640 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxString::Format( "current-line [l %d v %d]", aCurrent.Layer(), aCurrent.EndsWithVia() ) );
641 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxString::Format( "obstacle-line [l %d v %d]", obstacleLine.Layer(), obstacleLine.EndsWithVia() ) );
642 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
643 }
644
645 if( shoveOK )
646 {
647 int rank = aCurrent.Rank();
648 shovedLine.SetRank( rank - 1 );
649
650 shovedLine.Line().Simplify2();
651
652 replaceLine( obstacleLine, shovedLine, true, false );
653
654 if( !pushLineStack( shovedLine ) )
655 return SH_INCOMPLETE;
656
657 return SH_OK;
658 }
659
660 return SH_INCOMPLETE;
661}
662
663
664/*
665 * TODO describe....
666 */
668{
669 int segIndex;
670 LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
671 LINE shovedLine( obstacleLine );
672 ARC tmp( *aObstacleArc );
673
674 if( obstacleLine.HasLockedSegments() )
675 return SH_TRY_WALK;
676
677 bool shoveOK = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
678
679 const double extensionWalkThreshold = 1.0;
680
681 double obsLen = obstacleLine.CLine().Length();
682 double shovedLen = shovedLine.CLine().Length();
683 double extensionFactor = 0.0;
684
685 if( obsLen != 0.0f )
686 extensionFactor = shovedLen / obsLen - 1.0;
687
688 if( extensionFactor > extensionWalkThreshold )
689 return SH_TRY_WALK;
690
691 assert( obstacleLine.LayersOverlap( &shovedLine ) );
692
693 PNS_DBG( Dbg(), AddItem, &tmp, WHITE, 10000, wxT( "obstacle-arc" ) );
694 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
695 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxT( "obstacle-line" ) );
696 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
697
698 if( shoveOK )
699 {
700 int rank = aCurrent.Rank();
701 shovedLine.SetRank( rank - 1 );
702
703 replaceLine( obstacleLine, shovedLine, true, false );
704
705 if( !pushLineStack( shovedLine ) )
706 return SH_INCOMPLETE;
707 }
708
709 return SH_OK;
710}
711
712
713/*
714 * TODO describe....
715 */
716SHOVE::SHOVE_STATUS SHOVE::onCollidingLine( LINE& aCurrent, LINE& aObstacle, int aNextRank )
717{
718 LINE shovedLine( aObstacle );
719
720 bool shoveOK = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
721
722 PNS_DBG( Dbg(), AddItem, &aObstacle, RED, 100000, wxT( "obstacle-line" ) );
723 PNS_DBG( Dbg(), AddItem, &aCurrent, GREEN, 150000, wxT( "current-line" ) );
724 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 200000, wxT( "shoved-line" ) );
725
726 if( shoveOK )
727 {
728#if 0
729 if( shovedLine.Marker() & MK_HEAD )
730 {
731 if( m_multiLineMode )
732 return SH_INCOMPLETE;
733
734 m_newHead = shovedLine;
735 }
736#endif
737 replaceLine( aObstacle, shovedLine, true, false );
738
739 shovedLine.SetRank( aNextRank );
740
741 if( !pushLineStack( shovedLine ) )
742 return SH_INCOMPLETE;
743 }
744
745 return SH_OK;
746}
747
748
749/*
750 * TODO describe....
751 */
752SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle, OBSTACLE& aObstacleInfo )
753{
754 LINE walkaroundLine( aCurrent );
755
756 if( aCurrent.EndsWithVia() )
757 {
758 VIA vh = aCurrent.Via();
759 VIA* via = nullptr;
760 const JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
761
762 if( !jtStart )
763 return SH_INCOMPLETE;
764
765 for( ITEM* item : jtStart->LinkList() )
766 {
767 if( item->OfKind( ITEM::VIA_T ) )
768 {
769 via = (VIA*) item;
770 break;
771 }
772 }
773
774 // TODO(JE) viastacks -- can aObstacle be a via?
775 if( via && via->Collide( aObstacle, m_currentNode, aObstacle->Layer() ) )
776 return onCollidingVia( aObstacle, via, aObstacleInfo, aObstacle->Rank() - 1 );
777 }
778
779 TOPOLOGY topo( m_currentNode );
780 TOPOLOGY::CLUSTER cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start(), 10.0 );
781
782 PNS_DBG( Dbg(), BeginGroup, "walk-cluster", 1 );
783
784 for( ITEM* item : cluster.m_items )
785 PNS_DBG( Dbg(), AddItem, item, RED, 10000, wxT( "cl-item" ) );
786
787 PNS_DBGN( Dbg(), EndGroup );
788
789 WALKAROUND walkaround( m_currentNode, Router() );
790 walkaround.SetDebugDecorator( Dbg() );
791 walkaround.SetSolidsOnly( false );
792 walkaround.RestrictToCluster( true, cluster );
794 walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() ); // fixme: make configurable
795
796 int currentRank = aCurrent.Rank();
797 int nextRank;
798
799 bool success = false;
800
801 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
802
803 for( int attempt = 0; attempt < 2; attempt++ )
804 {
805 if( attempt == 1 || Settings().JumpOverObstacles() )
806 nextRank = currentRank - 1;
807 else
808 nextRank = currentRank + 10000;
809
810 WALKAROUND::RESULT status = walkaround.Route( aCurrent );
811
812 if( status.status[ WALKAROUND::WP_SHORTEST ] != WALKAROUND::ST_DONE )//fixme policies!
813 continue;
814
815 walkaroundLine = status.lines[ WALKAROUND::WP_SHORTEST ];
816
817 walkaroundLine.ClearLinks();
818 walkaroundLine.Unmark();
819 walkaroundLine.Line().Simplify2();
820
821 if( walkaroundLine.HasLoops() )
822 continue;
823
824 PNS_DBG( Dbg(), AddItem, &walkaroundLine, BLUE, 10000, wxT( "walk-line" ) );
825
826#if 0
827 if( aCurrent.Marker() & MK_HEAD )
828 {
829 walkaroundLine.Mark( MK_HEAD );
830
831 if( m_multiLineMode )
832 continue;
833
834 m_newHead = walkaroundLine;
835 }
836#endif
837
838
839 if( !m_lineStack.empty() )
840 {
841 LINE lastLine = m_lineStack.front();
842
843 if( lastLine.Collide( &walkaroundLine, m_currentNode, lastLine.Layer() ) )
844 {
845 LINE dummy( lastLine );
846
847 if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) )
848 {
849 success = true;
850 break;
851 }
852 }
853 else
854 {
855 success = true;
856 break;
857 }
858 }
859 }
860
861 if(!success)
862 return SH_INCOMPLETE;
863
864 replaceLine( aCurrent, walkaroundLine, true, false );
865 walkaroundLine.SetRank( nextRank );
866
867
868 popLineStack();
869
870 if( !pushLineStack( walkaroundLine ) )
871 return SH_INCOMPLETE;
872
873 return SH_OK;
874}
875
876
877void SHOVE::pruneRootLines( NODE *aRemovedNode )
878{
879 PNS_DBG( Dbg(), Message, wxString::Format("prune called" ) );
880
881 NODE::ITEM_VECTOR added, removed;
882 aRemovedNode->GetUpdatedItems( removed, added );
883
884 for( const ITEM* item : added )
885 {
886 if( item->OfKind( ITEM::LINKED_ITEM_MASK_T ) )
887 {
888 const LINKED_ITEM* litem = static_cast<const LINKED_ITEM*>( item );
889
890 m_rootLineHistory.erase( litem->Uid() );
891 }
892 }
893}
894
895
896/*
897 * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
898 * to the dragged via of the last unpopped state.
899 */
901{
902 while( m_nodeStack.size() > 1 )
903 {
904 SPRINGBACK_TAG& spTag = m_nodeStack.back();
905
906 // Prevent the springback algo from erasing NODEs that might contain items used by the ROUTER_TOOL/LINE_PLACER.
907 // I noticed this can happen for the endItem provided to LINE_PLACER::Move() and cause a nasty crash.
909 break;
910
911 std::optional<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
912
913 if( !obs && !spTag.m_locked )
914 {
915 int i;
916
917 PNS_DBG( Dbg(), Message, wxString::Format( "pop-sp node=%p depth=%d", spTag.m_node, spTag.m_node->Depth() ) );
918
919 pruneRootLines( spTag.m_node );
920
921
922 delete spTag.m_node;
923 m_nodeStack.pop_back();
924 }
925 else
926 {
927 break;
928 }
929 }
930
931 if( m_nodeStack.empty() )
932 return m_root;
933
934 SPRINGBACK_TAG& spTag = m_nodeStack.back();
935
936 for( int i = 0; i < spTag.m_draggedVias.size(); i++ )
937 {
938 if (spTag.m_draggedVias[i].valid)
939 {
940 m_headLines[i].prevVia = m_headLines[i].theVia = spTag.m_draggedVias[i];
941 m_headLines[i].geometryModified = true;
942 PNS_DBG( Dbg(), Message,
943 wxString::Format( "restore-springback-via depth=%d %d %d %d %d ",
944 spTag.m_node->Depth(),
945 (int) m_nodeStack.size(),
946 m_headLines[i].theVia->pos.x,
947 m_headLines[i].theVia->pos.y,
948 m_headLines[i].theVia->layers.Start(),
949 m_headLines[i].theVia->layers.End() ) );
950 }
951 }
952
953 return m_nodeStack.back().m_node;
954}
955
956
957/*
958 * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
959 * (which will be restored in the event the stackframe is popped).
960 */
961bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea )
962{
964 OPT_BOX2I prev_area;
965
966 if( !m_nodeStack.empty() )
967 prev_area = m_nodeStack.back().m_affectedArea;
968
969 st.m_draggedVias.resize( m_headLines.size() );
970 int n = 0;
971
972 for( HEAD_LINE_ENTRY& head : m_headLines )
973 {
974 if ( head.theVia )
975 {
976 VIA_HANDLE vhandle = *head.theVia;
977
978 PNS_DBG( Dbg(), Message,
979 wxString::Format( "push-sp via depth=%d %d %d %d %d ", aNode->Depth(), vhandle.pos.x,
980 vhandle.pos.y,
981 vhandle.layers.Start(),
982 vhandle.layers.End() ) );
983
984 st.m_draggedVias[n] = vhandle;
985 }
986
987 n++;
988 }
989
990 st.m_node = aNode;
991
992 if( aAffectedArea )
993 {
994 if( prev_area )
995 st.m_affectedArea = prev_area->Merge( *aAffectedArea );
996 else
997 st.m_affectedArea = aAffectedArea;
998 }
999 else
1000 {
1001 st.m_affectedArea = prev_area;
1002 }
1003
1004 st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
1005 st.m_locked = false;
1006
1007 m_nodeStack.push_back( st );
1008
1009 PNS_DBG( Dbg(), Message, wxString::Format( "push-sp depth=%d node=%p", st.m_node->Depth(), st.m_node ) );
1010
1011 return true;
1012}
1013
1014
1015/*
1016 * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
1017 * to keep it from landing on an existing joint.)
1018 */
1019SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aNewRank, bool aDontUnwindStack )
1020{
1021 LINE_PAIR_VEC draggedLines;
1022 VECTOR2I p0( aVia->Pos() );
1023 const JOINT* jt = m_currentNode->FindJoint( p0, aVia );
1024 VECTOR2I p0_pushed( p0 + aForce );
1025
1026 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "via force [%d %d]\n" ), aForce.x, aForce.y ) );
1027
1028 // nothing to do...
1029 if ( aForce.x == 0 && aForce.y == 0 )
1030 return SH_OK;
1031
1032 if( !jt )
1033 {
1034 PNS_DBG( Dbg(), Message, wxT( "weird, can't find the center-of-via joint\n" ) );
1035 return SH_INCOMPLETE;
1036 }
1037
1038 if( Settings().ShoveVias() == false || aVia->IsLocked() )
1039 return SH_TRY_WALK;
1040
1041 if( jt->IsLocked() )
1042 return SH_INCOMPLETE;
1043
1044 // make sure pushed via does not overlap with any existing joint
1045 while( true )
1046 {
1047 const JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
1048
1049 if( !jt_next )
1050 break;
1051
1052 p0_pushed += aForce.Resize( 2 );
1053 }
1054
1055 std::unique_ptr<VIA> pushedVia = Clone( *aVia );
1056 pushedVia->SetPos( p0_pushed );
1057 pushedVia->Mark( aVia->Marker() );
1058
1059 for( ITEM* item : jt->LinkList() )
1060 {
1061 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1062 {
1063 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1064 LINE_PAIR lp;
1065 int segIndex;
1066
1067 lp.first = assembleLine( li, &segIndex );
1068
1069 if( lp.first.HasLockedSegments() )
1070 return SH_TRY_WALK;
1071
1072 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
1073
1074 if( segIndex == 0 )
1075 lp.first.Reverse();
1076
1077 lp.second = lp.first;
1078 lp.second.ClearLinks();
1079 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
1080 lp.second.Line().Simplify2();
1081 draggedLines.push_back( lp );
1082 }
1083 }
1084
1085 pushedVia->SetRank( aNewRank );
1086 PNS_DBG( Dbg(), Message, wxString::Format("via rank %d, fanout %d\n", pushedVia->Rank(), (int) draggedLines.size() ) );
1087
1088 PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
1089 PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
1090
1091 VIA *v2 = pushedVia.get();
1092
1093 if( !aDontUnwindStack )
1094 unwindLineStack( aVia );
1095
1096 replaceItems( aVia, std::move( pushedVia ) );
1097
1098 if( draggedLines.empty() ) // stitching via? make sure the router won't forget about it
1099 {
1100 LINE tmpLine;
1101 tmpLine.LinkVia( v2 );
1102 if( !pushLineStack( tmpLine ) )
1103 return SH_INCOMPLETE;
1104 }
1105
1106 int n = 0;
1107 for( LINE_PAIR lp : draggedLines )
1108 {
1109 if( !aDontUnwindStack )
1110 unwindLineStack( &lp.first );
1111
1112 PNS_DBG( Dbg(), Message, wxString::Format("fan %d/%d\n", n, (int) draggedLines.size() ) );
1113 n++;
1114
1115 if( lp.second.SegmentCount() )
1116 {
1117 lp.second.ClearLinks();
1118 ROOT_LINE_ENTRY* rootEntry = replaceLine( lp.first, lp.second, true, true );
1119
1120 lp.second.LinkVia( v2 );
1121
1122 if( !aDontUnwindStack )
1123 unwindLineStack( &lp.second );
1124
1125 lp.second.SetRank( aNewRank );
1126
1127 if( rootEntry )
1128 rootEntry->newLine = lp.second; // fixme: it's inelegant
1129
1130
1131 PNS_DBG( Dbg(), Message, wxString::Format("PushViaF %p %d eov %d\n", &lp.second, lp.second.SegmentCount(), lp.second.EndsWithVia()?1:0 ) );
1132
1133 if( !pushLineStack( lp.second ) ) //, true ) ) // WHY?
1134 return SH_INCOMPLETE;
1135 }
1136 else
1137 {
1138 m_currentNode->Remove( lp.first );
1139 }
1140
1141 PNS_DBG( Dbg(), AddItem, &lp.first, LIGHTGREEN, 10000, wxT( "fan-pre" ) );
1142 PNS_DBG( Dbg(), AddItem, &lp.second, LIGHTRED, 10000, wxT( "fan-post" ) );
1143 }
1144
1145 return SH_OK;
1146}
1147
1148
1149/*
1150 * Calculate the minimum translation vector required to resolve a collision with a via and
1151 * shove the via by that distance.
1152 */
1153SHOVE::SHOVE_STATUS SHOVE::onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia, OBSTACLE& aObstacleInfo, int aNextRank )
1154{
1155 assert( aObstacleVia );
1156
1157 int clearance = getClearance( aCurrent, aObstacleVia );
1158 VECTOR2I mtv;
1159 int rank = -1;
1160
1161 bool lineCollision = false;
1162 bool viaCollision = false;
1163 bool solidCollision = false;
1164 VECTOR2I mtvLine, mtvVia, mtvSolid;
1165
1166 PNS_DBG( Dbg(), BeginGroup, "push-via-by-line", 1 );
1167
1168 if( aCurrent->OfKind( ITEM::LINE_T ) )
1169 {
1170 VIA vtmp ( *aObstacleVia );
1171 int layer = aCurrent->Layer();
1172
1173 if( aObstacleInfo.m_maxFanoutWidth > 0
1174 && aObstacleInfo.m_maxFanoutWidth > aObstacleVia->Diameter( layer ) )
1175 {
1176 vtmp.SetDiameter( layer, aObstacleInfo.m_maxFanoutWidth );
1177 }
1178
1179 LINE* currentLine = (LINE*) aCurrent;
1180
1181 PNS_DBG( Dbg(), AddItem, currentLine, LIGHTRED, 10000, wxT( "current-line" ) );
1182
1183 if( currentLine->EndsWithVia() )
1184 {
1185 PNS_DBG( Dbg(), AddItem, &currentLine->Via(), LIGHTRED, 10000, wxT( "current-line-via" ) );
1186 }
1187
1188 PNS_DBG( Dbg(), AddItem, vtmp.Clone(), LIGHTRED, 100000, wxT( "orig-via" ) );
1189
1190 lineCollision = vtmp.Shape( layer )->Collide( currentLine->Shape( -1 ),
1191 clearance + currentLine->Width() / 2,
1192 &mtvLine );
1193
1194 // Check the via if present. Via takes priority.
1195 if( currentLine->EndsWithVia() )
1196 {
1197 const VIA& currentVia = currentLine->Via();
1198 int viaClearance = getClearance( &currentVia, &vtmp );
1199 VECTOR2I layerMtv;
1200
1201 for( int viaLayer : currentVia.RelevantShapeLayers( &vtmp ) )
1202 {
1203 viaCollision |= currentVia.Shape( viaLayer )->Collide( vtmp.Shape( viaLayer ),
1204 viaClearance,
1205 &layerMtv );
1206
1207 if( layerMtv.SquaredEuclideanNorm() > mtvVia.SquaredEuclideanNorm() )
1208 mtvVia = layerMtv;
1209 }
1210 }
1211 }
1212 else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1213 {
1214 PNS_DBG( Dbg(), Message, wxT("collidee-is-solid" ) );
1215 // TODO(JE) if this case is real, handle via stacks
1216 solidCollision = aCurrent->Shape( -1 )->Collide( aObstacleVia->Shape( -1 ), clearance,
1217 &mtvSolid );
1218 //PNS_DBGN( Dbg(), EndGroup );
1219
1220 // TODO: is this possible at all? We don't shove solids.
1221 //return SH_INCOMPLETE;
1222 }
1223
1224 // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1225 if( viaCollision )
1226 mtv = -mtvVia;
1227 else if ( lineCollision )
1228 mtv = -mtvLine;
1229 else if ( solidCollision )
1230 mtv = -mtvSolid;
1231 else
1232 mtv = VECTOR2I(0, 0);
1233
1234 SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, aNextRank );
1235 PNS_DBG( Dbg(), Message, wxString::Format("push-or-shove-via st %d", st ) );
1236
1237 PNS_DBGN( Dbg(), EndGroup );
1238
1239 return st;
1240}
1241
1242
1243/*
1244 * TODO describe....
1245 */
1246SHOVE::SHOVE_STATUS SHOVE::onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia, OBSTACLE& aObstacleInfo )
1247{
1248 int n = 0;
1249
1250 if( aCurrent.EndsWithVia() )
1251 {
1252 const VECTOR2I p0 = aCurrent.Via().Pos();
1253 const VECTOR2I p1 = aObstacleVia->Pos();
1254
1255 int layer = aCurrent.Layer();
1256 int dist = (p0 - p1).EuclideanNorm() - aCurrent.Via().Diameter( layer ) / 2
1257 - aObstacleVia->Diameter( layer ) / 2;
1258
1259 int clearance = getClearance( &aCurrent.Via(), aObstacleVia );
1260
1261 SHAPE_LINE_CHAIN hull = aObstacleVia->Hull( clearance, aCurrent.Width(), layer );
1262
1263 bool epInsideHull = hull.PointInside( p0 );
1264
1265 PNS_DBG( Dbg(), AddShape, &hull, LIGHTYELLOW, 100000, wxT( "obstacle-via-hull" ) );
1266 PNS_DBG( Dbg(), Message, wxString::Format("via2via coll check dist %d cl %d delta %d pi %d\n", dist, clearance, dist - clearance, epInsideHull ? 1 : 0) );
1267
1268 bool viaCollision = false;
1269
1270 for( int viaLayer : aCurrent.Via().RelevantShapeLayers( aObstacleVia ) )
1271 {
1272 viaCollision |=
1273 aCurrent.Via().Shape( viaLayer )->Collide( aObstacleVia->Shape( viaLayer ),
1274 clearance );
1275 }
1276
1277 if( viaCollision )
1278 {
1279 return onCollidingVia( &aCurrent, aObstacleVia, aObstacleInfo, aCurrent.Rank() - 1 );
1280 }
1281 }
1282
1283 LINE cur( aCurrent );
1284 cur.ClearLinks();
1285
1286 const JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1287 LINE shoved( aCurrent );
1288 shoved.ClearLinks();
1289
1290 cur.RemoveVia();
1291 unwindLineStack( &aCurrent );
1292
1293 for( ITEM* item : jt->LinkList() )
1294 {
1295 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1296 {
1297 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1298 LINE head = assembleLine( li );
1299
1300 head.AppendVia( *aObstacleVia );
1301
1302 bool shoveOK = ShoveObstacleLine( head, cur, shoved );
1303
1304 if( !shoveOK )
1305 {
1306 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via-fail-shove", m_iter );
1307 PNS_DBG( Dbg(), AddItem, aObstacleVia, LIGHTRED, 100000, wxT( "obstacle-via" ) );
1308 PNS_DBG( Dbg(), AddItem, &aCurrent, LIGHTGREEN, 10000, wxT( "current-line" ) );
1309 PNS_DBG( Dbg(), AddItem, &shoved, LIGHTRED, 10000, wxT( "shoved-line" ) );
1310
1311 if( aCurrent.EndsWithVia() )
1312 {
1313 PNS_DBG( Dbg(), AddItem, &aCurrent.Via(), LIGHTGREEN, 100000, wxT( "current-line-via" ) );
1314 }
1315
1316 PNS_DBGN( Dbg(), EndGroup );
1317
1318 return SH_INCOMPLETE;
1319 }
1320
1321 cur.SetShape( shoved.CLine() );
1322 n++;
1323 }
1324 }
1325
1326 if( !n )
1327 {
1328 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via-fail-lonevia", m_iter );
1329 PNS_DBG( Dbg(), AddItem, aObstacleVia, LIGHTRED, 100000, wxT( "the-via" ) );
1330 PNS_DBG( Dbg(), AddItem, &aCurrent, LIGHTGREEN, 10000, wxT( "current-line" ) );
1331 PNS_DBGN( Dbg(), EndGroup );
1332
1333 LINE head( aCurrent );
1334 head.Line().Clear();
1335 head.AppendVia( *aObstacleVia );
1336 head.ClearLinks();
1337
1338 bool shoveOK = ShoveObstacleLine( head, aCurrent, shoved );
1339
1340 if( !shoveOK )
1341 return SH_INCOMPLETE;
1342
1343 cur.SetShape( shoved.CLine() );
1344 }
1345
1346 if( aCurrent.EndsWithVia() )
1347 shoved.AppendVia( aCurrent.Via() );
1348
1349 PNS_DBG( Dbg(), BeginGroup, "on-reverse-via", m_iter );
1350 PNS_DBG( Dbg(), AddItem, aObstacleVia, YELLOW, 0, wxT( "rr-the-via" ) );
1351 PNS_DBG( Dbg(), AddItem, &aCurrent, BLUE, 0, wxT( "rr-current-line" ) );
1352 PNS_DBG( Dbg(), AddItem, &shoved, GREEN, 0, wxT( "rr-shoved-line" ) );
1353 PNS_DBGN( Dbg(), EndGroup );
1354
1355 int currentRank = aCurrent.Rank();
1356 replaceLine( aCurrent, shoved, true, false );
1357
1358 if( !pushLineStack( shoved ) )
1359 return SH_INCOMPLETE;
1360
1361 shoved.SetRank( currentRank );
1362
1363 return SH_OK;
1364}
1365
1366
1368{
1369 int d = 0;
1370
1371 for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1372 {
1373 if( i->ContainsLink( aSeg ) )
1374 {
1375 PNS_DBG(Dbg(), Message, wxString::Format("Unwind lc %d (depth %d/%d)", i->SegmentCount(), d, (int)m_lineStack.size() ) );
1376
1377// note to my future self: if we have a "tadpole" in the stack, keep track of the via even if the parent line has been deleted.
1378// otherwise - the via will be ignored in the case of collisions with tracks on another layer. Can happen pretty often in densely packed PCBs.
1379 if( i->EndsWithVia() && !aSeg->OfKind( ITEM::VIA_T ) )
1380 {
1381 i = m_lineStack.erase( i );
1382 }
1383 else
1384 {
1385 VIA* via = nullptr;
1386
1387 for( LINKED_ITEM* l : i->Links() )
1388 {
1389 if( l->OfKind( ITEM::VIA_T ) )
1390 {
1391 via = static_cast<VIA*>( l );
1392 }
1393 }
1394
1395 if( via )
1396 {
1397 i->ClearLinks();
1398 i->LinkVia( via );
1399 }
1400 i++;
1401 }
1402 }
1403 else
1404 {
1405 i++;
1406 }
1407
1408 d++;
1409 }
1410
1411 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1412 {
1413 if( i->ContainsLink( aSeg ) )
1414 i = m_optimizerQueue.erase( i );
1415 else
1416 i++;
1417 }
1418}
1419
1420
1421void SHOVE::unwindLineStack( const ITEM* aItem )
1422{
1423 if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1424 {
1425 unwindLineStack( static_cast<const LINKED_ITEM*>( aItem ) );
1426 }
1427 else if( aItem->OfKind( ITEM::LINE_T ) )
1428 {
1429 const LINE* l = static_cast<const LINE*>( aItem );
1430
1431 for( const LINKED_ITEM* seg : l->Links() )
1432 unwindLineStack( seg );
1433 }
1434}
1435
1436
1437bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1438{
1439 if( !aL.IsLinked() && aL.SegmentCount() != 0 )
1440 {
1441 PNS_DBG( Dbg(), AddItem, &aL, BLUE, 10000, wxT( "push line stack failed" ) );
1442
1443 return false;
1444 }
1445
1446 if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1447 {
1448 m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1449 }
1450 else
1451 {
1452 m_lineStack.push_back( aL );
1453 }
1454
1455
1457 m_optimizerQueue.push_back( aL );
1458
1459 return true;
1460}
1461
1462
1464{
1465 int pre = m_optimizerQueue.size();
1466 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1467 {
1468 bool found = false;
1469
1470 for( LINKED_ITEM* s : aLine.Links() )
1471 {
1472 PNS_DBG( Dbg(), Message,
1473 wxString::Format( "cur lc %d lnk %p cnt %d", i->LinkCount(), s, aLine.LinkCount() ) );
1474
1475 if( i->ContainsLink( s ) && !s->OfKind( ITEM::VIA_T ) )
1476 {
1477
1478 i = m_optimizerQueue.erase( i );
1479 found = true;
1480 break;
1481 }
1482 }
1483
1484 if( !found )
1485 i++;
1486 }
1487
1488 return true;
1489}
1490
1492{
1493 LINE& l = m_lineStack.back();
1495 m_lineStack.pop_back();
1496}
1497
1498
1499bool SHOVE::fixupViaCollisions( const LINE* aCurrent, OBSTACLE& obs )
1500{
1501 int layer = aCurrent->Layer();
1502
1503 // if the current obstacle is a via, consider also the lines connected to it
1504 // if their widths are larger or equal than the via diameter, the shove algorithm
1505 // will very likely fail in the subsequent iterations (as our base assumption is track
1506 // ends can never move on their own, only dragged by force-propagated vias
1507
1508 // our colliding item is a via: just find the max width of the traces connected to it
1509 if( obs.m_item->OfKind( ITEM::VIA_T ) )
1510 {
1511 const VIA* v = static_cast<const VIA*>( obs.m_item );
1512 int maxw = 0;
1513 const JOINT* jv = m_currentNode->FindJoint( v->Pos(), v );
1514
1515 ITEM_SET links( jv->CLinks() );
1516
1517 for( ITEM* link : links )
1518 {
1519 if( link->OfKind( ITEM::SEGMENT_T ) ) // consider segments ...
1520 {
1521 const SEGMENT* seg = static_cast<const SEGMENT*>( link );
1522 maxw = std::max( seg->Width(), maxw );
1523 }
1524 else if( link->OfKind( ITEM::ARC_T ) ) // ... or arcs
1525 {
1526 const ARC* arc = static_cast<const ARC*>( link );
1527 maxw = std::max( arc->Width(), maxw );
1528 }
1529 }
1530
1531 obs.m_maxFanoutWidth = 0;
1532
1533 if( maxw > 0 && maxw >= v->Diameter( layer ) )
1534 {
1535 obs.m_maxFanoutWidth = maxw + 1;
1536 PNS_DBG( Dbg(), Message,
1537 wxString::Format( "Fixup via: new-w %d via-w %d", maxw, v->Diameter( layer ) ) );
1538
1539 return true;
1540 }
1541 return false;
1542 }
1543
1544
1545 // our colliding item is a segment. check if it has a via on either of the ends.
1546 if( !obs.m_item->OfKind( ITEM::SEGMENT_T ) )
1547 return false;
1548
1549 const SEGMENT* s = static_cast<const SEGMENT*>( obs.m_item );
1550 int sl = s->Layer();
1551
1552 const JOINT* ja = m_currentNode->FindJoint( s->Seg().A, s );
1553 const JOINT* jb = m_currentNode->FindJoint( s->Seg().B, s );
1554
1555 VIA* vias[] = { ja->Via(), jb->Via() };
1556
1557 for( int i = 0; i < 2; i++ )
1558 {
1559 VIA* v = vias[i];
1560
1561 // via diameter is larger than the segment width - cool, the force propagation algo
1562 // will be able to deal with it, no need to intervene
1563 if( !v || v->Diameter( sl ) > s->Width() )
1564 continue;
1565
1566 VIA vtest( *v );
1567 vtest.SetDiameter( sl, s->Width() );
1568
1569 // enlarge the via to the width of the segment
1570 if( vtest.Collide( aCurrent, m_currentNode, aCurrent->Layer() ) )
1571 {
1572 // if colliding, drop the segment in the shove iteration loop and force-propagate the via instead
1573 obs.m_item = v;
1574 obs.m_maxFanoutWidth = s->Width() + 1;
1575 return true;
1576 }
1577 }
1578 return false;
1579}
1580
1581/*
1582 * Resolve the next collision.
1583 */
1585{
1586 LINE currentLine = m_lineStack.back();
1587 NODE::OPT_OBSTACLE nearest;
1588 SHOVE_STATUS st = SH_NULL;
1589
1590 ROUTER_IFACE* iface = Router()->GetInterface();
1591
1592 if( Dbg() )
1593 Dbg()->SetIteration( aIter );
1594
1595 PNS_DBG( Dbg(), AddItem, &currentLine, RED, currentLine.Width(),
1596 wxString::Format( wxT( "current sc=%d net=%s evia=%d" ),
1597 currentLine.SegmentCount(),
1598 iface->GetNetName( currentLine.Net() ),
1599 currentLine.EndsWithVia() ? 1 : 0 ) );
1600
1602 {
1604 opts.m_kindMask = search_order;
1605 opts.m_filter = [ this ] ( const ITEM* item ) -> bool
1606 {
1607 bool rv = true;
1608
1610 {
1611 const LINKED_ITEM* litem = static_cast<const LINKED_ITEM*>( item );
1612 ROOT_LINE_ENTRY* ent = this->findRootLine( litem );
1613
1614 if( !ent && m_defaultPolicy & SHP_IGNORE )
1615 rv = false;
1616
1617 if( ent && ent->policy & SHP_IGNORE )
1618 rv = false;
1619 }
1620 else
1621 {
1623 rv = false;
1624 }
1625
1626 return rv;
1627 };
1628
1629 nearest = m_currentNode->NearestObstacle( &currentLine, opts );
1630
1631 if( nearest )
1632 {
1633 PNS_DBG( Dbg(), AddShape, nearest->m_item->Shape( currentLine.Layer() ), YELLOW, 10000,
1634 wxString::Format( "nearest %p %s rank %d",
1635 nearest->m_item,
1636 nearest->m_item->KindStr(),
1637 nearest->m_item->Rank() ) );
1638 }
1639
1640 if( nearest )
1641 break;
1642 }
1643
1644 if( !nearest )
1645 {
1646 m_lineStack.pop_back();
1647 PNS_DBG( Dbg(), Message, wxT( "no-nearest-item ") );
1648 return SH_OK;
1649 }
1650
1651 bool viaFixup = fixupViaCollisions( &currentLine, *nearest );
1652
1653 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "iter %d: via-fixup %d" ), aIter, viaFixup?1:0 ) );
1654
1655
1656 ITEM* ni = nearest->m_item;
1657
1658 UNITS_PROVIDER up( pcbIUScale, EDA_UNITS::MILLIMETRES );
1659 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "NI: %s (%s) %p %d" ),
1660
1661 ni->Format(),
1662 ni->Parent() ? ni->Parent()->GetItemDescription( &up, false )
1663 : wxString( wxT( "null" ) ),
1664 ni,
1665 ni->OwningNode()->Depth() ) );
1666
1667 unwindLineStack( ni );
1668
1669 if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1670 {
1671 // Collision with a higher-ranking object (ie: one that we've already shoved)
1672 //
1673 switch( ni->Kind() )
1674 {
1675 case ITEM::VIA_T:
1676 {
1677 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-via" ), aIter ), 0 );
1678
1679 // TODO(JE) viastacks -- via-via collisions here?
1680 if( currentLine.EndsWithVia()
1681 && nearest->m_item->Collide( &currentLine.Via(), m_currentNode,
1682 nearest->m_item->Layer() ) )
1683 {
1684 PNS_DBG( Dbg(), AddItem, nearest->m_item, YELLOW, 100000, wxT("v2v nearesti" ) );
1685 //PNS_DBG( Dbg(), AddItem, nearest->m_head,RED, 100000, wxString::Format("v2v nearesth force=%d,%d" ) );
1686
1687 st = onCollidingVia( &currentLine, (VIA*) ni, *nearest, ni->Rank() + 1 );
1688
1689 //ni->SetRank( currentLine.Rank() );
1690 }
1691 else
1692 {
1693 st = onReverseCollidingVia( currentLine, (VIA*) ni, *nearest );
1694 }
1695
1696 PNS_DBGN( Dbg(), EndGroup );
1697
1698 break;
1699 }
1700
1701 case ITEM::SEGMENT_T:
1702 {
1703 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-segment" ),
1704 aIter ), 0 );
1705
1706 PNS_DBG( Dbg(), AddItem, ni, YELLOW, 100000, wxT("head" ) );
1707
1708 LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1709
1710 popLineStack();
1711
1712 if( currentLine.EndsWithVia()
1713 && currentLine.Via().Collide( (SEGMENT*) ni, m_currentNode, currentLine.Layer() ) )
1714 {
1715 VIA_HANDLE vh;
1716 vh.layers = currentLine.Via().Layers();
1717 vh.net = currentLine.Via().Net();
1718 vh.pos = currentLine.Via().Pos();
1719 vh.valid = true;
1720 auto rvia = m_currentNode->FindViaByHandle( vh );
1721 if ( !rvia )
1722 st = SH_INCOMPLETE;
1723 else
1724 st = onCollidingVia( &revLine, rvia, *nearest, revLine.Rank() + 1 );
1725 }
1726 else
1727 st = onCollidingLine( revLine, currentLine, revLine.Rank() + 1 );
1728
1729
1730 if( !pushLineStack( revLine ) )
1731 {
1732 return SH_INCOMPLETE;
1733 }
1734
1735
1736 PNS_DBGN( Dbg(), EndGroup );
1737
1738 break;
1739 }
1740
1741 case ITEM::ARC_T:
1742 {
1743 //TODO(snh): Handle Arc shove separate from track
1744 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: reverse-collide-arc " ), aIter ), 0 );
1745 LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1746
1747 popLineStack();
1748 st = onCollidingLine( revLine, currentLine, revLine.Rank() - 1 );
1749
1750 PNS_DBGN( Dbg(), EndGroup );
1751
1752 if( !pushLineStack( revLine ) )
1753 return SH_INCOMPLETE;
1754
1755 break;
1756 }
1757
1758 default:
1759 assert( false );
1760 }
1761 }
1762 else
1763 {
1764 // Collision with a lower-ranking object or a solid
1765 //
1766 switch( ni->Kind() )
1767 {
1768 case ITEM::SEGMENT_T:
1769 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-segment " ), aIter ), 0 );
1770
1771 st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1772
1773 if( st == SH_TRY_WALK )
1774 st = onCollidingSolid( currentLine, ni, *nearest );
1775
1776 PNS_DBGN( Dbg(), EndGroup );
1777
1778 break;
1779
1780 //TODO(snh): Customize Arc collide
1781 case ITEM::ARC_T:
1782 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-arc " ), aIter ), 0 );
1783
1784 st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1785
1786 if( st == SH_TRY_WALK )
1787 st = onCollidingSolid( currentLine, ni, *nearest );
1788
1789 PNS_DBGN( Dbg(), EndGroup );
1790
1791 break;
1792
1793 case ITEM::VIA_T:
1794 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: collide-via (fixup: %d)" ), aIter, 0 ), 0 );
1795 st = onCollidingVia( &currentLine, (VIA*) ni, *nearest, currentLine.Rank() - 1 );
1796
1797 if( st == SH_TRY_WALK )
1798 st = onCollidingSolid( currentLine, ni, *nearest );
1799
1800 PNS_DBGN( Dbg(), EndGroup );
1801
1802 break;
1803
1804 case ITEM::HOLE_T:
1805 case ITEM::SOLID_T:
1806 PNS_DBG( Dbg(), BeginGroup, wxString::Format( wxT( "iter %d: walk-solid " ), aIter ), 0);
1807 st = onCollidingSolid( currentLine, ni, *nearest );
1808
1809 PNS_DBGN( Dbg(), EndGroup );
1810
1811 break;
1812
1813 default:
1814 break;
1815 }
1816 }
1817
1818 return st;
1819}
1820
1821
1822/*
1823 * Resolve collisions.
1824 * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1825 * long as they propagate further collisions, or until the iteration timeout or max iteration
1826 * count is reached.
1827 */
1829{
1830 SHOVE_STATUS st = SH_OK;
1831
1833
1834 PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1835 m_root->JointCount(),
1837
1838 int iterLimit = Settings().ShoveIterationLimit();
1839 TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1840
1841 m_iter = 0;
1842
1843 timeLimit.Restart();
1844
1845 if( m_lineStack.empty() && m_draggedVia )
1846 {
1847 // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1848 // the stack.
1850 }
1851
1852 while( !m_lineStack.empty() )
1853 {
1854 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1855 m_currentNode, (int) m_lineStack.size() ) );
1856
1857 st = shoveIteration( m_iter );
1858
1859 m_iter++;
1860
1861 if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1862 {
1863 PNS_DBG( Dbg(), Message, wxString::Format( "Fail [time limit expired: %d iter %d iter limit %d",
1864 timeLimit.Expired()?1:0, m_iter, iterLimit ) );
1865 st = SH_INCOMPLETE;
1866 break;
1867 }
1868 }
1869
1870 return st;
1871}
1872
1873
1875{
1876 OPT_BOX2I area;
1877
1878 if( !m_nodeStack.empty() )
1879 area = m_nodeStack.back().m_affectedArea;
1880
1881 if( area && m_affectedArea)
1882 area->Merge( *m_affectedArea );
1883 else if( !area )
1884 area = m_affectedArea;
1885
1886 return area;
1887}
1888
1889
1891{
1892 for( const LINKED_ITEM* link : aLine.Links() )
1893 {
1894 auto it = m_rootLineHistory.find( link->Uid() );
1895
1896 if( it != m_rootLineHistory.end() )
1897 return it->second;
1898 }
1899
1900 return nullptr;
1901}
1902
1904{
1905 auto it = m_rootLineHistory.find( aItem->Uid() );
1906
1907 if( it != m_rootLineHistory.end() )
1908 return it->second;
1909
1910 return nullptr;
1911}
1912
1913
1915{
1916 for( const LINKED_ITEM* link : aLine.Links() )
1917 {
1918 auto it = m_rootLineHistory.find( link->Uid() );
1919
1920 if( it != m_rootLineHistory.end() )
1921 {
1922 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "touch [found] uid=%llu type=%s"), link->Uid(), link->KindStr() ) );
1923
1924 return it->second;
1925 }
1926 }
1927
1928 auto rootEntry = new ROOT_LINE_ENTRY( aLine.Clone() );
1929
1930
1931 for( const LINKED_ITEM* link : aLine.Links() )
1932 {
1933 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "touch [create] uid=%llu type=%s"), link->Uid(), link->KindStr() ) );
1934 m_rootLineHistory[link->Uid()] = rootEntry;
1935 }
1936
1937
1938 return rootEntry;
1939}
1940
1941
1943{
1944 auto it = m_rootLineHistory.find( aItem->Uid() );
1945
1946 if( it != m_rootLineHistory.end() )
1947 {
1948 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "touch [create] uid=%llu"), aItem->Uid() ) );
1949 return it->second;
1950 }
1951
1952 auto rootEntry = new ROOT_LINE_ENTRY( nullptr );
1953
1954 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "touch [create] uid=%llu"), aItem->Uid() ) );
1955 m_rootLineHistory[ aItem->Uid() ] = rootEntry;
1956
1957 return rootEntry;
1958}
1959
1960
1962{
1963 OPTIMIZER optimizer( aNode );
1964 int optFlags = 0;
1965 int n_passes = 0;
1966
1968
1970
1971 int maxWidth = 0;
1972
1973 for( LINE& line : m_optimizerQueue )
1974 maxWidth = std::max( line.Width(), maxWidth );
1975
1976 if( area )
1977 {
1978 area->Inflate( maxWidth );
1979 area = area->Intersect( VisibleViewArea() );
1980 }
1981
1982 switch( effort )
1983 {
1984 case OE_LOW:
1985 optFlags |= OPTIMIZER::MERGE_OBTUSE;
1986 n_passes = 1;
1987 break;
1988
1989 case OE_MEDIUM:
1990 optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1991 n_passes = 2;
1992 break;
1993
1994 case OE_FULL:
1995 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1996 n_passes = 2;
1997 break;
1998
1999 default:
2000 break;
2001 }
2002
2004
2005 if( area )
2006 {
2007 SHAPE_RECT r( *area );
2008
2009 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "opt-area" ) );
2010
2011 optFlags |= OPTIMIZER::RESTRICT_AREA;
2012 optimizer.SetRestrictArea( *area, false );
2013 }
2014
2016
2017 // Smart Pads is incompatible with 90-degree mode for now
2018 if( Settings().SmartPads()
2019 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 ) )
2020 {
2021 optFlags |= OPTIMIZER::SMART_PADS;
2022 }
2023
2024
2025 optimizer.SetEffortLevel( optFlags & ~m_optFlagDisableMask );
2026 optimizer.SetCollisionMask( ITEM::ANY_T );
2027
2028 std::set<const ITEM*> itemsChk;
2029
2030 auto iface = Router()->GetInterface();
2031
2032 for( int pass = 0; pass < n_passes; pass++ )
2033 {
2034 std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
2035
2036 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "optimize %d lines, pass %d"), (int)m_optimizerQueue.size(), (int)pass ) );
2037
2038 for( int i = 0; i < m_optimizerQueue.size(); i++ )
2039 {
2040 LINE& lineToOpt = m_optimizerQueue[i];
2041 LINE* rootLine = nullptr;
2042 auto rootEntry = findRootLine( lineToOpt );
2043
2044 if( rootEntry )
2045 {
2046 rootLine = rootEntry->rootLine;
2047
2048 if( rootEntry->policy & SHP_DONT_OPTIMIZE )
2049 continue;
2050 if( rootEntry->isHead )
2051 continue;
2052 }
2053
2054 LINE optimized;
2055 if( optimizer.Optimize( &lineToOpt, &optimized, rootLine ) )
2056 {
2057 assert( optimized.LinkCount() == 0 );
2058
2059 PNS_DBG( Dbg(), AddShape, &lineToOpt.CLine(), BLUE, 0, wxT( "shove-pre-opt" ) );
2060 if( rootLine )
2061 PNS_DBG( Dbg(), AddItem, rootLine, RED, 0, wxT( "shove-root-opt" ) );
2062
2063 replaceLine( lineToOpt, optimized, false, aNode );
2064 m_optimizerQueue[i] = optimized; // keep links in the lines in the queue up to date
2065
2066 PNS_DBG( Dbg(), AddShape, &optimized.CLine(), GREEN, 0, wxT( "shove-post-opt" ) );
2067 }
2068 }
2069 }
2070}
2071
2072
2074{
2075 return m_currentNode ? m_currentNode : m_root; //m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
2076}
2077
2078
2080{
2081 SPRINGBACK_TAG sp;
2082 sp.m_node = aNode;
2083 sp.m_locked = true;
2084
2085 m_nodeStack.push_back(sp);
2086
2087 PNS_DBG( Dbg(), Message, wxString::Format( "addLockedSPNode node=%p stack=%d\n", sp.m_node, (int) m_nodeStack.size() ) );
2088
2089 return true;
2090}
2091
2092
2094{
2095 bool found = false;
2096
2097 auto iter = m_nodeStack.begin();
2098
2099 while( iter != m_nodeStack.end() )
2100 {
2101 if ( iter->m_node == aNode )
2102 {
2103 found = true;
2104 break;
2105 }
2106
2107 iter++;
2108 }
2109
2110 if( !found )
2111 return false;
2112
2113 auto start = iter;
2114
2115 aNode->KillChildren();
2116 m_nodeStack.erase( start, m_nodeStack.end() );
2117
2118 if( !m_nodeStack.empty() )
2119 m_currentNode = m_nodeStack.back().m_node;
2120 else
2122
2123 return true;
2124}
2125
2126
2128{
2129 if( m_nodeStack.empty() )
2130 return false;
2131
2132 while( !m_nodeStack.back().m_locked && m_nodeStack.size() > 1 )
2133 m_nodeStack.pop_back();
2134
2135 m_currentNode = m_nodeStack.back().m_node;
2136
2137 return m_nodeStack.back().m_locked;
2138}
2139
2140
2142{
2143 auto iter = m_nodeStack.begin();
2144
2145 while( iter != m_nodeStack.end() )
2146 {
2147 if ( iter->m_node == aNode )
2148 {
2149 iter->m_locked = false;
2150 break;
2151 }
2152
2153 iter++;
2154 }
2155}
2156
2157
2159{
2160 m_optFlagDisableMask = aMask;
2161}
2162
2163
2165{
2167}
2168
2169
2171{
2172 m_defaultPolicy = aPolicy;
2173}
2174
2175
2176void SHOVE::SetShovePolicy( const LINKED_ITEM* aItem, int aPolicy )
2177{
2178 auto rl = touchRootLine( aItem );
2179 rl->policy = aPolicy;
2180}
2181
2182void SHOVE::SetShovePolicy( const LINE& aLine, int aPolicy )
2183{
2184 auto rl = touchRootLine( aLine );
2185 rl->policy = aPolicy;
2186}
2187
2188
2190{
2191 m_headLines.clear();
2192}
2193
2194
2195void SHOVE::AddHeads( const LINE& aHead, int aPolicy )
2196{
2197 m_headLines.push_back( SHOVE::HEAD_LINE_ENTRY( aHead, aPolicy ) );
2198}
2199
2200
2201void SHOVE::AddHeads( VIA_HANDLE aHead, VECTOR2I aNewPos, int aPolicy )
2202{
2203 SHOVE::HEAD_LINE_ENTRY ent( aHead, aPolicy );
2204 ent.viaNewPos = aNewPos;
2205 ent.prevVia = aHead;
2206 ent.theVia = aHead;
2207 m_headLines.push_back( ent );
2208}
2209
2210void removeHead( NODE *aNode, LINE& head )
2211{
2212 for (auto lnk : head.Links() )
2213 {
2214 if( lnk->BelongsTo( aNode ) )
2215 aNode->Remove( lnk );
2216 }
2217}
2218
2220{
2221 auto iface = Router()->GetInterface();
2222
2223 for( auto& headEntry : m_headLines )
2224 {
2225 if( headEntry.newHead )
2226 {
2227 //nodeStats( Dbg(), m_currentNode, "pre-remove-new" );
2228 int n_lc = headEntry.newHead->LinkCount();
2229 removeHead(m_currentNode, *headEntry.newHead );
2230 //nodeStats( Dbg(), m_currentNode, "post-remove-new" );
2231
2232
2233 wxString msg = wxString::Format(
2234 "remove newhead [net %-20s]: sc %d lc %d\n",
2235 iface->GetNetName( headEntry.newHead->Net() ).c_str().AsChar(),
2236 headEntry.newHead->SegmentCount(), n_lc );
2237 PNS_DBG( Dbg(), Message, msg );
2238 }
2239 else if( headEntry.origHead )
2240 {
2241 wxString msg = wxString::Format(
2242 "remove orighead [net %-20s]: sc %d lc %d node %p depth %d\n",
2243 iface->GetNetName( headEntry.origHead->Net() ).c_str().AsChar(),
2244 headEntry.origHead->SegmentCount(), headEntry.origHead->LinkCount(),
2245 headEntry.origHead->OwningNode(), m_currentNode->Depth() );
2246 PNS_DBG( Dbg(), Message, msg );
2247
2248 removeHead( m_currentNode, *headEntry.origHead );
2249
2250 }
2251 }
2252}
2253
2254
2255void SHOVE::reconstructHeads( bool aShoveFailed )
2256{
2257 int i = 0;
2258 auto iface = Router()->GetInterface();
2259
2260 PNS_DBG( Dbg(), Message, wxString::Format("reconstructing %zu heads", m_headLines.size() ) );
2261
2262 for( auto& headEntry : m_headLines )
2263 {
2264 if( headEntry.origHead )
2265 {
2266 auto rootEntry = findRootLine( *headEntry.origHead );
2267
2268 PNS_DBG( Dbg(), Message, wxString::Format("orig LinkC=%d RE=%p", headEntry.origHead->LinkCount(), rootEntry ) );
2269
2270 assert( rootEntry );
2271 assert( rootEntry->rootLine );
2272
2273 if( rootEntry->newLine )
2274 {
2275 headEntry.newHead = rootEntry->newLine;
2276 headEntry.geometryModified = !rootEntry->newLine->CLine().CompareGeometry( rootEntry->rootLine->CLine() );
2277
2278 wxString msg = wxString::Format(
2279 "head %d/%d [net %-20s]: root %p, lc-root %d, lc-new %d\n", i, (int) m_headLines.size(),
2280 iface->GetNetName( rootEntry->rootLine->Net() ).c_str().AsChar(), rootEntry->rootLine, rootEntry->rootLine->LinkCount(), headEntry.newHead->LinkCount() );
2281 PNS_DBG( Dbg(), AddItem, rootEntry->rootLine, CYAN, 0, msg );
2282 PNS_DBG( Dbg(), Message, msg );
2283
2284 }
2285 else
2286 {
2287 wxString msg = wxString::Format(
2288 "head %d/%d [net %-20s]: unmodified, lc-orig %d\n", i, (int) m_headLines.size(),
2289 iface->GetNetName( headEntry.origHead->Net() ).c_str().AsChar(),
2290 headEntry.origHead->LinkCount() );
2291 PNS_DBG( Dbg(), Message, msg );
2292 }
2293
2294 i++;
2295 } else {
2296 auto rootEntry = findRootLine( headEntry.draggedVia );
2297
2298 if( rootEntry->newVia )
2299 {
2300 headEntry.geometryModified = true;
2301 headEntry.theVia = VIA_HANDLE( rootEntry->newVia->Pos(), rootEntry->newVia->Layers(), rootEntry->newVia->Net() );
2302 auto chk = m_currentNode->FindViaByHandle( *headEntry.theVia );
2303 wxString msg = wxString::Format( "[modif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2304
2305 PNS_DBG( Dbg(), Message, msg );
2306 assert( chk != nullptr );
2307 }
2308 else
2309 {
2310 headEntry.theVia = VIA_HANDLE( rootEntry->oldVia->Pos(), rootEntry->oldVia->Layers(), rootEntry->oldVia->Net() );
2311 auto chk = m_currentNode->FindViaByHandle( *headEntry.theVia );
2312 wxString msg = wxString::Format( "[unmodif] via orig %p chk %p\n", headEntry.draggedVia, chk );
2313 PNS_DBG( Dbg(), Message, msg );
2314 assert( chk != nullptr );
2315
2316 }
2317
2318
2319 }
2320
2321 m_headsModified |= headEntry.geometryModified;
2322 }
2323}
2324
2325
2326
2328{
2329 //COLLISION_SEARCH_CONTEXT ctx;
2330
2331 //ctx.options.m_differentNetsOnly = false;
2332 //ctx.options.m_kindMask = ITEM::SEGMENT_T; // fixme arcs
2333
2334 SHAPE_LINE_CHAIN orig( aOld->CLine() );
2335
2336 int vc_prev = orig.PointCount();
2337 orig.Simplify2();
2338 int vc_post = orig.PointCount();
2339
2340 *aNew = *aOld;
2341
2342 PNS_DBG( Dbg(), Message, wxString::Format( "**** PreshoveCleanup %d -> %d\n", vc_prev, vc_post ) );
2343
2344 if( vc_prev != vc_post )
2345 {
2346 aNew->ClearLinks();
2347 aNew->SetShape( orig );
2348 replaceLine( *aOld, *aNew );
2349 return true;
2350 }
2351
2352 return false;
2353}
2354
2355// new algo
2357{
2358 SHOVE_STATUS st = SH_OK;
2359
2360 m_multiLineMode = false;
2361 int currentHeadId = 0;
2362 int totalHeads = m_headLines.size();
2363
2364 m_headsModified = false;
2365 m_lineStack.clear();
2366 m_optimizerQueue.clear();
2367
2368 ITEM_SET headSet;
2369
2370 PNS_DBG( Dbg(), Message, wxString::Format("shove run (heads: %d, currentNode=%p, depth=%d)", (int) m_headLines.size(), m_currentNode, m_currentNode->Depth() ) );
2371
2372 for( auto& l : m_headLines )
2373 {
2374 if( l.theVia )
2375 {
2376 PNS_DBG( Dbg(), Message, wxString::Format("process head-via [%d %d] node=%p", l.theVia->pos.x, l.theVia->pos.y, m_currentNode ) );
2377 auto realVia = m_currentNode->FindViaByHandle( *l.theVia );
2378 assert( realVia != nullptr );
2379 headSet.Add( realVia->Clone() );
2380 }
2381 else
2382 {
2383 headSet.Add( *l.origHead->Clone() );
2384 }
2385 }
2386
2387 // Pop NODEs containing previous shoves which are no longer necessary
2388 NODE* parent = reduceSpringback( headSet );
2389 m_currentNode = parent->Branch();
2391
2392
2393
2394
2395
2396
2397 //nodeStats( Dbg(), m_currentNode, "right-after-branch" );
2398
2399 auto iface = Router()->GetInterface();
2400
2401 // for ( auto& hq : m_headLines )
2402 // if( hq.oldHead )
2403 // m_currentNode->Remove( *hq.oldHead );
2404
2405
2406 // Push the via to its new location
2407 for( auto& headLineEntry : m_headLines )
2408 {
2409 //if( rootEntry->line ) // head already processed in previous steps
2410 //{
2411 // PNS_DBG( Dbg(), Message, wxString::Format( "RL found" ) );
2412
2413 //continue;
2414 //}
2416
2417 if( headLineEntry.theVia )
2418 {
2419 VIA* viaToDrag = m_currentNode->FindViaByHandle( *headLineEntry.theVia );
2420
2421 if( !viaToDrag )
2422 {
2423 st = SH_INCOMPLETE;
2424 break;
2425 }
2426
2427 auto viaRoot = touchRootLine( viaToDrag );
2428 viaRoot->oldVia = viaToDrag;
2429 headLineEntry.draggedVia = viaToDrag;
2430
2431 st = pushOrShoveVia( viaToDrag, ( headLineEntry.viaNewPos - viaToDrag->Pos() ), 0, true );
2432
2433 if( st != SH_OK )
2434 break;
2435 }
2436 else
2437 {
2438 // Create a new NODE to store this version of the world
2439 assert( headLineEntry.origHead->LinkCount() == 0 );
2440 m_currentNode->Add( *headLineEntry.origHead );
2441
2442 //nodeStats( Dbg(), m_currentNode, "add-head" );
2443
2444
2445
2446 PNS_DBG( Dbg(), Message,
2447 wxString::Format( "touchRoot ohlc %d roots %d re=%p\n",
2448 headLineEntry.origHead->LinkCount(),
2449 (int) m_rootLineHistory.size(),
2450 findRootLine( *headLineEntry.origHead ) ) );
2451
2452
2453 LINE head( *headLineEntry.origHead );
2454
2455 // empty head? nothing to shove...
2456 if( !head.SegmentCount() && !head.EndsWithVia() )
2457 {
2458 st = SH_INCOMPLETE;
2459 break;
2460 }
2461
2462 currentHeadId++;
2463
2464 m_currentNode->LockJoint( head.CPoint( 0 ), &head, true );
2465
2466 if( !head.EndsWithVia() )
2467 m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
2468
2469 SetShovePolicy( head, headLineEntry.policy );
2470
2471 //head.Mark( MK_HEAD );
2472 head.SetRank( 100000 ); //- 100 * currentHeadId );
2473
2474 if( head.EndsWithVia() )
2475 {
2476 auto headVia = Clone( head.Via() );
2477 headVia->SetRank( 100000 ); // - 100 * currentHeadId );
2478 headLineEntry.origHead->LinkVia( headVia.get() );
2479 head.LinkVia( headVia.get() );
2480 m_currentNode->Add( std::move( headVia ) );
2481 }
2482
2483 auto headRoot = touchRootLine( *headLineEntry.origHead );
2484 headRoot->isHead = true;
2485 headRoot->rootLine = new PNS::LINE( *headLineEntry.origHead );
2486 headRoot->policy = headLineEntry.policy;
2487
2488
2489 PNS_DBG( Dbg(), Message,
2490 wxString::Format( "headLC %d, rlLC %d oolc %d eov %d\n", head.LinkCount(),
2491 headRoot->rootLine->LinkCount(),
2492 headLineEntry.origHead->LinkCount(),
2493 head.EndsWithVia()?1:0 ) );
2494
2495 //auto rootEntry = findRootLine( &head );
2496
2497 PNS_DBG( Dbg(), Message,
2498 wxString::Format( "Shove heads %d/%d h-lc=%d net=%s Line=%d Policy=%s",
2499 currentHeadId, totalHeads, head.LinkCount(),
2500 iface->GetNetName( head.Net() ), headRoot->newLine ? 1 : 0,
2501 headRoot ? formatPolicy( headRoot->policy )
2502 : wxString( wxT( "default[ne]" ) ) ) );
2503
2504
2505 // nodeStats( Dbg(), m_currentNode, "pre-push-stack" );
2506
2507 if( !pushLineStack( head ) )
2508 {
2509 st = SH_INCOMPLETE;
2510 break;
2511 }
2512 }
2513
2514 st = shoveMainLoop();
2515
2516 //nodeStats( Dbg(), m_currentNode, "post-main-loop" );
2517
2518 if( st != SH_OK )
2519 break;
2520 };
2521
2522 PNS_DBG( Dbg(), Message,
2523 wxString::Format( "Shove status : %s after %d iterations, heads: %d",
2524 ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE" ),
2525 m_iter, (int) m_headLines.size() ) );
2526 if( st == SH_OK )
2527 {
2528 //nodeStats( Dbg(), m_currentNode, "pre-opt" );
2529
2531
2532 reconstructHeads( false );
2533 removeHeads();
2534
2535 // this must be called afrter reconstructHeads as it requires up-to-date via handles
2537 }
2538 else
2539 {
2540 //reconstructHeads( true );
2541
2542 for( auto& headEntry : m_headLines )
2543 {
2544 if( headEntry.prevVia )
2545 {
2546
2547 PNS_DBG( Dbg(), Message,
2548 wxString::Format( "Fail-restore via mod [%d, %d] orig [%d, %d]",
2549 headEntry.theVia->pos.x,
2550 headEntry.theVia->pos.y,
2551 headEntry.prevVia->pos.x,
2552 headEntry.prevVia->pos.y ) );
2553
2554 headEntry.theVia = headEntry.prevVia;
2555 headEntry.geometryModified = true;
2556 m_headsModified = true;
2557 }
2558 }
2559
2561
2562 delete m_currentNode;
2563 m_currentNode = parent;
2564 }
2565
2566 return st;
2567}
2568
2570 {
2576 SHP_DONT_OPTIMIZE = 0x10
2578
2579const wxString SHOVE::formatPolicy( int aPolicy )
2580{
2581 if( aPolicy == SHP_DEFAULT )
2582 return wxString::Format( "default [%s]", m_defaultPolicy );
2583
2584 wxString rv;
2585
2586 if( aPolicy & SHP_SHOVE )
2587 rv.Append( "shove ");
2588 if( aPolicy & SHP_WALK_FORWARD )
2589 rv.Append( "walk-forward ");
2590 if( aPolicy & SHP_WALK_FORWARD )
2591 rv.Append( "walk-back ");
2592 if( aPolicy & SHP_IGNORE )
2593 rv.Append( "ignore ");
2594 if( aPolicy & SHP_IGNORE )
2595 rv.Append( "dont-optimize ");
2596
2597 return rv;
2598}
2599
2600bool SHOVE::HeadsModified( int aIndex ) const
2601{
2602 if( aIndex < 0 )
2603 return m_headsModified;
2604 else
2605 return m_headLines[ aIndex ].geometryModified;
2606}
2607
2608const PNS::LINE SHOVE::GetModifiedHead( int aIndex ) const
2609{
2610 return *m_headLines[ aIndex ].newHead;
2611}
2612
2613const VIA_HANDLE SHOVE::GetModifiedHeadVia( int aIndex ) const
2614{
2615 return *m_headLines[ aIndex ].theVia;
2616}
2617
2618
2619
2620}
2621
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:108
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:926
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition: box2.h:990
CORNER_MODE
Corner modes.
Definition: direction45.h:67
@ ROUNDED_45
H/V/45 with filleted corners.
Definition: direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition: direction45.h:68
virtual wxString GetItemDescription(UNITS_PROVIDER *aUnitsProvider, bool aFull) const
Return a user-visible description string of this item.
Definition: eda_item.cpp:111
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
int Width() const override
Definition: pns_arc.h:88
virtual void SetIteration(int iter)
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:33
Base class for PNS router board items.
Definition: pns_item.h:98
BOARD_ITEM * Parent() const
Definition: pns_item.h:190
virtual const std::string Format() const
Definition: pns_item.cpp:335
virtual int Rank() const
Definition: pns_item.h:254
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition: pns_item.h:230
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:200
virtual NET_HANDLE Net() const
Definition: pns_item.h:198
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:171
std::set< int > RelevantShapeLayers(const ITEM *aOther) const
Returns the set of layers on which either this or the other item can have a unique shape.
Definition: pns_item.cpp:94
virtual int Layer() const
Definition: pns_item.h:204
PnsKind
< Supported item types
Definition: pns_item.h:102
@ SEGMENT_T
Definition: pns_item.h:107
@ LINKED_ITEM_MASK_T
Definition: pns_item.h:113
bool Collide(const ITEM *aHead, const NODE *aNode, int aLayer, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:302
virtual const NODE * OwningNode() const
Definition: pns_item.cpp:351
bool OfKind(int aKindMask) const
Definition: pns_item.h:179
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:209
virtual HOLE * Hole() const
Definition: pns_item.h:292
virtual bool HasHole() const
Definition: pns_item.h:291
bool IsLocked() const
Definition: pns_item.h:266
virtual int Marker() const
Definition: pns_item.h:251
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:303
VIA * Via() const
Definition: pns_joint.h:275
const ITEM_SET & CLinks() const
Definition: pns_joint.h:308
bool IsLocked() const
Definition: pns_joint.h:357
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:62
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:146
bool HasLoops() const
Definition: pns_line.cpp:1186
bool HasLockedSegments() const
Definition: pns_line.cpp:1296
int Rank() const override
Definition: pns_line.cpp:1117
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:127
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:123
void LinkVia(VIA *aVia)
Definition: pns_line.cpp:1095
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
void RemoveVia()
Definition: pns_line.cpp:1315
void SetRank(int aRank) override
Definition: pns_line.cpp:1107
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
const SHAPE * Shape(int aLayer) const override
Modifiable accessor to the underlying shape.
Definition: pns_line.h:134
virtual int Marker() const override
Definition: pns_line.cpp:142
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1082
VIA & Via()
Definition: pns_line.h:198
int SegmentCount() const
Definition: pns_line.h:140
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:133
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:190
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:147
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:115
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:157
UNIQ_ID Uid() const
Keep the router "world" - i.e.
Definition: pns_node.h:231
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:143
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:242
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:129
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:869
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1446
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:410
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1245
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:241
int Depth() const
Definition: pns_node.h:281
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:665
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:286
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1272
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:275
VIA * FindViaByHandle(const VIA_HANDLE &handle) const
Definition: pns_node.cpp:1729
void KillChildren()
Definition: pns_node.cpp:1526
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1561
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:909
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:1047
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 wxString GetNetName(PNS::NET_HANDLE aNet) const =0
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:223
TIME_LIMIT ShoveTimeLimit() const
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
DIRECTION_45::CORNER_MODE GetCornerMode() const
const SEG & Seg() const
Definition: pns_segment.h:90
int Width() const override
Definition: pns_segment.h:85
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
Definition: pns_line.cpp:569
void SetSpringbackDoNotTouchNode(const NODE *aNode)
Definition: pns_shove.cpp:2164
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1584
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1828
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:110
void reconstructHeads(bool aShoveFailed)
Definition: pns_shove.cpp:2255
int m_iter
Definition: pns_shove.h:241
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:112
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aNextRank, bool aDontUnwindStack=false)
Definition: pns_shove.cpp:1019
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:1246
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:249
std::vector< LINE > m_lineStack
Definition: pns_shove.h:230
void popLineStack()
Definition: pns_shove.cpp:1491
ROOT_LINE_ENTRY * findRootLine(const LINE &aLine)
Definition: pns_shove.cpp:1890
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:229
@ SHP_DONT_OPTIMIZE
Definition: pns_shove.h:65
@ SHP_IGNORE
Definition: pns_shove.h:64
@ SHP_DEFAULT
Definition: pns_shove.h:60
@ SHP_WALK_FORWARD
Definition: pns_shove.h:62
bool shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls, bool aPermitAdjustingEndpoints=false)
Definition: pns_shove.cpp:305
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:667
NODE * m_currentNode
Definition: pns_shove.h:237
SHOVE_STATUS Run()
Definition: pns_shove.cpp:2356
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr, bool aPreCleanup=false)
Definition: pns_shove.cpp:215
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:238
int m_forceClearance
Definition: pns_shove.h:243
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:607
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:190
void DisablePostShoveOptimizations(int aMask)
Definition: pns_shove.cpp:2158
bool RewindSpringbackTo(NODE *aNode)
Definition: pns_shove.cpp:2093
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1437
@ 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:1874
bool RewindToLastLockedNode()
Definition: pns_shove.cpp:2127
std::deque< HEAD_LINE_ENTRY > m_headLines
Definition: pns_shove.h:232
int m_defaultPolicy
Definition: pns_shove.h:248
const wxString formatPolicy(int aPolicy)
Definition: pns_shove.cpp:2579
bool ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:504
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo, int aNextRank)
Definition: pns_shove.cpp:1153
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:183
int m_restrictSpringbackTagId
Definition: pns_shove.h:239
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1961
ROOT_LINE_ENTRY * touchRootLine(const LINE &aLine)
Definition: pns_shove.cpp:1914
const PNS::LINE GetModifiedHead(int aIndex) const
Definition: pns_shove.cpp:2608
bool HeadsModified(int aIndex=-1) const
Definition: pns_shove.cpp:2600
void UnlockSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:2141
NODE * m_root
Definition: pns_shove.h:236
NODE * reduceSpringback(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:900
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:2079
void SetDefaultShovePolicy(int aPolicy)
Definition: pns_shove.cpp:2170
void AddHeads(const LINE &aHead, int aPolicy=SHP_DEFAULT)
Definition: pns_shove.cpp:2195
void SetShovePolicy(const LINKED_ITEM *aItem, int aPolicy)
Definition: pns_shove.cpp:2176
void unwindLineStack(const LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1367
bool preShoveCleanup(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:2327
NODE * CurrentNode()
Definition: pns_shove.cpp:2073
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:166
bool m_multiLineMode
Definition: pns_shove.h:244
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:231
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:752
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:961
int m_optFlagDisableMask
Definition: pns_shove.h:246
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle, int aNextRank)
Definition: pns_shove.cpp:716
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
Definition: pns_shove.cpp:1499
bool pruneLineFromOptimizerQueue(const LINE &aLine)
Definition: pns_shove.cpp:1463
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:49
bool shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:258
VIA * m_draggedVia
Definition: pns_shove.h:240
bool m_headsModified
Definition: pns_shove.h:242
const NODE * m_springbackDoNotTouchNode
Definition: pns_shove.h:238
void ClearHeads()
Definition: pns_shove.cpp:2189
std::unordered_map< LINKED_ITEM::UNIQ_ID, ROOT_LINE_ENTRY * > m_rootLineHistory
Definition: pns_shove.h:234
void pruneRootLines(NODE *aRemovedNode)
Definition: pns_shove.cpp:877
const VIA_HANDLE GetModifiedHeadVia(int aIndex) const
Definition: pns_shove.cpp:2613
ROOT_LINE_ENTRY * replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, bool aAllowRedundantSegments=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:80
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:113
void removeHeads()
Definition: pns_shove.cpp:2219
bool Expired() const
Definition: time_limit.cpp:39
const CLUSTER AssembleCluster(ITEM *aStart, int aLayer, double aAreaExpansionLimit=0.0, NET_HANDLE aExcludedNet=nullptr)
int Diameter(int aLayer) const
Definition: pns_via.h:191
void SetDiameter(int aLayer, int aDiameter)
Definition: pns_via.h:198
const VECTOR2I & Pos() const
Definition: pns_via.h:175
const SHAPE * Shape(int aLayer) const override
Return the geometrical shape of the item.
Definition: pns_via.h:229
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:217
VIA * Clone() const override
Return a deep copy of the item.
Definition: pns_via.cpp:235
void SetIterationLimit(const int aIterLimit)
void RestrictToCluster(bool aEnabled, const TOPOLOGY::CLUSTER &aCluster)
void SetSolidsOnly(bool aSolidsOnly)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies)
int Start() const
Definition: pns_layerset.h:86
int End() const
Definition: pns_layerset.h:91
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:276
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Clear()
Remove all points from the line chain.
SHAPE_LINE_CHAIN & Simplify2(bool aRemoveColinear=true)
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
const std::string Format(bool aCplusPlus=true) const override
bool IsArcSegment(size_t aSegment) const
long long int Length() const
Return length of the line chain in Euclidean metric.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:181
constexpr extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition: vector2d.h:73
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:385
@ LIGHTGREEN
Definition: color4d.h:63
@ WHITE
Definition: color4d.h:48
@ BLUE
Definition: color4d.h:56
@ LIGHTGRAY
Definition: color4d.h:47
@ LIGHTYELLOW
Definition: color4d.h:49
@ GREEN
Definition: color4d.h:57
@ CYAN
Definition: color4d.h:58
@ YELLOW
Definition: color4d.h:67
@ LIGHTRED
Definition: color4d.h:65
@ RED
Definition: color4d.h:59
Push and Shove diff pair dimensions (gap) settings dialog.
SHOVE_POLICY
Definition: pns_shove.cpp:2570
@ SHP_DEFAULT
Definition: pns_shove.cpp:2571
@ SHP_WALK_BACK
Definition: pns_shove.cpp:2574
@ SHP_IGNORE
Definition: pns_shove.cpp:2575
@ SHP_WALK_FORWARD
Definition: pns_shove.cpp:2573
@ SHP_SHOVE
Definition: pns_shove.cpp:2572
@ SHP_DONT_OPTIMIZE
Definition: pns_shove.cpp:2576
@ MK_HEAD
Definition: pns_item.h:43
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:368
void removeHead(NODE *aNode, LINE &head)
Definition: pns_shove.cpp:2210
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:328
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
VECTOR2I::extended_type ecoord
Definition: pns_shove.cpp:45
std::vector< FAB_LAYER_COLOR > dummy
std::function< bool(const ITEM *)> m_filter
Definition: pns_node.h:119
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:87
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition: pns_node.h:94
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:89
Definition: pns_shove.h:130
std::optional< VIA_HANDLE > theVia
Definition: pns_shove.h:145
std::optional< VIA_HANDLE > prevVia
Definition: pns_shove.h:144
VECTOR2I viaNewPos
Definition: pns_shove.h:147
Definition: pns_shove.h:116
int policy
Definition: pns_shove.h:125
std::optional< LINE > newLine
Definition: pns_shove.h:124
VIA * newVia
Definition: pns_shove.h:123
std::vector< VIA_HANDLE > m_draggedVias
Definition: pns_shove.h:163
std::set< ITEM * > m_items
Definition: pns_topology.h:46
VECTOR2I pos
Definition: pns_via.h:53
NET_HANDLE net
Definition: pns_via.h:55
PNS_LAYER_RANGE layers
Definition: pns_via.h:54
LINE lines[MaxWalkPolicies]
STATUS status[MaxWalkPolicies]
VECTOR2I v2(1, 0)
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695