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