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