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  const std::vector<ssize_t>& headShapes = head.CShapes();
198  const std::vector<ssize_t>& tailShapes = tail.CShapes();
199 
200  wxASSERT( tail.PointCount() >= 2 );
201 
202  if( headShapes[0] == -1 )
203  first_head = DIRECTION_45( head.CSegment( 0 ) );
204  else
205  first_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
206 
207  int lastSegIdx = tail.PointCount() - 2;
208 
209  if( tailShapes[lastSegIdx] == -1 )
210  last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
211  else
212  last_tail = DIRECTION_45( tail.CArcs()[tailShapes[lastSegIdx]] );
213 
214  DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
215 
216  // case 1: we have a defined routing direction, and the currently computed
217  // head goes in different one.
218  bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
219 
220  // case 2: regardless of the current routing direction, if the tail/head
221  // extremities form an acute or right angle, reduce the tail by one segment
222  // (and hope that further iterations) will result with a cleaner trace
223  bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
224 
225  if( pullback_1 || pullback_2 )
226  {
227  lastSegIdx = tail.PrevShape( -1 );
228 
229  if( tailShapes[lastSegIdx] == -1 )
230  {
231  const SEG& seg = tail.CSegment( lastSegIdx );
232  m_direction = DIRECTION_45( seg );
233  m_p_start = seg.A;
234  }
235  else
236  {
237  const SHAPE_ARC& arc = tail.CArcs()[tailShapes[lastSegIdx]];
238  m_direction = DIRECTION_45( arc );
239  m_p_start = arc.GetP0();
240  }
241 
242  wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
243  n, last_tail.Format().c_str(), first_head.Format().c_str() );
244 
245  // erase the last point in the tail, hoping that the next iteration will
246  // result with a head trace that starts with a segment following our
247  // current direction.
248  if( n < 2 )
249  tail.Clear(); // don't leave a single-point tail
250  else
251  tail.RemoveShape( -1 );
252 
253  if( !tail.SegmentCount() )
255 
256  return true;
257  }
258 
259  return false;
260 }
261 
262 
264 {
265  SHAPE_LINE_CHAIN& head = m_head.Line();
266  SHAPE_LINE_CHAIN& tail = m_tail.Line();
267 
268  int n = tail.SegmentCount();
269 
270  if( head.SegmentCount() < 1 )
271  return false;
272 
273  // Don't attempt this for too short tails
274  if( n < 2 )
275  return false;
276 
277  // Start from the segment farthest from the end of the tail
278  // int start_index = std::max(n - 1 - ReductionDepth, 0);
279 
280  DIRECTION_45 new_direction;
281  VECTOR2I new_start;
282  int reduce_index = -1;
283 
284  for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
285  {
286  const SEG s = tail.CSegment( i );
287  DIRECTION_45 dir( s );
288 
289  // calculate a replacement route and check if it matches
290  // the direction of the segment to be replaced
291  SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
292 
293  if( replacement.SegmentCount() < 1 )
294  continue;
295 
296  LINE tmp( m_tail, replacement );
297 
299  break;
300 
301  if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
302  {
303  new_start = s.A;
304  new_direction = dir;
305  reduce_index = i;
306  }
307  }
308 
309  if( reduce_index >= 0 )
310  {
311  wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
312  SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
313 
314  m_p_start = new_start;
315  m_direction = new_direction;
316  tail.Remove( reduce_index + 1, -1 );
317  head.Clear();
318  return true;
319  }
320 
321  if( !tail.SegmentCount() )
323 
324  return false;
325 }
326 
327 
329 {
330  SHAPE_LINE_CHAIN& head = m_head.Line();
331  SHAPE_LINE_CHAIN& tail = m_tail.Line();
332 
333  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
336 
337  head.Simplify();
338  tail.Simplify();
339 
340  int n_head = head.ShapeCount();
341  int n_tail = tail.ShapeCount();
342 
343  if( n_head < 3 )
344  {
345  wxLogTrace( "PNS", "Merge failed: not enough head segs." );
346  return false;
347  }
348 
349  if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
350  {
351  wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
352  return false;
353  }
354 
355  if( m_head.CountCorners( ForbiddenAngles ) != 0 )
356  return false;
357 
358  DIRECTION_45 dir_tail, dir_head;
359 
360  const std::vector<ssize_t>& headShapes = head.CShapes();
361  const std::vector<ssize_t>& tailShapes = tail.CShapes();
362 
363  if( headShapes[0] == -1 )
364  dir_head = DIRECTION_45( head.CSegment( 0 ) );
365  else
366  dir_head = DIRECTION_45( head.CArcs()[ headShapes[0] ] );
367 
368  if( n_tail )
369  {
370  wxASSERT( tail.PointCount() >= 2 );
371  int lastSegIdx = tail.PointCount() - 2;
372 
373  if( tailShapes[lastSegIdx] == -1 )
374  dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
375  else
376  dir_tail = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
377 
378  if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
379  return false;
380  }
381 
382  tail.Append( head );
383 
384  tail.Simplify();
385 
386  SEG last = tail.CSegment( -1 );
387  m_p_start = last.B;
388 
389  int lastSegIdx = tail.PointCount() - 2;
390 
391  if( tailShapes[lastSegIdx] == -1 )
392  m_direction = DIRECTION_45( tail.CSegment( -1 ) );
393  else
394  m_direction = DIRECTION_45( tail.CArcs()[ tailShapes[lastSegIdx] ] );
395 
396  head.Remove( 0, -1 );
397 
398  wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head,
399  m_direction.Format().c_str() );
400 
401  head.Simplify();
402  tail.Simplify();
403 
404  return true;
405 }
406 
407 
409 {
410  // Keep distances squared for performance
411  SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
412  VECTOR2I closest;
413 
414  for( int i = 0; i < line.SegmentCount(); i++ )
415  {
416  const SEG& s = line.CSegment( i );
417  VECTOR2I a = s.NearestPoint( p );
418  int d_sq = (a - p).SquaredEuclideanNorm();
419 
420  if( d_sq < min_dist_sq )
421  {
422  min_dist_sq = d_sq;
423  closest = a;
424  }
425  }
426 
427  return closest;
428 }
429 
430 
431 static bool cursorDistMinimum( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aCursor, double lengthThreshold, int& theDist, VECTOR2I& aNearest )
432 {
433  std::vector<int> dists;
434  std::vector<VECTOR2I> pts;
435 
436  if( aL.PointCount() == 0 )
437  return false;
438 
439  VECTOR2I lastP = aL.CPoint(-1);
440  int accumulatedDist = 0;
441 
442  dists.reserve( 2 * aL.PointCount() );
443 
444  for( int i = 0; i < aL.SegmentCount(); i++ )
445  {
446  const SEG& s = aL.CSegment( i );
447 
448  dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
449  pts.push_back( s.A );
450  auto pn = s.NearestPoint( aCursor );
451 
452  if( pn != s.A && pn != s.B )
453  {
454  dists.push_back( ( pn - aCursor ).EuclideanNorm() );
455  pts.push_back( pn );
456  }
457 
458  accumulatedDist += s.Length();
459 
460  if ( accumulatedDist > lengthThreshold )
461  {
462  lastP = s.B;
463  break;
464  }
465  }
466 
467  dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
468  pts.push_back( lastP );
469 
470  int minDistLoc = std::numeric_limits<int>::max();
471  int minPLoc = -1;
472  int minDistGlob = std::numeric_limits<int>::max();
473  int minPGlob = -1;
474 
475  for( int i = 0; i < dists.size(); i++ )
476  {
477  int d = dists[i];
478 
479  if( d < minDistGlob )
480  {
481  minDistGlob = d;
482  minPGlob = i;
483  }
484  }
485 
486  if( dists.size() >= 3 )
487  {
488  for( int i = 0; i < dists.size() - 3; i++ )
489  {
490  if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
491  {
492  int d = dists[i + 1];
493  if( d < minDistLoc )
494  {
495  minDistLoc = d;
496  minPLoc = i + 1;
497  }
498  }
499  }
500 
501  if( dists.back() < minDistLoc && minPLoc >= 0 )
502  {
503  minDistLoc = dists.back();
504  minPLoc = dists.size() - 1;
505  }
506  }
507  else
508  {
509  // Too few points: just use the global
510  minDistLoc = minDistGlob;
511  minPLoc = minPGlob;
512  }
513 
514 // fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
515 // in the code, enabling the global one by default
516  minPLoc = -1;
517 
518  if( minPLoc < 0 )
519  {
520  theDist = minDistGlob;
521  aNearest = pts[minPGlob];
522  return true;
523  }
524  else
525  {
526  theDist = minDistLoc;
527  aNearest = pts[minPLoc];
528  return true;
529  }
530 }
531 
532 
533 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
534 {
535  LINE initTrack( m_head );
536  LINE walkFull( m_head );
537 
538  initTrack.RemoveVia();
539  walkFull.RemoveVia();
540 
541  int effort = 0;
542  bool viaOk = false;
543 
544  VECTOR2I walkP = aP;
545 
546  WALKAROUND walkaround( m_currentNode, Router() );
547 
548  walkaround.SetSolidsOnly( false );
549  walkaround.SetDebugDecorator( Dbg() );
550  walkaround.SetLogger( Logger() );
551  walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
552 
553  char name[50];
554  int round = 0;
555 
556  do {
557  snprintf( name, sizeof( name ), "walk-round-%d", round );
558  PNS_DBG( Dbg(), BeginGroup, name );
559 
560  viaOk = buildInitialLine( walkP, initTrack, round == 0 );
561 
562  double initialLength = initTrack.CLine().Length();
563  double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
564 
565  WALKAROUND::RESULT wr = walkaround.Route( initTrack );
566 
567  SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
568  SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
569 
571  {
572  int len_cw = wr.statusCw == WALKAROUND::DONE ? l_cw.Length() : INT_MAX;
573  int len_ccw = wr.statusCcw == WALKAROUND::DONE ? l_ccw.Length() : INT_MAX;
574 
575  PNS_DBG( Dbg(), AddLine, wr.lineCw.CLine(), CYAN, 10000, "wf-result-cw" );
576  PNS_DBG( Dbg(), AddLine, wr.lineCcw.CLine(), BLUE, 20000, "wf-result-ccw" );
577 
578  int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
579 
580  if( bestLength > hugThresholdLength )
581  {
584  }
585 
586  SHAPE_LINE_CHAIN& bestLine = len_cw < len_ccw ? l_cw : l_ccw;
587  walkFull.SetShape( bestLine );
588  }
589 
591  {
592  bool valid_cw = false, valid_ccw = false;
593  VECTOR2I p_cw, p_ccw;
594  int dist_ccw, dist_cw;
595 
597  {
598  valid_ccw = cursorDistMinimum( l_ccw, aP, hugThresholdLength, dist_ccw, p_ccw );
599  if( valid_ccw )
600  {
601  int idx_ccw = l_ccw.Split( p_ccw );
602  l_ccw = l_ccw.Slice( 0, idx_ccw );
603  PNS_DBG( Dbg(), AddPoint, p_ccw, BLUE, 500000, "hug-target-ccw" );
604  PNS_DBG( Dbg(), AddLine, l_ccw, MAGENTA, 200000, "wh-result-ccw" );
605  }
606  }
608  {
609  valid_cw = cursorDistMinimum( l_cw, aP, hugThresholdLength, dist_cw, p_cw );
610  if( valid_cw )
611  {
612  int idx_cw = l_cw.Split( p_cw );
613  l_cw = l_cw.Slice( 0, idx_cw );
614  PNS_DBG( Dbg(), AddPoint, p_cw, YELLOW, 500000, "hug-target-cw" );
615  PNS_DBG( Dbg(), AddLine, l_cw, BLUE, 200000, "wh-result-cw" );
616  }
617  }
618 
619  if( dist_cw < dist_ccw && valid_cw )
620  {
621  walkFull.SetShape( l_cw );
622  walkP = p_cw;
623  }
624  else if ( valid_ccw )
625  {
626  walkFull.SetShape( l_ccw );
627  walkP = p_ccw;
628  }
629  else
630  {
631  PNS_DBGN( Dbg(), EndGroup );
632  return false;
633  }
634  }
635  else if ( wr.statusCcw == WALKAROUND::STUCK || wr.statusCw == WALKAROUND::STUCK )
636  {
637  PNS_DBGN( Dbg(), EndGroup );
638  return false;
639  }
640 
641  PNS_DBGN( Dbg(), EndGroup );
642 
643  round++;
644  } while( round < 2 && m_placingVia );
645 
646  PNS_DBG( Dbg(), AddLine, walkFull.CLine(), GREEN, 200000, "walk-full" );
647 
648  switch( Settings().OptimizerEffort() )
649  {
650  case OE_LOW:
651  effort = 0;
652  break;
653 
654  case OE_MEDIUM:
655  case OE_FULL:
656  effort = OPTIMIZER::MERGE_SEGMENTS;
657  break;
658  }
659 
661  effort |= OPTIMIZER::SMART_PADS;
662 
663  if( m_placingVia && viaOk )
664  {
665  walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
666  }
667 
668  OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
669 
670 
671  if( m_currentNode->CheckColliding( &walkFull ) )
672  {
673  return false;
674  }
675 
676  aNewHead = walkFull;
677 
678  return true;
679 }
680 
681 
682 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
683 {
684  buildInitialLine( aP, m_head );
685  m_head.SetBlockingObstacle( nullptr );
686 
687  // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
688  // but we don't have one right now and there isn't a lot of demand for one. If we do end up
689  // doing that, put it in a new routing mode as "highlight collisions" mode should not have
690  // collision handling other than highlighting.
691 #if 0
692  if( !Settings().AllowDRCViolations() )
693  {
695 
696  if( obs && obs->m_distFirst != INT_MAX )
697  {
698  buildInitialLine( obs->m_ipFirst, m_head );
699  m_head.SetBlockingObstacle( obs->m_item );
700  }
701  }
702 #endif
703 
704  aNewHead = m_head;
705 
706  return true;
707 }
708 
709 
710 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
711 {
712  LINE initTrack( m_head );
713  LINE walkSolids, l2;
714 
715  bool viaOk = buildInitialLine( aP, initTrack );
716 
717  m_currentNode = m_shove->CurrentNode();
718 
719  m_shove->SetLogger( Logger() );
720  m_shove->SetDebugDecorator( Dbg() );
721 
722  OPTIMIZER optimizer( m_currentNode );
723 
724  WALKAROUND walkaround( m_currentNode, Router() );
725 
726  walkaround.SetSolidsOnly( true );
727  walkaround.SetIterationLimit( 10 );
728  walkaround.SetDebugDecorator( Dbg() );
729  walkaround.SetLogger( Logger() );
730  WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
731 
733  optimizer.SetCollisionMask( ITEM::SOLID_T );
734  optimizer.Optimize( &walkSolids );
735 
736  if( stat_solids == WALKAROUND::DONE )
737  l2 = walkSolids;
738  else
739  l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
740 
741  LINE l( m_tail );
742  l.Line().Append( l2.CLine() );
743  l.Line().Simplify();
744 
745  if( l.PointCount() == 0 || l2.PointCount() == 0 )
746  {
747  aNewHead = m_head;
748  return false;
749  }
750 
751  if( m_placingVia && viaOk )
752  {
753  VIA v1( makeVia( l.CPoint( -1 ) ) );
754  VIA v2( makeVia( l2.CPoint( -1 ) ) );
755 
756  l.AppendVia( v1 );
757  l2.AppendVia( v2 );
758  }
759 
760  l.Line().Simplify();
761 
762  // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
763  // shove to avoid screwing up the database.
764  if( l.HasLoops() )
765  {
766  aNewHead = m_head;
767  return false;
768  }
769 
770  SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
771 
772  m_currentNode = m_shove->CurrentNode();
773 
774  if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
775  {
776  if( status == SHOVE::SH_HEAD_MODIFIED )
777  l2 = m_shove->NewHead();
778 
779  optimizer.SetWorld( m_currentNode );
780 
781  int effortLevel = OPTIMIZER::MERGE_OBTUSE;
782 
783  if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
784  effortLevel = OPTIMIZER::SMART_PADS;
785 
786  optimizer.SetEffortLevel( effortLevel );
787 
788  optimizer.SetCollisionMask( ITEM::ANY_T );
789  optimizer.Optimize( &l2 );
790 
791  aNewHead = l2;
792 
793  return true;
794  }
795  else
796  {
797  walkaround.SetWorld( m_currentNode );
798  walkaround.SetSolidsOnly( false );
799  walkaround.SetIterationLimit( 10 );
800  walkaround.SetApproachCursor( true, aP );
801  walkaround.Route( initTrack, l2 );
802  aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
803 
804  return false;
805  }
806 
807  return false;
808 }
809 
810 
811 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
812 {
813  switch( m_currentMode )
814  {
815  case RM_MarkObstacles:
816  return rhMarkObstacles( aP, aNewHead );
817  case RM_Walkaround:
818  return rhWalkOnly( aP, aNewHead );
819  case RM_Shove:
820  return rhShoveOnly( aP, aNewHead );
821  default:
822  break;
823  }
824 
825  return false;
826 }
827 
828 
830 {
831  LINE linetmp = Trace();
832 
833  PNS_DBG( Dbg(), Message, "optimize HT" );
834 
836  {
837  if( linetmp.SegmentCount() < 1 )
838  return false;
839 
840  m_head = linetmp;
841  m_p_start = linetmp.CLine().CPoint( 0 );
842  m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
843  m_tail.Line().Clear();
844 
845  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize fanout-cleanup" ) );
846 
847 
848  return true;
849  }
850 
851  SHAPE_LINE_CHAIN& head = m_head.Line();
852  SHAPE_LINE_CHAIN& tail = m_tail.Line();
853 
854  int tailLookbackSegments = 3;
855 
856  //if(m_currentMode() == RM_Walkaround)
857  // tailLookbackSegments = 10000;
858 
859  int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
860 
861  if( tail.ShapeCount() < 3 )
862  return false;
863 
864  // assemble TailLookbackSegments tail segments with the current head
865  SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
866 
867  int end = std::min(2, head.PointCount() - 1 );
868 
869  opt_line.Append( head.Slice( 0, end ) );
870 
871  LINE new_head( m_tail, opt_line );
872 
873  // and see if it could be made simpler by merging obtuse/collnear segments.
874  // If so, replace the (threshold) last tail points and the head with
875  // the optimized line
876 
877 
878  PNS_DBG( Dbg(), AddLine, new_head.CLine(), LIGHTCYAN, 10000, "ht-newline" );
879 
881  {
882  LINE tmp( m_tail, opt_line );
883 
884  PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize tail-head [%d]", threshold ) );
885 
886  head.Clear();
887  tail.Replace( -threshold, -1, new_head.CLine() );
888  tail.Simplify();
889 
890  m_p_start = new_head.CLine().CPoint( -1 );
891  m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
892 
893  return true;
894  }
895 
896  return false;
897 }
898 
899 
901 {
902  bool fail = false;
903  bool go_back = false;
904 
905  int i, n_iter = 1;
906 
907  LINE new_head;
908 
909  wxLogTrace( "PNS", "routeStep: direction: %s head: %d, tail: %d shapes",
910  m_direction.Format().c_str(),
911  m_head.ShapeCount(),
912  m_tail.ShapeCount() );
913 
914  PNS_DBG( Dbg(), BeginGroup, "route-step" );
915 
916  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-init" );
917  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-init" );
918 
919  for( i = 0; i < n_iter; i++ )
920  {
921  if( !go_back && Settings().FollowMouse() )
922  reduceTail( aP );
923 
924  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-reduce" );
925  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-reduce" );
926 
927  go_back = false;
928 
929  if( !routeHead( aP, new_head ) )
930  fail = true;
931 
932  if( !new_head.Is45Degree() )
933  fail = true;
934 
935  if( fail )
936  break;
937 
938  m_head = new_head;
939 
940  PNS_DBG( Dbg(), AddLine, m_head.CLine(), LIGHTGREEN, 100000, "head-new" );
941 
943  {
944  n_iter++;
945  go_back = true;
946  }
947 
948  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-si" );
949  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-si" );
950 
951  if( !go_back && handlePullback() )
952  {
953  n_iter++;
954  go_back = true;
955  }
956 
957  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-after-pb" );
958  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-after-pb" );
959  }
960 
961  if( fail )
962  {
963  if( m_last_head.PointCount() > 0 )
964  {
966  }
967  else
968  {
969  m_head.RemoveVia();
970  m_head.Clear();
971  }
972  }
973  else
974  {
976  }
977 
978  if( !fail && Settings().FollowMouse() )
979  {
980  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-pre-merge" );
981  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-pre-merge" );
982 
984  {
985  mergeHead();
986  }
987 
988  PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-post-merge" );
989  PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-post-merge" );
990  }
991 
992  PNS_DBGN( Dbg(), EndGroup );
993 }
994 
995 
996 bool LINE_PLACER::route( const VECTOR2I& aP )
997 {
998  routeStep( aP );
999 
1000  if (!m_head.PointCount() )
1001  return false;
1002 
1003  return m_head.CPoint(-1) == aP;
1004 }
1005 
1006 
1008 {
1009  LINE tmp( m_head );
1010 
1011  tmp.SetShape( m_tail.CLine() );
1012  tmp.Line().Append( m_head.CLine() );
1013  tmp.Line().Simplify();
1014  return tmp;
1015 }
1016 
1017 
1019 {
1020  m_currentTrace = Trace();
1021  return ITEM_SET( &m_currentTrace );
1022 }
1023 
1024 
1026 {
1028 }
1029 
1030 
1031 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1032 {
1033  if( aLoopsRemoved && m_lastNode )
1034  return m_lastNode;
1035 
1036  return m_currentNode;
1037 }
1038 
1039 
1040 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
1041 {
1042  if( !aSeg )
1043  return false;
1044 
1045  if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1046  return false;
1047 
1048  JOINT* jt = aNode->FindJoint( aP, aSeg );
1049 
1050  if( jt && jt->LinkCount() >= 1 )
1051  return false;
1052 
1053  SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1054 
1055  std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1056 
1057  s_new[0]->SetEnds( s_old->Seg().A, aP );
1058  s_new[1]->SetEnds( aP, s_old->Seg().B );
1059 
1060  aNode->Remove( s_old );
1061  aNode->Add( std::move( s_new[0] ), true );
1062  aNode->Add( std::move( s_new[1] ), true );
1063 
1064  return true;
1065 }
1066 
1067 
1068 bool LINE_PLACER::SetLayer( int aLayer )
1069 {
1070  if( m_idle )
1071  {
1072  m_currentLayer = aLayer;
1073  return true;
1074  }
1075  else if( m_chainedPlacement )
1076  {
1077  return false;
1078  }
1079  else if( !m_startItem
1080  || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1081  || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1082  {
1083  m_currentLayer = aLayer;
1084  m_head.Line().Clear();
1085  m_tail.Line().Clear();
1086  m_last_head.Line().Clear();
1087  m_head.RemoveVia();
1088  m_tail.RemoveVia();
1092  Move( m_currentEnd, nullptr );
1093  return true;
1094  }
1095 
1096  return false;
1097 }
1098 
1099 
1100 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1101 {
1102  m_placementCorrect = false;
1103  m_currentStart = VECTOR2I( aP );
1104  m_currentEnd = VECTOR2I( aP );
1105  m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
1106  m_startItem = aStartItem;
1107  m_placingVia = false;
1108  m_chainedPlacement = false;
1109  m_fixedTail.Clear();
1110 
1111  setInitialDirection( Settings().InitialDirection() );
1112 
1113  initPlacement();
1114 
1115  DIRECTION_45 initialDir = m_initial_direction;
1117 
1118  if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1119  {
1120  // If we land on a segment endpoint, assume the starting direction is continuing along
1121  // the same direction as the endpoint. If we started in the middle, don't set a
1122  // direction so that the posture solver is not biased.
1123  SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1124 
1125  if( aP == seg.A )
1126  lastSegDir = DIRECTION_45( seg.Reversed() );
1127  else if( aP == seg.B )
1128  lastSegDir = DIRECTION_45( seg );
1129  }
1130  else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1131  static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1132  {
1133  double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
1134  angle = ( angle + 22.5 ) / 45.0;
1135  initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1136  }
1137 
1138  wxLogTrace( "PNS", "Posture: init %s, last seg %s", initialDir.Format(), lastSegDir.Format() );
1139 
1144  m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1145 
1146  NODE *n;
1147 
1148  if ( m_shove )
1149  n = m_shove->CurrentNode();
1150  else
1151  n = m_currentNode;
1152 
1154 
1155  return true;
1156 }
1157 
1158 
1160 {
1161  m_idle = false;
1162 
1163  m_head.Line().Clear();
1164  m_tail.Line().Clear();
1171  m_head.RemoveVia();
1172  m_tail.RemoveVia();
1173 
1176 
1177  NODE* world = Router()->GetWorld();
1178 
1179  world->KillChildren();
1180  NODE* rootNode = world->Branch();
1181 
1183 
1184  setWorld( rootNode );
1185 
1186  wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1187  m_world,
1188  m_direction.Format().c_str(),
1189  m_currentLayer );
1190 
1191  m_lastNode = nullptr;
1193  m_currentMode = Settings().Mode();
1194 
1195  m_shove.reset();
1196 
1198  m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1199 }
1200 
1201 
1202 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1203 {
1204  LINE current;
1205  VECTOR2I p = aP;
1206  int eiDepth = -1;
1207 
1208  if( aEndItem && aEndItem->Owner() )
1209  eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1210 
1211  if( m_lastNode )
1212  {
1213  delete m_lastNode;
1214  m_lastNode = nullptr;
1215  }
1216 
1217  bool reachesEnd = route( p );
1218 
1219  current = Trace();
1220 
1221  if( !current.PointCount() )
1223  else
1224  m_currentEnd = current.CLine().CPoint( -1 );
1225 
1226  NODE* latestNode = m_currentNode;
1227  m_lastNode = latestNode->Branch();
1228 
1229  if( reachesEnd
1230  && eiDepth >= 0
1231  && aEndItem && latestNode->Depth() > eiDepth
1232  && current.SegmentCount() )
1233  {
1234  SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1235 
1236  if( Settings().RemoveLoops() )
1237  removeLoops( m_lastNode, current );
1238  }
1239 
1242  return true;
1243 }
1244 
1245 
1246 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1247 {
1248  bool fixAll = Settings().GetFixAllSegments();
1249  bool realEnd = false;
1250 
1251  LINE pl = Trace();
1252 
1254  {
1255  // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1256  // user has more responsibility and authority.
1257 
1258  if( aEndItem )
1259  {
1260  // The user has indicated a connection should be made. If either the trace or
1261  // endItem is net-less, then allow the connection by adopting the net of the other.
1262  if( m_currentNet <= 0 )
1263  {
1264  m_currentNet = aEndItem->Net();
1265  pl.SetNet( m_currentNet );
1266  }
1267  else if (aEndItem->Net() <= 0 )
1268  {
1269  aEndItem->SetNet( m_currentNet );
1270  }
1271  }
1272 
1273  // Collisions still prevent fixing unless "Allow DRC violations" is checked
1274  if( !Settings().AllowDRCViolations() && m_world->CheckColliding( &pl ) )
1275  return false;
1276  }
1277 
1278  const SHAPE_LINE_CHAIN& l = pl.CLine();
1279 
1280  if( !l.SegmentCount() )
1281  {
1282  if( m_lastNode )
1283  {
1284  // Do a final optimization to the stored state
1285  NODE::ITEM_VECTOR removed, added;
1286  m_lastNode->GetUpdatedItems( removed, added );
1287 
1288  if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1289  simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1290  }
1291 
1292  // Nothing to commit if we have an empty line
1293  if( !pl.EndsWithVia() )
1294  return false;
1295 
1298  if( m_lastNode )
1299  m_lastNode->Add( Clone( pl.Via() ) );
1300 
1301  m_currentNode = nullptr;
1302 
1303  m_idle = true;
1304  m_placementCorrect = true;
1305  return true;
1306  }
1307 
1308  VECTOR2I p_pre_last = l.CPoint( -1 );
1309  const VECTOR2I p_last = l.CPoint( -1 );
1310 
1311  if( l.PointCount() > 2 )
1312  p_pre_last = l.CPoint( -2 );
1313 
1314  if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1315  realEnd = true;
1316 
1317  if( aForceFinish )
1318  realEnd = true;
1319 
1320  // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1321  // so if we are, act as though we are in fix-all mode.
1322  if( !fixAll && l.ArcCount() )
1323  fixAll = true;
1324 
1325  // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1326  SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1327  DIRECTION_45 d_last( lastDirSeg );
1328 
1329  int lastV;
1330 
1331  if( realEnd || m_placingVia || fixAll )
1332  lastV = l.SegmentCount();
1333  else
1334  lastV = std::max( 1, l.SegmentCount() - 1 );
1335 
1336  ARC arc;
1337  SEGMENT seg;
1338  LINKED_ITEM* lastItem = nullptr;
1339  int lastArc = -1;
1340 
1341  for( int i = 0; i < lastV; i++ )
1342  {
1343  ssize_t arcIndex = l.ArcIndex( i );
1344 
1345  if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && l.CShapes()[lastV] == -1 ) )
1346  {
1347  seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1348  seg.SetWidth( pl.Width() );
1349  seg.SetLayer( m_currentLayer );
1350 
1351  std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1352  lastItem = sp.get();
1353 
1354  if( !m_lastNode->Add( std::move( sp ) ) )
1355  lastItem = nullptr;
1356  }
1357  else
1358  {
1359  if( arcIndex == lastArc )
1360  continue;
1361 
1362  arc = ARC( l.Arc( arcIndex ), m_currentNet );
1363  arc.SetWidth( pl.Width() );
1364  arc.SetLayer( m_currentLayer );
1365 
1366  std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1367  lastItem = ap.get();
1368 
1369  m_lastNode->Add( std::move( ap ) );
1370  lastArc = arcIndex;
1371  }
1372  }
1373 
1374  if( pl.EndsWithVia() )
1375  m_lastNode->Add( Clone( pl.Via() ) );
1376 
1377  if( realEnd && lastItem )
1378  simplifyNewLine( m_lastNode, lastItem );
1379 
1380  if( !realEnd )
1381  {
1382  setInitialDirection( d_last );
1383  m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1384 
1386 
1387  m_startItem = nullptr;
1388  m_placingVia = false;
1390 
1393 
1394  m_head.Line().Clear();
1395  m_tail.Line().Clear();
1396  m_head.RemoveVia();
1397  m_tail.RemoveVia();
1400 
1401  if( m_shove )
1402  m_shove->AddLockedSpringbackNode( m_currentNode );
1403 
1404  DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1405 
1410 
1411  m_placementCorrect = true;
1412  }
1413  else
1414  {
1415  m_placementCorrect = true;
1416  m_idle = true;
1417  }
1418 
1419  return realEnd;
1420 }
1421 
1422 
1424 {
1425  FIXED_TAIL::STAGE st;
1426 
1427  if ( !m_fixedTail.PopStage( st ) )
1428  return false;
1429 
1430  m_head.Line().Clear();
1431  m_tail.Line().Clear();
1432  m_startItem = nullptr;
1433  m_p_start = st.pts[0].p;
1434  m_direction = st.pts[0].direction;
1435  m_placingVia = st.pts[0].placingVias;
1436  m_currentNode = st.commit;
1437  m_currentLayer = st.pts[0].layer;
1440  m_head.RemoveVia();
1441  m_tail.RemoveVia();
1442 
1446 
1447  if( m_shove )
1448  {
1449  m_shove->RewindSpringbackTo( m_currentNode );
1450  m_shove->UnlockSpringbackNode( m_currentNode );
1451  m_currentNode = m_shove->CurrentNode();
1453  }
1454 
1456 
1457  return true;
1458 }
1459 
1460 
1462 {
1463  return m_placementCorrect || m_fixedTail.StageCount() > 1;
1464 }
1465 
1466 
1468 {
1469  if( m_lastNode )
1471 
1472  m_lastNode = nullptr;
1473  m_currentNode = nullptr;
1474  return true;
1475 }
1476 
1477 
1478 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1479 {
1480  if( !aLatest.SegmentCount() )
1481  return;
1482 
1483  if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1484  return;
1485 
1486  std::set<LINKED_ITEM *> toErase;
1487  aNode->Add( aLatest, true );
1488 
1489  for( int s = 0; s < aLatest.LinkCount(); s++ )
1490  {
1491  LINKED_ITEM* seg = aLatest.GetLink(s);
1492  LINE ourLine = aNode->AssembleLine( seg );
1493  JOINT a, b;
1494  std::vector<LINE> lines;
1495 
1496  aNode->FindLineEnds( ourLine, a, b );
1497 
1498  if( a == b )
1499  aNode->FindLineEnds( aLatest, a, b );
1500 
1501  aNode->FindLinesBetweenJoints( a, b, lines );
1502 
1503  int removedCount = 0;
1504  int total = 0;
1505 
1506  for( LINE& line : lines )
1507  {
1508  total++;
1509 
1510  if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1511  {
1512  for( LINKED_ITEM* ss : line.Links() )
1513  toErase.insert( ss );
1514 
1515  removedCount++;
1516  }
1517  }
1518 
1519  wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1520  }
1521 
1522  for( LINKED_ITEM* s : toErase )
1523  aNode->Remove( s );
1524 
1525  aNode->Remove( aLatest );
1526 }
1527 
1528 
1530 {
1531  wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1532 
1533  // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1534  // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1535  // of the line and won't get cleaned up by the optimizer.
1536  NODE::ITEM_VECTOR removed, added;
1537  aNode->GetUpdatedItems( removed, added );
1538 
1539  std::set<ITEM*> cleanup;
1540 
1541  auto processJoint =
1542  [&]( JOINT* aJoint, ITEM* aItem )
1543  {
1544  if( !aJoint || aJoint->IsLineCorner() )
1545  return;
1546 
1547  SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1548 
1549  NODE::ITEM_VECTOR toRemove;
1550 
1551  for( ITEM* neighbor : aJoint->Links() )
1552  {
1553  if( neighbor == aItem || !neighbor->LayersOverlap( aItem ) )
1554  continue;
1555 
1556  const SEG& testSeg = static_cast<SEGMENT*>( neighbor )->Seg();
1557 
1558  if( refSeg.Contains( testSeg ) )
1559  {
1560  JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1561  JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1562 
1563  if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1564  ( nB == aJoint && nA->LinkCount() == 1 ) )
1565  {
1566  cleanup.insert( neighbor );
1567  }
1568  }
1569  }
1570  };
1571 
1572  for( ITEM* item : added )
1573  {
1574  if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1575  continue;
1576 
1577  JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1578  JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1579 
1580  processJoint( jA, item );
1581  processJoint( jB, item );
1582  }
1583 
1584  for( ITEM* seg : cleanup )
1585  aNode->Remove( seg );
1586 
1587  // And now we can proceed with assembling the final line and optimizing it.
1588 
1589  LINE l = aNode->AssembleLine( aLatest );
1590 
1591  bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1592 
1593  SHAPE_LINE_CHAIN simplified( l.CLine() );
1594 
1595  simplified.Simplify();
1596 
1597  if( optimized || simplified.PointCount() != l.PointCount() )
1598  {
1599  aNode->Remove( l );
1600  l.SetShape( simplified );
1601  aNode->Add( l );
1602  }
1603 }
1604 
1605 
1607 {
1608  m_sizes = aSizes;
1609 
1610  if( !m_idle )
1611  {
1612  // If the track width was originally determined from the rules resolver ("use netclass
1613  // width") or continuing from an existing track, we don't want to change the width unless
1614  // the user is moving to an explicitly-specified value.
1615  // NOTE: This doesn't quite correctly handle the case of moving *from* an explicit value
1616  // *to* the "use netclass width" value, but that is more complicated to handle.
1618  {
1621  }
1622 
1623  if( m_head.EndsWithVia() )
1624  {
1627  }
1628  }
1629 }
1630 
1631 
1633 {
1634  LINE current = Trace();
1635  SHAPE_LINE_CHAIN ratLine;
1636  TOPOLOGY topo( m_lastNode );
1637 
1638  if( topo.LeadingRatLine( &current, ratLine ) )
1639  m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1640 }
1641 
1642 
1643 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1644 {
1645  m_orthoMode = aOrthoMode;
1646 }
1647 
1648 
1649 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia )
1650 {
1651  SHAPE_LINE_CHAIN l;
1652  DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1653 
1654  wxLogTrace( "PNS", "buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1655  m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1656 
1657  // Rounded corners don't make sense when routing orthogonally (single track at a time)
1658  bool fillet = !m_orthoMode && Settings().GetCornerMode() == CORNER_MODE::ROUNDED_45;
1659 
1660  if( m_p_start == aP )
1661  {
1662  l.Clear();
1663  }
1664  else
1665  {
1666  if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1667  {
1668  l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1669  }
1670  else
1671  {
1672  if( !m_tail.PointCount() )
1673  l = guessedDir.BuildInitialTrace( m_p_start, aP, false, fillet );
1674  else
1675  l = m_direction.BuildInitialTrace( m_p_start, aP, false, fillet );
1676  }
1677 
1678  if( l.SegmentCount() > 1 && m_orthoMode )
1679  {
1680  VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1681 
1682  l.Remove( -1, -1 );
1683  l.SetPoint( 1, newLast );
1684  }
1685  }
1686 
1687  aHead.SetLayer( m_currentLayer );
1688  aHead.SetShape( l );
1689 
1690  if( !m_placingVia || aForceNoVia )
1691  return true;
1692 
1693  VIA v( makeVia( aP ) );
1694  v.SetNet( aHead.Net() );
1695 
1697  {
1698  aHead.AppendVia( v );
1699  return true;
1700  }
1701 
1702  VECTOR2I force;
1703  VECTOR2I lead = aP - m_p_start;
1704 
1705  bool solidsOnly = ( m_currentMode != RM_Walkaround );
1706 
1707  if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1708  {
1709  SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false,
1710  fillet );
1711  aHead = LINE( aHead, line );
1712 
1713  v.SetPos( v.Pos() + force );
1714  return true;
1715  }
1716 
1717  return false; // via placement unsuccessful
1718 }
1719 
1720 
1721 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1722 {
1723  aNets.push_back( m_currentNet );
1724 }
1725 
1726 
1728 {
1729  m_world->KillChildren();
1730  return true;
1731 }
1732 
1733 
1734 FIXED_TAIL::FIXED_TAIL( int aLineCount )
1735 {
1736 
1737 }
1738 
1739 
1741 {
1742 
1743 }
1744 
1745 
1747 {
1748  m_stages.clear();
1749 }
1750 
1751 
1752 void FIXED_TAIL::AddStage( VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction,
1753  NODE *aNode )
1754 {
1755  STAGE st;
1756  FIX_POINT pt;
1757 
1758  pt.p = aStart;
1759  pt.layer = aLayer;
1760  pt.direction = direction;
1761  pt.placingVias = placingVias;
1762 
1763  st.pts.push_back(pt);
1764  st.commit = aNode;
1765 
1766  m_stages.push_back( st );
1767 }
1768 
1769 
1771 {
1772  if( !m_stages.size() )
1773  return false;
1774 
1775  aStage = m_stages.back();
1776 
1777  if( m_stages.size() > 1 )
1778  m_stages.pop_back();
1779 
1780  return true;
1781 }
1782 
1783 
1785 {
1786  return m_stages.size();
1787 }
1788 
1789 }
1790 
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int Length() const
Return the length (this).
Definition: seg.h:350
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
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:281
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
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:198
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
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)
Removes 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)
Function Simplify()
std::vector< STAGE > m_stages
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to 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:694
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
Function Slice()
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:1013
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:1020
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:1027
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
Function PointCount()
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:127
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
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:810
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.
const std::vector< ssize_t > & CShapes() const
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
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
Function Point()
void SetApproachCursor(bool aEnabled, const VECTOR2I &aPos)
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
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:1369
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:920
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:95
void initPlacement()
Initialize placement of a new line with given parameters.
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
#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
Returns 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)
Function Remove()
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
Function SegmentCount()
bool CommitPlacement() override
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead)
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:1104
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
void AddStage(VECTOR2I aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
const char * name
Definition: DXF_plotter.cpp:59
Reduce corner cost by merging obtuse segments.
const SEG CSegment(int aIndex) const
Function CSegment()
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
SHAPE_LINE_CHAIN.
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:433
WALKAROUND_STATUS statusCcw
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
bool HasLoops() const
Definition: pns_line.cpp:1136
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:1302
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()
Function Clear() Removes 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:1256
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)
Function Replace()
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:621
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
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
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