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