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-2021 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 #include <memory>
24 
25 #include "pns_arc.h"
26 #include "pns_debug_decorator.h"
27 #include "pns_line_placer.h"
28 #include "pns_node.h"
29 #include "pns_router.h"
30 #include "pns_shove.h"
31 #include "pns_solid.h"
32 #include "pns_topology.h"
33 #include "pns_walkaround.h"
34 #include "pns_mouse_trail_tracer.h"
35 
36 #include <wx/log.h>
37 
38 namespace PNS {
39 
41  PLACEMENT_ALGO( aRouter )
42 {
44  m_world = nullptr;
45  m_shove = nullptr;
46  m_currentNode = nullptr;
47  m_idle = true;
48 
49  // Init temporary variables (do not leave uninitialized members)
50  m_lastNode = nullptr;
51  m_placingVia = false;
52  m_currentNet = 0;
53  m_currentLayer = 0;
55  m_startItem = nullptr;
56  m_chainedPlacement = false;
57  m_orthoMode = false;
58  m_placementCorrect = false;
59 }
60 
61 
63 {
64 }
65 
66 
67 void LINE_PLACER::setWorld( NODE* aWorld )
68 {
69  m_world = aWorld;
70 }
71 
72 
73 const VIA LINE_PLACER::makeVia( const VECTOR2I& aP )
74 {
77 
78  return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
79 }
80 
81 
82 bool LINE_PLACER::ToggleVia( bool aEnabled )
83 {
84  m_placingVia = aEnabled;
85 
86  if( !aEnabled )
87  m_head.RemoveVia();
88 
89  return true;
90 }
91 
92 
94 {
95  m_initial_direction = aDirection;
96 
97  if( m_tail.SegmentCount() == 0 )
98  m_direction = aDirection;
99 }
100 
101 
103 {
105  SHAPE_LINE_CHAIN& head = m_head.Line();
106  SHAPE_LINE_CHAIN& tail = m_tail.Line();
107 
108  // if there is no tail, there is nothing to intersect with
109  if( tail.PointCount() < 2 )
110  return false;
111 
112  if( head.PointCount() < 2 )
113  return false;
114 
115  // completely new head trace? chop off the tail
116  if( tail.CPoint(0) == head.CPoint(0) )
117  {
118  m_p_start = tail.CPoint( 0 );
120  tail.Clear();
121  return true;
122  }
123 
124  tail.Intersect( head, ips );
125 
126  // no intesection points - nothing to reduce
127  if( ips.empty() )
128  return false;
129 
130  int n = INT_MAX;
131  VECTOR2I ipoint;
132 
133  // if there is more than one intersection, find the one that is
134  // closest to the beginning of the tail.
135  for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
136  {
137  if( i.index_our < n )
138  {
139  n = i.index_our;
140  ipoint = i.p;
141  }
142  }
143 
144  // ignore the point where head and tail meet
145  if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
146  return false;
147 
148  // Intersection point is on the first or the second segment: just start routing
149  // from the beginning
150  if( n < 2 )
151  {
152  m_p_start = tail.CPoint( 0 );
154  tail.Clear();
155  head.Clear();
156 
157  return true;
158  }
159  else
160  {
161  // Clip till the last tail segment before intersection.
162  // Set the direction to the one of this segment.
163  const SEG last = tail.CSegment( n - 1 );
164  m_p_start = last.A;
165  m_direction = DIRECTION_45( last );
166  tail.Remove( n, -1 );
167  return true;
168  }
169 
170  return false;
171 }
172 
173 
175 {
176  SHAPE_LINE_CHAIN& head = m_head.Line();
177  SHAPE_LINE_CHAIN& tail = m_tail.Line();
178 
179  if( head.PointCount() < 2 )
180  return false;
181 
182  int n = tail.PointCount();
183 
184  if( n == 0 )
185  {
186  return false;
187  }
188  else if( n == 1 )
189  {
190  m_p_start = tail.CPoint( 0 );
191  tail.Clear();
192  return true;
193  }
194 
195  DIRECTION_45 first_head, last_tail;
196 
197  wxASSERT( tail.PointCount() >= 2 );
198 
199  if( !head.IsPtOnArc( 0 ) )
200  first_head = DIRECTION_45( head.CSegment( 0 ) );
201  else
202  first_head = DIRECTION_45( head.CArcs()[head.ArcIndex(0)] );
203 
204  int lastSegIdx = tail.PointCount() - 2;
205 
206  if( !tail.IsPtOnArc( lastSegIdx ) )
207  last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
208  else
209  last_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex(lastSegIdx)] );
210 
211  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
212 
213  // case 1: we have a defined routing direction, and the currently computed
214  // head goes in different one.
215  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
216 
217  // case 2: regardless of the current routing direction, if the tail/head
218  // extremities form an acute or right angle, reduce the tail by one segment
219  // (and hope that further iterations) will result with a cleaner trace
220  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
221 
222  if( pullback_1 || pullback_2 )
223  {
224  lastSegIdx = tail.PrevShape( -1 );
225 
226  if( !tail.IsPtOnArc( lastSegIdx ) )
227  {
228  const SEG& seg = tail.CSegment( lastSegIdx );
229  m_direction = DIRECTION_45( seg );
230  m_p_start = seg.A;
231  }
232  else
233  {
234  const SHAPE_ARC& arc = tail.CArcs()[tail.ArcIndex( lastSegIdx )];
235  m_direction = DIRECTION_45( arc );
236  m_p_start = arc.GetP0();
237  }
238 
239  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
240  n, last_tail.Format().c_str(), first_head.Format().c_str() );
241 
242  // erase the last point in the tail, hoping that the next iteration will
243  // result with a head trace that starts with a segment following our
244  // current direction.
245  if( n < 2 )
246  tail.Clear(); // don't leave a single-point tail
247  else
248  tail.RemoveShape( -1 );
249 
250  if( !tail.SegmentCount() )
252 
253  return true;
254  }
255 
256  return false;
257 }
258 
259 
261 {
262  SHAPE_LINE_CHAIN& head = m_head.Line();
263  SHAPE_LINE_CHAIN& tail = m_tail.Line();
264 
265  int n = tail.SegmentCount();
266 
267  if( head.SegmentCount() < 1 )
268  return false;
269 
270  // Don't attempt this for too short tails
271  if( n < 2 )
272  return false;
273 
274  // Start from the segment farthest from the end of the tail
275  // int start_index = std::max(n - 1 - ReductionDepth, 0);
276 
277  DIRECTION_45 new_direction;
278  VECTOR2I new_start;
279  int reduce_index = -1;
280 
281  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
282  {
283  const SEG s = tail.CSegment( i );
284  DIRECTION_45 dir( s );
285 
286  // calculate a replacement route and check if it matches
287  // the direction of the segment to be replaced
288  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
289 
290  if( replacement.SegmentCount() < 1 )
291  continue;
292 
293  LINE tmp( m_tail, replacement );
294 
296  break;
297 
298  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
299  {
300  new_start = s.A;
301  new_direction = dir;
302  reduce_index = i;
303  }
304  }
305 
306  if( reduce_index >= 0 )
307  {
308  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
309  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
310 
311  m_p_start = new_start;
312  m_direction = new_direction;
313  tail.Remove( reduce_index + 1, -1 );
314  head.Clear();
315  return true;
316  }
317 
318  if( !tail.SegmentCount() )
320 
321  return false;
322 }
323 
324 
326 {
327  SHAPE_LINE_CHAIN& head = m_head.Line();
328  SHAPE_LINE_CHAIN& tail = m_tail.Line();
329 
330  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
333 
334  head.Simplify();
335  tail.Simplify();
336 
337  int n_head = head.ShapeCount();
338  int n_tail = tail.ShapeCount();
339 
340  if( n_head < 3 )
341  {
342  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
343  return false;
344  }
345 
346  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
347  {
348  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
349  return false;
350  }
351 
352  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
353  return false;
354 
355  DIRECTION_45 dir_tail, dir_head;
356 
357  if( !head.IsPtOnArc( 0 ) )
358  dir_head = DIRECTION_45( head.CSegment( 0 ) );
359  else
360  dir_head = DIRECTION_45( head.CArcs()[head.ArcIndex( 0 )] );
361 
362  if( n_tail )
363  {
364  wxASSERT( tail.PointCount() >= 2 );
365  int lastSegIdx = tail.PointCount() - 2;
366 
367  if( !tail.IsPtOnArc( lastSegIdx ) )
368  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
369  else
370  dir_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
371 
372  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
373  return false;
374  }
375 
376  tail.Append( head );
377 
378  tail.Simplify();
379 
380  SEG last = tail.CSegment( -1 );
381  m_p_start = last.B;
382 
383  int lastSegIdx = tail.PointCount() - 2;
384 
385  if( !tail.IsArcSegment( lastSegIdx ) )
386  m_direction = DIRECTION_45( tail.CSegment( -1 ) );
387  else
388  m_direction = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
389 
390  head.Remove( 0, -1 );
391 
392  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head,
393  m_direction.Format().c_str() );
394 
395  head.Simplify();
396  tail.Simplify();
397 
398  return true;
399 }
400 
401 
403 {
404  // Keep distances squared for performance
405  SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
406  VECTOR2I closest;
407 
408  for( int i = 0; i < line.SegmentCount(); i++ )
409  {
410  const SEG& s = line.CSegment( i );
411  VECTOR2I a = s.NearestPoint( p );
412  int d_sq = (a - p).SquaredEuclideanNorm();
413 
414  if( d_sq < min_dist_sq )
415  {
416  min_dist_sq = d_sq;
417  closest = a;
418  }
419  }
420 
421  return closest;
422 }
423 
424 
425 static bool cursorDistMinimum( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aCursor, double lengthThreshold, int& theDist, VECTOR2I& aNearest )
426 {
427  std::vector<int> dists;
428  std::vector<VECTOR2I> pts;
429 
430  if( aL.PointCount() == 0 )
431  return false;
432 
433  VECTOR2I lastP = aL.CPoint(-1);
434  int accumulatedDist = 0;
435 
436  dists.reserve( 2 * aL.PointCount() );
437 
438  for( int i = 0; i < aL.SegmentCount(); i++ )
439  {
440  const SEG& s = aL.CSegment( i );
441 
442  dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
443  pts.push_back( s.A );
444  auto pn = s.NearestPoint( aCursor );
445 
446  if( pn != s.A && pn != s.B )
447  {
448  dists.push_back( ( pn - aCursor ).EuclideanNorm() );
449  pts.push_back( pn );
450  }
451 
452  accumulatedDist += s.Length();
453 
454  if ( accumulatedDist > lengthThreshold )
455  {
456  lastP = s.B;
457  break;
458  }
459  }
460 
461  dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
462  pts.push_back( lastP );
463 
464  int minDistLoc = std::numeric_limits<int>::max();
465  int minPLoc = -1;
466  int minDistGlob = std::numeric_limits<int>::max();
467  int minPGlob = -1;
468 
469  for( int i = 0; i < dists.size(); i++ )
470  {
471  int d = dists[i];
472 
473  if( d < minDistGlob )
474  {
475  minDistGlob = d;
476  minPGlob = i;
477  }
478  }
479 
480  if( dists.size() >= 3 )
481  {
482  for( int i = 0; i < dists.size() - 3; i++ )
483  {
484  if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
485  {
486  int d = dists[i + 1];
487  if( d < minDistLoc )
488  {
489  minDistLoc = d;
490  minPLoc = i + 1;
491  }
492  }
493  }
494 
495  if( dists.back() < minDistLoc && minPLoc >= 0 )
496  {
497  minDistLoc = dists.back();
498  minPLoc = dists.size() - 1;
499  }
500  }
501  else
502  {
503  // Too few points: just use the global
504  minDistLoc = minDistGlob;
505  minPLoc = minPGlob;
506  }
507 
508 // fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
509 // in the code, enabling the global one by default
510  minPLoc = -1;
511 
512  if( minPLoc < 0 )
513  {
514  theDist = minDistGlob;
515  aNearest = pts[minPGlob];
516  return true;
517  }
518  else
519  {
520  theDist = minDistLoc;
521  aNearest = pts[minPLoc];
522  return true;
523  }
524 }
525 
526 
527 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
528 {
529  LINE initTrack( m_head );
530  LINE walkFull( m_head );
531 
532  initTrack.RemoveVia();
533  walkFull.RemoveVia();
534 
535  int effort = 0;
536  bool viaOk = false;
537 
538  VECTOR2I walkP = aP;
539 
540  WALKAROUND walkaround( m_currentNode, Router() );
541 
542  walkaround.SetSolidsOnly( false );
543  walkaround.SetDebugDecorator( Dbg() );
544  walkaround.SetLogger( Logger() );
545  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
546 
547  char name[50];
548  int round = 0;
549 
550  do {
551  snprintf( name, sizeof( name ), "walk-round-%d", round );
552  PNS_DBG( Dbg(), BeginGroup, name );
553 
554  viaOk = buildInitialLine( walkP, initTrack, round == 0 );
555 
556  double initialLength = initTrack.CLine().Length();
557  double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
558 
559  WALKAROUND::RESULT wr = walkaround.Route( initTrack );
560 
561  SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
562  SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
563 
565  {
566  int len_cw = wr.statusCw == WALKAROUND::DONE ? l_cw.Length() : INT_MAX;
567  int len_ccw = wr.statusCcw == WALKAROUND::DONE ? l_ccw.Length() : INT_MAX;
568 
569  PNS_DBG( Dbg(), AddLine, wr.lineCw.CLine(), CYAN, 10000, "wf-result-cw" );
570  PNS_DBG( Dbg(), AddLine, wr.lineCcw.CLine(), BLUE, 20000, "wf-result-ccw" );
571 
572  int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
573 
574  if( bestLength > hugThresholdLength )
575  {
578  }
579 
580  SHAPE_LINE_CHAIN& bestLine = len_cw < len_ccw ? l_cw : l_ccw;
581  walkFull.SetShape( bestLine );
582  }
583 
585  {
586  bool valid_cw = false, valid_ccw = false;
587  VECTOR2I p_cw, p_ccw;
588  int dist_ccw = 0, dist_cw = 0;
589 
591  {
592  valid_ccw = cursorDistMinimum( l_ccw, aP, hugThresholdLength, dist_ccw, p_ccw );
593 
594  if( valid_ccw )
595  {
596  int idx_ccw = l_ccw.Split( p_ccw );
597  l_ccw = l_ccw.Slice( 0, idx_ccw );
598  PNS_DBG( Dbg(), AddPoint, p_ccw, BLUE, 500000, "hug-target-ccw" );
599  PNS_DBG( Dbg(), AddLine, l_ccw, MAGENTA, 200000, "wh-result-ccw" );
600  }
601  }
602 
604  {
605  valid_cw = cursorDistMinimum( l_cw, aP, hugThresholdLength, dist_cw, p_cw );
606 
607  if( valid_cw )
608  {
609  int idx_cw = l_cw.Split( p_cw );
610  l_cw = l_cw.Slice( 0, idx_cw );
611  PNS_DBG( Dbg(), AddPoint, p_cw, YELLOW, 500000, "hug-target-cw" );
612  PNS_DBG( Dbg(), AddLine, l_cw, BLUE, 200000, "wh-result-cw" );
613  }
614  }
615 
616  if( dist_cw < dist_ccw && valid_cw )
617  {
618  walkFull.SetShape( l_cw );
619  walkP = p_cw;
620  }
621  else if ( valid_ccw )
622  {
623  walkFull.SetShape( l_ccw );
624  walkP = p_ccw;
625  }
626  else
627  {
628  PNS_DBGN( Dbg(), EndGroup );
629  return false;
630  }
631  }
632  else if ( wr.statusCcw == WALKAROUND::STUCK || wr.statusCw == WALKAROUND::STUCK )
633  {
634  PNS_DBGN( Dbg(), EndGroup );
635  return false;
636  }
637 
638  PNS_DBGN( Dbg(), EndGroup );
639 
640  round++;
641  } while( round < 2 && m_placingVia );
642 
643  PNS_DBG( Dbg(), AddLine, walkFull.CLine(), GREEN, 200000, "walk-full" );
644 
645  switch( Settings().OptimizerEffort() )
646  {
647  case OE_LOW:
648  effort = 0;
649  break;
650 
651  case OE_MEDIUM:
652  case OE_FULL:
653  effort = OPTIMIZER::MERGE_SEGMENTS;
654  break;
655  }
656 
658  effort |= OPTIMIZER::SMART_PADS;
659 
660  if( m_placingVia && viaOk )
661  {
662  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
663  }
664 
665  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
666 
667  if( m_currentNode->CheckColliding( &walkFull ) )
668  {
669  return false;
670  }
671 
672  aNewHead = walkFull;
673 
674  return true;
675 }
676 
677 
678 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
679 {
680  buildInitialLine( aP, m_head );
681  m_head.SetBlockingObstacle( nullptr );
682 
683  // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
684  // but we don't have one right now and there isn't a lot of demand for one. If we do end up
685  // doing that, put it in a new routing mode as "highlight collisions" mode should not have
686  // collision handling other than highlighting.
687 #if 0
688  if( !Settings().AllowDRCViolations() )
689  {
691 
692  if( obs && obs->m_distFirst != INT_MAX )
693  {
694  buildInitialLine( obs->m_ipFirst, m_head );
695  m_head.SetBlockingObstacle( obs->m_item );
696  }
697  }
698 #endif
699 
700  aNewHead = m_head;
701 
702  return true;
703 }
704 
705 
706 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
707 {
708  LINE initTrack( m_head );
709  LINE walkSolids, l2;
710 
711  bool viaOk = buildInitialLine( aP, initTrack );
712 
713  m_currentNode = m_shove->CurrentNode();
714 
715  m_shove->SetLogger( Logger() );
716  m_shove->SetDebugDecorator( Dbg() );
717 
718  OPTIMIZER optimizer( m_currentNode );
719 
720  WALKAROUND walkaround( m_currentNode, Router() );
721 
722  walkaround.SetSolidsOnly( true );
723  walkaround.SetIterationLimit( 10 );
724  walkaround.SetDebugDecorator( Dbg() );
725  walkaround.SetLogger( Logger() );
726  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
727 
729  optimizer.SetCollisionMask( ITEM::SOLID_T );
730  optimizer.Optimize( &walkSolids );
731 
732  if( stat_solids == WALKAROUND::DONE )
733  l2 = walkSolids;
734  else
735  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
736 
737  LINE l( m_tail );
738  l.Line().Append( l2.CLine() );
739  l.Line().Simplify();
740 
741  if( l.PointCount() == 0 || l2.PointCount() == 0 )
742  {
743  aNewHead = m_head;
744  return false;
745  }
746 
747  if( m_placingVia && viaOk )
748  {
749  VIA v1( makeVia( l.CPoint( -1 ) ) );
750  VIA v2( makeVia( l2.CPoint( -1 ) ) );
751 
752  l.AppendVia( v1 );
753  l2.AppendVia( v2 );
754  }
755 
756  l.Line().Simplify();
757 
758  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
759  // shove to avoid screwing up the database.
760  if( l.HasLoops() )
761  {
762  aNewHead = m_head;
763  return false;
764  }
765 
766  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
767 
768  m_currentNode = m_shove->CurrentNode();
769 
770  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
771  {
772  if( status == SHOVE::SH_HEAD_MODIFIED )
773  l2 = m_shove->NewHead();
774 
775  optimizer.SetWorld( m_currentNode );
776 
777  int effortLevel = OPTIMIZER::MERGE_OBTUSE;
778 
779  if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
780  effortLevel = OPTIMIZER::SMART_PADS;
781 
782  optimizer.SetEffortLevel( effortLevel );
783 
784  optimizer.SetCollisionMask( ITEM::ANY_T );
785  optimizer.Optimize( &l2 );
786 
787  aNewHead = l2;
788 
789  return true;
790  }
791  else
792  {
793  walkaround.SetWorld( m_currentNode );
794  walkaround.SetSolidsOnly( false );
795  walkaround.SetIterationLimit( 10 );
796  walkaround.SetApproachCursor( true, aP );
797  walkaround.Route( initTrack, l2 );
798  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
799 
800  return false;
801  }
802 
803  return false;
804 }
805 
806 
807 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
808 {
809  switch( m_currentMode )
810  {
811  case RM_MarkObstacles:
812  return rhMarkObstacles( aP, aNewHead );
813  case RM_Walkaround:
814  return rhWalkOnly( aP, aNewHead );
815  case RM_Shove:
816  return rhShoveOnly( aP, aNewHead );
817  default:
818  break;
819  }
820 
821  return false;
822 }
823 
824 
826 {
827  LINE linetmp = Trace();
828 
829  PNS_DBG( Dbg(), Message, "optimize HT" );
830 
831  // NOTE: FANOUT_CLEANUP can override posture setting at the moment
834  {
835  if( linetmp.SegmentCount() < 1 )
836  return false;
837 
838  m_head = linetmp;
839  m_p_start = linetmp.CLine().CPoint( 0 );
840  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
841  m_tail.Line().Clear();
842 
843  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize fanout-cleanup" ) );
844 
845 
846  return true;
847  }
848 
849  SHAPE_LINE_CHAIN& head = m_head.Line();
850  SHAPE_LINE_CHAIN& tail = m_tail.Line();
851 
852  int tailLookbackSegments = 3;
853 
854  //if(m_currentMode() == RM_Walkaround)
855  // tailLookbackSegments = 10000;
856 
857  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
858 
859  if( tail.ShapeCount() < 3 )
860  return false;
861 
862  // assemble TailLookbackSegments tail segments with the current head
863  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
864 
865  int end = std::min(2, head.PointCount() - 1 );
866 
867  opt_line.Append( head.Slice( 0, end ) );
868 
869  LINE new_head( m_tail, opt_line );
870 
871  // and see if it could be made simpler by merging obtuse/collnear segments.
872  // If so, replace the (threshold) last tail points and the head with
873  // the optimized line
874 
875 
876  PNS_DBG( Dbg(), AddLine, new_head.CLine(), LIGHTCYAN, 10000, "ht-newline" );
877 
879  {
880  LINE tmp( m_tail, opt_line );
881 
882  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize tail-head [%d]", threshold ) );
883 
884  head.Clear();
885  tail.Replace( -threshold, -1, new_head.CLine() );
886  tail.Simplify();
887 
888  m_p_start = new_head.CLine().CPoint( -1 );
889  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
890 
891  return true;
892  }
893 
894  return false;
895 }
896 
897 
899 {
900  bool fail = false;
901  bool go_back = false;
902 
903  int i, n_iter = 1;
904 
905  LINE new_head;
906 
907  wxLogTrace( "PNS", "routeStep: direction: %s head: %d, tail: %d shapes",
908  m_direction.Format().c_str(),
909  m_head.ShapeCount(),
910  m_tail.ShapeCount() );
911 
912  PNS_DBG( Dbg(), BeginGroup, "route-step" );
913 
914  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-init" );
915  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-init" );
916 
917  for( i = 0; i < n_iter; i++ )
918  {
919  if( !go_back && Settings().FollowMouse() )
920  reduceTail( aP );
921 
922  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-reduce" );
923  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-reduce" );
924 
925  go_back = false;
926 
927  if( !routeHead( aP, new_head ) )
928  fail = true;
929 
930  if( !new_head.Is45Degree() &&
932  fail = true;
933 
934  if( fail )
935  break;
936 
937  m_head = new_head;
938 
939  PNS_DBG( Dbg(), AddLine, m_head.CLine(), LIGHTGREEN, 100000, "head-new" );
940 
942  {
943  n_iter++;
944  go_back = true;
945  }
946 
947  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-si" );
948  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-si" );
949 
950  if( !go_back && handlePullback() )
951  {
952  n_iter++;
953  go_back = true;
954  }
955 
956  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-after-pb" );
957  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-after-pb" );
958  }
959 
960  if( fail )
961  {
962  if( m_last_head.PointCount() > 0 )
963  {
965  }
966  else
967  {
968  m_head.RemoveVia();
969  m_head.Clear();
970  }
971  }
972  else
973  {
975  }
976 
977  if( !fail && Settings().FollowMouse() )
978  {
979  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-pre-merge" );
980  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-pre-merge" );
981 
983  {
984  mergeHead();
985  }
986 
987  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-post-merge" );
988  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-post-merge" );
989  }
990 
991  PNS_DBGN( Dbg(), EndGroup );
992 }
993 
994 
995 bool LINE_PLACER::route( const VECTOR2I& aP )
996 {
997  routeStep( aP );
998 
999  if (!m_head.PointCount() )
1000  return false;
1001 
1002  return m_head.CPoint(-1) == aP;
1003 }
1004 
1005 
1007 {
1008  LINE tmp( m_head );
1009 
1010  tmp.SetShape( m_tail.CLine() );
1011  tmp.Line().Append( m_head.CLine() );
1012  tmp.Line().Simplify();
1013  return tmp;
1014 }
1015 
1016 
1018 {
1019  m_currentTrace = Trace();
1020  return ITEM_SET( &m_currentTrace );
1021 }
1022 
1023 
1025 {
1027 }
1028 
1029 
1030 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1031 {
1032  if( aLoopsRemoved && m_lastNode )
1033  return m_lastNode;
1034 
1035  return m_currentNode;
1036 }
1037 
1038 
1039 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
1040 {
1041  if( !aSeg )
1042  return false;
1043 
1044  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1045  return false;
1046 
1047  JOINT* jt = aNode->FindJoint( aP, aSeg );
1048 
1049  if( jt && jt->LinkCount() >= 1 )
1050  return false;
1051 
1052  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1053 
1054  std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1055 
1056  s_new[0]->SetEnds( s_old->Seg().A, aP );
1057  s_new[1]->SetEnds( aP, s_old->Seg().B );
1058 
1059  aNode->Remove( s_old );
1060  aNode->Add( std::move( s_new[0] ), true );
1061  aNode->Add( std::move( s_new[1] ), true );
1062 
1063  return true;
1064 }
1065 
1066 
1067 bool LINE_PLACER::SetLayer( int aLayer )
1068 {
1069  if( m_idle )
1070  {
1071  m_currentLayer = aLayer;
1072  return true;
1073  }
1074  else if( m_chainedPlacement )
1075  {
1076  return false;
1077  }
1078  else if( !m_startItem
1079  || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1080  || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1081  {
1082  m_currentLayer = aLayer;
1083  m_head.Line().Clear();
1084  m_tail.Line().Clear();
1085  m_last_head.Line().Clear();
1086  m_head.RemoveVia();
1087  m_tail.RemoveVia();
1091  Move( m_currentEnd, nullptr );
1092  return true;
1093  }
1094 
1095  return false;
1096 }
1097 
1098 
1099 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1100 {
1101  m_placementCorrect = false;
1102  m_currentStart = VECTOR2I( aP );
1103  m_currentEnd = VECTOR2I( aP );
1104  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
1105  m_startItem = aStartItem;
1106  m_placingVia = false;
1107  m_chainedPlacement = false;
1108  m_fixedTail.Clear();
1109 
1110  setInitialDirection( Settings().InitialDirection() );
1111 
1112  initPlacement();
1113 
1114  DIRECTION_45 initialDir = m_initial_direction;
1116 
1117  if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1118  {
1119  // If we land on a segment endpoint, assume the starting direction is continuing along
1120  // the same direction as the endpoint. If we started in the middle, don't set a
1121  // direction so that the posture solver is not biased.
1122  SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1123 
1124  if( aP == seg.A )
1125  lastSegDir = DIRECTION_45( seg.Reversed() );
1126  else if( aP == seg.B )
1127  lastSegDir = DIRECTION_45( seg );
1128  }
1129  else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1130  static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1131  {
1132  double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
1133  angle = ( angle + 22.5 ) / 45.0;
1134  initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1135  }
1136 
1137  wxLogTrace( "PNS", "Posture: init %s, last seg %s", initialDir.Format(), lastSegDir.Format() );
1138 
1143  m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1144 
1145  NODE *n;
1146 
1147  if ( m_shove )
1148  n = m_shove->CurrentNode();
1149  else
1150  n = m_currentNode;
1151 
1153 
1154  return true;
1155 }
1156 
1157 
1159 {
1160  m_idle = false;
1161 
1162  m_head.Line().Clear();
1163  m_tail.Line().Clear();
1170  m_head.RemoveVia();
1171  m_tail.RemoveVia();
1172 
1175 
1176  NODE* world = Router()->GetWorld();
1177 
1178  world->KillChildren();
1179  NODE* rootNode = world->Branch();
1180 
1182 
1183  setWorld( rootNode );
1184 
1185  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1186  m_world,
1187  m_direction.Format().c_str(),
1188  m_currentLayer );
1189 
1190  m_lastNode = nullptr;
1192  m_currentMode = Settings().Mode();
1193 
1194  m_shove.reset();
1195 
1197  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1198 }
1199 
1200 
1201 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1202 {
1203  LINE current;
1204  VECTOR2I p = aP;
1205  int eiDepth = -1;
1206 
1207  if( aEndItem && aEndItem->Owner() )
1208  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1209 
1210  if( m_lastNode )
1211  {
1212  delete m_lastNode;
1213  m_lastNode = nullptr;
1214  }
1215 
1216  bool reachesEnd = route( p );
1217 
1218  current = Trace();
1219 
1220  if( !current.PointCount() )
1222  else
1223  m_currentEnd = current.CLine().CPoint( -1 );
1224 
1225  NODE* latestNode = m_currentNode;
1226  m_lastNode = latestNode->Branch();
1227 
1228  if( reachesEnd
1229  && eiDepth >= 0
1230  && aEndItem && latestNode->Depth() > eiDepth
1231  && current.SegmentCount() )
1232  {
1233  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1234 
1235  if( Settings().RemoveLoops() )
1236  removeLoops( m_lastNode, current );
1237  }
1238 
1241  return true;
1242 }
1243 
1244 
1245 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1246 {
1247  bool fixAll = Settings().GetFixAllSegments();
1248  bool realEnd = false;
1249 
1250  LINE pl = Trace();
1251 
1253  {
1254  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1255  // user has more responsibility and authority.
1256 
1257  if( aEndItem )
1258  {
1259  // The user has indicated a connection should be made. If either the trace or
1260  // endItem is net-less, then allow the connection by adopting the net of the other.
1261  if( m_currentNet <= 0 )
1262  {
1263  m_currentNet = aEndItem->Net();
1264  pl.SetNet( m_currentNet );
1265  }
1266  else if (aEndItem->Net() <= 0 )
1267  {
1268  aEndItem->SetNet( m_currentNet );
1269  }
1270  }
1271 
1272  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1273  if( !Settings().AllowDRCViolations() && m_world->CheckColliding( &pl ) )
1274  return false;
1275  }
1276 
1277  const SHAPE_LINE_CHAIN& l = pl.CLine();
1278 
1279  if( !l.SegmentCount() )
1280  {
1281  if( m_lastNode )
1282  {
1283  // Do a final optimization to the stored state
1284  NODE::ITEM_VECTOR removed, added;
1285  m_lastNode->GetUpdatedItems( removed, added );
1286 
1287  if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1288  simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1289  }
1290 
1291  // Nothing to commit if we have an empty line
1292  if( !pl.EndsWithVia() )
1293  return false;
1294 
1297  if( m_lastNode )
1298  m_lastNode->Add( Clone( pl.Via() ) );
1299 
1300  m_currentNode = nullptr;
1301 
1302  m_idle = true;
1303  m_placementCorrect = true;
1304  return true;
1305  }
1306 
1307  VECTOR2I p_pre_last = l.CPoint( -1 );
1308  const VECTOR2I p_last = l.CPoint( -1 );
1309 
1310  if( l.PointCount() > 2 )
1311  p_pre_last = l.CPoint( -2 );
1312 
1313  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1314  realEnd = true;
1315 
1316  if( aForceFinish )
1317  realEnd = true;
1318 
1319  // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1320  // so if we are, act as though we are in fix-all mode.
1321  if( !fixAll && l.ArcCount() )
1322  fixAll = true;
1323 
1324  // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1325  SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1326  DIRECTION_45 d_last( lastDirSeg );
1327 
1328  int lastV;
1329 
1330  if( realEnd || m_placingVia || fixAll )
1331  lastV = l.SegmentCount();
1332  else
1333  lastV = std::max( 1, l.SegmentCount() - 1 );
1334 
1335  ARC arc;
1336  SEGMENT seg;
1337  LINKED_ITEM* lastItem = nullptr;
1338  int lastArc = -1;
1339 
1340  for( int i = 0; i < lastV; i++ )
1341  {
1342  ssize_t arcIndex = l.ArcIndex( i );
1343 
1344  if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1345  {
1346  seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1347  seg.SetWidth( pl.Width() );
1348  seg.SetLayer( m_currentLayer );
1349 
1350  std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1351  lastItem = sp.get();
1352 
1353  if( !m_lastNode->Add( std::move( sp ) ) )
1354  lastItem = nullptr;
1355  }
1356  else
1357  {
1358  if( arcIndex == lastArc )
1359  continue;
1360 
1361  arc = ARC( l.Arc( arcIndex ), m_currentNet );
1362  arc.SetWidth( pl.Width() );
1363  arc.SetLayer( m_currentLayer );
1364 
1365  std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1366  lastItem = ap.get();
1367 
1368  if( !m_lastNode->Add( std::move( ap ) ) )
1369  lastItem = nullptr;
1370 
1371  lastArc = arcIndex;
1372  }
1373  }
1374 
1375  if( pl.EndsWithVia() )
1376  m_lastNode->Add( Clone( pl.Via() ) );
1377 
1378  if( realEnd && lastItem )
1379  simplifyNewLine( m_lastNode, lastItem );
1380 
1381  if( !realEnd )
1382  {
1383  setInitialDirection( d_last );
1384  m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1385 
1386  VECTOR2I ps;
1387  if( m_tail.SegmentCount() )
1388  ps = m_tail.CPoint( 0 );
1389  else
1390  ps = m_p_start;
1391 
1393 
1394  m_startItem = nullptr;
1395  m_placingVia = false;
1397 
1400 
1401  m_head.Line().Clear();
1402  m_tail.Line().Clear();
1403  m_head.RemoveVia();
1404  m_tail.RemoveVia();
1407 
1408  if( m_shove )
1409  m_shove->AddLockedSpringbackNode( m_currentNode );
1410 
1411  DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1412 
1417 
1418  m_placementCorrect = true;
1419  }
1420  else
1421  {
1422  m_placementCorrect = true;
1423  m_idle = true;
1424  }
1425 
1426  return realEnd;
1427 }
1428 
1429 
1431 {
1432  FIXED_TAIL::STAGE st;
1433 
1434  if ( !m_fixedTail.PopStage( st ) )
1435  return false;
1436 
1437  m_head.Line().Clear();
1438  m_tail.Line().Clear();
1439  m_startItem = nullptr;
1440  m_p_start = st.pts[0].p;
1441  m_direction = st.pts[0].direction;
1442  m_placingVia = st.pts[0].placingVias;
1443  m_currentNode = st.commit;
1444  m_currentLayer = st.pts[0].layer;
1447  m_head.RemoveVia();
1448  m_tail.RemoveVia();
1449 
1453 
1454  if( m_shove )
1455  {
1456  m_shove->RewindSpringbackTo( m_currentNode );
1457  m_shove->UnlockSpringbackNode( m_currentNode );
1458  m_currentNode = m_shove->CurrentNode();
1460  }
1461 
1463 
1464  return true;
1465 }
1466 
1467 
1469 {
1470  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1471 }
1472 
1473 
1475 {
1476  if( m_lastNode )
1478 
1479  m_lastNode = nullptr;
1480  m_currentNode = nullptr;
1481  return true;
1482 }
1483 
1484 
1485 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1486 {
1487  if( !aLatest.SegmentCount() )
1488  return;
1489 
1490  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1491  return;
1492 
1493  std::set<LINKED_ITEM *> toErase;
1494  aNode->Add( aLatest, true );
1495 
1496  for( int s = 0; s < aLatest.LinkCount(); s++ )
1497  {
1498  LINKED_ITEM* seg = aLatest.GetLink(s);
1499  LINE ourLine = aNode->AssembleLine( seg );
1500  JOINT a, b;
1501  std::vector<LINE> lines;
1502 
1503  aNode->FindLineEnds( ourLine, a, b );
1504 
1505  if( a == b )
1506  aNode->FindLineEnds( aLatest, a, b );
1507 
1508  aNode->FindLinesBetweenJoints( a, b, lines );
1509 
1510  int removedCount = 0;
1511  int total = 0;
1512 
1513  for( LINE& line : lines )
1514  {
1515  total++;
1516 
1517  if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1518  {
1519  for( LINKED_ITEM* ss : line.Links() )
1520  toErase.insert( ss );
1521 
1522  removedCount++;
1523  }
1524  }
1525 
1526  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1527  }
1528 
1529  for( LINKED_ITEM* s : toErase )
1530  aNode->Remove( s );
1531 
1532  aNode->Remove( aLatest );
1533 }
1534 
1535 
1537 {
1538  wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1539 
1540  // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1541  // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1542  // of the line and won't get cleaned up by the optimizer.
1543  NODE::ITEM_VECTOR removed, added;
1544  aNode->GetUpdatedItems( removed, added );
1545 
1546  std::set<ITEM*> cleanup;
1547 
1548  auto processJoint =
1549  [&]( JOINT* aJoint, ITEM* aItem )
1550  {
1551  if( !aJoint || aJoint->IsLineCorner() )
1552  return;
1553 
1554  SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1555 
1556  NODE::ITEM_VECTOR toRemove;
1557 
1558  for( ITEM* neighbor : aJoint->Links() )
1559  {
1560  if( neighbor == aItem || !neighbor->LayersOverlap( aItem ) )
1561  continue;
1562 
1563  const SEG& testSeg = static_cast<SEGMENT*>( neighbor )->Seg();
1564 
1565  if( refSeg.Contains( testSeg ) )
1566  {
1567  JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1568  JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1569 
1570  if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1571  ( nB == aJoint && nA->LinkCount() == 1 ) )
1572  {
1573  cleanup.insert( neighbor );
1574  }
1575  }
1576  }
1577  };
1578 
1579  for( ITEM* item : added )
1580  {
1581  if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1582  continue;
1583 
1584  JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1585  JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1586 
1587  processJoint( jA, item );
1588  processJoint( jB, item );
1589  }
1590 
1591  for( ITEM* seg : cleanup )
1592  aNode->Remove( seg );
1593 
1594  // And now we can proceed with assembling the final line and optimizing it.
1595 
1596  LINE l = aNode->AssembleLine( aLatest );
1597 
1598  bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1599 
1600  SHAPE_LINE_CHAIN simplified( l.CLine() );
1601 
1602  simplified.Simplify();
1603 
1604  if( optimized || simplified.PointCount() != l.PointCount() )
1605  {
1606  aNode->Remove( l );
1607  l.SetShape( simplified );
1608  aNode->Add( l );
1609  }
1610 }
1611 
1612 
1614 {
1615  m_sizes = aSizes;
1616 
1617  if( !m_idle )
1618  {
1619  // If the track width was originally determined from the rules resolver ("use netclass
1620  // width") or continuing from an existing track, we don't want to change the width unless
1621  // the user is moving to an explicitly-specified value.
1622  // NOTE: This doesn't quite correctly handle the case of moving *from* an explicit value
1623  // *to* the "use netclass width" value, but that is more complicated to handle.
1625  {
1628  }
1629 
1630  if( m_head.EndsWithVia() )
1631  {
1634  }
1635  }
1636 }
1637 
1638 
1640 {
1641  LINE current = Trace();
1642  SHAPE_LINE_CHAIN ratLine;
1643  TOPOLOGY topo( m_lastNode );
1644 
1645  if( topo.LeadingRatLine( &current, ratLine ) )
1646  m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1647 }
1648 
1649 
1650 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1651 {
1652  m_orthoMode = aOrthoMode;
1653 }
1654 
1655 
1656 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia )
1657 {
1658  SHAPE_LINE_CHAIN l;
1659  DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1660 
1661  wxLogTrace( "PNS", "buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1662  m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1663 
1664  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1665  bool fillet = !m_orthoMode && Settings().GetCornerMode() == CORNER_MODE::ROUNDED_45;
1666 
1667  if( m_p_start == aP )
1668  {
1669  l.Clear();
1670  }
1671  else
1672  {
1673  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1674  {
1675  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1676  }
1677  else
1678  {
1679  if( !m_tail.PointCount() )
1680  l = guessedDir.BuildInitialTrace( m_p_start, aP, false, fillet );
1681  else
1682  l = m_direction.BuildInitialTrace( m_p_start, aP, false, fillet );
1683  }
1684 
1685  if( l.SegmentCount() > 1 && m_orthoMode )
1686  {
1687  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1688 
1689  l.Remove( -1, -1 );
1690  l.SetPoint( 1, newLast );
1691  }
1692  }
1693 
1694  aHead.SetLayer( m_currentLayer );
1695  aHead.SetShape( l );
1696 
1697  if( !m_placingVia || aForceNoVia )
1698  return true;
1699 
1700  VIA v( makeVia( aP ) );
1701  v.SetNet( aHead.Net() );
1702 
1704  {
1705  aHead.AppendVia( v );
1706  return true;
1707  }
1708 
1709  VECTOR2I force;
1710  VECTOR2I lead = aP - m_p_start;
1711 
1712  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1713 
1714  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1715  {
1716  SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false,
1717  fillet );
1718  aHead = LINE( aHead, line );
1719 
1720  v.SetPos( v.Pos() + force );
1721  return true;
1722  }
1723 
1724  return false; // via placement unsuccessful
1725 }
1726 
1727 
1728 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1729 {
1730  aNets.push_back( m_currentNet );
1731 }
1732 
1733 
1735 {
1736  m_world->KillChildren();
1737  return true;
1738 }
1739 
1740 
1741 FIXED_TAIL::FIXED_TAIL( int aLineCount )
1742 {
1743 
1744 }
1745 
1746 
1748 {
1749 
1750 }
1751 
1752 
1754 {
1755  m_stages.clear();
1756 }
1757 
1758 
1759 void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
1760  DIRECTION_45 direction, NODE* aNode )
1761 {
1762  STAGE st;
1763  FIX_POINT pt;
1764 
1765  pt.p = aStart;
1766  pt.layer = aLayer;
1767  pt.direction = direction;
1768  pt.placingVias = placingVias;
1769 
1770  st.pts.push_back(pt);
1771  st.commit = aNode;
1772 
1773  m_stages.push_back( st );
1774 }
1775 
1776 
1778 {
1779  if( !m_stages.size() )
1780  return false;
1781 
1782  aStage = m_stages.back();
1783 
1784  if( m_stages.size() > 1 )
1785  m_stages.pop_back();
1786 
1787  return true;
1788 }
1789 
1790 
1792 {
1793  return m_stages.size();
1794 }
1795 
1796 }
1797 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
int Length() const
Return the length (this).
Definition: seg.h:350
Represent an intersection between two line segments.
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
int PrevShape(int aPointIndex) const
#define PNS_DBGN(dbg, method)
Base class for PNS router board items.
Definition: pns_item.h:55
bool SmartPads() const
Enable/disable Smart Pads (optimized connections).
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Return length of the line chain in Euclidean metric.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:198
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).
LINE m_last_head
Most recent successful (non-colliding) head.
VECTOR2I v2(1, 0)
Test suite for KiCad math code.
std::vector< INTERSECTION > INTERSECTIONS
Keep the router "world" - i.e.
Definition: pns_node.h:144
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
std::vector< STAGE > m_stages
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
NODE * m_world
pointer to world to search colliding items
void SetLayer(int aLayer)
Definition: pns_item.h:155
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:146
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:117
bool Is45Degree() const
Print out all linked segments.
Definition: pns_line.cpp:537
void CommitRouting()
Definition: pns_router.cpp:695
H/V/45 with filleted corners.
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
Simplify pad-pad and pad-via connections if possible.
WALKAROUND_STATUS statusCw
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
VECTOR2I::extended_type ecoord
Definition: seg.h:43
virtual LOGGER * Logger()
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1028
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
void RemoveVia()
Definition: pns_line.h:194
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step shove mode.
SIZES_SETTINGS m_sizes
std::vector< FIX_POINT > pts
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find the joints corresponding to the ends of line aLine.
Definition: pns_node.cpp:1035
bool PopStage(STAGE &aStage)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
FIXED_TAIL(int aLineCount=1)
const LINE Trace() const
Return the complete routed line.
class PAD, a pad in a footprint
Definition: typeinfo.h:89
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1030
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, int aColor=-1)=0
size_t ArcCount() const
const SEG & Seg() const
Definition: pns_segment.h:84
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
int Depth() const
Definition: pns_node.h:189
const std::vector< SHAPE_ARC > & CArcs() const
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Return the number of points (vertices) in this line chain.
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
const VECTOR2I & Pos() const
Definition: pns_via.h:99
int PointCount() const
Definition: pns_line.h:140
bool RemoveLoops() const
Enable/disable loop (redundant track) removal.
bool EndsWithVia() const
Definition: pns_line.h:191
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:149
void SetNet(int aNet)
Definition: pns_item.h:149
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:145
VIATYPE ViaType() const
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void SetCollisionMask(int aMask)
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, bool aSolidsOnly=true, int aMaxIterations=10)
Definition: pns_via.cpp:32
LINE_PLACER(ROUTER *aRouter)
bool FollowMouse() const
Return true if smoothing segments during dragging is enabled.
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:126
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
ITEM_SET & Links()
Definition: pns_joint.h:205
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
Definition: color4d.h:67
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:42
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:268
ROUTER * m_router
Definition: pns_algo_base.h:87
bool IsLineCorner() const
Definition: pns_joint.h:100
static bool cursorDistMinimum(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, int &theDist, VECTOR2I &aNearest)
DIRECTION_45 m_initial_direction
routing direction for new traces
void KillChildren()
Definition: pns_node.cpp:1405
bool IsArcSegment(size_t aSegment) const
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)
Set preferred direction of the very first track segment to be laid.
void SetWidth(int aWidth) override
Definition: pns_segment.h:74
int Net() const
Definition: pns_item.h:150
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
bool TrackWidthIsExplicit() const
std::unique_ptr< SHOVE > m_shove
The shove engine.
DIRECTION_45 m_direction
current routing direction
Definition: color4d.h:57
const VECTOR2I & GetP0() const
Definition: shape_arc.h:111
void initPlacement()
Initialize placement of a new line with given parameters.
#define PNS_DBG(dbg, method,...)
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void AddTrailPoint(const VECTOR2I &aP)
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
Definition: pns_line.cpp:566
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
PNS_MODE Mode() const
Set the routing mode.
void SetWidth(int aWidth) override
Definition: pns_arc.h:82
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:227
bool routeHead(const VECTOR2I &aP, LINE &aNewHead)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
Definition: color4d.h:58
void SetSolidsOnly(bool aSolidsOnly)
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
bool HasPlacedAnything() const override
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
VECTOR2I closestProjectedPoint(const SHAPE_LINE_CHAIN &line, const VECTOR2I &p)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
void GetModifiedNets(std::vector< int > &aNets) const override
Function GetModifiedNets.
FIXED_TAIL m_fixedTail
int SegmentCount() const
Return the number of segments in this line chain.
bool CommitPlacement() override
bool IsPtOnArc(size_t aPtIndex) const
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
void AddStage(const VECTOR2I &aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:296
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1140
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead)
Route step mark obstacles mode.
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:136
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:101
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:380
Definition: color4d.h:48
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
Definition: seg.h:40
void SetViaDrill(int aDrill)
Definition: pns_line.h:199
Guess what's better, try to make least mess on the PCB.
NODE * m_currentNode
Current world state.
int ShapeCount() const
Return the aIdx-th point of the line.
Definition: pns_line.h:142
Definition: color4d.h:56
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:65
void setWorld(NODE *aWorld)
Set the board to route.
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
Ignore collisions, mark obstacles.
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
CORNER_MODE GetCornerMode() const
const char * name
Definition: DXF_plotter.cpp:56
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:265
Represent a polyline (an zero-thickness chain of connected line segments).
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:450
Definition: layer_ids.h:70
WALKAROUND_STATUS statusCcw
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:1122
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
VECTOR2I A
Definition: seg.h:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:136
double WalkaroundHugLengthThreshold() const
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
bool SetLayer(int aLayer) override
Set the current routing layer.
Only walk around.
DIRECTION_45 GetPosture(const VECTOR2I &aP)
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1338
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:128
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:94
void Clear()
Remove all points from the line chain.
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void SetWorld(NODE *aNode)
Merge co-linear segments.
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:210
void SetEffortLevel(int aEffort)
void Clear()
Definition: pns_line.cpp:1242
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
NODE * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:169
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
bool AbortPlacement() override
const VIA & Via() const
Definition: pns_line.h:196
const VIA makeVia(const VECTOR2I &aP)
int StageCount() const
Push and Shove diff pair dimensions (gap) settings dialog.
void SetLogger(LOGGER *aLogger)
Definition: pns_algo_base.h:65
NODE * GetWorld() const
Definition: pns_router.h:153
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:207
void SetIterationLimit(const int aIterLimit)
bool UnfixRoute() override
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:31
const LAYER_RANGE & Layers() const
Definition: pns_item.h:152
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946
Reroute pad exits.
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:148
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
int CountCorners(int aAngles) const
Definition: pns_line.cpp:135
void SetBlockingObstacle(ITEM *aObstacle)
Definition: pns_line.h:205
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49