kicad-developers team mailing list archive
-
kicad-developers team
-
Mailing list archive
-
Message #36032
Re: [PATCH] Large board speed
Hi JP-
Thanks! Yes, your patch makes sense and the improved pad count speed is
nice. I've incorporated the static->dynamic change into the attached
patch.
Best-
Seth
Am Sa., 2. Juni 2018 um 08:47 Uhr schrieb jp charras <jp.charras@xxxxxxxxxx
>:
> Le 02/06/2018 à 14:12, jp charras a écrit :
> > Le 02/06/2018 à 11:02, jp charras a écrit :
> >> I have made a few tests (not a lot!) and did not see any problem.
> >>
> >
> > Hi Seth,
> >
> > I found an issue due to changes in connectivity algo:
> > CONNECTIVITY_DATA::GetPadCount( int aNet ) is significantly slower.
> >
> > And creates an issue in copper zones edition, when the net sorting is
> made by pad count.
> > The calculation time is so long it can freeze Pcbnew for large boards.
> >
> > This is due to a absolutely non optimized sort function (not optimized
> due to a lot of changes since
> > it was written) and the increased calculation time in
> CONNECTIVITY_DATA::GetPadCount due to a
> > dynamic cast instead of a static cast.
> >
> > Could you have a look into this patch that fixes this issue?
> > Thanks
> >
>
> Hi Seth,
> Please, just have a look into this patch about your change in
> CONNECTIVITY_DATA::GetPadCount().
>
> I have a better fix for the issue in sort by pad count function used in
> copper zones settings dialog
>
> Thanks.
>
> >>
> >>>
> >>> On Sat, Jun 2, 2018 at 12:17 AM, Wayne Stambaugh <stambaughw@xxxxxxxxx
> >>> <mailto:stambaughw@xxxxxxxxx>> wrote:
> >>>
> >>> On 6/1/2018 3:58 PM, Tomasz Wlostowski wrote:
> >>> > On 01/06/18 20:23, Seth Hillbrand wrote:
> >>> >> I think maybe we are seeing the severity of these bugs
> differently.
> >>> >> There are three substantial issues addressed by this patch.
> While they
> >>> >> don't affect many users, they do prevent KiCad from being used
> for
> >>> >> larger, more complex boards that we nominally support. This is
> a also
> >>> >> regression from v4.
> >>> >
> >>> > Hi all,
> >>> >
> >>> > I vote for merging Seth's patch.
> >>> >
> >>> > For those concerned about its correctness: the connectivity algo
> is
> >>> > designed in such way that in case of bugs in collision search
> (other
> >>> > than in BOARD_ITEM::HitTest()/POLY_GRID_PARTITION which haven't
> been
> >>> > touched for a year), it may find false unconnected items, but
> not false
> >>> > connected ones. In the worst case, we'll have false 'unconnected
> items'
> >>> > warnings in the DRC, but I doubt there will be any. The patch is
> simple
> >>> > and elegant.
> >>> >
> >>> > Tom
> >>>
> >>> Tom,
> >>>
> >>> Have you actually tested the patch? Voting for it doesn't help me
> make
> >>> an informed decision. What I really need is test feedback. I'm
> not
> >>> opposed to merging it but I would like as large of a test group as
> >>> possible so I have some confidence that it's not going to cause a
> bunch
> >>> of issues this close to the stable release. I plan on testing it
> >>> tomorrow but I am an infinite sample of one. A few other testers
> would
> >>> be appreciated before I'm willing to sign off on committing it.
> >>>
> >>> Cheers,
> >>>
> >>> Wayne
> >>>
> >>
> >
> >
> >
> >
> > _______________________________________________
> > Mailing list: https://launchpad.net/~kicad-developers
> > Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> > Unsubscribe : https://launchpad.net/~kicad-developers
> > More help : https://help.launchpad.net/ListHelp
> >
>
>
> --
> Jean-Pierre CHARRAS
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help : https://help.launchpad.net/ListHelp
>
From 0f406a6e6d7527fb076e1c1536695661cc506e1a Mon Sep 17 00:00:00 2001
From: Seth Hillbrand <hillbrand@xxxxxxxxxxx>
Date: Sun, 20 May 2018 17:06:01 -0700
Subject: [PATCH] Adjust connectivity to use RTree
Connectivity searches were slow for large, complex boards. This was
partly due to the need to search all lists for possible connections
between anchors.
We remove this requirement by creating an RTree based on items' bounding
boxes similar to the PNS router. Then we get both the colliding items
and search forward/backward to see if there are connections between the
anchors and the other item.
Because we use RTree, we no longer need the maintenance overhead of multiple
item lists and an anchor list in the connectivity class.
Fixes: lp:1701791
* https://bugs.launchpad.net/kicad/+bug/1701791
Fixes: lp:1769408
* https://bugs.launchpad.net/kicad/+bug/1769408
Fixes: lp:1761989
* https://bugs.launchpad.net/kicad/+bug/1761989
---
pcbnew/class_board.cpp | 4 +-
pcbnew/connectivity_algo.cpp | 409 +++++++++++++++++--------------------------
pcbnew/connectivity_algo.h | 215 ++++++++---------------
pcbnew/connectivity_data.cpp | 4 +-
pcbnew/connectivity_rtree.h | 108 ++++++++++++
5 files changed, 340 insertions(+), 400 deletions(-)
create mode 100644 pcbnew/connectivity_rtree.h
diff --git a/pcbnew/class_board.cpp b/pcbnew/class_board.cpp
index 1371c56ff..720da1f76 100644
--- a/pcbnew/class_board.cpp
+++ b/pcbnew/class_board.cpp
@@ -2704,9 +2704,9 @@ void BOARD::ReplaceNetlist( NETLIST& aNetlist, bool aDeleteSinglePadNets,
{
std::vector<unsigned int> padCount( connAlgo->NetCount() );
- for( const auto cnItem : connAlgo->PadList() )
+ for( const auto cnItem : connAlgo->ItemList() )
{
- if( !cnItem->Valid() )
+ if( !cnItem->Valid() || cnItem->Parent()->Type() != PCB_PAD_T )
continue;
int net = cnItem->Parent()->GetNetCode();
diff --git a/pcbnew/connectivity_algo.cpp b/pcbnew/connectivity_algo.cpp
index c9c4f6b21..9d110ddbf 100644
--- a/pcbnew/connectivity_algo.cpp
+++ b/pcbnew/connectivity_algo.cpp
@@ -24,6 +24,7 @@
#include <connectivity_algo.h>
#include <widgets/progress_reporter.h>
+#include <geometry/geometry_utils.h>
#include <thread>
#include <mutex>
@@ -168,25 +169,25 @@ bool CN_CONNECTIVITY_ALGO::Remove( BOARD_ITEM* aItem )
m_itemMap.erase( static_cast<BOARD_CONNECTED_ITEM*>( pad ) );
}
- m_padList.SetDirty( true );
+ m_itemList.SetDirty( true );
break;
case PCB_PAD_T:
m_itemMap[ static_cast<BOARD_CONNECTED_ITEM*>( aItem ) ].MarkItemsAsInvalid();
m_itemMap.erase( static_cast<BOARD_CONNECTED_ITEM*>( aItem ) );
- m_padList.SetDirty( true );
+ m_itemList.SetDirty( true );
break;
case PCB_TRACE_T:
m_itemMap[ static_cast<BOARD_CONNECTED_ITEM*>( aItem ) ].MarkItemsAsInvalid();
m_itemMap.erase( static_cast<BOARD_CONNECTED_ITEM*>( aItem ) );
- m_trackList.SetDirty( true );
+ m_itemList.SetDirty( true );
break;
case PCB_VIA_T:
m_itemMap[ static_cast<BOARD_CONNECTED_ITEM*>( aItem ) ].MarkItemsAsInvalid();
m_itemMap.erase( static_cast<BOARD_CONNECTED_ITEM*>( aItem ) );
- m_viaList.SetDirty( true );
+ m_itemList.SetDirty( true );
break;
case PCB_ZONE_AREA_T:
@@ -202,6 +203,10 @@ bool CN_CONNECTIVITY_ALGO::Remove( BOARD_ITEM* aItem )
return false;
}
+ // Once we delete an item, it may connect between lists, so mark both as potentially invalid
+ m_itemList.SetHasInvalid( true );
+ m_zoneList.SetHasInvalid( true );
+
return true;
}
@@ -243,7 +248,7 @@ bool CN_CONNECTIVITY_ALGO::Add( BOARD_ITEM* aItem )
if( m_itemMap.find( pad ) != m_itemMap.end() )
return false;
- add( m_padList, pad );
+ add( m_itemList, pad );
}
break;
@@ -252,7 +257,7 @@ bool CN_CONNECTIVITY_ALGO::Add( BOARD_ITEM* aItem )
if( m_itemMap.find ( static_cast<D_PAD*>( aItem ) ) != m_itemMap.end() )
return false;
- add( m_padList, static_cast<D_PAD*>( aItem ) );
+ add( m_itemList, static_cast<D_PAD*>( aItem ) );
break;
@@ -261,7 +266,7 @@ bool CN_CONNECTIVITY_ALGO::Add( BOARD_ITEM* aItem )
if( m_itemMap.find( static_cast<TRACK*>( aItem ) ) != m_itemMap.end() )
return false;
- add( m_trackList, static_cast<TRACK*>( aItem ) );
+ add( m_itemList, static_cast<TRACK*>( aItem ) );
break;
}
@@ -270,7 +275,7 @@ bool CN_CONNECTIVITY_ALGO::Add( BOARD_ITEM* aItem )
if( m_itemMap.find( static_cast<VIA*>( aItem ) ) != m_itemMap.end() )
return false;
- add( m_viaList, static_cast<VIA*>( aItem ) );
+ add( m_itemList, static_cast<VIA*>( aItem ) );
break;
@@ -302,143 +307,6 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
{
std::mutex cnListLock;
- int totalDirtyCount = 0;
-
- if( m_lastSearchWithZones != aIncludeZones )
- {
- m_padList.MarkAllAsDirty();
- m_viaList.MarkAllAsDirty();
- m_trackList.MarkAllAsDirty();
- m_zoneList.MarkAllAsDirty();
- }
-
- m_lastSearchWithZones = aIncludeZones;
-
- auto checkForConnection = [ &cnListLock ] ( const CN_ANCHOR_PTR point, CN_ITEM* aRefItem, int aMaxDist = 0 )
- {
- const auto parent = aRefItem->Parent();
-
- assert( point->Item() );
- assert( point->Item()->Parent() );
- assert( aRefItem->Parent() );
-
- if( !point->Item()->Valid() )
- return;
-
- if( !aRefItem->Valid() )
- return;
-
- if( parent == point->Item()->Parent() )
- return;
-
- if( !( parent->GetLayerSet() &
- point->Item()->Parent()->GetLayerSet() ).any() )
- return;
-
- switch( parent->Type() )
- {
- case PCB_PAD_T:
- case PCB_VIA_T:
-
- if( parent->HitTest( wxPoint( point->Pos().x, point->Pos().y ) ) )
- {
- std::lock_guard<std::mutex> lock( cnListLock );
- CN_ITEM::Connect( aRefItem, point->Item() );
- }
-
- break;
-
- case PCB_TRACE_T:
- {
- const auto track = static_cast<TRACK*> ( parent );
-
- const VECTOR2I d_start( VECTOR2I( track->GetStart() ) - point->Pos() );
- const VECTOR2I d_end( VECTOR2I( track->GetEnd() ) - point->Pos() );
-
- if( d_start.EuclideanNorm() < aMaxDist
- || d_end.EuclideanNorm() < aMaxDist )
- {
- std::lock_guard<std::mutex> lock( cnListLock );
- CN_ITEM::Connect( aRefItem, point->Item() );
- }
- break;
- }
-
- case PCB_ZONE_T:
- case PCB_ZONE_AREA_T:
- {
- const auto zone = static_cast<ZONE_CONTAINER*> ( parent );
- auto zoneItem = static_cast<CN_ZONE*> ( aRefItem );
-
- if( point->Item()->Net() != parent->GetNetCode() )
- return;
-
- if( !( zone->GetLayerSet() &
- point->Item()->Parent()->GetLayerSet() ).any() )
- return;
-
- if( zoneItem->ContainsAnchor( point ) )
- {
- std::lock_guard<std::mutex> lock( cnListLock );
- CN_ITEM::Connect( zoneItem, point->Item() );
- }
-
- break;
-
- }
- default :
- assert( false );
- }
- };
-
- auto checkInterZoneConnection = [ &cnListLock ] ( CN_ZONE* testedZone, CN_ZONE* aRefZone )
- {
- const auto parentZone = static_cast<const ZONE_CONTAINER*>( aRefZone->Parent() );
-
- if( testedZone->Parent()->Type () != PCB_ZONE_AREA_T )
- return;
-
- if( testedZone == aRefZone )
- return;
-
- if( testedZone->Parent() == aRefZone->Parent() )
- return;
-
- if( testedZone->Net() != parentZone->GetNetCode() )
- return; // we only test zones belonging to the same net
-
- if( !( testedZone->Parent()->GetLayerSet() & parentZone->GetLayerSet() ).any() )
- return; // and on same layer
-
- const auto& outline = parentZone->GetFilledPolysList().COutline( aRefZone->SubpolyIndex() );
-
- for( int i = 0; i < outline.PointCount(); i++ )
- {
- if( testedZone->ContainsPoint( outline.CPoint( i ) ) )
- {
- std::lock_guard<std::mutex> lock( cnListLock );
-
- CN_ITEM::Connect( aRefZone, testedZone );
- return;
- }
- }
-
- const auto testedZoneParent = static_cast<const ZONE_CONTAINER*>( testedZone->Parent() );
-
- const auto& outline2 = testedZoneParent->GetFilledPolysList().COutline( testedZone->SubpolyIndex() );
-
- for( int i = 0; i < outline2.PointCount(); i++ )
- {
- if( aRefZone->ContainsPoint( outline2.CPoint( i ) ) )
- {
- std::lock_guard<std::mutex> lock( cnListLock );
-
- CN_ITEM::Connect( aRefZone, testedZone );
- return;
- }
- }
- };
-
#ifdef CONNECTIVITY_DEBUG
printf("Search start\n");
#endif
@@ -449,16 +317,12 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
std::vector<CN_ITEM*> garbage;
garbage.reserve( 1024 );
- m_padList.RemoveInvalidItems( garbage );
- m_viaList.RemoveInvalidItems( garbage );
- m_trackList.RemoveInvalidItems( garbage );
+ m_itemList.RemoveInvalidItems( garbage );
m_zoneList.RemoveInvalidItems( garbage );
for( auto item : garbage )
delete item;
- //auto all = allItemsInBoard();
-
#ifdef CONNECTIVITY_DEBUG
for( auto item : m_padList )
if( all.find( item->Parent() ) == all.end() ) { printf("Failing pad : %p\n", item->Parent() ); assert ( false ); }
@@ -477,49 +341,20 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
garbage_collection.Show();
PROF_COUNTER search_cnt( "search-connections" );
PROF_COUNTER search_basic( "search-basic" );
- PROF_COUNTER search_pads( "search-pads" );
#endif
- if( m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
+ if( m_itemList.IsDirty() )
{
- totalDirtyCount++;
-
- for( auto padItem : m_padList )
- {
- auto pad = static_cast<D_PAD*> ( padItem->Parent() );
- auto searchPads = std::bind( checkForConnection, _1, padItem );
-
- m_padList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
- m_trackList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
- m_viaList.FindNearby( pad->ShapePos(), pad->GetBoundingRadius(), searchPads, pad->GetLayerSet() );
- }
-#ifdef PROFILE
- search_pads.Show();
- PROF_COUNTER search_tracks( "search-tracks" );
-#endif
-
- for( auto& trackItem : m_trackList )
- {
- auto track = static_cast<TRACK*> ( trackItem->Parent() );
- int dist_max = track->GetWidth() / 2;
- auto searchTracks = std::bind( checkForConnection, _1, trackItem, dist_max );
-
- m_trackList.FindNearby( track->GetStart(), dist_max, searchTracks, track->GetLayerSet() );
- m_trackList.FindNearby( track->GetEnd(), dist_max, searchTracks, track->GetLayerSet() );
- }
-#ifdef PROFILE
- search_tracks.Show();
-#endif
-
- for( auto& viaItem : m_viaList )
+ for( auto item : m_itemList )
{
- auto via = static_cast<VIA*> ( viaItem->Parent() );
- int dist_max = via->GetWidth() / 2;
- auto searchVias = std::bind( checkForConnection, _1, viaItem, dist_max );
+ if( item->Dirty() )
+ {
+ CN_VISITOR visitor( item, &cnListLock );
+ m_itemList.FindNearby( item, visitor );
- totalDirtyCount++;
- m_viaList.FindNearby( via->GetStart(), dist_max, searchVias );
- m_trackList.FindNearby( via->GetStart(), dist_max, searchVias );
+ if( aIncludeZones )
+ m_zoneList.FindNearby( item, visitor );
+ }
}
}
@@ -529,8 +364,6 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
if( aIncludeZones )
{
- int cnt = 0;
-
if( m_progressReporter )
{
m_progressReporter->SetMaxProgress( m_zoneList.Size() );
@@ -556,25 +389,17 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
{
auto item = m_zoneList[i];
auto zoneItem = static_cast<CN_ZONE *> (item);
- auto searchZones = std::bind( checkForConnection, _1, zoneItem );
- if( zoneItem->Dirty() || m_padList.IsDirty() || m_trackList.IsDirty() || m_viaList.IsDirty() )
+ if( zoneItem->Dirty() )
{
- totalDirtyCount++;
- m_viaList.FindNearby( zoneItem->BBox(), searchZones );
- m_trackList.FindNearby( zoneItem->BBox(), searchZones );
- m_padList.FindNearby( zoneItem->BBox(), searchZones );
- m_zoneList.FindNearbyZones( zoneItem->BBox(), std::bind( checkInterZoneConnection, _1, zoneItem ) );
+ CN_VISITOR visitor( item, &cnListLock );
+ m_itemList.FindNearby( item, visitor );
+ m_zoneList.FindNearby( item, visitor );
}
+ if (m_progressReporter)
{
- std::lock_guard<std::mutex> lock( cnListLock );
- cnt++;
-
- if (m_progressReporter)
- {
- m_progressReporter->AdvanceProgress();
- }
+ m_progressReporter->AdvanceProgress();
}
}
}
@@ -582,9 +407,7 @@ void CN_CONNECTIVITY_ALGO::searchConnections( bool aIncludeZones )
m_zoneList.ClearDirtyFlags();
}
- m_padList.ClearDirtyFlags();
- m_viaList.ClearDirtyFlags();
- m_trackList.ClearDirtyFlags();
+ m_itemList.ClearDirtyFlags();
#ifdef CONNECTIVITY_DEBUG
printf("Search end\n");
@@ -608,6 +431,9 @@ void CN_ITEM::RemoveInvalidRefs()
void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
{
+ if( !m_hasInvalid )
+ return;
+
auto lastItem = std::remove_if(m_items.begin(), m_items.end(), [&aGarbage] ( CN_ITEM* item )
{
if( !item->Valid() )
@@ -619,36 +445,22 @@ void CN_LIST::RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage )
return false;
} );
- if( lastItem != m_items.end())
- {
- auto lastAnchor = std::remove_if(m_anchors.begin(), m_anchors.end(),
- [] ( const CN_ANCHOR_PTR anchor ) {
- return !anchor->Valid();
- } );
-
- m_anchors.resize( lastAnchor - m_anchors.begin() );
- for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
- {
- lastAnchor = std::remove_if(m_layer_anchors[i].begin(), m_layer_anchors[i].end(),
- [] ( const CN_ANCHOR_PTR anchor ) {
- return !anchor->Valid();
- } );
-
- m_layer_anchors[i].resize( lastAnchor - m_layer_anchors[i].begin() );
- }
-
- m_items.resize( lastItem - m_items.begin() );
- }
+ m_items.resize( lastItem - m_items.begin() );
// fixme: mem leaks
for( auto item : m_items )
item->RemoveInvalidRefs();
+
+ for( auto item : aGarbage )
+ m_index.Remove( item );
+
+ m_hasInvalid = false;
}
bool CN_CONNECTIVITY_ALGO::isDirty() const
{
- return m_viaList.IsDirty() || m_trackList.IsDirty() || m_zoneList.IsDirty() || m_padList.IsDirty();
+ return m_itemList.IsDirty() || m_zoneList.IsDirty();
}
@@ -706,9 +518,7 @@ const CN_CONNECTIVITY_ALGO::CLUSTERS CN_CONNECTIVITY_ALGO::SearchClusters( CLUST
head->ListInsert( aItem );
};
- std::for_each( m_padList.begin(), m_padList.end(), addToSearchList );
- std::for_each( m_trackList.begin(), m_trackList.end(), addToSearchList );
- std::for_each( m_viaList.begin(), m_viaList.end(), addToSearchList );
+ std::for_each( m_itemList.begin(), m_itemList.end(), addToSearchList );
if( includeZones )
{
@@ -972,6 +782,116 @@ void CN_CONNECTIVITY_ALGO::MarkNetAsDirty( int aNet )
}
+void CN_VISITOR::checkZoneItemConnection( CN_ZONE* aZone, CN_ITEM* aItem )
+{
+ auto zoneItem = static_cast<CN_ZONE*> ( aZone );
+
+ if( zoneItem->Net() != aItem->Net() && !aItem->CanChangeNet() )
+ return;
+
+ if( zoneItem->ContainsPoint( aItem->GetAnchor( 0 ) ) ||
+ ( aItem->Parent()->Type() == PCB_TRACE_T &&
+ zoneItem->ContainsPoint( aItem->GetAnchor( 1 ) ) ) )
+ {
+ std::lock_guard<std::mutex> lock( *m_listLock );
+ CN_ITEM::Connect( zoneItem, aItem );
+ }
+}
+
+void CN_VISITOR::checkZoneZoneConnection( CN_ZONE* aZoneA, CN_ZONE* aZoneB )
+{
+ const auto refParent = static_cast<const ZONE_CONTAINER*>( aZoneA->Parent() );
+ const auto testedParent = static_cast<const ZONE_CONTAINER*>( aZoneB->Parent() );
+
+ if( testedParent->Type () != PCB_ZONE_AREA_T )
+ return;
+
+ if( aZoneB == aZoneA || refParent == testedParent )
+ return;
+
+ if( aZoneB->Net() != aZoneA->Net() )
+ return; // we only test zones belonging to the same net
+
+ const auto& outline = refParent->GetFilledPolysList().COutline( aZoneA->SubpolyIndex() );
+
+ for( int i = 0; i < outline.PointCount(); i++ )
+ {
+ if( aZoneB->ContainsPoint( outline.CPoint( i ) ) )
+ {
+ std::lock_guard<std::mutex> lock( *m_listLock );
+ CN_ITEM::Connect( aZoneA, aZoneB );
+ return;
+ }
+ }
+
+ const auto& outline2 = testedParent->GetFilledPolysList().COutline( aZoneB->SubpolyIndex() );
+
+ for( int i = 0; i < outline2.PointCount(); i++ )
+ {
+ if( aZoneA->ContainsPoint( outline2.CPoint( i ) ) )
+ {
+ std::lock_guard<std::mutex> lock( *m_listLock );
+ CN_ITEM::Connect( aZoneA, aZoneB );
+ return;
+ }
+ }
+}
+
+
+bool CN_VISITOR::operator()( CN_ITEM* aCandidate )
+{
+ const auto parentA = aCandidate->Parent();
+ const auto parentB = m_item->Parent();
+
+ if( !aCandidate->Valid() || !m_item->Valid() )
+ return true;
+
+ if( parentA == parentB )
+ return true;
+
+ if( !( parentA->GetLayerSet() & parentB->GetLayerSet() ).any() )
+ return true;
+
+ // We should handle zone-zone connection separately
+ if ( ( parentA->Type() == PCB_ZONE_AREA_T || parentA->Type() == PCB_ZONE_T ) &&
+ ( parentB->Type() == PCB_ZONE_AREA_T || parentB->Type() == PCB_ZONE_T ) )
+ {
+ checkZoneZoneConnection( static_cast<CN_ZONE*>( m_item ),
+ static_cast<CN_ZONE*>( aCandidate ) );
+ return true;
+ }
+
+ if( parentA->Type() == PCB_ZONE_AREA_T || parentA->Type() == PCB_ZONE_T)
+ {
+ checkZoneItemConnection( static_cast<CN_ZONE*>( aCandidate ), m_item );
+ return true;
+ }
+
+ if( parentB->Type() == PCB_ZONE_AREA_T || parentB->Type() == PCB_ZONE_T)
+ {
+ checkZoneItemConnection( static_cast<CN_ZONE*>( m_item ), aCandidate );
+ return true;
+ }
+
+ // Items do not necessarily have reciprocity as we only check for anchors
+ // therefore, we check HitTest both directions A->B & B->A
+ // TODO: Check for collision geometry on extended features
+ wxPoint ptA1( aCandidate->GetAnchor( 0 ).x, aCandidate->GetAnchor( 0 ).y );
+ wxPoint ptA2( aCandidate->GetAnchor( 1 ).x, aCandidate->GetAnchor( 1 ).y );
+ wxPoint ptB1( m_item->GetAnchor( 0 ).x, m_item->GetAnchor( 0 ).y );
+ wxPoint ptB2( m_item->GetAnchor( 1 ).x, m_item->GetAnchor( 1 ).y );
+ if( parentA->HitTest( ptB1 ) || parentB->HitTest( ptA1 ) ||
+ ( parentA->Type() == PCB_TRACE_T && parentB->HitTest( ptA2 ) ) ||
+ ( parentB->Type() == PCB_TRACE_T && parentA->HitTest( ptB2 ) ) )
+ {
+ std::lock_guard<std::mutex> lock( *m_listLock );
+ CN_ITEM::Connect( m_item, aCandidate );
+ }
+
+ return true;
+};
+
+
int CN_ITEM::AnchorCount() const
{
if( !m_valid )
@@ -1064,9 +984,7 @@ void CN_CONNECTIVITY_ALGO::Clear()
m_ratsnestClusters.clear();
m_connClusters.clear();
m_itemMap.clear();
- m_padList.Clear();
- m_trackList.Clear();
- m_viaList.Clear();
+ m_itemList.Clear();
m_zoneList.Clear();
}
@@ -1074,13 +992,8 @@ void CN_CONNECTIVITY_ALGO::Clear()
void CN_CONNECTIVITY_ALGO::ForEachItem( const std::function<void( CN_ITEM& )>& aFunc )
{
- for( auto item : m_padList )
- aFunc( *item );
-
- for( auto item : m_viaList )
- aFunc( *item );
- for( auto item : m_trackList )
+ for( auto item : m_itemList )
aFunc( *item );
for( auto item : m_zoneList )
@@ -1090,17 +1003,11 @@ void CN_CONNECTIVITY_ALGO::ForEachItem( const std::function<void( CN_ITEM& )>& a
void CN_CONNECTIVITY_ALGO::ForEachAnchor( const std::function<void( CN_ANCHOR& )>& aFunc )
{
- for( const auto& anchor : m_padList.Anchors() )
- aFunc( *anchor );
-
- for( const auto& anchor : m_viaList.Anchors() )
- aFunc( *anchor );
-
- for( const auto& anchor : m_trackList.Anchors() )
- aFunc( *anchor );
-
- for( const auto& anchor : m_zoneList.Anchors() )
- aFunc( *anchor );
+ ForEachItem( [aFunc] ( CN_ITEM& item ) {
+ for( const auto& anchor : item.Anchors() )
+ aFunc( *anchor );
+ }
+ );
}
diff --git a/pcbnew/connectivity_algo.h b/pcbnew/connectivity_algo.h
index a36af5fbf..ea79b9fea 100644
--- a/pcbnew/connectivity_algo.h
+++ b/pcbnew/connectivity_algo.h
@@ -43,6 +43,7 @@
#include <deque>
#include <intrusive_list.h>
+#include <connectivity_rtree.h>
#include <connectivity_data.h>
class CN_ITEM;
@@ -286,6 +287,9 @@ private:
///> dirty flag, used to identify recently added item not yet scanned into the connectivity search
bool m_dirty;
+ ///> bounding box for the item
+ BOX2I m_bbox;
+
public:
void Dump();
@@ -301,11 +305,9 @@ public:
virtual ~CN_ITEM() {};
- CN_ANCHOR_PTR AddAnchor( const VECTOR2I& aPos )
+ void AddAnchor( const VECTOR2I& aPos )
{
- m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
- //printf("%p add %d\n", this, m_anchors.size() );
- return m_anchors.back();
+ m_anchors.emplace_back( std::make_unique<CN_ANCHOR>( aPos, this ) );
}
CN_ANCHORS& Anchors()
@@ -333,6 +335,16 @@ public:
return m_dirty;
}
+ const BOX2I BBox()
+ {
+ if( m_dirty )
+ {
+ EDA_RECT box = m_parent->GetBoundingBox();
+ m_bbox = BOX2I( box.GetPosition(), box.GetSize() );
+ }
+ return m_bbox;
+ }
+
BOARD_CONNECTED_ITEM* Parent() const
{
return m_parent;
@@ -407,45 +419,23 @@ class CN_LIST
{
private:
bool m_dirty;
- std::vector<CN_ANCHOR_PTR> m_anchors;
- CN_ANCHORS m_layer_anchors[PCB_LAYER_ID_COUNT];
+ bool m_hasInvalid;
+
+ CN_RTREE<CN_ITEM*> m_index;
protected:
std::vector<CN_ITEM*> m_items;
- void addAnchor( VECTOR2I pos, CN_ITEM* item )
+ void addItemtoTree( CN_ITEM* item )
{
- CN_ANCHOR_PTR new_anchor = item->AddAnchor( pos );
- m_anchors.push_back( new_anchor );
-
- for( int i = 0; i < PCB_LAYER_ID_COUNT; i++ )
- {
- if( ( item->Parent()->GetLayerSet() & LSET( 1, i ) ).any() )
- m_layer_anchors[i].push_back( new_anchor );
- }
- }
-
-private:
-
- void sort()
- {
- if( m_dirty )
- {
- std::sort( m_anchors.begin(), m_anchors.end() );
-
- for( auto i = 0; i < PCB_LAYER_ID_COUNT; i++ )
- {
- std::sort( m_layer_anchors[i].begin(), m_layer_anchors[i].end() );
- }
-
- m_dirty = false;
- }
+ m_index.Insert( item );
}
public:
CN_LIST()
{
m_dirty = false;
+ m_hasInvalid = false;
}
void Clear()
@@ -454,6 +444,7 @@ public:
delete item;
m_items.clear();
+ m_index.RemoveAll();
}
using ITER = decltype(m_items)::iterator;
@@ -463,13 +454,13 @@ public:
CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
- std::vector<CN_ANCHOR_PTR>& Anchors() { return m_anchors; }
-
template <class T>
- void FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, LSET aLayers = LSET::AllLayersMask(), bool aDirtyOnly = false );
+ void FindNearby( CN_ITEM *aItem, T aFunc );
- template <class T>
- void FindNearby( BOX2I aBBox, T aFunc, LSET aLayers = LSET::AllLayersMask(), bool aDirtyOnly = false );
+ void SetHasInvalid( bool aInvalid = true )
+ {
+ m_hasInvalid = aInvalid;
+ }
void SetDirty( bool aDirty = true )
{
@@ -481,12 +472,6 @@ public:
return m_dirty;
}
- void ClearConnections()
- {
- for( auto& anchor : m_anchors )
- anchor->Item()->ClearConnections();
- }
-
void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
void ClearDirtyFlags()
@@ -509,52 +494,35 @@ public:
{
return m_items.size();
}
-};
-
-class CN_PAD_LIST : public CN_LIST
-{
-public:
CN_ITEM* Add( D_PAD* pad )
{
auto item = new CN_ITEM( pad, false, 2 );
-
- addAnchor( pad->ShapePos(), item );
+ item->AddAnchor( pad->ShapePos() );
+ addItemtoTree( item );
m_items.push_back( item );
-
SetDirty();
return item;
}
-};
-
-class CN_TRACK_LIST : public CN_LIST
-{
-public:
CN_ITEM* Add( TRACK* track )
{
auto item = new CN_ITEM( track, true );
-
m_items.push_back( item );
-
- addAnchor( track->GetStart(), item );
- addAnchor( track->GetEnd(), item );
+ item->AddAnchor( track->GetStart() );
+ item->AddAnchor( track->GetEnd() );
+ addItemtoTree( item );
SetDirty();
-
return item;
}
-};
-
-class CN_VIA_LIST : public CN_LIST
-{
-public:
CN_ITEM* Add( VIA* via )
{
auto item = new CN_ITEM( via, true );
m_items.push_back( item );
- addAnchor( via->GetStart(), item );
+ item->AddAnchor( via->GetStart() );
+ addItemtoTree( item );
SetDirty();
return item;
}
@@ -624,9 +592,10 @@ public:
const auto& outline = zone->GetFilledPolysList().COutline( j );
for( int k = 0; k < outline.PointCount(); k++ )
- addAnchor( outline.CPoint( k ), zitem );
+ zitem->AddAnchor( outline.CPoint( k ) );
m_items.push_back( zitem );
+ addItemtoTree( zitem );
rv.push_back( zitem );
SetDirty();
}
@@ -640,39 +609,6 @@ public:
template <class T>
-void CN_LIST::FindNearby( BOX2I aBBox, T aFunc, LSET aLayers, bool aDirtyOnly )
-{
- sort();
-
- CN_ANCHORS *anchor_set = &m_anchors;
- PCB_LAYER_ID layer = aLayers.ExtractLayer();
-
- if( layer > 0 )
- anchor_set = &(m_layer_anchors[ layer ]);
-
- if( (*anchor_set).size() == 0 )
- return;
-
- CN_ANCHOR_PTR lower_ptr = std::make_shared<CN_ANCHOR>
- ( aBBox.GetPosition(), (*anchor_set)[0]->Item() );
-
- auto lower_it = std::lower_bound( anchor_set->begin(), anchor_set->end(), lower_ptr,
- []( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) -> bool
- { return a->Pos().x < b->Pos().x; } );
-
- for( auto it = lower_it; it != anchor_set->end(); it++)
- {
- if( (*it)->Pos().x > aBBox.GetRight() )
- break;
-
- if( (*it)->Valid() && ( !aDirtyOnly || (*it)->IsDirty() )
- && aBBox.Contains( (*it)->Pos() ) )
- aFunc( *it );
- }
-}
-
-
-template <class T>
void CN_ZONE_LIST::FindNearbyZones( BOX2I aBBox, T aFunc, bool aDirtyOnly )
{
for( auto item : m_items )
@@ -689,47 +625,12 @@ void CN_ZONE_LIST::FindNearbyZones( BOX2I aBBox, T aFunc, bool aDirtyOnly )
}
}
-
template <class T>
-void CN_LIST::FindNearby( VECTOR2I aPosition, int aDistMax, T aFunc, LSET aLayers, bool aDirtyOnly )
+void CN_LIST::FindNearby( CN_ITEM *aItem, T aFunc )
{
- /* Search items in m_Candidates that position is <= aDistMax from aPosition
- * (Rectilinear distance)
- * m_Candidates is sorted by X then Y values, so binary search is made for the first
- * element. Then a linear iteration is made to identify all element that are also
- * in the correct y range.
- */
-
- sort();
-
- CN_ANCHORS *anchor_set = &m_anchors;
- PCB_LAYER_ID layer = aLayers.ExtractLayer();
-
- if( layer > 0 )
- anchor_set = &(m_layer_anchors[ layer ]);
-
- if( (*anchor_set).size() == 0 )
- return;
-
- CN_ANCHOR_PTR lower = std::make_shared<CN_ANCHOR>
- ( aPosition - VECTOR2I( aDistMax, 0 ), (*anchor_set)[0]->Item() );
-
- auto lower_it = std::lower_bound( anchor_set->begin(), anchor_set->end(), lower,
- []( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b ) -> bool
- { return a->Pos().x < b->Pos().x; } );
-
- for( auto it = lower_it; it != anchor_set->end(); it++ )
- {
- if( (*it)->Pos().x > aDistMax + aPosition.x )
- break;
-
- if( (*it)->Valid() && std::abs( (*it)->Pos().y - aPosition.y ) < aDistMax
- && ( !aDirtyOnly || (*it)->IsDirty() ) )
- aFunc( *it );
- }
+ m_index.Query( aItem->BBox(), aFunc );
}
-
class CN_CONNECTIVITY_ALGO
{
public:
@@ -744,8 +645,6 @@ public:
private:
- bool m_lastSearchWithZones = false;
-
class ITEM_MAP_ENTRY
{
public:
@@ -776,10 +675,7 @@ public:
std::list<CN_ITEM*> m_items;
};
-
- CN_PAD_LIST m_padList;
- CN_TRACK_LIST m_trackList;
- CN_VIA_LIST m_viaList;
+ CN_LIST m_itemList;
CN_ZONE_LIST m_zoneList;
using ITEM_MAP_PAIR = std::pair <const BOARD_CONNECTED_ITEM*, ITEM_MAP_ENTRY>;
@@ -874,7 +770,7 @@ public:
const CLUSTERS& GetClusters();
int GetUnconnectedCount();
- CN_PAD_LIST& PadList() { return m_padList; }
+ CN_LIST& ItemList() { return m_itemList; }
void ForEachAnchor( const std::function<void( CN_ANCHOR& )>& aFunc );
void ForEachItem( const std::function<void( CN_ITEM& )>& aFunc );
@@ -886,4 +782,33 @@ public:
bool operator<( const CN_ANCHOR_PTR& a, const CN_ANCHOR_PTR& b );
+
+/**
+ * Struct CN_VISTOR
+ **/
+class CN_VISITOR {
+
+public:
+
+ CN_VISITOR( CN_ITEM* aItem, std::mutex* aListLock ) :
+ m_item( aItem ),
+ m_listLock( aListLock )
+ {}
+
+ bool operator()( CN_ITEM* aCandidate );
+
+protected:
+
+ void checkZoneItemConnection( CN_ZONE* aZone, CN_ITEM* aItem );
+
+ void checkZoneZoneConnection( CN_ZONE* aZoneA, CN_ZONE* aZoneB );
+
+ ///> the item we are looking for connections to
+ CN_ITEM* m_item;
+
+ ///> the mutex protecting our connection list
+ std::mutex* m_listLock;
+
+};
+
#endif
diff --git a/pcbnew/connectivity_data.cpp b/pcbnew/connectivity_data.cpp
index b5a4f7aa6..cae4645b7 100644
--- a/pcbnew/connectivity_data.cpp
+++ b/pcbnew/connectivity_data.cpp
@@ -475,9 +475,9 @@ unsigned int CONNECTIVITY_DATA::GetPadCount( int aNet ) const
{
int n = 0;
- for( auto pad : m_connAlgo->PadList() )
+ for( auto pad : m_connAlgo->ItemList() )
{
- if( !pad->Valid() )
+ if( !pad->Valid() || pad->Parent()->Type() != PCB_PAD_T)
continue;
auto dpad = static_cast<D_PAD*>( pad->Parent() );
diff --git a/pcbnew/connectivity_rtree.h b/pcbnew/connectivity_rtree.h
new file mode 100644
index 000000000..cdf8faab0
--- /dev/null
+++ b/pcbnew/connectivity_rtree.h
@@ -0,0 +1,108 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2018 KiCad Developers, see AUTHORS.txt for contributors.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#ifndef PCBNEW_CONNECTIVITY_RTREE_H_
+#define PCBNEW_CONNECTIVITY_RTREE_H_
+
+#include <math/box2.h>
+
+#include <geometry/rtree.h>
+
+
+/**
+ * Class CN_RTREE -
+ * Implements an R-tree for fast spatial indexing of connectivity items.
+ * Non-owning.
+ */
+template< class T >
+class CN_RTREE
+{
+public:
+
+ CN_RTREE()
+ {
+ this->m_tree = new RTree<T, int, 2, float>();
+ }
+
+ ~CN_RTREE()
+ {
+ delete this->m_tree;
+ }
+
+ /**
+ * Function Insert()
+ * Inserts an item into the tree. Item's bounding box is taken via its BBox() method.
+ */
+ void Insert( T aItem )
+ {
+ const BOX2I& bbox = aItem->BBox();
+ const int mmin[2] = { bbox.GetX(), bbox.GetY() };
+ const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
+
+ m_tree->Insert( mmin, mmax, aItem );
+ }
+
+ /**
+ * Function Remove()
+ * Removes an item from the tree. Removal is done by comparing pointers, attempting
+ * to remove a copy of the item will fail.
+ */
+ void Remove( T aItem )
+ {
+ const BOX2I& bbox = aItem->BBox();
+ const int mmin[2] = { bbox.GetX(), bbox.GetY() };
+ const int mmax[2] = { bbox.GetRight(), bbox.GetBottom() };
+
+ m_tree->Remove( mmin, mmax, aItem );
+ }
+
+ /**
+ * Function RemoveAll()
+ * Removes all items from the RTree
+ */
+ void RemoveAll( )
+ {
+ m_tree->RemoveAll();
+ }
+
+ /**
+ * Function Query()
+ * Executes a function object aVisitor for each item whose bounding box intersects
+ * with aBounds.
+ */
+ template <class Visitor>
+ void Query( const BOX2I& aBounds, Visitor& aVisitor )
+ {
+ const int mmin[2] = { aBounds.GetX(), aBounds.GetY() };
+ const int mmax[2] = { aBounds.GetRight(), aBounds.GetBottom() };
+
+ m_tree->Search( mmin, mmax, aVisitor );
+ }
+
+private:
+
+ RTree<T, int, 2, float>* m_tree;
+};
+
+
+#endif /* PCBNEW_CONNECTIVITY_RTREE_H_ */
--
2.11.0
References
-
[PATCH] Large board speed
From: Seth Hillbrand, 2018-05-25
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-05-25
-
Re: [PATCH] Large board speed
From: Tomasz Wlostowski, 2018-05-28
-
Re: [PATCH] Large board speed
From: Wayne Stambaugh, 2018-05-29
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-05-29
-
Re: [PATCH] Large board speed
From: Jeff Young, 2018-05-29
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-05-29
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-05-29
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-06-01
-
Re: [PATCH] Large board speed
From: Simon Richter, 2018-06-01
-
Re: [PATCH] Large board speed
From: Seth Hillbrand, 2018-06-01
-
Re: [PATCH] Large board speed
From: Tomasz Wlostowski, 2018-06-01
-
Re: [PATCH] Large board speed
From: Wayne Stambaugh, 2018-06-01
-
Re: [PATCH] Large board speed
From: Janis Skujenieks, 2018-06-01
-
Re: [PATCH] Large board speed
From: jp charras, 2018-06-02
-
Re: [PATCH] Large board speed
From: jp charras, 2018-06-02
-
Re: [PATCH] Large board speed
From: jp charras, 2018-06-02
