KiCad PCB EDA Suite
pns_shove.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 CERN
5  * Copyright (C) 2016-2020 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 #include <math/box2.h>
25 
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 
47 namespace PNS {
48 
49 void 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 void SHOVE::replaceLine( LINE& aOld, LINE& aNew )
60 {
61  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
62 
63  if( changed_area )
64  {
65  if( Dbg() )
66  {
67  Dbg()->AddBox( *changed_area, 3, "shove-changed-area" );
68  }
69 
70  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
71  }
72 
73  m_currentNode->Replace( aOld, aNew );
74 }
75 
76 int SHOVE::getClearance( const ITEM* aA, const ITEM* aB ) const
77 {
78  if( m_forceClearance >= 0 )
79  return m_forceClearance;
80 
81  return m_currentNode->GetClearance( aA, aB );
82 }
83 
84 int SHOVE::getHoleClearance( const ITEM* aA, const ITEM* aB ) const
85 {
86  if( m_forceClearance >= 0 )
87  return m_forceClearance;
88 
89  return m_currentNode->GetHoleClearance( aA, aB );
90 }
91 
92 
93 void SHOVE::sanityCheck( LINE* aOld, LINE* aNew )
94 {
95  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
96  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
97 }
98 
99 
100 SHOVE::SHOVE( NODE* aWorld, ROUTER* aRouter ) :
101  ALGO_BASE( aRouter )
102 {
103  m_forceClearance = -1;
104  m_root = aWorld;
105  m_currentNode = aWorld;
107 
108  // Initialize other temporary variables:
109  m_draggedVia = NULL;
110  m_iter = 0;
111  m_multiLineMode = false;
113 }
114 
115 
117 {
118 }
119 
120 
121 LINE SHOVE::assembleLine( const LINKED_ITEM* aSeg, int* aIndex )
122 {
123  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
124 }
125 
126 // A dumb function that checks if the shoved line is shoved the right way, e.g. visually
127 // "outwards" of the line/via applying pressure on it. Unfortunately there's no mathematical
128 // concept of orientation of an open curve, so we use some primitive heuristics: if the shoved
129 // line wraps around the start of the "pusher", it's likely shoved in wrong direction.
130 
131 // Update: there's no concept of an orientation of an open curve, but nonetheless Tom's dumb as.... (censored)
132 // Two open curves put together make a closed polygon... Tom should learn high school geometry!
133 
134 bool SHOVE::checkShoveDirection( const LINE& aCurLine, const LINE& aObstacleLine,
135  const LINE& aShovedLine ) const
136 {
137  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
138  checker.AddPolyline( aObstacleLine.CLine() );
139  checker.AddPolyline( aShovedLine.CLine().Reverse() );
140 
141  bool inside = checker.IsInside();
142 
143  return !inside;
144 }
145 
146 
147 /*
148  * Push aObstacleLine away from aCurLine's via by the clearance distance, returning the result
149  * in aResultLine.
150  *
151  * Must be called only when aCurLine itself is on another layer (or has no segments) so that it
152  * can be ignored.
153  */
154 SHOVE::SHOVE_STATUS SHOVE::shoveLineFromLoneVia( const LINE& aCurLine, const LINE& aObstacleLine,
155  LINE& aResultLine )
156 {
157  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
158 
159  int obstacleLineWidth = aObstacleLine.Width();
160  int clearance = getClearance( &aCurLine, &aObstacleLine );
161  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
162 
163  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
164  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
165 
166  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
167  SHAPE_LINE_CHAIN path_cw;
168  SHAPE_LINE_CHAIN path_ccw;
169 
170  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
171  return SH_INCOMPLETE;
172 
173  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
174  return SH_INCOMPLETE;
175 
176  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
177 
178  if( shortest.PointCount() < 2 )
179  return SH_INCOMPLETE;
180 
181  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
182  return SH_INCOMPLETE;
183 
184  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
185  return SH_INCOMPLETE;
186 
187  aResultLine.SetShape( shortest );
188 
189  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
190  return SH_INCOMPLETE;
191 
192  return SH_OK;
193 }
194 
195 
196 /*
197  * Re-walk aObstacleLine around the given set of hulls, returning the result in aResultLine.
198  */
199 SHOVE::SHOVE_STATUS SHOVE::shoveLineToHullSet( const LINE& aCurLine, const LINE& aObstacleLine,
200  LINE& aResultLine, const HULL_SET& aHulls )
201 {
202  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
203 
204  int attempt;
205 
206  for( attempt = 0; attempt < 4; attempt++ )
207  {
208  bool invertTraversal = ( attempt >= 2 );
209  bool clockwise = attempt % 2;
210  int vFirst = -1, vLast = -1;
211 
212  SHAPE_LINE_CHAIN path;
213  LINE l( aObstacleLine );
214 
215  for( int i = 0; i < (int) aHulls.size(); i++ )
216  {
217  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
218 
219  if( ! l.Walkaround( hull, path, clockwise ) )
220  {
221  wxLogTrace("PNS", "Fail-Walk %s %s %d\n", hull.Format().c_str(), l.CLine().Format().c_str(), clockwise? 1:0);
222  return SH_INCOMPLETE;
223  }
224 
225  path.Simplify();
226  l.SetShape( path );
227  }
228 
229  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
230  {
231  if( path.CPoint( i ) != obs.CPoint( i ) )
232  {
233  vFirst = i;
234  break;
235  }
236  }
237 
238  int k = obs.PointCount() - 1;
239  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
240  {
241  if( path.CPoint( i ) != obs.CPoint( k ) )
242  {
243  vLast = i;
244  break;
245  }
246  }
247 
248  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
249  {
250  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
251  continue;
252  }
253 
254  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
255  {
256  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
257  continue;
258  }
259 
260  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
261  {
262  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
263  aResultLine.SetShape( l.CLine() );
264 
265  continue;
266  }
267 
268  if( path.SelfIntersecting() )
269  {
270  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
271  continue;
272  }
273 
274  bool colliding = l.Collide( &aCurLine, m_currentNode );
275 
276 #ifdef DEBUG
277  char str[128];
278  sprintf( str, "att-%d-shoved", attempt );
279  Dbg()->AddLine( l.CLine(), 3, 20000, str );
280 #endif
281 
282  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
283  {
284  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
285 
286  for( ITEM* item : jtStart->LinkList() )
287  {
288  if( item->Collide( &l, m_currentNode ) )
289  colliding = true;
290  }
291  }
292 
293  if( colliding )
294  {
295  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
296  continue;
297  }
298 
299  aResultLine.SetShape( l.CLine() );
300 
301  return SH_OK;
302  }
303 
304  return SH_INCOMPLETE;
305 }
306 
307 
308 /*
309  * Push aObstacleLine line away from aCurLine by the clearance distance, and return the result in
310  * aResultLine.
311  */
312 SHOVE::SHOVE_STATUS SHOVE::ShoveObstacleLine( const LINE& aCurLine, const LINE& aObstacleLine,
313  LINE& aResultLine )
314 {
315  aResultLine.ClearLinks();
316 
317  bool obstacleIsHead = false;
318 
319  for( LINKED_ITEM* s : aObstacleLine.Links() )
320  {
321  if( s->Marker() & MK_HEAD )
322  {
323  obstacleIsHead = true;
324  break;
325  }
326  }
327 
328  SHOVE_STATUS rv;
329  bool viaOnEnd = aCurLine.EndsWithVia();
330 
331  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
332  {
333  // Shove aObstacleLine to the hull of aCurLine's via.
334 
335  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
336  }
337  else
338  {
339  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
340  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
341  // hull it will be at the appropriate clearance.
342 
343  int obstacleLineWidth = aObstacleLine.Width();
344  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
345  int currentLineSegmentCount = aCurLine.SegmentCount();
346  HULL_SET hulls;
347 
348  hulls.reserve( currentLineSegmentCount + 1 );
349 
350 #ifdef DEBUG
351  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
352  aCurLine.Net(),
353  aObstacleLine.Net(),
354  clearance ) );
355 #endif
356 
357  for( int i = 0; i < currentLineSegmentCount; i++ )
358  {
359  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
360  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
361 
362  hulls.push_back( hull );
363  }
364 
365  if( viaOnEnd )
366  {
367  const VIA& via = aCurLine.Via();
368  int viaClearance = getClearance( &via, &aObstacleLine );
369  int holeClearance = getHoleClearance( &via, &aObstacleLine );
370 
371  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
372  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
373 
374  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
375  }
376 
377 #ifdef DEBUG
378  char str[128];
379  sprintf( str, "current-cl-%d", clearance );
380  Dbg()->AddLine( aCurLine.CLine(), 5, 20000, str );
381 #endif
382 
383  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
384  }
385 
386  if( obstacleIsHead )
387  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
388 
389  return rv;
390 }
391 
392 
393 /*
394  * TODO describe....
395  */
397 {
398  int segIndex;
399  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
400  LINE shovedLine( obstacleLine );
401  SEGMENT tmp( *aObstacleSeg );
402 
403  if( obstacleLine.HasLockedSegments() )
404  return SH_TRY_WALK;
405 
406  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
407 
408  const double extensionWalkThreshold = 1.0;
409 
410  double obsLen = obstacleLine.CLine().Length();
411  double shovedLen = shovedLine.CLine().Length();
412  double extensionFactor = 0.0;
413 
414  if( obsLen != 0.0f )
415  extensionFactor = shovedLen / obsLen - 1.0;
416 
417  if( extensionFactor > extensionWalkThreshold )
418  return SH_TRY_WALK;
419 
420  assert( obstacleLine.LayersOverlap( &shovedLine ) );
421 
422  if( Dbg() )
423  {
424  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d", m_iter ).ToStdString() );
425  Dbg()->AddSegment( tmp.Seg(), 0, "obstacle-segment" );
426  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
427  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
428  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
429  if( rv == SH_OK )
430  Dbg()->Message("Shove success");
431  else
432  Dbg()->Message("Shove FAIL");
433  Dbg()->EndGroup();
434  }
435 
436  if( rv == SH_OK )
437  {
438  if( shovedLine.Marker() & MK_HEAD )
439  {
440  if( m_multiLineMode )
441  return SH_INCOMPLETE;
442 
443  m_newHead = shovedLine;
444  }
445 
446  int rank = aCurrent.Rank();
447  shovedLine.SetRank( rank - 1 );
448 
449  sanityCheck( &obstacleLine, &shovedLine );
450  replaceLine( obstacleLine, shovedLine );
451 
452  if( !pushLineStack( shovedLine ) )
453  rv = SH_INCOMPLETE;
454  }
455 
456  return rv;
457 }
458 
459 
460 /*
461  * TODO describe....
462  */
464 {
465  int segIndex;
466  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
467  LINE shovedLine( obstacleLine );
468  ARC tmp( *aObstacleArc );
469 
470  if( obstacleLine.HasLockedSegments() )
471  return SH_TRY_WALK;
472 
473  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
474 
475  const double extensionWalkThreshold = 1.0;
476 
477  double obsLen = obstacleLine.CLine().Length();
478  double shovedLen = shovedLine.CLine().Length();
479  double extensionFactor = 0.0;
480 
481  if( obsLen != 0.0f )
482  extensionFactor = shovedLen / obsLen - 1.0;
483 
484  if( extensionFactor > extensionWalkThreshold )
485  return SH_TRY_WALK;
486 
487  assert( obstacleLine.LayersOverlap( &shovedLine ) );
488 
489  if ( Dbg() )
490  {
491  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
492  Dbg()->AddLine( tmp.CLine(), 0, 10000, "obstacle-segment" );
493  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
494  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
495  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
496  Dbg()->EndGroup();
497  }
498 
499  if( rv == SH_OK )
500  {
501  if( shovedLine.Marker() & MK_HEAD )
502  {
503  if( m_multiLineMode )
504  return SH_INCOMPLETE;
505 
506  m_newHead = shovedLine;
507  }
508 
509  int rank = aCurrent.Rank();
510  shovedLine.SetRank( rank - 1 );
511 
512  sanityCheck( &obstacleLine, &shovedLine );
513  replaceLine( obstacleLine, shovedLine );
514 
515  if( !pushLineStack( shovedLine ) )
516  rv = SH_INCOMPLETE;
517  }
518 
519  return rv;
520 }
521 
522 
523 /*
524  * TODO describe....
525  */
527 {
528  LINE shovedLine( aObstacle );
529 
530  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
531 
532  Dbg()->BeginGroup( "on-colliding-line" );
533  Dbg()->AddLine( aObstacle.CLine(), 1, 100000, "obstacle-line" );
534  Dbg()->AddLine( aCurrent.CLine(), 2, 150000, "current-line" );
535  Dbg()->AddLine( shovedLine.CLine(), 3, 200000, "shoved-line" );
536 
537  if( rv == SH_OK )
538  {
539  if( shovedLine.Marker() & MK_HEAD )
540  {
541  if( m_multiLineMode )
542  return SH_INCOMPLETE;
543 
544  m_newHead = shovedLine;
545  }
546 
547  sanityCheck( &aObstacle, &shovedLine );
548  replaceLine( aObstacle, shovedLine );
549 
550  int rank = aObstacle.Rank();
551  shovedLine.SetRank( rank - 1 );
552 
553 
554  if( !pushLineStack( shovedLine ) )
555  {
556  rv = SH_INCOMPLETE;
557  }
558  }
559 
560  return rv;
561 }
562 
563 
564 /*
565  * TODO describe....
566  */
568 {
569  WALKAROUND walkaround( m_currentNode, Router() );
570  LINE walkaroundLine( aCurrent );
571 
572  if( aCurrent.EndsWithVia() )
573  {
574  VIA vh = aCurrent.Via();
575  VIA* via = NULL;
576  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
577 
578  if( !jtStart )
579  return SH_INCOMPLETE;
580 
581  for( ITEM* item : jtStart->LinkList() )
582  {
583  if( item->OfKind( ITEM::VIA_T ) )
584  {
585  via = (VIA*) item;
586  break;
587  }
588  }
589 
590  if( via && via->Collide( aObstacle, m_currentNode ) )
591  return onCollidingVia( aObstacle, via );
592  }
593 
594  TOPOLOGY topo( m_currentNode );
595 
596  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
597 
598  walkaround.SetSolidsOnly( false );
599  walkaround.RestrictToSet( true, cluster );
600  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
601 
602  int currentRank = aCurrent.Rank();
603  int nextRank;
604 
605  bool success = false;
606 
607  for( int attempt = 0; attempt < 2; attempt++ )
608  {
609  if( attempt == 1 || Settings().JumpOverObstacles() )
610  {
611 
612  nextRank = currentRank - 1;
613  walkaround.SetSingleDirection( true );
614  }
615  else
616  {
617  nextRank = currentRank + 10000;
618  walkaround.SetSingleDirection( false );
619  }
620 
621 
622  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
623 
624  if( status != WALKAROUND::DONE )
625  continue;
626 
627  walkaroundLine.ClearLinks();
628  walkaroundLine.Unmark();
629  walkaroundLine.Line().Simplify();
630 
631  if( walkaroundLine.HasLoops() )
632  continue;
633 
634  if( aCurrent.Marker() & MK_HEAD )
635  {
636  walkaroundLine.Mark( MK_HEAD );
637 
638  if( m_multiLineMode )
639  continue;
640 
641  m_newHead = walkaroundLine;
642  }
643 
644  sanityCheck( &aCurrent, &walkaroundLine );
645 
646  if( !m_lineStack.empty() )
647  {
648  LINE lastLine = m_lineStack.front();
649 
650  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
651  {
652  LINE dummy( lastLine );
653 
654  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
655  {
656  success = true;
657  break;
658  }
659  } else {
660  success = true;
661  break;
662  }
663  }
664  }
665 
666  if(!success)
667  return SH_INCOMPLETE;
668 
669  replaceLine( aCurrent, walkaroundLine );
670  walkaroundLine.SetRank( nextRank );
671 
672  if( Dbg() )
673  {
674  Dbg()->BeginGroup( "on-colliding-solid" );
675  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
676  Dbg()->AddLine( walkaroundLine.CLine(), 3, 10000, "walk-line" );
677  Dbg()->EndGroup();
678  }
679 
680  popLineStack();
681 
682  if( !pushLineStack( walkaroundLine ) )
683  return SH_INCOMPLETE;
684 
685  return SH_OK;
686 }
687 
688 
689 /*
690  * Pops NODE stackframes which no longer collide with aHeadSet. Optionally sets aDraggedVia
691  * to the dragged via of the last unpopped state.
692  */
693 NODE* SHOVE::reduceSpringback( const ITEM_SET& aHeadSet, VIA_HANDLE& aDraggedVia )
694 {
695  while( !m_nodeStack.empty() )
696  {
697  SPRINGBACK_TAG& spTag = m_nodeStack.back();
698 
699  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
700 
701  if( !obs && !spTag.m_locked )
702  {
703  aDraggedVia = spTag.m_draggedVia;
704  aDraggedVia.valid = true;
705 
706  delete spTag.m_node;
707  m_nodeStack.pop_back();
708  }
709  else
710  break;
711  }
712 
713  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
714 }
715 
716 
717 /*
718  * Push the current NODE on to the stack. aDraggedVia is the dragged via *before* the push
719  * (which will be restored in the event the stackframe is popped).
720  */
721 bool SHOVE::pushSpringback( NODE* aNode, const OPT_BOX2I& aAffectedArea, VIA* aDraggedVia )
722 {
723  SPRINGBACK_TAG st;
724  OPT_BOX2I prev_area;
725 
726  if( !m_nodeStack.empty() )
727  prev_area = m_nodeStack.back().m_affectedArea;
728 
729  if( aDraggedVia )
730  {
731  st.m_draggedVia = aDraggedVia->MakeHandle();
732  }
733 
734  st.m_node = aNode;
735 
736  if( aAffectedArea )
737  {
738  if( prev_area )
739  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
740  else
741  st.m_affectedArea = aAffectedArea;
742  } else
743  st.m_affectedArea = prev_area;
744 
745  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
746  st.m_locked = false;
747 
748  m_nodeStack.push_back( st );
749 
750  return true;
751 }
752 
753 
754 /*
755  * Push or shove a via by at least aForce. (The via might be pushed or shoved slightly further
756  * to keep it from landing on an existing joint.)
757  */
758 SHOVE::SHOVE_STATUS SHOVE::pushOrShoveVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank )
759 {
760  LINE_PAIR_VEC draggedLines;
761  VECTOR2I p0( aVia->Pos() );
762  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
763  VECTOR2I p0_pushed( p0 + aForce );
764 
765  // nothing to do...
766  if ( aForce.x == 0 && aForce.y == 0 )
767  return SH_OK;
768 
769  if( !jt )
770  {
771  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
772  return SH_INCOMPLETE;
773  }
774 
775  if( aVia->IsLocked() )
776  return SH_TRY_WALK;
777 
778  if( jt->IsLocked() )
779  return SH_INCOMPLETE;
780 
781  // make sure pushed via does not overlap with any existing joint
782  while( true )
783  {
784  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
785 
786  if( !jt_next )
787  break;
788 
789  p0_pushed += aForce.Resize( 2 );
790  }
791 
792  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
793  pushedVia->SetPos( p0_pushed );
794  pushedVia->Mark( aVia->Marker() );
795 
796  for( ITEM* item : jt->LinkList() )
797  {
798  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
799  {
800  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
801  LINE_PAIR lp;
802  int segIndex;
803 
804  lp.first = assembleLine( li, &segIndex );
805 
806  if( lp.first.HasLockedSegments() )
807  return SH_TRY_WALK;
808 
809  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
810 
811  if( segIndex == 0 )
812  lp.first.Reverse();
813 
814  lp.second = lp.first;
815  lp.second.ClearLinks();
816  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
817  lp.second.AppendVia( *pushedVia );
818  draggedLines.push_back( lp );
819  }
820  }
821 
822 #if 0
823  m_logger.Log( aVia, 0, "obstacle-via" );
824 #endif
825 
826  pushedVia->SetRank( aCurrentRank - 1 );
827 
828 #if 0
829  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
830 #endif
831 
832  if( aVia->Marker() & MK_HEAD ) // push
833  {
834  m_draggedVia = pushedVia.get();
835  }
836  else
837  { // shove
838  if( jt->IsStitchingVia() )
839  pushLineStack( LINE( *pushedVia ) );
840  }
841 
842  replaceItems( aVia, std::move( pushedVia ) );
843 
844  for( LINE_PAIR lp : draggedLines )
845  {
846  if( lp.first.Marker() & MK_HEAD )
847  {
848  lp.second.Mark( MK_HEAD );
849 
850  if( m_multiLineMode )
851  return SH_INCOMPLETE;
852 
853  m_newHead = lp.second;
854  }
855 
856  unwindLineStack( &lp.first );
857 
858  if( lp.second.SegmentCount() )
859  {
860  replaceLine( lp.first, lp.second );
861  lp.second.SetRank( aCurrentRank - 1 );
862 
863  if( !pushLineStack( lp.second, true ) )
864  return SH_INCOMPLETE;
865  }
866  else
867  {
868  m_currentNode->Remove( lp.first );
869  }
870 
871 #if 0
872  m_logger.Log( &lp.first, 2, "fan-pre" );
873  m_logger.Log( &lp.second, 3, "fan-post" );
874 #endif
875  }
876 
877  return SH_OK;
878 }
879 
880 
881 /*
882  * Calculate the minimum translation vector required to resolve a collision with a via and
883  * shove the via by that distance.
884  */
886 {
887  int clearance = getClearance( aCurrent, aObstacleVia );
888  LINE_PAIR_VEC draggedLines;
889  VECTOR2I mtv;
890  int rank = -1;
891 
892  SHAPE_COMPOUND shape;
893 
894  if( aCurrent->OfKind( ITEM::LINE_T ) )
895  {
896  LINE* currentLine = (LINE*) aCurrent;
897 
898 #if 0
899  m_logger.NewGroup( "push-via-by-line", m_iter );
900  m_logger.Log( currentLine, 4, "current" );
901 #endif
902 
903  shape.AddShape( currentLine->Shape()->Clone() );
904 
905  // SHAPE_LINE_CHAIN collisions don't currently pay any attention to the line-chain's
906  // width, so we have to add it to the clearance.
907  clearance += currentLine->Width() / 2;
908 
909  // Add a second shape for the via (if any)
910  if( currentLine->EndsWithVia() )
911  {
912  const VIA& currentVia = currentLine->Via();
913  int viaClearance = getClearance( &currentVia, aObstacleVia );
914  int holeClearance = getHoleClearance( &currentVia, aObstacleVia );
915  int effectiveRadius = std::max( currentVia.Diameter() / 2 + viaClearance,
916  currentVia.Drill() / 2 + holeClearance );
917 
918  // Since we have to run the collision with the line's clearance + 1/2 its width (as
919  // it's the only way to take the SHAPE_LINE_CHAIN's width into account), we need to
920  // subtract that clearance back out of the via's effective radius.
921  shape.AddShape( new SHAPE_CIRCLE( currentVia.Pos(), effectiveRadius - clearance ) );
922  }
923  }
924  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
925  {
926  shape.AddShape( aCurrent->Shape()->Clone() );
927  }
928 
929  aObstacleVia->Shape()->Collide( &shape, clearance + PNS_HULL_MARGIN, &mtv );
930  rank = aCurrent->Rank() + 10000;
931 
932  return pushOrShoveVia( aObstacleVia, mtv, rank );
933 }
934 
935 
936 /*
937  * TODO describe....
938  */
940 {
941  int n = 0;
942  LINE cur( aCurrent );
943  cur.ClearLinks();
944 
945  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
946  LINE shoved( aCurrent );
947  shoved.ClearLinks();
948 
949  cur.RemoveVia();
950  unwindLineStack( &aCurrent );
951 
952  for( ITEM* item : jt->LinkList() )
953  {
954  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
955  {
956  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
957  LINE head = assembleLine( li );
958 
959  head.AppendVia( *aObstacleVia );
960 
961  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
962 
963  if( st != SH_OK )
964  {
965 #if 0
966  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
967  m_logger.Log( aObstacleVia, 0, "the-via" );
968  m_logger.Log( &aCurrent, 1, "current-line" );
969  m_logger.Log( &shoved, 3, "shoved-line" );
970 #endif
971 
972  return st;
973  }
974 
975  cur.SetShape( shoved.CLine() );
976  n++;
977  }
978  }
979 
980  if( !n )
981  {
982 #if 0
983  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
984  m_logger.Log( aObstacleVia, 0, "the-via" );
985  m_logger.Log( &aCurrent, 1, "current-line" );
986 #endif
987 
988  LINE head( aCurrent );
989  head.Line().Clear();
990  head.AppendVia( *aObstacleVia );
991  head.ClearLinks();
992 
993  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
994 
995  if( st != SH_OK )
996  return st;
997 
998  cur.SetShape( shoved.CLine() );
999  }
1000 
1001  if( aCurrent.EndsWithVia() )
1002  shoved.AppendVia( aCurrent.Via() );
1003 
1004 #if 0
1005  m_logger.NewGroup( "on-reverse-via", m_iter );
1006  m_logger.Log( aObstacleVia, 0, "the-via" );
1007  m_logger.Log( &aCurrent, 1, "current-line" );
1008  m_logger.Log( &shoved, 3, "shoved-line" );
1009 #endif
1010  int currentRank = aCurrent.Rank();
1011  replaceLine( aCurrent, shoved );
1012 
1013  if( !pushLineStack( shoved ) )
1014  return SH_INCOMPLETE;
1015 
1016  shoved.SetRank( currentRank );
1017 
1018  return SH_OK;
1019 }
1020 
1021 
1023 {
1024  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1025  {
1026  if( i->ContainsLink( aSeg ) )
1027  i = m_lineStack.erase( i );
1028  else
1029  i++;
1030  }
1031 
1032  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1033  {
1034  if( i->ContainsLink( aSeg ) )
1035  i = m_optimizerQueue.erase( i );
1036  else
1037  i++;
1038  }
1039 }
1040 
1041 
1043 {
1044  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1045  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1046  else if( aItem->OfKind( ITEM::LINE_T ) )
1047  {
1048  LINE* l = static_cast<LINE*>( aItem );
1049 
1050  for( LINKED_ITEM* seg : l->Links() )
1051  unwindLineStack( seg );
1052  }
1053 }
1054 
1055 
1056 bool SHOVE::pushLineStack( const LINE& aL, bool aKeepCurrentOnTop )
1057 {
1058  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1059  return false;
1060 
1061  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1062  {
1063  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1064  }
1065  else
1066  {
1067  m_lineStack.push_back( aL );
1068  }
1069 
1070  m_optimizerQueue.push_back( aL );
1071 
1072  return true;
1073 }
1074 
1076 {
1077  LINE& l = m_lineStack.back();
1078 
1079  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1080  {
1081  bool found = false;
1082 
1083  for( LINKED_ITEM* s : l.Links() )
1084  {
1085  if( i->ContainsLink( s ) )
1086  {
1087  i = m_optimizerQueue.erase( i );
1088  found = true;
1089  break;
1090  }
1091  }
1092 
1093  if( !found )
1094  i++;
1095  }
1096 
1097  m_lineStack.pop_back();
1098 }
1099 
1100 
1101 /*
1102  * Resolve the next collision.
1103  */
1105 {
1106  LINE currentLine = m_lineStack.back();
1107  NODE::OPT_OBSTACLE nearest;
1108  SHOVE_STATUS st = SH_NULL;
1109 
1110 #ifdef DEBUG
1111  Dbg()->SetIteration( aIter );
1112 #endif
1113 
1114  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1115  {
1116  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1117 
1118  if( nearest )
1119  break;
1120  }
1121 
1122  if( !nearest )
1123  {
1124  m_lineStack.pop_back();
1125  return SH_OK;
1126  }
1127 
1128  ITEM* ni = nearest->m_item;
1129 
1130  unwindLineStack( ni );
1131 
1132  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1133  {
1134  // Collision with a higher-ranking object (ie: one that we've already shoved)
1135  //
1136  switch( ni->Kind() )
1137  {
1138  case ITEM::VIA_T:
1139  {
1140  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1141 
1142  if( currentLine.EndsWithVia() )
1143  {
1144  st = SH_INCOMPLETE;
1145  }
1146  else
1147  {
1148  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1149  }
1150 
1151  break;
1152  }
1153 
1154  case ITEM::SEGMENT_T:
1155  {
1156  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1157  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1158 
1159  popLineStack();
1160  st = onCollidingLine( revLine, currentLine );
1161  if( !pushLineStack( revLine ) )
1162  return SH_INCOMPLETE;
1163 
1164  break;
1165  }
1166 
1167  case ITEM::ARC_T:
1168  {
1169  //TODO(snh): Handle Arc shove separate from track
1170  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1171  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1172 
1173  popLineStack();
1174  st = onCollidingLine( revLine, currentLine );
1175  if( !pushLineStack( revLine ) )
1176  return SH_INCOMPLETE;
1177 
1178  break;
1179  }
1180 
1181  default:
1182  assert( false );
1183  }
1184  }
1185  else
1186  {
1187  // Collision with a lower-ranking object or a solid
1188  //
1189  switch( ni->Kind() )
1190  {
1191  case ITEM::SEGMENT_T:
1192  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1193 
1194  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1195 
1196  if( st == SH_TRY_WALK )
1197  st = onCollidingSolid( currentLine, ni );
1198 
1199  break;
1200 
1201  //TODO(snh): Customize Arc collide
1202  case ITEM::ARC_T:
1203  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1204 
1205  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1206 
1207  if( st == SH_TRY_WALK )
1208  st = onCollidingSolid( currentLine, ni );
1209 
1210  break;
1211 
1212  case ITEM::VIA_T:
1213  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1214  st = onCollidingVia( &currentLine, (VIA*) ni );
1215 
1216  if( st == SH_TRY_WALK )
1217  st = onCollidingSolid( currentLine, ni );
1218 
1219  break;
1220 
1221  case ITEM::SOLID_T:
1222  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1223  st = onCollidingSolid( currentLine, (SOLID*) ni );
1224  break;
1225 
1226  default:
1227  break;
1228  }
1229  }
1230 
1231  return st;
1232 }
1233 
1234 
1235 /*
1236  * Resolve collisions.
1237  * Each iteration pushes the next colliding object out of the way. Iterations are continued as
1238  * long as they propagate further collisions, or until the iteration timeout or max iteration
1239  * count is reached.
1240  */
1242 {
1243  SHOVE_STATUS st = SH_OK;
1244 
1246 
1247  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1249 
1250  int iterLimit = Settings().ShoveIterationLimit();
1251  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1252 
1253  m_iter = 0;
1254 
1255  timeLimit.Restart();
1256 
1257  if( m_lineStack.empty() && m_draggedVia )
1258  {
1259  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1260  // the stack.
1262  }
1263 
1264  while( !m_lineStack.empty() )
1265  {
1266  st = shoveIteration( m_iter );
1267 
1268  m_iter++;
1269 
1270  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1271  {
1272  st = SH_INCOMPLETE;
1273  break;
1274  }
1275  }
1276 
1277  return st;
1278 }
1279 
1280 
1282 {
1283  OPT_BOX2I area;
1284 
1285  if( !m_nodeStack.empty() )
1286  area = m_nodeStack.back().m_affectedArea;
1287 
1288  if( area && m_affectedArea)
1289  area->Merge( *m_affectedArea );
1290  else if( !area )
1291  area = m_affectedArea;
1292 
1293  return area;
1294 }
1295 
1296 
1298 {
1299  SHOVE_STATUS st = SH_OK;
1300 
1301  m_multiLineMode = false;
1302 
1303  if( Dbg() )
1304  {
1305  Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
1306  }
1307 
1308  // empty head? nothing to shove...
1309 
1310  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1311  return SH_INCOMPLETE;
1312 
1313  LINE head( aCurrentHead );
1314  head.ClearLinks();
1315 
1316  m_lineStack.clear();
1317  m_optimizerQueue.clear();
1318  m_newHead = OPT_LINE();
1319 #if 0
1320  m_logger.Clear();
1321 #endif
1322 
1323  // Pop NODEs containing previous shoves which are no longer necessary
1324  //
1325  ITEM_SET headSet;
1326  headSet.Add( aCurrentHead );
1327 
1328  VIA_HANDLE dummyVia;
1329 
1330  NODE* parent = reduceSpringback( headSet, dummyVia );
1331 
1332  // Create a new NODE to store this version of the world
1333  //
1334  m_currentNode = parent->Branch();
1336  m_currentNode->Add( head );
1337 
1338  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1339 
1340  if( !head.EndsWithVia() )
1341  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1342 
1343  head.Mark( MK_HEAD );
1344  head.SetRank( 100000 );
1345 
1346  if ( Dbg() )
1347  {
1348 
1349  Dbg()->BeginGroup( "initial" );
1350  Dbg()->AddLine(head.CLine(), 5, head.Width(), "head" );
1351  Dbg()->EndGroup();
1352  }
1353 
1354  if( head.EndsWithVia() )
1355  {
1356  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1357  headVia->Mark( MK_HEAD );
1358  headVia->SetRank( 100000 );
1359  m_currentNode->Add( std::move( headVia ) );
1360  }
1361 
1362  if( !pushLineStack( head ) )
1363  {
1364  delete m_currentNode;
1365  m_currentNode = parent;
1366 
1367  return SH_INCOMPLETE;
1368  }
1369 
1370  st = shoveMainLoop();
1371 
1372  if( st == SH_OK )
1373  {
1375 
1376  if( m_newHead )
1378  else
1379  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1380  }
1381 
1383 
1384  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1385  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1386 
1387  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1388  {
1390  }
1391  else
1392  {
1393  delete m_currentNode;
1394 
1395  m_currentNode = parent;
1396  m_newHead = OPT_LINE();
1397  }
1398 
1399  if(m_newHead)
1400  m_newHead->Unmark();
1401 
1402  if( m_newHead && head.EndsWithVia() )
1403  {
1404  VIA v = head.Via();
1405  v.SetPos( m_newHead->CPoint( -1 ) );
1406  m_newHead->AppendVia(v);
1407  }
1408 
1409  return st;
1410 }
1411 
1412 
1414 {
1415  SHOVE_STATUS st = SH_OK;
1416 
1417  m_multiLineMode = true;
1418 
1419  ITEM_SET headSet;
1420 
1421  for( const ITEM* item : aHeadSet.CItems() )
1422  {
1423  const LINE* headOrig = static_cast<const LINE*>( item );
1424 
1425  // empty head? nothing to shove...
1426  if( !headOrig->SegmentCount() )
1427  return SH_INCOMPLETE;
1428 
1429  headSet.Add( *headOrig );
1430  }
1431 
1432  m_lineStack.clear();
1433  m_optimizerQueue.clear();
1434 #if 0
1435  m_logger.Clear();
1436 #endif
1437 
1438  VIA_HANDLE dummyVia;
1439 
1440  NODE* parent = reduceSpringback( headSet, dummyVia );
1441 
1442  m_currentNode = parent->Branch();
1444  int n = 0;
1445 
1446  for( const ITEM* item : aHeadSet.CItems() )
1447  {
1448  const LINE* headOrig = static_cast<const LINE*>( item );
1449  LINE head( *headOrig );
1450  head.ClearLinks();
1451 
1452  m_currentNode->Add( head );
1453 
1454  head.Mark( MK_HEAD );
1455  head.SetRank( 100000 );
1456  n++;
1457 
1458  if( !pushLineStack( head ) )
1459  return SH_INCOMPLETE;
1460 
1461  if( head.EndsWithVia() )
1462  {
1463  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1464  headVia->Mark( MK_HEAD );
1465  headVia->SetRank( 100000 );
1466  m_currentNode->Add( std::move( headVia ) );
1467  }
1468  }
1469 
1470  st = shoveMainLoop();
1471 
1472  if( st == SH_OK )
1474 
1476 
1477  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1478  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1479 
1480  if( st == SH_OK )
1481  {
1483  }
1484  else
1485  {
1486  delete m_currentNode;
1487  m_currentNode = parent;
1488  }
1489 
1490  return st;
1491 }
1492 
1493 static VIA* findViaByHandle ( NODE *aNode, const VIA_HANDLE& handle )
1494 {
1495  JOINT* jt = aNode->FindJoint( handle.pos, handle.layers.Start(), handle.net );
1496 
1497  if( !jt )
1498  return nullptr;
1499 
1500  for( ITEM* item : jt->LinkList() )
1501  {
1502  if( item->OfKind( ITEM::VIA_T ) )
1503  {
1504  if( item->Net() == handle.net && item->Layers().Overlaps(handle.layers) )
1505  return static_cast<VIA*>( item );
1506  }
1507  }
1508 
1509  return nullptr;
1510 }
1511 
1513 {
1514  SHOVE_STATUS st = SH_OK;
1515 
1516  m_lineStack.clear();
1517  m_optimizerQueue.clear();
1518  m_newHead = OPT_LINE();
1519  m_draggedVia = NULL;
1520 
1521  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1522 
1523  if( !viaToDrag )
1524  return SH_INCOMPLETE;
1525 
1526  // Pop NODEs containing previous shoves which are no longer necessary
1527  ITEM_SET headSet;
1528 
1529  VIA headVia ( *viaToDrag );
1530  headVia.SetPos( aWhere );
1531  headSet.Add( headVia );
1532  VIA_HANDLE prevViaHandle;
1533  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1534 
1535  if( prevViaHandle.valid )
1536  {
1537  aNewVia = prevViaHandle;
1538  viaToDrag = findViaByHandle( parent, prevViaHandle );
1539  }
1540 
1541  // Create a new NODE to store this version of the world
1542  //
1543  m_currentNode = parent->Branch();
1545 
1546  viaToDrag->Mark( MK_HEAD );
1547  viaToDrag->SetRank( 100000 );
1548 
1549  // Push the via to its new location
1550  //
1551  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1552 
1553  // Shove any colliding objects out of the way
1554  //
1555  if( st == SH_OK )
1556  st = shoveMainLoop();
1557 
1558  if( st == SH_OK )
1560 
1561  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1562  {
1563  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1564 
1565  if (!m_draggedVia)
1566  m_draggedVia = viaToDrag;
1567 
1568  aNewVia = m_draggedVia->MakeHandle();
1569 
1571  }
1572  else
1573  {
1574  delete m_currentNode;
1575  m_currentNode = parent;
1576  }
1577 
1578  return st;
1579 }
1580 
1581 
1583 {
1584  OPTIMIZER optimizer( aNode );
1585  int optFlags = 0;
1586  int n_passes = 0;
1587 
1589 
1590  OPT_BOX2I area = totalAffectedArea();
1591 
1592  int maxWidth = 0;
1593 
1594  for( LINE& line : m_optimizerQueue )
1595  maxWidth = std::max( line.Width(), maxWidth );
1596 
1597  if( area )
1598  {
1599  area->Inflate( maxWidth );
1600  area = area->Intersect( VisibleViewArea() );
1601  }
1602 
1603  switch( effort )
1604  {
1605  case OE_LOW:
1606  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1607  n_passes = 1;
1608  break;
1609 
1610  case OE_MEDIUM:
1611  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1612 
1613  n_passes = 2;
1614  break;
1615 
1616  case OE_FULL:
1617  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1618  n_passes = 2;
1619  break;
1620 
1621  default:
1622  break;
1623  }
1624 
1625  if( area )
1626  {
1627  if( Dbg() )
1628  {
1629  Dbg()->AddBox( *area, 1, "opt-area" );
1630  }
1631 
1632  optFlags |= OPTIMIZER::RESTRICT_AREA;
1633  optimizer.SetRestrictArea( *area, false );
1634  }
1635 
1636  if( Settings().SmartPads() )
1637  optFlags |= OPTIMIZER::SMART_PADS;
1638 
1639  optimizer.SetEffortLevel( optFlags );
1640  optimizer.SetCollisionMask( ITEM::ANY_T );
1641 
1642  for( int pass = 0; pass < n_passes; pass++ )
1643  {
1644  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1645 
1646  for( LINE& line : m_optimizerQueue)
1647  {
1648  if( !( line.Marker() & MK_HEAD ) )
1649  {
1650  LINE optimized;
1651 
1652  if( optimizer.Optimize( &line, &optimized ) )
1653  {
1654  aNode->Remove( line );
1655  line.SetShape( optimized.CLine() );
1656  aNode->Add( line );
1657  }
1658  }
1659  }
1660  }
1661 }
1662 
1663 
1665 {
1666  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1667 }
1668 
1669 
1670 const LINE SHOVE::NewHead() const
1671 {
1672  assert( m_newHead );
1673 
1674  return *m_newHead;
1675 }
1676 
1677 
1678 void SHOVE::SetInitialLine( LINE& aInitial )
1679 {
1680  m_root = m_root->Branch();
1681  m_root->Remove( aInitial );
1682 }
1683 
1684 
1686 {
1687  SPRINGBACK_TAG sp;
1688  sp.m_node = aNode;
1689  sp.m_locked = true;
1690 
1691  m_nodeStack.push_back(sp);
1692  return true;
1693 }
1694 
1695 
1697 {
1698  bool found = false;
1699 
1700  auto iter = m_nodeStack.begin();
1701 
1702  while( iter != m_nodeStack.end() )
1703  {
1704  if ( iter->m_node == aNode )
1705  {
1706  found = true;
1707  break;
1708  }
1709  iter++;
1710  }
1711 
1712  if( !found )
1713  return false;
1714 
1715  auto start = iter;
1716 
1717  aNode->KillChildren();
1718  m_nodeStack.erase( start, m_nodeStack.end() );
1719 
1720  return true;
1721 }
1722 
1723 
1725 {
1726  auto iter = m_nodeStack.begin();
1727 
1728  while( iter != m_nodeStack.end() )
1729  {
1730  if ( iter->m_node == aNode )
1731  {
1732  iter->m_locked = false;
1733  break;
1734  }
1735  iter++;
1736  }
1737 }
1738 
1739 }
1740 
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1327
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
virtual void SetIteration(int iter)
Base class for PNS router board items.
Definition: pns_item.h:55
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:285
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
long long int Length() const
Function Length()
virtual void AddBox(BOX2I aB, int aColor, const std::string aName="")
void popLineStack()
Definition: pns_shove.cpp:1075
int m_restrictSpringbackTagId
Definition: pns_shove.h:166
virtual int Layer() const
Definition: pns_item.h:154
Keep the router "world" - i.e.
Definition: pns_node.h:149
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
VECTOR2I::extended_type ecoord
Definition: pns_shove.cpp:45
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:567
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1022
virtual void Mark(int aMarker) const
Definition: pns_item.h:206
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
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).
int SegmentCount() const
Definition: pns_line.h:139
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:120
const LINE NewHead() const
Definition: pns_shove.cpp:1670
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:199
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:463
int Rank() const override
Definition: pns_line.cpp:893
Base class for all P&S algorithms (shoving, walkaround, line placement, dragging, etc....
Definition: pns_algo_base.h:42
void SetRestrictArea(const BOX2I &aArea, bool aStrict=true)
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
bool RewindSpringbackTo(NODE *aNode)
Definition: pns_shove.cpp:1696
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
void SetSingleDirection(bool aForceSingleDirection)
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:188
void RemoveVia()
Definition: pns_line.h:194
NODE * m_root
Definition: pns_shove.h:164
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
Definition: sch_symbol.cpp:69
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:870
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
const SEG & Seg() const
Definition: pns_segment.h:84
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:312
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:299
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:106
int PointCount() const
Function PointCount()
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:758
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_via.h:124
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
const VECTOR2I & Pos() const
Definition: pns_via.h:96
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:165
bool EndsWithVia() const
Definition: pns_line.h:191
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:804
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:526
int Start() const
Definition: pns_layerset.h:82
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:159
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:939
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
void SetCollisionMask(int aMask)
const std::set< ITEM * > AssembleCluster(ITEM *aStart, int aLayer)
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
bool IsLinkedChecked() const
Assign a shape to the line (a polyline/line chain).
Definition: pns_line.h:120
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1281
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:693
const SHAPE * Shape() const override
Modifiable accessor to the underlying shape.
Definition: pns_line.h:133
SHOVE_STATUS ShoveLines(const LINE &aCurrentHead)
Definition: pns_shove.cpp:1297
const VECTOR2I & CPoint(int aIndex) const
Function Point()
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
Definition: pns_joint.h:42
int Diameter() const
Definition: pns_via.h:107
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:97
void KillChildren()
Definition: pns_node.cpp:1292
bool AddLockedSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1685
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:912
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:885
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1582
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:93
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1104
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:196
int Net() const
Definition: pns_item.h:148
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1493
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
void RestrictToSet(bool aEnabled, const std::set< ITEM * > &aSet)
SHOVE(NODE *aWorld, ROUTER *aRouter)
Definition: pns_shove.cpp:100
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:97
virtual SHAPE * Clone() const
Return a dynamically allocated copy of the shape.
Definition: shape.h:139
void SetSolidsOnly(bool aSolidsOnly)
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:721
virtual void SetRank(int aRank)
Definition: pns_item.h:210
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:396
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
const std::string Format() const override
void SetRank(int aRank) override
Definition: pns_line.cpp:883
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
void UnlockSpringbackNode(NODE *aNode)
Definition: pns_shove.cpp:1724
virtual void AddSegment(SEG aS, int aColor, const std::string aName="")
void Clear()
Definition: pns_logger.cpp:47
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1027
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
SHOVE_STATUS ShoveDraggingVia(const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
Definition: pns_shove.cpp:1512
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:98
virtual void Message(const wxString msg)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:769
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1337
virtual void BeginGroup(const std::string name)
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
const BOX2I & VisibleViewArea() const
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
VIA * m_draggedVia
Definition: pns_shove.h:171
virtual int Rank() const
Definition: pns_item.h:211
virtual int Marker() const override
Definition: pns_line.cpp:109
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:74
Reduce corner cost by merging obtuse segments.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
SHAPE_LINE_CHAIN.
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:427
const SHAPE_LINE_CHAIN CLine() const
Definition: pns_arc.h:93
bool HasLoops() const
Definition: pns_line.cpp:979
LAYER_RANGE layers
Definition: pns_via.h:44
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:134
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
const ENTRIES & CItems() const
Definition: pns_itemset.h:139
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1241
bool IsLocked() const
Definition: pns_item.h:223
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
void SetInitialLine(LINE &aInitial)
Definition: pns_shove.cpp:1678
boost::optional< T > OPT
Definition: optional.h:7
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
VECTOR2I pos
Definition: pns_via.h:43
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:126
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
void Clear()
Function Clear() Removes all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:152
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:76
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:84
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:49
void SetEffortLevel(int aEffort)
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
SHOVE_STATUS ShoveMultiLines(const ITEM_SET &aHeadSet)
Definition: pns_shove.cpp:1413
NODE * m_currentNode
Definition: pns_shove.h:165
const VIA & Via() const
Definition: pns_line.h:196
int Drill() const
Definition: pns_via.h:115
Push and Shove diff pair dimensions (gap) settings dialog.
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
bool Expired() const
Definition: time_limit.cpp:39
LOGGER m_logger
Definition: pns_shove.h:170
int m_iter
Definition: pns_shove.h:173
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:154
void AddShape(SHAPE *aShape)
NODE * CurrentNode()
Definition: pns_shove.cpp:1664
void SetIterationLimit(const int aIterLimit)
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057
virtual int Marker() const
Definition: pns_item.h:208
int m_forceClearance
Definition: pns_shove.h:174
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:100
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
Reroute pad exits.
bool HasLockedSegments() const
Definition: pns_line.cpp:1089
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:90
TIME_LIMIT ShoveTimeLimit() const