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
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 )
79 : m_sizes.GetLayerTop();
80 int end = m_sizes.ViaType() == VIATYPE::THROUGH ? iface->GetPNSLayerFromBoardLayer( B_Cu )
81 : m_sizes.GetLayerBottom();
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 )
97 m_head.RemoveVia();
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.CLastPoint() )
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
299 if( m_currentNode->CheckColliding( &tmp, ITEM::ANY_T ) )
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.CLastPoint() )
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 = std::move( 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.CLastPoint();
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().CLastPoint();
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.CLastPoint() ).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.CLastPoint() ).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.CLastPoint();
709 }
710 else if( validCcw )
711 {
712 walkFull.SetShape( l_ccw );
713 walkP = l_ccw.CLastPoint();
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.CLastPoint() );
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 )
773 && !m_mouseTrailTracer.IsManuallyForced() )
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.CLastPoint(), RED, 1000000, wxString::Format( "VIA" ) );
804
805 aNewHead.AppendVia( makeVia( aNewHead.CLastPoint() ) );
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 {
851 NODE::OPT_OBSTACLE obs = m_currentNode->NearestObstacle( &m_head );
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.CLastPoint() ) )
885 {
886 l2.Line().Split( aOldTail.CLastPoint() );
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.CLastPoint() ) );
957 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-new-via" );
958
959 }
960
961 m_shove->ClearHeads();
962 m_shove->AddHeads( newHead, SHOVE::SHP_SHOVE );
963 bool shoveOk = m_shove->Run() == SHOVE::SH_OK;
964
965 m_currentNode = m_shove->CurrentNode();
966
967 int effort = 0;
968
969 switch( Settings().OptimizerEffort() )
970 {
971 case OE_LOW:
972 effort = 0;
973 break;
974
975 case OE_MEDIUM:
976 case OE_FULL:
978 break;
979 }
980
982
983 // Smart Pads is incompatible with 90-degree mode for now
984 if( Settings().SmartPads()
985 && ( cornerMode == DIRECTION_45::MITERED_45 || cornerMode == DIRECTION_45::ROUNDED_45 )
986 && !m_mouseTrailTracer.IsManuallyForced() )
987 {
988 effort |= OPTIMIZER::SMART_PADS;
989 }
990
991 if( shoveOk )
992 {
993 if( m_shove->HeadsModified() )
994 newHead = m_shove->GetModifiedHead( 0 );
995
996 if( newHead.EndsWithVia() )
997 {
998 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-via-preopt" );
999 PNS_DBG( Dbg(), AddPoint, newHead.Via().Pos(), GREEN, 1000000, "shove-via-postopt" );
1000 }
1001
1002 if( ! splitHeadTail( newHead, m_tail, aNewHead, aNewTail ) )
1003 return false;
1004
1005 if( newHead.EndsWithVia() )
1006 aNewHead.AppendVia( newHead.Via() );
1007
1008 OPTIMIZER::Optimize( &aNewHead, effort, m_currentNode );
1009 PNS_DBG( Dbg(), AddItem, aNewHead.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
1047 if( !m_mouseTrailTracer.IsManuallyForced() &&
1049 {
1050 if( linetmp.SegmentCount() < 1 )
1051 return false;
1052
1053 m_head = linetmp;
1054 m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
1055 m_tail.Line().Clear();
1056
1057 return true;
1058 }
1059
1060 SHAPE_LINE_CHAIN& head = m_head.Line();
1061 SHAPE_LINE_CHAIN& tail = m_tail.Line();
1062
1063 int tailLookbackSegments = 3;
1064
1065 //if(m_currentMode() == RM_Walkaround)
1066 // tailLookbackSegments = 10000;
1067
1068 int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
1069
1070 if( tail.ShapeCount() < 3 )
1071 return false;
1072
1073 // assemble TailLookbackSegments tail segments with the current head
1074 SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
1075
1076 int end = std::min(2, head.PointCount() - 1 );
1077
1078 opt_line.Append( head.Slice( 0, end ) );
1079
1080 LINE new_head( m_tail, opt_line );
1081
1082 // and see if it could be made simpler by merging obtuse/collnear segments.
1083 // If so, replace the (threshold) last tail points and the head with
1084 // the optimized line
1085
1086 PNS_DBG( Dbg(), AddItem, &new_head, LIGHTCYAN, 10000, wxT( "ht-newline" ) );
1087
1089 {
1090 LINE tmp( m_tail, opt_line );
1091
1092 head.Clear();
1093 tail.Replace( -threshold, -1, new_head.CLine() );
1094 tail.Simplify();
1095
1096 m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
1097
1098 return true;
1099 }
1100
1101 return false;
1102}
1103
1105{
1106 if( tail.CLine().PointCount() )
1107 m_p_start = tail.CLine().CLastPoint();
1108 else
1110}
1111
1113{
1114 bool fail = false;
1115 bool go_back = false;
1116
1117 int i, n_iter = 1;
1118
1119
1120 PNS_DBG( Dbg(), Message, wxString::Format( "routeStep: direction: %s head: %d, tail: %d shapes" ,
1121 m_direction.Format(),
1122 m_head.ShapeCount(),
1123 m_tail.ShapeCount() ) );
1124
1125 PNS_DBG( Dbg(), BeginGroup, wxT( "route-step" ), 0 );
1126
1127 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-init" ) );
1128 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-init" ) );
1129
1130 for( i = 0; i < n_iter; i++ )
1131 {
1132 LINE prevTail( m_tail );
1133 LINE prevHead( m_head );
1134 LINE newHead, newTail;
1135
1136 if( !go_back && Settings().FollowMouse() )
1137 reduceTail( aP );
1138
1139 PNS_DBG( Dbg(), AddItem, &m_tail, WHITE, 10000, wxT( "tail-after-reduce" ) );
1140 PNS_DBG( Dbg(), AddItem, &m_head, GREEN, 10000, wxT( "head-after-reduce" ) );
1141
1142 go_back = false;
1143
1145
1146 if( !routeHead( aP, newHead, newTail ) )
1147 {
1148 m_tail = 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 {
1156 m_tail.Line().Append( m_p_start );
1157 m_tail.Line().Append( m_p_start, true );
1158 }
1159
1160 fail = true;
1161 }
1162
1164
1165 PNS_DBG( Dbg(), AddItem, &newHead, LIGHTGREEN, 100000, wxString::Format( "new_head [fail: %d]", fail?1:0 ) );
1166
1167 if( fail )
1168 break;
1169
1170 PNS_DBG( Dbg(), Message, wxString::Format( "N VIA H %d T %d\n", m_head.EndsWithVia() ? 1 : 0, m_tail.EndsWithVia() ? 1 : 0 ) );
1171
1172 m_head = 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.CLastPoint() == aP;
1232}
1233
1234
1236{
1237 SHAPE_LINE_CHAIN l( m_tail.CLine() );
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.
1269 if( m_mouseTrailTracer.IsManuallyForced() == false && m_currentTrace.SegmentCount() > 0 )
1270 {
1271 DIRECTION_45 firstDirection( m_currentTrace.CSegment( 0 ) );
1272
1273 m_mouseTrailTracer.SetDefaultDirections( firstDirection, DIRECTION_45::UNDEFINED );
1274 }
1275
1276 m_mouseTrailTracer.FlipPosture();
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;
1367 m_mouseTrailTracer.Clear();
1368 m_head.Line().Clear();
1369 m_tail.Line().Clear();
1370 m_head.RemoveVia();
1371 m_tail.RemoveVia();
1372 m_head.SetLayer( m_currentLayer );
1373 m_tail.SetLayer( m_currentLayer );
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;
1392 m_fixedTail.Clear();
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
1425 m_mouseTrailTracer.Clear();
1426 m_mouseTrailTracer.AddTrailPoint( aP );
1427 m_mouseTrailTracer.SetTolerance( m_head.Width() );
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();
1450 m_head.SetNet( m_currentNet );
1451 m_tail.SetNet( m_currentNet );
1452 m_head.SetLayer( m_currentLayer );
1453 m_tail.SetLayer( m_currentLayer );
1454 m_head.SetWidth( m_sizes.TrackWidth() );
1455 m_tail.SetWidth( m_sizes.TrackWidth() );
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 VECTOR2I splitPoint = current.PointCount() ? current.CLine().CLastPoint() : m_p_start;
1505
1506 if( reachesEnd && aEndItem && current.SegmentCount() && aEndItem->OfKind( ITEM::SEGMENT_T ) )
1507 {
1508 const SEG lastSeg = current.CLine().CSegment( current.SegmentCount() - 1 );
1509 const SEG targetSeg = static_cast<SEGMENT*>( aEndItem )->Seg();
1510
1511 if( lastSeg.Collinear( targetSeg ) && targetSeg.Overlaps( lastSeg ) )
1512 {
1513 splitPoint = targetSeg.NearestPoint( lastSeg.A );
1514 current.Line().SetPoint( current.PointCount() - 1, splitPoint );
1515 m_head.Line().SetPoint( m_head.PointCount() - 1, splitPoint );
1516 }
1517 }
1518
1519 if( !current.PointCount() )
1521 else
1522 m_currentEnd = splitPoint;
1523
1524 NODE* latestNode = m_currentNode;
1525 m_lastNode = latestNode->Branch();
1526
1527 if( reachesEnd
1528 && eiDepth >= 0
1529 && aEndItem && latestNode->Depth() >= eiDepth
1530 && current.SegmentCount() )
1531 {
1532 if ( aEndItem->Net() == m_currentNet )
1533 SplitAdjacentSegments( m_lastNode, aEndItem, splitPoint );
1534
1535 if( Settings().RemoveLoops() )
1536 removeLoops( m_lastNode, current );
1537 }
1538
1540 m_mouseTrailTracer.AddTrailPoint( aP );
1541 return true;
1542}
1543
1544
1545bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1546{
1547 bool fixAll = Settings().GetFixAllSegments();
1548 bool realEnd = false;
1549
1550 LINE pl = Trace();
1551
1552 if( Settings().Mode() == RM_MarkObstacles )
1553 {
1554 // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1555 // user has more responsibility and authority.
1556
1557 if( aEndItem )
1558 {
1559 // The user has indicated a connection should be made. If either the trace or
1560 // endItem is net-less, then allow the connection by adopting the net of the other.
1561 if( m_router->GetInterface()->GetNetCode( m_currentNet ) <= 0 )
1562 {
1563 m_currentNet = aEndItem->Net();
1564 pl.SetNet( m_currentNet );
1565 }
1566 else if( m_router->GetInterface()->GetNetCode( aEndItem->Net() ) <= 0 )
1567 {
1568 aEndItem->SetNet( m_currentNet );
1569 }
1570 }
1571 }
1572
1573 // Collisions still prevent fixing unless "Allow DRC violations" is checked
1574 // Note that collisions can occur even in walk/shove modes if the beginning of the trace
1575 // collides (for example if the starting track width is too high).
1576
1577 if( !Settings().AllowDRCViolations() )
1578 {
1579 NODE* checkNode = ( Settings().Mode() == RM_Shove ) ? m_shove->CurrentNode() : m_world;
1580 std::optional<OBSTACLE> obs = checkNode->CheckColliding( &pl );
1581
1582 if( obs )
1583 {
1584 // TODO: Determine why the shove node sometimes reports collisions against shoved objects.
1585 // For now, to work around this issue, we consider only solids in shove mode.
1586 if( Settings().Mode() != RM_Shove || obs->m_item->OfKind( ITEM::SOLID_T ) )
1587 return false;
1588 }
1589 }
1590
1591 const SHAPE_LINE_CHAIN& l = pl.CLine();
1592
1593 if( !l.SegmentCount() )
1594 {
1595 if( m_lastNode )
1596 {
1597 // Do a final optimization to the stored state
1598 NODE::ITEM_VECTOR removed, added;
1599 m_lastNode->GetUpdatedItems( removed, added );
1600
1601 if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1602 simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1603 }
1604
1605 // Nothing to commit if we have an empty line
1606 if( !pl.EndsWithVia() )
1607 return false;
1608
1611 if( m_lastNode )
1612 {
1613 auto newVia = Clone( pl.Via() );
1614 newVia->ResetUid();
1615 m_lastNode->Add( std::move( newVia ) );
1616 m_shove->AddLockedSpringbackNode( m_lastNode );
1617 }
1618
1619 m_currentNode = nullptr;
1620
1621 m_idle = true;
1622 m_placementCorrect = true;
1623 return true;
1624 }
1625
1626 VECTOR2I p_pre_last = l.CLastPoint();
1627 const VECTOR2I p_last = l.CLastPoint();
1628
1629 if( l.PointCount() > 2 )
1630 p_pre_last = l.CPoints()[ l.PointCount() - 2 ];
1631
1632 if( aEndItem && m_currentNet && m_currentNet == aEndItem->Net() )
1633 realEnd = true;
1634
1635 if( aForceFinish )
1636 realEnd = true;
1637
1638 // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1639 // so if we are, act as though we are in fix-all mode.
1640 if( !fixAll && l.ArcCount() )
1641 fixAll = true;
1642
1643 // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1644 SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1645 DIRECTION_45 d_last( lastDirSeg );
1646
1647 int lastV;
1648
1649 if( realEnd || m_placingVia || fixAll )
1650 lastV = l.SegmentCount();
1651 else
1652 lastV = std::max( 1, l.SegmentCount() - 1 );
1653
1654 ARC arc;
1655 SEGMENT seg;
1656 LINKED_ITEM* lastItem = nullptr;
1657 int lastArc = -1;
1658
1659 for( int i = 0; i < lastV; i++ )
1660 {
1661 ssize_t arcIndex = l.ArcIndex( i );
1662
1663 if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1664 {
1665 seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1666 seg.SetWidth( pl.Width() );
1667 seg.SetLayer( m_currentLayer );
1668
1669 std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1670 lastItem = sp.get();
1671
1672 if( !m_lastNode->Add( std::move( sp ) ) )
1673 lastItem = nullptr;
1674 }
1675 else
1676 {
1677 if( arcIndex == lastArc )
1678 continue;
1679
1680 arc = ARC( l.Arc( arcIndex ), m_currentNet );
1681 arc.SetWidth( pl.Width() );
1682 arc.SetLayer( m_currentLayer );
1683
1684 std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1685 lastItem = ap.get();
1686
1687 if( !m_lastNode->Add( std::move( ap ) ) )
1688 lastItem = nullptr;
1689
1690 lastArc = arcIndex;
1691 }
1692 }
1693
1694 if( pl.EndsWithVia() )
1695 {
1696 auto newVia = Clone( pl.Via() );
1697 newVia->ResetUid();
1698 m_lastNode->Add( std::move( newVia ) );
1699 }
1700
1701
1702 if( realEnd && lastItem )
1703 simplifyNewLine( m_lastNode, lastItem );
1704
1705 if( !realEnd )
1706 {
1707 setInitialDirection( d_last );
1708 m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1709
1711
1713 m_startItem = nullptr;
1714 m_placingVia = false;
1716
1719
1720 m_head.Line().Clear();
1721 m_tail.Line().Clear();
1722 m_head.RemoveVia();
1723 m_tail.RemoveVia();
1725 m_lastNode = m_lastNode->Branch();
1726
1727 m_shove->AddLockedSpringbackNode( m_currentNode );
1728
1729 DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1730
1731 m_mouseTrailTracer.Clear();
1732 m_mouseTrailTracer.SetTolerance( m_head.Width() );
1733 m_mouseTrailTracer.AddTrailPoint( m_currentStart );
1734 m_mouseTrailTracer.SetDefaultDirections( lastSegDir, DIRECTION_45::UNDEFINED );
1735
1736 m_placementCorrect = true;
1737 }
1738 else
1739 {
1740 m_shove->AddLockedSpringbackNode( m_lastNode );
1741 m_placementCorrect = true;
1742 m_idle = true;
1743 }
1744
1745 return realEnd;
1746}
1747
1748
1749std::optional<VECTOR2I> LINE_PLACER::UnfixRoute()
1750{
1752 std::optional<VECTOR2I> ret;
1753
1754 if ( !m_fixedTail.PopStage( st ) )
1755 return ret;
1756
1757 if( m_head.Line().PointCount() )
1758 ret = m_head.Line().CPoint( 0 );
1759
1760 m_head.Line().Clear();
1761 m_tail.Line().Clear();
1762 m_startItem = nullptr;
1763 m_p_start = st.pts[0].p;
1765 m_direction = st.pts[0].direction;
1766 m_placingVia = st.pts[0].placingVias;
1767 m_currentNode = st.commit;
1768 m_currentLayer = st.pts[0].layer;
1770 m_head.SetLayer( m_currentLayer );
1771 m_tail.SetLayer( m_currentLayer );
1772 m_head.RemoveVia();
1773 m_tail.RemoveVia();
1774
1775 m_mouseTrailTracer.Clear();
1776 m_mouseTrailTracer.SetDefaultDirections( m_initial_direction, m_direction );
1777 m_mouseTrailTracer.AddTrailPoint( m_p_start );
1778
1779 m_shove->RewindSpringbackTo( m_currentNode );
1780 m_shove->UnlockSpringbackNode( m_currentNode );
1781
1782 if( Settings().Mode() == PNS::RM_Shove )
1783 {
1784 m_currentNode = m_shove->CurrentNode();
1785 m_currentNode->KillChildren();
1786 }
1787
1788 m_lastNode = m_currentNode->Branch();
1789
1790 return ret;
1791}
1792
1793
1795{
1796 return m_placementCorrect || m_fixedTail.StageCount() > 1;
1797}
1798
1799
1801{
1802 if( Settings().Mode() == PNS::RM_Shove )
1803 {
1804 m_shove->RewindToLastLockedNode();
1805 m_lastNode = m_shove->CurrentNode();
1806 m_lastNode->KillChildren();
1807 }
1808
1809 if( m_lastNode )
1811
1812 m_lastNode = nullptr;
1813 m_currentNode = nullptr;
1814 return true;
1815}
1816
1817
1818void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1819{
1820 if( !aLatest.SegmentCount() )
1821 return;
1822
1823 if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CLastPoint() )
1824 return;
1825
1826 std::set<LINKED_ITEM *> toErase;
1827 aLatest.ClearLinks();
1828 aNode->Add( aLatest, true );
1829
1830 for( int s = 0; s < aLatest.LinkCount(); s++ )
1831 {
1832 LINKED_ITEM* seg = aLatest.GetLink(s);
1833 LINE ourLine = aNode->AssembleLine( seg );
1834 JOINT a, b;
1835 std::vector<LINE> lines;
1836
1837 aNode->FindLineEnds( ourLine, a, b );
1838
1839 if( a == b )
1840 aNode->FindLineEnds( aLatest, a, b );
1841
1842 aNode->FindLinesBetweenJoints( a, b, lines );
1843
1844 int removedCount = 0;
1845 int total = 0;
1846
1847 for( LINE& line : lines )
1848 {
1849 total++;
1850
1851 if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1852 {
1853 for( LINKED_ITEM* ss : line.Links() )
1854 toErase.insert( ss );
1855
1856 removedCount++;
1857 }
1858 }
1859
1860 PNS_DBG( Dbg(), Message, wxString::Format( "total segs removed: %d/%d", removedCount, total ) );
1861 }
1862
1863 for( LINKED_ITEM* s : toErase )
1864 aNode->Remove( s );
1865
1866 aNode->Remove( aLatest );
1867}
1868
1869
1871{
1872 wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1873
1874 // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1875 // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1876 // of the line and won't get cleaned up by the optimizer.
1877 NODE::ITEM_VECTOR removed, added;
1878 aNode->GetUpdatedItems( removed, added );
1879
1880 std::set<ITEM*> cleanup;
1881
1882 auto processJoint =
1883 [&]( const JOINT* aJoint, ITEM* aItem )
1884 {
1885 if( !aJoint || aJoint->IsLineCorner() )
1886 return;
1887
1888 SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1889
1890 NODE::ITEM_VECTOR toRemove;
1891
1892 for( ITEM* neighbor : aJoint->CLinks().CItems() )
1893 {
1894 if( neighbor == aItem
1895 || !neighbor->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
1896 || !neighbor->LayersOverlap( aItem ) )
1897 {
1898 continue;
1899 }
1900
1901 if( static_cast<const SEGMENT*>( neighbor )->Width()
1902 != static_cast<const SEGMENT*>( aItem )->Width() )
1903 {
1904 continue;
1905 }
1906
1907 const SEG& testSeg = static_cast<const SEGMENT*>( neighbor )->Seg();
1908
1909 if( refSeg.Contains( testSeg ) )
1910 {
1911 const JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1912 const JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1913
1914 if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1915 ( nB == aJoint && nA->LinkCount() == 1 ) )
1916 {
1917 cleanup.insert( neighbor );
1918 }
1919 }
1920 else if( testSeg.Contains( refSeg ) )
1921 {
1922 const JOINT* aA = aNode->FindJoint( aItem->Anchor( 0 ), aItem );
1923 const JOINT* aB = aNode->FindJoint( aItem->Anchor( 1 ), aItem );
1924
1925 if( ( aA == aJoint && aB->LinkCount() == 1 ) ||
1926 ( aB == aJoint && aA->LinkCount() == 1 ) )
1927 {
1928 cleanup.insert( aItem );
1929 return;
1930 }
1931 }
1932 }
1933 };
1934
1935 for( ITEM* item : added )
1936 {
1937 if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1938 continue;
1939
1940 const JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1941 const JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1942
1943 processJoint( jA, item );
1944 processJoint( jB, item );
1945 }
1946
1947 for( ITEM* seg : cleanup )
1948 aNode->Remove( seg );
1949
1950 // And now we can proceed with assembling the final line and optimizing it.
1951
1952 LINE l_orig = aNode->AssembleLine( aLatest, nullptr, false, false, false );
1953 LINE l( l_orig );
1954
1955 bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1956
1957 SHAPE_LINE_CHAIN simplified( l.CLine() );
1958
1959 simplified.Simplify();
1960
1961 if( optimized || simplified.PointCount() != l.PointCount() )
1962 {
1963 aNode->Remove( l_orig );
1964 l.SetShape( simplified );
1965 aNode->Add( l );
1966 PNS_DBG( Dbg(), AddItem, &l, RED, 100000, wxT("simplified"));
1967 }
1968}
1969
1970
1972{
1973 m_sizes = aSizes;
1974
1975 if( !m_idle )
1976 {
1977 // If the track width continues from an existing track, we don't want to change the width.
1978 // Disallow changing width after the first segment has been fixed because we don't want to
1979 // go back and rip up tracks or allow DRC errors
1980 if( m_sizes.TrackWidthIsExplicit()
1981 || ( !HasPlacedAnything() && ( !m_startItem || m_startItem->Kind() != ITEM::SEGMENT_T ) ) )
1982 {
1983 m_head.SetWidth( m_sizes.TrackWidth() );
1984 m_tail.SetWidth( m_sizes.TrackWidth() );
1985 m_currentTrace.SetWidth( m_sizes.TrackWidth() );
1986 }
1987
1988 if( m_head.EndsWithVia() )
1989 {
1990 m_head.SetViaDiameter( m_sizes.ViaDiameter() );
1991 m_head.SetViaDrill( m_sizes.ViaDrill() );
1992 }
1993 }
1994}
1995
1996
1998{
1999 LINE current = Trace();
2000 SHAPE_LINE_CHAIN ratLine;
2001 TOPOLOGY topo( m_lastNode );
2002
2003 if( topo.LeadingRatLine( &current, ratLine ) )
2004 m_router->GetInterface()->DisplayRatline( ratLine, m_currentNet );
2005}
2006
2007
2008void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
2009{
2010 m_orthoMode = aOrthoMode;
2011}
2012
2013
2014bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, PNS::PNS_MODE aMode, bool aForceNoVia )
2015{
2017 DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
2018
2019 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "buildInitialLine: m_direction %s, guessedDir %s, tail points %d" ),
2020 m_direction.Format(), guessedDir.Format(), m_tail.PointCount() ) );
2021
2023 // Rounded corners don't make sense when routing orthogonally (single track at a time)
2024 if( m_orthoMode )
2026
2027 PNS_DBG( Dbg(), AddPoint, m_p_start, WHITE, 10000, wxT( "pstart [buildInitial]" ) );
2028
2029
2030 if( m_p_start == aP )
2031 {
2032 l.Clear();
2033 }
2034 else
2035 {
2036 if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
2037 {
2038 l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
2039 }
2040 else
2041 {
2042 if( !m_tail.PointCount() )
2043 l = guessedDir.BuildInitialTrace( m_p_start, aP, false, cornerMode );
2044 else
2045 l = m_direction.BuildInitialTrace( m_p_start, aP, false, cornerMode );
2046 }
2047
2048 if( l.SegmentCount() > 1 && m_orthoMode )
2049 {
2050 VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CLastPoint() );
2051
2052 l.Remove( -1, -1 );
2053 l.SetPoint( 1, newLast );
2054 }
2055 }
2056
2057 aHead.SetLayer( m_currentLayer );
2058 aHead.SetShape( l );
2059
2060 PNS_DBG( Dbg(), AddItem, &aHead, CYAN, 10000, wxT( "initial-trace" ) );
2061
2062
2063 if( !m_placingVia || aForceNoVia )
2064 return true;
2065
2066 VIA v( makeVia( aP ) );
2067 v.SetNet( aHead.Net() );
2068
2069 if( aMode == RM_MarkObstacles )
2070 {
2071 aHead.AppendVia( v );
2072 return true;
2073 }
2074
2075 const int collMask = ( aMode == RM_Walkaround ) ? ITEM::ANY_T : ITEM::SOLID_T;
2076 const int iterLimit = Settings().ViaForcePropIterationLimit();
2077
2078 for( int attempt = 0; attempt < 2; attempt++)
2079 {
2080 VECTOR2I lead = aP - m_p_start;
2081 VECTOR2I force;
2082
2083 if( attempt == 1 && m_last_p_end.has_value() )
2084 lead = aP - m_last_p_end.value();
2085
2086 if( v.PushoutForce( m_currentNode, lead, force, collMask, iterLimit ) )
2087 {
2088 SHAPE_LINE_CHAIN line = guessedDir.BuildInitialTrace( m_p_start, aP + force, false, cornerMode );
2089 aHead = LINE( aHead, line );
2090
2091 v.SetPos( v.Pos() + force );
2092
2093 aHead.AppendVia( v );
2094
2095 PNS_DBG( Dbg(), AddPoint, v.Pos(), GREEN, 1000000, "via-force-coll-2" );
2096
2097 return true;
2098 }
2099 }
2100
2101 return false; // via placement unsuccessful
2102}
2103
2104
2105void LINE_PLACER::GetModifiedNets( std::vector<NET_HANDLE>& aNets ) const
2106{
2107 aNets.push_back( m_currentNet );
2108}
2109
2110
2112{
2113 m_world->KillChildren();
2114 m_lastNode = nullptr;
2115 return true;
2116}
2117
2118
2119FIXED_TAIL::FIXED_TAIL( int aLineCount )
2120{
2121
2122}
2123
2124
2126{
2127
2128}
2129
2130
2132{
2133 m_stages.clear();
2134}
2135
2136
2137void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
2138 DIRECTION_45 direction, NODE* aNode )
2139{
2140 STAGE st;
2141 FIX_POINT pt;
2142
2143 pt.p = aStart;
2144 pt.layer = aLayer;
2145 pt.direction = direction;
2146 pt.placingVias = placingVias;
2147
2148 st.pts.push_back(pt);
2149 st.commit = aNode;
2150
2151 m_stages.push_back( st );
2152}
2153
2154
2156{
2157 if( !m_stages.size() )
2158 return false;
2159
2160 aStage = m_stages.back();
2161
2162 if( m_stages.size() > 1 )
2163 m_stages.pop_back();
2164
2165 return true;
2166}
2167
2168
2170{
2171 return m_stages.size();
2172}
2173
2174}
2175
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.
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition direction45.h:78
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
Definition direction45.h:49
CORNER_MODE
Corner modes.
Definition direction45.h:67
@ ROUNDED_90
H/V with filleted corners.
Definition direction45.h:71
@ MITERED_90
H/V only (90-degree corners)
Definition direction45.h:70
@ ROUNDED_45
H/V/45 with filleted corners.
Definition direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition direction45.h:68
const std::string Format() const
Format the direction in a human readable word.
KICAD_T Type() const
Returns the type of object.
Definition eda_item.h:110
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
void SetLogger(LOGGER *aLogger)
virtual LOGGER * Logger()
ROUTER * Router() const
Return current router settings.
ROUTER * m_router
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
DEBUG_DECORATOR * Dbg() const
SHAPE_ARC & Arc()
Definition pns_arc.h:115
void SetWidth(int aWidth) override
Definition pns_arc.h:83
FIXED_TAIL(int aLineCount=1)
bool PopStage(STAGE &aStage)
void AddStage(const VECTOR2I &aStart, int aLayer, bool placingVias, DIRECTION_45 direction, NODE *aNode)
std::vector< STAGE > m_stages
const std::vector< ITEM * > & CItems() const
Definition pns_itemset.h:88
Base class for PNS router board items.
Definition pns_item.h:98
BOARD_ITEM * Parent() const
Definition pns_item.h:199
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
void SetLayer(int aLayer)
Definition pns_item.h:215
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.
const ITEM_SET Traces() override
Return the complete routed line, as a single-member ITEM_SET.
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish) override
Commit the currently routed track to the parent node taking aP as the final end point and aEndItem as...
std::optional< VECTOR2I > UnfixRoute() override
bool ToggleVia(bool aEnabled) override
Enable/disable a via at the end of currently routed trace.
bool clipAndCheckCollisions(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aL, SHAPE_LINE_CHAIN &aOut, int &thresholdDist)
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
const VECTOR2I & CPoint(int aIdx) const
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
const VECTOR2I & CLastPoint() const
Definition pns_line.h:147
void RemoveVia()
SHAPE_LINE_CHAIN & Line()
Definition pns_line.h:137
void AppendVia(const VIA &aVia)
VIA & Via()
Definition pns_line.h:199
int SegmentCount() const
Definition pns_line.h:140
int PointCount() const
Definition pns_line.h:141
bool EndsWithVia() const
Definition pns_line.h:191
const SEG CSegment(int aIdx) const
Set line width.
Definition pns_line.h:148
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:158
void Clear()
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.
std::vector< ITEM * > ITEM_VECTOR
Definition pns_node.h:243
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition pns_node.cpp: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.
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.
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.
void KillChildren()
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...
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.
@ 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
PLACEMENT_ALGO(ROUTER *aRouter)
virtual NET_HANDLE GetOrphanedNetHandle()=0
ROUTER_IFACE * GetInterface() const
Definition pns_router.h:232
void CommitRouting()
NODE * GetWorld() const
Definition pns_router.h:178
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
void SetWidth(int aWidth) override
Definition pns_segment.h:83
bool LeadingRatLine(const LINE *aTrack, SHAPE_LINE_CHAIN &aRatLine)
const VECTOR2I & Pos() const
Definition pns_via.h:184
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
Definition pns_via.cpp:134
void SetPos(const VECTOR2I &aPos)
Definition pns_via.h:186
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 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:604
int Length() const
Return the length (this).
Definition seg.h:343
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition seg.h:286
bool Overlaps(const SEG &aSeg) const
Definition seg.h:301
bool Contains(const SEG &aSeg) const
Definition seg.h:324
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:656
SEG Reversed() const
Returns the center point of the line.
Definition seg.h:373
bool IsClockwise() const
Definition shape_arc.h:321
int GetWidth() const override
Definition shape_arc.h:213
const VECTOR2I & GetP1() const
Definition shape_arc.h:117
const VECTOR2I & GetP0() const
Definition shape_arc.h:116
const VECTOR2I & GetCenter() const
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.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
size_t ArcCount() const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
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 std::vector< VECTOR2I > & CPoints() const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
@ LIGHTGREEN
Definition color4d.h: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
@ SEGMENT
Definition eda_shape.h:45
@ 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)
@ THROUGH
Definition pcb_track.h:67
#define PNS_DBG(dbg, method,...)
#define PNS_DBGN(dbg, method)
@ VIA
Normal via.
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