1 /* 2 * This program source code file is part of KICAD, a free EDA CAD application. 3 * 4 * Copyright (C) 2013-2017 CERN 5 * Copyright (C) 2019-2021 KiCad Developers, see AUTHORS.txt for contributors. 6 * 7 * @author Maciej Suminski <maciej.suminski@cern.ch> 8 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> 9 * 10 * This program is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU General Public License 12 * as published by the Free Software Foundation; either version 2 13 * of the License, or (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, you may find one here: 22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html 23 * or you may search the http://www.gnu.org website for the version 2 license, 24 * or you may write to the Free Software Foundation, Inc., 25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 26 */ 27 28 // #define CONNECTIVITY_DEBUG 29 30 #ifndef __CONNECTIVITY_ALGO_H 31 #define __CONNECTIVITY_ALGO_H 32 33 #include <board.h> 34 #include <pad.h> 35 #include <footprint.h> 36 #include <zone.h> 37 38 #include <geometry/shape_poly_set.h> 39 #include <geometry/poly_grid_partition.h> 40 41 #include <memory> 42 #include <algorithm> 43 #include <functional> 44 #include <vector> 45 #include <deque> 46 #include <intrusive_list.h> 47 48 #include <connectivity/connectivity_rtree.h> 49 #include <connectivity/connectivity_data.h> 50 #include <connectivity/connectivity_items.h> 51 52 class CN_CONNECTIVITY_ALGO_IMPL; 53 class CN_RATSNEST_NODES; 54 class BOARD; 55 class BOARD_CONNECTED_ITEM; 56 class BOARD_ITEM; 57 class ZONE; 58 class PROGRESS_REPORTER; 59 60 61 /** 62 * CN_EDGE represents a point-to-point connection, whether realized or unrealized (ie: tracks etc. 63 * or a ratsnest line). 64 */ 65 class CN_EDGE 66 { 67 public: CN_EDGE()68 CN_EDGE() 69 : m_weight( 0 ), m_visible( true ) 70 {} 71 72 CN_EDGE( CN_ANCHOR_PTR aSource, CN_ANCHOR_PTR aTarget, unsigned aWeight = 0 ) m_source(aSource)73 : m_source( aSource ), m_target( aTarget ), m_weight( aWeight ), m_visible( true ) 74 {} 75 76 /** 77 * This sort operator provides a sort-by-weight for the ratsnest operation. 78 * 79 * @param aOther the other edge to compare. 80 * @return true if our weight is smaller than the other weight. 81 */ 82 bool operator<( CN_EDGE aOther ) const 83 { 84 return m_weight < aOther.m_weight; 85 } 86 GetSourceNode()87 CN_ANCHOR_PTR GetSourceNode() const { return m_source; } GetTargetNode()88 CN_ANCHOR_PTR GetTargetNode() const { return m_target; } GetWeight()89 unsigned GetWeight() const { return m_weight; } 90 SetSourceNode(const CN_ANCHOR_PTR & aNode)91 void SetSourceNode( const CN_ANCHOR_PTR& aNode ) { m_source = aNode; } SetTargetNode(const CN_ANCHOR_PTR & aNode)92 void SetTargetNode( const CN_ANCHOR_PTR& aNode ) { m_target = aNode; } SetWeight(unsigned weight)93 void SetWeight( unsigned weight ) { m_weight = weight; } 94 SetVisible(bool aVisible)95 void SetVisible( bool aVisible ) 96 { 97 m_visible = aVisible; 98 } 99 IsVisible()100 bool IsVisible() const 101 { 102 return m_visible; 103 } 104 GetSourcePos()105 const VECTOR2I GetSourcePos() const 106 { 107 return m_source->Pos(); 108 } 109 GetTargetPos()110 const VECTOR2I GetTargetPos() const 111 { 112 return m_target->Pos(); 113 } 114 115 private: 116 CN_ANCHOR_PTR m_source; 117 CN_ANCHOR_PTR m_target; 118 unsigned m_weight; 119 bool m_visible; 120 }; 121 122 123 class CN_CONNECTIVITY_ALGO 124 { 125 public: 126 enum CLUSTER_SEARCH_MODE 127 { 128 CSM_PROPAGATE, 129 CSM_CONNECTIVITY_CHECK, 130 CSM_RATSNEST 131 }; 132 133 using CLUSTERS = std::vector<CN_CLUSTER_PTR>; 134 135 class ITEM_MAP_ENTRY 136 { 137 public: 138 ITEM_MAP_ENTRY( CN_ITEM* aItem = nullptr ) 139 { 140 if( aItem ) 141 m_items.push_back( aItem ); 142 } 143 MarkItemsAsInvalid()144 void MarkItemsAsInvalid() 145 { 146 for( auto item : m_items ) 147 { 148 item->SetValid( false ); 149 } 150 } 151 Link(CN_ITEM * aItem)152 void Link( CN_ITEM* aItem ) 153 { 154 m_items.push_back( aItem ); 155 } 156 GetItems()157 const std::list<CN_ITEM*> GetItems() const 158 { 159 return m_items; 160 } 161 162 std::list<CN_ITEM*> m_items; 163 }; 164 CN_CONNECTIVITY_ALGO()165 CN_CONNECTIVITY_ALGO() {} ~CN_CONNECTIVITY_ALGO()166 ~CN_CONNECTIVITY_ALGO() { Clear(); } 167 ItemExists(const BOARD_CONNECTED_ITEM * aItem)168 bool ItemExists( const BOARD_CONNECTED_ITEM* aItem ) const 169 { 170 return m_itemMap.find( aItem ) != m_itemMap.end(); 171 } 172 ItemEntry(const BOARD_CONNECTED_ITEM * aItem)173 ITEM_MAP_ENTRY& ItemEntry( const BOARD_CONNECTED_ITEM* aItem ) 174 { 175 return m_itemMap[ aItem ]; 176 } 177 IsNetDirty(int aNet)178 bool IsNetDirty( int aNet ) const 179 { 180 if( aNet < 0 ) 181 return false; 182 183 return m_dirtyNets[ aNet ]; 184 } 185 ClearDirtyFlags()186 void ClearDirtyFlags() 187 { 188 for( auto i = m_dirtyNets.begin(); i != m_dirtyNets.end(); ++i ) 189 *i = false; 190 } 191 GetDirtyClusters(CLUSTERS & aClusters)192 void GetDirtyClusters( CLUSTERS& aClusters ) const 193 { 194 for( const auto& cl : m_ratsnestClusters ) 195 { 196 int net = cl->OriginNet(); 197 198 if( net >= 0 && m_dirtyNets[net] ) 199 aClusters.push_back( cl ); 200 } 201 } 202 NetCount()203 int NetCount() const 204 { 205 return m_dirtyNets.size(); 206 } 207 208 void Build( BOARD* aBoard, PROGRESS_REPORTER* aReporter = nullptr ); 209 void Build( const std::vector<BOARD_ITEM*>& aItems ); 210 211 void Clear(); 212 213 bool Remove( BOARD_ITEM* aItem ); 214 bool Add( BOARD_ITEM* aItem ); 215 216 const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode, const KICAD_T aTypes[], 217 int aSingleNet ); 218 const CLUSTERS SearchClusters( CLUSTER_SEARCH_MODE aMode ); 219 220 /** 221 * Propagate nets from pads to other items in clusters. 222 * @param aCommit is used to store undo information for items modified by the call. 223 * @param aMode controls how clusters with conflicting nets are resolved. 224 */ 225 void PropagateNets( BOARD_COMMIT* aCommit = nullptr, 226 PROPAGATE_MODE aMode = PROPAGATE_MODE::SKIP_CONFLICTS ); 227 228 void FindIsolatedCopperIslands( ZONE* aZone, PCB_LAYER_ID aLayer, std::vector<int>& aIslands ); 229 230 /** 231 * Find the copper islands that are not connected to a net. 232 * 233 * These are added to the m_islands vector. 234 * N.B. This must be called after aZones has been refreshed. 235 * 236 * @param: aZones is the set of zones to search for islands. 237 */ 238 void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones ); 239 240 const CLUSTERS& GetClusters(); 241 ItemList()242 const CN_LIST& ItemList() const 243 { 244 return m_itemList; 245 } 246 247 template <typename Func> ForEachAnchor(Func && aFunc)248 void ForEachAnchor( Func&& aFunc ) const 249 { 250 for( auto&& item : m_itemList ) 251 { 252 for( auto&& anchor : item->Anchors() ) 253 aFunc( *anchor ); 254 } 255 } 256 257 template <typename Func> ForEachItem(Func && aFunc)258 void ForEachItem( Func&& aFunc ) const 259 { 260 for( auto&& item : m_itemList ) 261 aFunc( *item ); 262 } 263 264 void MarkNetAsDirty( int aNet ); 265 void SetProgressReporter( PROGRESS_REPORTER* aReporter ); 266 267 private: 268 void searchConnections(); 269 270 void propagateConnections( BOARD_COMMIT* aCommit = nullptr, 271 PROPAGATE_MODE aMode = PROPAGATE_MODE::SKIP_CONFLICTS ); 272 273 template <class Container, class BItem> add(Container & c,BItem brditem)274 void add( Container& c, BItem brditem ) 275 { 276 auto item = c.Add( brditem ); 277 278 m_itemMap[ brditem ] = ITEM_MAP_ENTRY( item ); 279 } 280 281 void markItemNetAsDirty( const BOARD_ITEM* aItem ); 282 283 private: 284 CN_LIST m_itemList; 285 std::unordered_map<const BOARD_ITEM*, ITEM_MAP_ENTRY> m_itemMap; 286 287 CLUSTERS m_connClusters; 288 CLUSTERS m_ratsnestClusters; 289 std::vector<bool> m_dirtyNets; 290 291 PROGRESS_REPORTER* m_progressReporter = nullptr; 292 }; 293 294 295 class CN_VISITOR 296 { 297 public: CN_VISITOR(CN_ITEM * aItem)298 CN_VISITOR( CN_ITEM* aItem ) : 299 m_item( aItem ) 300 {} 301 302 bool operator()( CN_ITEM* aCandidate ); 303 304 protected: 305 void checkZoneItemConnection( CN_ZONE_LAYER* aZoneLayer, CN_ITEM* aItem ); 306 307 void checkZoneZoneConnection( CN_ZONE_LAYER* aZoneLayerA, CN_ZONE_LAYER* aZoneLayerB ); 308 309 protected: 310 CN_ITEM* m_item; ///< The item we are looking for connections to. 311 }; 312 313 #endif 314