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