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-2023 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 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
557 {
558 if( cluster->IsConflicting() )
559 {
560 // Conflicting pads in cluster: we don't know the user's intent so best to do
561 // nothing.
562 wxLogTrace( wxT( "CN" ), wxT( "Conflicting pads in cluster %p; skipping propagation" ),
563 cluster.get() );
564 }
565 else if( cluster->HasValidNet() )
566 {
567 // Propagate from the origin (will be a pad if there are any, or another item if
568 // there are no pads).
569 int n_changed = 0;
570
571 for( CN_ITEM* item : *cluster )
572 {
573 if( item->Valid() && item->CanChangeNet()
574 && item->Parent()->GetNetCode() != cluster->OriginNet() )
575 {
576 MarkNetAsDirty( item->Parent()->GetNetCode() );
577 MarkNetAsDirty( cluster->OriginNet() );
578
579 if( aCommit )
580 aCommit->Modify( item->Parent() );
581
582 item->Parent()->SetNetCode( cluster->OriginNet() );
583 n_changed++;
584 }
585 }
586
587 if( n_changed )
588 {
589 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: net: %d %s" ),
590 cluster.get(),
591 cluster->OriginNet(),
592 (const char*) cluster->OriginNetName().c_str() );
593 }
594 else
595 {
596 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: no changeable items to propagate to" ),
597 cluster.get() );
598 }
599 }
600 else
601 {
602 wxLogTrace( wxT( "CN" ), wxT( "Cluster %p: connected to unused net" ),
603 cluster.get() );
604 }
605 }
606}
607
608
610{
612 propagateConnections( aCommit );
613}
614
615
617 std::vector<int>& aIslands )
618{
619 if( aZone->GetFilledPolysList( aLayer )->IsEmpty() )
620 return;
621
622 aIslands.clear();
623
624 Remove( aZone );
625 Add( aZone );
626
628
629 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
630 {
631 if( cluster->Contains( aZone ) && cluster->IsOrphaned() )
632 {
633 for( CN_ITEM* z : *cluster )
634 {
635 if( z->Parent() == aZone && z->Layer() == aLayer )
636 aIslands.push_back( static_cast<CN_ZONE_LAYER*>(z)->SubpolyIndex() );
637 }
638 }
639 }
640
641 wxLogTrace( wxT( "CN" ), wxT( "Found %u isolated islands\n" ), (unsigned) aIslands.size() );
642}
643
644void CN_CONNECTIVITY_ALGO::FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones,
645 bool aConnectivityAlreadyRebuilt )
646{
647 int progressDelta = 50;
648 int ii = 0;
649
650 progressDelta = std::max( progressDelta, (int) aZones.size() / 4 );
651
652 if( !aConnectivityAlreadyRebuilt )
653 {
654 for( CN_ZONE_ISOLATED_ISLAND_LIST& z : aZones )
655 {
656 Remove( z.m_zone );
657 Add( z.m_zone );
658 ii++;
659
660 if( m_progressReporter && ( ii % progressDelta ) == 0 )
661 {
662 m_progressReporter->SetCurrentProgress( (double) ii / (double) aZones.size() );
664 }
665
667 return;
668 }
669 }
670
672
673 for( CN_ZONE_ISOLATED_ISLAND_LIST& zone : aZones )
674 {
675 for( PCB_LAYER_ID layer : zone.m_zone->GetLayerSet().Seq() )
676 {
677 if( zone.m_zone->GetFilledPolysList( layer )->IsEmpty() )
678 continue;
679
680 for( const std::shared_ptr<CN_CLUSTER>& cluster : m_connClusters )
681 {
682 if( cluster->Contains( zone.m_zone ) && cluster->IsOrphaned() )
683 {
684 for( CN_ITEM* z : *cluster )
685 {
686 if( z->Parent() == zone.m_zone && z->Layer() == layer )
687 {
688 zone.m_islands[layer].push_back(
689 static_cast<CN_ZONE_LAYER*>( z )->SubpolyIndex() );
690 }
691 }
692 }
693 }
694 }
695 }
696}
697
698
700{
702 return m_ratsnestClusters;
703}
704
705
707{
708 if( aNet < 0 )
709 return;
710
711 if( (int) m_dirtyNets.size() <= aNet )
712 {
713 int lastNet = m_dirtyNets.size() - 1;
714
715 if( lastNet < 0 )
716 lastNet = 0;
717
718 m_dirtyNets.resize( aNet + 1 );
719
720 for( int i = lastNet; i < aNet + 1; i++ )
721 m_dirtyNets[i] = true;
722 }
723
724 m_dirtyNets[aNet] = true;
725}
726
727
729{
730 PCB_LAYER_ID layer = aZoneLayer->GetLayer();
731 BOARD_CONNECTED_ITEM* item = aItem->Parent();
732
733 if( !item->IsOnLayer( layer ) )
734 return;
735
736 auto connect =
737 [&]()
738 {
739 aZoneLayer->Connect( aItem );
740 aItem->Connect( aZoneLayer );
741 };
742
743 // Try quick checks first...
744 if( item->Type() == PCB_PAD_T )
745 {
746 PAD* pad = static_cast<PAD*>( item );
747
748 if( pad->ConditionallyFlashed( layer )
749 && pad->GetZoneLayerOverride( layer ) == ZLO_FORCE_NO_ZONE_CONNECTION )
750 {
751 return;
752 }
753 }
754 else if( item->Type() == PCB_VIA_T )
755 {
756 PCB_VIA* via = static_cast<PCB_VIA*>( item );
757
758 if( via->ConditionallyFlashed( layer )
759 && via->GetZoneLayerOverride( layer ) == ZLO_FORCE_NO_ZONE_CONNECTION )
760 {
761 return;
762 }
763 }
764
765 for( int i = 0; i < aItem->AnchorCount(); ++i )
766 {
767 if( aZoneLayer->ContainsPoint( aItem->GetAnchor( i ) ) )
768 {
769 connect();
770 return;
771 }
772 }
773
774 if( item->Type() == PCB_VIA_T || item->Type() == PCB_PAD_T )
775 {
776 // As long as the pad/via crosses the zone layer, check for the full effective shape
777 // We check for the overlapping layers above
778 if( aZoneLayer->Collide( item->GetEffectiveShape( layer, FLASHING::ALWAYS_FLASHED ).get() ) )
779 connect();
780
781 return;
782 }
783
784 if( aZoneLayer->Collide( item->GetEffectiveShape( layer ).get() ) )
785 connect();
786}
787
789{
790 const ZONE* zoneA = static_cast<const ZONE*>( aZoneLayerA->Parent() );
791 const ZONE* zoneB = static_cast<const ZONE*>( aZoneLayerB->Parent() );
792
793 const BOX2I& boxA = aZoneLayerA->BBox();
794 const BOX2I& boxB = aZoneLayerB->BBox();
795
796 PCB_LAYER_ID layer = aZoneLayerA->GetLayer();
797
798 if( aZoneLayerB->GetLayer() != layer )
799 return;
800
801 if( !boxA.Intersects( boxB ) )
802 return;
803
804 const SHAPE_LINE_CHAIN& outline =
805 zoneA->GetFilledPolysList( layer )->COutline( aZoneLayerA->SubpolyIndex() );
806
807 for( int i = 0; i < outline.PointCount(); i++ )
808 {
809 if( !boxB.Contains( outline.CPoint( i ) ) )
810 continue;
811
812 if( aZoneLayerB->ContainsPoint( outline.CPoint( i ) ) )
813 {
814 aZoneLayerA->Connect( aZoneLayerB );
815 aZoneLayerB->Connect( aZoneLayerA );
816 return;
817 }
818 }
819
820 const SHAPE_LINE_CHAIN& outline2 =
821 zoneB->GetFilledPolysList( layer )->COutline( aZoneLayerB->SubpolyIndex() );
822
823 for( int i = 0; i < outline2.PointCount(); i++ )
824 {
825 if( !boxA.Contains( outline2.CPoint( i ) ) )
826 continue;
827
828 if( aZoneLayerA->ContainsPoint( outline2.CPoint( i ) ) )
829 {
830 aZoneLayerA->Connect( aZoneLayerB );
831 aZoneLayerB->Connect( aZoneLayerA );
832 return;
833 }
834 }
835}
836
837
839{
840 const BOARD_CONNECTED_ITEM* parentA = aCandidate->Parent();
841 const BOARD_CONNECTED_ITEM* parentB = m_item->Parent();
842
843 if( !aCandidate->Valid() || !m_item->Valid() )
844 return true;
845
846 if( parentA == parentB )
847 return true;
848
849 // Don't connect items in different nets that can't be changed
850 if( !aCandidate->CanChangeNet() && !m_item->CanChangeNet() && aCandidate->Net() != m_item->Net() )
851 return true;
852
853 // If both m_item and aCandidate are marked dirty, they will both be searched
854 // Since we are reciprocal in our connection, we arbitrarily pick one of the connections
855 // to conduct the expensive search
856 if( aCandidate->Dirty() && aCandidate < m_item )
857 return true;
858
859 // We should handle zone-zone connection separately
860 if ( parentA->Type() == PCB_ZONE_T && parentB->Type() == PCB_ZONE_T )
861 {
863 static_cast<CN_ZONE_LAYER*>( aCandidate ) );
864 return true;
865 }
866
867 if( parentA->Type() == PCB_ZONE_T )
868 {
869 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( aCandidate ), m_item );
870 return true;
871 }
872
873 if( parentB->Type() == PCB_ZONE_T )
874 {
875 checkZoneItemConnection( static_cast<CN_ZONE_LAYER*>( m_item ), aCandidate );
876 return true;
877 }
878
879 LSET commonLayers = parentA->GetLayerSet() & parentB->GetLayerSet();
880
881 for( PCB_LAYER_ID layer : commonLayers.Seq() )
882 {
885
886 if( const PAD* pad = dyn_cast<const PAD*>( parentA ) )
887 {
888 if( !pad->ConditionallyFlashed( layer ) )
889 flashingA = FLASHING::ALWAYS_FLASHED;
890 }
891 else if( const PCB_VIA* via = dyn_cast<const PCB_VIA*>( parentA ) )
892 {
893 if( !via->ConditionallyFlashed( layer ) )
894 flashingA = FLASHING::ALWAYS_FLASHED;
895 }
896
897 if( const PAD* pad = dyn_cast<const PAD*>( parentB ) )
898 {
899 if( !pad->ConditionallyFlashed( layer ) )
900 flashingB = FLASHING::ALWAYS_FLASHED;
901 }
902 else if( const PCB_VIA* via = dyn_cast<const PCB_VIA*>( parentB ) )
903 {
904 if( !via->ConditionallyFlashed( layer ) )
905 flashingB = FLASHING::ALWAYS_FLASHED;
906 }
907
908 if( parentA->GetEffectiveShape( layer, flashingA )->Collide(
909 parentB->GetEffectiveShape( layer, flashingB ).get() ) )
910 {
911 m_item->Connect( aCandidate );
912 aCandidate->Connect( m_item );
913 return true;
914 }
915 }
916
917 return true;
918};
919
920
922{
923 m_ratsnestClusters.clear();
924 m_connClusters.clear();
925 m_itemMap.clear();
927
928}
929
931{
932 m_progressReporter = aReporter;
933}
@ ZLO_FORCE_NO_ZONE_CONNECTION
Definition: board_item.h:60
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:70
virtual bool IsConnected() const
Returns information if the object is derived from BOARD_CONNECTED_ITEM.
Definition: board_item.h:127
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:197
BOARD_ITEM_CONTAINER * GetParentFootprint() const
Definition: board_item.cpp:239
virtual bool IsOnLayer(PCB_LAYER_ID aLayer, bool aIncludeCourtyards=false) const
Test to see if this object is on the given layer.
Definition: board_item.h:257
virtual bool IsOnCopperLayer() const
Definition: board_item.h:135
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:269
ZONES & Zones()
Definition: board.h:317
FOOTPRINTS & Footprints()
Definition: board.h:311
TRACKS & Tracks()
Definition: board.h:308
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 propagateConnections(BOARD_COMMIT *aCommit=nullptr)
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
void PropagateNets(BOARD_COMMIT *aCommit=nullptr)
Propagate nets from pads to other items in clusters.
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:532
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:67
Definition: pad.h:60
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:608
virtual LSET GetLayerSet() const override
Return a std::bitset of all layers on which the item physically resides.
Definition: zone.h:122
@ 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:827
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:59
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