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