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