KiCad PCB EDA Suite
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 (C) 2020-2022 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
38#include <wx/log.h>
39
40#ifdef PROFILE
41#include <profile.h>
42#endif
43
44
46{
47 markItemNetAsDirty( aItem );
48
49 switch( aItem->Type() )
50 {
51 case PCB_FOOTPRINT_T:
52 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
53 {
54 m_itemMap[pad].MarkItemsAsInvalid();
55 m_itemMap.erase( pad );
56 }
57
58 m_itemList.SetDirty( true );
59 break;
60
61 case PCB_PAD_T:
62 m_itemMap[aItem].MarkItemsAsInvalid();
63 m_itemMap.erase( aItem );
64 m_itemList.SetDirty( true );
65 break;
66
67 case PCB_TRACE_T:
68 case PCB_ARC_T:
69 m_itemMap[aItem].MarkItemsAsInvalid();
70 m_itemMap.erase( aItem );
71 m_itemList.SetDirty( true );
72 break;
73
74 case PCB_VIA_T:
75 m_itemMap[aItem].MarkItemsAsInvalid();
76 m_itemMap.erase( aItem );
77 m_itemList.SetDirty( true );
78 break;
79
80 case PCB_ZONE_T:
81 m_itemMap[aItem].MarkItemsAsInvalid();
82 m_itemMap.erase ( aItem );
83 m_itemList.SetDirty( true );
84 break;
85
86 default:
87 return false;
88 }
89
90 // Once we delete an item, it may connect between lists, so mark both as potentially invalid
92
93 return true;
94}
95
96
98{
99 if( aItem->IsConnected() )
100 {
101 const BOARD_CONNECTED_ITEM* citem = static_cast<const BOARD_CONNECTED_ITEM*>( aItem );
102 MarkNetAsDirty( citem->GetNetCode() );
103 }
104 else
105 {
106 if( aItem->Type() == PCB_FOOTPRINT_T )
107 {
108 const FOOTPRINT* footprint = static_cast<const FOOTPRINT*>( aItem );
109
110 for( PAD* pad : footprint->Pads() )
111 MarkNetAsDirty( pad->GetNetCode() );
112 }
113 }
114}
115
116
118{
119 if( !aItem->IsOnCopperLayer() )
120 return false;
121
122 switch( aItem->Type() )
123 {
124 case PCB_NETINFO_T:
125 MarkNetAsDirty( static_cast<NETINFO_ITEM*>( aItem )->GetNetCode() );
126 break;
127
128 case PCB_FOOTPRINT_T:
129 {
130 if( static_cast<FOOTPRINT*>( aItem )->GetAttributes() & FP_JUST_ADDED )
131 return false;
132
133 for( PAD* pad : static_cast<FOOTPRINT*>( aItem )->Pads() )
134 {
135 if( m_itemMap.find( pad ) != m_itemMap.end() )
136 return false;
137
138 add( m_itemList, pad );
139 }
140
141 break;
142 }
143
144 case PCB_PAD_T:
145 {
146 if( FOOTPRINT* fp = dynamic_cast<FOOTPRINT*>( aItem->GetParentFootprint() ) )
147 {
148 if( fp->GetAttributes() & FP_JUST_ADDED )
149 return false;
150 }
151
152 if( m_itemMap.find( aItem ) != m_itemMap.end() )
153 return false;
154
155 add( m_itemList, static_cast<PAD*>( aItem ) );
156 break;
157 }
158
159 case PCB_TRACE_T:
160 if( m_itemMap.find( aItem ) != m_itemMap.end() )
161 return false;
162
163 add( m_itemList, static_cast<PCB_TRACK*>( aItem ) );
164 break;
165
166 case PCB_ARC_T:
167 if( m_itemMap.find( aItem ) != m_itemMap.end() )
168 return false;
169
170 add( m_itemList, static_cast<PCB_ARC*>( aItem ) );
171 break;
172
173 case PCB_VIA_T:
174 if( m_itemMap.find( aItem ) != m_itemMap.end() )
175 return false;
176
177 add( m_itemList, static_cast<PCB_VIA*>( aItem ) );
178 break;
179
180 case PCB_ZONE_T:
181 {
182 ZONE* zone = static_cast<ZONE*>( aItem );
183
184 if( m_itemMap.find( aItem ) != m_itemMap.end() )
185 return false;
186
187 m_itemMap[zone] = ITEM_MAP_ENTRY();
188
189 for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
190 {
191 for( CN_ITEM* zitem : m_itemList.Add( zone, layer ) )
192 m_itemMap[zone].Link( zitem );
193 }
194 }
195 break;
196
197 default:
198 return false;
199 }
200
201 markItemNetAsDirty( aItem );
202
203 return true;
204}
205
206
208{
209#ifdef PROFILE
210 PROF_TIMER garbage_collection( "garbage-collection" );
211#endif
212 std::vector<CN_ITEM*> garbage;
213 garbage.reserve( 1024 );
214
216
217 for( CN_ITEM* item : garbage )
218 delete item;
219
220#ifdef PROFILE
221 garbage_collection.Show();
222 PROF_TIMER search_basic( "search-basic" );
223#endif
224
226 std::vector<CN_ITEM*> dirtyItems;
227 std::copy_if( m_itemList.begin(), m_itemList.end(), std::back_inserter( dirtyItems ),
228 [] ( CN_ITEM* aItem )
229 {
230 return aItem->Dirty();
231 } );
232
234 {
235 m_progressReporter->SetMaxProgress( dirtyItems.size() );
236
238 return;
239 }
240
241 if( m_itemList.IsDirty() )
242 {
243
244 std::vector<std::future<size_t>> returns( dirtyItems.size() );
245
246 auto conn_lambda =
247 [&dirtyItems]( size_t aItem, CN_LIST* aItemList,
248 PROGRESS_REPORTER* aReporter) -> size_t
249 {
250 if( aReporter && aReporter->IsCancelled() )
251 return 0;
252
253 CN_VISITOR visitor( dirtyItems[aItem] );
254 aItemList->FindNearby( dirtyItems[aItem], visitor );
255
256 if( aReporter )
257 aReporter->AdvanceProgress();
258
259 return 1;
260 };
261
262 for( size_t ii = 0; ii < dirtyItems.size(); ++ii )
263 returns[ii] = tp.submit( conn_lambda, ii, &m_itemList, m_progressReporter );
264
265 for( const std::future<size_t>& ret : returns )
266 {
267 // Here we balance returns with a 250ms timeout to allow UI updating
268 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
269
270 while( status != std::future_status::ready )
271 {
274
275 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
276 }
277 }
278
281 }
282
283#ifdef PROFILE
284 search_basic.Show();
285#endif
286
288}
289
290
292{
293 if( aMode == CSM_PROPAGATE )
294 {
295 return SearchClusters( aMode,
297 -1 );
298 }
299 else
300 {
301 return SearchClusters( aMode,
303 -1 );
304 }
305}
306
307
310 const std::initializer_list<KICAD_T>& aTypes,
311 int aSingleNet, CN_ITEM* rootItem )
312{
313 bool withinAnyNet = ( aMode != CSM_PROPAGATE );
314
315 std::deque<CN_ITEM*> Q;
316 std::set<CN_ITEM*> item_set;
317
318 CLUSTERS clusters;
319
320 if( m_itemList.IsDirty() )
322
323 auto addToSearchList =
324 [&item_set, withinAnyNet, aSingleNet, &aTypes, rootItem ]( CN_ITEM *aItem )
325 {
326 if( withinAnyNet && aItem->Net() <= 0 )
327 return;
328
329 if( !aItem->Valid() )
330 return;
331
332 if( aSingleNet >=0 && aItem->Net() != aSingleNet )
333 return;
334
335 bool found = false;
336
337 for( KICAD_T type : aTypes )
338 {
339 if( aItem->Parent()->Type() == type )
340 {
341 found = true;
342 break;
343 }
344 }
345
346 if( !found && aItem != rootItem )
347 return;
348
349 aItem->SetVisited( false );
350
351 item_set.insert( aItem );
352 };
353
354 std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
355
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() && (*it)->Visited() )
366 it = item_set.erase( item_set.begin() );
367
368 if( it == item_set.end() )
369 break;
370
371 root = *it;
372 root->SetVisited( true );
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( !n->Visited() && n->Valid() )
390 {
391 n->SetVisited( true );
392 Q.push_back( n );
393 }
394 }
395 }
396
397 clusters.push_back( cluster );
398 }
399
401 return CLUSTERS();
402
403 std::sort( clusters.begin(), clusters.end(),
404 []( const std::shared_ptr<CN_CLUSTER>& a, const std::shared_ptr<CN_CLUSTER>& b )
405 {
406 return a->OriginNet() < b->OriginNet();
407 } );
408
409 return clusters;
410}
411
412
414{
415 // Generate CN_ZONE_LAYERs for each island on each layer of each zone
416 //
417 std::vector<CN_ZONE_LAYER*> zitems;
418
419 for( ZONE* zone : aBoard->Zones() )
420 {
421 if( zone->IsOnCopperLayer() )
422 {
423 m_itemMap[zone] = ITEM_MAP_ENTRY();
424 markItemNetAsDirty( zone );
425
426 for( PCB_LAYER_ID layer : zone->GetLayerSet().Seq() )
427 {
428 if( IsCopperLayer( layer ) )
429 {
430 for( int j = 0; j < zone->GetFilledPolysList( layer )->OutlineCount(); j++ )
431 zitems.push_back( new CN_ZONE_LAYER( zone, layer, j ) );
432 }
433 }
434 }
435 }
436
437 // Setup progress metrics
438 //
439 int progressDelta = 50;
440 double size = 0.0;
441
442 size += zitems.size(); // Once for building RTrees
443 size += zitems.size(); // Once for adding to connectivity
444 size += aBoard->Tracks().size();
445
446 for( FOOTPRINT* footprint : aBoard->Footprints() )
447 size += footprint->Pads().size();
448
449 size *= 1.5; // Our caller gets the other third of the progress bar
450
451 progressDelta = std::max( progressDelta, (int) size / 4 );
452
453 auto report =
454 [&]( int progress )
455 {
456 if( aReporter && ( progress % progressDelta ) == 0 )
457 {
458 aReporter->SetCurrentProgress( progress / size );
459 aReporter->KeepRefreshing( false );
460 }
461 };
462
463 // Generate RTrees for CN_ZONE_LAYER items (in parallel)
464 //
466 std::vector<std::future<size_t>> returns( zitems.size() );
467
468 auto cache_zones =
469 [aReporter]( CN_ZONE_LAYER* aZoneLayer ) -> size_t
470 {
471 if( aReporter && aReporter->IsCancelled() )
472 return 0;
473
474 aZoneLayer->BuildRTree();
475
476 if( aReporter )
477 aReporter->AdvanceProgress();
478
479 return 1;
480 };
481
482 for( size_t ii = 0; ii < zitems.size(); ++ii )
483 returns[ii] = tp.submit( cache_zones, zitems[ii] );
484
485 for( const std::future<size_t>& ret : returns )
486 {
487 std::future_status status = ret.wait_for( std::chrono::milliseconds( 250 ) );
488
489 while( status != std::future_status::ready )
490 {
491 if( aReporter )
492 aReporter->KeepRefreshing();
493
494 status = ret.wait_for( std::chrono::milliseconds( 250 ) );
495 }
496
497 }
498
499 // Add CN_ZONE_LAYERS, tracks, and pads to connectivity
500 //
501 int ii = zitems.size();
502
503 for( CN_ZONE_LAYER* zitem : zitems )
504 {
505 m_itemList.Add( zitem );
506 m_itemMap[ zitem->Parent() ].Link( zitem );
507 report( ++ii );
508 }
509
510 for( PCB_TRACK* tv : aBoard->Tracks() )
511 {
512 Add( tv );
513 report( ++ii );
514 }
515
516 for( FOOTPRINT* footprint : aBoard->Footprints() )
517 {
518 for( PAD* pad : footprint->Pads() )
519 {
520 Add( pad );
521 report( ++ii );
522 }
523 }
524
525 if( aReporter )
526 {
527 aReporter->SetCurrentProgress( (double) ii / (double) size );
528 aReporter->KeepRefreshing( false );
529 }
530}
531
532
533void CN_CONNECTIVITY_ALGO::LocalBuild( const std::vector<BOARD_ITEM*>& aItems )
534{
535 for( BOARD_ITEM* item : aItems )
536 {
537 switch( item->Type() )
538 {
539 case PCB_TRACE_T:
540 case PCB_ARC_T:
541 case PCB_VIA_T:
542 case PCB_PAD_T:
543 case PCB_FOOTPRINT_T:
544 Add( item );
545 break;
546
547 default:
548 break;
549 }
550 }
551}
552
553
555{
556 bool skipConflicts = ( aMode == PROPAGATE_MODE::SKIP_CONFLICTS );
557
558 wxLogTrace( wxT( "CN" ), wxT( "propagateConnections: propagate skip conflicts? %d" ),
559 skipConflicts );
560
561 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
562 {
563 if( skipConflicts && cluster->IsConflicting() )
564 {
565 wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; skipping update" ),
566 cluster.get() );
567 }
568 else if( cluster->IsOrphaned() )
569 {
570 wxLogTrace( wxT( "CN" ), wxT( "Skipping orphaned cluster %p [net: %s]" ),
571 cluster.get(),
572 (const char*) cluster->OriginNetName().c_str() );
573 }
574 else if( cluster->HasValidNet() )
575 {
576 if( cluster->IsConflicting() )
577 {
578 wxLogTrace( wxT( "CN" ), wxT( "Conflicting nets in cluster %p; chose %d (%s)" ),
579 cluster.get(),
580 cluster->OriginNet(),
581 cluster->OriginNetName() );
582 }
583
584 // normal cluster: just propagate from the pads
585 int n_changed = 0;
586
587 for( CN_ITEM* item : *cluster )
588 {
589 if( item->CanChangeNet() )
590 {
591 if( item->Valid() && item->Parent()->GetNetCode() != cluster->OriginNet() )
592 {
593 MarkNetAsDirty( item->Parent()->GetNetCode() );
594 MarkNetAsDirty( cluster->OriginNet() );
595
596 if( aCommit )
597 aCommit->Modify( item->Parent() );
598
599 item->Parent()->SetNetCode( cluster->OriginNet() );
600 n_changed++;
601 }
602 }
603 }
604
605 if( n_changed )
606 {
607 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : net : %d %s" ),
608 cluster.get(),
609 cluster->OriginNet(),
610 (const char*) cluster->OriginNetName().c_str() );
611 }
612 else
613 {
614 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : nothing to propagate" ),
615 cluster.get() );
616 }
617 }
618 else
619 {
620 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p : connected to unused net" ),
621 cluster.get() );
622 }
623 }
624}
625
626
628{
630 propagateConnections( aCommit, aMode );
631}
632
633
635 std::vector<int>& aIslands )
636{
637 if( aZone->GetFilledPolysList( aLayer )->IsEmpty() )
638 return;
639
640 aIslands.clear();
641
642 Remove( aZone );
643 Add( aZone );
644
646
647 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
648 {
649 if( cluster->Contains( aZone ) && cluster->IsOrphaned() )
650 {
651 for( CN_ITEM* z : *cluster )
652 {
653 if( z->Parent() == aZone && z->Layer() == aLayer )
654 aIslands.push_back( static_cast<CN_ZONE_LAYER*>(z)->SubpolyIndex() );
655 }
656 }
657 }
658
659 wxLogTrace( wxT( "CN" ), wxT( "Found %u isolated islands\n" ), (unsigned) aIslands.size() );
660}
661
662void CN_CONNECTIVITY_ALGO::FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones,
663 bool aConnectivityAlreadyRebuilt )
664{
665 int progressDelta = 50;
666 int ii = 0;
667
668 progressDelta = std::max( progressDelta, (int) aZones.size() / 4 );
669
670 if( !aConnectivityAlreadyRebuilt )
671 {
672 for( CN_ZONE_ISOLATED_ISLAND_LIST& z : aZones )
673 {
674 Remove( z.m_zone );
675 Add( z.m_zone );
676 ii++;
677
678 if( m_progressReporter && ( ii % progressDelta ) == 0 )
679 {
680 m_progressReporter->SetCurrentProgress( (double) ii / (double) aZones.size() );
682 }
683
685 return;
686 }
687 }
688
690
691 for( CN_ZONE_ISOLATED_ISLAND_LIST& zone : aZones )
692 {
693 for( PCB_LAYER_ID layer : zone.m_zone->GetLayerSet().Seq() )
694 {
695 if( zone.m_zone->GetFilledPolysList( layer )->IsEmpty() )
696 continue;
697
698 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
699 {
700 if( cluster->Contains( zone.m_zone ) && cluster->IsOrphaned() )
701 {
702 for( CN_ITEM* z : *cluster )
703 {
704 if( z->Parent() == zone.m_zone && z->Layer() == layer )
705 {
706 zone.m_islands[layer].push_back(
707 static_cast<CN_ZONE_LAYER*>( z )->SubpolyIndex() );
708 }
709 }
710 }
711 }
712 }
713 }
714}
715
716
718{
720 return m_ratsnestClusters;
721}
722
723
725{
726 if( aNet < 0 )
727 return;
728
729 if( (int) m_dirtyNets.size() <= aNet )
730 {
731 int lastNet = m_dirtyNets.size() - 1;
732
733 if( lastNet < 0 )
734 lastNet = 0;
735
736 m_dirtyNets.resize( aNet + 1 );
737
738 for( int i = lastNet; i < aNet + 1; i++ )
739 m_dirtyNets[i] = true;
740 }
741
742 m_dirtyNets[aNet] = true;
743}
744
745
747{
748 PCB_LAYER_ID layer = aZoneLayer->GetLayer();
749 BOARD_CONNECTED_ITEM* item = aItem->Parent();
750
751 if( !item->IsOnLayer( layer ) )
752 return;
753
754 auto connect =
755 [&]()
756 {
757 aZoneLayer->Connect( aItem );
758 aItem->Connect( aZoneLayer );
759 };
760
761 // Try quick checks first...
762 if( item->Type() == PCB_PAD_T )
763 {
764 PAD* pad = static_cast<PAD*>( item );
765
766 if( pad->ConditionallyFlashed( layer ) && pad->ZoneConnectionCache( layer ) == ZLC_UNCONNECTED )
767 return;
768 }
769 else if( item->Type() == PCB_VIA_T )
770 {
771 PCB_VIA* via = static_cast<PCB_VIA*>( item );
772
773 if( via->ConditionallyFlashed( layer ) && via->ZoneConnectionCache( layer ) == ZLC_UNCONNECTED )
774 return;
775 }
776
777 for( int i = 0; i < aItem->AnchorCount(); ++i )
778 {
779 if( aZoneLayer->ContainsPoint( aItem->GetAnchor( i ) ) )
780 {
781 connect();
782 return;
783 }
784 }
785
786 if( item->Type() == PCB_VIA_T || item->Type() == PCB_PAD_T )
787 {
788 // As long as the pad/via crosses the zone layer, check for the full effective shape
789 // We check for the overlapping layers above
790 if( aZoneLayer->Collide( item->GetEffectiveShape( layer, FLASHING::ALWAYS_FLASHED ).get() ) )
791 connect();
792
793 return;
794 }
795
796 if( aZoneLayer->Collide( item->GetEffectiveShape( layer ).get() ) )
797 connect();
798}
799
801{
802 const ZONE* zoneA = static_cast<const ZONE*>( aZoneLayerA->Parent() );
803 const ZONE* zoneB = static_cast<const ZONE*>( aZoneLayerB->Parent() );
804
805 const BOX2I& boxA = aZoneLayerA->BBox();
806 const BOX2I& boxB = aZoneLayerB->BBox();
807
808 PCB_LAYER_ID layer = aZoneLayerA->GetLayer();
809
810 if( aZoneLayerB->GetLayer() != layer )
811 return;
812
813 if( !boxA.Intersects( boxB ) )
814 return;
815
816 const SHAPE_LINE_CHAIN& outline =
817 zoneA->GetFilledPolysList( layer )->COutline( aZoneLayerA->SubpolyIndex() );
818
819 for( int i = 0; i < outline.PointCount(); i++ )
820 {
821 if( !boxB.Contains( outline.CPoint( i ) ) )
822 continue;
823
824 if( aZoneLayerB->ContainsPoint( outline.CPoint( i ) ) )
825 {
826 aZoneLayerA->Connect( aZoneLayerB );
827 aZoneLayerB->Connect( aZoneLayerA );
828 return;
829 }
830 }
831
832 const SHAPE_LINE_CHAIN& outline2 =
833 zoneB->GetFilledPolysList( layer )->COutline( aZoneLayerB->SubpolyIndex() );
834
835 for( int i = 0; i < outline2.PointCount(); i++ )
836 {
837 if( !boxA.Contains( outline2.CPoint( i ) ) )
838 continue;
839
840 if( aZoneLayerA->ContainsPoint( outline2.CPoint( i ) ) )
841 {
842 aZoneLayerA->Connect( aZoneLayerB );
843 aZoneLayerB->Connect( aZoneLayerA );
844 return;
845 }
846 }
847}
848
849
851{
852 const BOARD_CONNECTED_ITEM* parentA = aCandidate->Parent();
853 const BOARD_CONNECTED_ITEM* parentB = m_item->Parent();
854
855 if( !aCandidate->Valid() || !m_item->Valid() )
856 return true;
857
858 if( parentA == parentB )
859 return true;
860
861 // Don't connect items in different nets that can't be changed
862 if( !aCandidate->CanChangeNet() && !m_item->CanChangeNet() && aCandidate->Net() != m_item->Net() )
863 return true;
864
865 // If both m_item and aCandidate are marked dirty, they will both be searched
866 // Since we are reciprocal in our connection, we arbitrarily pick one of the connections
867 // to conduct the expensive search
868 if( aCandidate->Dirty() && aCandidate < m_item )
869 return true;
870
871 // We should handle zone-zone connection separately
872 if ( parentA->Type() == PCB_ZONE_T && parentB->Type() == PCB_ZONE_T )
873 {
875 static_cast<CN_ZONE_LAYER*>( aCandidate ) );
876 return true;
877 }
878
879 if( parentA->Type() == PCB_ZONE_T )
880 {
881 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( aCandidate ), m_item );
882 return true;
883 }
884
885 if( parentB->Type() == PCB_ZONE_T )
886 {
887 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( m_item ), aCandidate );
888 return true;
889 }
890
891 LSET commonLayers = parentA->GetLayerSet() & parentB->GetLayerSet();
892
893 for( PCB_LAYER_ID layer : commonLayers.Seq() )
894 {
897
898 if( const PAD* pad = dyn_cast<const PAD*>( parentA ) )
899 {
900 if( !pad->ConditionallyFlashed( layer ) )
901 flashingA = FLASHING::ALWAYS_FLASHED;
902 }
903 else if( const PCB_VIA* via = dyn_cast<const PCB_VIA*>( parentA ) )
904 {
905 if( !via->ConditionallyFlashed( layer ) )
906 flashingA = FLASHING::ALWAYS_FLASHED;
907 }
908
909 if( const PAD* pad = dyn_cast<const PAD*>( parentB ) )
910 {
911 if( !pad->ConditionallyFlashed( layer ) )
912 flashingB = FLASHING::ALWAYS_FLASHED;
913 }
914 else if( const PCB_VIA* via = dyn_cast<const PCB_VIA*>( parentB ) )
915 {
916 if( !via->ConditionallyFlashed( layer ) )
917 flashingB = FLASHING::ALWAYS_FLASHED;
918 }
919
920 if( parentA->GetEffectiveShape( layer, flashingA )->Collide(
921 parentB->GetEffectiveShape( layer, flashingB ).get() ) )
922 {
923 m_item->Connect( aCandidate );
924 aCandidate->Connect( m_item );
925 return true;
926 }
927 }
928
929 return true;
930};
931
932
934{
935 m_ratsnestClusters.clear();
936 m_connClusters.clear();
937 m_itemMap.clear();
939
940}
941
943{
944 m_progressReporter = aReporter;
945}
@ ZLC_UNCONNECTED
Definition: board_item.h:48
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:58
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:115
virtual bool IsOnLayer(PCB_LAYER_ID aLayer) const
Test to see if this object is on the given layer.
Definition: board_item.h:245
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.
Definition: board_item.cpp:219
virtual LSET GetLayerSet() const
Return a std::bitset of all layers on which the item physically resides.
Definition: board_item.h:185
BOARD_ITEM_CONTAINER * GetParentFootprint() const
Definition: board_item.cpp:239
virtual bool IsOnCopperLayer() const
Definition: board_item.h:123
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:265
ZONES & Zones()
Definition: board.h:313
FOOTPRINTS & Footprints()
Definition: board.h:307
TRACKS & Tracks()
Definition: board.h:304
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:269
bool Contains(const Vec &aPoint) const
Definition: box2.h:141
bool Remove(BOARD_ITEM *aItem)
void add(Container &c, BItem brditem)
PROGRESS_REPORTER * m_progressReporter
std::vector< std::shared_ptr< CN_CLUSTER > > m_connClusters
void PropagateNets(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
Propagate nets from pads to other items in clusters.
void propagateConnections(BOARD_COMMIT *aCommit=nullptr, PROPAGATE_MODE aMode=PROPAGATE_MODE::SKIP_CONFLICTS)
const CLUSTERS & GetClusters()
void FindIsolatedCopperIslands(ZONE *aZone, PCB_LAYER_ID aLayer, std::vector< int > &aIslands)
const CLUSTERS SearchClusters(CLUSTER_SEARCH_MODE aMode, const std::initializer_list< KICAD_T > &aTypes, int aSingleNet, CN_ITEM *rootItem=nullptr)
void Build(BOARD *aZoneLayer, PROGRESS_REPORTER *aReporter=nullptr)
void MarkNetAsDirty(int aNet)
void markItemNetAsDirty(const BOARD_ITEM *aItem)
std::vector< std::shared_ptr< CN_CLUSTER > > m_ratsnestClusters
std::vector< bool > m_dirtyNets
std::vector< std::shared_ptr< CN_CLUSTER > > CLUSTERS
void LocalBuild(const std::vector< BOARD_ITEM * > &aItems)
std::unordered_map< const BOARD_ITEM *, ITEM_MAP_ENTRY > m_itemMap
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
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
allow parallel connection threads
bool Valid() const
virtual const VECTOR2I GetAnchor(int n) const
bool CanChangeNet() const
void SetVisited(bool aVisited)
bool Dirty() const
BOARD_CONNECTED_ITEM * Parent() const
CN_ITEM * Add(PAD *pad)
void SetDirty(bool aDirty=true)
bool IsDirty() const
void ClearDirtyFlags()
void SetHasInvalid(bool aInvalid=true)
void RemoveInvalidItems(std::vector< CN_ITEM * > &aGarbage)
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)
Create an undo entry for an item that has been already modified.
Definition: commit.h:103
KICAD_T Type() const
Returns the type of object.
Definition: eda_item.h:97
PADS & Pads()
Definition: footprint.h:170
LSET is a set of PCB_LAYER_IDs.
Definition: layer_ids.h:530
LSEQ Seq(const PCB_LAYER_ID *aWishListSequence, unsigned aCount) const
Return an LSEQ from the union of this LSET and a desired sequence.
Definition: lset.cpp:411
Handle the data for a net.
Definition: netinfo.h:66
Definition: pad.h:59
A small class to help profiling.
Definition: profile.h:47
void Show(std::ostream &aStream=std::cerr)
Print the elapsed time (in a suitable unit) to a stream.
Definition: profile.h:103
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).
virtual void SetMaxProgress(int aMaxProgress)=0
Fix the value that gives the 100 percent progress bar length (inside the current virtual zone).
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.
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
const std::shared_ptr< SHAPE_POLY_SET > & GetFilledPolysList(PCB_LAYER_ID aLayer) const
Definition: zone.h:602
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition: zone.h:122
PROPAGATE_MODE
Controls how nets are propagated through clusters.
@ FP_JUST_ADDED
Definition: footprint.h:73
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:147
@ ALWAYS_FLASHED
bool IsCopperLayer(int aLayerId)
Tests whether a layer is a copper layer.
Definition: layer_ids.h:825
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
#define Q()
A structure used for calculating isolated islands on a given zone across all its layers.
thread_pool & GetKiCadThreadPool()
Get a reference to the current thread pool.
Definition: thread_pool.cpp:32
static thread_pool * tp
Definition: thread_pool.cpp:30
BS::thread_pool thread_pool
Definition: thread_pool.h:30
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:78
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:102
@ PCB_ZONE_T
class ZONE, a copper pour area
Definition: typeinfo.h:112
@ 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:103
@ PCB_NETINFO_T
class NETINFO_ITEM, a description of a net
Definition: typeinfo.h:114
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:101