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