KiCad PCB EDA Suite
pns_line_placer.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2017 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 <core/optional.h>
23 
24 #include "pns_node.h"
25 #include "pns_line_placer.h"
26 #include "pns_walkaround.h"
27 #include "pns_shove.h"
28 #include "pns_utils.h"
29 #include "pns_router.h"
30 #include "pns_topology.h"
31 #include "pns_debug_decorator.h"
32 
33 #include <class_board_item.h>
34 
35 namespace PNS {
36 
38  PLACEMENT_ALGO( aRouter )
39 {
41  m_world = NULL;
42  m_shove = NULL;
43  m_currentNode = NULL;
44  m_idle = true;
45 
46  // Init temporary variables (do not leave uninitialized members)
47  m_lastNode = NULL;
48  m_placingVia = false;
49  m_currentNet = 0;
50  m_currentLayer = 0;
52  m_startItem = NULL;
53  m_chainedPlacement = false;
54  m_orthoMode = false;
55 }
56 
57 
59 {
60 }
61 
62 
63 void LINE_PLACER::setWorld( NODE* aWorld )
64 {
65  m_world = aWorld;
66 }
67 
68 
69 const VIA LINE_PLACER::makeVia( const VECTOR2I& aP )
70 {
72 
73  return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
74 }
75 
76 
77 bool LINE_PLACER::ToggleVia( bool aEnabled )
78 {
79  m_placingVia = aEnabled;
80 
81  if( !aEnabled )
82  m_head.RemoveVia();
83 
84  return true;
85 }
86 
87 
89 {
90  m_initial_direction = aDirection;
91 
92  if( m_tail.SegmentCount() == 0 )
93  m_direction = aDirection;
94 }
95 
96 
98 {
100  SHAPE_LINE_CHAIN& head = m_head.Line();
101  SHAPE_LINE_CHAIN& tail = m_tail.Line();
102 
103  // if there is no tail, there is nothing to intersect with
104  if( tail.PointCount() < 2 )
105  return false;
106 
107  tail.Intersect( head, ips );
108 
109  // no intesection points - nothing to reduce
110  if( ips.empty() )
111  return false;
112 
113  int n = INT_MAX;
114  VECTOR2I ipoint;
115 
116  // if there is more than one intersection, find the one that is
117  // closest to the beginning of the tail.
118  for( SHAPE_LINE_CHAIN::INTERSECTION i : ips )
119  {
120  if( i.our.Index() < n )
121  {
122  n = i.our.Index();
123  ipoint = i.p;
124  }
125  }
126 
127  // ignore the point where head and tail meet
128  if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
129  return false;
130 
131  // Intersection point is on the first or the second segment: just start routing
132  // from the beginning
133  if( n < 2 )
134  {
135  m_p_start = tail.Point( 0 );
137  tail.Clear();
138  head.Clear();
139 
140  return true;
141  }
142  else
143  {
144  // Clip till the last tail segment before intersection.
145  // Set the direction to the one of this segment.
146  const SEG last = tail.CSegment( n - 1 );
147  m_p_start = last.A;
148  m_direction = DIRECTION_45( last );
149  tail.Remove( n, -1 );
150  return true;
151  }
152 
153  return false;
154 }
155 
156 
158 {
159  SHAPE_LINE_CHAIN& head = m_head.Line();
160  SHAPE_LINE_CHAIN& tail = m_tail.Line();
161 
162  if( head.PointCount() < 2 )
163  return false;
164 
165  int n = tail.PointCount();
166 
167  if( n == 0 )
168  return false;
169  else if( n == 1 )
170  {
171  m_p_start = tail.CPoint( 0 );
172  tail.Clear();
173  return true;
174  }
175 
176  DIRECTION_45 first_head( head.CSegment( 0 ) );
177  DIRECTION_45 last_tail( tail.CSegment( -1 ) );
178  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
179 
180  // case 1: we have a defined routing direction, and the currently computed
181  // head goes in different one.
182  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
183 
184  // case 2: regardless of the current routing direction, if the tail/head
185  // extremities form an acute or right angle, reduce the tail by one segment
186  // (and hope that further iterations) will result with a cleaner trace
187  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
188 
189  if( pullback_1 || pullback_2 )
190  {
191  const SEG last = tail.CSegment( -1 );
192  m_direction = DIRECTION_45( last );
193  m_p_start = last.A;
194 
195  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
196  n, last_tail.Format().c_str(), first_head.Format().c_str() );
197 
198  // erase the last point in the tail, hoping that the next iteration will
199  // result with a head trace that starts with a segment following our
200  // current direction.
201  if( n < 2 )
202  tail.Clear(); // don't leave a single-point tail
203  else
204  tail.Remove( -1, -1 );
205 
206  if( !tail.SegmentCount() )
208 
209  return true;
210  }
211 
212  return false;
213 }
214 
215 
217 {
218  SHAPE_LINE_CHAIN& head = m_head.Line();
219  SHAPE_LINE_CHAIN& tail = m_tail.Line();
220 
221  int n = tail.SegmentCount();
222 
223  if( head.SegmentCount() < 1 )
224  return false;
225 
226  // Don't attempt this for too short tails
227  if( n < 2 )
228  return false;
229 
230  // Start from the segment farthest from the end of the tail
231  // int start_index = std::max(n - 1 - ReductionDepth, 0);
232 
233  DIRECTION_45 new_direction;
234  VECTOR2I new_start;
235  int reduce_index = -1;
236 
237  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
238  {
239  const SEG s = tail.CSegment( i );
240  DIRECTION_45 dir( s );
241 
242  // calculate a replacement route and check if it matches
243  // the direction of the segment to be replaced
244  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
245 
246  LINE tmp( m_tail, replacement );
247 
249  break;
250 
251  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
252  {
253  new_start = s.A;
254  new_direction = dir;
255  reduce_index = i;
256  }
257  }
258 
259  if( reduce_index >= 0 )
260  {
261  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
262  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
263 
264  m_p_start = new_start;
265  m_direction = new_direction;
266  tail.Remove( reduce_index + 1, -1 );
267  head.Clear();
268  return true;
269  }
270 
271  if( !tail.SegmentCount() )
273 
274  return false;
275 }
276 
277 
278 bool LINE_PLACER::checkObtusity( const SEG& aA, const SEG& aB ) const
279 {
280  const DIRECTION_45 dir_a( aA );
281  const DIRECTION_45 dir_b( aB );
282 
283  return dir_a.IsObtuse( dir_b ) || dir_a == dir_b;
284 }
285 
286 
288 {
289  SHAPE_LINE_CHAIN& head = m_head.Line();
290  SHAPE_LINE_CHAIN& tail = m_tail.Line();
291 
292  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE |
295 
296  head.Simplify();
297  tail.Simplify();
298 
299  int n_head = head.SegmentCount();
300  int n_tail = tail.SegmentCount();
301 
302  if( n_head < 3 )
303  {
304  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
305  return false;
306  }
307 
308  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
309  {
310  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
311  return false;
312  }
313 
314  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
315  return false;
316 
317  DIRECTION_45 dir_tail, dir_head;
318 
319  dir_head = DIRECTION_45( head.CSegment( 0 ) );
320 
321  if( n_tail )
322  {
323  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
324 
325  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
326  return false;
327  }
328 
329  if( !n_tail )
330  tail.Append( head.CSegment( 0 ).A );
331 
332  for( int i = 0; i < n_head - 2; i++ )
333  {
334  tail.Append( head.CSegment( i ).B );
335  }
336 
337  tail.Simplify();
338 
339  SEG last = tail.CSegment( -1 );
340 
341  m_p_start = last.B;
342  m_direction = DIRECTION_45( last ).Right();
343 
344  head.Remove( 0, n_head - 2 );
345 
346  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head, m_direction.Format().c_str() );
347 
348  head.Simplify();
349  tail.Simplify();
350 
351  return true;
352 }
353 
354 
355 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
356 {
357  LINE initTrack( m_head );
358  LINE walkFull;
359  int effort = 0;
360  bool rv = true, viaOk;
361 
362  viaOk = buildInitialLine( aP, initTrack );
363 
364  WALKAROUND walkaround( m_currentNode, Router() );
365 
366  walkaround.SetSolidsOnly( false );
367  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
368 
369  WALKAROUND::WALKAROUND_STATUS wf = walkaround.Route( initTrack, walkFull, false );
370 
371  switch( Settings().OptimizerEffort() )
372  {
373  case OE_LOW:
374  effort = 0;
375  break;
376 
377  case OE_MEDIUM:
378  case OE_FULL:
379  effort = OPTIMIZER::MERGE_SEGMENTS;
380  break;
381  }
382 
383  if( Settings().SmartPads() )
384  effort |= OPTIMIZER::SMART_PADS;
385 
386  if( wf == WALKAROUND::STUCK )
387  {
388  walkFull = walkFull.ClipToNearestObstacle( m_currentNode );
389  rv = true;
390  }
391  else if( m_placingVia && viaOk )
392  {
393  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
394  }
395 
396  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
397 
398  if( m_currentNode->CheckColliding( &walkFull ) )
399  {
400  aNewHead = m_head;
401  return false;
402  }
403 
404  m_head = walkFull;
405  aNewHead = walkFull;
406 
407  return rv;
408 }
409 
410 
411 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
412 {
413  buildInitialLine( aP, m_head );
414 
415  auto obs = m_currentNode->NearestObstacle( &m_head );
416 
417  if( obs )
418  {
419  int cl = m_currentNode->GetClearance( obs->m_item, &m_head );
420  auto hull = obs->m_item->Hull( cl, m_head.Width() );
421 
422  auto nearest = hull.NearestPoint( aP );
423  Dbg()->AddLine( hull, 2, 10000 );
424 
425  if( ( nearest - aP ).EuclideanNorm() < m_head.Width() )
426  {
427  buildInitialLine( nearest, m_head );
428  }
429  }
430 
431  aNewHead = m_head;
432 
433  return static_cast<bool>( m_currentNode->CheckColliding( &m_head ) );
434 }
435 
436 
437 const LINE LINE_PLACER::reduceToNearestObstacle( const LINE& aOriginalLine )
438 {
439  auto l0 = aOriginalLine.CLine();
440 
441  if ( !l0.PointCount() )
442  return aOriginalLine;
443 
444  int l = l0.Length();
445  int step = l / 2;
446  VECTOR2I target;
447 
448  LINE l_test( aOriginalLine );
449 
450  while( step > 0 )
451  {
452  target = l0.PointAlong( l );
453  SHAPE_LINE_CHAIN l_cur( l0 );
454 
455  int index = l_cur.Split( target );
456 
457  l_test.SetShape( l_cur.Slice( 0, index ) );
458 
459  if ( m_currentNode->CheckColliding( &l_test ) )
460  l -= step;
461  else
462  l += step;
463 
464  step /= 2;
465  }
466 
467  l = l_test.CLine().Length();
468 
469  while( m_currentNode->CheckColliding( &l_test ) && l > 0 )
470  {
471  l--;
472  target = l0.PointAlong( l );
473  SHAPE_LINE_CHAIN l_cur( l0 );
474 
475  int index = l_cur.Split( target );
476 
477  l_test.SetShape( l_cur.Slice( 0, index ) );
478  }
479 
480  return l_test;
481 }
482 
483 
485 {
486  LINE l0;
487  l0 = m_head;
488 
489  buildInitialLine( aP, l0 );
490 
491  LINE l_cur = reduceToNearestObstacle( l0 );
492 
493  const auto l_shape = l_cur.CLine();
494 
495  if( l_shape.SegmentCount() == 0 )
496  {
497  return false;
498  }
499 
500  if( l_shape.SegmentCount() == 1 )
501  {
502  auto s = l_shape.CSegment( 0 );
503 
504  VECTOR2I dL( DIRECTION_45( s ).Left().ToVector() );
505  VECTOR2I dR( DIRECTION_45( s ).Right().ToVector() );
506 
507  SEG leadL( s.B, s.B + dL );
508  SEG leadR( s.B, s.B + dR );
509 
510  SEG segL( s.B, leadL.LineProject( aP ) );
511  SEG segR( s.B, leadR.LineProject( aP ) );
512 
513  LINE finishL( l0, SHAPE_LINE_CHAIN( segL.A, segL.B ) );
514  LINE finishR( l0, SHAPE_LINE_CHAIN( segR.A, segR.B ) );
515 
516  LINE reducedL = reduceToNearestObstacle( finishL );
517  LINE reducedR = reduceToNearestObstacle( finishR );
518 
519  int lL = reducedL.CLine().Length();
520  int lR = reducedR.CLine().Length();
521 
522  if( lL > lR )
523  l_cur.Line().Append( reducedL.CLine() );
524  else
525  l_cur.Line().Append( reducedR.CLine() );
526 
527  l_cur.Line().Simplify();
528  }
529 
530  m_head = l_cur;
531  aNewHead = m_head;
532  return true;
533 }
534 
535 
536 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
537 {
538  LINE initTrack( m_head );
539  LINE walkSolids, l2;
540 
541  bool viaOk = buildInitialLine( aP, initTrack );
542 
543  m_currentNode = m_shove->CurrentNode();
544  OPTIMIZER optimizer( m_currentNode );
545 
546  WALKAROUND walkaround( m_currentNode, Router() );
547 
548  walkaround.SetSolidsOnly( true );
549  walkaround.SetIterationLimit( 10 );
550  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
551 
553  optimizer.SetCollisionMask( ITEM::SOLID_T );
554  optimizer.Optimize( &walkSolids );
555 
556  if( stat_solids == WALKAROUND::DONE )
557  l2 = walkSolids;
558  else
559  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
560 
561  LINE l( m_tail );
562  l.Line().Append( l2.CLine() );
563  l.Line().Simplify();
564 
565  if( l.PointCount() == 0 || l2.PointCount() == 0 )
566  {
567  aNewHead = m_head;
568  return false;
569  }
570 
571  if( m_placingVia && viaOk )
572  {
573  VIA v1( makeVia( l.CPoint( -1 ) ) );
574  VIA v2( makeVia( l2.CPoint( -1 ) ) );
575 
576  l.AppendVia( v1 );
577  l2.AppendVia( v2 );
578  }
579 
580  l.Line().Simplify();
581 
582  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't shove to avoid
583  // screwing up the database.
584  if( l.HasLoops() )
585  {
586  aNewHead = m_head;
587  return false;
588  }
589 
590  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
591 
592  m_currentNode = m_shove->CurrentNode();
593 
594  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
595  {
596  if( status == SHOVE::SH_HEAD_MODIFIED )
597  {
598  l2 = m_shove->NewHead();
599  }
600 
601  optimizer.SetWorld( m_currentNode );
603  optimizer.SetCollisionMask( ITEM::ANY_T );
604  optimizer.Optimize( &l2 );
605 
606  aNewHead = l2;
607 
608  return true;
609  }
610  else
611  {
612  walkaround.SetWorld( m_currentNode );
613  walkaround.SetSolidsOnly( false );
614  walkaround.SetIterationLimit( 10 );
615  walkaround.SetApproachCursor( true, aP );
616  walkaround.Route( initTrack, l2 );
617  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
618 
619  return false;
620  }
621 
622  return false;
623 }
624 
625 
626 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
627 {
628  switch( m_currentMode )
629  {
630  case RM_MarkObstacles:
631  return rhMarkObstacles( aP, aNewHead );
632  case RM_Walkaround:
633  return rhWalkOnly( aP, aNewHead );
634  case RM_Shove:
635  return rhShoveOnly( aP, aNewHead );
636  default:
637  break;
638  }
639 
640  return false;
641 }
642 
643 
645 {
646  LINE linetmp = Trace();
647 
649  {
650  if( linetmp.SegmentCount() < 1 )
651  return false;
652 
653  m_head = linetmp;
654  m_p_start = linetmp.CLine().CPoint( 0 );
655  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
656  m_tail.Line().Clear();
657 
658  return true;
659  }
660 
661  SHAPE_LINE_CHAIN& head = m_head.Line();
662  SHAPE_LINE_CHAIN& tail = m_tail.Line();
663 
664  int tailLookbackSegments = 3;
665 
666  //if(m_currentMode() == RM_Walkaround)
667  // tailLookbackSegments = 10000;
668 
669  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
670 
671  if( tail.SegmentCount() < 3 )
672  return false;
673 
674  // assemble TailLookbackSegments tail segments with the current head
675  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
676 
677  int end = std::min(2, head.PointCount() - 1 );
678 
679  opt_line.Append( head.Slice( 0, end ) );
680 
681  LINE new_head( m_tail, opt_line );
682 
683  // and see if it could be made simpler by merging obtuse/collnear segments.
684  // If so, replace the (threshold) last tail points and the head with
685  // the optimized line
686 
688  {
689  LINE tmp( m_tail, opt_line );
690 
691  wxLogTrace( "PNS", "Placer: optimize tail-head [%d]", threshold );
692 
693  head.Clear();
694  tail.Replace( -threshold, -1, new_head.CLine() );
695  tail.Simplify();
696 
697  m_p_start = new_head.CLine().CPoint( -1 );
698  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
699 
700  return true;
701  }
702 
703  return false;
704 }
705 
706 
708 {
709  bool fail = false;
710  bool go_back = false;
711 
712  int i, n_iter = 1;
713 
714  LINE new_head;
715 
716  wxLogTrace( "PNS", "INIT-DIR: %s head: %d, tail: %d segs",
718 
719  for( i = 0; i < n_iter; i++ )
720  {
721  if( !go_back && Settings().FollowMouse() )
722  reduceTail( aP );
723 
724  go_back = false;
725 
726  if( !routeHead( aP, new_head ) )
727  fail = true;
728 
729  if( !new_head.Is45Degree() )
730  fail = true;
731 
732  if( !Settings().FollowMouse() )
733  return;
734 
735  m_head = new_head;
736 
738  {
739  n_iter++;
740  go_back = true;
741  }
742 
743  if( !go_back && handlePullback() )
744  {
745  n_iter++;
746  go_back = true;
747  }
748  }
749 
750  if( !fail )
751  {
753  return;
754 
755  mergeHead();
756  }
757 }
758 
759 
760 bool LINE_PLACER::route( const VECTOR2I& aP )
761 {
762  routeStep( aP );
763  return CurrentEnd() == aP;
764 }
765 
766 
768 {
769  LINE tmp( m_head );
770 
771  tmp.SetShape( m_tail.CLine() );
772  tmp.Line().Append( m_head.CLine() );
773  tmp.Line().Simplify();
774  return tmp;
775 }
776 
777 
779 {
780  m_currentTrace = Trace();
781  return ITEM_SET( &m_currentTrace );
782 }
783 
784 
786 {
789 }
790 
791 
792 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
793 {
794  if( aLoopsRemoved && m_lastNode )
795  return m_lastNode;
796 
797  return m_currentNode;
798 }
799 
800 
801 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
802 {
803  if( !aSeg )
804  return false;
805 
806  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
807  return false;
808 
809  JOINT* jt = aNode->FindJoint( aP, aSeg );
810 
811  if( jt && jt->LinkCount() >= 1 )
812  return false;
813 
814  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
815 
816  std::unique_ptr< SEGMENT > s_new[2] = {
817  Clone( *s_old ),
818  Clone( *s_old )
819  };
820 
821  s_new[0]->SetEnds( s_old->Seg().A, aP );
822  s_new[1]->SetEnds( aP, s_old->Seg().B );
823 
824  aNode->Remove( s_old );
825  aNode->Add( std::move( s_new[0] ), true );
826  aNode->Add( std::move( s_new[1] ), true );
827 
828  return true;
829 }
830 
831 
832 bool LINE_PLACER::SetLayer( int aLayer )
833 {
834  if( m_idle )
835  {
836  m_currentLayer = aLayer;
837  return true;
838  }
839  else if( m_chainedPlacement )
840  {
841  return false;
842  }
843  else if( !m_startItem || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
844  {
845  m_currentLayer = aLayer;
846  initPlacement();
847  Move( m_currentEnd, NULL );
848  return true;
849  }
850 
851  return false;
852 }
853 
854 
855 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
856 {
857  VECTOR2I p( aP );
858 
859  static int unknowNetIdx = 0; // -10000;
860  int net = -1;
861 
862  if( !aStartItem || aStartItem->Net() < 0 )
863  net = unknowNetIdx--;
864  else
865  net = aStartItem->Net();
866 
867  m_currentStart = p;
868  m_currentEnd = p;
869  m_currentNet = net;
870  m_startItem = aStartItem;
871  m_placingVia = false;
872  m_chainedPlacement = false;
873 
874  setInitialDirection( Settings().InitialDirection() );
875 
876  initPlacement();
877  return true;
878 }
879 
880 
882 {
883  m_idle = false;
884 
885  m_head.Line().Clear();
886  m_tail.Line().Clear();
893  m_head.RemoveVia();
894  m_tail.RemoveVia();
895 
898 
899  NODE* world = Router()->GetWorld();
900 
901  world->KillChildren();
902  NODE* rootNode = world->Branch();
903 
905 
906  setWorld( rootNode );
907 
908  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
910 
911  m_lastNode = NULL;
914 
915  m_shove.reset();
916 
918  {
919  m_shove.reset( new SHOVE( m_world->Branch(), Router() ) );
920  }
921 }
922 
923 
924 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
925 {
926  LINE current;
927  VECTOR2I p = aP;
928  int eiDepth = -1;
929 
930  if( aEndItem && aEndItem->Owner() )
931  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
932 
933  if( m_lastNode )
934  {
935  delete m_lastNode;
936  m_lastNode = NULL;
937  }
938 
939  route( p );
940 
941  current = Trace();
942 
943  if( !current.PointCount() )
945  else
946  m_currentEnd = current.CLine().CPoint( -1 );
947 
948  NODE* latestNode = m_currentNode;
949  m_lastNode = latestNode->Branch();
950 
951  if( eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
952  {
953  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
954 
955  if( Settings().RemoveLoops() )
956  removeLoops( m_lastNode, current );
957  }
958 
960  return true;
961 }
962 
963 
964 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
965 {
966  bool realEnd = false;
967  int lastV;
968 
969  LINE pl = Trace();
970 
972  !Settings().CanViolateDRC() &&
973  m_world->CheckColliding( &pl ) )
974  return false;
975 
976  const SHAPE_LINE_CHAIN& l = pl.CLine();
977 
978  if( !l.SegmentCount() )
979  {
980  if( pl.EndsWithVia() )
981  {
982  m_lastNode->Add( Clone( pl.Via() ) );
984 
985  m_lastNode = NULL;
986  m_currentNode = NULL;
987 
988  m_idle = true;
989  }
990 
991  return true;
992  }
993 
994  VECTOR2I p_pre_last = l.CPoint( -1 );
995  const VECTOR2I p_last = l.CPoint( -1 );
996  DIRECTION_45 d_last( l.CSegment( -1 ) );
997 
998  if( l.PointCount() > 2 )
999  p_pre_last = l.CPoint( -2 );
1000 
1001  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1002  realEnd = true;
1003 
1004  if( realEnd || m_placingVia )
1005  lastV = l.SegmentCount();
1006  else
1007  lastV = std::max( 1, l.SegmentCount() - 1 );
1008 
1009  SEGMENT* lastSeg = NULL;
1010 
1011  for( int i = 0; i < lastV; i++ )
1012  {
1013  const SEG& s = pl.CSegment( i );
1014  std::unique_ptr< SEGMENT > seg( new SEGMENT( s, m_currentNet ) );
1015  seg->SetWidth( pl.Width() );
1016  seg->SetLayer( m_currentLayer );
1017  lastSeg = seg.get();
1018  m_lastNode->Add( std::move( seg ) );
1019  }
1020 
1021  if( pl.EndsWithVia() )
1022  m_lastNode->Add( Clone( pl.Via() ) );
1023 
1024  if( realEnd )
1025  simplifyNewLine( m_lastNode, lastSeg );
1026 
1028 
1029  m_lastNode = NULL;
1030  m_currentNode = NULL;
1031 
1032  if( !realEnd )
1033  {
1034  setInitialDirection( d_last );
1035  m_currentStart = m_placingVia ? p_last : p_pre_last;
1036  m_startItem = NULL;
1037  m_placingVia = false;
1039  initPlacement();
1040  }
1041  else
1042  {
1043  m_idle = true;
1044  }
1045 
1046  return realEnd;
1047 }
1048 
1049 
1050 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1051 {
1052  if( !aLatest.SegmentCount() )
1053  return;
1054 
1055  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1056  return;
1057 
1058  std::set<SEGMENT *> toErase;
1059  aNode->Add( aLatest, true );
1060 
1061  for( int s = 0; s < aLatest.LinkCount(); s++ )
1062  {
1063  SEGMENT* seg = aLatest.GetLink(s);
1064  LINE ourLine = aNode->AssembleLine( seg );
1065  JOINT a, b;
1066  std::vector<LINE> lines;
1067 
1068  aNode->FindLineEnds( ourLine, a, b );
1069 
1070  if( a == b )
1071  {
1072  aNode->FindLineEnds( aLatest, a, b );
1073  }
1074 
1075  aNode->FindLinesBetweenJoints( a, b, lines );
1076 
1077  int removedCount = 0;
1078  int total = 0;
1079 
1080  for( LINE& line : lines )
1081  {
1082  total++;
1083 
1084  if( !( line.ContainsSegment( seg ) ) && line.SegmentCount() )
1085  {
1086  for( SEGMENT *ss : line.LinkedSegments() )
1087  toErase.insert( ss );
1088 
1089  removedCount++;
1090  }
1091  }
1092 
1093  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1094  }
1095 
1096  for( SEGMENT *s : toErase )
1097  aNode->Remove( s );
1098 
1099  aNode->Remove( aLatest );
1100 }
1101 
1102 
1104 {
1105  LINE l = aNode->AssembleLine( aLatest );
1106  SHAPE_LINE_CHAIN simplified( l.CLine() );
1107 
1108  simplified.Simplify();
1109 
1110  if( simplified.PointCount() != l.PointCount() )
1111  {
1112  aNode->Remove( l );
1113  l.SetShape( simplified );
1114  aNode->Add( l );
1115  }
1116 }
1117 
1118 
1120 {
1121  m_sizes = aSizes;
1122 
1123  if( !m_idle )
1124  {
1125  initPlacement();
1126  }
1127 }
1128 
1129 
1131 {
1132  LINE current = Trace();
1133  SHAPE_LINE_CHAIN ratLine;
1134  TOPOLOGY topo( m_lastNode );
1135 
1136  if( topo.LeadingRatLine( &current, ratLine ) )
1137  Dbg()->AddLine( ratLine, 5, 10000 );
1138 }
1139 
1140 
1141 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1142 {
1143  m_orthoMode = aOrthoMode;
1144 }
1145 
1146 
1147 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aInvertPosture )
1148 {
1149  SHAPE_LINE_CHAIN l;
1150 
1151  if( m_p_start == aP )
1152  {
1153  l.Clear();
1154  }
1155  else
1156  {
1157  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1158  {
1159  l = SHAPE_LINE_CHAIN( m_p_start, aP );
1160  }
1161  else
1162  {
1163  if ( aInvertPosture )
1165  else
1167  }
1168 
1169  if( l.SegmentCount() > 1 && m_orthoMode )
1170  {
1171  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1172 
1173  l.Remove( -1, -1 );
1174  l.Point( 1 ) = newLast;
1175  }
1176  }
1177 
1178  aHead.SetShape( l );
1179 
1180  if( !m_placingVia )
1181  return true;
1182 
1183  VIA v( makeVia( aP ) );
1184  v.SetNet( aHead.Net() );
1185 
1187  {
1188  aHead.AppendVia( v );
1189  return true;
1190  }
1191 
1192  VECTOR2I force;
1193  VECTOR2I lead = aP - m_p_start;
1194 
1195  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1196 
1197  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1198  {
1199  SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force );
1200  aHead = LINE( aHead, line );
1201 
1202  v.SetPos( v.Pos() + force );
1203  return true;
1204  }
1205 
1206  return false; // via placement unsuccessful
1207 }
1208 
1209 
1210 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1211 {
1212  aNets.push_back( m_currentNet );
1213 }
1214 
1216 {
1217  if( m_shove )
1218  return m_shove->Logger();
1219 
1220  return NULL;
1221 }
1222 
1223 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:123
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem) override
Function FixRoute()
PNS_MODE Mode() const
Returns the routing mode.
Class ITEM.
Definition: pns_item.h:53
bool FollowMouse() const
Returns true if follow mouse mode is active (permanently on for the moment).
int Depth() const
Returns the number of nodes in the inheritance chain (wrs to the root node)
Definition: pns_node.h:180
int Split(const VECTOR2I &aP)
Function Split()
const VIA & Via() const
Definition: pns_line.h:253
const ITEM_SET Traces() override
Function Traces()
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
std::vector< INTERSECTION > INTERSECTIONS
Class NODE.
Definition: pns_node.h:137
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:302
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:207
VIATYPE_T ViaType() const
void routeStep(const VECTOR2I &aP)
Function routeStep()
Class SHOVE.
Definition: pns_shove.h:46
NODE * m_world
pointer to world to search colliding items
int PointCount() const
Function PointCount()
void SetLayer(int aLayer)
Function SetLayer()
Definition: pns_item.h:197
Classes BOARD_ITEM and BOARD_CONNECTED_ITEM.
void removeLoops(NODE *aNode, LINE &aLatest)
Function removeLoops()
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:70
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:832
Ignore collisions, mark obstacles
int FindLinesBetweenJoints(JOINT &aA, JOINT &aB, std::vector< LINE > &aLines)
finds all lines between a pair of joints. Used by the loop removal procedure.
Definition: pns_node.cpp:932
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:331
const LINE reduceToNearestObstacle(const LINE &aOriginalLine)
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
finds the joints corresponding to the ends of line aLine
Definition: pns_node.cpp:887
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
Definition: pns_via.cpp:31
LINE m_head
routing "head": volatile part of the track from the previously analyzed point to the current routing ...
void RemoveVia()
Definition: pns_line.h:251
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
route step, walkaround mode
SIZES_SETTINGS m_sizes
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
ROUTING_SETTINGS & Settings() const
Returns current router settings
void simplifyNewLine(NODE *aNode, SEGMENT *aLatest)
Function simplifyNewLine()
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:736
bool checkObtusity(const SEG &aA, const SEG &aB) const
Function checkObtusity()
bool reduceTail(const VECTOR2I &aEnd)
Function reduceTail()
const VECTOR2I & Pos() const
Definition: pns_via.h:88
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
SEGMENT * GetLink(int aIndex) const
Definition: pns_line.h:203
int Width() const
Returns line width
Definition: pns_line.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
NODE * GetWorld() const
Definition: pns_router.h:143
Class PLACEMENT_ALGO.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetWidth(int aWidth)
Sets line width
Definition: pns_line.h:153
void SetNet(int aNet)
Function SetNet()
Definition: pns_item.h:167
int PointCount() const
Returns the number of points in the line
Definition: pns_line.h:135
bool handlePullback()
Function handlePullback()
void SetCollisionMask(int aMask)
LINE_PLACER(ROUTER *aRouter)
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assigns a shape to the line (a polyline/line chain)
Definition: pns_line.h:105
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
int CountCorners(int aAngles) const
Returns the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:136
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0)
const SEG CSegment(int aIndex) const
Function CSegment()
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
Class JOINT.
Definition: pns_joint.h:43
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Function UpdateSizes()
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1225
void SetWorld(NODE *aNode)
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:205
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles ...
void setInitialDirection(const DIRECTION_45 &aDirection)
Function setInitialDirection()
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:129
Class DIRECTION_45.
Definition: direction45.h:33
LOGGER * Logger() override
Returns the logger object, allowing to dump geometry to a file.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Function SplitAdjacentSegments()
DIRECTION_45 m_direction
current routing direction
bool IsObtuse(const DIRECTION_45 &aOther) const
Function IsObtuse()
Definition: direction45.h:169
void initPlacement()
Function startPlacement()
bool EndsWithVia() const
Definition: pns_line.h:248
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aInvertPosture=false)
void updateLeadingRatLine()
Function updateLeadingRatLine()
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Function routeHead()
void SetSolidsOnly(bool aSolidsOnly)
bool handleSelfIntersections()
Function handleSelfIntersections()
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
bool route(const VECTOR2I &aP)
Function route()
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:49
std::unique_ptr< SHOVE > m_shove
The shove engine
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:68
NODE * Owner() const
Function Owner()
Definition: pns_item.h:259
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
route step, mark obstacles mode
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
route step, shove mode
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape
Definition: pns_line.h:117
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:93
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:367
Definition: seg.h:36
Only walkaround
NODE * m_currentNode
Current world state
bool Is45Degree() const
Definition: pns_line.cpp:271
const SEG CSegment(int aIdx) const
Returns the aIdx-th segment of the line
Definition: pns_line.h:147
AngleType
Enum AngleType Represents kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:59
bool RemoveLoops() const
Returns true if loop (redundant track) removal is on.
void setWorld(NODE *aWorld)
Function setWorld()
bool optimizeTailHeadTransition()
Function optimizeTailHeadTransition()
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:98
bool ToggleVia(bool aEnabled) override
Function ToggleVia()
void CommitRouting(NODE *aNode)
Definition: pns_router.cpp:326
void FlipPosture() override
Function FlipPosture()
#define max(a, b)
Definition: auxiliary.h:86
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
const std::string Format() const
Function Format() Formats the direction in a human readable word.
Definition: direction45.h:94
bool m_placingVia
Are we placing a via?
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:798
VECTOR2I A
Definition: seg.h:46
AngleType Angle(const DIRECTION_45 &aOther) const
Function Angle() Returns the type of angle between directions (this) and aOther.
Definition: direction45.h:146
const LINE ClipToNearestObstacle(NODE *aNode) const
Clips the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:297
int Net() const
Function Net()
Definition: pns_item.h:177
bool SetLayer(int aLayer) override
Function SetLayer()
const DIRECTION_45 Right() const
Function Right()
Definition: direction45.h:259
Class OPTIMIZER.
Definition: pns_optimizer.h:90
void Clear()
Function Clear() Removes all points from the line chain.
VECTOR2I m_p_start
current routing start point (end of tail, beginning of head)
const SEG & Seg() const
Definition: pns_segment.h:93
VECTOR2I & Point(int aIndex)
Function Point()
void SetWorld(NODE *aNode)
bool mergeHead()
Function mergeHead()
void SetEffortLevel(int aEffort)
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false) const
Function BuildInitialTrace()
Definition: direction45.h:199
bool rhStopAtNearestObstacle(const VECTOR2I &aP, LINE &aNewHead)
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
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 makeVia(const VECTOR2I &aP)
Push and Shove diff pair dimensions (gap) settings dialog.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
int LinkCount() const
Returns the number of segments that were assembled together to form this line.
Definition: pns_line.h:212
int SegmentCount() const
Function SegmentCount()
void SetIterationLimit(const int aIterLimit)
Class LAYER_RANGE.
Definition: pns_layerset.h:32
int Length() const
Function Length()
const LINE Trace() const
Function Trace()
#define min(a, b)
Definition: auxiliary.h:85
const VECTOR2I & CPoint(int aIdx) const
Returns the aIdx-th point of the line
Definition: pns_line.h:141
VECTOR2I B
Definition: seg.h:47