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