KiCad PCB EDA Suite
connectivity_data.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) 2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 #ifdef PROFILE
25 #include <profile.h>
26 #endif
27 
28 #include <connectivity_data.h>
29 #include <connectivity_algo.h>
30 #include <ratsnest_data.h>
31 
32 #ifdef USE_OPENMP
33 #include <omp.h>
34 #endif /* USE_OPENMP */
35 
37 {
38  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
39  m_progressReporter = nullptr;
40 }
41 
42 
44 {
45  Clear();
46 }
47 
48 
50 {
51  m_connAlgo->Add( aItem );
52  return true;
53 }
54 
55 
57 {
58  m_connAlgo->Remove( aItem );
59  return true;
60 }
61 
62 
64 {
65  m_connAlgo->Remove( aItem );
66  m_connAlgo->Add( aItem );
67  return true;
68 }
69 
70 
72 {
73  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
74  m_connAlgo->Build( aBoard );
76 }
77 
78 
79 void CONNECTIVITY_DATA::Build( const std::vector<BOARD_ITEM*>& aItems )
80 {
81  m_connAlgo.reset( new CN_CONNECTIVITY_ALGO );
82  m_connAlgo->Build( aItems );
83 
85 }
86 
87 
89 {
90  int lastNet = m_connAlgo->NetCount();
91 
92  #ifdef PROFILE
93  PROF_COUNTER rnUpdate( "update-ratsnest" );
94  #endif
95 
96  int nDirty = 0;
97 
98  int i;
99 
100  #ifdef USE_OPENMP
101  #pragma omp parallel shared(lastNet) private(i)
102  {
103  #pragma omp for schedule(guided, 1)
104  #else /* USE_OPENMP */
105  {
106  #endif
107 
108  // Start with net number 1, as 0 stands for not connected
109  for( i = 1; i < lastNet; ++i )
110  {
111  if( m_nets[i]->IsDirty() )
112  {
113  m_nets[i]->Update();
114  nDirty++;
115  }
116  }
117  } /* end of parallel section */
118 
119  #ifdef PROFILE
120  rnUpdate.Show();
121  #endif /* PROFILE */
122 }
123 
124 
125 void CONNECTIVITY_DATA::addRatsnestCluster( const std::shared_ptr<CN_CLUSTER>& aCluster )
126 {
127  auto rnNet = m_nets[ aCluster->OriginNet() ];
128 
129  rnNet->AddCluster( aCluster );
130 }
131 
132 
134 {
135  m_connAlgo->PropagateNets();
136 
137  int lastNet = m_connAlgo->NetCount();
138 
139  if( lastNet >= (int) m_nets.size() )
140  {
141  unsigned int prevSize = m_nets.size();
142  m_nets.resize( lastNet + 1 );
143 
144  for( unsigned int i = prevSize; i < m_nets.size(); i++ )
145  m_nets[i] = new RN_NET;
146  }
147 
148  auto clusters = m_connAlgo->GetClusters();
149 
150  int dirtyNets = 0;
151 
152  for( int net = 0; net < lastNet; net++ )
153  {
154  if( m_connAlgo->IsNetDirty( net ) )
155  {
156  m_nets[net]->Clear();
157  dirtyNets++;
158  }
159  }
160 
161  for( auto c : clusters )
162  {
163  int net = c->OriginNet();
164 
165  if( m_connAlgo->IsNetDirty( net ) )
166  {
167  addRatsnestCluster( c );
168  }
169  }
170 
171  m_connAlgo->ClearDirtyFlags();
172 
173  updateRatsnest();
174 }
175 
176 
177 void CONNECTIVITY_DATA::BlockRatsnestItems( const std::vector<BOARD_ITEM*>& aItems )
178 {
179  std::vector<BOARD_CONNECTED_ITEM*> citems;
180 
181  for( auto item : aItems )
182  {
183  if( item->Type() == PCB_MODULE_T )
184  {
185  for( auto pad : static_cast<MODULE*>(item)->Pads() )
186  citems.push_back( pad );
187  }
188  else
189  {
190  citems.push_back( static_cast<BOARD_CONNECTED_ITEM*>(item) );
191  }
192  }
193 
194  for( auto item : citems )
195  {
196  if ( m_connAlgo->ItemExists( item ) )
197  {
198  auto& entry = m_connAlgo->ItemEntry( item );
199 
200  for( auto cnItem : entry.GetItems() )
201  {
202  for( auto anchor : cnItem->Anchors() )
203  anchor->SetNoLine( true );
204  }
205  }
206  }
207 }
208 
209 
211 {
212  return m_connAlgo->NetCount();
213 }
214 
215 
217  std::vector<int>& aIslands )
218 {
219  m_connAlgo->FindIsolatedCopperIslands( aZone, aIslands );
220 }
221 
222 void CONNECTIVITY_DATA::FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones )
223 {
224  m_connAlgo->FindIsolatedCopperIslands( aZones );
225 }
226 
227 int CONNECTIVITY_DATA::countRelevantItems( const std::vector<BOARD_ITEM*>& aItems )
228 {
229  int n = 0;
230 
231  for( const auto item : aItems )
232  {
233  switch( item->Type() )
234  {
235  case PCB_TRACE_T:
236  case PCB_PAD_T:
237  case PCB_ZONE_AREA_T:
238  case PCB_MODULE_T:
239  case PCB_VIA_T:
240  n++;
241  break;
242 
243  default:
244  break;
245  }
246  }
247 
248  return n;
249 }
250 
251 
252 void CONNECTIVITY_DATA::ComputeDynamicRatsnest( const std::vector<BOARD_ITEM*>& aItems )
253 {
254  if( countRelevantItems( aItems ) == 0 )
255  {
256  m_dynamicRatsnest.clear();
257  return ;
258  }
259 
261  m_dynamicConnectivity->Build( aItems );
262 
263  m_dynamicRatsnest.clear();
264 
265  BlockRatsnestItems( aItems );
266 
267  for( unsigned int nc = 1; nc < m_dynamicConnectivity->m_nets.size(); nc++ )
268  {
269  auto dynNet = m_dynamicConnectivity->m_nets[nc];
270 
271  if( dynNet->GetNodeCount() != 0 )
272  {
273  auto ourNet = m_nets[nc];
274  CN_ANCHOR_PTR nodeA, nodeB;
275 
276  if( ourNet->NearestBicoloredPair( *dynNet, nodeA, nodeB ) )
277  {
278  RN_DYNAMIC_LINE l;
279  l.a = nodeA->Pos();
280  l.b = nodeB->Pos();
281  l.netCode = nc;
282 
283  m_dynamicRatsnest.push_back( l );
284  }
285  }
286  }
287 
288  for( auto net : m_dynamicConnectivity->m_nets )
289  {
290  if( !net )
291  continue;
292 
293  const auto& edges = net->GetUnconnected();
294 
295  if( edges.empty() )
296  continue;
297 
298  for( const auto& edge : edges )
299  {
300  const auto& nodeA = edge.GetSourceNode();
301  const auto& nodeB = edge.GetTargetNode();
302  RN_DYNAMIC_LINE l;
303 
304  l.a = nodeA->Pos();
305  l.b = nodeB->Pos();
306  l.netCode = 0;
307  m_dynamicRatsnest.push_back( l );
308  }
309  }
310 }
311 
312 
314 {
315  m_connAlgo->ForEachAnchor( [] ( CN_ANCHOR& anchor ) { anchor.SetNoLine( false ); } );
317 }
318 
319 
321 {
322  m_dynamicConnectivity.reset();
323  m_dynamicRatsnest.clear();
324 }
325 
326 
328 {
329  m_connAlgo->PropagateNets();
330 }
331 
332 
334 {
335  unsigned int unconnected = 0;
336 
337  for( auto net : m_nets )
338  {
339  if( !net )
340  continue;
341 
342  const auto& edges = net->GetUnconnected();
343 
344  if( edges.empty() )
345  continue;
346 
347  unconnected += edges.size();
348  }
349 
350  return unconnected;
351 }
352 
353 
355 {
356  for( auto net : m_nets )
357  delete net;
358 
359  m_nets.clear();
360 }
361 
362 
363 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetConnectedItems(
364  const BOARD_CONNECTED_ITEM* aItem,
365  const KICAD_T aTypes[] ) const
366 {
367  std::vector<BOARD_CONNECTED_ITEM*> rv;
368  const auto clusters = m_connAlgo->SearchClusters( CN_CONNECTIVITY_ALGO::CSM_CONNECTIVITY_CHECK,
369  aTypes, aItem->GetNetCode() );
370 
371  for( auto cl : clusters )
372  {
373  if( cl->Contains( aItem ) )
374  {
375  for( const auto item : *cl )
376  {
377  if( item->Valid() )
378  rv.push_back( item->Parent() );
379  }
380  }
381  }
382 
383  return rv;
384 }
385 
386 
387 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetNetItems( int aNetCode,
388  const KICAD_T aTypes[] ) const
389 {
390  std::set<BOARD_CONNECTED_ITEM*> items;
391  std::vector<BOARD_CONNECTED_ITEM*> rv;
392 
393  m_connAlgo->ForEachItem( [&items, aNetCode, &aTypes] ( CN_ITEM& aItem )
394  {
395  if( aItem.Valid() && ( aItem.Net() == aNetCode ) )
396  {
397  KICAD_T itemType = aItem.Parent()->Type();
398 
399  for( int i = 0; aTypes[i] > 0; ++i )
400  {
401  wxASSERT( aTypes[i] < MAX_STRUCT_TYPE_ID );
402 
403  if( itemType == aTypes[i] )
404  {
405  items.insert( aItem.Parent() );
406  break;
407  }
408  }
409  }
410  } );
411 
412  std::copy( items.begin(), items.end(), std::back_inserter( rv ) );
413 
414  return rv;
415 }
416 
417 
418 bool CONNECTIVITY_DATA::CheckConnectivity( std::vector<CN_DISJOINT_NET_ENTRY>& aReport )
419 {
421 
422  for( auto net : m_nets )
423  {
424  if( net )
425  {
426  for( const auto& edge : net->GetEdges() )
427  {
429  ent.net = edge.GetSourceNode()->Parent()->GetNetCode();
430  ent.a = edge.GetSourceNode()->Parent();
431  ent.b = edge.GetTargetNode()->Parent();
432  ent.anchorA = edge.GetSourceNode()->Pos();
433  ent.anchorB = edge.GetTargetNode()->Pos();
434  aReport.push_back( ent );
435  }
436  }
437  }
438 
439  return aReport.empty();
440 }
441 
442 
443 const std::vector<TRACK*> CONNECTIVITY_DATA::GetConnectedTracks( const BOARD_CONNECTED_ITEM* aItem )
444 const
445 {
446  auto& entry = m_connAlgo->ItemEntry( aItem );
447 
448  std::set<TRACK*> tracks;
449  std::vector<TRACK*> rv;
450 
451  for( auto citem : entry.GetItems() )
452  {
453  for( auto connected : citem->ConnectedItems() )
454  {
455  if( connected->Valid() && ( connected->Parent()->Type() == PCB_TRACE_T || connected->Parent()->Type() == PCB_VIA_T ) )
456  tracks.insert( static_cast<TRACK*> ( connected->Parent() ) );
457  }
458  }
459 
460  std::copy( tracks.begin(), tracks.end(), std::back_inserter( rv ) );
461  return rv;
462 }
463 
464 
465 const std::vector<D_PAD*> CONNECTIVITY_DATA::GetConnectedPads( const BOARD_CONNECTED_ITEM* aItem )
466 const
467 {
468  auto& entry = m_connAlgo->ItemEntry( aItem );
469 
470  std::set<D_PAD*> pads;
471  std::vector<D_PAD*> rv;
472 
473  for( auto citem : entry.GetItems() )
474  {
475  for( auto connected : citem->ConnectedItems() )
476  {
477  if( connected->Valid() && connected->Parent()->Type() == PCB_PAD_T )
478  pads.insert( static_cast<D_PAD*> ( connected->Parent() ) );
479  }
480  }
481 
482  std::copy( pads.begin(), pads.end(), std::back_inserter( rv ) );
483  return rv;
484 }
485 
486 
487 unsigned int CONNECTIVITY_DATA::GetNodeCount( int aNet ) const
488 {
489  int sum = 0;
490 
491  if( aNet < 0 ) // Node count for all nets
492  {
493  for( const auto& net : m_nets )
494  sum += net->GetNodeCount();
495  }
496  else if( aNet < (int) m_nets.size() )
497  {
498  sum = m_nets[aNet]->GetNodeCount();
499  }
500 
501  return sum;
502 }
503 
504 
505 unsigned int CONNECTIVITY_DATA::GetPadCount( int aNet ) const
506 {
507  int n = 0;
508 
509  for( auto pad : m_connAlgo->ItemList() )
510  {
511  if( !pad->Valid() || pad->Parent()->Type() != PCB_PAD_T)
512  continue;
513 
514  auto dpad = static_cast<D_PAD*>( pad->Parent() );
515 
516  if( aNet < 0 || aNet == dpad->GetNetCode() )
517  {
518  n++;
519  }
520  }
521 
522  return n;
523 }
524 
525 
527  const BOARD_CONNECTED_ITEM* aRef,
528  const VECTOR2I& aPos,
529  int aNet )
530 {
531  CN_CLUSTER_PTR refCluster;
532  int refNet = -1;
533 
534  if( aRef )
535  refNet = aRef->GetNetCode();
536 
537  if( aNet >= 0 )
538  refNet = aNet;
539 
540  if( aRef )
541  {
542  for( auto cl : m_connAlgo->GetClusters() )
543  {
544  if( cl->Contains( aRef ) )
545  {
546  refCluster = cl;
547  break;
548  }
549  }
550  }
551 
552  std::set <VECTOR2I> anchors;
553 
554  for( auto cl : m_connAlgo->GetClusters() )
555  {
556  if( cl != refCluster )
557  {
558  for( auto item : *cl )
559  {
560  if( item->Valid() && item->Parent()->GetNetCode() == refNet
561  && item->Parent()->Type() != PCB_ZONE_AREA_T )
562  {
563  for( auto anchor : item->Anchors() )
564  {
565  anchors.insert( anchor->Pos() );
566  }
567  }
568  }
569  }
570  }
571 
572 
573  std::vector<VECTOR2I> rv;
574 
575  std::copy( anchors.begin(), anchors.end(), std::back_inserter( rv ) );
576  std::sort( rv.begin(), rv.end(), [aPos] ( const VECTOR2I& a, const VECTOR2I& b )
577  {
578  auto da = (a - aPos).EuclideanNorm();
579  auto db = (b - aPos).EuclideanNorm();
580 
581  return da < db;
582  } );
583 
584  return rv;
585 }
586 
587 
588 void CONNECTIVITY_DATA::GetUnconnectedEdges( std::vector<CN_EDGE>& aEdges) const
589 {
590  for( auto rnNet : m_nets )
591  {
592  if( rnNet )
593  {
594  for( auto edge : rnNet->GetEdges() )
595  {
596  aEdges.push_back( edge );
597  }
598  }
599  }
600 }
601 
602 
603 const std::vector<BOARD_CONNECTED_ITEM*> CONNECTIVITY_DATA::GetConnectedItems(
604  const BOARD_CONNECTED_ITEM* aItem, const VECTOR2I& aAnchor, KICAD_T aTypes[] )
605 {
606  auto& entry = m_connAlgo->ItemEntry( aItem );
607  std::vector<BOARD_CONNECTED_ITEM* > rv;
608 
609  for( auto cnItem : entry.GetItems() )
610  {
611  for( auto anchor : cnItem->Anchors() )
612  {
613  if( anchor->Pos() == aAnchor )
614  {
615  for( int i = 0; aTypes[i] > 0; i++ )
616  {
617  if( cnItem->Valid() && cnItem->Parent()->Type() == aTypes[i] )
618  {
619  rv.push_back( cnItem->Parent() );
620  break;
621  }
622  }
623  }
624  }
625  }
626 
627  return rv;
628 }
629 
630 
632 {
633  if ( aNet < 0 || aNet >= (int) m_nets.size() )
634  {
635  return nullptr;
636  }
637 
638  return m_nets[ aNet ];
639 }
640 
641 
643 {
644  if (aItem->Type() == PCB_MODULE_T)
645  {
646  for ( auto pad : static_cast<MODULE*>( aItem )->Pads() )
647  {
648  m_connAlgo->MarkNetAsDirty( pad->GetNetCode() );
649  }
650  }
651  if (aItem->IsConnected() )
652  {
653  m_connAlgo->MarkNetAsDirty( static_cast<BOARD_CONNECTED_ITEM*>( aItem )->GetNetCode() );
654  }
655 }
656 
658 {
659  m_progressReporter = aReporter;
660  m_connAlgo->SetProgressReporter( m_progressReporter );
661 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
KICAD_T Type() const
Function Type()
Definition: base_struct.h:209
void Clear()
Function Clear() Erases the connectivity database.
Class ZONE_CONTAINER handles a list of polygons defining a copper zone.
Definition: class_zone.h:60
const std::vector< D_PAD * > GetConnectedPads(const BOARD_CONNECTED_ITEM *aItem) const
Class BOARD_ITEM is a base class for any item which can be embedded within the BOARD container class...
A progress reporter for use in multi-threaded environments.
std::shared_ptr< CN_CONNECTIVITY_ALGO > m_connAlgo
Class that computes missing connections on a PCB.
PROGRESS_REPORTER * m_progressReporter
class ZONE_CONTAINER, a zone area
Definition: typeinfo.h:102
bool Update(BOARD_ITEM *aItem)
Function Update() Updates the connectivity data for an item.
const std::vector< BOARD_CONNECTED_ITEM * > GetConnectedItems(const BOARD_CONNECTED_ITEM *aItem, const VECTOR2I &aAnchor, KICAD_T aTypes[])
void ComputeDynamicRatsnest(const std::vector< BOARD_ITEM * > &aItems)
Function ComputeDynamicRatsnest() Calculates the temporary dynamic ratsnest (i.e. ...
unsigned int GetNodeCount(int aNet=-1) const
class D_PAD, a pad in a footprint
Definition: typeinfo.h:90
void Show()
Print the elapsed time (in ms) to STDERR.
Definition: profile.h:93
void RecalculateRatsnest()
Function RecalculateRatsnest() Updates the ratsnest for the board.
void FindIsolatedCopperIslands(ZONE_CONTAINER *aZone, std::vector< int > &aIslands)
Function FindIsolatedCopperIslands() Searches for copper islands in zone aZone that are not connected...
The class PROF_COUNTER is a small class to help profiling.
Definition: profile.h:45
const std::vector< TRACK * > GetConnectedTracks(const BOARD_CONNECTED_ITEM *aItem) const
BOARD_CONNECTED_ITEM * b
Class BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected an...
std::vector< RN_DYNAMIC_LINE > m_dynamicRatsnest
VECTOR2I anchorB
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:95
class MODULE, a footprint
Definition: typeinfo.h:89
VECTOR2I anchorA
bool Valid() const
const std::vector< VECTOR2I > NearestUnconnectedTargets(const BOARD_CONNECTED_ITEM *aRef, const VECTOR2I &aPos, int aMaxCount=-1)
void PropagateNets()
Function PropagateNets() Propagates the net codes from the source pads to the tracks/vias.
std::shared_ptr< CN_CLUSTER > CN_CLUSTER_PTR
unsigned int GetUnconnectedCount() const
Function GetUnconnectedCount() Returns the number of remaining edges in the ratsnest.
int GetNetCount() const
Function GetNetCount() Returns the total number of nets in the connectivity database.
int Net() const
void ClearDynamicRatsnest()
Function ClearDynamicRatsnest() Erases the temporary dynamic ratsnest (i.e.
void SetProgressReporter(PROGRESS_REPORTER *aReporter)
bool Remove(BOARD_ITEM *aItem)
Function Remove() Removes an item from the connectivity data.
int countRelevantItems(const std::vector< BOARD_ITEM * > &aItems)
void MarkItemNetAsDirty(BOARD_ITEM *aItem)
std::unique_ptr< CONNECTIVITY_DATA > m_dynamicConnectivity
std::vector< RN_NET * > m_nets
bool Add(BOARD_ITEM *aItem)
Function Add() Adds an item to the connectivity data.
int GetNetCode() const
Function GetNetCode.
void BlockRatsnestItems(const std::vector< BOARD_ITEM * > &aItems)
RN_NET * GetRatsnestForNet(int aNet)
Function GetRatsnestForNet() Returns the ratsnest, expressed as a set of graph edges for a given net...
BOARD_CONNECTED_ITEM * a
BOARD_CONNECTED_ITEM * Parent() const
bool CheckConnectivity(std::vector< CN_DISJOINT_NET_ENTRY > &aReport)
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:169
virtual bool IsConnected() const
Function IsConnected() Returns information if the object is derived from BOARD_CONNECTED_ITEM.
size_t i
Definition: json11.cpp:597
int net
void GetUnconnectedEdges(std::vector< CN_EDGE > &aEdges) const
void SetNoLine(bool aEnable)
Decides whether this node can be a ratsnest line target.
unsigned int GetPadCount(int aNet=-1) const
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:96
Class RN_NET Describes ratsnest for a single net.
Definition: ratsnest_data.h:59
std::shared_ptr< CN_ANCHOR > CN_ANCHOR_PTR
void Build(BOARD *aBoard)
Function Build() Builds the connectivity database for the board aBoard.
void HideDynamicRatsnest()
Hides the temporary dynamic ratsnest lines.
void addRatsnestCluster(const std::shared_ptr< CN_CLUSTER > &aCluster)
const std::vector< BOARD_CONNECTED_ITEM * > GetNetItems(int aNetCode, const KICAD_T aTypes[]) const
Function GetNetItems() Returns the list of items that belong to a certain net.