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