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 <tomasz.wlostowski@cern.ch>
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 <core/optional.h>
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"
34 #include "pns_mouse_trail_tracer.h"
35 
36 #include <wx/log.h>
37 
38 namespace PNS {
39 
LINE_PLACER(ROUTER * aRouter)40 LINE_PLACER::LINE_PLACER( ROUTER* aRouter ) :
41     PLACEMENT_ALGO( aRouter )
42 {
43     m_initial_direction = DIRECTION_45::N;
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 = 0;
53     m_currentLayer = 0;
54     m_startItem = nullptr;
55     m_chainedPlacement = false;
56     m_orthoMode = false;
57     m_placementCorrect = false;
58 }
59 
60 
~LINE_PLACER()61 LINE_PLACER::~LINE_PLACER()
62 {
63 }
64 
65 
setWorld(NODE * aWorld)66 void LINE_PLACER::setWorld( NODE* aWorld )
67 {
68     m_world = aWorld;
69 }
70 
71 
makeVia(const VECTOR2I & aP)72 const VIA LINE_PLACER::makeVia( const VECTOR2I& aP )
73 {
74     const LAYER_RANGE layers( m_sizes.ViaType() == VIATYPE::THROUGH ? F_Cu : m_sizes.GetLayerTop(),
75                               m_sizes.ViaType() == VIATYPE::THROUGH ? B_Cu : m_sizes.GetLayerBottom() );
76 
77     return VIA( aP, layers, m_sizes.ViaDiameter(), m_sizes.ViaDrill(), -1, m_sizes.ViaType() );
78 }
79 
80 
ToggleVia(bool aEnabled)81 bool LINE_PLACER::ToggleVia( bool aEnabled )
82 {
83     m_placingVia = aEnabled;
84 
85     if( !aEnabled )
86         m_head.RemoveVia();
87 
88     return true;
89 }
90 
91 
setInitialDirection(const DIRECTION_45 & aDirection)92 void LINE_PLACER::setInitialDirection( const DIRECTION_45& aDirection )
93 {
94     m_initial_direction = aDirection;
95 
96     if( m_tail.SegmentCount() == 0 )
97             m_direction = aDirection;
98 }
99 
100 
handleSelfIntersections()101 bool LINE_PLACER::handleSelfIntersections()
102 {
103     SHAPE_LINE_CHAIN::INTERSECTIONS ips;
104     SHAPE_LINE_CHAIN& head = m_head.Line();
105     SHAPE_LINE_CHAIN& tail = m_tail.Line();
106 
107     // if there is no tail, there is nothing to intersect with
108     if( tail.PointCount() < 2 )
109         return false;
110 
111     if( head.PointCount() < 2 )
112         return false;
113 
114     // completely new head trace? chop off the tail
115     if( tail.CPoint(0) == head.CPoint(0) )
116     {
117         m_p_start = tail.CPoint( 0 );
118         m_direction = m_initial_direction;
119         tail.Clear();
120         return true;
121     }
122 
123     tail.Intersect( head, ips );
124 
125     // no intesection points - nothing to reduce
126     if( ips.empty() )
127         return false;
128 
129     int n = INT_MAX;
130     VECTOR2I ipoint;
131 
132     // if there is more than one intersection, find the one that is
133     // closest to the beginning of the tail.
134     for( const SHAPE_LINE_CHAIN::INTERSECTION& i : ips )
135     {
136         if( i.index_our < n )
137         {
138             n = i.index_our;
139             ipoint = i.p;
140         }
141     }
142 
143     // ignore the point where head and tail meet
144     if( ipoint == head.CPoint( 0 ) || ipoint == tail.CPoint( -1 ) )
145         return false;
146 
147     // Intersection point is on the first or the second segment: just start routing
148     // from the beginning
149     if( n < 2 )
150     {
151         m_p_start = tail.CPoint( 0 );
152         m_direction = m_initial_direction;
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_p_start = last.A;
164         m_direction = DIRECTION_45( last );
165         tail.Remove( n, -1 );
166         return true;
167     }
168 
169     return false;
170 }
171 
172 
handlePullback()173 bool LINE_PLACER::handlePullback()
174 {
175     SHAPE_LINE_CHAIN& head = m_head.Line();
176     SHAPE_LINE_CHAIN& tail = m_tail.Line();
177 
178     if( head.PointCount() < 2 )
179         return false;
180 
181     int n = tail.PointCount();
182 
183     if( n == 0 )
184     {
185         return false;
186     }
187     else if( n == 1 )
188     {
189         m_p_start = tail.CPoint( 0 );
190         tail.Clear();
191         return true;
192     }
193 
194     DIRECTION_45 first_head, last_tail;
195 
196     wxASSERT( tail.PointCount() >= 2 );
197 
198     if( !head.IsPtOnArc( 0 ) )
199         first_head = DIRECTION_45( head.CSegment( 0 ) );
200     else
201         first_head = DIRECTION_45( head.CArcs()[head.ArcIndex(0)] );
202 
203     int lastSegIdx = tail.PointCount() - 2;
204 
205     if( !tail.IsPtOnArc( lastSegIdx ) )
206         last_tail = DIRECTION_45( tail.CSegment( lastSegIdx ) );
207     else
208         last_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex(lastSegIdx)] );
209 
210     DIRECTION_45::AngleType angle = first_head.Angle( last_tail );
211 
212     // case 1: we have a defined routing direction, and the currently computed
213     // head goes in different one.
214     bool pullback_1 = false;    // (m_direction != DIRECTION_45::UNDEFINED && m_direction != first_head);
215 
216     // case 2: regardless of the current routing direction, if the tail/head
217     // extremities form an acute or right angle, reduce the tail by one segment
218     // (and hope that further iterations) will result with a cleaner trace
219     bool pullback_2 = ( angle == DIRECTION_45::ANG_RIGHT || angle == DIRECTION_45::ANG_ACUTE );
220 
221     if( pullback_1 || pullback_2 )
222     {
223         lastSegIdx = tail.PrevShape( -1 );
224 
225         if( !tail.IsPtOnArc( lastSegIdx ) )
226         {
227             const SEG& seg = tail.CSegment( lastSegIdx );
228             m_direction    = DIRECTION_45( seg );
229             m_p_start      = seg.A;
230         }
231         else
232         {
233             const SHAPE_ARC& arc = tail.CArcs()[tail.ArcIndex( lastSegIdx )];
234             m_direction          = DIRECTION_45( arc );
235             m_p_start            = arc.GetP0();
236         }
237 
238         wxLogTrace( "PNS", "Placer: pullback triggered [%d] [%s %s]",
239                     n, last_tail.Format().c_str(), first_head.Format().c_str() );
240 
241         // erase the last point in the tail, hoping that the next iteration will
242         // result with a head trace that starts with a segment following our
243         // current direction.
244         if( n < 2 )
245             tail.Clear(); // don't leave a single-point tail
246         else
247             tail.RemoveShape( -1 );
248 
249         if( !tail.SegmentCount() )
250             m_direction = m_initial_direction;
251 
252         return true;
253     }
254 
255     return false;
256 }
257 
258 
reduceTail(const VECTOR2I & aEnd)259 bool LINE_PLACER::reduceTail( const VECTOR2I& aEnd )
260 {
261     SHAPE_LINE_CHAIN& head = m_head.Line();
262     SHAPE_LINE_CHAIN& tail = m_tail.Line();
263 
264     int n = tail.SegmentCount();
265 
266     if( head.SegmentCount() < 1 )
267         return false;
268 
269     // Don't attempt this for too short tails
270     if( n < 2 )
271         return false;
272 
273     // Start from the segment farthest from the end of the tail
274     // int start_index = std::max(n - 1 - ReductionDepth, 0);
275 
276     DIRECTION_45 new_direction;
277     VECTOR2I new_start;
278     int reduce_index = -1;
279 
280     for( int i = tail.SegmentCount() - 1; i >= 0; i-- )
281     {
282         const SEG s = tail.CSegment( i );
283         DIRECTION_45 dir( s );
284 
285         // calculate a replacement route and check if it matches
286         // the direction of the segment to be replaced
287         SHAPE_LINE_CHAIN replacement = dir.BuildInitialTrace( s.A, aEnd );
288 
289         if( replacement.SegmentCount() < 1 )
290             continue;
291 
292         LINE tmp( m_tail, replacement );
293 
294         if( m_currentNode->CheckColliding( &tmp, ITEM::ANY_T ) )
295             break;
296 
297         if( DIRECTION_45( replacement.CSegment( 0 ) ) == dir )
298         {
299             new_start = s.A;
300             new_direction = dir;
301             reduce_index = i;
302         }
303     }
304 
305     if( reduce_index >= 0 )
306     {
307         wxLogTrace( "PNS", "Placer: reducing tail: %d", reduce_index );
308         SHAPE_LINE_CHAIN reducedLine = new_direction.BuildInitialTrace( new_start, aEnd );
309 
310         m_p_start = new_start;
311         m_direction = new_direction;
312         tail.Remove( reduce_index + 1, -1 );
313         head.Clear();
314         return true;
315     }
316 
317     if( !tail.SegmentCount() )
318         m_direction = m_initial_direction;
319 
320     return false;
321 }
322 
323 
mergeHead()324 bool LINE_PLACER::mergeHead()
325 {
326     SHAPE_LINE_CHAIN& head = m_head.Line();
327     SHAPE_LINE_CHAIN& tail = m_tail.Line();
328 
329     const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE
330                                     | DIRECTION_45::ANG_HALF_FULL
331                                     | DIRECTION_45::ANG_UNDEFINED;
332 
333     head.Simplify();
334     tail.Simplify();
335 
336     int n_head  = head.ShapeCount();
337     int n_tail  = tail.ShapeCount();
338 
339     if( n_head < 3 )
340     {
341         wxLogTrace( "PNS", "Merge failed: not enough head segs." );
342         return false;
343     }
344 
345     if( n_tail && head.CPoint( 0 ) != tail.CPoint( -1 ) )
346     {
347         wxLogTrace( "PNS", "Merge failed: head and tail discontinuous." );
348         return false;
349     }
350 
351     if( m_head.CountCorners( ForbiddenAngles ) != 0 )
352         return false;
353 
354     DIRECTION_45 dir_tail, dir_head;
355 
356     if( !head.IsPtOnArc( 0 ) )
357         dir_head = DIRECTION_45( head.CSegment( 0 ) );
358     else
359         dir_head = DIRECTION_45( head.CArcs()[head.ArcIndex( 0 )] );
360 
361     if( n_tail )
362     {
363         wxASSERT( tail.PointCount() >= 2 );
364         int lastSegIdx = tail.PointCount() - 2;
365 
366         if( !tail.IsPtOnArc( lastSegIdx ) )
367             dir_tail = DIRECTION_45( tail.CSegment( -1 ) );
368         else
369             dir_tail = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
370 
371         if( dir_head.Angle( dir_tail ) & ForbiddenAngles )
372             return false;
373     }
374 
375     tail.Append( head );
376 
377     tail.Simplify();
378 
379     SEG last  = tail.CSegment( -1 );
380     m_p_start = last.B;
381 
382     int lastSegIdx = tail.PointCount() - 2;
383 
384     if( !tail.IsArcSegment( lastSegIdx ) )
385         m_direction = DIRECTION_45( tail.CSegment( -1 ) );
386     else
387         m_direction = DIRECTION_45( tail.CArcs()[tail.ArcIndex( lastSegIdx )] );
388 
389     head.Remove( 0, -1 );
390 
391     wxLogTrace( "PNS", "Placer: merge %d, new direction: %s", n_head,
392                 m_direction.Format().c_str() );
393 
394     head.Simplify();
395     tail.Simplify();
396 
397     return true;
398 }
399 
400 
closestProjectedPoint(const SHAPE_LINE_CHAIN & line,const VECTOR2I & p)401 VECTOR2I closestProjectedPoint( const SHAPE_LINE_CHAIN& line, const VECTOR2I& p )
402 {
403     // Keep distances squared for performance
404     SEG::ecoord min_dist_sq = VECTOR2I::ECOORD_MAX;
405     VECTOR2I    closest;
406 
407     for( int i = 0; i < line.SegmentCount(); i++ )
408     {
409         const SEG& s = line.CSegment( i );
410         VECTOR2I   a = s.NearestPoint( p );
411         int        d_sq = (a - p).SquaredEuclideanNorm();
412 
413         if( d_sq < min_dist_sq )
414         {
415             min_dist_sq = d_sq;
416             closest = a;
417         }
418     }
419 
420     return closest;
421 }
422 
423 
cursorDistMinimum(const SHAPE_LINE_CHAIN & aL,const VECTOR2I & aCursor,double lengthThreshold,int & theDist,VECTOR2I & aNearest)424 static bool cursorDistMinimum( const SHAPE_LINE_CHAIN& aL, const VECTOR2I& aCursor,  double lengthThreshold, int& theDist, VECTOR2I& aNearest )
425 {
426     std::vector<int>      dists;
427     std::vector<VECTOR2I> pts;
428 
429     if( aL.PointCount() == 0 )
430         return false;
431 
432     VECTOR2I lastP = aL.CPoint(-1);
433     int accumulatedDist = 0;
434 
435     dists.reserve( 2 * aL.PointCount() );
436 
437     for( int i = 0; i < aL.SegmentCount(); i++ )
438     {
439         const SEG& s = aL.CSegment( i );
440 
441         dists.push_back( ( aCursor - s.A ).EuclideanNorm() );
442         pts.push_back( s.A );
443         auto pn = s.NearestPoint( aCursor );
444 
445         if( pn != s.A && pn != s.B )
446         {
447             dists.push_back( ( pn - aCursor ).EuclideanNorm() );
448             pts.push_back( pn );
449         }
450 
451         accumulatedDist += s.Length();
452 
453         if ( accumulatedDist > lengthThreshold )
454         {
455             lastP = s.B;
456             break;
457         }
458     }
459 
460     dists.push_back( ( aCursor - lastP ).EuclideanNorm() );
461     pts.push_back( lastP );
462 
463     int minDistLoc = std::numeric_limits<int>::max();
464     int minPLoc = -1;
465     int minDistGlob = std::numeric_limits<int>::max();
466     int minPGlob = -1;
467 
468     for( int i = 0; i < dists.size(); i++ )
469     {
470         int d = dists[i];
471 
472         if( d < minDistGlob )
473         {
474             minDistGlob = d;
475             minPGlob = i;
476         }
477     }
478 
479     if( dists.size() >= 3 )
480     {
481         for( int i = 0; i < dists.size() - 3; i++ )
482         {
483             if( dists[i + 2] > dists[i + 1] && dists[i] > dists[i + 1] )
484             {
485                 int d = dists[i + 1];
486                 if( d < minDistLoc )
487                 {
488                     minDistLoc = d;
489                     minPLoc    = i + 1;
490                 }
491             }
492         }
493 
494         if( dists.back() < minDistLoc && minPLoc >= 0 )
495         {
496             minDistLoc = dists.back();
497             minPLoc    = dists.size() - 1;
498         }
499     }
500     else
501     {
502         // Too few points: just use the global
503         minDistLoc = minDistGlob;
504         minPLoc    = minPGlob;
505     }
506 
507 // fixme: I didn't make my mind yet if local or global minimum feels better. I'm leaving both
508 // in the code, enabling the global one by default
509     minPLoc = -1;
510 
511     if( minPLoc < 0 )
512     {
513         theDist = minDistGlob;
514         aNearest = pts[minPGlob];
515         return true;
516     }
517     else
518     {
519         theDist = minDistLoc;
520         aNearest = pts[minPLoc];
521         return true;
522     }
523 }
524 
525 
rhWalkOnly(const VECTOR2I & aP,LINE & aNewHead)526 bool LINE_PLACER::rhWalkOnly( const VECTOR2I& aP, LINE& aNewHead )
527 {
528     LINE initTrack( m_head );
529     LINE walkFull( m_head );
530 
531     initTrack.RemoveVia();
532     walkFull.RemoveVia();
533 
534     int effort = 0;
535     bool viaOk = false;
536 
537     VECTOR2I walkP = aP;
538 
539     WALKAROUND walkaround( m_currentNode, Router() );
540 
541     walkaround.SetSolidsOnly( false );
542     walkaround.SetDebugDecorator( Dbg() );
543     walkaround.SetLogger( Logger() );
544     walkaround.SetIterationLimit( Settings().WalkaroundIterationLimit() );
545 
546     char name[50];
547     int round = 0;
548 
549     do {
550         snprintf( name, sizeof( name ), "walk-round-%d", round );
551         PNS_DBG( Dbg(), BeginGroup, name );
552 
553         viaOk = buildInitialLine( walkP, initTrack, round == 0 );
554 
555         double initialLength = initTrack.CLine().Length();
556         double hugThresholdLength = initialLength * Settings().WalkaroundHugLengthThreshold();
557 
558         WALKAROUND::RESULT wr = walkaround.Route( initTrack );
559 
560         SHAPE_LINE_CHAIN l_cw = wr.lineCw.CLine();
561         SHAPE_LINE_CHAIN l_ccw = wr.lineCcw.CLine();
562 
563         if( wr.statusCcw == WALKAROUND::DONE || wr.statusCw == WALKAROUND::DONE )
564         {
565             int len_cw = wr.statusCw == WALKAROUND::DONE ? l_cw.Length() : INT_MAX;
566             int len_ccw = wr.statusCcw == WALKAROUND::DONE ? l_ccw.Length() : INT_MAX;
567 
568             PNS_DBG( Dbg(), AddLine, wr.lineCw.CLine(), CYAN, 10000, "wf-result-cw" );
569             PNS_DBG( Dbg(), AddLine, wr.lineCcw.CLine(), BLUE, 20000, "wf-result-ccw" );
570 
571             int bestLength = len_cw < len_ccw ? len_cw : len_ccw;
572 
573             if( bestLength > hugThresholdLength )
574             {
575                 wr.statusCw = WALKAROUND::ALMOST_DONE;
576                 wr.statusCcw = WALKAROUND::ALMOST_DONE;
577             }
578 
579             SHAPE_LINE_CHAIN& bestLine = len_cw < len_ccw ? l_cw : l_ccw;
580             walkFull.SetShape( bestLine );
581         }
582 
583         if( wr.statusCcw == WALKAROUND::ALMOST_DONE || wr.statusCw == WALKAROUND::ALMOST_DONE )
584         {
585             bool valid_cw = false, valid_ccw = false;
586             VECTOR2I p_cw, p_ccw;
587             int dist_ccw = 0, dist_cw = 0;
588 
589             if( wr.statusCcw == WALKAROUND::ALMOST_DONE )
590             {
591                 valid_ccw = cursorDistMinimum( l_ccw, aP, hugThresholdLength, dist_ccw, p_ccw );
592 
593                 if( valid_ccw )
594                 {
595                     int idx_ccw = l_ccw.Split( p_ccw );
596                     l_ccw = l_ccw.Slice( 0, idx_ccw );
597                     PNS_DBG( Dbg(), AddPoint, p_ccw, BLUE, 500000, "hug-target-ccw" );
598                     PNS_DBG( Dbg(), AddLine, l_ccw, MAGENTA, 200000, "wh-result-ccw" );
599                 }
600             }
601 
602             if( wr.statusCw == WALKAROUND::ALMOST_DONE )
603             {
604                 valid_cw = cursorDistMinimum( l_cw, aP, hugThresholdLength, dist_cw, p_cw );
605 
606                 if( valid_cw )
607                 {
608                     int idx_cw = l_cw.Split( p_cw );
609                     l_cw = l_cw.Slice( 0, idx_cw );
610                     PNS_DBG( Dbg(), AddPoint, p_cw, YELLOW, 500000, "hug-target-cw" );
611                     PNS_DBG( Dbg(), AddLine, l_cw, BLUE, 200000, "wh-result-cw" );
612                 }
613             }
614 
615             if( dist_cw < dist_ccw && valid_cw )
616             {
617                 walkFull.SetShape( l_cw );
618                 walkP = p_cw;
619             }
620             else if ( valid_ccw )
621             {
622                 walkFull.SetShape( l_ccw );
623                 walkP = p_ccw;
624             }
625             else
626             {
627                 PNS_DBGN( Dbg(), EndGroup );
628                 return false;
629             }
630         }
631         else if ( wr.statusCcw == WALKAROUND::STUCK || wr.statusCw == WALKAROUND::STUCK )
632         {
633             PNS_DBGN( Dbg(), EndGroup );
634             return false;
635         }
636 
637         PNS_DBGN( Dbg(), EndGroup );
638 
639         round++;
640     } while( round < 2 && m_placingVia );
641 
642     PNS_DBG( Dbg(), AddLine, walkFull.CLine(), GREEN, 200000, "walk-full" );
643 
644     switch( Settings().OptimizerEffort() )
645     {
646     case OE_LOW:
647         effort = 0;
648         break;
649 
650     case OE_MEDIUM:
651     case OE_FULL:
652         effort = OPTIMIZER::MERGE_SEGMENTS;
653         break;
654     }
655 
656     if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
657         effort |= OPTIMIZER::SMART_PADS;
658 
659     if( m_placingVia && viaOk )
660     {
661         walkFull.AppendVia( makeVia( walkFull.CPoint( -1 ) ) );
662     }
663 
664     OPTIMIZER::Optimize( &walkFull, effort, m_currentNode );
665 
666     if( m_currentNode->CheckColliding( &walkFull ) )
667     {
668         return false;
669     }
670 
671     aNewHead = walkFull;
672 
673     return true;
674 }
675 
676 
rhMarkObstacles(const VECTOR2I & aP,LINE & aNewHead)677 bool LINE_PLACER::rhMarkObstacles( const VECTOR2I& aP, LINE& aNewHead )
678 {
679     buildInitialLine( aP, m_head );
680     m_head.SetBlockingObstacle( nullptr );
681 
682     // Note: Something like the below could be used to implement a "stop at first obstacle" mode,
683     // but we don't have one right now and there isn't a lot of demand for one.  If we do end up
684     // doing that, put it in a new routing mode as "highlight collisions" mode should not have
685     // collision handling other than highlighting.
686 #if 0
687     if( !Settings().AllowDRCViolations() )
688     {
689         NODE::OPT_OBSTACLE obs = m_currentNode->NearestObstacle( &m_head );
690 
691         if( obs && obs->m_distFirst != INT_MAX )
692         {
693             buildInitialLine( obs->m_ipFirst, m_head );
694             m_head.SetBlockingObstacle( obs->m_item );
695         }
696     }
697 #endif
698 
699     aNewHead = m_head;
700 
701     return true;
702 }
703 
704 
rhShoveOnly(const VECTOR2I & aP,LINE & aNewHead)705 bool LINE_PLACER::rhShoveOnly( const VECTOR2I& aP, LINE& aNewHead )
706 {
707     LINE initTrack( m_head );
708     LINE walkSolids, l2;
709 
710     bool viaOk = buildInitialLine( aP, initTrack );
711 
712     m_currentNode = m_shove->CurrentNode();
713 
714     m_shove->SetLogger( Logger() );
715     m_shove->SetDebugDecorator( Dbg() );
716 
717     OPTIMIZER optimizer( m_currentNode );
718 
719     WALKAROUND walkaround( m_currentNode, Router() );
720 
721     walkaround.SetSolidsOnly( true );
722     walkaround.SetIterationLimit( 10 );
723     walkaround.SetDebugDecorator( Dbg() );
724     walkaround.SetLogger( Logger() );
725     WALKAROUND::WALKAROUND_STATUS stat_solids = walkaround.Route( initTrack, walkSolids );
726 
727     optimizer.SetEffortLevel( OPTIMIZER::MERGE_SEGMENTS );
728     optimizer.SetCollisionMask( ITEM::SOLID_T );
729     optimizer.Optimize( &walkSolids );
730 
731     if( stat_solids == WALKAROUND::DONE )
732         l2 = walkSolids;
733     else
734         l2 = initTrack.ClipToNearestObstacle( m_shove->CurrentNode() );
735 
736     LINE l( m_tail );
737     l.Line().Append( l2.CLine() );
738     l.Line().Simplify();
739 
740     if( l.PointCount() == 0 || l2.PointCount() == 0 )
741     {
742         aNewHead = m_head;
743         return false;
744     }
745 
746     if( m_placingVia && viaOk )
747     {
748         VIA v1( makeVia( l.CPoint( -1 ) ) );
749         VIA v2( makeVia( l2.CPoint( -1 ) ) );
750 
751         l.AppendVia( v1 );
752         l2.AppendVia( v2 );
753     }
754 
755     l.Line().Simplify();
756 
757     // in certain, uncommon cases there may be loops in the head+tail, In such case, we don't
758     // shove to avoid screwing up the database.
759     if( l.HasLoops() )
760     {
761         aNewHead = m_head;
762         return false;
763     }
764 
765     if( m_endItem )
766     {
767         // Make sure the springback algorithm won't erase the NODE that owns m_endItem.
768         m_shove->SetSpringbackDoNotTouchNode( m_endItem->Owner() );
769     }
770 
771     SHOVE::SHOVE_STATUS status = m_shove->ShoveLines( l );
772 
773     m_currentNode = m_shove->CurrentNode();
774 
775     if( status == SHOVE::SH_OK  || status == SHOVE::SH_HEAD_MODIFIED )
776     {
777         if( status == SHOVE::SH_HEAD_MODIFIED )
778             l2 = m_shove->NewHead();
779 
780         optimizer.SetWorld( m_currentNode );
781 
782         int effortLevel = OPTIMIZER::MERGE_OBTUSE;
783 
784         if( Settings().SmartPads() && !m_mouseTrailTracer.IsManuallyForced() )
785             effortLevel = OPTIMIZER::SMART_PADS;
786 
787         optimizer.SetEffortLevel( effortLevel );
788 
789         optimizer.SetCollisionMask( ITEM::ANY_T );
790         optimizer.Optimize( &l2 );
791 
792         aNewHead = l2;
793 
794         return true;
795     }
796     else
797     {
798         walkaround.SetWorld( m_currentNode );
799         walkaround.SetSolidsOnly( false );
800         walkaround.SetIterationLimit( 10 );
801         walkaround.SetApproachCursor( true, aP );
802         walkaround.Route( initTrack, l2 );
803         aNewHead = l2.ClipToNearestObstacle( m_shove->CurrentNode() );
804 
805         return false;
806     }
807 
808     return false;
809 }
810 
811 
routeHead(const VECTOR2I & aP,LINE & aNewHead)812 bool LINE_PLACER::routeHead( const VECTOR2I& aP, LINE& aNewHead )
813 {
814     switch( Settings().Mode() )
815     {
816     case RM_MarkObstacles:
817         return rhMarkObstacles( aP, aNewHead );
818     case RM_Walkaround:
819         return rhWalkOnly( aP, aNewHead );
820     case RM_Shove:
821         return rhShoveOnly( aP, aNewHead );
822     default:
823         break;
824     }
825 
826     return false;
827 }
828 
829 
optimizeTailHeadTransition()830 bool LINE_PLACER::optimizeTailHeadTransition()
831 {
832     LINE linetmp = Trace();
833 
834     PNS_DBG( Dbg(), Message, "optimize HT" );
835 
836     // NOTE: FANOUT_CLEANUP can override posture setting at the moment
837     if( !m_mouseTrailTracer.IsManuallyForced() &&
838         OPTIMIZER::Optimize( &linetmp, OPTIMIZER::FANOUT_CLEANUP, m_currentNode ) )
839     {
840         if( linetmp.SegmentCount() < 1 )
841             return false;
842 
843         m_head = linetmp;
844         m_p_start = linetmp.CLine().CPoint( 0 );
845         m_direction = DIRECTION_45( linetmp.CSegment( 0 ) );
846         m_tail.Line().Clear();
847 
848         PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize fanout-cleanup" ) );
849 
850 
851         return true;
852     }
853 
854     SHAPE_LINE_CHAIN& head = m_head.Line();
855     SHAPE_LINE_CHAIN& tail = m_tail.Line();
856 
857     int tailLookbackSegments = 3;
858 
859     //if(m_currentMode() == RM_Walkaround)
860     //    tailLookbackSegments = 10000;
861 
862     int threshold = std::min( tail.PointCount(), tailLookbackSegments + 1 );
863 
864     if( tail.ShapeCount() < 3 )
865         return false;
866 
867     // assemble TailLookbackSegments tail segments with the current head
868     SHAPE_LINE_CHAIN opt_line = tail.Slice( -threshold, -1 );
869 
870     int end = std::min(2, head.PointCount() - 1 );
871 
872     opt_line.Append( head.Slice( 0, end ) );
873 
874     LINE new_head( m_tail, opt_line );
875 
876     // and see if it could be made simpler by merging obtuse/collnear segments.
877     // If so, replace the (threshold) last tail points and the head with
878     // the optimized line
879 
880 
881     PNS_DBG( Dbg(), AddLine, new_head.CLine(), LIGHTCYAN, 10000, "ht-newline" );
882 
883     if( OPTIMIZER::Optimize( &new_head, OPTIMIZER::MERGE_SEGMENTS, m_currentNode ) )
884     {
885         LINE tmp( m_tail, opt_line );
886 
887         PNS_DBG( Dbg(), Message, wxString::Format( "Placer: optimize tail-head [%d]", threshold ) );
888 
889         head.Clear();
890         tail.Replace( -threshold, -1, new_head.CLine() );
891         tail.Simplify();
892 
893         m_p_start = new_head.CLine().CPoint( -1 );
894         m_direction = DIRECTION_45( new_head.CSegment( -1 ) );
895 
896         return true;
897     }
898 
899     return false;
900 }
901 
902 
routeStep(const VECTOR2I & aP)903 void LINE_PLACER::routeStep( const VECTOR2I& aP )
904 {
905     bool fail = false;
906     bool go_back = false;
907 
908     int i, n_iter = 1;
909 
910     LINE new_head;
911 
912     wxLogTrace( "PNS", "routeStep: direction: %s head: %d, tail: %d shapes",
913                 m_direction.Format().c_str(),
914                 m_head.ShapeCount(),
915                 m_tail.ShapeCount() );
916 
917     PNS_DBG( Dbg(), BeginGroup, "route-step" );
918 
919     PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-init" );
920     PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-init" );
921 
922     for( i = 0; i < n_iter; i++ )
923     {
924         if( !go_back && Settings().FollowMouse() )
925             reduceTail( aP );
926 
927         PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-reduce" );
928         PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-reduce" );
929 
930         go_back = false;
931 
932         if( !routeHead( aP, new_head ) )
933             fail = true;
934 
935         if( !new_head.Is45Degree() &&
936             !(Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles) )
937             fail = true;
938 
939         if( fail )
940             break;
941 
942         m_head = new_head;
943 
944         PNS_DBG( Dbg(), AddLine, m_head.CLine(), LIGHTGREEN, 100000, "head-new" );
945 
946         if( handleSelfIntersections() )
947         {
948             n_iter++;
949             go_back = true;
950         }
951 
952         PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-after-si" );
953         PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-after-si" );
954 
955         if( !go_back && handlePullback() )
956         {
957             n_iter++;
958             go_back = true;
959         }
960 
961         PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-after-pb" );
962         PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-after-pb" );
963     }
964 
965     if( fail )
966     {
967         if( m_last_head.PointCount() > 0 )
968         {
969             m_head = m_last_head;
970         }
971         else
972         {
973             m_head.RemoveVia();
974             m_head.Clear();
975         }
976     }
977     else
978     {
979         m_last_head = m_head;
980     }
981 
982     if( !fail && Settings().FollowMouse() )
983     {
984         PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 10000, "tail-pre-merge" );
985         PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 10000, "head-pre-merge" );
986 
987         if( !optimizeTailHeadTransition() )
988         {
989             mergeHead();
990         }
991 
992         PNS_DBG( Dbg(), AddLine, m_tail.CLine(), WHITE, 100000, "tail-post-merge" );
993         PNS_DBG( Dbg(), AddLine, m_head.CLine(), GREEN, 100000, "head-post-merge" );
994     }
995 
996     PNS_DBGN( Dbg(), EndGroup );
997 }
998 
999 
route(const VECTOR2I & aP)1000 bool LINE_PLACER::route( const VECTOR2I& aP )
1001 {
1002     routeStep( aP );
1003 
1004     if (!m_head.PointCount() )
1005         return false;
1006 
1007     return m_head.CPoint(-1) == aP;
1008 }
1009 
1010 
Trace() const1011 const LINE LINE_PLACER::Trace() const
1012 {
1013     LINE tmp( m_head );
1014 
1015     tmp.SetShape( m_tail.CLine() );
1016     tmp.Line().Append( m_head.CLine() );
1017     tmp.Line().Simplify();
1018     return tmp;
1019 }
1020 
1021 
Traces()1022 const ITEM_SET LINE_PLACER::Traces()
1023 {
1024     m_currentTrace = Trace();
1025     return ITEM_SET( &m_currentTrace );
1026 }
1027 
1028 
FlipPosture()1029 void LINE_PLACER::FlipPosture()
1030 {
1031     m_mouseTrailTracer.FlipPosture();
1032 }
1033 
1034 
CurrentNode(bool aLoopsRemoved) const1035 NODE* LINE_PLACER::CurrentNode( bool aLoopsRemoved ) const
1036 {
1037     if( aLoopsRemoved && m_lastNode )
1038         return m_lastNode;
1039 
1040     return m_currentNode;
1041 }
1042 
1043 
SplitAdjacentSegments(NODE * aNode,ITEM * aSeg,const VECTOR2I & aP)1044 bool LINE_PLACER::SplitAdjacentSegments( NODE* aNode, ITEM* aSeg, const VECTOR2I& aP )
1045 {
1046     if( !aSeg )
1047         return false;
1048 
1049     if( !aSeg->OfKind( ITEM::SEGMENT_T ) )
1050         return false;
1051 
1052     JOINT* jt = aNode->FindJoint( aP, aSeg );
1053 
1054     if( jt && jt->LinkCount() >= 1 )
1055         return false;
1056 
1057     SEGMENT* s_old = static_cast<SEGMENT*>( aSeg );
1058 
1059     std::unique_ptr<SEGMENT> s_new[2] = { Clone( *s_old ), Clone( *s_old ) };
1060 
1061     s_new[0]->SetEnds( s_old->Seg().A, aP );
1062     s_new[1]->SetEnds( aP, s_old->Seg().B );
1063 
1064     aNode->Remove( s_old );
1065     aNode->Add( std::move( s_new[0] ), true );
1066     aNode->Add( std::move( s_new[1] ), true );
1067 
1068     return true;
1069 }
1070 
1071 
SetLayer(int aLayer)1072 bool LINE_PLACER::SetLayer( int aLayer )
1073 {
1074     if( m_idle )
1075     {
1076         m_currentLayer = aLayer;
1077         return true;
1078     }
1079     else if( m_chainedPlacement )
1080     {
1081         return false;
1082     }
1083     else if( !m_startItem
1084             || ( m_startItem->OfKind( ITEM::VIA_T ) && m_startItem->Layers().Overlaps( aLayer ) )
1085             || ( m_startItem->OfKind( ITEM::SOLID_T ) && m_startItem->Layers().Overlaps( aLayer ) ) )
1086     {
1087         m_currentLayer = aLayer;
1088         m_p_start = m_currentStart;
1089         m_direction = m_initial_direction;
1090         m_mouseTrailTracer.Clear();
1091         m_head.Line().Clear();
1092         m_tail.Line().Clear();
1093         m_last_head.Line().Clear();
1094         m_head.RemoveVia();
1095         m_tail.RemoveVia();
1096         m_last_head.RemoveVia();
1097         m_head.SetLayer( m_currentLayer );
1098         m_tail.SetLayer( m_currentLayer );
1099         Move( m_currentEnd, nullptr );
1100         return true;
1101     }
1102 
1103     return false;
1104 }
1105 
1106 
Start(const VECTOR2I & aP,ITEM * aStartItem)1107 bool LINE_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
1108 {
1109     m_placementCorrect = false;
1110     m_currentStart = VECTOR2I( aP );
1111     m_currentEnd = VECTOR2I( aP );
1112     m_currentNet = std::max( 0, aStartItem ? aStartItem->Net() : 0 );
1113     m_startItem = aStartItem;
1114     m_placingVia = false;
1115     m_chainedPlacement = false;
1116     m_fixedTail.Clear();
1117     m_endItem = nullptr;
1118 
1119     setInitialDirection( Settings().InitialDirection() );
1120 
1121     initPlacement();
1122 
1123     DIRECTION_45 initialDir = m_initial_direction;
1124     DIRECTION_45 lastSegDir = DIRECTION_45::UNDEFINED;
1125 
1126     if( aStartItem && aStartItem->Kind() == ITEM::SEGMENT_T )
1127     {
1128         // If we land on a segment endpoint, assume the starting direction is continuing along
1129         // the same direction as the endpoint.  If we started in the middle, don't set a
1130         // direction so that the posture solver is not biased.
1131         SEG seg = static_cast<SEGMENT*>( aStartItem )->Seg();
1132 
1133         if( aP == seg.A )
1134             lastSegDir = DIRECTION_45( seg.Reversed() );
1135         else if( aP == seg.B )
1136             lastSegDir = DIRECTION_45( seg );
1137     }
1138     else if( aStartItem && aStartItem->Kind() == ITEM::SOLID_T &&
1139              static_cast<SOLID*>( aStartItem )->Parent()->Type() == PCB_PAD_T )
1140     {
1141         double angle = static_cast<SOLID*>( aStartItem )->GetOrientation() / 10.0;
1142         angle        = ( angle + 22.5 ) / 45.0;
1143         initialDir   = DIRECTION_45( static_cast<DIRECTION_45::Directions>( int( angle ) ) );
1144     }
1145 
1146     wxLogTrace( "PNS", "Posture: init %s, last seg %s", initialDir.Format(), lastSegDir.Format() );
1147 
1148     m_mouseTrailTracer.Clear();
1149     m_mouseTrailTracer.AddTrailPoint( aP );
1150     m_mouseTrailTracer.SetTolerance( m_head.Width() );
1151     m_mouseTrailTracer.SetDefaultDirections( m_initial_direction, DIRECTION_45::UNDEFINED );
1152     m_mouseTrailTracer.SetMouseDisabled( !Settings().GetAutoPosture() );
1153 
1154     NODE *n;
1155 
1156     if ( Settings().Mode() == PNS::RM_Shove )
1157         n = m_shove->CurrentNode();
1158     else
1159         n = m_currentNode;
1160 
1161     m_fixedTail.AddStage( m_currentStart, m_currentLayer, m_placingVia, m_direction, n );
1162 
1163     return true;
1164 }
1165 
1166 
initPlacement()1167 void LINE_PLACER::initPlacement()
1168 {
1169     m_idle = false;
1170 
1171     m_head.Line().Clear();
1172     m_tail.Line().Clear();
1173     m_head.SetNet( m_currentNet );
1174     m_tail.SetNet( m_currentNet );
1175     m_head.SetLayer( m_currentLayer );
1176     m_tail.SetLayer( m_currentLayer );
1177     m_head.SetWidth( m_sizes.TrackWidth() );
1178     m_tail.SetWidth( m_sizes.TrackWidth() );
1179     m_head.RemoveVia();
1180     m_tail.RemoveVia();
1181 
1182     m_p_start = m_currentStart;
1183     m_direction = m_initial_direction;
1184 
1185     NODE* world = Router()->GetWorld();
1186 
1187     world->KillChildren();
1188     NODE* rootNode = world->Branch();
1189 
1190     SplitAdjacentSegments( rootNode, m_startItem, m_currentStart );
1191 
1192     setWorld( rootNode );
1193 
1194     wxLogTrace( "PNS", "world %p, intitial-direction %s layer %d",
1195                 m_world,
1196                 m_direction.Format().c_str(),
1197                 m_currentLayer );
1198 
1199     m_lastNode = nullptr;
1200     m_currentNode = m_world;
1201 
1202     m_shove = std::make_unique<SHOVE>( m_world->Branch(), Router() );
1203 }
1204 
1205 
Move(const VECTOR2I & aP,ITEM * aEndItem)1206 bool LINE_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
1207 {
1208     LINE current;
1209     VECTOR2I p = aP;
1210     int eiDepth = -1;
1211 
1212     if( aEndItem && aEndItem->Owner() )
1213         eiDepth = static_cast<NODE*>( aEndItem->Owner() )->Depth();
1214 
1215     if( m_lastNode )
1216     {
1217         delete m_lastNode;
1218         m_lastNode = nullptr;
1219     }
1220 
1221     m_endItem = aEndItem;
1222 
1223     bool reachesEnd = route( p );
1224 
1225     current = Trace();
1226 
1227     if( !current.PointCount() )
1228         m_currentEnd = m_p_start;
1229     else
1230         m_currentEnd = current.CLine().CPoint( -1 );
1231 
1232     NODE* latestNode = m_currentNode;
1233     m_lastNode = latestNode->Branch();
1234 
1235     if( reachesEnd
1236             && eiDepth >= 0
1237             && aEndItem && latestNode->Depth() >= eiDepth
1238             && current.SegmentCount() )
1239     {
1240         SplitAdjacentSegments( m_lastNode, aEndItem, current.CPoint( -1 ) );
1241 
1242         if( Settings().RemoveLoops() )
1243             removeLoops( m_lastNode, current );
1244     }
1245 
1246     updateLeadingRatLine();
1247     m_mouseTrailTracer.AddTrailPoint( aP );
1248     return true;
1249 }
1250 
1251 
FixRoute(const VECTOR2I & aP,ITEM * aEndItem,bool aForceFinish)1252 bool LINE_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
1253 {
1254     bool fixAll  = Settings().GetFixAllSegments();
1255     bool realEnd = false;
1256 
1257     LINE pl = Trace();
1258 
1259     if( Settings().Mode() == RM_MarkObstacles )
1260     {
1261         // Mark Obstacles is sort of a half-manual, half-automated mode in which the
1262         // user has more responsibility and authority.
1263 
1264         if( aEndItem )
1265         {
1266             // The user has indicated a connection should be made.  If either the trace or
1267             // endItem is net-less, then allow the connection by adopting the net of the other.
1268             if( m_currentNet <= 0 )
1269             {
1270                 m_currentNet = aEndItem->Net();
1271                 pl.SetNet( m_currentNet );
1272             }
1273             else if (aEndItem->Net() <= 0 )
1274             {
1275                 aEndItem->SetNet( m_currentNet );
1276             }
1277         }
1278 
1279         // Collisions still prevent fixing unless "Allow DRC violations" is checked
1280         if( !Settings().AllowDRCViolations() && m_world->CheckColliding( &pl ) )
1281             return false;
1282     }
1283 
1284     const SHAPE_LINE_CHAIN& l = pl.CLine();
1285 
1286     if( !l.SegmentCount() )
1287     {
1288         if( m_lastNode )
1289         {
1290             // Do a final optimization to the stored state
1291             NODE::ITEM_VECTOR removed, added;
1292             m_lastNode->GetUpdatedItems( removed, added );
1293 
1294             if( !added.empty() && added.back()->Kind() == ITEM::SEGMENT_T )
1295                 simplifyNewLine( m_lastNode, static_cast<SEGMENT*>( added.back() ) );
1296         }
1297 
1298         // Nothing to commit if we have an empty line
1299         if( !pl.EndsWithVia() )
1300             return false;
1301 
1302         ///< @todo Determine what to do if m_lastNode is a null pointer.  I'm guessing return
1303         ///<       false but someone with more knowledge of the code will need to determine that..
1304         if( m_lastNode )
1305         {
1306             m_lastNode->Add( Clone( pl.Via() ) );
1307             m_shove->AddLockedSpringbackNode( m_lastNode );
1308         }
1309 
1310         m_currentNode = nullptr;
1311 
1312         m_idle = true;
1313         m_placementCorrect = true;
1314         return true;
1315     }
1316 
1317     VECTOR2I p_pre_last = l.CPoint( -1 );
1318     const VECTOR2I p_last = l.CPoint( -1 );
1319 
1320     if( l.PointCount() > 2 )
1321         p_pre_last = l.CPoint( -2 );
1322 
1323     if( aEndItem && m_currentNet >= 0 && m_currentNet == aEndItem->Net() )
1324         realEnd = true;
1325 
1326     if( aForceFinish )
1327         realEnd = true;
1328 
1329     // TODO: Rollback doesn't work properly if fix-all isn't enabled and we are placing arcs,
1330     // so if we are, act as though we are in fix-all mode.
1331     if( !fixAll && l.ArcCount() )
1332         fixAll = true;
1333 
1334     // TODO: lastDirSeg will be calculated incorrectly if we end on an arc
1335     SEG lastDirSeg = ( !fixAll && l.SegmentCount() > 1 ) ? l.CSegment( -2 ) : l.CSegment( -1 );
1336     DIRECTION_45 d_last( lastDirSeg );
1337 
1338     int lastV;
1339 
1340     if( realEnd || m_placingVia || fixAll )
1341         lastV = l.SegmentCount();
1342     else
1343         lastV = std::max( 1, l.SegmentCount() - 1 );
1344 
1345     ARC          arc;
1346     SEGMENT      seg;
1347     LINKED_ITEM* lastItem = nullptr;
1348     int          lastArc  = -1;
1349 
1350     for( int i = 0; i < lastV; i++ )
1351     {
1352         ssize_t arcIndex = l.ArcIndex( i );
1353 
1354         if( arcIndex < 0 || ( lastArc >= 0 && i == lastV - 1 && !l.IsPtOnArc( lastV ) ) )
1355         {
1356             seg = SEGMENT( pl.CSegment( i ), m_currentNet );
1357             seg.SetWidth( pl.Width() );
1358             seg.SetLayer( m_currentLayer );
1359 
1360             std::unique_ptr<SEGMENT> sp = std::make_unique<SEGMENT>( seg );
1361             lastItem = sp.get();
1362 
1363             if( !m_lastNode->Add( std::move( sp ) ) )
1364                 lastItem = nullptr;
1365         }
1366         else
1367         {
1368             if( arcIndex == lastArc )
1369                 continue;
1370 
1371             arc = ARC( l.Arc( arcIndex ), m_currentNet );
1372             arc.SetWidth( pl.Width() );
1373             arc.SetLayer( m_currentLayer );
1374 
1375             std::unique_ptr<ARC> ap = std::make_unique<ARC>( arc );
1376             lastItem = ap.get();
1377 
1378             if( !m_lastNode->Add( std::move( ap ) ) )
1379                 lastItem = nullptr;
1380 
1381             lastArc  = arcIndex;
1382         }
1383     }
1384 
1385     if( pl.EndsWithVia() )
1386         m_lastNode->Add( Clone( pl.Via() ) );
1387 
1388     if( realEnd && lastItem )
1389         simplifyNewLine( m_lastNode, lastItem );
1390 
1391     if( !realEnd )
1392     {
1393         setInitialDirection( d_last );
1394         m_currentStart = ( m_placingVia || fixAll ) ? p_last : p_pre_last;
1395 
1396         VECTOR2I ps;
1397         if( m_tail.SegmentCount() )
1398             ps = m_tail.CPoint( 0 );
1399         else
1400             ps = m_p_start;
1401 
1402         m_fixedTail.AddStage( ps, m_currentLayer, m_placingVia, m_direction, m_currentNode );
1403 
1404         m_startItem = nullptr;
1405         m_placingVia = false;
1406         m_chainedPlacement = !pl.EndsWithVia();
1407 
1408         m_p_start = m_currentStart;
1409         m_direction = m_initial_direction;
1410 
1411         m_head.Line().Clear();
1412         m_tail.Line().Clear();
1413         m_head.RemoveVia();
1414         m_tail.RemoveVia();
1415         m_currentNode = m_lastNode;
1416         m_lastNode = m_lastNode->Branch();
1417 
1418         m_shove->AddLockedSpringbackNode( m_currentNode );
1419 
1420         DIRECTION_45 lastSegDir = pl.EndsWithVia() ? DIRECTION_45::UNDEFINED : d_last;
1421 
1422         m_mouseTrailTracer.Clear();
1423         m_mouseTrailTracer.SetTolerance( m_head.Width() );
1424         m_mouseTrailTracer.AddTrailPoint( m_currentStart );
1425         m_mouseTrailTracer.SetDefaultDirections( m_initial_direction, lastSegDir );
1426 
1427         m_placementCorrect = true;
1428     }
1429     else
1430     {
1431         m_shove->AddLockedSpringbackNode( m_lastNode );
1432         m_placementCorrect = true;
1433         m_idle = true;
1434     }
1435 
1436     return realEnd;
1437 }
1438 
1439 
UnfixRoute()1440 bool LINE_PLACER::UnfixRoute()
1441 {
1442     FIXED_TAIL::STAGE st;
1443 
1444     if ( !m_fixedTail.PopStage( st ) )
1445         return false;
1446 
1447     m_head.Line().Clear();
1448     m_tail.Line().Clear();
1449     m_startItem = nullptr;
1450     m_p_start = st.pts[0].p;
1451     m_direction = st.pts[0].direction;
1452     m_placingVia = st.pts[0].placingVias;
1453     m_currentNode = st.commit;
1454     m_currentLayer = st.pts[0].layer;
1455     m_head.SetLayer( m_currentLayer );
1456     m_tail.SetLayer( m_currentLayer );
1457     m_head.RemoveVia();
1458     m_tail.RemoveVia();
1459 
1460     m_mouseTrailTracer.Clear();
1461     m_mouseTrailTracer.SetDefaultDirections( m_initial_direction, m_direction );
1462     m_mouseTrailTracer.AddTrailPoint( m_p_start );
1463 
1464     m_shove->RewindSpringbackTo( m_currentNode );
1465     m_shove->UnlockSpringbackNode( m_currentNode );
1466 
1467     if( Settings().Mode() == PNS::RM_Shove )
1468     {
1469         m_currentNode = m_shove->CurrentNode();
1470         m_currentNode->KillChildren();
1471     }
1472 
1473     m_lastNode = m_currentNode->Branch();
1474 
1475     return true;
1476 }
1477 
1478 
HasPlacedAnything() const1479 bool LINE_PLACER::HasPlacedAnything() const
1480 {
1481      return m_placementCorrect || m_fixedTail.StageCount() > 1;
1482 }
1483 
1484 
CommitPlacement()1485 bool LINE_PLACER::CommitPlacement()
1486 {
1487     if( Settings().Mode() == PNS::RM_Shove )
1488     {
1489         m_shove->RewindToLastLockedNode();
1490         m_lastNode = m_shove->CurrentNode();
1491         m_lastNode->KillChildren();
1492     }
1493 
1494     if( m_lastNode )
1495         Router()->CommitRouting( m_lastNode );
1496 
1497     m_lastNode = nullptr;
1498     m_currentNode = nullptr;
1499     return true;
1500 }
1501 
1502 
removeLoops(NODE * aNode,LINE & aLatest)1503 void LINE_PLACER::removeLoops( NODE* aNode, LINE& aLatest )
1504 {
1505     if( !aLatest.SegmentCount() )
1506         return;
1507 
1508     if( aLatest.CLine().CPoint( 0 ) == aLatest.CLine().CPoint( -1 ) )
1509         return;
1510 
1511     std::set<LINKED_ITEM *> toErase;
1512     aNode->Add( aLatest, true );
1513 
1514     for( int s = 0; s < aLatest.LinkCount(); s++ )
1515     {
1516         LINKED_ITEM* seg = aLatest.GetLink(s);
1517         LINE ourLine = aNode->AssembleLine( seg );
1518         JOINT a, b;
1519         std::vector<LINE> lines;
1520 
1521         aNode->FindLineEnds( ourLine, a, b );
1522 
1523         if( a == b )
1524             aNode->FindLineEnds( aLatest, a, b );
1525 
1526         aNode->FindLinesBetweenJoints( a, b, lines );
1527 
1528         int removedCount = 0;
1529         int total = 0;
1530 
1531         for( LINE& line : lines )
1532         {
1533             total++;
1534 
1535             if( !( line.ContainsLink( seg ) ) && line.SegmentCount() )
1536             {
1537                 for( LINKED_ITEM* ss : line.Links() )
1538                     toErase.insert( ss );
1539 
1540                 removedCount++;
1541             }
1542         }
1543 
1544         wxLogTrace( "PNS", "total segs removed: %d/%d", removedCount, total );
1545     }
1546 
1547     for( LINKED_ITEM* s : toErase )
1548         aNode->Remove( s );
1549 
1550     aNode->Remove( aLatest );
1551 }
1552 
1553 
simplifyNewLine(NODE * aNode,LINKED_ITEM * aLatest)1554 void LINE_PLACER::simplifyNewLine( NODE* aNode, LINKED_ITEM* aLatest )
1555 {
1556     wxASSERT( aLatest->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) );
1557 
1558     // Before we assemble the final line and run the optimizer, do a separate pass to clean up
1559     // colinear segments that exist on non-line-corner joints, as these will prevent proper assembly
1560     // of the line and won't get cleaned up by the optimizer.
1561     NODE::ITEM_VECTOR removed, added;
1562     aNode->GetUpdatedItems( removed, added );
1563 
1564     std::set<ITEM*> cleanup;
1565 
1566     auto processJoint =
1567             [&]( JOINT* aJoint, ITEM* aItem )
1568             {
1569                 if( !aJoint || aJoint->IsLineCorner() )
1570                     return;
1571 
1572                 SEG refSeg = static_cast<SEGMENT*>( aItem )->Seg();
1573 
1574                 NODE::ITEM_VECTOR toRemove;
1575 
1576                 for( ITEM* neighbor : aJoint->Links() )
1577                 {
1578                     if( neighbor == aItem
1579                         || !neighbor->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
1580                         || !neighbor->LayersOverlap( aItem ) )
1581                     {
1582                         continue;
1583                     }
1584 
1585                     if( static_cast<SEGMENT*>( neighbor )->Width()
1586                             != static_cast<SEGMENT*>( aItem )->Width() )
1587                     {
1588                         continue;
1589                     }
1590 
1591                     const SEG& testSeg = static_cast<SEGMENT*>( neighbor )->Seg();
1592 
1593                     if( refSeg.Contains( testSeg ) )
1594                     {
1595                         JOINT* nA = aNode->FindJoint( neighbor->Anchor( 0 ), neighbor );
1596                         JOINT* nB = aNode->FindJoint( neighbor->Anchor( 1 ), neighbor );
1597 
1598                         if( ( nA == aJoint && nB->LinkCount() == 1 ) ||
1599                             ( nB == aJoint && nA->LinkCount() == 1 ) )
1600                         {
1601                             cleanup.insert( neighbor );
1602                         }
1603                     }
1604                 }
1605             };
1606 
1607     for( ITEM* item : added )
1608     {
1609         if( !item->OfKind( ITEM::SEGMENT_T ) || cleanup.count( item ) )
1610             continue;
1611 
1612         JOINT* jA = aNode->FindJoint( item->Anchor( 0 ), item );
1613         JOINT* jB = aNode->FindJoint( item->Anchor( 1 ), item );
1614 
1615         processJoint( jA, item );
1616         processJoint( jB, item );
1617     }
1618 
1619     for( ITEM* seg : cleanup )
1620         aNode->Remove( seg );
1621 
1622     // And now we can proceed with assembling the final line and optimizing it.
1623 
1624     LINE l = aNode->AssembleLine( aLatest );
1625 
1626     bool optimized = OPTIMIZER::Optimize( &l, OPTIMIZER::MERGE_COLINEAR, aNode );
1627 
1628     SHAPE_LINE_CHAIN simplified( l.CLine() );
1629 
1630     simplified.Simplify();
1631 
1632     if( optimized || simplified.PointCount() != l.PointCount() )
1633     {
1634         aNode->Remove( l );
1635         l.SetShape( simplified );
1636         aNode->Add( l );
1637     }
1638 }
1639 
1640 
UpdateSizes(const SIZES_SETTINGS & aSizes)1641 void LINE_PLACER::UpdateSizes( const SIZES_SETTINGS& aSizes )
1642 {
1643     m_sizes = aSizes;
1644 
1645     if( !m_idle )
1646     {
1647         // If the track width continues from an existing track, we don't want to change the width.
1648         // Disallow changing width after the first segment has been fixed because we don't want to
1649         // go back and rip up tracks or allow DRC errors
1650         if( m_sizes.TrackWidthIsExplicit() || ( !HasPlacedAnything()
1651                         && ( !m_startItem || m_startItem->Kind() != ITEM::SEGMENT_T ) ) )
1652         {
1653             m_head.SetWidth( m_sizes.TrackWidth() );
1654             m_tail.SetWidth( m_sizes.TrackWidth() );
1655             m_currentTrace.SetWidth( m_sizes.TrackWidth() );
1656         }
1657 
1658         if( m_head.EndsWithVia() )
1659         {
1660             m_head.SetViaDiameter( m_sizes.ViaDiameter() );
1661             m_head.SetViaDrill( m_sizes.ViaDrill() );
1662         }
1663     }
1664 }
1665 
1666 
updateLeadingRatLine()1667 void LINE_PLACER::updateLeadingRatLine()
1668 {
1669     LINE current = Trace();
1670     SHAPE_LINE_CHAIN ratLine;
1671     TOPOLOGY topo( m_lastNode );
1672 
1673     if( topo.LeadingRatLine( &current, ratLine ) )
1674         m_router->GetInterface()->DisplayRatline( ratLine, 5 );
1675 }
1676 
1677 
SetOrthoMode(bool aOrthoMode)1678 void LINE_PLACER::SetOrthoMode( bool aOrthoMode )
1679 {
1680     m_orthoMode = aOrthoMode;
1681 }
1682 
1683 
buildInitialLine(const VECTOR2I & aP,LINE & aHead,bool aForceNoVia)1684 bool LINE_PLACER::buildInitialLine( const VECTOR2I& aP, LINE& aHead, bool aForceNoVia )
1685 {
1686     SHAPE_LINE_CHAIN l;
1687     DIRECTION_45 guessedDir = m_mouseTrailTracer.GetPosture( aP );
1688 
1689     wxLogTrace( "PNS", "buildInitialLine: m_direction %s, guessedDir %s, tail points %d",
1690                 m_direction.Format(), guessedDir.Format(), m_tail.PointCount() );
1691 
1692     DIRECTION_45::CORNER_MODE cornerMode = Settings().GetCornerMode();
1693     // Rounded corners don't make sense when routing orthogonally (single track at a time)
1694     if( m_orthoMode )
1695         cornerMode = DIRECTION_45::CORNER_MODE::MITERED_45;
1696 
1697     if( m_p_start == aP )
1698     {
1699         l.Clear();
1700     }
1701     else
1702     {
1703         if( Settings().GetFreeAngleMode() && Settings().Mode() == RM_MarkObstacles )
1704         {
1705             l = SHAPE_LINE_CHAIN( { m_p_start, aP } );
1706         }
1707         else
1708         {
1709             if( !m_tail.PointCount() )
1710                 l = guessedDir.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1711             else
1712                 l = m_direction.BuildInitialTrace( m_p_start, aP, false, cornerMode );
1713         }
1714 
1715         if( l.SegmentCount() > 1 && m_orthoMode )
1716         {
1717             VECTOR2I newLast = l.CSegment( 0 ).LineProject( l.CPoint( -1 ) );
1718 
1719             l.Remove( -1, -1 );
1720             l.SetPoint( 1, newLast );
1721         }
1722     }
1723 
1724     aHead.SetLayer( m_currentLayer );
1725     aHead.SetShape( l );
1726 
1727     if( !m_placingVia || aForceNoVia )
1728         return true;
1729 
1730     VIA v( makeVia( aP ) );
1731     v.SetNet( aHead.Net() );
1732 
1733     if( Settings().Mode() == RM_MarkObstacles )
1734     {
1735         aHead.AppendVia( v );
1736         return true;
1737     }
1738 
1739     VECTOR2I force;
1740     VECTOR2I lead = aP - m_p_start;
1741 
1742     bool solidsOnly = ( Settings().Mode() != RM_Walkaround );
1743 
1744     if( v.PushoutForce( m_currentNode, lead, force, solidsOnly, 40 ) )
1745     {
1746         SHAPE_LINE_CHAIN line =
1747                 guessedDir.BuildInitialTrace( m_p_start, aP + force, false, cornerMode );
1748         aHead = LINE( aHead, line );
1749 
1750         v.SetPos( v.Pos() + force );
1751         return true;
1752     }
1753 
1754     return false; // via placement unsuccessful
1755 }
1756 
1757 
GetModifiedNets(std::vector<int> & aNets) const1758 void LINE_PLACER::GetModifiedNets( std::vector<int>& aNets ) const
1759 {
1760     aNets.push_back( m_currentNet );
1761 }
1762 
1763 
AbortPlacement()1764 bool LINE_PLACER::AbortPlacement()
1765 {
1766     m_world->KillChildren();
1767     return true;
1768 }
1769 
1770 
FIXED_TAIL(int aLineCount)1771 FIXED_TAIL::FIXED_TAIL( int aLineCount )
1772 {
1773 
1774 }
1775 
1776 
~FIXED_TAIL()1777 FIXED_TAIL::~FIXED_TAIL()
1778 {
1779 
1780 }
1781 
1782 
Clear()1783 void FIXED_TAIL::Clear()
1784 {
1785     m_stages.clear();
1786 }
1787 
1788 
AddStage(const VECTOR2I & aStart,int aLayer,bool placingVias,DIRECTION_45 direction,NODE * aNode)1789 void FIXED_TAIL::AddStage( const VECTOR2I& aStart, int aLayer, bool placingVias,
1790                            DIRECTION_45 direction, NODE* aNode )
1791 {
1792     STAGE st;
1793     FIX_POINT pt;
1794 
1795     pt.p = aStart;
1796     pt.layer = aLayer;
1797     pt.direction = direction;
1798     pt.placingVias = placingVias;
1799 
1800     st.pts.push_back(pt);
1801     st.commit = aNode;
1802 
1803     m_stages.push_back( st );
1804 }
1805 
1806 
PopStage(FIXED_TAIL::STAGE & aStage)1807 bool FIXED_TAIL::PopStage( FIXED_TAIL::STAGE& aStage )
1808 {
1809     if( !m_stages.size() )
1810         return false;
1811 
1812     aStage = m_stages.back();
1813 
1814     if( m_stages.size() > 1 )
1815         m_stages.pop_back();
1816 
1817     return true;
1818 }
1819 
1820 
StageCount() const1821 int FIXED_TAIL::StageCount() const
1822 {
1823     return m_stages.size();
1824 }
1825 
1826 }
1827 
1828