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