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( ¤t, 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