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