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