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  const 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  m_currentStart = VECTOR2I( aP );
858  m_currentEnd = VECTOR2I( aP );
859  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
860  m_startItem = aStartItem;
861  m_placingVia = false;
862  m_chainedPlacement = false;
863 
864  setInitialDirection( Settings().InitialDirection() );
865 
866  initPlacement();
867  return true;
868 }
869 
870 
872 {
873  m_idle = false;
874 
875  m_head.Line().Clear();
876  m_tail.Line().Clear();
883  m_head.RemoveVia();
884  m_tail.RemoveVia();
885 
888 
889  NODE* world = Router()->GetWorld();
890 
891  world->KillChildren();
892  NODE* rootNode = world->Branch();
893 
895 
896  setWorld( rootNode );
897 
898  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
900 
901  m_lastNode = NULL;
904 
905  m_shove.reset();
906 
908  {
909  m_shove.reset( new SHOVE( m_world->Branch(), Router() ) );
910  }
911 }
912 
913 
914 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
915 {
916  LINE current;
917  VECTOR2I p = aP;
918  int eiDepth = -1;
919 
920  if( aEndItem && aEndItem->Owner() )
921  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
922 
923  if( m_lastNode )
924  {
925  delete m_lastNode;
926  m_lastNode = NULL;
927  }
928 
929  route( p );
930 
931  current = Trace();
932 
933  if( !current.PointCount() )
935  else
936  m_currentEnd = current.CLine().CPoint( -1 );
937 
938  NODE* latestNode = m_currentNode;
939  m_lastNode = latestNode->Branch();
940 
941  if( eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
942  {
943  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
944 
945  if( Settings().RemoveLoops() )
946  removeLoops( m_lastNode, current );
947  }
948 
950  return true;
951 }
952 
953 
954 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
955 {
956  bool realEnd = false;
957  int lastV;
958 
959  LINE pl = Trace();
960 
962  {
963  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
964  // user has more responsibility and authority.
965 
966  if( aEndItem )
967  {
968  // The user has indicated a connection should be made. If either the
969  // trace or endItem is netless, then allow the connection by adopting the net of the other.
970  if( m_currentNet <= 0 )
971  {
972  m_currentNet = aEndItem->Net();
973  pl.SetNet( m_currentNet );
974  }
975  else if (aEndItem->Net() <= 0 )
976  aEndItem->SetNet( m_currentNet );
977  }
978 
979  // Collisions still prevent fixing unless "Allow DRC violations" is checked
980  if( !Settings().CanViolateDRC() && m_world->CheckColliding( &pl ) )
981  return false;
982  }
983 
984  const SHAPE_LINE_CHAIN& l = pl.CLine();
985 
986  if( !l.SegmentCount() )
987  {
988  if( pl.EndsWithVia() )
989  {
990  m_lastNode->Add( Clone( pl.Via() ) );
992 
993  m_lastNode = NULL;
994  m_currentNode = NULL;
995 
996  m_idle = true;
997  }
998 
999  return true;
1000  }
1001 
1002  VECTOR2I p_pre_last = l.CPoint( -1 );
1003  const VECTOR2I p_last = l.CPoint( -1 );
1004  DIRECTION_45 d_last( l.CSegment( -1 ) );
1005 
1006  if( l.PointCount() > 2 )
1007  p_pre_last = l.CPoint( -2 );
1008 
1009  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1010  realEnd = true;
1011 
1012  if( realEnd || m_placingVia )
1013  lastV = l.SegmentCount();
1014  else
1015  lastV = std::max( 1, l.SegmentCount() - 1 );
1016 
1017  SEGMENT* lastSeg = nullptr;
1018 
1019  for( int i = 0; i < lastV; i++ )
1020  {
1021  const SEG& s = pl.CSegment( i );
1022  lastSeg = new SEGMENT( s, m_currentNet );
1023  std::unique_ptr< SEGMENT > seg( lastSeg );
1024  seg->SetWidth( pl.Width() );
1025  seg->SetLayer( m_currentLayer );
1026  if( ! m_lastNode->Add( std::move( seg ) ) )
1027  {
1028  lastSeg = nullptr;
1029  }
1030  }
1031 
1032  if( pl.EndsWithVia() )
1033  m_lastNode->Add( Clone( pl.Via() ) );
1034 
1035  if( realEnd && lastSeg )
1036  simplifyNewLine( m_lastNode, lastSeg );
1037 
1039 
1040  m_lastNode = NULL;
1041  m_currentNode = NULL;
1042 
1043  if( !realEnd )
1044  {
1045  setInitialDirection( d_last );
1046  m_currentStart = m_placingVia ? p_last : p_pre_last;
1047  m_startItem = NULL;
1048  m_placingVia = false;
1050  initPlacement();
1051  }
1052  else
1053  {
1054  m_idle = true;
1055  }
1056 
1057  return realEnd;
1058 }
1059 
1060 
1061 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1062 {
1063  if( !aLatest.SegmentCount() )
1064  return;
1065 
1066  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1067  return;
1068 
1069  std::set<SEGMENT *> toErase;
1070  aNode->Add( aLatest, true );
1071 
1072  for( int s = 0; s < aLatest.LinkCount(); s++ )
1073  {
1074  SEGMENT* seg = aLatest.GetLink(s);
1075  LINE ourLine = aNode->AssembleLine( seg );
1076  JOINT a, b;
1077  std::vector<LINE> lines;
1078 
1079  aNode->FindLineEnds( ourLine, a, b );
1080 
1081  if( a == b )
1082  {
1083  aNode->FindLineEnds( aLatest, a, b );
1084  }
1085 
1086  aNode->FindLinesBetweenJoints( a, b, lines );
1087 
1088  int removedCount = 0;
1089  int total = 0;
1090 
1091  for( LINE& line : lines )
1092  {
1093  total++;
1094 
1095  if( !( line.ContainsSegment( seg ) ) && line.SegmentCount() )
1096  {
1097  for( SEGMENT *ss : line.LinkedSegments() )
1098  toErase.insert( ss );
1099 
1100  removedCount++;
1101  }
1102  }
1103 
1104  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1105  }
1106 
1107  for( SEGMENT *s : toErase )
1108  aNode->Remove( s );
1109 
1110  aNode->Remove( aLatest );
1111 }
1112 
1113 
1115 {
1116  LINE l = aNode->AssembleLine( aLatest );
1117  SHAPE_LINE_CHAIN simplified( l.CLine() );
1118 
1119  simplified.Simplify();
1120 
1121  if( simplified.PointCount() != l.PointCount() )
1122  {
1123  aNode->Remove( l );
1124  l.SetShape( simplified );
1125  aNode->Add( l );
1126  }
1127 }
1128 
1129 
1131 {
1132  m_sizes = aSizes;
1133 
1134  if( !m_idle )
1135  {
1136  initPlacement();
1137  }
1138 }
1139 
1140 
1142 {
1143  LINE current = Trace();
1144  SHAPE_LINE_CHAIN ratLine;
1145  TOPOLOGY topo( m_lastNode );
1146 
1147  if( topo.LeadingRatLine( &current, ratLine ) )
1148  Dbg()->AddLine( ratLine, 5, 10000 );
1149 }
1150 
1151 
1152 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1153 {
1154  m_orthoMode = aOrthoMode;
1155 }
1156 
1157 
1158 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aInvertPosture )
1159 {
1160  SHAPE_LINE_CHAIN l;
1161 
1162  if( m_p_start == aP )
1163  {
1164  l.Clear();
1165  }
1166  else
1167  {
1168  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1169  {
1170  l = SHAPE_LINE_CHAIN( m_p_start, aP );
1171  }
1172  else
1173  {
1174  if ( aInvertPosture )
1176  else
1178  }
1179 
1180  if( l.SegmentCount() > 1 && m_orthoMode )
1181  {
1182  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1183 
1184  l.Remove( -1, -1 );
1185  l.Point( 1 ) = newLast;
1186  }
1187  }
1188 
1189  aHead.SetShape( l );
1190 
1191  if( !m_placingVia )
1192  return true;
1193 
1194  VIA v( makeVia( aP ) );
1195  v.SetNet( aHead.Net() );
1196 
1198  {
1199  aHead.AppendVia( v );
1200  return true;
1201  }
1202 
1203  VECTOR2I force;
1204  VECTOR2I lead = aP - m_p_start;
1205 
1206  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1207 
1208  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1209  {
1210  SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force );
1211  aHead = LINE( aHead, line );
1212 
1213  v.SetPos( v.Pos() + force );
1214  return true;
1215  }
1216 
1217  return false; // via placement unsuccessful
1218 }
1219 
1220 
1221 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1222 {
1223  aNets.push_back( m_currentNet );
1224 }
1225 
1227 {
1228  if( m_shove )
1229  return m_shove->Logger();
1230 
1231  return NULL;
1232 }
1233 
1234 }
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:181
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:138
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:209
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:199
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:834
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:934
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:337
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:889
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:741
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
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
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:169
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:132
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:1227
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:36
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:172
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:261
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
route step, mark obstacles mode
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:968
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:380
Definition: seg.h:36
Only walkaround
NODE * m_currentNode
Current world state
bool Is45Degree() const
Definition: pns_line.cpp:276
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:62
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:347
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:97
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)
size_t i
Definition: json11.cpp:597
bool HasLoops() const
Definition: pns_line.cpp:803
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:149
const LINE ClipToNearestObstacle(NODE *aNode) const
Clips the line to the nearest obstacle, traversing from the line&#39;s start vertex (0).
Definition: pns_line.cpp:302
int Net() const
Function Net()
Definition: pns_item.h:179
bool SetLayer(int aLayer) override
Function SetLayer()
const DIRECTION_45 Right() const
Function Right()
Definition: direction45.h:262
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:202
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()
bool 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