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 The 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
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22#include <optional>
23#include <memory>
24
25#include <wx/log.h>
26
27#include <board_item.h>
28
29#include "pns_arc.h"
30#include "pns_debug_decorator.h"
31#include "pns_line_placer.h"
32#include "pns_node.h"
33#include "pns_router.h"
34#include "pns_shove.h"
35#include "pns_solid.h"
36#include "pns_topology.h"
37#include "pns_walkaround.h"
39#include "pns_utils.h"
40
41
42namespace PNS {
43
45 PLACEMENT_ALGO( aRouter )
46{
48 m_world = nullptr;
49 m_shove = nullptr;
50 m_currentNode = nullptr;
51 m_idle = true;
52
53 // Init temporary variables (do not leave uninitialized members)
54 m_lastNode = nullptr;
55 m_placingVia = false;
56 m_currentNet = nullptr;
58 m_startItem = nullptr;
59 m_routeStartItem = nullptr;
60 m_endItem = nullptr;
61 m_chainedPlacement = false;
62 m_orthoMode = false;
63 m_placementCorrect = false;
64}
65
66
70
71
73{
74 m_world = aWorld;
75}
76
77
79{
81
82 return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), nullptr, m_sizes.ViaType() );
83}
84
85
86bool LINE_PLACER::ToggleVia( bool aEnabled )
87{
88 m_placingVia = aEnabled;
89
90 if( !aEnabled )
91 m_head.RemoveVia();
92
93 return true;
94}
95
96
98{
99 m_initial_direction = aDirection;
100
101 if( m_tail.SegmentCount() == 0 )
102 m_direction = aDirection;
103}
104
105
107{
108 std::vector<SHAPE_LINE_CHAIN::INTERSECTION> ips;
109 SHAPE_LINE_CHAIN& head = m_head.Line();
110 SHAPE_LINE_CHAIN& tail = m_tail.Line();
111
112 // if there is no tail, there is nothing to intersect with
113 if( tail.PointCount() < 2 )
114 return false;
115
116 if( head.PointCount() < 2 )
117 return false;
118
119 // completely new head trace? chop off the tail
120 if( tail.CPoint(0) == head.CPoint(0) )
121 {
123 tail.Clear();
124 return true;
125 }
126
127 tail.Intersect( head, ips );
128
129 // no intesection points - nothing to reduce
130 if( ips.empty() )
131 return false;
132
133 int n = INT_MAX;
134 VECTOR2I ipoint;
135
136 // if there is more than one intersection, find the one that is
137 // closest to the beginning of the tail.
138 for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
139 {
140 if( i.index_our < n )
141 {
142 n = i.index_our;
143 ipoint = i.p;
144 }
145 }
146
147 // ignore the point where head and tail meet
148 if( ipoint == head.CPoint( 0 ) || ipoint == tail.CLastPoint() )
149 return false;
150
151 // Intersection point is on the first or the second segment: just start routing
152 // from the beginning
153 if( n < 2 )
154 {
156 tail.Clear();
157 head.Clear();
158
159 return true;
160 }
161 else
162 {
163 // Clip till the last tail segment before intersection.
164 // Set the direction to the one of this segment.
165 const SEG last = tail.CSegment( n - 1 );
166 m_direction = DIRECTION_45( last );
167 tail.Remove( n, -1 );
168 return true;
169 }
170
171 return false;
172}
173
174
176{
177 SHAPE_LINE_CHAIN& head = m_head.Line();
178 SHAPE_LINE_CHAIN& tail = m_tail.Line();
179
180 if( head.PointCount() < 2 )
181 return false;
182
183 int n = tail.PointCount();
184
185 if( n == 0 )
186 {
187 return false;
188 }
189 else if( n == 1 )
190 {
191 tail.Clear();
192 return true;
193 }
194
195 DIRECTION_45 first_head, last_tail;
196
197 wxASSERT( tail.PointCount() >= 2 );
198
199 if( !head.IsPtOnArc( 0 ) )
200 first_head = DIRECTION_45( head.CSegment( 0 ) );
201 else
202 first_head = DIRECTION_45( head.CArcs()[head.ArcIndex(0)] );
203
204 int lastSegIdx = tail.PointCount() - 2;
205
206 if( !tail.IsPtOnArc( lastSegIdx ) )
207 last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
208 else
209 last_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex(lastSegIdx)] );
210
211 DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
212
213 // case 1: we have a defined routing direction, and the currently computed
214 // head goes in different one.
215 bool pullback_1 = false; // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
216
217 // case 2: regardless of the current routing direction, if the tail/head
218 // extremities form an acute or right angle, reduce the tail by one segment
219 // (and hope that further iterations) will result with a cleaner trace
220 bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
221
222 if( pullback_1 || pullback_2 )
223 {
224 if( !tail.IsArcSegment( lastSegIdx ) )
225 {
226 const SEG& seg = tail.CSegment( lastSegIdx );
227 m_direction = DIRECTION_45( seg );
228 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "new-pstart [pullback3]" ) );
229
230 }
231 else
232 {
233 const SHAPE_ARC& arc = tail.CArcs()[tail.ArcIndex( lastSegIdx )];
234 m_direction = DIRECTION_45( arc );
235 }
236
237 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: pullback triggered [%d] [%s %s]",
238 n, last_tail.Format(), first_head.Format() ) );
239
240 // erase the last point in the tail, hoping that the next iteration will
241 // result with a head trace that starts with a segment following our
242 // current direction.
243 if( n < 2 )
244 tail.Clear(); // don't leave a single-point tail
245 else
246 tail.RemoveShape( -1 );
247
248 if( !tail.SegmentCount() )
250
251 return true;
252 }
253
254 return false;
255}
256
257
259{
260 SHAPE_LINE_CHAIN& head = m_head.Line();
261 SHAPE_LINE_CHAIN& tail = m_tail.Line();
262
263 int n = tail.SegmentCount();
264
265 if( head.SegmentCount() < 1 )
266 return false;
267
268 // Don't attempt this for too short tails
269 if( n < 2 )
270 return false;
271
272 // Start from the segment farthest from the end of the tail
273 // int start_index = std::max(n - 1 - ReductionDepth, 0);
274
275 DIRECTION_45 new_direction;
276 VECTOR2I new_start;
277 int reduce_index = -1;
278
279 for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
280 {
281 const SEG s = tail.CSegment( i );
282 DIRECTION_45 dir( s );
283
284 // calculate a replacement route and check if it matches
285 // the direction of the segment to be replaced
286 SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
287
288 if( replacement.SegmentCount() < 1 )
289 continue;
290
291 LINE tmp( m_tail, replacement );
292
293 if( m_currentNode->CheckColliding( &tmp, ITEM::ANY_T ) )
294 break;
295
296 if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
297 {
298 new_start = s.A;
299 new_direction = dir;
300 reduce_index = i;
301 }
302 }
303
304 if( reduce_index >= 0 )
305 {
306 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: reducing tail: %d" , reduce_index ) );
307 SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
308
309 m_direction = new_direction;
310 tail.Remove( reduce_index + 1, -1 );
311 head.Clear();
312 return true;
313 }
314
315 if( !tail.SegmentCount() )
317
318 return false;
319}
320
321
323{
324 SHAPE_LINE_CHAIN& head = m_head.Line();
325 SHAPE_LINE_CHAIN& tail = m_tail.Line();
326
327 const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
330
331 head.Simplify();
332 tail.Simplify();
333
334 int n_head = head.ShapeCount();
335 int n_tail = tail.ShapeCount();
336
337 if( n_head < 3 )
338 {
339 PNS_DBG( Dbg(), Message, wxT( "Merge failed: not enough head segs." ) );
340 return false;
341 }
342
343 if( n_tail && head.CPoint( 0 ) != tail.CLastPoint() )
344 {
345 PNS_DBG( Dbg(), Message, wxT( "Merge failed: head and tail discontinuous." ) );
346 return false;
347 }
348
349 if( m_head.CountCorners( ForbiddenAngles ) != 0 )
350 return false;
351
352 DIRECTION_45 dir_tail, dir_head;
353
354 if( !head.IsPtOnArc( 0 ) )
355 dir_head = DIRECTION_45( head.CSegment( 0 ) );
356 else
357 dir_head = DIRECTION_45( head.CArcs()[head.ArcIndex( 0 )] );
358
359 if( n_tail )
360 {
361 wxASSERT( tail.PointCount() >= 2 );
362 int lastSegIdx = tail.PointCount() - 2;
363
364 if( !tail.IsPtOnArc( lastSegIdx ) )
365 dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
366 else
367 dir_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
368
369 if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
370 return false;
371 }
372
373 tail.Append( head );
374
375 tail.Simplify();
376
377 int lastSegIdx = tail.PointCount() - 2;
378
379 if( !tail.IsArcSegment( lastSegIdx ) )
380 m_direction = DIRECTION_45( tail.CSegment( -1 ) );
381 else
382 m_direction = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
383
384 head.Remove( 0, -1 );
385
386 PNS_DBG( Dbg(), Message, wxString::Format( "Placer: merge %d, new direction: %s" , n_head,
387 m_direction.Format() ) );
388
389 head.Simplify();
390 tail.Simplify();
391
392 return true;
393}
394
395
397 SHAPE_LINE_CHAIN& aOut, int &thresholdDist )
398{
399 SHAPE_LINE_CHAIN l( aL );
400 int idx = l.Split( aP );
401
402 if( idx < 0)
403 return false;
404
405 bool rv = true;
406
407 SHAPE_LINE_CHAIN l2 = l.Slice( 0, idx );
408 int dist = l2.Length();
409
410 PNS_DBG( Dbg(), AddPoint, aP, BLUE, 500000, wxString::Format( "hug-target-check-%d", idx ) );
411 PNS_DBG( Dbg(), AddShape, &l2, BLUE, 500000, wxT( "hug-target-line" ) );
412
413 if( dist < thresholdDist )
414 rv = false;
415
416 LINE ctest( m_head, l2 );
417
418 if( m_currentNode->CheckColliding( &ctest ).has_value() )
419 rv = false;
420
421 if( rv )
422 {
423 aOut = std::move( l2 );
424 thresholdDist = dist;
425 }
426
427 return rv;
428}
429
430
432 double lengthThreshold, SHAPE_LINE_CHAIN &aOut )
433{
434 std::vector<int> dists;
435 std::vector<VECTOR2I> pts;
436
437 if( aL.PointCount() == 0 )
438 return false;
439
440 VECTOR2I lastP = aL.CLastPoint();
441 int accumulatedDist = 0;
442
443 dists.reserve( 2 * aL.PointCount() );
444
445 for( int i = 0; i < aL.SegmentCount(); i++ )
446 {
447 const SEG& s = aL.CSegment( i );
448
449 dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
450 pts.push_back( s.A );
451 auto pn = s.NearestPoint( aCursor );
452
453 if( pn != s.A && pn != s.B )
454 {
455 dists.push_back( ( pn - aCursor ).EuclideanNorm() );
456 pts.push_back( pn );
457 }
458
459 accumulatedDist += s.Length();
460
461 if ( accumulatedDist > lengthThreshold )
462 {
463 lastP = s.B;
464 break;
465 }
466 }
467
468 dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
469 pts.push_back( lastP );
470
471 int minDistLoc = std::numeric_limits<int>::max();
472 int minPLoc = -1;
473 int minDistGlob = std::numeric_limits<int>::max();
474 int minPGlob = -1;
475
476 for( int i = 0; i < (int) dists.size(); i++ )
477 {
478 int d = dists[i];
479
480 if( d < minDistGlob )
481 {
482 minDistGlob = d;
483 minPGlob = i;
484 }
485 }
486
487 if( dists.size() >= 3 )
488 {
489 for( int i = 0; i < (int) dists.size() - 3; i++ )
490 {
491 if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
492 {
493 int d = dists[i + 1];
494 if( d < minDistLoc )
495 {
496 minDistLoc = d;
497 minPLoc = i + 1;
498 }
499 }
500 }
501
502 if( dists.back() < minDistLoc && minPLoc >= 0 )
503 {
504 minDistLoc = dists.back();
505 minPLoc = dists.size() - 1;
506 }
507 }
508 else
509 {
510 // Too few points: just use the global
511 minDistLoc = minDistGlob;
512 minPLoc = minPGlob;
513 }
514
515// fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
516// in the code, enabling the global one by default
517 minPLoc = -1;
518 int preferred;
519
520 if( minPLoc < 0 )
521 {
522 preferred = minPGlob;
523 }
524 else
525 {
526 preferred = minPLoc;
527 }
528
529 int thresholdDist = 0;
530
531 if( clipAndCheckCollisions( pts[preferred], aL, aOut, thresholdDist ) )
532 return true;
533
534 thresholdDist = 0;
535
536 SHAPE_LINE_CHAIN l( aL ), prefL;
537
538 bool ok = false;
539
540 for( int i = 0; i < (int) pts.size() ; i++)
541 {
542 //PNS_DBG( Dbg(), AddPoint, pts[i], BLUE, 500000, wxT( "hug-target-fallback" ) );
543
544 ok |= clipAndCheckCollisions( pts[i], aL, aOut, thresholdDist );
545 }
546
547 return ok;
548}
549
550
551bool LINE_PLACER::rhWalkBase( const VECTOR2I& aP, LINE& aWalkLine, int aCollisionMask,
552 PNS::PNS_MODE aMode, bool& aViaOk )
553{
554 LINE walkFull( m_head );
555 LINE l1( m_head );
556
557 PNS_DBG( Dbg(), AddItem, &m_tail, GREEN, 100000, wxT( "walk-base-old-tail" ) );
558 PNS_DBG( Dbg(), AddItem, &m_head, BLUE, 100000, wxT( "walk-base-old-head" ) );
559
560 VECTOR2I walkP = aP;
561
562 WALKAROUND walkaround( m_currentNode, Router() );
563
564 walkaround.SetSolidsOnly( false );
565 walkaround.SetDebugDecorator( Dbg() );
566 walkaround.SetLogger( Logger() );
567 walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
568 walkaround.SetItemMask( aCollisionMask );
570
571 int round = 0;
572
573 do
574 {
575 l1.Clear();
576
577 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "walk-round-%d", round ), 0 );
578 round++;
579
580 aViaOk = buildInitialLine( walkP, l1, aMode, round == 0 );
581 PNS_DBG( Dbg(), AddItem, &l1, BLUE, 20000, wxT( "walk-base-l1" ) );
582
583 if( l1.EndsWithVia() )
584 PNS_DBG( Dbg(), AddPoint, l1.Via().Pos(), BLUE, 100000, wxT( "walk-base-l1-via" ) );
585
586 LINE initTrack( m_tail );
587 initTrack.Line().Append( l1.CLine() );
588 initTrack.Line().Simplify();
589
590
591 double initialLength = initTrack.CLine().Length();
592 double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
593 double hugThresholdLengthComplete =
594 2.0 * initialLength * Settings().WalkaroundHugLengthThreshold();
595
596 WALKAROUND::RESULT wr = walkaround.Route( initTrack );
597 std::optional<LINE> bestLine;
598
599 OPTIMIZER optimizer( m_currentNode );
600
602 optimizer.SetCollisionMask( aCollisionMask );
603
604 using WALKAROUND::WP_CW;
605 using WALKAROUND::WP_CCW;
606
607 int len_cw = wr.status[WP_CW] != WALKAROUND::ST_STUCK ? wr.lines[WP_CW].CLine().Length()
608 : std::numeric_limits<int>::max();
609 int len_ccw = wr.status[WP_CCW] != WALKAROUND::ST_STUCK ? wr.lines[WP_CCW].CLine().Length()
610 : std::numeric_limits<int>::max();
611
612
613 if( wr.status[ WP_CW ] == WALKAROUND::ST_DONE )
614 {
615 PNS_DBG( Dbg(), AddItem, &wr.lines[WP_CW], BLUE, 20000, wxT( "wf-result-cw-preopt" ) );
616 LINE tmpHead, tmpTail;
617
618
620
621 if( splitHeadTail( wr.lines[WP_CW], m_tail, tmpHead, tmpTail ) )
622 {
623 optimizer.Optimize( &tmpHead );
624 wr.lines[WP_CW].SetShape( tmpTail.CLine () );
625 wr.lines[WP_CW].Line().Append( tmpHead.CLine( ) );
626 }
627
628 PNS_DBG( Dbg(), AddItem, &wr.lines[WP_CW], RED, 20000, wxT( "wf-result-cw-postopt" ) );
629 len_cw = wr.lines[WP_CW].CLine().Length();
630 bestLine = wr.lines[WP_CW];
631 }
632
633 if( wr.status[WP_CCW] == WALKAROUND::ST_DONE )
634 {
635 PNS_DBG( Dbg(), AddItem, &wr.lines[WP_CCW], BLUE, 20000, wxT( "wf-result-ccw-preopt" ) );
636
637 LINE tmpHead, tmpTail;
638
640
641 if( splitHeadTail( wr.lines[WP_CCW], m_tail, tmpHead, tmpTail ) )
642 {
643 optimizer.Optimize( &tmpHead );
644 wr.lines[WP_CCW].SetShape( tmpTail.CLine () );
645 wr.lines[WP_CCW].Line().Append( tmpHead.CLine( ) );
646 }
647
648 PNS_DBG( Dbg(), AddItem, &wr.lines[WP_CCW], RED, 20000, wxT( "wf-result-ccw-postopt" ) );
649 len_ccw = wr.lines[WP_CCW].CLine().Length();
650
651 if( len_ccw < len_cw )
652 bestLine = wr.lines[WP_CCW];
653 }
654
655 int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
656
657 if( bestLength < hugThresholdLengthComplete && bestLine.has_value() )
658 {
659 walkFull.SetShape( bestLine->CLine() );
660 walkP = walkFull.CLine().CLastPoint();
661 PNS_DBGN( Dbg(), EndGroup );
662 continue;
663 }
664
665 bool validCw = false;
666 bool validCcw = false;
667 int distCcw = std::numeric_limits<int>::max();
668 int distCw = std::numeric_limits<int>::max();
669
670 SHAPE_LINE_CHAIN l_cw, l_ccw;
671
672
673 if( wr.status[WP_CW] != WALKAROUND::ST_STUCK )
674 {
675 validCw = cursorDistMinimum( wr.lines[WP_CW].CLine(), aP, hugThresholdLength, l_cw );
676
677 if( validCw )
678 distCw = ( aP - l_cw.CLastPoint() ).EuclideanNorm();
679
680 PNS_DBG( Dbg(), AddShape, &l_cw, MAGENTA, 200000, wxString::Format( "wh-result-cw %s",
681 validCw ? "non-colliding"
682 : "colliding" ) );
683 }
684
685 if( wr.status[WP_CCW] != WALKAROUND::ST_STUCK )
686 {
687 validCcw = cursorDistMinimum( wr.lines[WP_CCW].CLine(), aP, hugThresholdLength, l_ccw );
688
689 if( validCcw )
690 distCcw = ( aP - l_ccw.CLastPoint() ).EuclideanNorm();
691
692 PNS_DBG( Dbg(), AddShape, &l_ccw, MAGENTA, 200000, wxString::Format( "wh-result-ccw %s",
693 validCcw ? "non-colliding"
694 : "colliding" ) );
695 }
696
697
698 if( distCw < distCcw && validCw )
699 {
700 walkFull.SetShape( l_cw );
701 walkP = l_cw.CLastPoint();
702 }
703 else if( validCcw )
704 {
705 walkFull.SetShape( l_ccw );
706 walkP = l_ccw.CLastPoint();
707 }
708 else
709 {
710 PNS_DBGN( Dbg(), EndGroup );
711 return false;
712 }
713
714 PNS_DBGN( Dbg(), EndGroup );
715 } while( round < 2 && m_placingVia );
716
717
718 if( l1.EndsWithVia() )
719 {
720 VIA v ( l1.Via() );
721 v.SetPos( walkFull.CLastPoint() );
722 walkFull.AppendVia( v );
723 }
724
725 PNS_DBG( Dbg(), AddItem, &walkFull, GREEN, 200000, wxT( "walk-full" ) );
726
727 if( walkFull.EndsWithVia() )
728 {
729 PNS_DBG( Dbg(), AddPoint, walkFull.Via().Pos(), GREEN, 200000,
730 wxString::Format( "walk-via ok %d", aViaOk ? 1 : 0 ) );
731 }
732
733 aWalkLine = walkFull;
734
735 return !walkFull.EndsWithVia() || aViaOk;
736}
737
738
739bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
740{
741 LINE walkFull;
742
743 int effort = 0;
744 bool viaOk = false;
745
746 if( ! rhWalkBase( aP, walkFull, ITEM::ANY_T, RM_Walkaround, viaOk ) )
747 return false;
748
749 switch( Settings().OptimizerEffort() )
750 {
751 case OE_LOW:
752 effort = 0;
753 break;
754
755 case OE_MEDIUM:
756 case OE_FULL:
758 break;
759 }
760
762
763 // Smart Pads is incompatible with 90-degree mode for now
764 if( Settings().SmartPads()
765 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
766 && !m_mouseTrailTracer.IsManuallyForced() )
767 {
768 effort |= OPTIMIZER::SMART_PADS;
769 }
770
771 if( m_currentNode->CheckColliding( &walkFull ) )
772 {
773 PNS_DBG( Dbg(), AddItem, &walkFull, GREEN, 100000, wxString::Format( "collision check fail" ) );
774 return false;
775 }
776
777 // OK, this deserves a bit of explanation. We used to calculate the walk path for the head only,
778 // but then the clearance epsilon was added, with the intent of improving collision resolution robustness
779 // (now a hull or a walk/shove line cannot collide with the 'owner' of the hull under any circumstances).
780 // This, however, introduced a subtle bug. For a row/column/any other 'regular' arrangement
781 // of overlapping hulls (think of pads of a SOP/SOIC chip or a regular via grid), walking around may
782 // produce a new 'head' that is not considered colliding (due to the clearance epsilon), but with
783 // its start point inside one of the subsequent hulls to process.
784 // We can't have head[0] inside any hull for the algorithm to work - therefore, we now consider the entire
785 // 'tail+head' trace when walking around and in case of success, reconstruct the
786 // 'head' and 'tail' by splitting the walk line at a point that is as close as possible to the original
787 // head[0], but not inside any obstacle hull.
788 //
789 // EXECUTIVE SUMMARY: asinine heuristic to make the router get stuck much less often.
790
791 if( ! splitHeadTail( walkFull, m_tail, aNewHead, aNewTail ) )
792 return false;
793
794 if( m_placingVia && viaOk )
795 {
796 PNS_DBG( Dbg(), AddPoint, aNewHead.CLastPoint(), RED, 1000000, wxString::Format( "VIA" ) );
797
798 aNewHead.AppendVia( makeVia( aNewHead.CLastPoint() ) );
799 }
800
801 OPTIMIZER::Optimize( &aNewHead, effort, m_currentNode );
802
803 PNS_DBG( Dbg(), AddItem, &aNewHead, GREEN, 100000, wxString::Format( "walk-new-head" ) );
804 PNS_DBG( Dbg(), AddItem, &aNewTail, BLUE, 100000, wxT( "walk-new-tail" ) );
805
806 return true;
807}
808
809
810bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
811{
813 m_head.SetBlockingObstacle( nullptr );
814
815 auto obs = m_currentNode->NearestObstacle( &m_head );
816
817 // If the head is in colliding state, snap to the hull of the first obstacle.
818 // This way, one can route tracks as tightly as possible without enabling
819 // the shove/walk mode that certain users find too intrusive.
820 if( obs )
821 {
822 int clearance = m_currentNode->GetClearance( obs->m_item, &m_head, false );
823 const SHAPE_LINE_CHAIN& hull = m_currentNode->GetRuleResolver()->HullCache(
824 obs->m_item, clearance, m_head.Width(), m_head.Layer() );
825 VECTOR2I nearest;
826
828
829 if( cornerMode == DIRECTION_45::MITERED_90 || cornerMode == DIRECTION_45::ROUNDED_90 )
830 nearest = hull.BBox().NearestPoint( aP );
831 else
832 nearest = hull.NearestPoint( aP );
833
834 if( ( nearest - aP ).EuclideanNorm() < m_head.Width() / 2 )
836 }
837
838 // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
839 // but we don't have one right now and there isn't a lot of demand for one. If we do end up
840 // doing that, put it in a new routing mode as "highlight collisions" mode should not have
841 // collision handling other than highlighting.
842#if 0
843 if( !Settings().AllowDRCViolations() )
844 {
845 NODE::OPT_OBSTACLE obs = m_currentNode->NearestObstacle( &m_head );
846
847 if( obs && obs->m_distFirst != INT_MAX )
848 {
849 buildInitialLine( obs->m_ipFirst, m_head );
850 m_head.SetBlockingObstacle( obs->m_item );
851 }
852 }
853#endif
854
855 aNewHead = m_head;
856 aNewTail = m_tail;
857
858 return true;
859}
860
861
862bool LINE_PLACER::splitHeadTail( const LINE& aNewLine, const LINE& aOldTail, LINE& aNewHead,
863 LINE& aNewTail )
864{
865 LINE newTail( aOldTail );
866 LINE newHead( aOldTail );
867 LINE l2( aNewLine );
868
869 newTail.RemoveVia();
870 newHead.Clear();
871
872 int i;
873 bool found = false;
874 int n = l2.PointCount();
875
876 if( n > 1 && aOldTail.PointCount() > 1 )
877 {
878 if( l2.CLine().PointOnEdge( aOldTail.CLastPoint() ) )
879 {
880 l2.Line().Split( aOldTail.CLastPoint() );
881 }
882
883 for( i = 0; i < aOldTail.PointCount(); i++ )
884 {
885 if( l2.CLine().Find( aOldTail.CPoint( i ) ) < 0 )
886 {
887 found = true;
888 break;
889 }
890 }
891
892 if( !found )
893 i--;
894
895 // If the old tail doesn't have any points of the new line, we can't split it.
896 if( i >= l2.PointCount() )
897 i = l2.PointCount() - 1;
898
899 newHead.Clear();
900
901 if( i == 0 )
902 newTail.Clear();
903 else
904 newTail.SetShape( l2.CLine().Slice( 0, i ) );
905
906 newHead.SetShape( l2.CLine().Slice( i, -1 ) );
907 }
908 else
909 {
910 newTail.Clear();
911 newHead = std::move( l2 );
912 }
913
914 PNS_DBG( Dbg(), AddItem, &newHead, BLUE, 500000, wxT( "head-post-split" ) );
915
916 aNewHead = std::move( newHead );
917 aNewTail = std::move( newTail );
918
919 return true;
920}
921
922
923bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
924{
925 LINE walkSolids;
926
927 bool viaOk = false;
928
929 if( ! rhWalkBase( aP, walkSolids, ITEM::SOLID_T, RM_Shove, viaOk ) )
930 return false;
931
932 m_currentNode = m_shove->CurrentNode();
933
934 m_shove->SetLogger( Logger() );
935 m_shove->SetDebugDecorator( Dbg() );
936
937 if( m_endItem )
938 {
939 // Make sure the springback algorithm won't erase the NODE that owns m_endItem.
940 m_shove->SetSpringbackDoNotTouchNode( static_cast<const NODE*>( m_endItem->Owner() ) );
941 }
942 else
943 {
944 // No end item under the cursor anymore. Clear the DoNotTouchNode so springback
945 // can roll back past frames pinned by an earlier obstacle touch.
946 m_shove->SetSpringbackDoNotTouchNode( nullptr );
947 }
948
949 LINE newHead( walkSolids );
950
951 if( walkSolids.EndsWithVia() )
952 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), RED, 1000000, wxString::Format( "SVIA [%d]", viaOk?1:0 ) );
953
954 if( m_placingVia && viaOk )
955 {
956 newHead.AppendVia( makeVia( newHead.CLastPoint() ) );
957 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-new-via" );
958
959 }
960
961 m_shove->ClearHeads();
962 m_shove->AddHeads( newHead, SHOVE::SHP_SHOVE );
963 bool shoveOk = m_shove->Run() == SHOVE::SH_OK;
964
965 m_currentNode = m_shove->CurrentNode();
966
967 int effort = 0;
968
969 switch( Settings().OptimizerEffort() )
970 {
971 case OE_LOW:
972 effort = 0;
973 break;
974
975 case OE_MEDIUM:
976 case OE_FULL:
978 break;
979 }
980
982
983 // Smart Pads is incompatible with 90-degree mode for now
984 if( Settings().SmartPads()
985 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
986 && !m_mouseTrailTracer.IsManuallyForced() )
987 {
988 effort |= OPTIMIZER::SMART_PADS;
989 }
990
991 if( shoveOk )
992 {
993 if( m_shove->HeadsModified() )
994 newHead = m_shove->GetModifiedHead( 0 );
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::Optimize( &aNewHead, effort, m_currentNode );
1009 PNS_DBG( Dbg(), AddItem, &aNewHead, GREEN, 1000000, "head-sh-postopt" );
1010
1011 return true;
1012 }
1013 else
1014 {
1015 return rhWalkOnly( aP, aNewHead, aNewTail );
1016 }
1017
1018 return false;
1019}
1020
1021
1022bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead, LINE& aNewTail )
1023{
1024 switch( Settings().Mode() )
1025 {
1026 case RM_MarkObstacles:
1027 return rhMarkObstacles( aP, aNewHead, aNewTail );
1028 case RM_Walkaround:
1029 return rhWalkOnly( aP, aNewHead, aNewTail );
1030 case RM_Shove:
1031 return rhShoveOnly( aP, aNewHead, aNewTail );
1032 default:
1033 break;
1034 }
1035
1036 return false;
1037}
1038
1039
1041{
1042 LINE linetmp = Trace();
1043
1044 PNS_DBG( Dbg(), Message, "optimize HT" );
1045
1046 // NOTE: FANOUT_CLEANUP can override posture setting at the moment
1047 if( !m_mouseTrailTracer.IsManuallyForced() &&
1049 {
1050 if( linetmp.SegmentCount() < 1 )
1051 return false;
1052
1053 m_head = linetmp;
1054 m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
1055 m_tail.Line().Clear();
1056
1057 return true;
1058 }
1059
1060 SHAPE_LINE_CHAIN& head = m_head.Line();
1061 SHAPE_LINE_CHAIN& tail = m_tail.Line();
1062
1063 int tailLookbackSegments = 3;
1064
1065 //if(m_currentMode() == RM_Walkaround)
1066 // tailLookbackSegments = 10000;
1067
1068 int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
1069
1070 if( tail.ShapeCount() < 3 )
1071 return false;
1072
1073 // assemble TailLookbackSegments tail segments with the current head
1074 SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
1075
1076 int end = std::min(2, head.PointCount() - 1 );
1077
1078 opt_line.Append( head.Slice( 0, end ) );
1079
1080 LINE new_head( m_tail, opt_line );
1081
1082 // and see if it could be made simpler by merging obtuse/collnear segments.
1083 // If so, replace the (threshold) last tail points and the head with
1084 // the optimized line
1085
1086 PNS_DBG( Dbg(), AddItem, &new_head, LIGHTCYAN, 10000, wxT( "ht-newline" ) );
1087
1089 {
1090 LINE tmp( m_tail, opt_line );
1091
1092 head.Clear();
1093 tail.Replace( -threshold, -1, new_head.CLine() );
1094 tail.Simplify();
1095
1096 m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
1097
1098 return true;
1099 }
1100
1101 return false;
1102}
1103
1105{
1106 if( tail.CLine().PointCount() )
1107 m_p_start = tail.CLine().CLastPoint();
1108 else
1110}
1111
1113{
1114 bool fail = false;
1115 bool go_back = false;
1116
1117 int i, n_iter = 1;
1118
1119
1120 PNS_DBG( Dbg(), Message, wxString::Format( "routeStep: direction: %s head: %d, tail: %d shapes" ,
1121 m_direction.Format(),
1122 m_head.ShapeCount(),
1123 m_tail.ShapeCount() ) );
1124
1125 PNS_DBG( Dbg(), BeginGroup, wxT( "route-step" ), 0 );
1126
1127 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-init" ) );
1128 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-init" ) );
1129
1130 for( i = 0; i < n_iter; i++ )
1131 {
1132 LINE prevTail( m_tail );
1133 LINE prevHead( m_head );
1134 LINE newHead, newTail;
1135
1136 if( !go_back && Settings().FollowMouse() )
1137 reduceTail( aP );
1138
1139 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-reduce" ) );
1140 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-reduce" ) );
1141
1142 go_back = false;
1143
1145
1146 if( !routeHead( aP, newHead, newTail ) )
1147 {
1148 m_tail = std::move( prevTail );
1149 m_head = std::move( prevHead );
1150
1151 // If we fail to walk out of the initial point (no tail), instead of returning an empty
1152 // line, return a zero-length line so that the user gets some feedback that routing is
1153 // happening. This will get pruned later.
1154 if( m_tail.PointCount() == 0 )
1155 {
1156 m_tail.Line().Append( m_p_start );
1157 m_tail.Line().Append( m_p_start, true );
1158 }
1159
1160 fail = true;
1161 }
1162
1164
1165 PNS_DBG( Dbg(), AddItem, &newHead, LIGHTGREEN, 100000, wxString::Format( "new_head [fail: %d]", fail?1:0 ) );
1166
1167 if( fail )
1168 break;
1169
1170 PNS_DBG( Dbg(), Message, wxString::Format( "N VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1171
1172 m_head = std::move( newHead );
1173 m_tail = std::move( newTail );
1174
1176 {
1177 n_iter++;
1178 go_back = true;
1179 }
1180
1181 PNS_DBG( Dbg(), Message, wxString::Format( "SI VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1182
1183 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-si" ) );
1184 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-si" ) );
1185
1186 if( !go_back && handlePullback() )
1187 {
1188 n_iter++;
1189 m_head.Clear();
1190 go_back = true;
1191 }
1192
1193 PNS_DBG( Dbg(), Message, wxString::Format( "PB VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1194
1195 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-after-pb" ) );
1196 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-after-pb" ) );
1197 }
1198
1199
1200 if( !fail && Settings().FollowMouse() )
1201 {
1202 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-pre-merge" ) );
1203 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-pre-merge" ) );
1204
1206 {
1207 PNS_DBG( Dbg(), Message, wxString::Format( "PreM VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1208
1209 mergeHead();
1210
1211 PNS_DBG( Dbg(), Message, wxString::Format( "PostM VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1212 }
1213
1214 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 100000, wxT( "tail-post-merge" ) );
1215 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 100000, wxT( "head-post-merge" ) );
1216 }
1217
1218 m_last_p_end = aP;
1219
1220 PNS_DBGN( Dbg(), EndGroup );
1221}
1222
1223
1225{
1226 routeStep( aP );
1227
1228 // Shove and walkaround can merge the whole head into the tail
1229 const LINE& last = m_head.PointCount() ? m_head : m_tail;
1230
1231 if( !last.PointCount() )
1232 return false;
1233
1234 return last.CLastPoint() == aP;
1235}
1236
1237
1239{
1240 SHAPE_LINE_CHAIN l( m_tail.CLine() );
1241 l.Append( m_head.CLine() );
1242
1243 // Only simplify if we have more than two points, because if we have a zero-length seg as the
1244 // only part of the trace, we don't want it to be removed at this stage (will be the case if
1245 // the routing start point violates DRC due to track width in shove/walk mode, for example).
1246 if( l.PointCount() > 2 )
1247 l.Simplify();
1248
1249 LINE tmp( m_head );
1250
1251 tmp.SetShape( l );
1252
1253 PNS_DBG( Dbg(), AddItem, &m_tail, GREEN, 100000, wxT( "tmp-tail" ) );
1254 PNS_DBG( Dbg(), AddItem, &m_head, LIGHTGREEN, 100000, wxT( "tmp-head" ) );
1255
1256 return tmp;
1257}
1258
1259
1261{
1263 return ITEM_SET( &m_currentTrace );
1264}
1265
1266
1268{
1269 // In order to fix issue 12369 get the current line placer first direction
1270 // and copy it to the mouse trail tracer, as the current placer may have
1271 // changed the route.
1272 if( m_mouseTrailTracer.IsManuallyForced() == false && m_currentTrace.SegmentCount() > 0 )
1273 {
1274 DIRECTION_45 firstDirection( m_currentTrace.CSegment( 0 ) );
1275
1276 m_mouseTrailTracer.SetDefaultDirections( firstDirection, DIRECTION_45::UNDEFINED );
1277 }
1278
1279 m_mouseTrailTracer.FlipPosture();
1280}
1281
1282
1283NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1284{
1285 if( aLoopsRemoved && m_lastNode )
1286 return m_lastNode;
1287
1288 return m_currentNode;
1289}
1290
1291
1292bool LINE_PLACER::SetLayer( int aLayer )
1293{
1294 if( m_idle )
1295 {
1296 m_currentLayer = aLayer;
1297 return true;
1298 }
1299 else if( m_chainedPlacement )
1300 {
1301 return false;
1302 }
1303 else if( !m_startItem
1304 || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1305 || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1306 {
1307 m_currentLayer = aLayer;
1310 m_mouseTrailTracer.Clear();
1311 m_head.Line().Clear();
1312 m_tail.Line().Clear();
1313 m_head.RemoveVia();
1314 m_tail.RemoveVia();
1315 m_head.SetLayer( m_currentLayer );
1316 m_tail.SetLayer( m_currentLayer );
1317 Move( m_currentEnd, nullptr );
1318 return true;
1319 }
1320
1321 return false;
1322}
1323
1324
1325bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1326{
1327 m_placementCorrect = false;
1328 m_currentStart = VECTOR2I( aP );
1329 m_fixStart = VECTOR2I( aP );
1330 m_currentEnd = VECTOR2I( aP );
1331 m_currentNet = aStartItem ? aStartItem->Net() : Router()->GetInterface()->GetOrphanedNetHandle();
1332 m_startItem = aStartItem;
1333 m_routeStartItem = aStartItem;
1334 m_routeStart = aP;
1335 m_placingVia = false;
1336 m_chainedPlacement = false;
1337 m_fixedTail.Clear();
1338 m_endItem = nullptr;
1339
1340 setInitialDirection( Settings().InitialDirection() );
1341
1342 initPlacement();
1343
1344 DIRECTION_45 initialDir = m_initial_direction;
1346
1347 if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1348 {
1349 // If we land on a segment endpoint, assume the starting direction is continuing along
1350 // the same direction as the endpoint. If we started in the middle, don't set a
1351 // direction so that the posture solver is not biased.
1352 SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1353
1354 if( aP == seg.A )
1355 lastSegDir = DIRECTION_45( seg.Reversed() );
1356 else if( aP == seg.B )
1357 lastSegDir = DIRECTION_45( seg );
1358 }
1359 else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1360 static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1361 {
1362 double angle = static_cast<SOLID*>( aStartItem )->GetOrientation().AsDegrees();
1363 angle = ( angle + 22.5 ) / 45.0;
1364 initialDir = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1365 }
1366
1367 PNS_DBG( Dbg(), Message, wxString::Format( "Posture: init %s, last seg %s",
1368 initialDir.Format(), lastSegDir.Format() ) );
1369
1370 m_mouseTrailTracer.Clear();
1371 m_mouseTrailTracer.AddTrailPoint( aP );
1372 m_mouseTrailTracer.SetTolerance( m_head.Width() );
1374 m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1375
1376 NODE *n;
1377
1378 if ( Settings().Mode() == PNS::RM_Shove )
1379 n = m_shove->CurrentNode();
1380 else
1381 n = m_currentNode;
1382
1384
1385 return true;
1386}
1387
1388
1390{
1391 m_idle = false;
1392
1393 m_head.Line().Clear();
1394 m_tail.Line().Clear();
1395 m_head.SetNet( m_currentNet );
1396 m_tail.SetNet( m_currentNet );
1397 m_head.SetLayer( m_currentLayer );
1398 m_tail.SetLayer( m_currentLayer );
1399 m_head.SetWidth( m_sizes.TrackWidth() );
1400 m_tail.SetWidth( m_sizes.TrackWidth() );
1401 m_head.RemoveVia();
1402 m_tail.RemoveVia();
1403
1404 // Solder mask overrides live on the board item, so a rework carries its start track to the
1405 // write back; the tail too, since splitHeadTail() rebuilds both halves from it
1406 BOARD_ITEM* source = nullptr;
1407
1409 source = m_startItem->GetSourceItem();
1410
1411 m_head.SetSourceItem( source );
1412 m_tail.SetSourceItem( source );
1413
1414 m_last_p_end.reset();
1417
1418 NODE* world = Router()->GetWorld();
1419
1420 world->KillChildren();
1421 NODE* rootNode = world->Branch();
1422
1424
1425 setWorld( rootNode );
1426
1427 wxLogTrace( wxT( "PNS" ), wxT( "world %p, intitial-direction %s layer %d" ),
1428 m_world,
1429 m_direction.Format().c_str(),
1431
1432 m_lastNode = nullptr;
1434
1435 m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1436}
1437
1438
1439bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1440{
1441 LINE current;
1442 int eiDepth = -1;
1443
1444 if( aEndItem && aEndItem->Owner() )
1445 eiDepth = static_cast<const NODE*>( aEndItem->Owner() )->Depth();
1446
1447 if( m_lastNode )
1448 {
1449 delete m_lastNode;
1450 m_lastNode = nullptr;
1451 }
1452
1453 m_endItem = aEndItem;
1454
1455 bool reachesEnd = route( aP );
1456
1457 // When the user enables via placement (e.g. pressing 'V') and the cursor has not moved
1458 // from the routing start, the pushout-force algorithm in buildInitialLine cannot resolve
1459 // a collision because the lead vector is zero. The trace head then does not carry a via
1460 // and a subsequent commit click silently drops the via. Force-attach the via to the head
1461 // at the requested position so the via is part of the trace and can be committed.
1462 if( m_placingVia && aP == m_p_start && !m_head.EndsWithVia() )
1463 {
1464 VIA fallbackVia = makeVia( aP );
1465 fallbackVia.SetNet( m_currentNet );
1466 m_head.AppendVia( fallbackVia );
1467 }
1468
1469 current = Trace();
1470
1471 VECTOR2I splitPoint = current.PointCount() ? current.CLine().CLastPoint() : m_p_start;
1472
1473 if( reachesEnd && aEndItem && current.SegmentCount() && aEndItem->OfKind( ITEM::SEGMENT_T ) )
1474 {
1475 const SEG lastSeg = current.CLine().CSegment( current.SegmentCount() - 1 );
1476 const SEG targetSeg = static_cast<SEGMENT*>( aEndItem )->Seg();
1477
1478 if( lastSeg.Collinear( targetSeg ) && targetSeg.Overlaps( lastSeg ) )
1479 {
1480 splitPoint = targetSeg.NearestPoint( lastSeg.A );
1481 current.Line().SetPoint( current.PointCount() - 1, splitPoint );
1482 LINE& last = m_head.PointCount() ? m_head : m_tail;
1483 last.Line().SetPoint( last.PointCount() - 1, splitPoint );
1484 }
1485 }
1486
1487 if( !current.PointCount() )
1489 else
1490 m_currentEnd = splitPoint;
1491
1492 NODE* latestNode = m_currentNode;
1493 m_lastNode = latestNode->Branch();
1494
1495 if( reachesEnd
1496 && eiDepth >= 0
1497 && aEndItem && latestNode->Depth() >= eiDepth
1498 && current.SegmentCount() )
1499 {
1500 if ( aEndItem->Net() == m_currentNet )
1501 SplitAdjacentSegments( m_lastNode, aEndItem, splitPoint );
1502
1503 if( Settings().RemoveLoops() )
1504 removeLoops( m_lastNode, current );
1505 }
1506
1508 m_mouseTrailTracer.AddTrailPoint( aP );
1509 return true;
1510}
1511
1512
1513bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1514{
1515 bool fixAll = Settings().GetFixAllSegments();
1516 bool realEnd = false;
1517
1518 LINE pl = Trace();
1519
1520 if( Settings().Mode() == RM_MarkObstacles )
1521 {
1522 // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1523 // user has more responsibility and authority.
1524
1525 if( aEndItem )
1526 {
1527 // The user has indicated a connection should be made. If either the trace or
1528 // endItem is net-less, then allow the connection by adopting the net of the other.
1529 if( m_router->GetInterface()->GetNetCode( m_currentNet ) <= 0 )
1530 {
1531 m_currentNet = aEndItem->Net();
1532 pl.SetNet( m_currentNet );
1533 }
1534 else if( m_router->GetInterface()->GetNetCode( aEndItem->Net() ) <= 0 )
1535 {
1536 aEndItem->SetNet( m_currentNet );
1537 }
1538 }
1539 }
1540
1541 // Collisions still prevent fixing unless "Allow DRC violations" is checked
1542 // Note that collisions can occur even in walk/shove modes if the beginning of the trace
1543 // collides (for example if the starting track width is too high).
1544
1545 if( !Settings().AllowDRCViolations() )
1546 {
1547 NODE* checkNode = ( Settings().Mode() == RM_Shove ) ? m_shove->CurrentNode() : m_world;
1548 std::optional<OBSTACLE> obs = checkNode->CheckColliding( &pl );
1549
1550 if( obs )
1551 {
1552 // TODO: Determine why the shove node sometimes reports collisions against shoved objects.
1553 // For now, to work around this issue, we consider only solids in shove mode.
1554 if( Settings().Mode() != RM_Shove || obs->m_item->OfKind( ITEM::SOLID_T ) )
1555 return false;
1556 }
1557 }
1558
1559 const SHAPE_LINE_CHAIN& l = pl.CLine();
1560
1561 if( !l.SegmentCount() )
1562 {
1563 if( m_lastNode )
1564 {
1565 // Do a final optimization to the stored state
1566 NODE::ITEM_VECTOR removed, added;
1567 m_lastNode->GetUpdatedItems( removed, added );
1568
1569 if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1570 simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1571 }
1572
1573 // Nothing to commit if we have an empty line
1574 if( !pl.EndsWithVia() )
1575 return false;
1576
1579 if( m_lastNode )
1580 {
1581 auto newVia = Clone( pl.Via() );
1582 newVia->ResetUid();
1583 m_lastNode->Add( std::move( newVia ) );
1584 m_shove->AddLockedSpringbackNode( m_lastNode );
1585 }
1586
1587 m_currentNode = nullptr;
1588
1589 m_idle = true;
1590 m_placementCorrect = true;
1591 return true;
1592 }
1593
1594 VECTOR2I p_pre_last = l.CLastPoint();
1595 const VECTOR2I p_last = l.CLastPoint();
1596
1597 if( l.PointCount() > 2 )
1598 p_pre_last = l.CPoints()[ l.PointCount() - 2 ];
1599
1600 if( aEndItem && m_currentNet && m_currentNet == aEndItem->Net() )
1601 realEnd = true;
1602
1603 if( aForceFinish )
1604 realEnd = true;
1605
1606 // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1607 // so if we are, act as though we are in fix-all mode.
1608 if( !fixAll && l.ArcCount() )
1609 fixAll = true;
1610
1611 // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1612 SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1613 DIRECTION_45 d_last( lastDirSeg );
1614
1615 int lastV;
1616
1617 if( realEnd || m_placingVia || fixAll )
1618 lastV = l.SegmentCount();
1619 else
1620 lastV = std::max( 1, l.SegmentCount() - 1 );
1621
1622 ARC arc;
1623 SEGMENT seg;
1624 LINKED_ITEM* lastItem = nullptr;
1625 int lastArc = -1;
1626
1627 // Copied by hand, as the SEGMENT( LINE, SEG ) and ARC( LINE, SHAPE_ARC ) constructors would
1628 // also carry the head's marker into the fixed items
1629 for( int i = 0; i < lastV; i++ )
1630 {
1631 ssize_t arcIndex = l.ArcIndex( i );
1632
1633 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1634 {
1635 seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1636 seg.SetWidth( pl.Width() );
1637 seg.SetLayer( m_currentLayer );
1638 seg.SetSourceItem( pl.GetSourceItem() );
1639
1640 std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1641 lastItem = sp.get();
1642
1643 if( !m_lastNode->Add( std::move( sp ) ) )
1644 lastItem = nullptr;
1645 }
1646 else
1647 {
1648 if( arcIndex == lastArc )
1649 continue;
1650
1651 arc = ARC( l.Arc( arcIndex ), m_currentNet );
1652 arc.SetWidth( pl.Width() );
1653 arc.SetLayer( m_currentLayer );
1654 arc.SetSourceItem( pl.GetSourceItem() );
1655
1656 std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1657 lastItem = ap.get();
1658
1659 if( !m_lastNode->Add( std::move( ap ) ) )
1660 lastItem = nullptr;
1661
1662 lastArc = arcIndex;
1663 }
1664 }
1665
1666 if( pl.EndsWithVia() )
1667 {
1668 auto newVia = Clone( pl.Via() );
1669 newVia->ResetUid();
1670 m_lastNode->Add( std::move( newVia ) );
1671 }
1672
1673
1674 if( lastItem )
1675 simplifyNewLine( m_lastNode, lastItem );
1676
1677 if( realEnd && Settings().RemoveLoops() )
1678 {
1679 removeAntennas( m_lastNode, aEndItem, p_last );
1681 }
1682
1683 if( !realEnd )
1684 {
1685 setInitialDirection( d_last );
1686 m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1687
1689
1691 m_startItem = nullptr;
1692 m_placingVia = false;
1694
1697
1698 m_head.Line().Clear();
1699 m_tail.Line().Clear();
1700 m_head.RemoveVia();
1701 m_tail.RemoveVia();
1703 m_lastNode = m_lastNode->Branch();
1704
1705 m_shove->AddLockedSpringbackNode( m_currentNode );
1706
1707 DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1708
1709 m_mouseTrailTracer.Clear();
1710 m_mouseTrailTracer.SetTolerance( m_head.Width() );
1711 m_mouseTrailTracer.AddTrailPoint( m_currentStart );
1712 m_mouseTrailTracer.SetDefaultDirections( lastSegDir, lastSegDir );
1713
1714 m_placementCorrect = true;
1715 }
1716 else
1717 {
1718 m_shove->AddLockedSpringbackNode( m_lastNode );
1719 m_placementCorrect = true;
1720 m_idle = true;
1721 }
1722
1723 return realEnd;
1724}
1725
1726
1727std::optional<VECTOR2I> LINE_PLACER::UnfixRoute()
1728{
1730 std::optional<VECTOR2I> ret;
1731
1732 if ( !m_fixedTail.PopStage( st ) )
1733 return ret;
1734
1735 if( m_head.Line().PointCount() )
1736 ret = m_head.Line().CPoint( 0 );
1737
1738 m_head.Line().Clear();
1739 m_tail.Line().Clear();
1740 m_startItem = nullptr;
1741 m_p_start = st.pts[0].p;
1743 m_direction = st.pts[0].direction;
1744 m_placingVia = st.pts[0].placingVias;
1745 m_currentNode = st.commit;
1746 m_currentLayer = st.pts[0].layer;
1748 m_head.SetLayer( m_currentLayer );
1749 m_tail.SetLayer( m_currentLayer );
1750 m_head.RemoveVia();
1751 m_tail.RemoveVia();
1752
1753 m_mouseTrailTracer.Clear();
1754 m_mouseTrailTracer.SetDefaultDirections( m_initial_direction, m_direction );
1755 m_mouseTrailTracer.AddTrailPoint( m_p_start );
1756
1757 m_shove->RewindSpringbackTo( m_currentNode );
1758 m_shove->UnlockSpringbackNode( m_currentNode );
1759
1760 if( Settings().Mode() == PNS::RM_Shove )
1761 {
1762 m_currentNode = m_shove->CurrentNode();
1763 m_currentNode->KillChildren();
1764 }
1765
1766 m_lastNode = m_currentNode->Branch();
1767
1768 return ret;
1769}
1770
1771
1773{
1774 return m_placementCorrect || m_fixedTail.StageCount() > 1;
1775}
1776
1777
1779{
1780 // AbortPlacement() already tore down every node, including the shove springback stack.
1781 if( !m_lastNode && !m_currentNode )
1782 return true;
1783
1784 if( Settings().Mode() == PNS::RM_Shove )
1785 {
1786 m_shove->RewindToLastLockedNode();
1787 m_lastNode = m_shove->CurrentNode();
1788 m_lastNode->KillChildren();
1789 }
1790
1791 if( m_lastNode )
1793
1794 m_lastNode = nullptr;
1795 m_currentNode = nullptr;
1796 return true;
1797}
1798
1799
1801{
1802 wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1803
1804 // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1805 // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1806 // of the line and won't get cleaned up by the optimizer.
1807 NODE::ITEM_VECTOR removed, added;
1808 aNode->GetUpdatedItems( removed, added );
1809
1810 std::set<ITEM*> cleanup;
1811
1812 auto processJoint =
1813 [&]( const JOINT* aJoint, ITEM* aItem )
1814 {
1815 if( !aJoint || aJoint->IsLineCorner() )
1816 return;
1817
1818 SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1819
1820 NODE::ITEM_VECTOR toRemove;
1821
1822 for( ITEM* neighbor : aJoint->CLinks().CItems() )
1823 {
1824 if( neighbor == aItem
1825 || !neighbor->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
1826 || !neighbor->LayersOverlap( aItem ) )
1827 {
1828 continue;
1829 }
1830
1831 if( static_cast<const SEGMENT*>( neighbor )->Width()
1832 != static_cast<const SEGMENT*>( aItem )->Width() )
1833 {
1834 continue;
1835 }
1836
1837 const SEG& testSeg = static_cast<const SEGMENT*>( neighbor )->Seg();
1838
1839 if( refSeg.Contains( testSeg ) )
1840 {
1841 const JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1842 const JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1843
1844 if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1845 ( nB == aJoint && nA->LinkCount() == 1 ) )
1846 {
1847 cleanup.insert( neighbor );
1848 }
1849 }
1850 else if( testSeg.Contains( refSeg ) )
1851 {
1852 const JOINT* aA = aNode->FindJoint( aItem->Anchor( 0 ), aItem );
1853 const JOINT* aB = aNode->FindJoint( aItem->Anchor( 1 ), aItem );
1854
1855 if( ( aA == aJoint && aB->LinkCount() == 1 ) ||
1856 ( aB == aJoint && aA->LinkCount() == 1 ) )
1857 {
1858 cleanup.insert( aItem );
1859 return;
1860 }
1861 }
1862 }
1863 };
1864
1865 for( ITEM* item : added )
1866 {
1867 if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1868 continue;
1869
1870 const JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1871 const JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1872
1873 processJoint( jA, item );
1874 processJoint( jB, item );
1875 }
1876
1877 for( ITEM* seg : cleanup )
1878 aNode->Remove( seg );
1879
1880 // And now we can proceed with assembling the final line and optimizing it.
1881
1882 LINE l_orig = aNode->AssembleLine( aLatest, nullptr, false, false, false );
1883 LINE l( l_orig );
1884
1885 bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1886
1887 SHAPE_LINE_CHAIN simplified( l.CLine() );
1888
1889 simplified.Simplify();
1890
1891 if( optimized || simplified.PointCount() != l.PointCount() )
1892 {
1893 aNode->Remove( l_orig );
1894 l.SetShape( simplified );
1895 aNode->Add( l );
1896 PNS_DBG( Dbg(), AddItem, &l, RED, 100000, wxT("simplified"));
1897 }
1898
1899 return true;
1900}
1901
1902
1904{
1905 m_sizes = aSizes;
1906
1907 if( !m_idle )
1908 {
1909 // If the track width continues from an existing track, we don't want to change the width.
1910 // Disallow changing width after the first segment has been fixed because we don't want to
1911 // go back and rip up tracks or allow DRC errors
1912 if( m_sizes.TrackWidthIsExplicit()
1913 || ( !HasPlacedAnything() && ( !m_startItem || m_startItem->Kind() != ITEM::SEGMENT_T ) ) )
1914 {
1915 m_head.SetWidth( m_sizes.TrackWidth() );
1916 m_tail.SetWidth( m_sizes.TrackWidth() );
1917 m_currentTrace.SetWidth( m_sizes.TrackWidth() );
1918 }
1919
1920 if( m_head.EndsWithVia() )
1921 {
1922 m_head.SetViaDiameter( m_sizes.ViaDiameter() );
1923 m_head.SetViaDrill( m_sizes.ViaDrill() );
1924 }
1925 }
1926}
1927
1928
1930{
1931 LINE current = Trace();
1932 SHAPE_LINE_CHAIN ratLine;
1933 TOPOLOGY topo( m_lastNode, m_router->GetInterface() );
1934
1935 if( topo.LeadingRatLine( &current, ratLine ) )
1936 m_router->GetInterface()->DisplayRatline( ratLine, m_currentNet );
1937}
1938
1939
1940void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1941{
1942 m_orthoMode = aOrthoMode;
1943}
1944
1945
1946bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, PNS::PNS_MODE aMode, bool aForceNoVia )
1947{
1949 DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1950
1951 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "buildInitialLine: m_direction %s, guessedDir %s, tail points %d" ),
1952 m_direction.Format(), guessedDir.Format(), m_tail.PointCount() ) );
1953
1955 // Rounded corners don't make sense when routing orthogonally (single track at a time)
1956 if( m_orthoMode )
1958
1959 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "pstart [buildInitial]" ) );
1960
1961 if( m_mouseTrailTracer.IsManuallyForced() )
1962 {
1963 // If head+tail together forms a 'typical' obtuse initial track,
1964 // erase the tail instead of guessing the direction from it. This results in more deterministic
1965 // posture switching in walkaround & shove modes.
1966 if( m_tail.SegmentCount() == 1 && m_head.SegmentCount() > 0 )
1967 {
1968 bool dirMatch = DIRECTION_45( m_tail.CSegment(0) ) == DIRECTION_45( m_head.CSegment( 0 ) );
1969 if( dirMatch || m_head.SegmentCount() == 1 )
1970 {
1971 m_p_start = m_tail.CLine().CPoint( 0 );
1972 m_tail.Clear();
1973 }
1974 }
1975 }
1976
1977 if( m_p_start == aP )
1978 {
1979 l.Clear();
1980 }
1981 else
1982 {
1983 if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1984 {
1985 l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1986 }
1987 else
1988 {
1989 if( !m_tail.PointCount() )
1990 l = guessedDir.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1991 else
1992 l = m_direction.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1993 }
1994
1995 if( l.SegmentCount() > 1 && m_orthoMode )
1996 {
1997 VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CLastPoint() );
1998
1999 l.Remove( -1, -1 );
2000 l.SetPoint( 1, newLast );
2001 }
2002 }
2003
2004 aHead.SetLayer( m_currentLayer );
2005 aHead.SetShape( l );
2006
2007 PNS_DBG( Dbg(), AddItem, &aHead, CYAN, 10000, wxT( "initial-trace" ) );
2008
2009
2010 if( !m_placingVia || aForceNoVia )
2011 return true;
2012
2013 VIA v( makeVia( aP ) );
2014 v.SetNet( aHead.Net() );
2015
2016 if( aMode == RM_MarkObstacles )
2017 {
2018 aHead.AppendVia( v );
2019 return true;
2020 }
2021
2022 const int collMask = ( aMode == RM_Walkaround ) ? ITEM::ANY_T : ITEM::SOLID_T;
2023 const int iterLimit = Settings().ViaForcePropIterationLimit();
2024
2025 for( int attempt = 0; attempt < 2; attempt++)
2026 {
2027 VECTOR2I lead = aP - m_p_start;
2028 VECTOR2I force;
2029
2030 if( attempt == 1 && m_last_p_end.has_value() )
2031 lead = aP - m_last_p_end.value();
2032
2033 if( v.PushoutForce( m_currentNode, lead, force, collMask, iterLimit ) )
2034 {
2035 SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false, cornerMode );
2036 aHead = LINE( aHead, line );
2037
2038 v.SetPos( v.Pos() + force );
2039
2040 aHead.AppendVia( v );
2041
2042 PNS_DBG( Dbg(), AddPoint, v.Pos(), GREEN, 1000000, "via-force-coll-2" );
2043
2044 return true;
2045 }
2046 }
2047
2048 return false; // via placement unsuccessful
2049}
2050
2051
2052void LINE_PLACER::GetModifiedNets( std::vector<NET_HANDLE>& aNets ) const
2053{
2054 aNets.push_back( m_currentNet );
2055}
2056
2057
2059{
2060 m_world->KillChildren();
2061 m_lastNode = nullptr;
2062 m_currentNode = nullptr;
2063 return true;
2064}
2065
2066
2067FIXED_TAIL::FIXED_TAIL( int aLineCount )
2068{
2069
2070}
2071
2072
2074{
2075
2076}
2077
2078
2080{
2081 m_stages.clear();
2082}
2083
2084
2085void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
2086 DIRECTION_45 direction, NODE* aNode )
2087{
2088 STAGE st;
2089 FIX_POINT pt;
2090
2091 pt.p = aStart;
2092 pt.layer = aLayer;
2093 pt.direction = direction;
2094 pt.placingVias = placingVias;
2095
2096 st.pts.push_back(pt);
2097 st.commit = aNode;
2098
2099 m_stages.push_back( std::move( st ) );
2100}
2101
2102
2104{
2105 if( !m_stages.size() )
2106 return false;
2107
2108 aStage = m_stages.back();
2109
2110 if( m_stages.size() > 1 )
2111 m_stages.pop_back();
2112
2113 return true;
2114}
2115
2116
2118{
2119 return m_stages.size();
2120}
2121
2122
2123void LINE_PLACER::removeAntennas( NODE* aNode, const ITEM* aEndItem, const VECTOR2I& aJoin )
2124{
2125 if( !aNode || !aEndItem || aEndItem->Kind() != ITEM::SEGMENT_T || !aEndItem->Parent() || aEndItem->IsLocked()
2126 || aJoin == aEndItem->Anchor( 0 ) || aJoin == aEndItem->Anchor( 1 ) )
2127 {
2128 return;
2129 }
2130
2131 const JOINT* junction = aNode->FindJoint( aJoin, aEndItem );
2132
2133 if( !junction )
2134 return;
2135
2136 std::vector<const ITEM*> newLinks;
2137
2138 for( const ITEM* item : junction->LinkList() )
2139 {
2140 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && !item->Parent() && !item->IsVirtual() )
2141 newLinks.push_back( item );
2142 }
2143
2144 if( newLinks.empty() )
2145 return;
2146
2147 auto reachesAnchor = [&]( const JOINT* aStart, bool aIncludeNew, bool aSkipTarget )
2148 {
2149 std::vector<const JOINT*> pending = { aStart };
2150 std::set<const JOINT*> visited;
2151
2152 while( !pending.empty() )
2153 {
2154 const JOINT* joint = pending.back();
2155 pending.pop_back();
2156
2157 if( !joint || joint->Pos() == aJoin || !visited.insert( joint ).second )
2158 continue;
2159
2160 for( const ITEM* item : joint->LinkList() )
2161 {
2162 if( item->IsVirtual() || ( !aIncludeNew && !item->Parent() )
2163 || ( aSkipTarget && item->Parent() == aEndItem->Parent() ) )
2164 continue;
2165
2166 if( item->OfKind( ITEM::SOLID_T | ITEM::VIA_T ) )
2167 return true;
2168
2169 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
2170 {
2171 for( int end = 0; end < 2; ++end )
2172 {
2173 if( item->Anchor( end ) != joint->Pos() )
2174 pending.push_back( aNode->FindJoint( item->Anchor( end ), item ) );
2175 }
2176 }
2177 }
2178 }
2179
2180 return false;
2181 };
2182
2183 bool newRouteAnchored = false;
2184
2185 for( const ITEM* item : newLinks )
2186 {
2187 for( int end = 0; end < 2; ++end )
2188 {
2189 if( item->Anchor( end ) != aJoin
2190 && reachesAnchor( aNode->FindJoint( item->Anchor( end ), item ), true, true ) )
2191 {
2192 newRouteAnchored = true;
2193 break;
2194 }
2195 }
2196
2197 if( newRouteAnchored )
2198 break;
2199 }
2200
2201 if( !newRouteAnchored )
2202 return;
2203
2204 std::vector<std::vector<LINKED_ITEM*>> candidates;
2205 bool hasAnchoredSide = false;
2206 int targetSides = 0;
2207
2208 for( ITEM* item : junction->LinkList() )
2209 {
2210 if( !item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) || item->Parent() != aEndItem->Parent() )
2211 continue;
2212
2213 LINKED_ITEM* link = static_cast<LINKED_ITEM*>( item );
2214 targetSides++;
2215
2216 if( link->Anchor( 0 ) != aJoin && link->Anchor( 1 ) != aJoin )
2217 continue;
2218
2219 VECTOR2I farEnd = link->Anchor( 0 ) == aJoin ? link->Anchor( 1 ) : link->Anchor( 0 );
2220
2221 if( reachesAnchor( aNode->FindJoint( farEnd, link ), false, false ) )
2222 {
2223 hasAnchoredSide = true;
2224 continue;
2225 }
2226
2227 VECTOR2I from = aJoin;
2228 std::vector<LINKED_ITEM*> branch;
2229 std::set<LINKED_ITEM*> seen;
2230
2231 while( link && link->Parent() && !link->IsLocked() && !link->IsVirtual() && seen.insert( link ).second )
2232 {
2233 if( link->Anchor( 0 ) != from && link->Anchor( 1 ) != from )
2234 break;
2235
2236 if( Router()->GetInterface()->TouchesCopperZone( link ) )
2237 {
2238 hasAnchoredSide = true;
2239 break;
2240 }
2241
2242 branch.push_back( link );
2243 farEnd = link->Anchor( 0 ) == from ? link->Anchor( 1 ) : link->Anchor( 0 );
2244
2245 const JOINT* end = aNode->FindJoint( farEnd, link );
2246
2247 if( !end )
2248 break;
2249
2250 if( end->LinkCount() == 1 )
2251 {
2252 candidates.push_back( std::move( branch ) );
2253 break;
2254 }
2255
2256 if( end->LinkCount() != 2 )
2257 break;
2258
2259 LINKED_ITEM* next = nullptr;
2260
2261 for( ITEM* adjacent : end->LinkList() )
2262 {
2263 if( adjacent != link && adjacent->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
2264 next = static_cast<LINKED_ITEM*>( adjacent );
2265 }
2266
2267 from = farEnd;
2268 link = next;
2269 }
2270 }
2271
2272 // Loop removal may have consumed the anchored half before this route is fixed.
2273 if( ( targetSides == 2 && hasAnchoredSide ) || targetSides == 1 )
2274 {
2275 for( const std::vector<LINKED_ITEM*>& branch : candidates )
2276 {
2277 for( LINKED_ITEM* segment : branch )
2278 aNode->Remove( segment );
2279 }
2280 }
2281}
2282
2283
2284bool PLACEMENT_ALGO::removeLoops( NODE* aNode, LINE& aLatest )
2285{
2286 if( !aLatest.SegmentCount() )
2287 return false;
2288
2289 if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CLastPoint() )
2290 return false;
2291
2292 std::set<LINKED_ITEM *> toErase;
2293 aLatest.ClearLinks();
2294 aNode->Add( aLatest, true );
2295
2296 for( int s = 0; s < aLatest.LinkCount(); s++ )
2297 {
2298 LINKED_ITEM* seg = aLatest.GetLink(s);
2299 LINE ourLine = aNode->AssembleLine( seg );
2300 JOINT a, b;
2301 std::vector<LINE> lines;
2302
2303 aNode->FindLineEnds( ourLine, a, b );
2304
2305 if( a == b )
2306 aNode->FindLineEnds( aLatest, a, b );
2307
2308 aNode->FindLinesBetweenJoints( a, b, lines );
2309
2310 int removedCount = 0;
2311 int total = 0;
2312
2313 for( LINE& line : lines )
2314 {
2315 total++;
2316
2317 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
2318 {
2319 // Don't remove locked tracks
2320 bool hasLockedSegment = false;
2321 for( LINKED_ITEM* ss : line.Links() )
2322 {
2323 if( ss->IsLocked() )
2324 {
2325 hasLockedSegment = true;
2326 break;
2327}
2328 }
2329
2330 if( !hasLockedSegment )
2331 {
2332 for( LINKED_ITEM* ss : line.Links() )
2333 toErase.insert( ss );
2334
2335 removedCount++;
2336 }
2337 }
2338 }
2339
2340 PNS_DBG( Dbg(), Message, wxString::Format( "total segs removed: %d/%d", removedCount, total ) );
2341 }
2342
2343 for( LINKED_ITEM* s : toErase )
2344 aNode->Remove( s );
2345
2346 aNode->Remove( aLatest );
2347
2348
2349 return true;
2350}
2351
2352
2353}
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition board_item.h:99
constexpr Vec NearestPoint(const Vec &aPoint) const
Return the point in this rect that is closest to the provided point.
Definition box2.h:802
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.
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.
KICAD_T Type() const
Returns the type of object.
Definition eda_item.h:110
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
void SetLogger(LOGGER *aLogger)
virtual LOGGER * Logger()
Return the logger object, allowing to dump geometry to a file.
ROUTER * Router() const
Return the instance of our router.
ROUTER * m_router
ROUTING_SETTINGS & Settings() const
Return current router settings.
DEBUG_DECORATOR * Dbg() const
void SetWidth(int aWidth) override
Definition pns_arc.h:85
FIXED_TAIL(int aLineCount=1)
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:96
Base class for PNS router board items.
Definition pns_item.h:98
BOARD_ITEM * Parent() const
Definition pns_item.h:199
void SetSourceItem(BOARD_ITEM *aSourceItem)
Definition pns_item.h:201
virtual NET_HANDLE Net() const
Definition pns_item.h:210
PnsKind Kind() const
Return the type (kind) of the item.
Definition pns_item.h:173
void SetNet(NET_HANDLE aNet)
Definition pns_item.h:209
BOARD_ITEM * GetSourceItem() const
Definition pns_item.h:202
void SetLayer(int aLayer)
Definition pns_item.h:215
bool OfKind(int aKindMask) const
Definition pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:272
bool IsLocked() const
Definition pns_item.h:282
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
const std::vector< ITEM * > & LinkList() const
Definition pns_joint.h:307
int LinkCount(int aMask=-1) const
Definition pns_joint.h:322
bool IsLineCorner(bool aAllowLockedSegs=false) const
Check if a joint connects two segments of the same net, layer, and width.
Definition pns_joint.h:102
const ITEM_SET & CLinks() const
Definition pns_joint.h:312
const VECTOR2I & Pos() const
Definition pns_joint.h:297
bool mergeHead()
Moves "established" segments from the head to the tail if certain conditions are met.
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
Force the router to place a straight 90/45 degree trace (with the end as near to the cursor as possib...
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.
NODE * m_currentNode
Current world state.
bool buildInitialLine(const VECTOR2I &aP, LINE &aHead, PNS::PNS_MODE aMode, bool aForceNoVia=false)
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
VECTOR2I m_fixStart
start point of the last 'fix'
bool rhMarkObstacles(const VECTOR2I &aP, LINE &aNewHead, LINE &aNewTail)
Route step mark obstacles mode.
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 rhWalkBase(const VECTOR2I &aP, LINE &aWalkLine, int aCollisionMask, PNS::PNS_MODE aMode, bool &aViaOk)
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)
Route step walk around mode.
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 CommitPlacement() override
VECTOR2I m_p_start
current routing start (end of tail, beginning of head)
void GetModifiedNets(std::vector< NET_HANDLE > &aNets) const override
Return the nets of all currently routed trace(s)
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 removeAntennas(NODE *aNode, const ITEM *aEndItem, const VECTOR2I &aJoin)
DIRECTION_45 m_direction
current routing direction
void initPlacement()
Initialize placement of a new line with given parameters.
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
const VECTOR2I & CPoint(int aIdx) const
Return the aIdx-th point of the line.
Definition pns_line.h:157
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assign a shape to the line (a polyline/line chain).
Definition pns_line.h:138
const SHAPE_LINE_CHAIN & CLine() const
Definition pns_line.h:149
const VECTOR2I & CLastPoint() const
Definition pns_line.h:158
void RemoveVia()
SHAPE_LINE_CHAIN & Line()
Modifiable accessor to the underlying shape.
Definition pns_line.h:148
void AppendVia(const VIA &aVia)
VIA & Via()
Definition pns_line.h:212
int SegmentCount() const
Definition pns_line.h:151
int PointCount() const
Definition pns_line.h:152
bool EndsWithVia() const
Definition pns_line.h:204
const SEG CSegment(int aIdx) const
Definition pns_line.h:159
int Width() const
Return line width.
Definition pns_line.h:169
void Clear()
Keep the router "world" - i.e.
Definition pns_node.h:274
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition pns_node.cpp:174
int FindLinesBetweenJoints(const JOINT &aA, const JOINT &aB, std::vector< LINE > &aLines)
Find all lines between a pair of joints. Used by the loop removal procedure.
std::vector< ITEM * > ITEM_VECTOR
Definition pns_node.h:285
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.
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:510
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.
std::optional< OBSTACLE > OPT_OBSTACLE
Definition pns_node.h:284
int Depth() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition pns_node.h:335
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Find the joints corresponding to the ends of line aLine.
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition pns_node.cpp:765
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false, bool aAllowSegmentSizeMismatch=true)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
void KillChildren()
Destroy all child nodes. Applicable only to the root node.
void Remove(ARC *aArc)
Remove an item from this branch.
Perform various optimizations of the lines being routed, attempting to make the lines shorter and les...
void SetCollisionMask(int aMask)
void SetEffortLevel(int aEffort)
static bool Optimize(LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I &aV=VECTOR2I(0, 0))
A quick shortcut to optimize a line without creating and setting up an optimizer.
@ SMART_PADS
Reroute pad exits.
@ FANOUT_CLEANUP
Simplify pad-pad and pad-via connections if possible.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
@ 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:72
virtual bool removeLoops(NODE *aNode, LINE &aLatest)
PLACEMENT_ALGO(ROUTER *aRouter)
virtual bool simplifyNewLine(NODE *aNode, LINKED_ITEM *aLatest)
Assemble a line starting from segment or arc aLatest, removes collinear segments and redundant vertic...
PNS_LAYER_RANGE GetViaLayerRange(const SIZES_SETTINGS &aSizes) const
Return the layer span a via placed with aSizes occupies.
Definition pns_router.h:156
virtual NET_HANDLE GetOrphanedNetHandle()=0
ROUTER_IFACE * GetInterface() const
Definition pns_router.h:266
void CommitRouting()
NODE * GetWorld() const
Definition pns_router.h:212
double WalkaroundHugLengthThreshold() const
PNS_MODE Mode() const
Return the routing mode.
DIRECTION_45::CORNER_MODE GetCornerMode() const
void SetWidth(int aWidth) override
Definition pns_segment.h:91
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const VECTOR2I & Pos() const
Definition pns_via.h:206
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
Definition pns_via.cpp:159
void SetPos(const VECTOR2I &aPos)
Definition pns_via.h:208
void SetIterationLimit(const int aIterLimit)
void SetAllowedPolicies(std::vector< WALK_POLICY > aPolicies, bool aAnyCompletePolicyIsSuccess=false)
void SetSolidsOnly(bool aSolidsOnly)
STATUS Route(const LINE &aInitialPath, LINE &aWalkPath, bool aOptimize=true)
void SetItemMask(int aMask)
Represent a contiguous set of PCB layers.
Definition seg.h:38
VECTOR2I A
Definition seg.h:45
VECTOR2I B
Definition seg.h:46
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition seg.cpp:599
int Length() const
Return the length (this).
Definition seg.h:361
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition seg.h:283
bool Overlaps(const SEG &aSeg) const
Definition seg.h:298
bool Contains(const SEG &aSeg) const
Definition seg.h:342
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:651
SEG Reversed() const
Definition seg.h:391
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...
int Intersect(const SEG &aSeg, std::vector< INTERSECTION > &aIp) const
Find all intersection points between our line chain and the segment aSeg.
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 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.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
int SegmentCount() const
Return the number of segments in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the 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.
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 std::vector< VECTOR2I > & CPoints() const
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:59
@ WHITE
Definition color4d.h:44
@ BLUE
Definition color4d.h:52
@ MAGENTA
Definition color4d.h:56
@ GREEN
Definition color4d.h:53
@ CYAN
Definition color4d.h:54
@ LIGHTCYAN
Definition color4d.h:60
@ RED
Definition color4d.h:55
@ SEGMENT
Definition eda_shape.h:57
std::string source
Push and Shove diff pair dimensions (gap) settings dialog.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Snaps the point aP to segment aSeg.
PNS_MODE
Routing modes.
@ 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:348
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
CITER next(CITER it)
Definition ptree.cpp:120
@ VIA
Normal via.
std::vector< FIX_POINT > pts
LINE lines[MaxWalkPolicies]
STATUS status[MaxWalkPolicies]
Represent an intersection between two line segments.
static std::vector< int > candidates(const SEGMENT_INDEX &aIndex, const SEG &aQuery, int aPadding)
VECTOR2I end
int clearance
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition typeinfo.h:79
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708