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 void LINE_PLACER::splitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
804 {
805  if( !aSeg )
806  return;
807 
808  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
809  return;
810 
811  JOINT* jt = aNode->FindJoint( aP, aSeg );
812 
813  if( jt && jt->LinkCount() >= 1 )
814  return;
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 
831 
832 bool LINE_PLACER::SetLayer( int aLayer )
833 {
834  if( m_idle )
835  {
836  m_currentLayer = aLayer;
837  return true;
838  }
839  else if( m_chainedPlacement )
840  {
841  return false;
842  }
843  else if( !m_startItem || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
844  {
845  m_currentLayer = aLayer;
846  initPlacement();
847  Move( m_currentEnd, NULL );
848  return true;
849  }
850 
851  return false;
852 }
853 
854 
855 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
856 {
857  VECTOR2I p( aP );
858 
859  static int unknowNetIdx = 0; // -10000;
860  int net = -1;
861 
862  if( !aStartItem || aStartItem->Net() < 0 )
863  net = unknowNetIdx--;
864  else
865  net = aStartItem->Net();
866 
867  m_currentStart = p;
868  m_currentEnd = p;
869  m_currentNet = net;
870  m_startItem = aStartItem;
871  m_placingVia = false;
872  m_chainedPlacement = false;
873 
874  setInitialDirection( Settings().InitialDirection() );
875 
876  initPlacement();
877  return true;
878 }
879 
880 
882 {
883  m_idle = false;
884 
885  m_head.Line().Clear();
886  m_tail.Line().Clear();
893  m_head.RemoveVia();
894  m_tail.RemoveVia();
895 
898 
899  NODE* world = Router()->GetWorld();
900 
901  world->KillChildren();
902  NODE* rootNode = world->Branch();
903 
905 
906  setWorld( rootNode );
907 
908  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
910 
911  m_lastNode = NULL;
914 
915  m_shove.reset();
916 
918  {
919  m_shove.reset( new SHOVE( m_world->Branch(), Router() ) );
920  }
921 }
922 
923 
924 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
925 {
926  LINE current;
927  VECTOR2I p = aP;
928  int eiDepth = -1;
929 
930  if( aEndItem && aEndItem->Owner() )
931  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
932 
933  if( m_lastNode )
934  {
935  delete m_lastNode;
936  m_lastNode = NULL;
937  }
938 
939  route( p );
940 
941  current = Trace();
942 
943  if( !current.PointCount() )
945  else
946  m_currentEnd = current.CLine().CPoint( -1 );
947 
948  NODE* latestNode = m_currentNode;
949  m_lastNode = latestNode->Branch();
950 
951  if( eiDepth >= 0 && aEndItem && latestNode->Depth() > eiDepth && current.SegmentCount() )
952  {
953  splitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
954 
955  if( Settings().RemoveLoops() )
956  removeLoops( m_lastNode, current );
957  }
958 
960  return true;
961 }
962 
963 
964 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
965 {
966  bool realEnd = false;
967  int lastV;
968 
969  LINE pl = Trace();
970 
972  !Settings().CanViolateDRC() &&
973  m_world->CheckColliding( &pl ) )
974  return false;
975 
976  const SHAPE_LINE_CHAIN& l = pl.CLine();
977 
978  if( !l.SegmentCount() )
979  {
980  if( pl.EndsWithVia() )
981  {
982  m_lastNode->Add( Clone( pl.Via() ) );
984 
985  m_lastNode = NULL;
986  m_currentNode = NULL;
987 
988  m_idle = true;
989  }
990 
991  return true;
992  }
993 
994  VECTOR2I p_pre_last = l.CPoint( -1 );
995  const VECTOR2I p_last = l.CPoint( -1 );
996  DIRECTION_45 d_last( l.CSegment( -1 ) );
997 
998  if( l.PointCount() > 2 )
999  p_pre_last = l.CPoint( -2 );
1000 
1001  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1002  realEnd = true;
1003 
1004  if( realEnd || m_placingVia )
1005  lastV = l.SegmentCount();
1006  else
1007  lastV = std::max( 1, l.SegmentCount() - 1 );
1008 
1009  SEGMENT* lastSeg = NULL;
1010 
1011  for( int i = 0; i < lastV; i++ )
1012  {
1013  const SEG& s = pl.CSegment( i );
1014  std::unique_ptr< SEGMENT > seg( new SEGMENT( s, m_currentNet ) );
1015  seg->SetWidth( pl.Width() );
1016  seg->SetLayer( m_currentLayer );
1017  lastSeg = seg.get();
1018  m_lastNode->Add( std::move( seg ) );
1019  }
1020 
1021  if( pl.EndsWithVia() )
1022  m_lastNode->Add( Clone( pl.Via() ) );
1023 
1024  if( realEnd )
1025  simplifyNewLine( m_lastNode, lastSeg );
1026 
1028 
1029  m_lastNode = NULL;
1030  m_currentNode = NULL;
1031 
1032  if( !realEnd )
1033  {
1034  setInitialDirection( d_last );
1035  m_currentStart = m_placingVia ? p_last : p_pre_last;
1036  m_startItem = NULL;
1037  m_placingVia = false;
1039  initPlacement();
1040  }
1041  else
1042  {
1043  m_idle = true;
1044  }
1045 
1046  return realEnd;
1047 }
1048 
1049 
1050 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1051 {
1052  if( !aLatest.SegmentCount() )
1053  return;
1054 
1055  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1056  return;
1057 
1058  std::set<SEGMENT *> toErase;
1059  aNode->Add( aLatest, true );
1060 
1061  for( int s = 0; s < aLatest.LinkCount(); s++ )
1062  {
1063  SEGMENT* seg = aLatest.GetLink(s);
1064  LINE ourLine = aNode->AssembleLine( seg );
1065  JOINT a, b;
1066  std::vector<LINE> lines;
1067 
1068  aNode->FindLineEnds( ourLine, a, b );
1069 
1070  if( a == b )
1071  {
1072  aNode->FindLineEnds( aLatest, a, b );
1073  }
1074 
1075  aNode->FindLinesBetweenJoints( a, b, lines );
1076 
1077  int removedCount = 0;
1078  int total = 0;
1079 
1080  for( LINE& line : lines )
1081  {
1082  total++;
1083 
1084  if( !( line.ContainsSegment( seg ) ) && line.SegmentCount() )
1085  {
1086  for( SEGMENT *ss : line.LinkedSegments() )
1087  toErase.insert( ss );
1088 
1089  removedCount++;
1090  }
1091  }
1092 
1093  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1094  }
1095 
1096  for( SEGMENT *s : toErase )
1097  aNode->Remove( s );
1098 
1099  aNode->Remove( aLatest );
1100 }
1101 
1102 
1104 {
1105  LINE l = aNode->AssembleLine( aLatest );
1106  SHAPE_LINE_CHAIN simplified( l.CLine() );
1107 
1108  simplified.Simplify();
1109 
1110  if( simplified.PointCount() != l.PointCount() )
1111  {
1112  aNode->Remove( l );
1113  l.SetShape( simplified );
1114  aNode->Add( l );
1115  }
1116 }
1117 
1118 
1120 {
1121  m_sizes = aSizes;
1122 
1123  if( !m_idle )
1124  {
1125  initPlacement();
1126  }
1127 }
1128 
1129 
1131 {
1132  LINE current = Trace();
1133  SHAPE_LINE_CHAIN ratLine;
1134  TOPOLOGY topo( m_lastNode );
1135 
1136  if( topo.LeadingRatLine( &current, ratLine ) )
1137  Dbg()->AddLine( ratLine, 5, 10000 );
1138 }
1139 
1140 
1141 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1142 {
1143  m_orthoMode = aOrthoMode;
1144 }
1145 
1146 
1147 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aInvertPosture )
1148 {
1149  SHAPE_LINE_CHAIN l;
1150 
1151  if( m_p_start == aP )
1152  {
1153  l.Clear();
1154  }
1155  else
1156  {
1157  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1158  {
1159  l = SHAPE_LINE_CHAIN( m_p_start, aP );
1160  }
1161  else
1162  {
1163  if ( aInvertPosture )
1165  else
1167  }
1168 
1169  if( l.SegmentCount() > 1 && m_orthoMode )
1170  {
1171  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1172 
1173  l.Remove( -1, -1 );
1174  l.Point( 1 ) = newLast;
1175  }
1176  }
1177 
1178  aHead.SetShape( l );
1179 
1180  if( !m_placingVia )
1181  return true;
1182 
1183  VIA v( makeVia( aP ) );
1184  v.SetNet( aHead.Net() );
1185 
1187  {
1188  aHead.AppendVia( v );
1189  return true;
1190  }
1191 
1192  VECTOR2I force;
1193  VECTOR2I lead = aP - m_p_start;
1194 
1195  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1196 
1197  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1198  {
1199  SHAPE_LINE_CHAIN line = m_direction.BuildInitialTrace( m_p_start, aP + force );
1200  aHead = LINE( aHead, line );
1201 
1202  v.SetPos( v.Pos() + force );
1203  return true;
1204  }
1205 
1206  return false; // via placement unsuccessful
1207 }
1208 
1209 
1210 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1211 {
1212  aNets.push_back( m_currentNet );
1213 }
1214 
1216 {
1217  if( m_shove )
1218  return m_shove->Logger();
1219 
1220  return NULL;
1221 }
1222 
1223 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h: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:321
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:707
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:134
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.
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()
void splitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Function splitAdjacentSegments()
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:324
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:769
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