1 /*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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
25 #include "pns_line.h"
26 #include "pns_node.h"
27 #include "pns_walkaround.h"
28 #include "pns_shove.h"
29 #include "pns_solid.h"
30 #include "pns_optimizer.h"
31 #include "pns_via.h"
32 #include "pns_utils.h"
33 #include "pns_router.h"
34 #include "pns_topology.h"
35
36 #include "time_limit.h"
37
38 namespace PNS {
39
replaceItems(ITEM * aOld,std::unique_ptr<ITEM> aNew)40 void SHOVE::replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew )
41 {
42 OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
43
44 if( changed_area )
45 {
46 m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
47 }
48
49 m_currentNode->Replace( aOld, std::move( aNew ) );
50 }
51
replaceLine(LINE & aOld,LINE & aNew)52 void SHOVE::replaceLine( LINE& aOld, LINE& aNew )
53 {
54 OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
55
56 if( changed_area )
57 {
58 m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
59 }
60
61 m_currentNode->Replace( aOld, aNew );
62 }
63
getClearance(const ITEM * aA,const ITEM * aB) const64 int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
65 {
66 if( m_forceClearance >= 0 )
67 return m_forceClearance;
68
69 return m_currentNode->GetClearance( aA, aB );
70 }
71
72
sanityCheck(LINE * aOld,LINE * aNew)73 void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
74 {
75 assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
76 assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
77 }
78
79
SHOVE(NODE * aWorld,ROUTER * aRouter)80 SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
81 ALGO_BASE( aRouter )
82 {
83 m_forceClearance = -1;
84 m_root = aWorld;
85 m_currentNode = aWorld;
86
87 // Initialize other temporary variables:
88 m_draggedVia = NULL;
89 m_iter = 0;
90 m_multiLineMode = false;
91 }
92
93
~SHOVE()94 SHOVE::~SHOVE()
95 {
96 }
97
98
assembleLine(const SEGMENT * aSeg,int * aIndex)99 LINE SHOVE::assembleLine( const SEGMENT* aSeg, int* aIndex )
100 {
101 return m_currentNode->AssembleLine( const_cast<SEGMENT*>( aSeg ), aIndex, true );
102 }
103
104 // A dumb function that checks if the shoved line is shoved the right way, e.g.
105 // visually "outwards" of the line/via applying pressure on it. Unfortunately there's no
106 // mathematical concept of orientation of an open curve, so we use some primitive heuristics:
107 // if the shoved line wraps around the start of the "pusher", it's likely shoved in wrong direction.
checkBumpDirection(const LINE & aCurrent,const LINE & aShoved) const108 bool SHOVE::checkBumpDirection( const LINE& aCurrent, const LINE& aShoved ) const
109 {
110 const SEG& ss = aCurrent.CSegment( 0 );
111
112 int dist = getClearance( &aCurrent, &aShoved ) + PNS_HULL_MARGIN;
113
114 dist += aCurrent.Width() / 2;
115 dist += aShoved.Width() / 2;
116
117 const VECTOR2I ps = ss.A - ( ss.B - ss.A ).Resize( dist );
118
119 return !aShoved.CLine().PointOnEdge( ps );
120 }
121
122
walkaroundLoneVia(LINE & aCurrent,LINE & aObstacle,LINE & aShoved)123 SHOVE::SHOVE_STATUS SHOVE::walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle, LINE& aShoved )
124 {
125 int clearance = getClearance( &aCurrent, &aObstacle );
126 const SHAPE_LINE_CHAIN hull = aCurrent.Via().Hull( clearance, aObstacle.Width() );
127 SHAPE_LINE_CHAIN path_cw;
128 SHAPE_LINE_CHAIN path_ccw;
129 VECTOR2I dummy;
130
131 if( ! aObstacle.Walkaround( hull, path_cw, true ) )
132 return SH_INCOMPLETE;
133
134 if( ! aObstacle.Walkaround( hull, path_ccw, false ) )
135 return SH_INCOMPLETE;
136
137 const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
138
139 if( shortest.PointCount() < 2 )
140 return SH_INCOMPLETE;
141
142 if( aObstacle.CPoint( -1 ) != shortest.CPoint( -1 ) )
143 return SH_INCOMPLETE;
144
145 if( aObstacle.CPoint( 0 ) != shortest.CPoint( 0 ) )
146 return SH_INCOMPLETE;
147
148 aShoved.SetShape( shortest );
149
150 if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
151 return SH_INCOMPLETE;
152
153 return SH_OK;
154 }
155
156
processHullSet(LINE & aCurrent,LINE & aObstacle,LINE & aShoved,const HULL_SET & aHulls)157 SHOVE::SHOVE_STATUS SHOVE::processHullSet( LINE& aCurrent, LINE& aObstacle,
158 LINE& aShoved, const HULL_SET& aHulls )
159 {
160 const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
161
162 int attempt;
163
164 for( attempt = 0; attempt < 4; attempt++ )
165 {
166 bool invertTraversal = ( attempt >= 2 );
167 bool clockwise = attempt % 2;
168 int vFirst = -1, vLast = -1;
169
170 SHAPE_LINE_CHAIN path;
171 LINE l( aObstacle );
172
173 for( int i = 0; i < (int) aHulls.size(); i++ )
174 {
175 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
176
177 if( ! l.Walkaround( hull, path, clockwise ) )
178 return SH_INCOMPLETE;
179
180 path.Simplify();
181 l.SetShape( path );
182 }
183
184 for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
185 {
186 if( path.CPoint( i ) != obs.CPoint( i ) )
187 {
188 vFirst = i;
189 break;
190 }
191 }
192
193 int k = obs.PointCount() - 1;
194 for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
195 {
196 if( path.CPoint( i ) != obs.CPoint( k ) )
197 {
198 vLast = i;
199 break;
200 }
201 }
202
203 if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
204 {
205 wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
206 continue;
207 }
208
209 if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
210 {
211 wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
212 continue;
213 }
214
215 if( !checkBumpDirection( aCurrent, l ) )
216 {
217 wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
218 aShoved.SetShape( l.CLine() );
219
220 continue;
221 }
222
223 if( path.SelfIntersecting() )
224 {
225 wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
226 continue;
227 }
228
229 bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
230
231 if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
232 {
233 JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
234
235 for( ITEM* item : jtStart->LinkList() )
236 {
237 if( m_currentNode->CheckColliding( item, &l ) )
238 colliding = true;
239 }
240 }
241
242 if( colliding )
243 {
244 wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
245 continue;
246 }
247
248 aShoved.SetShape( l.CLine() );
249
250 return SH_OK;
251 }
252
253 return SH_INCOMPLETE;
254 }
255
256
ProcessSingleLine(LINE & aCurrent,LINE & aObstacle,LINE & aShoved)257 SHOVE::SHOVE_STATUS SHOVE::ProcessSingleLine( LINE& aCurrent, LINE& aObstacle, LINE& aShoved )
258 {
259 aShoved.ClearSegmentLinks();
260
261 bool obstacleIsHead = false;
262
263 for( SEGMENT* s : aObstacle.LinkedSegments() )
264 {
265 if( s->Marker() & MK_HEAD )
266 {
267 obstacleIsHead = true;
268 break;
269 }
270 }
271
272 SHOVE_STATUS rv;
273
274 bool viaOnEnd = aCurrent.EndsWithVia();
275
276 if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
277 {
278 rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
279 }
280 else
281 {
282 int w = aObstacle.Width();
283 int n_segs = aCurrent.SegmentCount();
284
285 int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
286
287 HULL_SET hulls;
288
289 hulls.reserve( n_segs + 1 );
290
291 for( int i = 0; i < n_segs; i++ )
292 {
293 SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
294 SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w );
295
296 hulls.push_back( hull );
297 }
298
299 if( viaOnEnd )
300 hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
301
302 rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
303 }
304
305 if( obstacleIsHead )
306 aShoved.Mark( aShoved.Marker() | MK_HEAD );
307
308 return rv;
309 }
310
311
onCollidingSegment(LINE & aCurrent,SEGMENT * aObstacleSeg)312 SHOVE::SHOVE_STATUS SHOVE::onCollidingSegment( LINE& aCurrent, SEGMENT* aObstacleSeg )
313 {
314 int segIndex;
315 LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
316 LINE shovedLine( obstacleLine );
317 SEGMENT tmp( *aObstacleSeg );
318
319 if( obstacleLine.HasLockedSegments() )
320 return SH_TRY_WALK;
321
322 SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
323
324 const double extensionWalkThreshold = 1.0;
325
326 double obsLen = obstacleLine.CLine().Length();
327 double shovedLen = shovedLine.CLine().Length();
328 double extensionFactor = 0.0;
329
330 if( obsLen != 0.0f )
331 extensionFactor = shovedLen / obsLen - 1.0;
332
333 if( extensionFactor > extensionWalkThreshold )
334 return SH_TRY_WALK;
335
336 assert( obstacleLine.LayersOverlap( &shovedLine ) );
337
338 #ifdef DEBUG
339 m_logger.NewGroup( "on-colliding-segment", m_iter );
340 m_logger.Log( &tmp, 0, "obstacle-segment" );
341 m_logger.Log( &aCurrent, 1, "current-line" );
342 m_logger.Log( &obstacleLine, 2, "obstacle-line" );
343 m_logger.Log( &shovedLine, 3, "shoved-line" );
344 #endif
345
346 if( rv == SH_OK )
347 {
348 if( shovedLine.Marker() & MK_HEAD )
349 {
350 if( m_multiLineMode )
351 return SH_INCOMPLETE;
352
353 m_newHead = shovedLine;
354 }
355
356 int rank = aCurrent.Rank();
357 shovedLine.SetRank( rank - 1 );
358
359 sanityCheck( &obstacleLine, &shovedLine );
360 replaceLine( obstacleLine, shovedLine );
361
362 if( !pushLine( shovedLine ) )
363 rv = SH_INCOMPLETE;
364 }
365
366 return rv;
367 }
368
369
onCollidingLine(LINE & aCurrent,LINE & aObstacle)370 SHOVE::SHOVE_STATUS SHOVE::onCollidingLine( LINE& aCurrent, LINE& aObstacle )
371 {
372 LINE shovedLine( aObstacle );
373
374 SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
375
376 #ifdef DEBUG
377 m_logger.NewGroup( "on-colliding-line", m_iter );
378 m_logger.Log( &aObstacle, 0, "obstacle-line" );
379 m_logger.Log( &aCurrent, 1, "current-line" );
380 m_logger.Log( &shovedLine, 3, "shoved-line" );
381 #endif
382
383 if( rv == SH_OK )
384 {
385 if( shovedLine.Marker() & MK_HEAD )
386 {
387 if( m_multiLineMode )
388 return SH_INCOMPLETE;
389
390 m_newHead = shovedLine;
391 }
392
393 sanityCheck( &aObstacle, &shovedLine );
394 replaceLine( aObstacle, shovedLine );
395
396 int rank = aObstacle.Rank();
397 shovedLine.SetRank( rank - 1 );
398
399
400 if( !pushLine( shovedLine ) )
401 {
402 rv = SH_INCOMPLETE;
403 }
404 }
405
406 return rv;
407 }
408
onCollidingSolid(LINE & aCurrent,ITEM * aObstacle)409 SHOVE::SHOVE_STATUS SHOVE::onCollidingSolid( LINE& aCurrent, ITEM* aObstacle )
410 {
411 WALKAROUND walkaround( m_currentNode, Router() );
412 LINE walkaroundLine( aCurrent );
413
414 if( aCurrent.EndsWithVia() )
415 {
416 VIA vh = aCurrent.Via();
417 VIA* via = NULL;
418 JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
419
420 if( !jtStart )
421 return SH_INCOMPLETE;
422
423 for( ITEM* item : jtStart->LinkList() )
424 {
425 if( item->OfKind( ITEM::VIA_T ) )
426 {
427 via = (VIA*) item;
428 break;
429 }
430 }
431
432 if( via && m_currentNode->CheckColliding( via, aObstacle ) )
433 return onCollidingVia( aObstacle, via );
434 }
435
436 TOPOLOGY topo( m_currentNode );
437
438 std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
439
440 #ifdef DEBUG
441 m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
442 for( ITEM* item : cluster )
443 {
444 m_logger.Log( item, 0, "cluster-entry" );
445 }
446 #endif
447
448 walkaround.SetSolidsOnly( false );
449 walkaround.RestrictToSet( true, cluster );
450 walkaround.SetIterationLimit( 16 ); // fixme: make configurable
451
452 int currentRank = aCurrent.Rank();
453 int nextRank;
454
455 bool success = false;
456
457 for( int attempt = 0; attempt < 2; attempt++ )
458 {
459 if( attempt == 1 || Settings().JumpOverObstacles() )
460 {
461
462 nextRank = currentRank - 1;
463 walkaround.SetSingleDirection( true );
464 }
465 else
466 {
467 nextRank = currentRank + 10000;
468 walkaround.SetSingleDirection( false );
469 }
470
471
472 WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
473
474 if( status != WALKAROUND::DONE )
475 continue;
476
477 walkaroundLine.ClearSegmentLinks();
478 walkaroundLine.Unmark();
479 walkaroundLine.Line().Simplify();
480
481 if( walkaroundLine.HasLoops() )
482 continue;
483
484 if( aCurrent.Marker() & MK_HEAD )
485 {
486 walkaroundLine.Mark( MK_HEAD );
487
488 if( m_multiLineMode )
489 continue;
490
491 m_newHead = walkaroundLine;
492 }
493
494 sanityCheck( &aCurrent, &walkaroundLine );
495
496 if( !m_lineStack.empty() )
497 {
498 LINE lastLine = m_lineStack.front();
499
500 if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
501 {
502 LINE dummy( lastLine );
503
504 if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
505 {
506 success = true;
507 break;
508 }
509 } else {
510 success = true;
511 break;
512 }
513 }
514 }
515
516 if(!success)
517 return SH_INCOMPLETE;
518
519 replaceLine( aCurrent, walkaroundLine );
520 walkaroundLine.SetRank( nextRank );
521
522 #ifdef DEBUG
523 m_logger.NewGroup( "on-colliding-solid", m_iter );
524 m_logger.Log( aObstacle, 0, "obstacle-solid" );
525 m_logger.Log( &aCurrent, 1, "current-line" );
526 m_logger.Log( &walkaroundLine, 3, "walk-line" );
527 #endif
528
529 popLine();
530
531 if( !pushLine( walkaroundLine ) )
532 return SH_INCOMPLETE;
533
534 return SH_OK;
535 }
536
537
reduceSpringback(const ITEM_SET & aHeadSet)538 bool SHOVE::reduceSpringback( const ITEM_SET& aHeadSet )
539 {
540 bool rv = false;
541
542 while( !m_nodeStack.empty() )
543 {
544 SPRINGBACK_TAG spTag = m_nodeStack.back();
545
546 if( !spTag.m_node->CheckColliding( aHeadSet ) )
547 {
548 rv = true;
549
550 delete spTag.m_node;
551 m_nodeStack.pop_back();
552 }
553 else
554 break;
555 }
556
557 return rv;
558 }
559
560
pushSpringback(NODE * aNode,const ITEM_SET & aHeadItems,const COST_ESTIMATOR & aCost,const OPT_BOX2I & aAffectedArea)561 bool SHOVE::pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
562 const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea )
563 {
564 SPRINGBACK_TAG st;
565 OPT_BOX2I prev_area;
566
567 if( !m_nodeStack.empty() )
568 prev_area = m_nodeStack.back().m_affectedArea;
569
570 st.m_node = aNode;
571 st.m_cost = aCost;
572 st.m_headItems = aHeadItems;
573
574 if( aAffectedArea )
575 {
576 if( prev_area )
577 st.m_affectedArea = prev_area->Merge( *aAffectedArea );
578 else
579 st.m_affectedArea = aAffectedArea;
580 } else
581 st.m_affectedArea = prev_area;
582
583 m_nodeStack.push_back( st );
584
585 return true;
586 }
587
588
pushVia(VIA * aVia,const VECTOR2I & aForce,int aCurrentRank,bool aDryRun)589 SHOVE::SHOVE_STATUS SHOVE::pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun )
590 {
591 LINE_PAIR_VEC draggedLines;
592 VECTOR2I p0( aVia->Pos() );
593 JOINT* jt = m_currentNode->FindJoint( p0, aVia );
594 VECTOR2I p0_pushed( p0 + aForce );
595
596 if( !jt )
597 {
598 wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
599 return SH_INCOMPLETE;
600 }
601
602 if( aVia->IsLocked() )
603 return SH_TRY_WALK;
604
605 if( jt->IsStitchingVia() )
606 return SH_TRY_WALK;
607
608 if( jt->IsLocked() )
609 return SH_INCOMPLETE;
610
611 // nothing to push...
612 if ( aForce.x == 0 && aForce.y == 0 )
613 return SH_OK;
614
615 while( aForce.x != 0 || aForce.y != 0 )
616 {
617 JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
618
619 if( !jt_next )
620 break;
621
622 p0_pushed += aForce.Resize( 2 ); // make sure pushed via does not overlap with any existing joint
623 }
624
625 std::unique_ptr< VIA > pushedVia = Clone( *aVia );
626 pushedVia->SetPos( p0_pushed );
627 pushedVia->Mark( aVia->Marker() );
628
629 for( ITEM* item : jt->LinkList() )
630 {
631 if( SEGMENT* seg = dynamic_cast<SEGMENT*>( item ) )
632 {
633 LINE_PAIR lp;
634 int segIndex;
635
636 lp.first = assembleLine( seg, &segIndex );
637
638 if( lp.first.HasLockedSegments() )
639 return SH_TRY_WALK;
640
641 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
642
643 if( segIndex == 0 )
644 lp.first.Reverse();
645
646 lp.second = lp.first;
647 lp.second.ClearSegmentLinks();
648 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
649 lp.second.AppendVia( *pushedVia );
650 draggedLines.push_back( lp );
651
652 if( aVia->Marker() & MK_HEAD )
653 m_draggedViaHeadSet.Add( lp.second );
654 }
655 }
656
657 m_draggedViaHeadSet.Add( pushedVia.get() );
658
659 if( aDryRun )
660 return SH_OK;
661
662 #ifdef DEBUG
663 m_logger.Log( aVia, 0, "obstacle-via" );
664 #endif
665
666 pushedVia->SetRank( aCurrentRank - 1 );
667
668 #ifdef DEBUG
669 m_logger.Log( pushedVia.get(), 1, "pushed-via" );
670 #endif
671
672 if( aVia->Marker() & MK_HEAD )
673 {
674 m_draggedVia = pushedVia.get();
675 m_draggedViaHeadSet.Clear();
676 }
677
678 replaceItems( aVia, std::move( pushedVia ) );
679
680 for( LINE_PAIR lp : draggedLines )
681 {
682 if( lp.first.Marker() & MK_HEAD )
683 {
684 lp.second.Mark( MK_HEAD );
685
686 if( m_multiLineMode )
687 return SH_INCOMPLETE;
688
689 m_newHead = lp.second;
690 }
691
692 unwindStack( &lp.first );
693
694 if( lp.second.SegmentCount() )
695 {
696 replaceLine( lp.first, lp.second );
697 lp.second.SetRank( aCurrentRank - 1 );
698
699 if( !pushLine( lp.second, true ) )
700 return SH_INCOMPLETE;
701 }
702 else
703 {
704 m_currentNode->Remove( lp.first );
705 }
706
707 #ifdef DEBUG
708 m_logger.Log( &lp.first, 2, "fan-pre" );
709 m_logger.Log( &lp.second, 3, "fan-post" );
710 #endif
711 }
712
713 return SH_OK;
714 }
715
716
onCollidingVia(ITEM * aCurrent,VIA * aObstacleVia)717 SHOVE::SHOVE_STATUS SHOVE::onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia )
718 {
719 int clearance = getClearance( aCurrent, aObstacleVia ) ;
720 LINE_PAIR_VEC draggedLines;
721 bool lineCollision = false;
722 bool viaCollision = false;
723 LINE* currentLine = NULL;
724 VECTOR2I mtvLine;
725 VECTOR2I mtvVia;
726 VECTOR2I mtvSolid;
727 VECTOR2I mtv;
728 int rank = -1;
729
730 if( aCurrent->OfKind( ITEM::LINE_T ) )
731 {
732 #ifdef DEBUG
733 m_logger.NewGroup( "push-via-by-line", m_iter );
734 m_logger.Log( aCurrent, 4, "current" );
735 #endif
736
737 currentLine = (LINE*) aCurrent;
738 lineCollision = CollideShapes( aObstacleVia->Shape(), currentLine->Shape(),
739 clearance + currentLine->Width() / 2 + PNS_HULL_MARGIN,
740 true, mtvLine );
741
742 if( currentLine->EndsWithVia() )
743 {
744 viaCollision = CollideShapes( currentLine->Via().Shape(), aObstacleVia->Shape(),
745 clearance + PNS_HULL_MARGIN, true, mtvVia );
746 }
747
748 if( !lineCollision && !viaCollision )
749 return SH_OK;
750
751 if( lineCollision && viaCollision )
752 mtv = mtvVia.EuclideanNorm() > mtvLine.EuclideanNorm() ? mtvVia : mtvLine;
753 else if( lineCollision )
754 mtv = mtvLine;
755 else
756 mtv = mtvVia;
757
758 rank = currentLine->Rank();
759 }
760 else if( aCurrent->OfKind( ITEM::SOLID_T ) )
761 {
762 CollideShapes( aObstacleVia->Shape(), aCurrent->Shape(),
763 clearance + PNS_HULL_MARGIN, true, mtvSolid );
764 mtv = -mtvSolid;
765 rank = aCurrent->Rank() + 10000;
766 }
767
768 return pushVia( aObstacleVia, mtv, rank );
769 }
770
771
onReverseCollidingVia(LINE & aCurrent,VIA * aObstacleVia)772 SHOVE::SHOVE_STATUS SHOVE::onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia )
773 {
774 int n = 0;
775 LINE cur( aCurrent );
776 cur.ClearSegmentLinks();
777
778 JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
779 LINE shoved( aCurrent );
780 shoved.ClearSegmentLinks();
781
782 cur.RemoveVia();
783 unwindStack( &aCurrent );
784
785 for( ITEM* item : jt->LinkList() )
786 {
787 if( item->OfKind( ITEM::SEGMENT_T ) && item->LayersOverlap( &aCurrent ) )
788 {
789 SEGMENT* seg = (SEGMENT*) item;
790 LINE head = assembleLine( seg );
791
792 head.AppendVia( *aObstacleVia );
793
794 SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
795
796 if( st != SH_OK )
797 {
798 #ifdef DEBUG
799 m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
800 m_logger.Log( aObstacleVia, 0, "the-via" );
801 m_logger.Log( &aCurrent, 1, "current-line" );
802 m_logger.Log( &shoved, 3, "shoved-line" );
803 #endif
804
805 return st;
806 }
807
808 cur.SetShape( shoved.CLine() );
809 n++;
810 }
811 }
812
813 if( !n )
814 {
815 #ifdef DEBUG
816 m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
817 m_logger.Log( aObstacleVia, 0, "the-via" );
818 m_logger.Log( &aCurrent, 1, "current-line" );
819 #endif
820
821 LINE head( aCurrent );
822 head.Line().Clear();
823 head.AppendVia( *aObstacleVia );
824 head.ClearSegmentLinks();
825
826 SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
827
828 if( st != SH_OK )
829 return st;
830
831 cur.SetShape( shoved.CLine() );
832 }
833
834 if( aCurrent.EndsWithVia() )
835 shoved.AppendVia( aCurrent.Via() );
836
837 #ifdef DEBUG
838 m_logger.NewGroup( "on-reverse-via", m_iter );
839 m_logger.Log( aObstacleVia, 0, "the-via" );
840 m_logger.Log( &aCurrent, 1, "current-line" );
841 m_logger.Log( &shoved, 3, "shoved-line" );
842 #endif
843 int currentRank = aCurrent.Rank();
844 replaceLine( aCurrent, shoved );
845
846 if( !pushLine( shoved ) )
847 return SH_INCOMPLETE;
848
849 shoved.SetRank( currentRank );
850
851 return SH_OK;
852 }
853
854
unwindStack(SEGMENT * aSeg)855 void SHOVE::unwindStack( SEGMENT* aSeg )
856 {
857 for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
858 {
859 if( i->ContainsSegment( aSeg ) )
860 i = m_lineStack.erase( i );
861 else
862 i++;
863 }
864
865 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
866 {
867 if( i->ContainsSegment( aSeg ) )
868 i = m_optimizerQueue.erase( i );
869 else
870 i++;
871 }
872 }
873
874
unwindStack(ITEM * aItem)875 void SHOVE::unwindStack( ITEM* aItem )
876 {
877 if( aItem->OfKind( ITEM::SEGMENT_T ) )
878 unwindStack( static_cast<SEGMENT*>( aItem ) );
879 else if( aItem->OfKind( ITEM::LINE_T ) )
880 {
881 LINE* l = static_cast<LINE*>( aItem );
882
883 for( SEGMENT* seg : l->LinkedSegments() )
884 unwindStack( seg );
885 }
886 }
887
888
pushLine(const LINE & aL,bool aKeepCurrentOnTop)889 bool SHOVE::pushLine( const LINE& aL, bool aKeepCurrentOnTop )
890 {
891 if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
892 return false;
893
894 if( aKeepCurrentOnTop && m_lineStack.size() > 0)
895 {
896 m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
897 }
898 else
899 {
900 m_lineStack.push_back( aL );
901 }
902
903 m_optimizerQueue.push_back( aL );
904
905 return true;
906 }
907
popLine()908 void SHOVE::popLine( )
909 {
910 LINE& l = m_lineStack.back();
911
912 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
913 {
914 bool found = false;
915
916 for( SEGMENT *s : l.LinkedSegments() )
917 {
918 if( i->ContainsSegment( s ) )
919 {
920 i = m_optimizerQueue.erase( i );
921 found = true;
922 break;
923 }
924 }
925
926 if( !found )
927 i++;
928 }
929
930 m_lineStack.pop_back();
931 }
932
933
shoveIteration(int aIter)934 SHOVE::SHOVE_STATUS SHOVE::shoveIteration( int aIter )
935 {
936 LINE currentLine = m_lineStack.back();
937 NODE::OPT_OBSTACLE nearest;
938 SHOVE_STATUS st = SH_NULL;
939
940 ITEM::PnsKind search_order[] = { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T };
941
942 for( int i = 0; i < 3; i++ )
943 {
944 nearest = m_currentNode->NearestObstacle( ¤tLine, search_order[i] );
945
946 if( nearest )
947 break;
948 }
949
950 if( !nearest )
951 {
952 m_lineStack.pop_back();
953 return SH_OK;
954 }
955
956 ITEM* ni = nearest->m_item;
957
958 unwindStack( ni );
959
960 if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
961 {
962 switch( ni->Kind() )
963 {
964 case ITEM::VIA_T:
965 {
966 VIA* revVia = (VIA*) ni;
967 wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
968
969 if( currentLine.EndsWithVia() && m_currentNode->CheckColliding( ¤tLine.Via(), revVia ) )
970 {
971 st = SH_INCOMPLETE;
972 }
973 else
974 {
975 st = onReverseCollidingVia( currentLine, revVia );
976 }
977
978 break;
979 }
980
981 case ITEM::SEGMENT_T:
982 {
983 SEGMENT* seg = (SEGMENT*) ni;
984 wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
985 LINE revLine = assembleLine( seg );
986
987 popLine();
988 st = onCollidingLine( revLine, currentLine );
989 if( !pushLine( revLine ) )
990 return SH_INCOMPLETE;
991
992 break;
993 }
994
995 default:
996 assert( false );
997 }
998 }
999 else
1000 { // "forward" collisions
1001 switch( ni->Kind() )
1002 {
1003 case ITEM::SEGMENT_T:
1004 wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1005
1006 st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1007
1008 if( st == SH_TRY_WALK )
1009 st = onCollidingSolid( currentLine, ni );
1010
1011 break;
1012
1013 case ITEM::VIA_T:
1014 wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1015 st = onCollidingVia( ¤tLine, (VIA*) ni );
1016
1017 if( st == SH_TRY_WALK )
1018 st = onCollidingSolid( currentLine, ni );
1019
1020 break;
1021
1022 case ITEM::SOLID_T:
1023 wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1024 st = onCollidingSolid( currentLine, (SOLID*) ni );
1025 break;
1026
1027 default:
1028 break;
1029 }
1030 }
1031
1032 return st;
1033 }
1034
1035
shoveMainLoop()1036 SHOVE::SHOVE_STATUS SHOVE::shoveMainLoop()
1037 {
1038 SHOVE_STATUS st = SH_OK;
1039
1040 m_affectedAreaSum = OPT_BOX2I();
1041
1042 wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1043 m_currentNode->JointCount() );
1044
1045 int iterLimit = Settings().ShoveIterationLimit();
1046 TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1047
1048 m_iter = 0;
1049
1050 timeLimit.Restart();
1051
1052 while( !m_lineStack.empty() )
1053 {
1054 st = shoveIteration( m_iter );
1055
1056 m_iter++;
1057
1058 if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1059 {
1060 st = SH_INCOMPLETE;
1061 break;
1062 }
1063 }
1064
1065 return st;
1066 }
1067
1068
totalAffectedArea() const1069 OPT_BOX2I SHOVE::totalAffectedArea() const
1070 {
1071 OPT_BOX2I area;
1072 if( !m_nodeStack.empty() )
1073 area = m_nodeStack.back().m_affectedArea;
1074
1075 if( area )
1076 {
1077 if( m_affectedAreaSum )
1078 area->Merge( *m_affectedAreaSum );
1079 }
1080 else
1081 area = m_affectedAreaSum;
1082
1083 return area;
1084 }
1085
1086
ShoveLines(const LINE & aCurrentHead)1087 SHOVE::SHOVE_STATUS SHOVE::ShoveLines( const LINE& aCurrentHead )
1088 {
1089 SHOVE_STATUS st = SH_OK;
1090
1091 m_multiLineMode = false;
1092
1093 // empty head? nothing to shove...
1094
1095 if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1096 return SH_INCOMPLETE;
1097
1098 LINE head( aCurrentHead );
1099 head.ClearSegmentLinks();
1100
1101 m_lineStack.clear();
1102 m_optimizerQueue.clear();
1103 m_newHead = OPT_LINE();
1104 m_logger.Clear();
1105
1106 ITEM_SET headSet;
1107 headSet.Add( aCurrentHead );
1108
1109 reduceSpringback( headSet );
1110
1111 NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1112
1113 m_currentNode = parent->Branch();
1114 m_currentNode->ClearRanks();
1115 m_currentNode->Add( head );
1116
1117 m_currentNode->LockJoint( head.CPoint(0), &head, true );
1118
1119 if( !head.EndsWithVia() )
1120 m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1121
1122 head.Mark( MK_HEAD );
1123 head.SetRank( 100000 );
1124
1125 m_logger.NewGroup( "initial", 0 );
1126 m_logger.Log( &head, 0, "head" );
1127
1128 if( head.EndsWithVia() )
1129 {
1130 std::unique_ptr< VIA >headVia = Clone( head.Via() );
1131 headVia->Mark( MK_HEAD );
1132 headVia->SetRank( 100000 );
1133 m_logger.Log( headVia.get(), 0, "head-via" );
1134 m_currentNode->Add( std::move( headVia ) );
1135 }
1136
1137 if( !pushLine( head ) )
1138 {
1139 delete m_currentNode;
1140 m_currentNode = parent;
1141
1142 return SH_INCOMPLETE;
1143 }
1144
1145 st = shoveMainLoop();
1146
1147 if( st == SH_OK )
1148 {
1149 runOptimizer( m_currentNode );
1150
1151 if( m_newHead )
1152 st = m_currentNode->CheckColliding( &( *m_newHead ) ) ? SH_INCOMPLETE : SH_HEAD_MODIFIED;
1153 else
1154 st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1155 }
1156
1157 m_currentNode->RemoveByMarker( MK_HEAD );
1158
1159 wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1160 ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1161
1162 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1163 {
1164 pushSpringback( m_currentNode, headSet, COST_ESTIMATOR(), m_affectedAreaSum );
1165 }
1166 else
1167 {
1168 delete m_currentNode;
1169
1170 m_currentNode = parent;
1171 m_newHead = OPT_LINE();
1172 }
1173
1174 if(m_newHead)
1175 m_newHead->Unmark();
1176
1177 if( m_newHead && head.EndsWithVia() )
1178 {
1179 VIA v = head.Via();
1180 v.SetPos( m_newHead->CPoint( -1 ) );
1181 m_newHead->AppendVia(v);
1182 }
1183
1184 return st;
1185 }
1186
1187
ShoveMultiLines(const ITEM_SET & aHeadSet)1188 SHOVE::SHOVE_STATUS SHOVE::ShoveMultiLines( const ITEM_SET& aHeadSet )
1189 {
1190 SHOVE_STATUS st = SH_OK;
1191
1192 m_multiLineMode = true;
1193
1194 ITEM_SET headSet;
1195
1196 for( const ITEM* item : aHeadSet.CItems() )
1197 {
1198 const LINE* headOrig = static_cast<const LINE*>( item );
1199
1200 // empty head? nothing to shove...
1201 if( !headOrig->SegmentCount() )
1202 return SH_INCOMPLETE;
1203
1204 headSet.Add( *headOrig );
1205 }
1206
1207 m_lineStack.clear();
1208 m_optimizerQueue.clear();
1209 m_logger.Clear();
1210
1211 reduceSpringback( headSet );
1212
1213 NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1214
1215 m_currentNode = parent->Branch();
1216 m_currentNode->ClearRanks();
1217 int n = 0;
1218
1219 for( const ITEM* item : aHeadSet.CItems() )
1220 {
1221 const LINE* headOrig = static_cast<const LINE*>( item );
1222 LINE head( *headOrig );
1223 head.ClearSegmentLinks();
1224
1225 m_currentNode->Add( head );
1226
1227 head.Mark( MK_HEAD );
1228 head.SetRank( 100000 );
1229 n++;
1230
1231 if( !pushLine( head ) )
1232 return SH_INCOMPLETE;
1233
1234 if( head.EndsWithVia() )
1235 {
1236 std::unique_ptr< VIA > headVia = Clone( head.Via() );
1237 headVia->Mark( MK_HEAD );
1238 headVia->SetRank( 100000 );
1239 m_logger.Log( headVia.get(), 0, "head-via" );
1240 m_currentNode->Add( std::move( headVia ) );
1241 }
1242 }
1243
1244 m_logger.NewGroup( "initial", 0 );
1245 //m_logger.Log( head, 0, "head" );
1246
1247 st = shoveMainLoop();
1248
1249 if( st == SH_OK )
1250 runOptimizer( m_currentNode );
1251
1252 m_currentNode->RemoveByMarker( MK_HEAD );
1253
1254 wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1255 ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1256
1257 if( st == SH_OK )
1258 {
1259 pushSpringback( m_currentNode, ITEM_SET(), COST_ESTIMATOR(), m_affectedAreaSum );
1260 }
1261 else
1262 {
1263 delete m_currentNode;
1264 m_currentNode = parent;
1265 }
1266
1267 return st;
1268 }
1269
1270
ShoveDraggingVia(VIA * aVia,const VECTOR2I & aWhere,VIA ** aNewVia)1271 SHOVE::SHOVE_STATUS SHOVE::ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere, VIA** aNewVia )
1272 {
1273 SHOVE_STATUS st = SH_OK;
1274
1275 m_lineStack.clear();
1276 m_optimizerQueue.clear();
1277 m_newHead = OPT_LINE();
1278 m_draggedVia = NULL;
1279 m_draggedViaHeadSet.Clear();
1280
1281 NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1282
1283 m_currentNode = parent;
1284
1285 parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1286
1287 m_currentNode = parent->Branch();
1288 m_currentNode->ClearRanks();
1289
1290 aVia->Mark( MK_HEAD );
1291
1292 st = pushVia( aVia, ( aWhere - aVia->Pos() ), 0 );
1293 st = shoveMainLoop();
1294
1295 if( st == SH_OK )
1296 runOptimizer( m_currentNode );
1297
1298 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1299 {
1300 if( aNewVia )
1301 {
1302 wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1303 *aNewVia = m_draggedVia;
1304 }
1305
1306 pushSpringback( m_currentNode, m_draggedViaHeadSet, COST_ESTIMATOR(), m_affectedAreaSum );
1307 }
1308 else
1309 {
1310 if( aNewVia )
1311 *aNewVia = nullptr;
1312
1313 delete m_currentNode;
1314 m_currentNode = parent;
1315 }
1316
1317 return st;
1318 }
1319
1320
runOptimizer(NODE * aNode)1321 void SHOVE::runOptimizer( NODE* aNode )
1322 {
1323 OPTIMIZER optimizer( aNode );
1324 int optFlags = 0;
1325 int n_passes = 0;
1326
1327 PNS_OPTIMIZATION_EFFORT effort = Settings().OptimizerEffort();
1328
1329 OPT_BOX2I area = totalAffectedArea();
1330
1331 int maxWidth = 0;
1332
1333 for( LINE& line : m_optimizerQueue )
1334 maxWidth = std::max( line.Width(), maxWidth );
1335
1336 if( area )
1337 area->Inflate( 10 * maxWidth );
1338
1339 switch( effort )
1340 {
1341 case OE_LOW:
1342 optFlags = OPTIMIZER::MERGE_OBTUSE;
1343 n_passes = 1;
1344 break;
1345
1346 case OE_MEDIUM:
1347 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1348
1349 if( area )
1350 optimizer.SetRestrictArea( *area );
1351
1352 n_passes = 2;
1353 break;
1354
1355 case OE_FULL:
1356 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1357 n_passes = 2;
1358 break;
1359
1360 default:
1361 break;
1362 }
1363
1364 if( Settings().SmartPads() )
1365 optFlags |= OPTIMIZER::SMART_PADS;
1366
1367 optimizer.SetEffortLevel( optFlags );
1368 optimizer.SetCollisionMask( ITEM::ANY_T );
1369
1370 for( int pass = 0; pass < n_passes; pass++ )
1371 {
1372 std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1373
1374 for( LINE& line : m_optimizerQueue)
1375 {
1376 if( !( line.Marker() & MK_HEAD ) )
1377 {
1378 LINE optimized;
1379
1380 if( optimizer.Optimize( &line, &optimized ) )
1381 {
1382 aNode->Remove( line );
1383 line.SetShape( optimized.CLine() );
1384 aNode->Add( line );
1385 }
1386 }
1387 }
1388 }
1389 }
1390
1391
CurrentNode()1392 NODE* SHOVE::CurrentNode()
1393 {
1394 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1395 }
1396
1397
NewHead() const1398 const LINE SHOVE::NewHead() const
1399 {
1400 assert( m_newHead );
1401
1402 return *m_newHead;
1403 }
1404
1405
SetInitialLine(LINE & aInitial)1406 void SHOVE::SetInitialLine( LINE& aInitial )
1407 {
1408 m_root = m_root->Branch();
1409 m_root->Remove( aInitial );
1410 }
1411
1412 }
1413