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