KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_item.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include "pns_node.h"
23#include "pns_item.h"
24#include "pns_line.h"
25#include "pns_router.h"
26
29
31
32namespace PNS {
33
34static void dumpObstacles( const PNS::NODE::OBSTACLES &obstacles )
35{
36 printf( "&&&& %zu obstacles: \n", obstacles.size() );
37
38 for( const auto& obs : obstacles )
39 {
40 printf( "%p [%s] - %p [%s], clearance %d\n",
41 obs.m_head, obs.m_head->KindStr().c_str(),
42 obs.m_item, obs.m_item->KindStr().c_str(),
43 obs.m_clearance );
44 }
45}
46
47
48// prune self-collisions, i.e. a via/pad annular ring with its own hole
49static bool shouldWeConsiderHoleCollisions( const ITEM* aItem, const ITEM* aHead )
50{
51 const HOLE* holeI = aItem->OfKind( ITEM::HOLE_T ) ? static_cast<const HOLE*>( aItem ) : nullptr;
52 const HOLE* holeH = aHead->OfKind( ITEM::HOLE_T ) ? static_cast<const HOLE*>( aHead ) : nullptr;
53
54 if( holeI && holeH ) // hole-to-hole case
55 {
56 const ITEM* parentI = holeI->ParentPadVia();
57 const ITEM* parentH = holeH->ParentPadVia();
58 if( !parentH || !parentI )
59 return true;
60
61 const VIA* parentViaI = dyn_cast<const VIA*>( parentI );
62 const VIA* parentViaH = dyn_cast<const VIA*>( parentH );
63
64 // Note to self: the if() below is an ugly heuristic to determine if we aren't trying
65 // to check for collisions of the hole of the via with another (although identical)
66 // copy of it. Such case occurs when checking a LINE against a NODE where this LINE
67 // has been already added. LINE has no notion of ownership of it's via (it's just a
68 // copy) and before hole-to-hole clearance support has been introduced it didn't matter
69 // becasue we didn't consider collisions of the objects belonging to the same net anyway
70 // Now that hole clearance check doesn't care about the nets assigned to the parent
71 // vias/solids, I'll probably have to refactor the LINE class to manage ownership of
72 // its (optional) VIA. For the moment, we just treat via holes that are geometrically
73 // identical and belonging to the same net as non-colliding.
74
75 if( parentViaI && parentViaH && parentViaI->Pos() == parentViaH->Pos()
76 && parentViaI->Diameter() == parentViaH->Diameter()
77 && parentViaI->Net() == parentViaH->Net()
78 && parentViaI->Drill() == parentViaH->Drill() )
79 return false;
80
81 return parentI != parentH;
82 }
83
84 if( holeI )
85 return holeI->ParentPadVia() != aHead;
86 else if( holeH )
87 return holeH->ParentPadVia() != aItem;
88 else
89 return true;
90}
91
92
93bool ITEM::collideSimple( const ITEM* aHead, const NODE* aNode,
94 COLLISION_SEARCH_CONTEXT* aCtx ) const
95{
96 // Note: if 'this' is a pad or a via then its hole is a separate PNS::ITEM in the node's
97 // index and we don't need to deal with holeI here. The same is *not* true of the routing
98 // "head", so we do need to handle holeH.
99
100 const SHAPE* shapeI = Shape();
101 int lineWidthI = 0;
102
103 const SHAPE* shapeH = aHead->Shape();
104 const HOLE* holeH = aHead->Hole();
105 int lineWidthH = 0;
106 bool collisionsFound = false;
107
108 if( this == aHead ) // we cannot be self-colliding
109 return false;
110
111 if ( !shouldWeConsiderHoleCollisions( this, aHead ) )
112 return false;
113
114 // Special cases for "head" lines with vias attached at the end. Note that this does not
115 // support head-line-via to head-line-via collisions, but you can't route two independent
116 // tracks at once so it shouldn't come up.
117
118 if( const auto line = dyn_cast<const LINE*>( this ) )
119 {
120 if( line->EndsWithVia() )
121 collisionsFound |= line->Via().collideSimple( aHead, aNode, aCtx );
122 }
123
124 if( const auto line = dyn_cast<const LINE*>( aHead ) )
125 {
126 if( line->EndsWithVia() )
127 collisionsFound |= line->Via().collideSimple( this, aNode, aCtx );
128 }
129
130 // And a special case for the "head" via's hole.
131 if( holeH && shouldWeConsiderHoleCollisions( this, holeH ) )
132 {
133 if( collideSimple( holeH, aNode, aCtx ) )
134 collisionsFound = true;
135 }
136
137 // Sadly collision routines ignore SHAPE_POLY_LINE widths so we have to pass them in as part
138 // of the clearance value.
139 if( m_kind == LINE_T )
140 lineWidthI = static_cast<const LINE*>( this )->Width() / 2;
141
142 if( aHead->m_kind == LINE_T )
143 lineWidthH = static_cast<const LINE*>( aHead )->Width() / 2;
144
145 // check if we are not on completely different layers first
146 if( !m_layers.Overlaps( aHead->m_layers ) )
147 return false;
148
149 // fixme: this f***ing singleton must go...
150 ROUTER* router = ROUTER::GetInstance();
151 ROUTER_IFACE* iface = router ? router->GetInterface() : nullptr;
152 bool differentNetsOnly = true;
153 bool enforce = false;
154 int clearance;
155
156 if( aCtx )
157 differentNetsOnly = aCtx->options.m_differentNetsOnly;
158
159 // Hole-to-hole collisions don't have anything to do with nets
160 if( Kind() == HOLE_T && aHead->Kind() == HOLE_T )
161 differentNetsOnly = false;
162
163 if( differentNetsOnly && Net() == aHead->Net() && aHead->Net() )
164 {
165 // same nets? no clearance!
166 clearance = -1;
167 }
168 else if( differentNetsOnly && ( IsFreePad() || aHead->IsFreePad() ) )
169 {
170 // a pad associated with a "free" pin (NIC) doesn't have a net until it has been used
171 clearance = -1;
172 }
173 else if( aNode->GetRuleResolver()->IsKeepout( this, aHead, &enforce ) )
174 {
175 if( enforce )
176 clearance = 0; // keepouts are exact boundary; no clearance
177 else
178 clearance = -1;
179 }
180 else if( iface && !iface->IsFlashedOnLayer( this, aHead->Layers() ) )
181 {
182 clearance = -1;
183 }
184 else if( iface && !iface->IsFlashedOnLayer( aHead, Layers() ) )
185 {
186 clearance = -1;
187 }
188 else if( aCtx && aCtx->options.m_overrideClearance >= 0 )
189 {
190 clearance = aCtx->options.m_overrideClearance;
191 }
192 else
193 {
194 clearance = aNode->GetClearance( this, aHead, aCtx ? aCtx->options.m_useClearanceEpsilon
195 : false );
196 }
197
198 if( clearance >= 0 )
199 {
200 // Note: we can't do castellation or net-tie processing in GetClearance() because they
201 // depend on *where* the collision is.
202
203 bool checkCastellation = ( m_parent && m_parent->GetLayer() == Edge_Cuts )
204 || aNode->GetRuleResolver()->IsNonPlatedSlot( this );
205
206 bool checkNetTie = aNode->GetRuleResolver()->IsInNetTie( this );
207
208 if( checkCastellation || checkNetTie )
209 {
210 // Slow method
211 int actual;
212 VECTOR2I pos;
213
214 // The extra "1" here is to account for the fact that the hulls are built to exactly
215 // the clearance distance, so we need to allow for no collision when exactly at the
216 // clearance distance.
217 if( shapeH->Collide( shapeI, clearance + lineWidthH + lineWidthI - 1, &actual, &pos ) )
218 {
219 if( checkCastellation && aNode->QueryEdgeExclusions( pos ) )
220 return false;
221
222 if( checkNetTie && aNode->GetRuleResolver()->IsNetTieExclusion( aHead, pos, this ) )
223 return false;
224
225 if( aCtx )
226 {
227 collisionsFound = true;
228 OBSTACLE obs;
229 obs.m_head = const_cast<ITEM*>( aHead );
230 obs.m_item = const_cast<ITEM*>( this );
231 obs.m_clearance = clearance;
232 obs.m_distFirst = 0;
233 obs.m_maxFanoutWidth = 0;
234 aCtx->obstacles.insert( obs );
235 }
236 else
237 {
238 return true;
239 }
240 }
241 }
242 else
243 {
244 // Fast method
245 // The extra "1" here is to account for the fact that the hulls are built to exactly
246 // the clearance distance, so we need to allow for no collision when exactly at the
247 // clearance distance.
248 if( shapeH->Collide( shapeI, clearance + lineWidthH + lineWidthI - 1 ) )
249 {
250 if( aCtx )
251 {
252 collisionsFound = true;
253 OBSTACLE obs;
254 obs.m_head = const_cast<ITEM*>( aHead );
255 obs.m_item = const_cast<ITEM*>( this );
256 obs.m_clearance = clearance;
257 obs.m_distFirst = 0;
258 obs.m_maxFanoutWidth = 0;
259 aCtx->obstacles.insert( obs );
260 }
261 else
262 {
263 return true;
264 }
265 }
266 }
267 }
268
269 return collisionsFound;
270}
271
272
273bool ITEM::Collide( const ITEM* aOther, const NODE* aNode, COLLISION_SEARCH_CONTEXT *aCtx ) const
274{
275 if( collideSimple( aOther, aNode, aCtx ) )
276 return true;
277
278 return false;
279}
280
281
282std::string ITEM::KindStr() const
283{
284 switch( m_kind )
285 {
286 case ARC_T: return "arc";
287 case LINE_T: return "line";
288 case SEGMENT_T: return "segment";
289 case VIA_T: return "via";
290 case JOINT_T: return "joint";
291 case SOLID_T: return "solid";
292 case DIFF_PAIR_T: return "diff-pair";
293 case HOLE_T: return "hole";
294
295 default: return "unknown";
296 }
297}
298
299
301{
302}
303
304
305const std::string ITEM::Format() const
306{
307 ROUTER* router = ROUTER::GetInstance();
308 ROUTER_IFACE* iface = router ? router->GetInterface() : nullptr;
309
310 std::stringstream ss;
311 ss << KindStr() << " ";
312
313 if( iface )
314 ss << "net " << iface->GetNetName( Net() ) << " ";
315
316 ss << "layers " << m_layers.Start() << " " << m_layers.End();
317 return ss.str();
318}
319
320
321const NODE* ITEM::OwningNode() const
322{
323 if( ParentPadVia() )
324 return static_cast<const NODE*>( ParentPadVia()->Owner() );
325 else
326 return static_cast<const NODE*>( Owner() );
327}
328
329} // namespace PNS
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:231
int Start() const
Definition: pns_layerset.h:82
int End() const
Definition: pns_layerset.h:87
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
ITEM * ParentPadVia() const override
Definition: pns_hole.h:72
Base class for PNS router board items.
Definition: pns_item.h:97
bool IsFreePad() const
Definition: pns_item.h:257
PnsKind m_kind
Definition: pns_item.h:285
virtual const std::string Format() const
Definition: pns_item.cpp:305
virtual ITEM * ParentPadVia() const
Definition: pns_item.h:262
virtual NET_HANDLE Net() const
Definition: pns_item.h:194
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
LAYER_RANGE m_layers
Definition: pns_item.h:288
bool collideSimple(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx) const
Definition: pns_item.cpp:93
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:225
@ SEGMENT_T
Definition: pns_item.h:106
@ DIFF_PAIR_T
Definition: pns_item.h:109
const LAYER_RANGE & Layers() const
Definition: pns_item.h:196
virtual ~ITEM()
Definition: pns_item.cpp:300
virtual const NODE * OwningNode() const
Definition: pns_item.cpp:321
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
std::string KindStr() const
Definition: pns_item.cpp:282
virtual HOLE * Hole() const
Definition: pns_item.h:273
bool Collide(const ITEM *aHead, const NODE *aNode, COLLISION_SEARCH_CONTEXT *aCtx=nullptr) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:273
BOARD_ITEM * m_parent
Definition: pns_item.h:287
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
Keep the router "world" - i.e.
Definition: pns_node.h:207
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Return the pre-set worst case clearance between any pair of items.
Definition: pns_node.cpp:129
bool QueryEdgeExclusions(const VECTOR2I &aPos) const
Definition: pns_node.cpp:713
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:245
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:219
const ITEM_OWNER * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:71
virtual wxString GetNetName(PNS::NET_HANDLE aNet) const =0
virtual bool IsFlashedOnLayer(const PNS::ITEM *aItem, int aLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:218
static ROUTER * GetInstance()
Definition: pns_router.cpp:80
virtual bool IsNonPlatedSlot(const PNS::ITEM *aItem)=0
virtual bool IsNetTieExclusion(const ITEM *aItem, const VECTOR2I &aCollisionPos, const ITEM *aCollidingItem)=0
virtual bool IsKeepout(const ITEM *aObstacle, const ITEM *aItem, bool *aEnforce)=0
virtual bool IsInNetTie(const ITEM *aA)=0
const VECTOR2I & Pos() const
Definition: pns_via.h:128
int Diameter() const
Definition: pns_via.h:142
int Drill() const
Definition: pns_via.h:150
An abstract shape on 2D plane.
Definition: shape.h:126
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:181
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:72
@ Edge_Cuts
Definition: layer_ids.h:113
Push and Shove diff pair dimensions (gap) settings dialog.
static void dumpObstacles(const PNS::NODE::OBSTACLES &obstacles)
Definition: pns_item.cpp:34
static bool shouldWeConsiderHoleCollisions(const ITEM *aItem, const ITEM *aHead)
Definition: pns_item.cpp:49
VECTOR2I::extended_type ecoord
Definition: pns_item.cpp:30
const COLLISION_SEARCH_OPTIONS options
Definition: pns_node.h:132
std::set< OBSTACLE > & obstacles
Definition: pns_node.h:131
Hold an object colliding with another object, along with some useful data about the collision.
Definition: pns_node.h:87
int m_distFirst
... and the distance thereof
Definition: pns_node.h:93
int m_clearance
Definition: pns_node.h:91
int m_maxFanoutWidth
worst case (largest) width of the tracks connected to the item
Definition: pns_node.h:94
ITEM * m_head
Line we search collisions against.
Definition: pns_node.h:88
ITEM * m_item
Item found to be colliding with m_head.
Definition: pns_node.h:89