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 (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <cstdio>
23#include <memory>
24#include <vector>
25
26#include <view/view.h>
27#include <view/view_group.h>
29
30#include <advanced_config.h>
32
33#include <pcb_painter.h>
34#include <pcbnew_settings.h>
35#include <pad.h>
36#include <zone.h>
37
38#include <geometry/shape.h>
39
40#include "pns_node.h"
41#include "pns_line_placer.h"
42#include "pns_line.h"
43#include "pns_solid.h"
44#include "pns_utils.h"
45#include "pns_router.h"
46#include "pns_shove.h"
47#include "pns_dragger.h"
49#include "pns_topology.h"
51#include "pns_meander_placer.h"
54
55namespace PNS {
56
57// an ugly singleton for drawing debug items within the router context.
58// To be fixed sometime in the future.
60
62{
63 theRouter = this;
64
65 m_state = IDLE;
67
68 m_logger = nullptr;
69
70 if( ADVANCED_CFG::GetCfg().m_EnableRouterDump )
71 m_logger = new LOGGER;
72
73 // Initialize all other variables:
74 m_lastNode = nullptr;
75 m_iterLimit = 0;
76 m_settings = nullptr;
77 m_iface = nullptr;
79}
80
81
83{
84 return theRouter;
85}
86
87
89{
90 ClearWorld();
91 theRouter = nullptr;
92 delete m_logger;
93}
94
95
97{
98 ClearWorld();
99
100 m_world = std::make_unique<NODE>( );
101 m_iface->SyncWorld( m_world.get() );
102 m_world->FixupVirtualVias();
103}
104
105
107{
108 if( m_world )
109 {
110 m_world->SetRuleResolver( nullptr );
111 m_world->KillChildren();
112 m_world.reset();
113 }
114
115 m_placer.reset();
116}
117
118
120{
121 return m_state != IDLE;
122}
123
124
125const ITEM_SET ROUTER::QueryHoverItems( const VECTOR2I& aP, bool aUseClearance )
126{
127 NODE* node = nullptr;
128 int clearance = 0;
129
130 if( m_state == IDLE || m_placer == nullptr )
131 {
132 node = m_world.get();
133 clearance = 0;
134 }
135 else if( m_mode == PNS_MODE_ROUTE_SINGLE )
136 {
137 node = m_placer->CurrentNode();
138 clearance = m_sizes.Clearance() + m_sizes.TrackWidth() / 2;
139 }
140 else if( m_mode == PNS_MODE_ROUTE_DIFF_PAIR )
141 {
142 node = m_placer->CurrentNode();
143 clearance = m_sizes.Clearance() + m_sizes.DiffPairWidth() / 2;
144 }
145
146 if( aUseClearance )
147 {
148 NODE::OBSTACLES obs;
149 SEGMENT test( SEG( aP, aP ), nullptr );
151
152 test.SetWidth( 1 );
153 test.SetLayers( LAYER_RANGE::All() );
154
155 opts.m_differentNetsOnly = false;
156 opts.m_overrideClearance = clearance;
157
158 PNS::ITEM_SET ret;
159
160 wxCHECK( node, ret );
161
162 node->QueryColliding( &test, obs, opts );
163
164 for( const OBSTACLE& obstacle : obs )
165 ret.Add( obstacle.m_item, false );
166
167 return ret;
168 }
169 else
170 {
171 return node->HitTest( aP );
172 }
173}
174
175
176bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM* aItem, int aDragMode )
177{
178 return StartDragging( aP, ITEM_SET( aItem ), aDragMode );
179}
180
181
182bool ROUTER::StartDragging( const VECTOR2I& aP, ITEM_SET aStartItems, int aDragMode )
183{
184 if( aStartItems.Empty() )
185 return false;
186
188
189 if( aStartItems.Count( ITEM::SOLID_T ) == aStartItems.Size() )
190 {
191 m_dragger = std::make_unique<COMPONENT_DRAGGER>( this );
194 }
195 else
196 {
197 if( aDragMode & DM_FREE_ANGLE )
199 else
201
202 m_dragger = std::make_unique<DRAGGER>( this );
204 }
205
206 m_dragger->SetMode( static_cast<PNS::DRAG_MODE>( aDragMode ) );
207 m_dragger->SetWorld( m_world.get() );
208 m_dragger->SetLogger( m_logger );
209 m_dragger->SetDebugDecorator( m_iface->GetDebugDecorator() );
210
211 if( m_logger )
212 m_logger->Clear();
213
214 if( m_logger && aStartItems.Size() )
215 m_logger->Log( LOGGER::EVT_START_DRAG, aP, aStartItems[0] );
216
217 if( m_dragger->Start( aP, aStartItems ) )
218 {
219 return true;
220 }
221 else
222 {
223 m_dragger.reset();
224 m_state = IDLE;
225 return false;
226 }
227}
228
229
230bool ROUTER::isStartingPointRoutable( const VECTOR2I& aWhere, ITEM* aStartItem, int aLayer )
231{
232 if( Settings().AllowDRCViolations() )
233 return true;
234
236 {
238 {
239 SetFailureReason( _( "Diff pair gap is less than board minimum clearance." ) );
240 return false;
241 }
242 }
243
244 ITEM_SET candidates = QueryHoverItems( aWhere );
245 wxString failureReason;
246
247 for( ITEM* item : candidates.Items() )
248 {
249 // Edge cuts are put on all layers, but they're not *really* on all layers
250 if( item->BoardItem() && item->BoardItem()->GetLayer() == Edge_Cuts )
251 continue;
252
253 if( !item->Layers().Overlaps( aLayer ) )
254 continue;
255
256 if( item->IsRoutable() )
257 {
258 failureReason = wxEmptyString;
259 break;
260 }
261 else
262 {
263 BOARD_ITEM* parent = item->BoardItem();
264
265 switch( parent->Type() )
266 {
267 case PCB_PAD_T:
268 {
269 PAD* pad = static_cast<PAD*>( parent );
270
271 if( pad->GetAttribute() == PAD_ATTRIB::NPTH )
272 failureReason = _( "Cannot start routing from a non-plated hole." );
273 }
274 break;
275
276 case PCB_ZONE_T:
277 {
278 ZONE* zone = static_cast<ZONE*>( parent );
279
280 if( !zone->GetZoneName().IsEmpty() )
281 {
282 failureReason = wxString::Format( _( "Rule area '%s' disallows tracks." ),
283 zone->GetZoneName() );
284 }
285 else
286 {
287 failureReason = _( "Rule area disallows tracks." );
288 }
289 }
290 break;
291
292 case PCB_FIELD_T:
293 case PCB_TEXT_T:
294 case PCB_TEXTBOX_T:
295 failureReason = _( "Cannot start routing from a text item." );
296 break;
297
298 default:
299 break;
300 }
301 }
302 }
303
304 if( !failureReason.IsEmpty() )
305 {
306 SetFailureReason( failureReason );
307 return false;
308 }
309
310 VECTOR2I startPoint = aWhere;
311
313 {
314 SHAPE_LINE_CHAIN dummyStartSeg;
315 LINE dummyStartLine;
316
317 dummyStartSeg.Append( startPoint );
318 dummyStartSeg.Append( startPoint, true );
319
320 dummyStartLine.SetShape( dummyStartSeg );
321 dummyStartLine.SetLayer( aLayer );
322 dummyStartLine.SetNet( aStartItem ? aStartItem->Net() : 0 );
323 dummyStartLine.SetWidth( m_sizes.TrackWidth() );
324
325 if( m_world->CheckColliding( &dummyStartLine, ITEM::ANY_T ) )
326 {
327 // If the only reason we collide is track width; it's better to allow the user to start
328 // anyway and just highlight the resulting collisions, so they can change width later.
329 dummyStartLine.SetWidth( m_sizes.BoardMinTrackWidth() );
330
331 if( m_world->CheckColliding( &dummyStartLine, ITEM::ANY_T ) )
332 {
333 ITEM_SET dummyStartSet( &dummyStartLine );
334 NODE::ITEM_VECTOR highlightedItems;
335
336 markViolations( m_world.get(), dummyStartSet, highlightedItems );
337
338 for( ITEM* item : highlightedItems )
339 m_iface->HideItem( item );
340
341 SetFailureReason( _( "The routing start point violates DRC." ) );
342 return false;
343 }
344 }
345 }
346 else if( m_mode == PNS_MODE_ROUTE_DIFF_PAIR )
347 {
348 if( !aStartItem )
349 {
350 SetFailureReason( _( "Cannot start a differential pair in the middle of nowhere." ) );
351 return false;
352 }
353
354 DP_PRIMITIVE_PAIR dpPair;
355 wxString errorMsg;
356
357 if( !DIFF_PAIR_PLACER::FindDpPrimitivePair( m_world.get(), startPoint, aStartItem, dpPair,
358 &errorMsg ) )
359 {
360 SetFailureReason( errorMsg );
361 return false;
362 }
363
364 SHAPE_LINE_CHAIN dummyStartSegA;
365 SHAPE_LINE_CHAIN dummyStartSegB;
366 LINE dummyStartLineA;
367 LINE dummyStartLineB;
368
369 dummyStartSegA.Append( dpPair.AnchorN() );
370 dummyStartSegA.Append( dpPair.AnchorN(), true );
371
372 dummyStartSegB.Append( dpPair.AnchorP() );
373 dummyStartSegB.Append( dpPair.AnchorP(), true );
374
375 dummyStartLineA.SetShape( dummyStartSegA );
376 dummyStartLineA.SetLayer( aLayer );
377 dummyStartLineA.SetNet( dpPair.PrimN()->Net() );
378 dummyStartLineA.SetWidth( m_sizes.DiffPairWidth() );
379
380 dummyStartLineB.SetShape( dummyStartSegB );
381 dummyStartLineB.SetLayer( aLayer );
382 dummyStartLineB.SetNet( dpPair.PrimP()->Net() );
383 dummyStartLineB.SetWidth( m_sizes.DiffPairWidth() );
384
385 if( m_world->CheckColliding( &dummyStartLineA, ITEM::ANY_T )
386 || m_world->CheckColliding( &dummyStartLineB, ITEM::ANY_T ) )
387 {
388 // If the only reason we collide is track width; it's better to allow the user to start
389 // anyway and just highlight the resulting collisions, so they can change width later.
390 dummyStartLineA.SetWidth( m_sizes.BoardMinTrackWidth() );
391 dummyStartLineB.SetWidth( m_sizes.BoardMinTrackWidth() );
392
393 if( m_world->CheckColliding( &dummyStartLineA, ITEM::ANY_T )
394 || m_world->CheckColliding( &dummyStartLineB, ITEM::ANY_T ) )
395 {
396 ITEM_SET dummyStartSet;
397 NODE::ITEM_VECTOR highlightedItems;
398
399 dummyStartSet.Add( dummyStartLineA );
400 dummyStartSet.Add( dummyStartLineB );
401 markViolations( m_world.get(), dummyStartSet, highlightedItems );
402
403 for( ITEM* item : highlightedItems )
404 m_iface->HideItem( item );
405
406 SetFailureReason( _( "The routing start point violates DRC." ) );
407 return false;
408 }
409 }
410 }
411
412 return true;
413}
414
415
416bool ROUTER::StartRouting( const VECTOR2I& aP, ITEM* aStartItem, int aLayer )
417{
419
420 if( !isStartingPointRoutable( aP, aStartItem, aLayer ) )
421 return false;
422
424
425 switch( m_mode )
426 {
428 m_placer = std::make_unique<LINE_PLACER>( this );
429 break;
430
432 m_placer = std::make_unique<DIFF_PAIR_PLACER>( this );
433 break;
434
436 m_placer = std::make_unique<MEANDER_PLACER>( this );
437 break;
438
440 m_placer = std::make_unique<DP_MEANDER_PLACER>( this );
441 break;
442
444 m_placer = std::make_unique<MEANDER_SKEW_PLACER>( this );
445 break;
446
447 default:
448 return false;
449 }
450
451 m_placer->UpdateSizes( m_sizes );
452 m_placer->SetLayer( aLayer );
453 m_placer->SetDebugDecorator( m_iface->GetDebugDecorator() );
454 m_placer->SetLogger( m_logger );
455
456 if( m_placer->Start( aP, aStartItem ) )
457 {
459
460 if( m_logger )
461 {
462 m_logger->Clear();
463 m_logger->Log( LOGGER::EVT_START_ROUTE, aP, aStartItem, &m_sizes );
464 }
465
466 return true;
467 }
468 else
469 {
470 m_state = IDLE;
471 return false;
472 }
473}
474
475
476bool ROUTER::Move( const VECTOR2I& aP, ITEM* endItem )
477{
478 if( m_logger )
479 m_logger->Log( LOGGER::EVT_MOVE, aP, endItem );
480
481 switch( m_state )
482 {
483 case ROUTE_TRACK:
484 return movePlacing( aP, endItem );
485
486 case DRAG_SEGMENT:
487 case DRAG_COMPONENT:
488 return moveDragging( aP, endItem );
489
490 default:
491 break;
492 }
493
494 return false;
495}
496
497
498bool ROUTER::getNearestRatnestAnchor( VECTOR2I& aOtherEnd, LAYER_RANGE& aOtherEndLayers,
499 ITEM*& aOtherEndItem )
500{
501 // Can't finish something with no connections
502 if( GetCurrentNets().empty() )
503 return false;
504
505 PLACEMENT_ALGO* placer = Placer();
506
507 if( placer == nullptr || placer->Traces().Size() == 0 )
508 return false;
509
510 LINE* trace = dynamic_cast<LINE*>( placer->Traces()[0] );
511
512 if( trace == nullptr )
513 return false;
514
515 PNS::NODE* lastNode = placer->CurrentNode( true );
516 PNS::TOPOLOGY topo( lastNode );
517
518 // If the user has drawn a line, get the anchor nearest to the line end
519 if( trace->SegmentCount() > 0 )
520 {
521 return topo.NearestUnconnectedAnchorPoint( trace, aOtherEnd, aOtherEndLayers,
522 aOtherEndItem );
523 }
524
525 // Otherwise, find the closest anchor to our start point
526
527 // Get joint from placer start item
528 const JOINT* jt = lastNode->FindJoint( placer->CurrentStart(), placer->CurrentLayer(),
529 placer->CurrentNets()[0] );
530
531 if( !jt )
532 return false;
533
534 // Get unconnected item from joint
535 int anchor;
536 PNS::ITEM* it = topo.NearestUnconnectedItem( jt, &anchor );
537
538 if( !it )
539 return false;
540
541 aOtherEnd = it->Anchor( anchor );
542 aOtherEndLayers = it->Layers();
543 aOtherEndItem = it;
544
545 return true;
546}
547
548
550{
551 if( m_state != ROUTE_TRACK )
552 return false;
553
554 PLACEMENT_ALGO* placer = Placer();
555
556 if( placer == nullptr || placer->Traces().Size() == 0 )
557 return false;
558
559 LINE* current = dynamic_cast<LINE*>( placer->Traces()[0] );
560
561 if( current == nullptr )
562 return false;
563
564 // Get our current line and position and nearest ratsnest to them if it exists
565 VECTOR2I otherEnd;
566 LAYER_RANGE otherEndLayers;
567 ITEM* otherEndItem = nullptr;
568
569 // Get the anchor nearest to the end of the trace the user is routing
570 if( !getNearestRatnestAnchor( otherEnd, otherEndLayers, otherEndItem ) )
571 return false;
572
573 // Keep moving until we don't change position or hit the limit
574 int triesLeft = 5;
575 VECTOR2I moveResultPoint;
576
577 do
578 {
579 moveResultPoint = placer->CurrentEnd();
580 Move( otherEnd, otherEndItem );
581 triesLeft--;
582 } while( placer->CurrentEnd() != moveResultPoint && triesLeft );
583
584 // If we've made it, fix the route and we're done
585 if( moveResultPoint == otherEnd && otherEndLayers.Overlaps( GetCurrentLayer() ) )
586 return FixRoute( otherEnd, otherEndItem, false );
587
588 return false;
589}
590
591
593{
594 PLACEMENT_ALGO* placer = Placer();
595
596 if( placer == nullptr || placer->Traces().Size() == 0 )
597 return false;
598
599 LINE* current = dynamic_cast<LINE*>( placer->Traces()[0] );
600
601 if( current == nullptr )
602 return false;
603
604 int currentLayer = GetCurrentLayer();
605 VECTOR2I currentEnd = placer->CurrentEnd();
606 VECTOR2I otherEnd;
607 LAYER_RANGE otherEndLayers;
608 ITEM* otherEndItem = nullptr;
609
610 // Get the anchor nearest to the end of the trace the user is routing
611 if( !getNearestRatnestAnchor( otherEnd, otherEndLayers, otherEndItem ) )
612 return false;
613
615
616 // Commit whatever we've fixed and restart routing from the other end
617 int nextLayer = otherEndLayers.Overlaps( currentLayer ) ? currentLayer : otherEndLayers.Start();
618
619 if( !StartRouting( otherEnd, otherEndItem, nextLayer ) )
620 return false;
621
622 // Attempt to route to our current position
623 Move( currentEnd, current );
624
625 return true;
626}
627
628
629bool ROUTER::moveDragging( const VECTOR2I& aP, ITEM* aEndItem )
630{
632
633 bool ret = m_dragger->Drag( aP );
634 ITEM_SET dragged = m_dragger->Traces();
635
636 updateView( m_dragger->CurrentNode(), dragged, true );
637 return ret;
638}
639
640
641void ROUTER::markViolations( NODE* aNode, ITEM_SET& aCurrent, NODE::ITEM_VECTOR& aRemoved )
642{
643 auto updateItem =
644 [&]( ITEM* currentItem, ITEM* itemToMark )
645 {
646 std::unique_ptr<ITEM> tmp( itemToMark->Clone() );
647
648 int clearance;
649 bool removeOriginal = true;
650
651 clearance = aNode->GetClearance( currentItem, itemToMark );
652
653 if( itemToMark->Layers().IsMultilayer() && !currentItem->Layers().IsMultilayer() )
654 tmp->SetLayer( currentItem->Layer() );
655
656 if( itemToMark->IsCompoundShapePrimitive() )
657 {
658 // We're only highlighting one (or more) of several primitives so we don't
659 // want all the other parts of the object to disappear
660 removeOriginal = false;
661 }
662
663 m_iface->DisplayItem( tmp.get(), clearance );
664
665 if( removeOriginal )
666 aRemoved.push_back( itemToMark );
667 };
668
669 for( ITEM* item : aCurrent.Items() )
670 {
671 NODE::OBSTACLES obstacles;
672
673 aNode->QueryColliding( item, obstacles );
674
675 if( item->OfKind( ITEM::LINE_T ) )
676 {
677 LINE* l = static_cast<LINE*>( item );
678
679 if( l->EndsWithVia() )
680 {
681 VIA v( l->Via() );
682 aNode->QueryColliding( &v, obstacles );
683 }
684 }
685
686 ITEM_SET draggedItems;
687
688 if( GetDragger() )
689 draggedItems = GetDragger()->Traces();
690
691 for( const OBSTACLE& obs : obstacles )
692 {
693 // Don't mark items being dragged; only board items they collide with
694 if( draggedItems.Contains( obs.m_item ) )
695 continue;
696
697 obs.m_item->Mark( obs.m_item->Marker() | MK_VIOLATION );
698 updateItem( item, obs.m_item );
699 }
700
701 if( item->Kind() == ITEM::LINE_T )
702 {
703 LINE* line = static_cast<LINE*>( item );
704
705 // Show clearance on any blocking obstacles
706 if( line->GetBlockingObstacle() )
707 updateItem( item, line->GetBlockingObstacle() );
708 }
709 }
710}
711
712
713void ROUTER::updateView( NODE* aNode, ITEM_SET& aCurrent, bool aDragging )
714{
715 NODE::ITEM_VECTOR removed, added;
716 NODE::OBSTACLES obstacles;
717
718 if( !aNode )
719 return;
720
721 markViolations( aNode, aCurrent, removed );
722
723 aNode->GetUpdatedItems( removed, added );
724
725 std::vector<const PNS::ITEM*> cacheCheckItems( added.begin(), added.end() );
726 GetRuleResolver()->ClearCacheForItems( cacheCheckItems );
727
728 for( ITEM* item : added )
729 {
730 int clearance = GetRuleResolver()->Clearance( item, nullptr );
731 m_iface->DisplayItem( item, clearance, aDragging );
732 }
733
734 for( ITEM* item : removed )
735 m_iface->HideItem( item );
736}
737
738
740{
741 m_sizes = aSizes;
742
743 // Change track/via size settings
744 if( m_state == ROUTE_TRACK )
745 m_placer->UpdateSizes( m_sizes );
746}
747
748
749bool ROUTER::movePlacing( const VECTOR2I& aP, ITEM* aEndItem )
750{
752
753 bool ret = m_placer->Move( aP, aEndItem );
754 ITEM_SET current = m_placer->Traces();
755
756 for( const ITEM* item : current.CItems() )
757 {
758 if( !item->OfKind( ITEM::LINE_T ) )
759 continue;
760
761 const LINE* l = static_cast<const LINE*>( item );
762 int clearance = GetRuleResolver()->Clearance( item, nullptr );
763
764 m_iface->DisplayItem( l, clearance, false, true );
765
766 if( l->EndsWithVia() )
767 {
768 const VIA& via = l->Via();
769 clearance = GetRuleResolver()->Clearance( &via, nullptr );
770
771 if( via.HasHole() )
772 {
773 int holeClearance = GetRuleResolver()->Clearance( via.Hole(), nullptr );
774 int annularWidth = std::max( 0, via.Diameter() - via.Drill() ) / 2;
775 int excessHoleClearance = holeClearance - annularWidth;
776
777 if( excessHoleClearance > clearance )
778 clearance = excessHoleClearance;
779 }
780
781 m_iface->DisplayItem( &l->Via(), clearance, false, true );
782 }
783 }
784
785 //ITEM_SET tmp( &current );
786
787 updateView( m_placer->CurrentNode( true ), current );
788
789 return ret;
790}
791
792
793void ROUTER::GetUpdatedItems( std::vector<PNS::ITEM*>& aRemoved, std::vector<PNS::ITEM*>& aAdded,
794 std::vector<PNS::ITEM*>& aHeads )
795{
796 NODE *node = nullptr;
797 ITEM_SET current;
798
799 if( m_state == ROUTE_TRACK )
800 {
801 node = m_placer->CurrentNode( true );
802 current = m_placer->Traces();
803 }
804 else if ( m_state == DRAG_SEGMENT )
805 {
806 node = m_dragger->CurrentNode();
807 current = m_dragger->Traces();
808 }
809
810 // There probably should be a debugging assertion and possibly a PNS_LOGGER call here but
811 // I'm not sure how to be proceed WLS.
812 if( !node )
813 return;
814
815 node->GetUpdatedItems( aRemoved, aAdded );
816
817 for( const ITEM* item : current.CItems() )
818 aHeads.push_back( item->Clone() );
819}
820
821
823{
824 if( m_state == ROUTE_TRACK && !m_placer->HasPlacedAnything() )
825 return;
826
827 NODE::ITEM_VECTOR removed;
828 NODE::ITEM_VECTOR added;
829 NODE::ITEM_VECTOR changed;
830
831 aNode->GetUpdatedItems( removed, added );
832
833 for( ITEM* item : removed )
834 {
835 bool is_changed = false;
836
837 // Items in remove/add that share the same parent are just updated versions
838 // We move them to the updated vector to preserve attributes such as UUID and pad data
839 if( item->Parent() )
840 {
841 for( NODE::ITEM_VECTOR::iterator added_it = added.begin();
842 added_it != added.end(); ++added_it )
843 {
844 if( ( *added_it )->Parent() && ( *added_it )->Parent() == item->Parent() )
845 {
846 changed.push_back( *added_it );
847 added.erase( added_it );
848 is_changed = true;
849 break;
850 }
851 }
852 }
853
854 if( !is_changed && !item->IsVirtual() )
855 m_iface->RemoveItem( item );
856 }
857
858 for( ITEM* item : added )
859 {
860 if( !item->IsVirtual() )
861 m_iface->AddItem( item );
862 }
863
864 for( ITEM* item : changed )
865 {
866 if( !item->IsVirtual() )
867 m_iface->UpdateItem( item );
868 }
869
870 m_iface->Commit();
871 m_world->Commit( aNode );
872}
873
874
875bool ROUTER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
876{
877 bool rv = false;
878
879 if( m_logger )
880 m_logger->Log( LOGGER::EVT_FIX, aP, aEndItem );
881
882 switch( m_state )
883 {
884 case ROUTE_TRACK:
885 rv = m_placer->FixRoute( aP, aEndItem, aForceFinish );
886 break;
887
888 case DRAG_SEGMENT:
889 case DRAG_COMPONENT:
890 rv = m_dragger->FixRoute();
891 break;
892
893 default:
894 break;
895 }
896
897 return rv;
898}
899
900
901std::optional<VECTOR2I> ROUTER::UndoLastSegment()
902{
903 if( !RoutingInProgress() )
904 return std::nullopt;
905
906 if( m_logger )
908
909 return m_placer->UnfixRoute();
910}
911
912
914{
915 if( m_state == ROUTE_TRACK )
916 m_placer->CommitPlacement();
917
918 StopRouting();
919}
920
921
923{
924 // Update the ratsnest with new changes
925
926 if( m_placer )
927 {
928 std::vector<NET_HANDLE> nets;
929 m_placer->GetModifiedNets( nets );
930
931 // Update the ratsnest with new changes
932 for( NET_HANDLE n : nets )
933 m_iface->UpdateNet( n );
934 }
935
936 if( !RoutingInProgress() )
937 return;
938
939 m_placer.reset();
940 m_dragger.reset();
941
943
944 m_state = IDLE;
945 m_world->KillChildren();
946 m_world->ClearRanks();
947}
948
949
951{
953}
954
955
957{
958 if( m_state == ROUTE_TRACK )
959 {
960 m_placer->FlipPosture();
961 }
962}
963
964
965bool ROUTER::SwitchLayer( int aLayer )
966{
967 if( m_state == ROUTE_TRACK )
968 return m_placer->SetLayer( aLayer );
969
970 return false;
971}
972
973
975{
976 if( m_state == ROUTE_TRACK )
977 {
978 bool toggle = !m_placer->IsPlacingVia();
979 m_placer->ToggleVia( toggle );
980
981 if( m_logger )
983 }
984}
985
986
987const std::vector<NET_HANDLE> ROUTER::GetCurrentNets() const
988{
989 if( m_placer )
990 return m_placer->CurrentNets();
991 else if( m_dragger )
992 return m_dragger->CurrentNets();
993
994 return std::vector<NET_HANDLE>();
995}
996
997
999{
1000 if( m_placer )
1001 return m_placer->CurrentLayer();
1002 else if( m_dragger )
1003 return m_dragger->CurrentLayer();
1004
1005 return -1;
1006}
1007
1008
1010{
1011 return m_logger;
1012}
1013
1014
1016{
1017 if( !m_placer )
1018 return false;
1019
1020 return m_placer->IsPlacingVia();
1021}
1022
1023
1025{
1027
1028 switch( m_settings->GetCornerMode() )
1029 {
1034 }
1035
1036 m_settings->SetCornerMode( mode );
1037}
1038
1039
1040void ROUTER::SetOrthoMode( bool aEnable )
1041{
1042 if( !m_placer )
1043 return;
1044
1045 m_placer->SetOrthoMode( aEnable );
1046}
1047
1048
1050{
1051 m_mode = aMode;
1052}
1053
1054
1056{
1057 m_iface = aIface;
1058}
1059
1060
1061void ROUTER::BreakSegment( ITEM *aItem, const VECTOR2I& aP )
1062{
1063 NODE *node = m_world->Branch();
1064
1065 LINE_PLACER placer( this );
1066
1067 if( placer.SplitAdjacentSegments( node, aItem, aP ) )
1068 {
1069 CommitRouting( node );
1070 }
1071 else
1072 {
1073 delete node;
1074 }
1075}
1076
1077}
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:77
void SetMaximum()
Definition: box2.h:64
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:97
Represent a contiguous set of PCB layers.
Definition: pns_layerset.h:32
int Start() const
Definition: pns_layerset.h:82
bool IsMultilayer() const
Definition: pns_layerset.h:77
static LAYER_RANGE All()
Definition: pns_layerset.h:125
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
Definition: pad.h:58
static 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.
const VECTOR2I & AnchorN() const
ITEM * PrimN() const
const VECTOR2I & AnchorP() const
ITEM * PrimP() const
virtual const ITEM_SET Traces()=0
Function Traces()
bool Empty() const
Definition: pns_itemset.h:82
int Size() const
Definition: pns_itemset.h:112
int Count(int aKindMask=-1) const
Definition: pns_itemset.h:66
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
bool Contains(ITEM *aItem) const
Definition: pns_itemset.h:151
std::vector< ITEM * > & Items()
Definition: pns_itemset.h:87
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:97
virtual NET_HANDLE Net() const
Definition: pns_item.h:193
void SetNet(NET_HANDLE aNet)
Definition: pns_item.h:192
virtual int Layer() const
Definition: pns_item.h:199
void SetLayer(int aLayer)
Definition: pns_item.h:198
const LAYER_RANGE & Layers() const
Definition: pns_item.h:195
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:236
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
Single track placement algorithm.
bool SplitAdjacentSegments(NODE *aNode, ITEM *aSeg, const VECTOR2I &aP)
Check if point aP lies on segment aSeg.
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
ITEM * GetBlockingObstacle() const
Definition: pns_line.h:204
void SetShape(const SHAPE_LINE_CHAIN &aLine)
Return the shape of the line.
Definition: pns_line.h:125
VIA & Via()
Definition: pns_line.h:193
int SegmentCount() const
Definition: pns_line.h:138
void SetWidth(int aWidth)
Return line width.
Definition: pns_line.h:148
bool EndsWithVia() const
Definition: pns_line.h:188
void Clear()
Definition: pns_logger.cpp:40
@ EVT_START_ROUTE
Definition: pns_logger.h:47
@ EVT_START_DRAG
Definition: pns_logger.h:48
@ EVT_TOGGLE_VIA
Definition: pns_logger.h:52
void Log(EVENT_TYPE evt, const VECTOR2I &pos=VECTOR2I(), const ITEM *item=nullptr, const SIZES_SETTINGS *sizes=nullptr)
Definition: pns_logger.cpp:46
Keep the router "world" - i.e.
Definition: pns_node.h:198
std::vector< ITEM * > ITEM_VECTOR
Definition: pns_node.h:209
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:129
void GetUpdatedItems(ITEM_VECTOR &aRemoved, ITEM_VECTOR &aAdded)
Return the list of items removed and added in this branch with respect to the root branch.
Definition: pns_node.cpp:1393
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.
Definition: pns_node.cpp:1189
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:210
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:252
const ITEM_SET HitTest(const VECTOR2I &aPoint) const
Find all items that contain the point aPoint.
Definition: pns_node.cpp:466
virtual NODE * CurrentNode(bool aLoopsRemoved=false) const =0
Function CurrentNode()
virtual const VECTOR2I & CurrentEnd() const =0
Function CurrentEnd()
virtual const ITEM_SET Traces()=0
Function Traces()
virtual const VECTOR2I & CurrentStart() const =0
Function CurrentStart()
virtual int CurrentLayer() const =0
Function CurrentLayer()
virtual const std::vector< NET_HANDLE > CurrentNets() const =0
Function CurrentNets()
virtual void RemoveItem(ITEM *aItem)=0
virtual void UpdateItem(ITEM *aItem)=0
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
virtual void HideItem(ITEM *aItem)=0
virtual void Commit()=0
virtual void UpdateNet(NET_HANDLE aNet)=0
virtual void AddItem(ITEM *aItem)=0
virtual void EraseView()=0
virtual void SyncWorld(NODE *aNode)=0
virtual void DisplayItem(const ITEM *aItem, int aClearance, bool aEdit=false, bool aIsHeadTrace=false)=0
void updateView(NODE *aNode, ITEM_SET &aCurrent, bool aDragging=false)
Definition: pns_router.cpp:713
void SetMode(ROUTER_MODE aMode)
bool moveDragging(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:629
bool SwitchLayer(int layer)
Definition: pns_router.cpp:965
void StopRouting()
Definition: pns_router.cpp:922
void ClearViewDecorations()
Definition: pns_router.cpp:950
bool getNearestRatnestAnchor(VECTOR2I &aOtherEnd, LAYER_RANGE &aOtherEndLayers, ITEM *&aOtherEndItem)
Definition: pns_router.cpp:498
void ToggleCornerMode()
int m_iterLimit
Definition: pns_router.h:250
PLACEMENT_ALGO * Placer()
Definition: pns_router.h:215
NODE * m_lastNode
Definition: pns_router.h:242
void ClearWorld()
Definition: pns_router.cpp:106
void UpdateSizes(const SIZES_SETTINGS &aSizes)
Applies stored settings.
Definition: pns_router.cpp:739
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:212
LOGGER * Logger()
RouterState m_state
Definition: pns_router.h:239
void CommitRouting()
Definition: pns_router.cpp:913
bool m_forceMarkObstaclesMode
Definition: pns_router.h:251
std::unique_ptr< DRAG_ALGO > m_dragger
Definition: pns_router.h:245
void SetInterface(ROUTER_IFACE *aIface)
bool Finish()
Definition: pns_router.cpp:549
void markViolations(NODE *aNode, ITEM_SET &aCurrent, NODE::ITEM_VECTOR &aRemoved)
Definition: pns_router.cpp:641
void SyncWorld()
Definition: pns_router.cpp:96
bool ContinueFromEnd()
Definition: pns_router.cpp:592
std::unique_ptr< PLACEMENT_ALGO > m_placer
Definition: pns_router.h:244
bool isStartingPointRoutable(const VECTOR2I &aWhere, ITEM *aItem, int aLayer)
Definition: pns_router.cpp:230
ROUTER_IFACE * m_iface
Definition: pns_router.h:248
bool IsPlacingVia() const
void FlipPosture()
Definition: pns_router.cpp:956
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:179
SIZES_SETTINGS m_sizes
Definition: pns_router.h:254
const ITEM_SET QueryHoverItems(const VECTOR2I &aP, bool aUseClearance=false)
Definition: pns_router.cpp:125
ROUTING_SETTINGS & Settings()
Definition: pns_router.h:191
bool FixRoute(const VECTOR2I &aP, ITEM *aItem, bool aForceFinish=false)
Definition: pns_router.cpp:875
DRAG_ALGO * GetDragger()
Definition: pns_router.h:139
bool movePlacing(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:749
bool RoutingInProgress() const
Definition: pns_router.cpp:119
BOX2I m_visibleViewArea
Definition: pns_router.h:238
static ROUTER * GetInstance()
Definition: pns_router.cpp:82
std::optional< VECTOR2I > UndoLastSegment()
Definition: pns_router.cpp:901
LOGGER * m_logger
Definition: pns_router.h:256
void BreakSegment(ITEM *aItem, const VECTOR2I &aP)
void SetOrthoMode(bool aEnable)
bool StartDragging(const VECTOR2I &aP, ITEM *aItem, int aDragMode=DM_ANY)
Definition: pns_router.cpp:176
bool StartRouting(const VECTOR2I &aP, ITEM *aItem, int aLayer)
Definition: pns_router.cpp:416
int GetCurrentLayer() const
Definition: pns_router.cpp:998
void GetUpdatedItems(std::vector< PNS::ITEM * > &aRemoved, std::vector< PNS::ITEM * > &aAdded, std::vector< PNS::ITEM * > &aHeads)
Definition: pns_router.cpp:793
std::unique_ptr< NODE > m_world
Definition: pns_router.h:241
void ToggleViaPlacement()
Definition: pns_router.cpp:974
ROUTING_SETTINGS * m_settings
Definition: pns_router.h:253
const std::vector< NET_HANDLE > GetCurrentNets() const
Definition: pns_router.cpp:987
ROUTER_MODE m_mode
Definition: pns_router.h:255
bool Move(const VECTOR2I &aP, ITEM *aItem)
Definition: pns_router.cpp:476
void SetCornerMode(DIRECTION_45::CORNER_MODE aMode)
DIRECTION_45::CORNER_MODE GetCornerMode() const
virtual void ClearCacheForItems(std::vector< const ITEM * > &aItems)
Definition: pns_node.h:158
virtual int Clearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true)=0
virtual void ClearCaches()
Definition: pns_node.h:159
int BoardMinTrackWidth() const
ITEM * NearestUnconnectedItem(const JOINT *aStart, int *aAnchor=nullptr, int aKindMask=ITEM::ANY_T)
bool NearestUnconnectedAnchorPoint(const LINE *aTrack, VECTOR2I &aPoint, LAYER_RANGE &aLayers, ITEM *&aItem)
Definition: seg.h:42
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:72
const wxString & GetZoneName() const
Definition: zone.h:131
static bool empty(const wxTextEntryBase *aCtrl)
#define _(s)
@ Edge_Cuts
Definition: layer_ids.h:114
Push and Shove diff pair dimensions (gap) settings dialog.
static ROUTER * theRouter
Definition: pns_router.cpp:59
void * NET_HANDLE
Definition: pns_item.h:54
ROUTER_MODE
Definition: pns_router.h:62
@ PNS_MODE_ROUTE_SINGLE
Definition: pns_router.h:63
@ PNS_MODE_ROUTE_DIFF_PAIR
Definition: pns_router.h:64
@ PNS_MODE_TUNE_DIFF_PAIR
Definition: pns_router.h:66
@ PNS_MODE_TUNE_SINGLE
Definition: pns_router.h:65
@ PNS_MODE_TUNE_DIFF_PAIR_SKEW
Definition: pns_router.h:67
DRAG_MODE
Definition: pns_router.h:71
@ DM_FREE_ANGLE
Definition: pns_router.h:75
@ MK_VIOLATION
Definition: pns_item.h:43
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:84
@ PCB_TEXTBOX_T
class PCB_TEXTBOX, wrapped text on a layer
Definition: typeinfo.h:92
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:104
@ PCB_TEXT_T
class PCB_TEXT, text on a layer
Definition: typeinfo.h:91
@ PCB_FIELD_T
class PCB_FIELD, text associated with a footprint property
Definition: typeinfo.h:90
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588