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