KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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-2024 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
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 <optional>
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"
35
36#include <wx/log.h>
37
38namespace 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 = nullptr;
54 m_startItem = nullptr;
55 m_endItem = nullptr;
56 m_chainedPlacement = false;
57 m_orthoMode = false;
58 m_placementCorrect = false;
59}
60
61
63{
64}
65
66
68{
69 m_world = aWorld;
70}
71
72
74{
75 const LAYER_RANGE layers( m_sizes.ViaType() == VIATYPE::THROUGH ? F_Cu : m_sizes.GetLayerTop(),
76 m_sizes.ViaType() == VIATYPE::THROUGH ? B_Cu : m_sizes.GetLayerBottom() );
77
78 return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), nullptr, m_sizes.ViaType() );
79}
80
81
82bool LINE_PLACER::ToggleVia( bool aEnabled )
83{
84 m_placingVia = aEnabled;
85
86 if( !aEnabled )
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 {
119 tail.Clear();
120 return true;
121 }
122
123 tail.Intersect( head, ips );
124
125 // no intesection points - nothing to reduce
126 if( ips.empty() )
127 return false;
128
129 int n = INT_MAX;
130 VECTOR2I ipoint;
131
132 // if there is more than one intersection, find the one that is
133 // closest to the beginning of the tail.
134 for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
135 {
136 if( i.index_our < n )
137 {
138 n = i.index_our;
139 ipoint = i.p;
140 }
141 }
142
143 // ignore the point where head and tail meet
144 if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
145 return false;
146
147 // Intersection point is on the first or the second segment: just start routing
148 // from the beginning
149 if( n < 2 )
150 {
152 tail.Clear();
153 head.Clear();
154
155 return true;
156 }
157 else
158 {
159 // Clip till the last tail segment before intersection.
160 // Set the direction to the one of this segment.
161 const SEG last = tail.CSegment( n - 1 );
162 m_direction = DIRECTION_45( last );
163 tail.Remove( n, -1 );
164 return true;
165 }
166
167 return false;
168}
169
170
172{
173 SHAPE_LINE_CHAIN& head = m_head.Line();
174 SHAPE_LINE_CHAIN& tail = m_tail.Line();
175
176 if( head.PointCount() < 2 )
177 return false;
178
179 int n = tail.PointCount();
180
181 if( n == 0 )
182 {
183 return false;
184 }
185 else if( n == 1 )
186 {
187 tail.Clear();
188 return true;
189 }
190
191 DIRECTION_45 first_head, last_tail;
192
193 wxASSERT( tail.PointCount() >= 2 );
194
195 if( !head.IsPtOnArc( 0 ) )
196 first_head = DIRECTION_45( head.CSegment( 0 ) );
197 else
198 first_head = DIRECTION_45( head.CArcs()[head.ArcIndex(0)] );
199
200 int lastSegIdx = tail.PointCount() - 2;
201
202 if( !tail.IsPtOnArc( lastSegIdx ) )
203 last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
204 else
205 last_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex(lastSegIdx)] );
206
207 DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
208
209 // case 1: we have a defined routing direction, and the currently computed
210 // head goes in different one.
211 bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
212
213 // case 2: regardless of the current routing direction, if the tail/head
214 // extremities form an acute or right angle, reduce the tail by one segment
215 // (and hope that further iterations) will result with a cleaner trace
216 bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
217
218 if( pullback_1 || pullback_2 )
219 {
220 if( !tail.IsArcSegment( lastSegIdx ) )
221 {
222 const SEG& seg = tail.CSegment( lastSegIdx );
223 m_direction = DIRECTION_45( seg );
224 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [pullback3]" ) );
225
226 }
227 else
228 {
229 const SHAPE_ARC& arc = tail.CArcs()[tail.ArcIndex( lastSegIdx )];
230 m_direction = DIRECTION_45( arc );
231 }
232
233 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: pullback triggered [%d] [%s %s]",
234 n, last_tail.Format(), first_head.Format() ) );
235
236 // erase the last point in the tail, hoping that the next iteration will
237 // result with a head trace that starts with a segment following our
238 // current direction.
239 if( n < 2 )
240 tail.Clear(); // don't leave a single-point tail
241 else
242 tail.RemoveShape( -1 );
243
244 if( !tail.SegmentCount() )
246
247 return true;
248 }
249
250 return false;
251}
252
253
255{
256 SHAPE_LINE_CHAIN& head = m_head.Line();
257 SHAPE_LINE_CHAIN& tail = m_tail.Line();
258
259 int n = tail.SegmentCount();
260
261 if( head.SegmentCount() < 1 )
262 return false;
263
264 // Don't attempt this for too short tails
265 if( n < 2 )
266 return false;
267
268 // Start from the segment farthest from the end of the tail
269 // int start_index = std::max(n - 1 - ReductionDepth, 0);
270
271 DIRECTION_45 new_direction;
272 VECTOR2I new_start;
273 int reduce_index = -1;
274
275 for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
276 {
277 const SEG s = tail.CSegment( i );
278 DIRECTION_45 dir( s );
279
280 // calculate a replacement route and check if it matches
281 // the direction of the segment to be replaced
282 SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
283
284 if( replacement.SegmentCount() < 1 )
285 continue;
286
287 LINE tmp( m_tail, replacement );
288
290 break;
291
292 if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
293 {
294 new_start = s.A;
295 new_direction = dir;
296 reduce_index = i;
297 }
298 }
299
300 if( reduce_index >= 0 )
301 {
302 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: reducing tail: %d" , reduce_index ) );
303 SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
304
305 m_direction = new_direction;
306 tail.Remove( reduce_index + 1, -1 );
307 head.Clear();
308 return true;
309 }
310
311 if( !tail.SegmentCount() )
313
314 return false;
315}
316
317
319{
320 SHAPE_LINE_CHAIN& head = m_head.Line();
321 SHAPE_LINE_CHAIN& tail = m_tail.Line();
322
323 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
326
327 head.Simplify();
328 tail.Simplify();
329
330 int n_head = head.ShapeCount();
331 int n_tail = tail.ShapeCount();
332
333 if( n_head < 3 )
334 {
335 PNS_DBG( Dbg(), Message, wxT( "Merge failed: not enough head segs." ) );
336 return false;
337 }
338
339 if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
340 {
341 PNS_DBG( Dbg(), Message, wxT( "Merge failed: head and tail discontinuous." ) );
342 return false;
343 }
344
345 if( m_head.CountCorners( ForbiddenAngles ) != 0 )
346 return false;
347
348 DIRECTION_45 dir_tail, dir_head;
349
350 if( !head.IsPtOnArc( 0 ) )
351 dir_head = DIRECTION_45( head.CSegment( 0 ) );
352 else
353 dir_head = DIRECTION_45( head.CArcs()[head.ArcIndex( 0 )] );
354
355 if( n_tail )
356 {
357 wxASSERT( tail.PointCount() >= 2 );
358 int lastSegIdx = tail.PointCount() - 2;
359
360 if( !tail.IsPtOnArc( lastSegIdx ) )
361 dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
362 else
363 dir_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
364
365 if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
366 return false;
367 }
368
369 tail.Append( head );
370
371 tail.Simplify();
372
373 int lastSegIdx = tail.PointCount() - 2;
374
375 if( !tail.IsArcSegment( lastSegIdx ) )
376 m_direction = DIRECTION_45( tail.CSegment( -1 ) );
377 else
378 m_direction = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
379
380 head.Remove( 0, -1 );
381
382 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: merge %d, new direction: %s" , n_head,
383 m_direction.Format() ) );
384
385 head.Simplify();
386 tail.Simplify();
387
388 return true;
389}
390
391
393 SHAPE_LINE_CHAIN& aOut, int &thresholdDist )
394{
395 SHAPE_LINE_CHAIN l( aL );
396 int idx = l.Split( aP );
397
398 if( idx < 0)
399 return false;
400
401 bool rv = true;
402
403 SHAPE_LINE_CHAIN l2 = l.Slice( 0, idx );
404 int dist = l2.Length();
405
406 PNS_DBG( Dbg(), AddPoint, aP, BLUE, 500000, wxString::Format( "hug-target-check-%d", idx ) );
407 PNS_DBG( Dbg(), AddShape, &l2, BLUE, 500000, wxT( "hug-target-line" ) );
408
409 if( dist < thresholdDist )
410 rv = false;
411
412 LINE ctest( m_head, l2 );
413
414 if( m_currentNode->CheckColliding( &ctest ).has_value() )
415 rv = false;
416
417 if( rv )
418 {
419 aOut = l2;
420 thresholdDist = dist;
421 }
422
423 return rv;
424}
425
426
428 double lengthThreshold, SHAPE_LINE_CHAIN &aOut )
429{
430 std::vector<int> dists;
431 std::vector<VECTOR2I> pts;
432
433 if( aL.PointCount() == 0 )
434 return false;
435
436 VECTOR2I lastP = aL.CPoint(-1);
437 int accumulatedDist = 0;
438
439 dists.reserve( 2 * aL.PointCount() );
440
441 for( int i = 0; i < aL.SegmentCount(); i++ )
442 {
443 const SEG& s = aL.CSegment( i );
444
445 dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
446 pts.push_back( s.A );
447 auto pn = s.NearestPoint( aCursor );
448
449 if( pn != s.A && pn != s.B )
450 {
451 dists.push_back( ( pn - aCursor ).EuclideanNorm() );
452 pts.push_back( pn );
453 }
454
455 accumulatedDist += s.Length();
456
457 if ( accumulatedDist > lengthThreshold )
458 {
459 lastP = s.B;
460 break;
461 }
462 }
463
464 dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
465 pts.push_back( lastP );
466
467 int minDistLoc = std::numeric_limits<int>::max();
468 int minPLoc = -1;
469 int minDistGlob = std::numeric_limits<int>::max();
470 int minPGlob = -1;
471
472 for( int i = 0; i < dists.size(); i++ )
473 {
474 int d = dists[i];
475
476 if( d < minDistGlob )
477 {
478 minDistGlob = d;
479 minPGlob = i;
480 }
481 }
482
483 if( dists.size() >= 3 )
484 {
485 for( int i = 0; i < dists.size() - 3; i++ )
486 {
487 if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
488 {
489 int d = dists[i + 1];
490 if( d < minDistLoc )
491 {
492 minDistLoc = d;
493 minPLoc = i + 1;
494 }
495 }
496 }
497
498 if( dists.back() < minDistLoc && minPLoc >= 0 )
499 {
500 minDistLoc = dists.back();
501 minPLoc = dists.size() - 1;
502 }
503 }
504 else
505 {
506 // Too few points: just use the global
507 minDistLoc = minDistGlob;
508 minPLoc = minPGlob;
509 }
510
511// fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
512// in the code, enabling the global one by default
513 minPLoc = -1;
514 int preferred;
515
516 if( minPLoc < 0 )
517 {
518 preferred = minPGlob;
519 }
520 else
521 {
522 preferred = minPLoc;
523 }
524
525 int thresholdDist = 0;
526
527 if( clipAndCheckCollisions( pts[preferred], aL, aOut, thresholdDist ) )
528 return true;
529
530 thresholdDist = 0;
531
532 SHAPE_LINE_CHAIN l( aL ), prefL;
533 int minDist = std::numeric_limits<int>::max();
534
535 bool ok = false;
536
537 for( int i = 0; i < pts.size() ; i++)
538 {
539 //PNS_DBG( Dbg(), AddPoint, pts[i], BLUE, 500000, wxT( "hug-target-fallback" ) );
540
541 ok |= clipAndCheckCollisions( pts[i], aL, aOut, thresholdDist );
542 }
543
544 return ok;
545}
546
547
548bool LINE_PLACER::rhWalkBase( const VECTOR2I& aP, LINE& aWalkLine, int aCollisionMask,
549 bool& aViaOk )
550{
551 LINE walkFull( m_head );
552 LINE l1( m_head );
553
554 PNS_DBG( Dbg(), AddItem, &m_tail, GREEN, 100000, wxT( "walk-base-old-tail" ) );
555 PNS_DBG( Dbg(), AddItem, &m_head, BLUE, 100000, wxT( "walk-base-old-head" ) );
556
557 VECTOR2I walkP = aP;
558
559 WALKAROUND walkaround( m_currentNode, Router() );
560
561 walkaround.SetSolidsOnly( false );
562 walkaround.SetDebugDecorator( Dbg() );
563 walkaround.SetLogger( Logger() );
564 walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
565 walkaround.SetItemMask( aCollisionMask );
566
567 int round = 0;
568
569 do
570 {
571 l1.Clear();
572
573 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "walk-round-%d", round ), 0 );
574 round++;
575
576 aViaOk = buildInitialLine( walkP, l1, round == 0 );
577 PNS_DBG( Dbg(), AddItem, &l1, BLUE, 20000, wxT( "walk-base-l1" ) );
578
579 if( l1.EndsWithVia() )
580 PNS_DBG( Dbg(), AddPoint, l1.Via().Pos(), BLUE, 100000, wxT( "walk-base-l1-via" ) );
581
582 LINE initTrack( m_tail );
583 initTrack.Line().Append( l1.CLine() );
584 initTrack.Line().Simplify();
585
586
587 double initialLength = initTrack.CLine().Length();
588 double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
589 double hugThresholdLengthComplete =
590 2.0 * initialLength * Settings().WalkaroundHugLengthThreshold();
591
592 WALKAROUND::RESULT wr = walkaround.Route( initTrack );
593 std::optional<LINE> bestLine;
594
595 OPTIMIZER optimizer( m_currentNode );
596
598 optimizer.SetCollisionMask( aCollisionMask );
599
600 int len_cw = wr.statusCw != WALKAROUND::STUCK ? wr.lineCw.CLine().Length()
601 : std::numeric_limits<int>::max();
602 int len_ccw = wr.statusCcw != WALKAROUND::STUCK ? wr.lineCcw.CLine().Length()
603 : std::numeric_limits<int>::max();
604
605 if( wr.statusCw == WALKAROUND::DONE )
606 {
607 PNS_DBG( Dbg(), AddItem, &wr.lineCw, BLUE, 20000, wxT( "wf-result-cw-preopt" ) );
608 LINE tmpHead, tmpTail;
609
610 if( splitHeadTail( wr.lineCw, m_tail, tmpHead, tmpTail ) )
611 {
612 optimizer.Optimize( &tmpHead );
613 wr.lineCw.SetShape( tmpTail.CLine () );
614 wr.lineCw.Line().Append( tmpHead.CLine( ) );
615 }
616
617 PNS_DBG( Dbg(), AddItem, &wr.lineCw, RED, 20000, wxT( "wf-result-cw-postopt" ) );
618 len_cw = wr.lineCw.CLine().Length();
619 bestLine = wr.lineCw;
620 }
621
622 if( wr.statusCcw == WALKAROUND::DONE )
623 {
624 PNS_DBG( Dbg(), AddItem, &wr.lineCcw, BLUE, 20000, wxT( "wf-result-ccw-preopt" ) );
625
626 LINE tmpHead, tmpTail;
627
628 if( splitHeadTail( wr.lineCw, m_tail, tmpHead, tmpTail ) )
629 {
630 optimizer.Optimize( &tmpHead );
631 wr.lineCw.SetShape( tmpTail.CLine () );
632 wr.lineCw.Line().Append( tmpHead.CLine( ) );
633 }
634
635 PNS_DBG( Dbg(), AddItem, &wr.lineCcw, RED, 20000, wxT( "wf-result-ccw-postopt" ) );
636 len_ccw = wr.lineCcw.CLine().Length();
637
638 if( len_ccw < len_cw )
639 bestLine = wr.lineCcw;
640 }
641
642 int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
643
644 if( bestLength < hugThresholdLengthComplete && bestLine.has_value() )
645 {
646 walkFull.SetShape( bestLine->CLine() );
647 walkP = walkFull.CLine().CPoint(-1);
648 PNS_DBGN( Dbg(), EndGroup );
649 continue;
650 }
651
652 bool validCw = false;
653 bool validCcw = false;
654 int distCcw = std::numeric_limits<int>::max();
655 int distCw = std::numeric_limits<int>::max();
656
657 SHAPE_LINE_CHAIN l_cw, l_ccw;
658
659 if( wr.statusCw != WALKAROUND::STUCK )
660 {
661 validCw = cursorDistMinimum( wr.lineCw.CLine(), aP, hugThresholdLength, l_cw );
662
663 if( validCw )
664 distCw = ( aP - l_cw.CPoint( -1 ) ).EuclideanNorm();
665
666 PNS_DBG( Dbg(), AddShape, &l_cw, MAGENTA, 200000, wxString::Format( "wh-result-cw %s",
667 validCw ? "non-colliding"
668 : "colliding" ) );
669 }
670
671 if( wr.statusCcw != WALKAROUND::STUCK )
672 {
673 validCcw = cursorDistMinimum( wr.lineCcw.CLine(), aP, hugThresholdLength, l_ccw );
674
675 if( validCcw )
676 distCcw = ( aP - l_ccw.CPoint( -1 ) ).EuclideanNorm();
677
678 PNS_DBG( Dbg(), AddShape, &l_ccw, MAGENTA, 200000, wxString::Format( "wh-result-ccw %s",
679 validCcw ? "non-colliding"
680 : "colliding" ) );
681 }
682
683
684 if( distCw < distCcw && validCw )
685 {
686 walkFull.SetShape( l_cw );
687 walkP = l_cw.CPoint(-1);
688 }
689 else if( validCcw )
690 {
691 walkFull.SetShape( l_ccw );
692 walkP = l_ccw.CPoint(-1);
693 }
694 else
695 {
696 PNS_DBGN( Dbg(), EndGroup );
697 return false;
698 }
699
700 PNS_DBGN( Dbg(), EndGroup );
701 } while( round < 2 && m_placingVia );
702
703
704 if( l1.EndsWithVia() )
705 {
706 VIA v ( l1.Via() );
707 v.SetPos( walkFull.CPoint( -1 ) );
708 walkFull.AppendVia( v );
709 }
710
711 PNS_DBG( Dbg(), AddItem, &walkFull, GREEN, 200000, wxT( "walk-full" ) );
712
713 if( walkFull.EndsWithVia() )
714 {
715 PNS_DBG( Dbg(), AddPoint, walkFull.Via().Pos(), GREEN, 200000,
716 wxString::Format( "walk-via ok %d", aViaOk ? 1 : 0 ) );
717 }
718
719 aWalkLine = walkFull;
720
721 return !walkFull.EndsWithVia() || aViaOk;
722}
723
724
725bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
726{
727 LINE walkFull;
728
729 int effort = 0;
730 bool viaOk = false;
731
732 if( ! rhWalkBase( aP, walkFull, ITEM::ANY_T, viaOk ) )
733 return false;
734
735 switch( Settings().OptimizerEffort() )
736 {
737 case OE_LOW:
738 effort = 0;
739 break;
740
741 case OE_MEDIUM:
742 case OE_FULL:
744 break;
745 }
746
748
749 // Smart Pads is incompatible with 90-degree mode for now
750 if( Settings().SmartPads()
751 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
753 {
754 effort |= OPTIMIZER::SMART_PADS;
755 }
756
757 if( m_currentNode->CheckColliding( &walkFull ) )
758 {
759 PNS_DBG( Dbg(), AddItem, &walkFull, GREEN, 100000, wxString::Format( "collision check fail" ) );
760 return false;
761 }
762
763 // OK, this deserves a bit of explanation. We used to calculate the walk path for the head only,
764 // but then the clearance epsilon was added, with the intent of improving collision resolution robustness
765 // (now a hull or a walk/shove line cannot collide with the 'owner' of the hull under any circumstances).
766 // This, however, introduced a subtle bug. For a row/column/any other 'regular' arrangement
767 // of overlapping hulls (think of pads of a SOP/SOIC chip or a regular via grid), walking around may
768 // produce a new 'head' that is not considered colliding (due to the clearance epsilon), but with
769 // its start point inside one of the subsequent hulls to process.
770 // We can't have head[0] inside any hull for the algorithm to work - therefore, we now consider the entire
771 // 'tail+head' trace when walking around and in case of success, reconstruct the
772 // 'head' and 'tail' by splitting the walk line at a point that is as close as possible to the original
773 // head[0], but not inside any obstacle hull.
774 //
775 // EXECUTIVE SUMMARY: asinine heuristic to make the router get stuck much less often.
776
777 if( ! splitHeadTail( walkFull, m_tail, aNewHead, aNewTail ) )
778 return false;
779
780 if( m_placingVia && viaOk )
781 {
782 PNS_DBG( Dbg(), AddPoint, aNewHead.CPoint(-1), RED, 1000000, wxString::Format( "VIA" ) );
783
784 aNewHead.AppendVia( makeVia( aNewHead.CPoint( -1 ) ) );
785 }
786
787 OPTIMIZER::Optimize( &aNewHead, effort, m_currentNode );
788
789 PNS_DBG( Dbg(), AddItem, &aNewHead, GREEN, 100000, wxString::Format( "walk-new-head" ) );
790 PNS_DBG( Dbg(), AddItem, &aNewTail, BLUE, 100000, wxT( "walk-new-tail" ) );
791
792 return true;
793}
794
795
796bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
797{
799 m_head.SetBlockingObstacle( nullptr );
800
801 auto obs = m_currentNode->NearestObstacle( &m_head );
802
803 // If the head is in colliding state, snap to the hull of the first obstacle.
804 // This way, one can route tracks as tightly as possible without enabling
805 // the shove/walk mode that certain users find too intrusive.
806 if( obs )
807 {
808 int clearance = m_currentNode->GetClearance( obs->m_item, &m_head, false );
809 SHAPE_LINE_CHAIN hull = obs->m_item->Hull( clearance, m_head.Width() );
810 VECTOR2I nearest;
811
813
814 if( cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90 )
815 nearest = hull.BBox().ClosestPointTo( aP );
816 else
817 nearest = hull.NearestPoint( aP );
818
819 if( ( nearest - aP ).EuclideanNorm() < m_head.Width() / 2 )
820 buildInitialLine( nearest, m_head );
821 }
822
823 // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
824 // but we don't have one right now and there isn't a lot of demand for one. If we do end up
825 // doing that, put it in a new routing mode as "highlight collisions" mode should not have
826 // collision handling other than highlighting.
827#if 0
828 if( !Settings().AllowDRCViolations() )
829 {
831
832 if( obs && obs->m_distFirst != INT_MAX )
833 {
834 buildInitialLine( obs->m_ipFirst, m_head );
835 m_head.SetBlockingObstacle( obs->m_item );
836 }
837 }
838#endif
839
840 aNewHead = m_head;
841 aNewTail = m_tail;
842
843 return true;
844}
845
846
847bool LINE_PLACER::splitHeadTail( const LINE& aNewLine, const LINE& aOldTail, LINE& aNewHead,
848 LINE& aNewTail )
849{
850 LINE newTail( aOldTail );
851 LINE newHead( aOldTail );
852 LINE l2( aNewLine );
853
854 newTail.RemoveVia();
855 newHead.Clear();
856
857 int i;
858 bool found = false;
859 int n = l2.PointCount();
860
861 if( n > 1 && aOldTail.PointCount() > 1 )
862 {
863 if( l2.CLine().PointOnEdge( aOldTail.CPoint( -1 ) ) )
864 {
865 l2.Line().Split( aOldTail.CPoint( -1 ) );
866 }
867
868 for( i = 0; i < aOldTail.PointCount(); i++ )
869 {
870 if( l2.CLine().Find( aOldTail.CPoint( i ) ) < 0 )
871 {
872 found = true;
873 break;
874 }
875 }
876
877 if( !found )
878 i--;
879
880 // If the old tail doesn't have any points of the new line, we can't split it.
881 if( i >= l2.PointCount() )
882 i = l2.PointCount() - 1;
883
884 newHead.Clear();
885
886 if( i == 0 )
887 newTail.Clear();
888 else
889 newTail.SetShape( l2.CLine().Slice( 0, i ) );
890
891 newHead.SetShape( l2.CLine().Slice( i, -1 ) );
892 }
893 else
894 {
895 newTail.Clear();
896 newHead = l2;
897 }
898
899 PNS_DBG( Dbg(), AddItem, &newHead, BLUE, 500000, wxT( "head-post-split" ) );
900
901 aNewHead = newHead;
902 aNewTail = newTail;
903
904 return true;
905}
906
907
908bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
909{
910 LINE walkSolids;
911
912 bool viaOk = false;
913
914 if( ! rhWalkBase( aP, walkSolids, ITEM::SOLID_T, viaOk ) )
915 return false;
916
917 m_currentNode = m_shove->CurrentNode();
918
919 m_shove->SetLogger( Logger() );
920 m_shove->SetDebugDecorator( Dbg() );
921
922 if( m_endItem )
923 {
924 // Make sure the springback algorithm won't erase the NODE that owns m_endItem.
925 m_shove->SetSpringbackDoNotTouchNode( static_cast<const NODE*>( m_endItem->Owner() ) );
926 }
927
928 LINE newHead( walkSolids );
929
930 if( walkSolids.EndsWithVia() )
931 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), RED, 1000000, wxString::Format( "SVIA [%d]", viaOk?1:0 ) );
932
933 if( m_placingVia && viaOk )
934 {
935 newHead.AppendVia( makeVia( newHead.CPoint( -1 ) ) );
936 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-new-via" );
937
938 }
939
940 SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( newHead );
941
942 m_currentNode = m_shove->CurrentNode();
943
944 int effort = 0;
945
946 switch( Settings().OptimizerEffort() )
947 {
948 case OE_LOW:
949 effort = 0;
950 break;
951
952 case OE_MEDIUM:
953 case OE_FULL:
955 break;
956 }
957
959
960 // Smart Pads is incompatible with 90-degree mode for now
961 if( Settings().SmartPads()
962 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
964 {
965 effort |= OPTIMIZER::SMART_PADS;
966 }
967
968 if( status == SHOVE::SH_OK || status == SHOVE::SH_HEAD_MODIFIED )
969 {
970 if( status == SHOVE::SH_HEAD_MODIFIED )
971 newHead = m_shove->NewHead();
972
973 OPTIMIZER optimizer( m_currentNode );
974
975 if( newHead.EndsWithVia() )
976 {
977 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-via-preopt" );
978 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-via-postopt" );
979 }
980
981 if( ! splitHeadTail( newHead, m_tail, aNewHead, aNewTail ) )
982 return false;
983
984 if( newHead.EndsWithVia() )
985 aNewHead.AppendVia( newHead.Via() );
986
987 optimizer.SetEffortLevel( effort );
988 optimizer.SetCollisionMask( ITEM::ANY_T );
989 optimizer.Optimize( &aNewHead );
990
991 return true;
992 }
993 else
994 {
995 return rhWalkOnly( aP, aNewHead, aNewTail );
996 }
997
998 return false;
999}
1000
1001
1002bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
1003{
1004 switch( Settings().Mode() )
1005 {
1006 case RM_MarkObstacles:
1007 return rhMarkObstacles( aP, aNewHead, aNewTail );
1008 case RM_Walkaround:
1009 return rhWalkOnly( aP, aNewHead, aNewTail );
1010 case RM_Shove:
1011 return rhShoveOnly( aP, aNewHead, aNewTail );
1012 default:
1013 break;
1014 }
1015
1016 return false;
1017}
1018
1019
1021{
1022 LINE linetmp = Trace();
1023
1024 PNS_DBG( Dbg(), Message, "optimize HT" );
1025
1026 // NOTE: FANOUT_CLEANUP can override posture setting at the moment
1029 {
1030 if( linetmp.SegmentCount() < 1 )
1031 return false;
1032
1033 m_head = linetmp;
1034 m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
1035 m_tail.Line().Clear();
1036
1037 return true;
1038 }
1039
1040 SHAPE_LINE_CHAIN& head = m_head.Line();
1041 SHAPE_LINE_CHAIN& tail = m_tail.Line();
1042
1043 int tailLookbackSegments = 3;
1044
1045 //if(m_currentMode() == RM_Walkaround)
1046 // tailLookbackSegments = 10000;
1047
1048 int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
1049
1050 if( tail.ShapeCount() < 3 )
1051 return false;
1052
1053 // assemble TailLookbackSegments tail segments with the current head
1054 SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
1055
1056 int end = std::min(2, head.PointCount() - 1 );
1057
1058 opt_line.Append( head.Slice( 0, end ) );
1059
1060 LINE new_head( m_tail, opt_line );
1061
1062 // and see if it could be made simpler by merging obtuse/collnear segments.
1063 // If so, replace the (threshold) last tail points and the head with
1064 // the optimized line
1065
1066 PNS_DBG( Dbg(), AddItem, &new_head, LIGHTCYAN, 10000, wxT( "ht-newline" ) );
1067
1069 {
1070 LINE tmp( m_tail, opt_line );
1071
1072 head.Clear();
1073 tail.Replace( -threshold, -1, new_head.CLine() );
1074 tail.Simplify();
1075
1076 m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
1077
1078 return true;
1079 }
1080
1081 return false;
1082}
1083
1085{
1086 if( tail.CLine().PointCount() )
1087 m_p_start = tail.CLine().CPoint(-1);
1088 else
1090}
1091
1093{
1094 bool fail = false;
1095 bool go_back = false;
1096
1097 int i, n_iter = 1;
1098
1099
1100 PNS_DBG( Dbg(), Message, wxString::Format( "routeStep: direction: %s head: %d, tail: %d shapes" ,
1103 m_tail.ShapeCount() ) );
1104
1105 PNS_DBG( Dbg(), BeginGroup, wxT( "route-step" ), 0 );
1106
1107 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-init" ) );
1108 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-init" ) );
1109
1110 for( i = 0; i < n_iter; i++ )
1111 {
1112 LINE prevTail( m_tail );
1113 LINE prevHead( m_head );
1114 LINE newHead, newTail;
1115
1116 if( !go_back && Settings().FollowMouse() )
1117 reduceTail( aP );
1118
1119 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-reduce" ) );
1120 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-reduce" ) );
1121
1122 go_back = false;
1123
1125
1126 if( !routeHead( aP, newHead, newTail ) )
1127 {
1128 m_tail = prevTail;
1129 m_head = prevHead;
1130
1131 // If we fail to walk out of the initial point (no tail), instead of returning an empty
1132 // line, return a zero-length line so that the user gets some feedback that routing is
1133 // happening. This will get pruned later.
1134 if( m_tail.PointCount() == 0 )
1135 {
1137 m_tail.Line().Append( m_p_start, true );
1138 }
1139
1140 fail = true;
1141 }
1142
1144
1145 PNS_DBG( Dbg(), AddItem, &newHead, LIGHTGREEN, 100000, wxString::Format( "new_head [fail: %d]", fail?1:0 ) );
1146
1147 if( fail )
1148 break;
1149
1150 PNS_DBG( Dbg(), Message, wxString::Format( "N VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1151
1152 m_head = newHead;
1153 m_tail = newTail;
1154
1156 {
1157 n_iter++;
1158 go_back = true;
1159 }
1160
1161 PNS_DBG( Dbg(), Message, wxString::Format( "SI VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1162
1163 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-si" ) );
1164 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-si" ) );
1165
1166 if( !go_back && handlePullback() )
1167 {
1168 n_iter++;
1169 m_head.Clear();
1170 go_back = true;
1171 }
1172
1173 PNS_DBG( Dbg(), Message, wxString::Format( "PB VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1174
1175 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-after-pb" ) );
1176 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-after-pb" ) );
1177 }
1178
1179
1180 if( !fail && Settings().FollowMouse() )
1181 {
1182 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-pre-merge" ) );
1183 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-pre-merge" ) );
1184
1186 {
1187 PNS_DBG( Dbg(), Message, wxString::Format( "PreM VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1188
1189 mergeHead();
1190
1191 PNS_DBG( Dbg(), Message, wxString::Format( "PostM VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1192 }
1193
1194 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-post-merge" ) );
1195 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-post-merge" ) );
1196 }
1197
1198 m_last_p_end = aP;
1199
1200 PNS_DBGN( Dbg(), EndGroup );
1201}
1202
1203
1205{
1206 routeStep( aP );
1207
1208 if( !m_head.PointCount() )
1209 return false;
1210
1211 return m_head.CPoint( -1 ) == aP;
1212}
1213
1214
1216{
1218 l.Append( m_head.CLine() );
1219
1220 // Only simplify if we have more than two points, because if we have a zero-length seg as the
1221 // only part of the trace, we don't want it to be removed at this stage (will be the case if
1222 // the routing start point violates DRC due to track width in shove/walk mode, for example).
1223 if( l.PointCount() > 2 )
1224 l.Simplify();
1225
1226 LINE tmp( m_head );
1227
1228 tmp.SetShape( l );
1229
1230 PNS_DBG( Dbg(), AddItem, &m_tail, GREEN, 100000, wxT( "tmp-tail" ) );
1231 PNS_DBG( Dbg(), AddItem, &m_head, LIGHTGREEN, 100000, wxT( "tmp-head" ) );
1232
1233 return tmp;
1234}
1235
1236
1238{
1240 return ITEM_SET( &m_currentTrace );
1241}
1242
1243
1245{
1246 // In order to fix issue 12369 get the current line placer first direction
1247 // and copy it to the mouse trail tracer, as the current placer may have
1248 // changed the route.
1250 {
1251 DIRECTION_45 firstDirection( m_currentTrace.CSegment( 0 ) );
1252
1254 }
1255
1257}
1258
1259
1260NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1261{
1262 if( aLoopsRemoved && m_lastNode )
1263 return m_lastNode;
1264
1265 return m_currentNode;
1266}
1267
1268
1270{
1271 if( !aSeg )
1272 return false;
1273
1274 if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1275 return false;
1276
1277 const JOINT* jt = aNode->FindJoint( aP, aSeg );
1278
1279 if( jt && jt->LinkCount() >= 1 )
1280 return false;
1281
1282 SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1283
1284 std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1285
1286 s_new[0]->SetEnds( s_old->Seg().A, aP );
1287 s_new[1]->SetEnds( aP, s_old->Seg().B );
1288
1289 aNode->Remove( s_old );
1290 aNode->Add( std::move( s_new[0] ), true );
1291 aNode->Add( std::move( s_new[1] ), true );
1292
1293 return true;
1294}
1295
1296
1297bool LINE_PLACER::SplitAdjacentArcs( NODE* aNode, ITEM* aArc, const VECTOR2I& aP )
1298{
1299 if( !aArc )
1300 return false;
1301
1302 if( !aArc->OfKind( ITEM::ARC_T ) )
1303 return false;
1304
1305 const JOINT* jt = aNode->FindJoint( aP, aArc );
1306
1307 if( jt && jt->LinkCount() >= 1 )
1308 return false;
1309
1310 ARC* a_old = static_cast<ARC*>( aArc );
1311 const SHAPE_ARC& o_arc = a_old->Arc();
1312
1313 std::unique_ptr<ARC> a_new[2] = { Clone( *a_old ), Clone( *a_old ) };
1314
1315 a_new[0]->Arc().ConstructFromStartEndCenter( o_arc.GetP0(), aP, o_arc.GetCenter(),
1316 o_arc.IsClockwise(), o_arc.GetWidth() );
1317
1318 a_new[1]->Arc().ConstructFromStartEndCenter( aP, o_arc.GetP1(), o_arc.GetCenter(),
1319 o_arc.IsClockwise(), o_arc.GetWidth() );
1320
1321 aNode->Remove( a_old );
1322 aNode->Add( std::move( a_new[0] ), true );
1323 aNode->Add( std::move( a_new[1] ), true );
1324
1325 return true;
1326}
1327
1328
1329bool LINE_PLACER::SetLayer( int aLayer )
1330{
1331 if( m_idle )
1332 {
1333 m_currentLayer = aLayer;
1334 return true;
1335 }
1336 else if( m_chainedPlacement )
1337 {
1338 return false;
1339 }
1340 else if( !m_startItem
1341 || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1342 || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1343 {
1344 m_currentLayer = aLayer;
1348 m_head.Line().Clear();
1349 m_tail.Line().Clear();
1350 m_head.RemoveVia();
1351 m_tail.RemoveVia();
1354 Move( m_currentEnd, nullptr );
1355 return true;
1356 }
1357
1358 return false;
1359}
1360
1361
1362bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1363{
1364 m_placementCorrect = false;
1365 m_currentStart = VECTOR2I( aP );
1366 m_fixStart = VECTOR2I( aP );
1367 m_currentEnd = VECTOR2I( aP );
1368 m_currentNet = aStartItem ? aStartItem->Net() : Router()->GetInterface()->GetOrphanedNetHandle();
1369 m_startItem = aStartItem;
1370 m_placingVia = false;
1371 m_chainedPlacement = false;
1373 m_endItem = nullptr;
1374
1375 setInitialDirection( Settings().InitialDirection() );
1376
1377 initPlacement();
1378
1379 DIRECTION_45 initialDir = m_initial_direction;
1381
1382 if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1383 {
1384 // If we land on a segment endpoint, assume the starting direction is continuing along
1385 // the same direction as the endpoint. If we started in the middle, don't set a
1386 // direction so that the posture solver is not biased.
1387 SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1388
1389 if( aP == seg.A )
1390 lastSegDir = DIRECTION_45( seg.Reversed() );
1391 else if( aP == seg.B )
1392 lastSegDir = DIRECTION_45( seg );
1393 }
1394 else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1395 static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1396 {
1397 double angle = static_cast<SOLID*>( aStartItem )->GetOrientation().AsDegrees();
1398 angle = ( angle + 22.5 ) / 45.0;
1399 initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1400 }
1401
1402 PNS_DBG( Dbg(), Message, wxString::Format( "Posture: init %s, last seg %s",
1403 initialDir.Format(), lastSegDir.Format() ) );
1404
1409 m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1410
1411 NODE *n;
1412
1413 if ( Settings().Mode() == PNS::RM_Shove )
1414 n = m_shove->CurrentNode();
1415 else
1416 n = m_currentNode;
1417
1419
1420 return true;
1421}
1422
1423
1425{
1426 m_idle = false;
1427
1428 m_head.Line().Clear();
1429 m_tail.Line().Clear();
1436 m_head.RemoveVia();
1437 m_tail.RemoveVia();
1438
1439 m_last_p_end.reset();
1442
1443 NODE* world = Router()->GetWorld();
1444
1445 world->KillChildren();
1446 NODE* rootNode = world->Branch();
1447
1449
1450 setWorld( rootNode );
1451
1452 wxLogTrace( wxT( "PNS" ), wxT( "world %p, intitial-direction %s layer %d" ),
1453 m_world,
1454 m_direction.Format().c_str(),
1456
1457 m_lastNode = nullptr;
1459
1460 m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1461}
1462
1463
1464bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1465{
1466 LINE current;
1467 int eiDepth = -1;
1468
1469 if( aEndItem && aEndItem->Owner() )
1470 eiDepth = static_cast<const NODE*>( aEndItem->Owner() )->Depth();
1471
1472 if( m_lastNode )
1473 {
1474 delete m_lastNode;
1475 m_lastNode = nullptr;
1476 }
1477
1478 m_endItem = aEndItem;
1479
1480 bool reachesEnd = route( aP );
1481
1482 current = Trace();
1483
1484 if( !current.PointCount() )
1486 else
1487 m_currentEnd = current.CLine().CPoint( -1 );
1488
1489 NODE* latestNode = m_currentNode;
1490 m_lastNode = latestNode->Branch();
1491
1492 if( reachesEnd
1493 && eiDepth >= 0
1494 && aEndItem && latestNode->Depth() >= eiDepth
1495 && current.SegmentCount() )
1496 {
1497 if ( aEndItem->Net() == m_currentNet )
1498 SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1499
1500 if( Settings().RemoveLoops() )
1501 removeLoops( m_lastNode, current );
1502 }
1503
1506 return true;
1507}
1508
1509
1510bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1511{
1512 bool fixAll = Settings().GetFixAllSegments();
1513 bool realEnd = false;
1514
1515 LINE pl = Trace();
1516
1517 if( Settings().Mode() == RM_MarkObstacles )
1518 {
1519 // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1520 // user has more responsibility and authority.
1521
1522 if( aEndItem )
1523 {
1524 // The user has indicated a connection should be made. If either the trace or
1525 // endItem is net-less, then allow the connection by adopting the net of the other.
1527 {
1528 m_currentNet = aEndItem->Net();
1529 pl.SetNet( m_currentNet );
1530 }
1531 else if( m_router->GetInterface()->GetNetCode( aEndItem->Net() ) <= 0 )
1532 {
1533 aEndItem->SetNet( m_currentNet );
1534 }
1535 }
1536 }
1537
1538 // Collisions still prevent fixing unless "Allow DRC violations" is checked
1539 // Note that collisions can occur even in walk/shove modes if the beginning of the trace
1540 // collides (for example if the starting track width is too high).
1541
1542 if( !Settings().AllowDRCViolations() )
1543 {
1544 NODE* checkNode = ( Settings().Mode() == RM_Shove ) ? m_shove->CurrentNode() : m_world;
1545 std::optional<OBSTACLE> obs = checkNode->CheckColliding( &pl );
1546
1547 if( obs )
1548 {
1549 // TODO: Determine why the shove node sometimes reports collisions against shoved objects.
1550 // For now, to work around this issue, we consider only solids in shove mode.
1551 if( Settings().Mode() != RM_Shove || obs->m_item->OfKind( ITEM::SOLID_T ) )
1552 return false;
1553 }
1554 }
1555
1556 const SHAPE_LINE_CHAIN& l = pl.CLine();
1557
1558 if( !l.SegmentCount() )
1559 {
1560 if( m_lastNode )
1561 {
1562 // Do a final optimization to the stored state
1563 NODE::ITEM_VECTOR removed, added;
1564 m_lastNode->GetUpdatedItems( removed, added );
1565
1566 if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1567 simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1568 }
1569
1570 // Nothing to commit if we have an empty line
1571 if( !pl.EndsWithVia() )
1572 return false;
1573
1576 if( m_lastNode )
1577 {
1578 m_lastNode->Add( Clone( pl.Via() ) );
1579 m_shove->AddLockedSpringbackNode( m_lastNode );
1580 }
1581
1582 m_currentNode = nullptr;
1583
1584 m_idle = true;
1585 m_placementCorrect = true;
1586 return true;
1587 }
1588
1589 VECTOR2I p_pre_last = l.CPoint( -1 );
1590 const VECTOR2I p_last = l.CPoint( -1 );
1591
1592 if( l.PointCount() > 2 )
1593 p_pre_last = l.CPoint( -2 );
1594
1595 if( aEndItem && m_currentNet && m_currentNet == aEndItem->Net() )
1596 realEnd = true;
1597
1598 if( aForceFinish )
1599 realEnd = true;
1600
1601 // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1602 // so if we are, act as though we are in fix-all mode.
1603 if( !fixAll && l.ArcCount() )
1604 fixAll = true;
1605
1606 // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1607 SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1608 DIRECTION_45 d_last( lastDirSeg );
1609
1610 int lastV;
1611
1612 if( realEnd || m_placingVia || fixAll )
1613 lastV = l.SegmentCount();
1614 else
1615 lastV = std::max( 1, l.SegmentCount() - 1 );
1616
1617 ARC arc;
1618 SEGMENT seg;
1619 LINKED_ITEM* lastItem = nullptr;
1620 int lastArc = -1;
1621
1622 for( int i = 0; i < lastV; i++ )
1623 {
1624 ssize_t arcIndex = l.ArcIndex( i );
1625
1626 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1627 {
1628 seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1629 seg.SetWidth( pl.Width() );
1630 seg.SetLayer( m_currentLayer );
1631
1632 std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1633 lastItem = sp.get();
1634
1635 if( !m_lastNode->Add( std::move( sp ) ) )
1636 lastItem = nullptr;
1637 }
1638 else
1639 {
1640 if( arcIndex == lastArc )
1641 continue;
1642
1643 arc = ARC( l.Arc( arcIndex ), m_currentNet );
1644 arc.SetWidth( pl.Width() );
1645 arc.SetLayer( m_currentLayer );
1646
1647 std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1648 lastItem = ap.get();
1649
1650 if( !m_lastNode->Add( std::move( ap ) ) )
1651 lastItem = nullptr;
1652
1653 lastArc = arcIndex;
1654 }
1655 }
1656
1657 if( pl.EndsWithVia() )
1658 m_lastNode->Add( Clone( pl.Via() ) );
1659
1660 if( realEnd && lastItem )
1661 simplifyNewLine( m_lastNode, lastItem );
1662
1663 if( !realEnd )
1664 {
1665 setInitialDirection( d_last );
1666 m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1667
1669
1671 m_startItem = nullptr;
1672 m_placingVia = false;
1674
1677
1678 m_head.Line().Clear();
1679 m_tail.Line().Clear();
1680 m_head.RemoveVia();
1681 m_tail.RemoveVia();
1684
1685 m_shove->AddLockedSpringbackNode( m_currentNode );
1686
1687 DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1688
1693
1694 m_placementCorrect = true;
1695 }
1696 else
1697 {
1698 m_shove->AddLockedSpringbackNode( m_lastNode );
1699 m_placementCorrect = true;
1700 m_idle = true;
1701 }
1702
1703 return realEnd;
1704}
1705
1706
1707std::optional<VECTOR2I> LINE_PLACER::UnfixRoute()
1708{
1710 std::optional<VECTOR2I> ret;
1711
1712 if ( !m_fixedTail.PopStage( st ) )
1713 return ret;
1714
1715 if( m_head.Line().PointCount() )
1716 ret = m_head.Line().CPoint( 0 );
1717
1718 m_head.Line().Clear();
1719 m_tail.Line().Clear();
1720 m_startItem = nullptr;
1721 m_p_start = st.pts[0].p;
1723 m_direction = st.pts[0].direction;
1724 m_placingVia = st.pts[0].placingVias;
1725 m_currentNode = st.commit;
1726 m_currentLayer = st.pts[0].layer;
1730 m_head.RemoveVia();
1731 m_tail.RemoveVia();
1732
1736
1737 m_shove->RewindSpringbackTo( m_currentNode );
1738 m_shove->UnlockSpringbackNode( m_currentNode );
1739
1740 if( Settings().Mode() == PNS::RM_Shove )
1741 {
1742 m_currentNode = m_shove->CurrentNode();
1744 }
1745
1747
1748 return ret;
1749}
1750
1751
1753{
1755}
1756
1757
1759{
1760 if( Settings().Mode() == PNS::RM_Shove )
1761 {
1762 m_shove->RewindToLastLockedNode();
1763 m_lastNode = m_shove->CurrentNode();
1765 }
1766
1767 if( m_lastNode )
1769
1770 m_lastNode = nullptr;
1771 m_currentNode = nullptr;
1772 return true;
1773}
1774
1775
1776void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1777{
1778 if( !aLatest.SegmentCount() )
1779 return;
1780
1781 if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1782 return;
1783
1784 std::set<LINKED_ITEM *> toErase;
1785 aNode->Add( aLatest, true );
1786
1787 for( int s = 0; s < aLatest.LinkCount(); s++ )
1788 {
1789 LINKED_ITEM* seg = aLatest.GetLink(s);
1790 LINE ourLine = aNode->AssembleLine( seg );
1791 JOINT a, b;
1792 std::vector<LINE> lines;
1793
1794 aNode->FindLineEnds( ourLine, a, b );
1795
1796 if( a == b )
1797 aNode->FindLineEnds( aLatest, a, b );
1798
1799 aNode->FindLinesBetweenJoints( a, b, lines );
1800
1801 int removedCount = 0;
1802 int total = 0;
1803
1804 for( LINE& line : lines )
1805 {
1806 total++;
1807
1808 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1809 {
1810 for( LINKED_ITEM* ss : line.Links() )
1811 toErase.insert( ss );
1812
1813 removedCount++;
1814 }
1815 }
1816
1817 PNS_DBG( Dbg(), Message, wxString::Format( "total segs removed: %d/%d", removedCount, total ) );
1818 }
1819
1820 for( LINKED_ITEM* s : toErase )
1821 aNode->Remove( s );
1822
1823 aNode->Remove( aLatest );
1824}
1825
1826
1828{
1829 wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1830
1831 // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1832 // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1833 // of the line and won't get cleaned up by the optimizer.
1834 NODE::ITEM_VECTOR removed, added;
1835 aNode->GetUpdatedItems( removed, added );
1836
1837 std::set<ITEM*> cleanup;
1838
1839 auto processJoint =
1840 [&]( const JOINT* aJoint, ITEM* aItem )
1841 {
1842 if( !aJoint || aJoint->IsLineCorner() )
1843 return;
1844
1845 SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1846
1847 NODE::ITEM_VECTOR toRemove;
1848
1849 for( ITEM* neighbor : aJoint->CLinks().CItems() )
1850 {
1851 if( neighbor == aItem
1852 || !neighbor->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
1853 || !neighbor->LayersOverlap( aItem ) )
1854 {
1855 continue;
1856 }
1857
1858 if( static_cast<const SEGMENT*>( neighbor )->Width()
1859 != static_cast<const SEGMENT*>( aItem )->Width() )
1860 {
1861 continue;
1862 }
1863
1864 const SEG& testSeg = static_cast<const SEGMENT*>( neighbor )->Seg();
1865
1866 if( refSeg.Contains( testSeg ) )
1867 {
1868 const JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1869 const JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1870
1871 if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1872 ( nB == aJoint && nA->LinkCount() == 1 ) )
1873 {
1874 cleanup.insert( neighbor );
1875 }
1876 }
1877 }
1878 };
1879
1880 for( ITEM* item : added )
1881 {
1882 if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1883 continue;
1884
1885 const JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1886 const JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1887
1888 processJoint( jA, item );
1889 processJoint( jB, item );
1890 }
1891
1892 for( ITEM* seg : cleanup )
1893 aNode->Remove( seg );
1894
1895 // And now we can proceed with assembling the final line and optimizing it.
1896
1897 LINE l = aNode->AssembleLine( aLatest );
1898
1899 bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1900
1901 SHAPE_LINE_CHAIN simplified( l.CLine() );
1902
1903 simplified.Simplify();
1904
1905 if( optimized || simplified.PointCount() != l.PointCount() )
1906 {
1907 aNode->Remove( l );
1908 l.SetShape( simplified );
1909 aNode->Add( l );
1910 }
1911}
1912
1913
1915{
1916 m_sizes = aSizes;
1917
1918 if( !m_idle )
1919 {
1920 // If the track width continues from an existing track, we don't want to change the width.
1921 // Disallow changing width after the first segment has been fixed because we don't want to
1922 // go back and rip up tracks or allow DRC errors
1924 || ( !HasPlacedAnything() && ( !m_startItem || m_startItem->Kind() != ITEM::SEGMENT_T ) ) )
1925 {
1929 }
1930
1931 if( m_head.EndsWithVia() )
1932 {
1935 }
1936 }
1937}
1938
1939
1941{
1942 LINE current = Trace();
1943 SHAPE_LINE_CHAIN ratLine;
1944 TOPOLOGY topo( m_lastNode );
1945
1946 if( topo.LeadingRatLine( &current, ratLine ) )
1948}
1949
1950
1951void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1952{
1953 m_orthoMode = aOrthoMode;
1954}
1955
1956
1957bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia )
1958{
1960 DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1961
1962 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "buildInitialLine: m_direction %s, guessedDir %s, tail points %d" ),
1963 m_direction.Format(), guessedDir.Format(), m_tail.PointCount() ) );
1964
1966 // Rounded corners don't make sense when routing orthogonally (single track at a time)
1967 if( m_orthoMode )
1969
1970 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "pstart [buildInitial]" ) );
1971
1972
1973 if( m_p_start == aP )
1974 {
1975 l.Clear();
1976 }
1977 else
1978 {
1979 if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1980 {
1981 l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1982 }
1983 else
1984 {
1985 if( !m_tail.PointCount() )
1986 l = guessedDir.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1987 else
1988 l = m_direction.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1989 }
1990
1991 if( l.SegmentCount() > 1 && m_orthoMode )
1992 {
1993 VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1994
1995 l.Remove( -1, -1 );
1996 l.SetPoint( 1, newLast );
1997 }
1998 }
1999
2000 aHead.SetLayer( m_currentLayer );
2001 aHead.SetShape( l );
2002
2003 PNS_DBG( Dbg(), AddItem, &aHead, CYAN, 10000, wxT( "initial-trace" ) );
2004
2005
2006 if( !m_placingVia || aForceNoVia )
2007 return true;
2008
2009 VIA v( makeVia( aP ) );
2010 v.SetNet( aHead.Net() );
2011
2012 if( Settings().Mode() == RM_MarkObstacles )
2013 {
2014 aHead.AppendVia( v );
2015 return true;
2016 }
2017
2018 const int collMask = ( Settings().Mode() == RM_Walkaround ) ? ITEM::ANY_T : ITEM::SOLID_T;
2019 const int iterLimit = Settings().ViaForcePropIterationLimit();
2020
2021 for( int attempt = 0; attempt < 2; attempt++)
2022 {
2023 VECTOR2I lead = aP - m_p_start;
2024 VECTOR2I force;
2025
2026 if( attempt == 1 && m_last_p_end.has_value() )
2027 lead = aP - m_last_p_end.value();
2028
2029 if( v.PushoutForce( m_currentNode, lead, force, collMask, iterLimit ) )
2030 {
2031 SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false, cornerMode );
2032 aHead = LINE( aHead, line );
2033
2034 v.SetPos( v.Pos() + force );
2035
2036 aHead.AppendVia( v );
2037
2038 PNS_DBG( Dbg(), AddPoint, v.Pos(), GREEN, 1000000, "via-force-coll-2" );
2039
2040 return true;
2041 }
2042 }
2043
2044 return false; // via placement unsuccessful
2045}
2046
2047
2048void LINE_PLACER::GetModifiedNets( std::vector<NET_HANDLE>& aNets ) const
2049{
2050 aNets.push_back( m_currentNet );
2051}
2052
2053
2055{
2057 return true;
2058}
2059
2060
2061FIXED_TAIL::FIXED_TAIL( int aLineCount )
2062{
2063
2064}
2065
2066
2068{
2069
2070}
2071
2072
2074{
2075 m_stages.clear();
2076}
2077
2078
2079void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
2080 DIRECTION_45 direction, NODE* aNode )
2081{
2082 STAGE st;
2083 FIX_POINT pt;
2084
2085 pt.p = aStart;
2086 pt.layer = aLayer;
2087 pt.direction = direction;
2088 pt.placingVias = placingVias;
2089
2090 st.pts.push_back(pt);
2091 st.commit = aNode;
2092
2093 m_stages.push_back( st );
2094}
2095
2096
2098{
2099 if( !m_stages.size() )
2100 return false;
2101
2102 aStage = m_stages.back();
2103
2104 if( m_stages.size() > 1 )
2105 m_stages.pop_back();
2106
2107 return true;
2108}
2109
2110
2112{
2113 return m_stages.size();
2114}
2115
2116}
2117
const Vec ClosestPointTo(const Vec &aPoint) const
Return the point in this rect that is closest to the provided point.
Definition: box2.h:806
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:181
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:78
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
Definition: direction45.h:49
CORNER_MODE
Corner modes.
Definition: direction45.h:67
@ ROUNDED_90
H/V with filleted corners.
Definition: direction45.h:71
@ MITERED_90
H/V only (90-degree corners)
Definition: direction45.h:70
@ ROUNDED_45
H/V/45 with filleted corners.
Definition: direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition: direction45.h:68
const std::string Format() const
Format the direction in a human readable word.
Definition: direction45.h:129
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:100
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
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
void SetLogger(LOGGER *aLogger)
Definition: pns_algo_base.h:65
virtual LOGGER * Logger()
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
SHAPE_ARC & Arc()
Definition: pns_arc.h:115
void SetWidth(int aWidth) override
Definition: pns_arc.h:83
FIXED_TAIL(int aLineCount=1)
int StageCount() const
bool PopStage(STAGE &aStage)
void AddStage(const VECTOR2I &aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
std::vector< STAGE > m_stages
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:97
BOARD_ITEM * Parent() const
Definition: pns_item.h:186
virtual NET_HANDLE Net() const
Definition: pns_item.h:194
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
void SetNet(NET_HANDLE aNet)
Definition: pns_item.h:193
void SetLayer(int aLayer)
Definition: pns_item.h:199
@ SEGMENT_T
Definition: pns_item.h:106
const LAYER_RANGE & Layers() const
Definition: pns_item.h:196
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
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:43
int LinkCount(int aMask=-1) const
Definition: pns_joint.h:289
bool IsLineCorner(bool aAllowLockedSegs=false) const
Checks if a joint connects two segments of the same net, layer, and width.
Definition: pns_joint.h:101
const ITEM_SET & CLinks() const
Definition: pns_joint.h:279
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
bool SplitAdjacentArcs(NODE *aNode, ITEM *aArc, const VECTOR2I &aP)
Snaps the point aP to arc aArc.
bool handleSelfIntersections()
Check if the head of the track intersects its tail.
LINE_PLACER(ROUTER *aRouter)
bool SetLayer(int aLayer) override
Set the current routing layer.
NODE * m_lastNode
Postprocessed world state (including marked collisions & removed loops)
bool route(const VECTOR2I &aP)
Re-route the current track to point aP.
void updatePStart(const LINE &tail)
bool AbortPlacement() override
std::unique_ptr< SHOVE > m_shove
The shove engine.
const LINE Trace() const
Return the complete routed line.
bool splitHeadTail(const LINE &aNewLine, const LINE &aOldTail, LINE &aNewHead, LINE &aNewTail)
bool handlePullback()
Deal with pull-back: reduces the tail if head trace is moved backwards wrs to the current tail direct...
void setWorld(NODE *aWorld)
Set the board to route.
void UpdateSizes(const SIZES_SETTINGS &aSizes) override
Perform on-the-fly update of the width, via diameter & drill size from a settings class.
bool reduceTail(const VECTOR2I &aEnd)
Attempt to reduce the number of segments in the tail by trying to replace a certain number of latest ...
void SetOrthoMode(bool aOrthoMode) override
Function SetOrthoMode()
LINE m_tail
routing "tail": part of the track that has been already fixed due to collisions with obstacles
MOUSE_TRAIL_TRACER m_mouseTrailTracer
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
std::optional< VECTOR2I > m_last_p_end
bool optimizeTailHeadTransition()
Try to reduce the corner count of the most recent part of tail/head by merging obtuse/collinear segme...
bool HasPlacedAnything() const override
void routeStep(const VECTOR2I &aP)
Perform a single routing algorithm step, for the end point aP.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, bool aForceNoVia=false)
NODE * m_currentNode
Current world state.
bool cursorDistMinimum(const SHAPE_LINE_CHAIN &aL, const VECTOR2I &aCursor, double lengthThreshold, SHAPE_LINE_CHAIN &aOut)
LINE m_head
the volatile part of the track from the previously analyzed point to the current routing destination
void removeLoops(NODE *aNode, LINE &aLatest)
Searches aNode for traces concurrent to aLatest and removes them.
VECTOR2I m_fixStart
start point of the last 'fix'
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
NODE * m_world
pointer to world to search colliding items
NET_HANDLE m_currentNet
DIRECTION_45 m_initial_direction
routing direction for new traces
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
SIZES_SETTINGS m_sizes
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Snaps the point aP to segment aSeg.
void setInitialDirection(const DIRECTION_45 &aDirection)
Set preferred direction of the very first track segment to be laid.
void updateLeadingRatLine()
Draw the "leading" rats nest line, which connects the end of currently routed track and the nearest y...
bool routeHead(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
Compute the head trace between the current start point (m_p_start) and point aP, starting with direct...
bool rhWalkOnly(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
void FlipPosture() override
Toggle the current posture (straight/diagonal) of the trace head.
const VIA makeVia(const VECTOR2I &aP)
bool rhShoveOnly(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
< Route step shove mode.
bool rhWalkBase(const VECTOR2I &aP, LINE &aWalkLine, int aCollisionMask, bool &aViaOk)
bool CommitPlacement() override
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void GetModifiedNets(std::vector< NET_HANDLE > &aNets) const override
Function GetModifiedNets.
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).
void simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Initialize placement of a new line with given parameters.
FIXED_TAIL m_fixedTail
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
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...
std::optional< VECTOR2I > UnfixRoute() override
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
bool clipAndCheckCollisions(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aL, SHAPE_LINE_CHAIN &aOut, int &thresholdDist)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
void SetViaDrill(int aDrill)
Definition: pns_line.h:197
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:144
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:125
void RemoveVia()
Definition: pns_line.cpp:1271
int CountCorners(int aAngles) const
Definition: pns_line.cpp:153
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:136
void Clear()
Definition: pns_line.cpp:1264
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:135
VIA & Via()
Definition: pns_line.h:193
int SegmentCount() const
Definition: pns_line.h:138
void SetViaDiameter(int aDiameter)
Definition: pns_line.h:196
int PointCount() const
Definition: pns_line.h:139
int ShapeCount() const
Return the aIdx-th point of the line.
Definition: pns_line.h:141
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1051
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:148
void SetBlockingObstacle(ITEM *aObstacle)
Definition: pns_line.h:203
bool EndsWithVia() const
Definition: pns_line.h:188
const SEG CSegment(int aIdx) const
Set line width.
Definition: pns_line.h:145
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
void SetDefaultDirections(DIRECTION_45 aInitDirection, DIRECTION_45 aLastSegDir)
void SetMouseDisabled(bool aDisabled=true)
Disables the mouse-trail portion of the posture solver; leaving only the manual posture switch and th...
void AddTrailPoint(const VECTOR2I &aP)
DIRECTION_45 GetPosture(const VECTOR2I &aP)
Keep the router "world" - i.e.
Definition: pns_node.h:207
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:143
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:1107
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:218
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:129
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:1416
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:410
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1212
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:217
int Depth() const
Definition: pns_node.h:257
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1100
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:663
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:283
void KillChildren()
Definition: pns_node.cpp:1496
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:884
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:1014
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
Definition: pns_optimizer.h:95
void SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_COLINEAR
Merge co-linear segments.
const ITEM_OWNER * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:71
virtual int GetNetCode(NET_HANDLE aNet) const =0
virtual void DisplayRatline(const SHAPE_LINE_CHAIN &aRatline, NET_HANDLE aNetCode)=0
virtual NET_HANDLE GetOrphanedNetHandle()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:218
void CommitRouting()
Definition: pns_router.cpp:896
NODE * GetWorld() const
Definition: pns_router.h:164
int ViaForcePropIterationLimit() const
double WalkaroundHugLengthThreshold() const
PNS_MODE Mode() const
Set the routing mode.
DIRECTION_45::CORNER_MODE GetCornerMode() const
const SEG & Seg() const
Definition: pns_segment.h:84
int Width() const override
Definition: pns_segment.h:79
void SetWidth(int aWidth) override
Definition: pns_segment.h:74
@ SH_HEAD_MODIFIED
Definition: pns_shove.h:54
VIATYPE ViaType() const
bool TrackWidthIsExplicit() const
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const VECTOR2I & Pos() const
Definition: pns_via.h:128
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
Definition: pns_via.cpp:52
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:130
void SetIterationLimit(const int aIterLimit)
void SetSolidsOnly(bool aSolidsOnly)
void SetItemMask(int aMask)
WALKAROUND_STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:269
int Length() const
Return the length (this).
Definition: seg.h:326
bool Contains(const SEG &aSeg) const
Definition: seg.h:307
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:312
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:356
bool IsClockwise() const
Definition: shape_arc.h:263
int GetWidth() const
Definition: shape_arc.h:158
const VECTOR2I & GetP1() const
Definition: shape_arc.h:114
const VECTOR2I & GetP0() const
Definition: shape_arc.h:113
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:505
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
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.
const std::vector< SHAPE_ARC > & CArcs() const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int SegmentCount() const
Return the number of segments in this line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
size_t ArcCount() const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
@ LIGHTGREEN
Definition: color4d.h:63
@ WHITE
Definition: color4d.h:48
@ BLUE
Definition: color4d.h:56
@ MAGENTA
Definition: color4d.h:60
@ GREEN
Definition: color4d.h:57
@ CYAN
Definition: color4d.h:58
@ LIGHTCYAN
Definition: color4d.h:64
@ RED
Definition: color4d.h:59
@ B_Cu
Definition: layer_ids.h:95
@ F_Cu
Definition: layer_ids.h:64
Push and Shove diff pair dimensions (gap) settings dialog.
@ RM_MarkObstacles
Ignore collisions, mark obstacles.
@ RM_Walkaround
Only walk around.
@ RM_Shove
Only shove.
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:309
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
std::vector< FIX_POINT > pts
WALKAROUND_STATUS statusCcw
WALKAROUND_STATUS statusCw
Represent an intersection between two line segments.
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:638