KiCad PCB EDA Suite
Loading...
Searching...
No Matches
connectivity_algo.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KICAD, a free EDA CAD application.
3 *
4 * Copyright (C) 2016-2018 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
27
28#include <algorithm>
29#include <future>
30#include <mutex>
31
33#include <progress_reporter.h>
35#include <board_commit.h>
36#include <thread_pool.h>
37#include <pcb_shape.h>
38
39#include <wx/log.h>
40
41#ifdef PROFILE
42#include <core/profile.h>
43#endif
44
45
47{
48 markItemNetAsDirty( aItem );
49
50 switch( aItem->Type() )
51 {
52 case PCB_FOOTPRINT_T:
53 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
54 {
55 m_itemMap[pad].MarkItemsAsInvalid();
56 m_itemMap.erase( pad );
57 }
58
59 m_itemList.SetDirty( true );
60 break;
61
62 case PCB_PAD_T:
63 case PCB_TRACE_T:
64 case PCB_ARC_T:
65 case PCB_VIA_T:
66 case PCB_ZONE_T:
67 case PCB_SHAPE_T:
68 m_itemMap[aItem].MarkItemsAsInvalid();
69 m_itemMap.erase ( aItem );
70 m_itemList.SetDirty( true );
71 break;
72
73 default:
74 return false;
75 }
76
77 // Once we delete an item, it may connect between lists, so mark both as potentially invalid
78 m_itemList.SetHasInvalid( true );
79
80 return true;
81}
82
83
85{
86 if( aItem->IsConnected() )
87 {
88 const BOARD_CONNECTED_ITEM* citem = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
89 MarkNetAsDirty( citem->GetNetCode() );
90 }
91 else
92 {
93 if( aItem->Type() == PCB_FOOTPRINT_T )
94 {
95 const FOOTPRINT* footprint = static_cast<const FOOTPRINT*>( aItem );
96
97 for( PAD* pad : footprint->Pads() )
98 MarkNetAsDirty( pad->GetNetCode() );
99 }
100 }
101}
102
103
105{
106 if( !aItem->IsOnCopperLayer() )
107 return false;
108
109 auto alreadyAdded =
110 [this]( BOARD_ITEM* item )
111 {
112 auto it = m_itemMap.find( item );
113
114 if( it == m_itemMap.end() )
115 return false;
116
117 // Don't be fooled by an empty ITEM_MAP_ENTRY auto-created by operator[].
118 return !it->second.GetItems().empty();
119 };
120
121 switch( aItem->Type() )
122 {
123 case PCB_NETINFO_T:
124 MarkNetAsDirty( static_cast<NETINFO_ITEM*>( aItem )->GetNetCode() );
125 break;
126
127 case PCB_FOOTPRINT_T:
128 {
129 if( static_cast<FOOTPRINT*>( aItem )->GetAttributes() & FP_JUST_ADDED )
130 return false;
131
132 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
133 {
134 if( alreadyAdded( pad ) )
135 return false;
136
137 add( m_itemList, pad );
138 }
139
140 break;
141 }
142
143 case PCB_PAD_T:
144 {
145 if( FOOTPRINT* fp = aItem->GetParentFootprint() )
146 {
147 if( fp->GetAttributes() & FP_JUST_ADDED )
148 return false;
149 }
150
151 if( alreadyAdded( aItem ) )
152 return false;
153
154 add( m_itemList, static_cast<PAD*>( aItem ) );
155 break;
156 }
157
158 case PCB_TRACE_T:
159 if( alreadyAdded( aItem ) )
160 return false;
161
162 add( m_itemList, static_cast<PCB_TRACK*>( aItem ) );
163 break;
164
165 case PCB_ARC_T:
166 if( alreadyAdded( aItem ) )
167 return false;
168
169 add( m_itemList, static_cast<PCB_ARC*>( aItem ) );
170 break;
171
172 case PCB_VIA_T:
173 if( alreadyAdded( aItem ) )
174 return false;
175
176 add( m_itemList, static_cast<PCB_VIA*>( aItem ) );
177 break;
178
179 case PCB_SHAPE_T:
180 if( alreadyAdded( aItem ) )
181 return false;
182
183 if( !IsCopperLayer( aItem->GetLayer() ) )
184 return false;
185
186 add( m_itemList, static_cast<PCB_SHAPE*>( aItem ) );
187 break;
188
189 case PCB_ZONE_T:
190 {
191 ZONE* zone = static_cast<ZONE*>( aItem );
192
193 if( alreadyAdded( aItem ) )
194 return false;
195
196 m_itemMap[zone] = ITEM_MAP_ENTRY();
197
198 // Don't check for connections on layers that only exist in the zone but
199 // were disabled in the board
200 BOARD* board = zone->GetBoard();
201 LSET layerset = board->GetEnabledLayers() & zone->GetLayerSet();
202
203 layerset.RunOnLayers(
204 [&]( PCB_LAYER_ID layer )
205 {
206 for( CN_ITEM* zitem : m_itemList.Add( zone, layer ) )
207 m_itemMap[zone].Link( zitem );
208 } );
209 }
210 break;
211
212 default:
213 return false;
214 }
215
216 markItemNetAsDirty( aItem );
217
218 return true;
219}
220
221
223{
224 for( CN_ITEM* item : m_itemList )
225 item->RemoveInvalidRefs();
226}
227
228
230{
231 std::lock_guard lock( m_mutex );
232#ifdef PROFILE
233 PROF_TIMER garbage_collection( "garbage-collection" );
234#endif
235 std::vector<CN_ITEM*> garbage;
236 garbage.reserve( 1024 );
237
238 m_parentConnectivityData->RemoveInvalidRefs();
239
240 if( m_isLocal )
241 m_globalConnectivityData->RemoveInvalidRefs();
242
243 m_itemList.RemoveInvalidItems( garbage );
244
245 for( CN_ITEM* item : garbage )
246 delete item;
247
248#ifdef PROFILE
249 garbage_collection.Show();
250 PROF_TIMER search_basic( "search-basic" );
251#endif
252
254 std::vector<CN_ITEM*> dirtyItems;
255 std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
256 [] ( CN_ITEM* aItem )
257 {
258 return aItem->Dirty();
259 } );
260
262 {
263 m_progressReporter->SetMaxProgress( dirtyItems.size() );
264
265 if( !m_progressReporter->KeepRefreshing() )
266 return;
267 }
268
269 if( m_itemList.IsDirty() )
270 {
271 std::vector<std::future<size_t>> returns( dirtyItems.size() );
272
273 for( size_t ii = 0; ii < dirtyItems.size(); ++ii )
274 {
275 returns[ii] = tp.submit_task(
276 [&dirtyItems, ii, this] () ->size_t {
277 if( m_progressReporter && m_progressReporter->IsCancelled() )
278 return 0;
279
280 CN_VISITOR visitor( dirtyItems[ii] );
281 m_itemList.FindNearby( dirtyItems[ii], visitor );
282
284 m_progressReporter->AdvanceProgress();
285
286 return 1; } );
287 }
288
289 for( const std::future<size_t>& ret : returns )
290 {
291 // Here we balance returns with a 250ms timeout to allow UI updating
292 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
293
294 while( status != std::future_status::ready )
295 {
297 m_progressReporter->KeepRefreshing();
298
299 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
300 }
301 }
302
304 m_progressReporter->KeepRefreshing();
305 }
306
307#ifdef PROFILE
308 search_basic.Show();
309#endif
310
311 m_itemList.ClearDirtyFlags();
312}
313
314
319
320
322CN_CONNECTIVITY_ALGO::SearchClusters( CLUSTER_SEARCH_MODE aMode, bool aExcludeZones, int aSingleNet )
323{
324 bool withinAnyNet = ( aMode != CSM_PROPAGATE );
325
326 std::deque<CN_ITEM*> Q;
327 std::set<CN_ITEM*> item_set;
328
329 CLUSTERS clusters;
330
331 if( m_itemList.IsDirty() )
333
334 std::set<CN_ITEM*> visited;
335
336 auto addToSearchList =
337 [&item_set, withinAnyNet, aSingleNet, &aExcludeZones]( CN_ITEM *aItem )
338 {
339 if( withinAnyNet && aItem->Net() <= 0 )
340 return;
341
342 if( !aItem->Valid() )
343 return;
344
345 if( aSingleNet >=0 && aItem->Net() != aSingleNet )
346 return;
347
348 if( aExcludeZones && aItem->Parent()->Type() == PCB_ZONE_T )
349 return;
350
351 item_set.insert( aItem );
352 };
353
354 std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
355
356 if( m_progressReporter && m_progressReporter->IsCancelled() )
357 return CLUSTERS();
358
359 while( !item_set.empty() )
360 {
361 std::shared_ptr<CN_CLUSTER> cluster = std::make_shared<CN_CLUSTER>();
362 CN_ITEM* root;
363 auto it = item_set.begin();
364
365 while( it != item_set.end() && visited.contains( *it ) )
366 it = item_set.erase( item_set.begin() );
367
368 if( it == item_set.end() )
369 break;
370
371 root = *it;
372 visited.insert( root );
373
374 Q.clear();
375 Q.push_back( root );
376
377 while( Q.size() )
378 {
379 CN_ITEM* current = Q.front();
380
381 Q.pop_front();
382 cluster->Add( current );
383
384 for( CN_ITEM* n : current->ConnectedItems() )
385 {
386 if( withinAnyNet && n->Net() != root->Net() )
387 continue;
388
389 if( aExcludeZones && n->Parent()->Type() == PCB_ZONE_T )
390 continue;
391
392 if( !visited.contains( n ) && n->Valid() )
393 {
394 visited.insert( n );
395 Q.push_back( n );
396 }
397 }
398 }
399
400 clusters.push_back( std::move( cluster ) );
401 }
402
403 if( m_progressReporter && m_progressReporter->IsCancelled() )
404 return CLUSTERS();
405
406 std::sort( clusters.begin(), clusters.end(),
407 []( const std::shared_ptr<CN_CLUSTER>& a, const std::shared_ptr<CN_CLUSTER>& b )
408 {
409 return a->OriginNet() < b->OriginNet();
410 } );
411
412 return clusters;
413}
414
415
417{
418 // Generate CN_ZONE_LAYERs for each island on each layer of each zone
419 //
420 std::vector<CN_ZONE_LAYER*> zitems;
421
422 for( ZONE* zone : aBoard->Zones() )
423 {
424 if( zone->IsOnCopperLayer() )
425 {
426 m_itemMap[zone] = ITEM_MAP_ENTRY();
427 markItemNetAsDirty( zone );
428
429 // Don't check for connections on layers that only exist in the zone but
430 // were disabled in the board
431 BOARD* board = zone->GetBoard();
432 LSET layerset = board->GetEnabledLayers() & zone->GetLayerSet() & LSET::AllCuMask();
433
434 layerset.RunOnLayers(
435 [&]( PCB_LAYER_ID layer )
436 {
437 for( int j = 0; j < zone->GetFilledPolysList( layer )->OutlineCount(); j++ )
438 zitems.push_back( new CN_ZONE_LAYER( zone, layer, j ) );
439 } );
440 }
441 }
442
443 // Setup progress metrics
444 //
445 int progressDelta = 50;
446 double size = 0.0;
447
448 size += zitems.size(); // Once for building RTrees
449 size += zitems.size(); // Once for adding to connectivity
450 size += aBoard->Tracks().size();
451 size += aBoard->Drawings().size();
452
453 for( FOOTPRINT* footprint : aBoard->Footprints() )
454 size += footprint->Pads().size();
455
456 size *= 1.5; // Our caller gets the other third of the progress bar
457
458 progressDelta = std::max( progressDelta, (int) size / 4 );
459
460 auto report =
461 [&]( int progress )
462 {
463 if( aReporter && ( progress % progressDelta ) == 0 )
464 {
465 aReporter->SetCurrentProgress( progress / size );
466 aReporter->KeepRefreshing( false );
467 }
468 };
469
470 // Generate RTrees for CN_ZONE_LAYER items (in parallel)
471 //
473 std::vector<std::future<size_t>> returns( zitems.size() );
474
475 auto cache_zones =
476 [aReporter]( CN_ZONE_LAYER* aZoneLayer ) -> size_t
477 {
478 if( aReporter && aReporter->IsCancelled() )
479 return 0;
480
481 aZoneLayer->BuildRTree();
482
483 if( aReporter )
484 aReporter->AdvanceProgress();
485
486 return 1;
487 };
488
489 for( size_t ii = 0; ii < zitems.size(); ++ii )
490 {
491 CN_ZONE_LAYER* ptr = zitems[ii];
492 returns[ii] = tp.submit_task(
493 [cache_zones, ptr] { return cache_zones( ptr ); } );
494 }
495
496 for( const std::future<size_t>& ret : returns )
497 {
498 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
499
500 while( status != std::future_status::ready )
501 {
502 if( aReporter )
503 aReporter->KeepRefreshing();
504
505 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
506 }
507
508 }
509
510 // Add CN_ZONE_LAYERS, tracks, and pads to connectivity
511 //
512 int ii = zitems.size();
513
514 for( CN_ZONE_LAYER* zitem : zitems )
515 {
516 m_itemList.Add( zitem );
517 m_itemMap[ zitem->Parent() ].Link( zitem );
518 report( ++ii );
519 }
520
521 for( PCB_TRACK* tv : aBoard->Tracks() )
522 {
523 Add( tv );
524 report( ++ii );
525 }
526
527 for( FOOTPRINT* footprint : aBoard->Footprints() )
528 {
529 for( PAD* pad : footprint->Pads() )
530 {
531 Add( pad );
532 report( ++ii );
533 }
534 }
535
536 for( BOARD_ITEM* drawing : aBoard->Drawings() )
537 {
538 if( PCB_SHAPE* shape = dynamic_cast<PCB_SHAPE*>( drawing ) )
539 {
540 if( shape->IsOnCopperLayer() )
541 Add( shape );
542 }
543
544 report( ++ii );
545 }
546
547 if( aReporter )
548 {
549 aReporter->SetCurrentProgress( (double) ii / (double) size );
550 aReporter->KeepRefreshing( false );
551 }
552}
553
554
555void CN_CONNECTIVITY_ALGO::LocalBuild( const std::shared_ptr<CONNECTIVITY_DATA>& aGlobalConnectivity,
556 const std::vector<BOARD_ITEM*>& aLocalItems )
557{
558 m_isLocal = true;
559 m_globalConnectivityData = aGlobalConnectivity;
560
561 for( BOARD_ITEM* item : aLocalItems )
562 {
563 switch( item->Type() )
564 {
565 case PCB_TRACE_T:
566 case PCB_ARC_T:
567 case PCB_VIA_T:
568 case PCB_PAD_T:
569 case PCB_FOOTPRINT_T:
570 case PCB_SHAPE_T:
571 Add( item );
572 break;
573
574 default:
575 break;
576 }
577 }
578}
579
580
582{
583 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
584 {
585 if( cluster->IsConflicting() )
586 {
587 // Conflicting pads in cluster: we don't know the user's intent so best to do
588 // nothing.
589 wxLogTrace( wxT( "CN" ), wxT( "Conflicting pads in cluster %p; skipping propagation" ),
590 cluster.get() );
591 }
592 else if( cluster->HasValidNet() )
593 {
594 // Propagate from the origin (will be a pad if there are any, or another item if
595 // there are no pads).
596 int n_changed = 0;
597
598 for( CN_ITEM* item : *cluster )
599 {
600 if( item->Valid() && item->CanChangeNet()
601 && item->Parent()->GetNetCode() != cluster->OriginNet() )
602 {
603 MarkNetAsDirty( item->Parent()->GetNetCode() );
604 MarkNetAsDirty( cluster->OriginNet() );
605
606 if( aCommit )
607 aCommit->Modify( item->Parent() );
608
609 item->Parent()->SetNetCode( cluster->OriginNet() );
610 n_changed++;
611 }
612 }
613
614 if( n_changed )
615 {
616 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: net: %d %s" ),
617 cluster.get(),
618 cluster->OriginNet(),
619 (const char*) cluster->OriginNetName().c_str() );
620 }
621 else
622 {
623 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: no changeable items to propagate to" ),
624 cluster.get() );
625 }
626 }
627 else
628 {
629 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: connected to unused net" ),
630 cluster.get() );
631 }
632 }
633}
634
635
642
643
645 std::map<ZONE*, std::map<PCB_LAYER_ID, ISOLATED_ISLANDS>>& aMap,
646 bool aConnectivityAlreadyRebuilt )
647{
648 int progressDelta = 50;
649 int ii = 0;
650
651 progressDelta = std::max( progressDelta, (int) aMap.size() / 4 );
652
653 if( !aConnectivityAlreadyRebuilt )
654 {
655 for( const auto& [ zone, islands ] : aMap )
656 {
657 Remove( zone );
658 Add( zone );
659 ii++;
660
661 if( m_progressReporter && ( ii % progressDelta ) == 0 )
662 {
663 m_progressReporter->SetCurrentProgress( (double) ii / (double) aMap.size() );
664 m_progressReporter->KeepRefreshing( false );
665 }
666
667 if( m_progressReporter && m_progressReporter->IsCancelled() )
668 return;
669 }
670 }
671
673
674 for( auto& [ zone, zoneIslands ] : aMap )
675 {
676 for( auto& [ layer, layerIslands ] : zoneIslands )
677 {
678 if( zone->GetFilledPolysList( layer )->IsEmpty() )
679 continue;
680
681 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
682 {
683 for( CN_ITEM* item : *cluster )
684 {
685 if( item->Parent() == zone && item->GetBoardLayer() == layer )
686 {
687 CN_ZONE_LAYER* z = static_cast<CN_ZONE_LAYER*>( item );
688
689 if( cluster->IsOrphaned() )
690 layerIslands.m_IsolatedOutlines.push_back( z->SubpolyIndex() );
691 else if( z->HasSingleConnection() )
692 layerIslands.m_SingleConnectionOutlines.push_back( z->SubpolyIndex() );
693 }
694 }
695 }
696 }
697 }
698}
699
700
706
707
709{
710 if( aNet < 0 )
711 return;
712
713 if( (int) m_dirtyNets.size() <= aNet )
714 {
715 int lastNet = m_dirtyNets.size() - 1;
716
717 if( lastNet < 0 )
718 lastNet = 0;
719
720 m_dirtyNets.resize( aNet + 1 );
721
722 for( int i = lastNet; i < aNet + 1; i++ )
723 m_dirtyNets[i] = true;
724 }
725
726 m_dirtyNets[aNet] = true;
727}
728
729
731{
732 PCB_LAYER_ID layer = aZoneLayer->GetLayer();
733 BOARD_CONNECTED_ITEM* item = aItem->Parent();
734
735 if( !item->IsOnLayer( layer ) )
736 return;
737
738 auto connect =
739 [&]()
740 {
741 // We don't propagate nets from zones, so any free-via net changes need to happen now.
742 if( aItem->Parent()->Type() == PCB_VIA_T && aItem->CanChangeNet() )
743 aItem->Parent()->SetNetCode( aZoneLayer->Net() );
744
745 aZoneLayer->Connect( aItem );
746 aItem->Connect( aZoneLayer );
747 };
748
749 // Try quick checks first...
750 if( item->Type() == PCB_PAD_T )
751 {
752 PAD* pad = static_cast<PAD*>( item );
753
754 if( pad->ConditionallyFlashed( layer )
755 && pad->GetZoneLayerOverride( layer ) == ZLO_FORCE_NO_ZONE_CONNECTION )
756 {
757 return;
758 }
759 }
760 else if( item->Type() == PCB_VIA_T )
761 {
762 PCB_VIA* via = static_cast<PCB_VIA*>( item );
763
764 if( via->ConditionallyFlashed( layer )
765 && via->GetZoneLayerOverride( layer ) == ZLO_FORCE_NO_ZONE_CONNECTION )
766 {
767 return;
768 }
769 }
770
771 for( int i = 0; i < aItem->AnchorCount(); ++i )
772 {
773 if( aZoneLayer->ContainsPoint( aItem->GetAnchor( i ) ) )
774 {
775 connect();
776 return;
777 }
778 }
779
780 if( item->Type() == PCB_VIA_T || item->Type() == PCB_PAD_T )
781 {
782 // As long as the pad/via crosses the zone layer, check for the full effective shape
783 // We check for the overlapping layers above
784 if( aZoneLayer->Collide( item->GetEffectiveShape( layer, FLASHING::ALWAYS_FLASHED ).get() ) )
785 connect();
786
787 return;
788 }
789
790 if( aZoneLayer->Collide( item->GetEffectiveShape( layer ).get() ) )
791 connect();
792}
793
795{
796 const ZONE* zoneA = static_cast<const ZONE*>( aZoneLayerA->Parent() );
797 const ZONE* zoneB = static_cast<const ZONE*>( aZoneLayerB->Parent() );
798
799 const BOX2I& boxA = aZoneLayerA->BBox();
800 const BOX2I& boxB = aZoneLayerB->BBox();
801
802 PCB_LAYER_ID layer = aZoneLayerA->GetLayer();
803
804 if( aZoneLayerB->GetLayer() != layer )
805 return;
806
807 if( !boxA.Intersects( boxB ) )
808 return;
809
810 const SHAPE_LINE_CHAIN& outline =
811 zoneA->GetFilledPolysList( layer )->COutline( aZoneLayerA->SubpolyIndex() );
812
813 for( int i = 0; i < outline.PointCount(); i++ )
814 {
815 if( !boxB.Contains( outline.CPoint( i ) ) )
816 continue;
817
818 if( aZoneLayerB->ContainsPoint( outline.CPoint( i ) ) )
819 {
820 aZoneLayerA->Connect( aZoneLayerB );
821 aZoneLayerB->Connect( aZoneLayerA );
822 return;
823 }
824 }
825
826 const SHAPE_LINE_CHAIN& outline2 =
827 zoneB->GetFilledPolysList( layer )->COutline( aZoneLayerB->SubpolyIndex() );
828
829 for( int i = 0; i < outline2.PointCount(); i++ )
830 {
831 if( !boxA.Contains( outline2.CPoint( i ) ) )
832 continue;
833
834 if( aZoneLayerA->ContainsPoint( outline2.CPoint( i ) ) )
835 {
836 aZoneLayerA->Connect( aZoneLayerB );
837 aZoneLayerB->Connect( aZoneLayerA );
838 return;
839 }
840 }
841}
842
843
845{
846 const BOARD_CONNECTED_ITEM* parentA = aCandidate->Parent();
847 const BOARD_CONNECTED_ITEM* parentB = m_item->Parent();
848
849 if( !aCandidate->Valid() || !m_item->Valid() )
850 return true;
851
852 if( parentA == parentB )
853 return true;
854
855 // Don't connect items in different nets that can't be changed
856 if( !aCandidate->CanChangeNet() && !m_item->CanChangeNet() && aCandidate->Net() != m_item->Net() )
857 return true;
858
859 // If both m_item and aCandidate are marked dirty, they will both be searched
860 // Since we are reciprocal in our connection, we arbitrarily pick one of the connections
861 // to conduct the expensive search
862 if( aCandidate->Dirty() && aCandidate < m_item )
863 return true;
864
865 // We should handle zone-zone connection separately
866 if ( parentA->Type() == PCB_ZONE_T && parentB->Type() == PCB_ZONE_T )
867 {
869 static_cast<CN_ZONE_LAYER*>( aCandidate ) );
870 return true;
871 }
872
873 if( parentA->Type() == PCB_ZONE_T )
874 {
875 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( aCandidate ), m_item );
876 return true;
877 }
878
879 if( parentB->Type() == PCB_ZONE_T )
880 {
881 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( m_item ), aCandidate );
882 return true;
883 }
884
885 LSET commonLayers = parentA->GetLayerSet() & parentB->GetLayerSet();
886
887 if( const BOARD* board = parentA->GetBoard() )
888 commonLayers &= board->GetEnabledLayers();
889
890 for( PCB_LAYER_ID layer : commonLayers )
891 {
894
895 if( parentA->Type() == PCB_PAD_T )
896 {
897 if( !static_cast<const PAD*>( parentA )->ConditionallyFlashed( layer ) )
898 flashingA = FLASHING::ALWAYS_FLASHED;
899 }
900 else if( parentA->Type() == PCB_VIA_T )
901 {
902 if( !static_cast<const PCB_VIA*>( parentA )->ConditionallyFlashed( layer ) )
903 flashingA = FLASHING::ALWAYS_FLASHED;
904 }
905
906 if( parentB->Type() == PCB_PAD_T )
907 {
908 if( !static_cast<const PAD*>( parentB )->ConditionallyFlashed( layer ) )
909 flashingB = FLASHING::ALWAYS_FLASHED;
910 }
911 else if( parentB->Type() == PCB_VIA_T )
912 {
913 if( !static_cast<const PCB_VIA*>( parentB )->ConditionallyFlashed( layer ) )
914 flashingB = FLASHING::ALWAYS_FLASHED;
915 }
916
917 if( parentA->GetEffectiveShape( layer, flashingA )->Collide(
918 parentB->GetEffectiveShape( layer, flashingB ).get() ) )
919 {
920 m_item->Connect( aCandidate );
921 aCandidate->Connect( m_item );
922 return true;
923 }
924 }
925
926 return true;
927};
928
929
931{
932 m_ratsnestClusters.clear();
933 m_connClusters.clear();
934 m_itemMap.clear();
935 m_itemList.Clear();
936
937}
938
943
944
946{
947 // Map of footprint -> map of pad number -> list of CN_ITEMs for pads with that number
948 std::map<FOOTPRINT*, std::map<wxString, std::vector<CN_ITEM*>>> padsByFootprint;
949
950 for( CN_ITEM* item : m_itemList )
951 {
952 if( !item->Valid() || item->Parent()->Type() != PCB_PAD_T )
953 continue;
954
955 auto pad = static_cast<const PAD*>( item->Parent() );
956
957 FOOTPRINT* fp = pad->GetParentFootprint();
958
959 padsByFootprint[fp][ pad->GetNumber() ].emplace_back( item );
960 }
961
962 for( auto& [footprint, padsMap] : padsByFootprint )
963 {
964 if( footprint->GetDuplicatePadNumbersAreJumpers() )
965 {
966 for( const std::vector<CN_ITEM*>& padsList : padsMap | std::views::values )
967 {
968 for( size_t i = 0; i < padsList.size(); ++i )
969 {
970 for( size_t j = 1; j < padsList.size(); ++j )
971 {
972 padsList[i]->Connect( padsList[j] );
973 padsList[j]->Connect( padsList[i] );
974 }
975 }
976 }
977 }
978
979 for( const std::set<wxString>& group : footprint->JumperPadGroups() )
980 {
981 std::vector<CN_ITEM*> toConnect;
982
983 for( const wxString& padNumber : group )
984 std::ranges::copy( padsMap[padNumber], std::back_inserter( toConnect ) );
985
986 for( size_t i = 0; i < toConnect.size(); ++i )
987 {
988 for( size_t j = 1; j < toConnect.size(); ++j )
989 {
990 toConnect[i]->Connect( toConnect[j] );
991 toConnect[j]->Connect( toConnect[i] );
992 }
993 }
994 }
995 }
996}
@ ZLO_FORCE_NO_ZONE_CONNECTION
Definition board_item.h:70
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
bool SetNetCode(int aNetCode, bool aNoAssert)
Set net using a net code.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition board_item.h:79
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition board_item.h:232
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition board_item.h:134
virtual bool IsOnLayer(PCB_LAYER_ID aLayer) const
Test to see if this object is on the given layer.
Definition board_item.h:314
virtual std::shared_ptr< SHAPE > GetEffectiveShape(PCB_LAYER_ID aLayer=UNDEFINED_LAYER, FLASHING aFlash=FLASHING::DEFAULT) const
Some pad shapes can be complex (rounded/chamfered rectangle), even without considering custom shapes.
virtual const BOARD * GetBoard() const
Return the BOARD in which this BOARD_ITEM resides, or NULL if none.
FOOTPRINT * GetParentFootprint() const
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition board_item.h:252
virtual bool IsOnCopperLayer() const
Definition board_item.h:151
Information pertinent to a Pcbnew printed circuit board.
Definition board.h:317
const ZONES & Zones() const
Definition board.h:362
const FOOTPRINTS & Footprints() const
Definition board.h:358
const TRACKS & Tracks() const
Definition board.h:356
const LSET & GetEnabledLayers() const
A proxy function that calls the corresponding function in m_BoardSettings.
Definition board.cpp:923
const DRAWINGS & Drawings() const
Definition board.h:360
constexpr bool Contains(const Vec &aPoint) const
Definition box2.h:168
constexpr bool Intersects(const BOX2< Vec > &aRect) const
Definition box2.h:311
void FillIsolatedIslandsMap(std::map< ZONE *, std::map< PCB_LAYER_ID, ISOLATED_ISLANDS > > &aMap, bool aConnectivityAlreadyRebuilt)
Fill in the isolated islands map with copper islands that are not connected to a net.
bool Remove(BOARD_ITEM *aItem)
CONNECTIVITY_DATA * m_parentConnectivityData
void add(Container &c, BItem brditem)
PROGRESS_REPORTER * m_progressReporter
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
void propagateConnections(BOARD_COMMIT *aCommit=nullptr)
const CLUSTERS & GetClusters()
void LocalBuild(const std::shared_ptr< CONNECTIVITY_DATA > &aGlobalConnectivity, const std::vector< BOARD_ITEM * > &aLocalItems)
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, bool aExcludeZones, int aSingleNet)
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagate nets from pads to other items in clusters.
std::shared_ptr< CONNECTIVITY_DATA > m_globalConnectivityData
std::vector< bool > m_dirtyNets
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
void Build(BOARD *aBoard, PROGRESS_REPORTER *aReporter=nullptr)
bool Add(BOARD_ITEM *aItem)
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
void Connect(CN_ITEM *b)
const BOX2I & BBox()
virtual int AnchorCount() const
const std::vector< CN_ITEM * > & ConnectedItems() const
int Net() const
bool Valid() const
virtual const VECTOR2I GetAnchor(int n) const
bool CanChangeNet() const
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
void checkZoneItemConnection(CN_ZONE_LAYER *aZoneLayer, CN_ITEM *aItem)
CN_ITEM * m_item
The item we are looking for connections to.
void checkZoneZoneConnection(CN_ZONE_LAYER *aZoneLayerA, CN_ZONE_LAYER *aZoneLayerB)
bool operator()(CN_ITEM *aCandidate)
PCB_LAYER_ID GetLayer() const
bool Collide(SHAPE *aRefShape) const
int SubpolyIndex() const
bool ContainsPoint(const VECTOR2I &p) const
COMMIT & Modify(EDA_ITEM *aItem, BASE_SCREEN *aScreen=nullptr, RECURSE_MODE aRecurse=RECURSE_MODE::NO_RECURSE)
Modify a given item in the model.
Definition commit.h:106
KICAD_T Type() const
Returns the type of object.
Definition eda_item.h:110
std::deque< PAD * > & Pads()
Definition footprint.h:224
LSET is a set of PCB_LAYER_IDs.
Definition lset.h:37
void RunOnLayers(const std::function< void(PCB_LAYER_ID)> &aFunction) const
Execute a function on each layer of the LSET.
Definition lset.h:252
static LSET AllCuMask()
return AllCuMask( MAX_CU_LAYERS );
Definition lset.cpp:591
Handle the data for a net.
Definition netinfo.h:54
Definition pad.h:54
A small class to help profiling.
Definition profile.h:49
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition profile.h:105
A progress reporter interface for use in multi-threaded environments.
virtual bool IsCancelled() const =0
virtual bool KeepRefreshing(bool aWait=false)=0
Update the UI (if any).
virtual void AdvanceProgress()=0
Increment the progress bar length (inside the current virtual zone).
virtual void SetCurrentProgress(double aProgress)=0
Set the progress value to aProgress (0..1).
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition shape.h:181
Handle a list of polygons defining a copper zone.
Definition zone.h:74
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition zone.h:600
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition zone.h:136
@ FP_JUST_ADDED
Definition footprint.h:86
a few functions useful in geometry calculations.
FLASHING
Enum used during connectivity building to ensure we do not query connectivity while building the data...
Definition layer_ids.h:184
@ NEVER_FLASHED
Never flashed for connectivity.
Definition layer_ids.h:187
@ ALWAYS_FLASHED
Always flashed for connectivity.
Definition layer_ids.h:186
bool IsCopperLayer(int aLayerId)
Test whether a layer is a copper layer.
Definition layer_ids.h:674
PCB_LAYER_ID
A quick note on layer IDs:
Definition layer_ids.h:60
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
static thread_pool * tp
BS::thread_pool< 0 > thread_pool
Definition thread_pool.h:31
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition typeinfo.h:88
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition typeinfo.h:97
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition typeinfo.h:107
@ PCB_FOOTPRINT_T
class FOOTPRINT, a footprint
Definition typeinfo.h:86
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition typeinfo.h:87
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition typeinfo.h:98
@ PCB_NETINFO_T
class NETINFO_ITEM, a description of a net
Definition typeinfo.h:109
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition typeinfo.h:96