KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_router.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22#include <cstdio>
23#include <memory>
24#include <vector>
25
27
28#include <advanced_config.h>
30
31#include <pcb_painter.h>
32#include <pad.h>
33#include <zone.h>
34
35#include <geometry/shape.h>
36
37#include "pns_node.h"
38#include "pns_line_placer.h"
39#include "pns_line.h"
40#include "pns_solid.h"
41#include "pns_utils.h"
42#include "pns_router.h"
43#include "pns_shove.h"
44#include "pns_dragger.h"
45#include "pns_multi_dragger.h"
46#include "pns_block_dragger.h"
48#include "pns_topology.h"
50#include "pns_meander_placer.h"
53#include "pns_tracks_spreader.h"
54#include "pns_utils.h"
55#include "pns_diff_pair.h"
56
57#include "router_preview_item.h"
58
59namespace PNS {
60
61// an ugly singleton for drawing debug items within the router context.
62// To be fixed sometime in the future.
64
66{
67 theRouter = this;
68
69 m_state = IDLE;
71
72 m_logger = nullptr;
73
74 if( ADVANCED_CFG::GetCfg().m_EnableRouterDump )
75 m_logger = new LOGGER;
76
77 // Initialize all other variables:
78 m_lastNode = nullptr;
79 m_iterLimit = 0;
80 m_settings = nullptr;
81 m_iface = nullptr;
82 m_visibleViewArea.SetMaximum();
83}
84
85
87{
88 return theRouter;
89}
90
91
93{
94 ClearWorld();
95 theRouter = nullptr;
96 delete m_logger;
97}
98
99
101{
102 ClearWorld();
103
104 m_world = std::make_unique<NODE>();
105 m_world->BeginBulkAdd();
106 m_iface->SyncWorld( m_world.get() );
107 m_world->FinalizeBulkAdd();
108 m_world->FixupVirtualVias();
109}
110
111
113{
114 if( m_world )
115 {
116 m_world->SetRuleResolver( nullptr );
117 m_world->KillChildren();
118 m_world.reset();
119 }
120
121 m_placer.reset();
122}
123
124
126{
127 return m_state != IDLE;
128}
129
130
131const ITEM_SET ROUTER::QueryHoverItems( const VECTOR2I& aP, int aSlopRadius )
132{
133 NODE* node = m_placer ? m_placer->CurrentNode() : m_world.get();
134 PNS::ITEM_SET ret;
135
136 wxCHECK( node, ret );
137
139 {
140 NODE::OBSTACLES obs;
141 SEGMENT test( SEG( aP, aP ), nullptr );
143
144 test.SetWidth( Sizes().DiffPairGap() + 2 * Sizes().DiffPairWidth() );
145 test.SetLayers( PNS_LAYER_RANGE::All() );
146
147 opts.m_differentNetsOnly = false;
148 node->QueryColliding( &test, obs, opts );
149
150 DIFF_PAIR_PLACER* dpPlacer = static_cast<DIFF_PAIR_PLACER*>( Placer() );
151 auto currentDP = dpPlacer->CurrentTrace();
152
153 int distP = std::numeric_limits<int>::max();
154 int distN = std::numeric_limits<int>::max();
155
156 ITEM* best = nullptr;
157
158 for( const OBSTACLE& obstacle : obs )
159 {
160 NET_HANDLE netP, netN;
161
162 if( m_iface->GetRuleResolver()->DpNetPair( obstacle.m_item, netP, netN ) )
163 {
164 int dist = obstacle.m_item->Shape( obstacle.m_item->Layer() )->Distance( aP );
165
166 if( dist <= 0 )
167 {
168 ret.Add( obstacle.m_item, false );
169 }
170
171 int polarity = m_iface->GetRuleResolver()->DpNetPolarity( obstacle.m_item->Net() );
172
173 if( polarity > 0 )
174 {
175 if( dist < distP )
176 {
177 distP = dist;
178 best = obstacle.m_item;
179 }
180 }
181 else
182 {
183 if( dist < distN )
184 {
185 distN = dist;
186 if( distN <= distP )
187 best = obstacle.m_item;
188 }
189 }
190 }
191 }
192
193 if( distP < Sizes().DiffPairGap() && distN < Sizes().DiffPairGap() )
194 {
195 ret.Add( best, false );
196 return ret;
197 }
198
199 return ret;
200 }
201
202 if( aSlopRadius > 0 )
203 {
204 NODE::OBSTACLES obs;
205 SEGMENT test( SEG( aP, aP ), nullptr );
207
208 test.SetWidth( 1 );
209 test.SetLayers( PNS_LAYER_RANGE::All() );
210
211 opts.m_differentNetsOnly = false;
212 opts.SetFixedClearanceOverride( aSlopRadius );
213
214 node->QueryColliding( &test, obs, opts );
215
216 for( const OBSTACLE& obstacle : obs )
217 ret.Add( obstacle.m_item, false );
218
219 return ret;
220 }
221 else
222 {
223 return node->HitTest( aP );
224 }
225}
226
227
228bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aItem, int aDragMode )
229{
230 m_leaderSegments.clear();
231 return StartDragging( aP, ITEM_SET( aItem ), aDragMode );
232}
233
234bool ROUTER::hasDiffPairMembers( const ITEM_SET& aItems ) const
235{
236 auto rr = GetRuleResolver();
237
238 for( auto item : aItems.CItems() )
239 {
240
241 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
242 {
243 NET_HANDLE coupledNet = rr->DpCoupledNet( item->Net() );
244 if( coupledNet )
245 {
246 PNS_DBG( dbg(), Message, wxString::Format( wxT("found DP in itemset: %s/%s"),
247 GetInterface()->GetNetName( item->Net() ),
248 GetInterface()->GetNetName( coupledNet ) ) );
249 return true;
250 }
251 }
252 }
253
254 return false;
255}
256
257
258bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM_SET aStartItems, int aDragMode )
259{
260 m_leaderSegments.clear();
261 SetFailureReason( wxEmptyString );
263 if( aStartItems.Empty() )
264 return false;
265
266 auto rr = GetRuleResolver();
267 rr->ClearCaches();
268
269 bool useMultidragger = aStartItems.Count( ITEM::SEGMENT_T | ITEM::ARC_T ) > 1;
270
271 PNS_DBG( dbg, Message, wxString::Format(wxT("start-drag items %d usemulti %d"),
272 aStartItems.Count( ITEM::SEGMENT_T | ITEM::ARC_T ), useMultidragger?1:0 ));
273
274 // we use MULTI_DRAGGER also for differential pairs (with somewhat different optimization strategy)
275 if( !useMultidragger && Settings().GetKeepDPCouplingWhenDragging() )
276 {
277 useMultidragger = hasDiffPairMembers( aStartItems );
278 }
279
280 if( aDragMode & DM_BLOCK )
281 {
282 m_dragger = std::make_unique<BLOCK_DRAGGER>( this );
284 }
285 else if( aStartItems.Count( ITEM::SOLID_T ) > 0 )
286 {
287 m_dragger = std::make_unique<COMPONENT_DRAGGER>( this );
289 }
290 // more than 1 track segment or arc to drag? launch the multisegment dragger
291 else if( useMultidragger )
292 {
293 m_dragger = std::make_unique<MULTI_DRAGGER>( this );
295 }
296 else
297 {
298 m_dragger = std::make_unique<DRAGGER>( this );
300 }
301
302 m_dragger->SetMode( static_cast<PNS::DRAG_MODE>( aDragMode ) );
303 m_dragger->SetWorld( m_world.get() );
304 m_dragger->SetLogger( m_logger );
305 m_dragger->SetDebugDecorator( m_iface->GetDebugDecorator() );
306
307 if( m_logger )
308 m_logger->Clear();
309
310 if( m_logger )
311 {
312 if( aStartItems.Size() == 1 )
313 m_logger->Log( LOGGER::EVT_START_DRAG, aP, aStartItems[0] );
314 else if( aStartItems.Size() > 1 )
315 m_logger->LogM( LOGGER::EVT_START_MULTIDRAG, aP, aStartItems.Items() ); // fixme default args
316 }
317
318 if( m_dragger->Start( aP, aStartItems ) )
319 {
320 return true;
321 }
322 else
323 {
324 m_dragger.reset();
325 m_state = IDLE;
326 return false;
327 }
328}
329
330
331bool ROUTER::isStartingPointRoutable( const VECTOR2I& aWhere, ITEM* aStartItem, int aLayer )
332{
333 if( Settings().AllowDRCViolations() )
334 return true;
335
337 {
338 if( m_sizes.DiffPairGap() < m_sizes.MinClearance() )
339 {
340 SetFailureReason( _( "Diff pair gap is less than board minimum clearance." ) );
341 return false;
342 }
343 }
344
346 wxString failureReason;
347
348 for( ITEM* item : candidates.Items() )
349 {
350 // Edge cuts are put on all layers, but they're not *really* on all layers
351 if( item->BoardItem() && item->BoardItem()->GetLayer() == Edge_Cuts )
352 continue;
353
354 if( !item->Layers().Overlaps( aLayer ) )
355 continue;
356
357 if( item->IsRoutable() )
358 {
359 failureReason = wxEmptyString;
360 break;
361 }
362 else
363 {
364 BOARD_ITEM* parent = item->BoardItem();
365
366 switch( parent->Type() )
367 {
368 case PCB_PAD_T:
369 {
370 PAD* pad = static_cast<PAD*>( parent );
371
372 if( pad->GetAttribute() == PAD_ATTRIB::NPTH )
373 failureReason = _( "Cannot start routing from a non-plated hole." );
374 }
375 break;
376
377 case PCB_ZONE_T:
378 {
379 ZONE* zone = static_cast<ZONE*>( parent );
380
381 if( !zone->HasKeepoutParametersSet() )
382 break;
383
384 if( !zone->GetZoneName().IsEmpty() )
385 {
386 failureReason = wxString::Format( _( "Rule area '%s' disallows tracks." ),
387 zone->GetZoneName() );
388 }
389 else
390 {
391 failureReason = _( "Rule area disallows tracks." );
392 }
393 }
394 break;
395
396 case PCB_FIELD_T:
397 case PCB_TEXT_T:
398 case PCB_TEXTBOX_T:
399 failureReason = _( "Cannot start routing from a text item." );
400 break;
401
402 default:
403 break;
404 }
405 }
406 }
407
408 if( !failureReason.IsEmpty() )
409 {
410 SetFailureReason( failureReason );
411 return false;
412 }
413
414 VECTOR2I startPoint = aWhere;
415
417 {
418 SHAPE_LINE_CHAIN dummyStartSeg;
419 LINE dummyStartLine;
420
421 dummyStartSeg.Append( startPoint );
422 dummyStartSeg.Append( startPoint, true );
423
424 dummyStartLine.SetShape( dummyStartSeg );
425 dummyStartLine.SetLayer( aLayer );
426 dummyStartLine.SetNet( aStartItem ? aStartItem->Net() : 0 );
427 dummyStartLine.SetWidth( m_sizes.TrackWidth() );
428
429 if( m_world->CheckColliding( &dummyStartLine, ITEM::ANY_T ) )
430 {
431 // If the only reason we collide is track width; it's better to allow the user to start
432 // anyway and just highlight the resulting collisions, so they can change width later.
433 dummyStartLine.SetWidth( m_sizes.BoardMinTrackWidth() );
434
435 if( m_world->CheckColliding( &dummyStartLine, ITEM::ANY_T ) )
436 {
437 ITEM_SET dummyStartSet( &dummyStartLine );
438 NODE::ITEM_VECTOR highlightedItems;
439
440 markViolations( m_world.get(), dummyStartSet, highlightedItems );
441
442 for( ITEM* item : highlightedItems )
443 m_iface->HideItem( item );
444
445 SetFailureReason( _( "The routing start point violates DRC." ) );
446 return false;
447 }
448 }
449 }
450 else if( m_mode == PNS_MODE_ROUTE_DIFF_PAIR )
451 {
452 if( !aStartItem )
453 {
454 SetFailureReason( _( "Cannot start a differential pair in the middle of nowhere." ) );
455 return false;
456 }
457
458 DP_PRIMITIVE_PAIR dpPair;
459 DIFF_PAIR_PLACER dpPlacer( this );
460 wxString errorMsg;
461
462
463 if( !dpPlacer.FindDpPrimitivePair( m_world.get(), startPoint, aStartItem, dpPair,
464 &errorMsg ) )
465 {
466 SetFailureReason( errorMsg );
467 return false;
468 }
469
470 }
471
472 return true;
473}
474
475
476bool ROUTER::StartRouting( const VECTOR2I& aP, ITEM* aStartItem, int aLayer, const ITEM_SET& aAuxItems )
477{
479
481 {
482 if( !isStartingPointRoutable( aP, aStartItem, aLayer ) )
483 return false;
484 }
485
486 switch( m_mode )
487 {
489 m_placer = std::make_unique<LINE_PLACER>( this );
490 break;
491
493 m_placer = std::make_unique<DIFF_PAIR_PLACER>( this );
494 break;
495
497 m_placer = std::make_unique<MEANDER_PLACER>( this );
498 break;
499
501 m_placer = std::make_unique<DP_MEANDER_PLACER>( this );
502 break;
503
505 m_placer = std::make_unique<MEANDER_SKEW_PLACER>( this );
506 break;
507
509 m_placer = std::make_unique<TRACKS_SPREADER>( this );
510 // fixme: ugly cast
511 static_cast<TRACKS_SPREADER*>( m_placer.get() )->SetSpreadableItems( aAuxItems );
512 break;
513
514 default:
515 return false;
516 }
517
518 m_placer->UpdateSizes( m_sizes );
519 m_placer->SetLayer( aLayer );
520 m_placer->SetDebugDecorator( m_iface->GetDebugDecorator() );
521 m_placer->SetLogger( m_logger );
522
523 if( m_placer->Start( aP, aStartItem ) )
524 {
526
527 if( m_logger )
528 {
529 m_logger->Clear();
530 std::vector<ITEM*> logItems;
531 logItems.push_back( aStartItem );
532
534 {
535 auto spreadable = static_cast<TRACKS_SPREADER*>( m_placer.get() )->GetSpreadableItems();
536 for( auto item : spreadable.Items() )
537 logItems.push_back( item );
538 }
539
540 m_logger->LogM( LOGGER::EVT_START_ROUTE, aP, logItems, &m_sizes, m_placer->CurrentLayer() );
541 }
542
543 return true;
544 }
545 else
546 {
547 m_state = IDLE;
548 m_placer.reset();
549
550 return false;
551 }
552}
553
554
555bool ROUTER::Move( const VECTOR2I& aP, ITEM* endItem )
556{
557 if( m_logger )
558 m_logger->Log( LOGGER::EVT_MOVE, aP, endItem );
559
560 switch( m_state )
561 {
562 case ROUTE_TRACK:
563 return movePlacing( aP, endItem );
564
565 case DRAG_SEGMENT:
566 case DRAG_COMPONENT:
567 return moveDragging( aP, endItem );
568
569 default:
570 break;
571 }
572
574
575 return false;
576}
577
578
580 ITEM*& aOtherEndItem )
581{
582 // Can't finish something with no connections
583 if( GetCurrentNets().empty() )
584 return false;
585
586 PLACEMENT_ALGO* placer = Placer();
587
588 if( placer == nullptr || placer->Traces().Size() == 0 )
589 return false;
590
591 LINE* trace = dynamic_cast<LINE*>( placer->Traces()[0] );
592
593 if( trace == nullptr )
594 return false;
595
596 PNS::NODE* lastNode = placer->CurrentNode( true );
597 PNS::TOPOLOGY topo( lastNode, m_iface );
598
599 // If the user has drawn a line, get the anchor nearest to the line end
600 if( trace->SegmentCount() > 0 )
601 {
602 return topo.NearestUnconnectedAnchorPoint( trace, aOtherEnd, aOtherEndLayers,
603 aOtherEndItem );
604 }
605
606 // Otherwise, find the closest anchor to our start point
607
608 // Get joint from placer start item
609 const JOINT* jt = lastNode->FindJoint( placer->CurrentStart(), placer->CurrentLayer(),
610 placer->CurrentNets()[0] );
611
612 if( !jt )
613 return false;
614
615 // Get unconnected item from joint
616 int anchor;
617 PNS::ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
618
619 if( !it )
620 return false;
621
622 aOtherEnd = it->Anchor( anchor );
623 aOtherEndLayers = it->Layers();
624 aOtherEndItem = it;
625
626 return true;
627}
628
629
631{
632 if( m_state != ROUTE_TRACK )
633 return false;
634
635 PLACEMENT_ALGO* placer = Placer();
636
637 if( placer == nullptr || placer->Traces().Size() == 0 )
638 return false;
639
640 LINE* current = dynamic_cast<LINE*>( placer->Traces()[0] );
641
642 if( current == nullptr )
643 return false;
644
645 // Get our current line and position and nearest ratsnest to them if it exists
646 VECTOR2I otherEnd;
647 PNS_LAYER_RANGE otherEndLayers;
648 ITEM* otherEndItem = nullptr;
649
650 // Get the anchor nearest to the end of the trace the user is routing
651 if( !GetNearestRatnestAnchor( otherEnd, otherEndLayers, otherEndItem ) )
652 return false;
653
654 // Keep moving until we don't change position or hit the limit
655 int triesLeft = 5;
656 VECTOR2I moveResultPoint;
657
658 do
659 {
660 moveResultPoint = placer->CurrentEnd();
661 Move( otherEnd, otherEndItem );
662 triesLeft--;
663 } while( placer->CurrentEnd() != moveResultPoint && triesLeft );
664
665 // If we've made it, fix the route and we're done
666 if( placer->CurrentEnd() == otherEnd && otherEndLayers.Overlaps( GetCurrentLayer() ) )
667 {
668 bool forceFinish = false;
669 bool allowViolations = false;
670
671 return FixRoute( otherEnd, otherEndItem, forceFinish, allowViolations );
672 }
673
674 return false;
675}
676
677
678bool ROUTER::ContinueFromEnd( ITEM** aNewStartItem )
679{
680 PLACEMENT_ALGO* placer = Placer();
681
682 if( placer == nullptr || placer->Traces().Size() == 0 )
683 return false;
684
685 LINE* current = dynamic_cast<LINE*>( placer->Traces()[0] );
686
687 if( current == nullptr )
688 return false;
689
690 int currentLayer = GetCurrentLayer();
691 VECTOR2I currentEnd = placer->CurrentEnd();
692 VECTOR2I otherEnd;
693 PNS_LAYER_RANGE otherEndLayers;
694 ITEM* otherEndItem = nullptr;
695
696 // Get the anchor nearest to the end of the trace the user is routing
697 if( !GetNearestRatnestAnchor( otherEnd, otherEndLayers, otherEndItem ) )
698 return false;
699
701
702 // Commit whatever we've fixed and restart routing from the other end
703 int nextLayer = otherEndLayers.Overlaps( currentLayer ) ? currentLayer : otherEndLayers.Start();
704
705 if( !StartRouting( otherEnd, otherEndItem, nextLayer ) )
706 return false;
707
708 // Attempt to route to our current position
709 Move( currentEnd, nullptr );
710
711 *aNewStartItem = otherEndItem;
712
713 return true;
714}
715
716
717bool ROUTER::moveDragging( const VECTOR2I& aP, ITEM* aEndItem )
718{
719 m_iface->EraseView();
720
721 bool ret = m_dragger->Drag( aP );
722 ITEM_SET dragged = m_dragger->Traces();
723
724 m_leaderSegments = m_dragger->GetLastCommittedLeaderSegments();
725
726 updateView( m_dragger->CurrentNode(), dragged, true );
727 return ret;
728}
729
730
731void ROUTER::markViolations( NODE* aNode, ITEM_SET& aCurrent, NODE::ITEM_VECTOR& aRemoved )
732{
733 auto updateItem =
734 [&]( ITEM* currentItem, ITEM* itemToMark )
735 {
736 std::unique_ptr<ITEM> tmp( itemToMark->Clone() );
737
738 int clearance;
739 bool removeOriginal = true;
740
741 clearance = aNode->GetClearance( currentItem, itemToMark );
742
743 if( itemToMark->Layers().IsMultilayer() && !currentItem->Layers().IsMultilayer()
744 && !itemToMark->HasUniqueShapeLayers() )
745 {
746 tmp->SetLayer( currentItem->Layer() );
747 }
748
749 if( itemToMark->IsCompoundShapePrimitive() )
750 {
751 // We're only highlighting one (or more) of several primitives so we don't
752 // want all the other parts of the object to disappear
753 removeOriginal = false;
754 }
755
756 m_iface->DisplayItem( tmp.get(), clearance );
757
758 if( removeOriginal )
759 aRemoved.push_back( itemToMark );
760 };
761
762 for( ITEM* item : aCurrent.Items() )
763 {
764 NODE::OBSTACLES obstacles;
765
766 aNode->QueryColliding( item, obstacles );
767
768 if( item->OfKind( ITEM::LINE_T ) )
769 {
770 LINE* l = static_cast<LINE*>( item );
771
772 if( l->EndsWithVia() )
773 {
774 VIA v( l->Via() );
775 aNode->QueryColliding( &v, obstacles );
776 }
777 }
778
779 ITEM_SET draggedItems;
780
781 if( GetDragger() )
782 draggedItems = GetDragger()->Traces();
783
784 for( const OBSTACLE& obs : obstacles )
785 {
786 // Don't mark items being dragged; only board items they collide with
787 if( draggedItems.Contains( obs.m_item ) )
788 continue;
789
790 obs.m_item->Mark( obs.m_item->Marker() | MK_VIOLATION );
791 updateItem( item, obs.m_item );
792 }
793
794 if( item->Kind() == ITEM::LINE_T )
795 {
796 LINE* line = static_cast<LINE*>( item );
797
798 // Show clearance on any blocking obstacles
799 if( line->GetBlockingObstacle() )
800 updateItem( item, line->GetBlockingObstacle() );
801 }
802 }
803}
804
805
807{
808 if( m_state != ROUTE_TRACK )
809 return false;
810
812 return true;
813
814 return false;
815}
816
817
818void ROUTER::updateView( NODE* aNode, ITEM_SET& aCurrent, bool aDragging )
819{
820 NODE::ITEM_VECTOR removed, added;
821 NODE::OBSTACLES obstacles;
822
823 if( !aNode )
824 return;
825
826 // hack: we only mark violations when routing, not when length tuning - as the length tuner
827 // by design can never generate clearance violations. Since markViolations() calls multiple
828 // collision/clearance queries, it can be extremely expensive with certain custom DRC rules
829 // (rule area/courtyard-based, see issue #24052 for examples)
830 if( !areWeLengthTuning() )
831 {
832 markViolations( aNode, aCurrent, removed );
833 }
834
835 aNode->GetUpdatedItems( removed, added );
836
837 std::vector<const PNS::ITEM*> cacheCheckItems( added.begin(), added.end() );
838 GetRuleResolver()->ClearCacheForItems( cacheCheckItems );
839
840 for( ITEM* item : added )
841 {
842 int clearance = GetRuleResolver()->Clearance( item, nullptr );
843 m_iface->DisplayItem( item, clearance, aDragging );
844 }
845
846 for( ITEM* item : removed )
847 m_iface->HideItem( item );
848}
849
850
852{
853 m_sizes = aSizes;
854
855 // Change track/via size settings
856 if( m_state == ROUTE_TRACK )
857 m_placer->UpdateSizes( m_sizes );
858}
859
860
861bool ROUTER::movePlacing( const VECTOR2I& aP, ITEM* aEndItem )
862{
863 m_iface->EraseView();
864
865 bool ret = m_placer->Move( aP, aEndItem );
866 ITEM_SET current = m_placer->Traces();
867
868 for( const ITEM* item : current.CItems() )
869 {
870 if( !item->OfKind( ITEM::LINE_T ) )
871 continue;
872
873 const LINE* l = static_cast<const LINE*>( item );
874 int clearance = GetRuleResolver()->Clearance( item, nullptr );
875
876 m_iface->DisplayItem( l, clearance, false, PNS_HEAD_TRACE );
877
878 if( l->EndsWithVia() )
879 {
880 const VIA& via = l->Via();
881 clearance = GetRuleResolver()->Clearance( &via, nullptr );
882
883 if( via.HasHole() )
884 {
885 int holeClearance = GetRuleResolver()->Clearance( via.Hole(), nullptr );
886 int annularWidth = std::max( 0, via.Diameter( l->Layer() ) - via.Drill() ) / 2;
887 int excessHoleClearance = holeClearance - annularWidth;
888
889 if( excessHoleClearance > clearance )
890 clearance = excessHoleClearance;
891 }
892
893 m_iface->DisplayItem( &l->Via(), clearance, false, PNS_HEAD_TRACE );
894 }
895 }
896
897 //ITEM_SET tmp( &current );
898
899 updateView( m_placer->CurrentNode( true ), current );
900
901 return ret;
902}
903
904
905void ROUTER::GetUpdatedItems( std::vector<PNS::ITEM*>& aRemoved, std::vector<PNS::ITEM*>& aAdded,
906 std::vector<PNS::ITEM*>& aHeads )
907{
908 NODE *node = nullptr;
909 ITEM_SET current;
910
911 if( m_state == ROUTE_TRACK )
912 {
913 node = m_placer->CurrentNode( true );
914 current = m_placer->Traces();
915 }
916 else if ( m_state == DRAG_SEGMENT )
917 {
918 node = m_dragger->CurrentNode();
919 current = m_dragger->Traces();
920 }
921
922 // There probably should be a debugging assertion and possibly a PNS_LOGGER call here but
923 // I'm not sure how to be proceed WLS.
924 if( !node )
925 return;
926
927 node->GetUpdatedItems( aRemoved, aAdded );
928
929 for( const ITEM* item : current.CItems() )
930 aHeads.push_back( item->Clone() );
931}
932
933
935{
936 if( m_state == ROUTE_TRACK && !m_placer->HasPlacedAnything() )
937 return;
938
939 NODE::ITEM_VECTOR removed;
940 NODE::ITEM_VECTOR added;
941 NODE::ITEM_VECTOR changed;
942
943 aNode->GetUpdatedItems( removed, added );
944
945 for( ITEM* item : removed )
946 {
947 bool is_changed = false;
948
949 // Items in remove/add that share the same parent are just updated versions
950 // We move them to the updated vector to preserve attributes such as UUID and pad data
951 if( item->Parent() )
952 {
953 for( NODE::ITEM_VECTOR::iterator added_it = added.begin();
954 added_it != added.end(); ++added_it )
955 {
956 if( ( *added_it )->Parent() && ( *added_it )->Parent() == item->Parent() )
957 {
958 changed.push_back( *added_it );
959 added.erase( added_it );
960 is_changed = true;
961 break;
962 }
963 }
964 }
965
966 if( !is_changed && !item->IsVirtual() )
967 m_iface->RemoveItem( item );
968 }
969
970 for( ITEM* item : added )
971 {
972 if( !item->IsVirtual() )
973 m_iface->AddItem( item );
974 }
975
976 for( ITEM* item : changed )
977 {
978 if( !item->IsVirtual() )
979 m_iface->UpdateItem( item );
980 }
981
982 m_iface->Commit();
983 m_world->Commit( aNode );
984}
985
986
987bool ROUTER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish, bool aForceCommit )
988{
989 bool rv = false;
990
991 if( m_logger )
992 m_logger->Log( LOGGER::EVT_FIX, aP, aEndItem );
993
994 switch( m_state )
995 {
996 case ROUTE_TRACK:
997 rv = m_placer->FixRoute( aP, aEndItem, aForceFinish );
998 break;
999
1000 case DRAG_SEGMENT:
1001 case DRAG_COMPONENT:
1002 rv = m_dragger->FixRoute( aForceCommit );
1003 break;
1004
1005 default:
1006 break;
1007 }
1008
1009 return rv;
1010}
1011
1013{
1014 return m_leaderSegments;
1015};
1016
1017
1018std::optional<VECTOR2I> ROUTER::UndoLastSegment()
1019{
1020 if( !RoutingInProgress() )
1021 return std::nullopt;
1022
1023 if( m_logger )
1025
1026 return m_placer->UnfixRoute();
1027}
1028
1029
1031{
1032 if( m_state == ROUTE_TRACK )
1033 m_placer->CommitPlacement();
1034
1035 StopRouting();
1036}
1037
1038
1040{
1041 // Update the ratsnest with new changes
1042
1043 if( m_placer )
1044 {
1045 std::vector<NET_HANDLE> nets;
1046 m_placer->GetModifiedNets( nets );
1047
1048 // Update the ratsnest with new changes
1049 for( NET_HANDLE n : nets )
1050 m_iface->UpdateNet( n );
1051 }
1052
1053 if( !RoutingInProgress() )
1054 return;
1055
1056 m_placer.reset();
1057 m_dragger.reset();
1058
1059 m_iface->EraseView();
1060
1061 m_state = IDLE;
1062 m_world->KillChildren();
1063 m_world->ClearRanks();
1064}
1065
1066
1068{
1069 m_iface->EraseView();
1070}
1071
1072
1074{
1075 if( m_state == ROUTE_TRACK )
1076 {
1077 m_placer->FlipPosture();
1078 }
1079}
1080
1081
1082bool ROUTER::SwitchLayer( int aLayer )
1083{
1084 if( m_state == ROUTE_TRACK )
1085 return m_placer->SetLayer( aLayer );
1086
1087 return false;
1088}
1089
1090
1092{
1093 if( m_state == ROUTE_TRACK )
1094 {
1095 bool toggle = !m_placer->IsPlacingVia();
1096 m_placer->ToggleVia( toggle );
1097
1098 if( m_logger )
1099 m_logger->Log( LOGGER::EVT_TOGGLE_VIA, VECTOR2I(), nullptr, &m_sizes );
1100 }
1101}
1102
1103
1104const std::vector<NET_HANDLE> ROUTER::GetCurrentNets() const
1105{
1106 if( m_placer )
1107 return m_placer->CurrentNets();
1108 else if( m_dragger )
1109 return m_dragger->CurrentNets();
1110
1111 return std::vector<NET_HANDLE>();
1112}
1113
1114
1116{
1117 if( m_placer )
1118 return m_placer->CurrentLayer();
1119 else if( m_dragger )
1120 return m_dragger->CurrentLayer();
1121
1122 return -1;
1123}
1124
1125
1127{
1128 return m_logger;
1129}
1130
1131
1133{
1134 if( !m_placer )
1135 return false;
1136
1137 return m_placer->IsPlacingVia();
1138}
1139
1140
1155
1156
1157void ROUTER::SetOrthoMode( bool aEnable )
1158{
1159 if( !m_placer )
1160 return;
1161
1162 m_placer->SetOrthoMode( aEnable );
1163}
1164
1165
1167{
1168 m_mode = aMode;
1169}
1170
1171
1173{
1174 m_iface = aIface;
1175}
1176
1177
1178void ROUTER::BreakSegmentOrArc( ITEM *aItem, const VECTOR2I& aP )
1179{
1180 NODE *node = m_world->Branch();
1181
1182 bool ret = false;
1183
1184 if( aItem->OfKind( ITEM::SEGMENT_T ) )
1185 ret = SplitAdjacentSegments( node, aItem, aP );
1186 else if( aItem->OfKind( ITEM::ARC_T ) )
1187 ret = SplitAdjacentArcs( node, aItem, aP );
1188
1189 if( ret )
1190 {
1191 CommitRouting( node );
1192 }
1193 else
1194 {
1195 delete node;
1196 }
1197}
1198
1199
1201{
1202 if( m_placer )
1203 m_placer->AbortPlacement();
1204}
1205
1206}
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition board_item.h:99
CORNER_MODE
Corner modes.
Definition direction45.h:67
@ ROUNDED_90
H/V with filleted corners.
Definition direction45.h:71
@ MITERED_90
H/V only (90-degree corners)
Definition direction45.h:70
@ ROUNDED_45
H/V/45 with filleted corners.
Definition direction45.h:69
@ MITERED_45
H/V/45 with mitered corners (default)
Definition direction45.h:68
KICAD_T Type() const
Returns the type of object.
Definition eda_item.h:110
Definition pad.h:61
Single track placement algorithm.
const DIFF_PAIR CurrentTrace() const
bool FindDpPrimitivePair(NODE *aWorld, const VECTOR2I &aP, ITEM *aItem, DP_PRIMITIVE_PAIR &aPair, wxString *aErrorMsg=nullptr)
Store starting/ending primitives (pads, vias or segments) for a differential pair.
virtual const ITEM_SET Traces()=0
Function Traces()
bool Empty() const
Definition pns_itemset.h:90
int Size() const
int Count(int aKindMask=-1) const
Definition pns_itemset.h:74
void Add(const LINE &aLine)
bool Contains(ITEM *aItem) const
std::vector< ITEM * > & Items()
Definition pns_itemset.h:95
const std::vector< ITEM * > & CItems() const
Definition pns_itemset.h:96
Base class for PNS router board items.
Definition pns_item.h:98
const PNS_LAYER_RANGE & Layers() const
Definition pns_item.h:212
virtual NET_HANDLE Net() const
Definition pns_item.h:210
void SetNet(NET_HANDLE aNet)
Definition pns_item.h:209
virtual int Layer() const
Definition pns_item.h:216
void SetLayer(int aLayer)
Definition pns_item.h:215
bool OfKind(int aKindMask) const
Definition pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:272
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition pns_joint.h:43
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
ITEM * GetBlockingObstacle() const
Definition pns_line.h:244
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Assign a shape to the line (a polyline/line chain).
Definition pns_line.h:138
VIA & Via()
Definition pns_line.h:212
int SegmentCount() const
Definition pns_line.h:151
void SetWidth(int aWidth)
Set line width.
Definition pns_line.h:162
bool EndsWithVia() const
Definition pns_line.h:204
@ EVT_START_MULTIDRAG
Definition pns_logger.h:68
Keep the router "world" - i.e.
Definition pns_node.h:274
std::vector< ITEM * > ITEM_VECTOR
Definition pns_node.h:285
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
const JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, NET_HANDLE aNet) const
Search for a joint at a given position, layer and belonging to given net.
std::set< OBSTACLE > OBSTACLES
Definition pns_node.h:286
int QueryColliding(const ITEM *aItem, OBSTACLES &aObstacles, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS()) const
Find items colliding (closer than clearance) with the item aItem.
Definition pns_node.cpp:284
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS()) const
Return the expected clearance between items a and b.
Definition pns_node.cpp:148
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition pns_node.cpp:590
Abstract class for a P&S placement/dragging algorithm.
virtual NODE * CurrentNode(bool aLoopsRemoved=false) const =0
Return the most recent board state.
virtual const VECTOR2I & CurrentEnd() const =0
Return the current end of the line(s) being placed/tuned.
virtual const ITEM_SET Traces()=0
Return all routed/tuned traces.
virtual const VECTOR2I & CurrentStart() const =0
Return the current start of the line(s) being placed/tuned.
virtual int CurrentLayer() const =0
Return the layer of currently routed track.
virtual const std::vector< NET_HANDLE > CurrentNets() const =0
Returns the net(s) of currently routed track(s).
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
void updateView(NODE *aNode, ITEM_SET &aCurrent, bool aDragging=false)
void SetMode(ROUTER_MODE aMode)
bool moveDragging(const VECTOR2I &aP, ITEM *aItem)
bool SwitchLayer(int layer)
void StopRouting()
void ClearViewDecorations()
std::vector< PNS::ITEM * > m_leaderSegments
Definition pns_router.h:308
void ToggleCornerMode()
PLACEMENT_ALGO * Placer()
Definition pns_router.h:264
std::vector< PNS::ITEM * > GetLastCommittedLeaderSegments()
NODE * m_lastNode
Definition pns_router.h:303
void ClearWorld()
ROUTER_IFACE * GetInterface() const
Definition pns_router.h:266
void BreakSegmentOrArc(ITEM *aItem, const VECTOR2I &aP)
bool ContinueFromEnd(ITEM **aNewStartItem)
void UpdateSizes(const SIZES_SETTINGS &aSizes)
Applies stored settings.
void SetFailureReason(const wxString &aReason)
Definition pns_router.h:261
LOGGER * Logger()
RouterState m_state
Definition pns_router.h:300
void CommitRouting()
std::unique_ptr< DRAG_ALGO > m_dragger
Definition pns_router.h:306
const ITEM_SET QueryHoverItems(const VECTOR2I &aP, int aSlopRadius=0)
void SetInterface(ROUTER_IFACE *aIface)
void markViolations(NODE *aNode, ITEM_SET &aCurrent, NODE::ITEM_VECTOR &aRemoved)
void SyncWorld()
std::unique_ptr< PLACEMENT_ALGO > m_placer
Definition pns_router.h:305
bool isStartingPointRoutable(const VECTOR2I &aWhere, ITEM *aItem, int aLayer)
ROUTER_IFACE * m_iface
Definition pns_router.h:310
bool IsPlacingVia() const
void FlipPosture()
RULE_RESOLVER * GetRuleResolver() const
Definition pns_router.h:228
SIZES_SETTINGS m_sizes
Definition pns_router.h:315
DEBUG_DECORATOR * dbg() const
Definition pns_router.h:279
ROUTING_SETTINGS & Settings()
Definition pns_router.h:240
DRAG_ALGO * GetDragger()
Definition pns_router.h:187
bool movePlacing(const VECTOR2I &aP, ITEM *aItem)
bool RoutingInProgress() const
BOX2I m_visibleViewArea
Definition pns_router.h:299
static ROUTER * GetInstance()
std::optional< VECTOR2I > UndoLastSegment()
void AbortPlacement()
LOGGER * m_logger
Definition pns_router.h:317
void SetOrthoMode(bool aEnable)
bool StartDragging(const VECTOR2I &aP, ITEM *aItem, int aDragMode=DM_ANY)
bool StartRouting(const VECTOR2I &aP, ITEM *aItem, int aLayer, const ITEM_SET &aAuxItems=ITEM_SET())
bool areWeLengthTuning() const
int GetCurrentLayer() const
void GetUpdatedItems(std::vector< PNS::ITEM * > &aRemoved, std::vector< PNS::ITEM * > &aAdded, std::vector< PNS::ITEM * > &aHeads)
SIZES_SETTINGS & Sizes()
Definition pns_router.h:259
bool FixRoute(const VECTOR2I &aP, ITEM *aItem, bool aForceFinish, bool aForceCommit)
std::unique_ptr< NODE > m_world
Definition pns_router.h:302
void ToggleViaPlacement()
ROUTING_SETTINGS * m_settings
Definition pns_router.h:314
bool hasDiffPairMembers(const ITEM_SET &aItems) const
const std::vector< NET_HANDLE > GetCurrentNets() const
ROUTER_MODE m_mode
Definition pns_router.h:316
bool GetNearestRatnestAnchor(VECTOR2I &aOtherEnd, PNS_LAYER_RANGE &aOtherEndLayers, ITEM *&aOtherEndItem)
bool Move(const VECTOR2I &aP, ITEM *aItem)
virtual void ClearCacheForItems(std::vector< const ITEM * > &aItems)
Definition pns_node.h:202
virtual void ClearTemporaryCaches()
Definition pns_node.h:204
virtual int Clearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0
virtual void ClearCaches()
Definition pns_node.h:203
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, PNS_LAYER_RANGE &aLayers, ITEM *&aItem)
void SetSpreadableItems(const ITEM_SET &aAuxItems)
const ITEM_SET & GetSpreadableItems() const
Represent a contiguous set of PCB layers.
int Start() const
bool Overlaps(const PNS_LAYER_RANGE &aOther) const
static PNS_LAYER_RANGE All()
Shortcut for comparisons/overlap tests.
bool IsMultilayer() const
Definition seg.h:38
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Handle a list of polygons defining a copper zone.
Definition zone.h:70
const wxString & GetZoneName() const
Definition zone.h:160
bool HasKeepoutParametersSet() const
Accessor to determine if any keepout parameters are set.
Definition zone.h:825
static bool empty(const wxTextEntryBase *aCtrl)
#define _(s)
@ Edge_Cuts
Definition layer_ids.h:108
Push and Shove diff pair dimensions (gap) settings dialog.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Snaps the point aP to segment aSeg.
static ROUTER * theRouter
void * NET_HANDLE
Definition pns_item.h:55
bool SplitAdjacentArcs(NODE *aNode, ITEM *aArc, const VECTOR2I &aP)
Snaps the point aP to arc aArc.
ROUTER_MODE
Definition pns_router.h:68
@ PNS_MODE_ROUTE_SINGLE
Definition pns_router.h:69
@ PNS_MODE_ROUTE_DIFF_PAIR
Definition pns_router.h:70
@ PNS_MODE_SPREAD_TRACKS
Definition pns_router.h:74
@ PNS_MODE_TUNE_DIFF_PAIR
Definition pns_router.h:72
@ PNS_MODE_TUNE_SINGLE
Definition pns_router.h:71
@ PNS_MODE_TUNE_DIFF_PAIR_SKEW
Definition pns_router.h:73
DRAG_MODE
Definition pns_router.h:78
@ DM_BLOCK
Definition pns_router.h:86
@ MK_VIOLATION
Definition pns_item.h:44
@ NPTH
like PAD_PTH, but not plated mechanical use only, no connection allowed
Definition padstack.h:104
#define PNS_DBG(dbg, method,...)
#define PNS_HEAD_TRACE
void SetFixedClearanceOverride(int aClearance)
Definition pns_node.h:147
Hold an object colliding with another object, along with some useful data about the collision.
Definition pns_node.h:98
static std::vector< int > candidates(const SEGMENT_INDEX &aIndex, const SEG &aQuery, int aPadding)
int clearance
@ PCB_TEXTBOX_T
class PCB_TEXTBOX, wrapped text on a layer
Definition typeinfo.h:85
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition typeinfo.h:100
@ PCB_TEXT_T
class PCB_TEXT, text on a layer
Definition typeinfo.h:84
@ PCB_FIELD_T
class PCB_FIELD, text associated with a footprint property
Definition typeinfo.h:82
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition typeinfo.h:79
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708