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 int clearanceEpsilon = aNode->GetRuleResolver()->ClearanceEpsilon();
107 bool collisionsFound = false;
108
109 if( this == aHead ) // we cannot be self-colliding
110 return false;
111
112 if ( !shouldWeConsiderHoleCollisions( this, aHead ) )
113 return false;
114
115 // Special cases for "head" lines with vias attached at the end. Note that this does not
116 // support head-line-via to head-line-via collisions, but you can't route two independent
117 // tracks at once so it shouldn't come up.
118
119 if( const auto line = dyn_cast<const LINE*>( this ) )
120 {
121 if( line->EndsWithVia() )
122 collisionsFound |= line->Via().collideSimple( aHead, aNode, aCtx );
123 }
124
125 if( const auto line = dyn_cast<const LINE*>( aHead ) )
126 {
127 if( line->EndsWithVia() )
128 collisionsFound |= line->Via().collideSimple( this, aNode, aCtx );
129 }
130
131 // And a special case for the "head" via's hole.
132 if( holeH && shouldWeConsiderHoleCollisions( this, holeH ) )
133 {
134 if( collideSimple( holeH, aNode, aCtx ) )
135 collisionsFound = true;
136 }
137
138 // Sadly collision routines ignore SHAPE_POLY_LINE widths so we have to pass them in as part
139 // of the clearance value.
140 if( m_kind == LINE_T )
141 lineWidthI = static_cast<const LINE*>( this )->Width() / 2;
142
143 if( aHead->m_kind == LINE_T )
144 lineWidthH = static_cast<const LINE*>( aHead )->Width() / 2;
145
146 // check if we are not on completely different layers first
147 if( !m_layers.Overlaps( aHead->m_layers ) )
148 return false;
149
150 // fixme: this f***ing singleton must go...
151 ROUTER* router = ROUTER::GetInstance();
152 ROUTER_IFACE* iface = router ? router->GetInterface() : nullptr;
153 bool differentNetsOnly = true;
154 bool enforce = false;
155 int clearance;
156
157 if( aCtx )
158 differentNetsOnly = aCtx->options.m_differentNetsOnly;
159
160 // Hole-to-hole collisions don't have anything to do with nets
161 if( Kind() == HOLE_T && aHead->Kind() == HOLE_T )
162 differentNetsOnly = false;
163
164 if( differentNetsOnly && Net() == aHead->Net() && aHead->Net() )
165 {
166 // same nets? no clearance!
167 clearance = -1;
168 }
169 else if( differentNetsOnly && ( IsFreePad() || aHead->IsFreePad() ) )
170 {
171 // a pad associated with a "free" pin (NIC) doesn't have a net until it has been used
172 clearance = -1;
173 }
174 else if( aNode->GetRuleResolver()->IsKeepout( this, aHead, &enforce ) )
175 {
176 if( enforce )
177 clearance = 0; // keepouts are exact boundary; no clearance
178 else
179 clearance = -1;
180 }
181 else if( iface && !iface->IsFlashedOnLayer( this, aHead->Layers() ) )
182 {
183 clearance = -1;
184 }
185 else if( iface && !iface->IsFlashedOnLayer( aHead, Layers() ) )
186 {
187 clearance = -1;
188 }
189 else if( aCtx && aCtx->options.m_overrideClearance >= 0 )
190 {
191 clearance = aCtx->options.m_overrideClearance;
192 }
193 else
194 {
195 clearance = aNode->GetClearance( this, aHead, aCtx ? aCtx->options.m_useClearanceEpsilon
196 : false );
197 }
198
199 if( clearance >= 0 )
200 {
201 // Note: we can't do castellation or net-tie processing in GetClearance() because they
202 // depend on *where* the collision is.
203
204 bool checkCastellation = ( m_parent && m_parent->GetLayer() == Edge_Cuts );
205 bool checkNetTie = ( m_parent && aNode->GetRuleResolver()->IsInNetTie( this ) );
206
207 if( checkCastellation || checkNetTie )
208 {
209 // Slow method
210 int actual;
211 VECTOR2I pos;
212
213 if( shapeH->Collide( shapeI, clearance + lineWidthH + lineWidthI - clearanceEpsilon,
214 &actual, &pos ) )
215 {
216 if( checkCastellation && aNode->QueryEdgeExclusions( pos ) )
217 return false;
218
219 if( checkNetTie && aNode->GetRuleResolver()->IsNetTieExclusion( aHead, pos, this ) )
220 return false;
221
222 if( aCtx )
223 {
224 collisionsFound = true;
225 OBSTACLE obs;
226 obs.m_head = const_cast<ITEM*>( aHead );
227 obs.m_item = const_cast<ITEM*>( this );
228 obs.m_clearance = clearance;
229 obs.m_distFirst = 0;
230 obs.m_maxFanoutWidth = 0;
231 aCtx->obstacles.insert( obs );
232 }
233 else
234 {
235 return true;
236 }
237 }
238 }
239 else
240 {
241 // Fast method
242 if( shapeH->Collide( shapeI, clearance + lineWidthH + lineWidthI - clearanceEpsilon ) )
243 {
244 if( aCtx )
245 {
246 collisionsFound = true;
247 OBSTACLE obs;
248 obs.m_head = const_cast<ITEM*>( aHead );
249 obs.m_item = const_cast<ITEM*>( this );
250 obs.m_clearance = clearance;
251 obs.m_distFirst = 0;
252 obs.m_maxFanoutWidth = 0;
254 aCtx->obstacles.insert( obs );
255 }
256 else
257 {
258 return true;
259 }
260 }
261 }
262 }
263
264 return collisionsFound;
265}
266
267
268bool ITEM::Collide( const ITEM* aOther, const NODE* aNode, COLLISION_SEARCH_CONTEXT *aCtx ) const
269{
270 if( collideSimple( aOther, aNode, aCtx ) )
271 return true;
272
273 return false;
274}
275
276
277std::string ITEM::KindStr() const
278{
279 switch( m_kind )
280 {
281 case ARC_T: return "arc";
282 case LINE_T: return "line";
283 case SEGMENT_T: return "segment";
284 case VIA_T: return "via";
285 case JOINT_T: return "joint";
286 case SOLID_T: return "solid";
287 case DIFF_PAIR_T: return "diff-pair";
288 case HOLE_T: return "hole";
289
290 default: return "unknown";
291 }
292}
293
294
296{
297}
298
299
300const std::string ITEM::Format() const
301{
302 ROUTER* router = ROUTER::GetInstance();
303 ROUTER_IFACE* iface = router ? router->GetInterface() : nullptr;
304
305 std::stringstream ss;
306 ss << KindStr() << " ";
307
308 if( iface )
309 ss << "net " << iface->GetNetCode( Net() ) << " ";
310
311 ss << "layers " << m_layers.Start() << " " << m_layers.End();
312 return ss.str();
313}
314
315
316const NODE* ITEM::OwningNode() const
317{
318 if( ParentPadVia() )
319 return static_cast<const NODE*>( ParentPadVia()->Owner() );
320 else
321 return static_cast<const NODE*>( Owner() );
322}
323
324} // namespace PNS
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:225
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:256
PnsKind m_kind
Definition: pns_item.h:284
virtual const std::string Format() const
Definition: pns_item.cpp:300
virtual ITEM * ParentPadVia() const
Definition: pns_item.h:261
virtual NET_HANDLE Net() const
Definition: pns_item.h:193
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:166
LAYER_RANGE m_layers
Definition: pns_item.h:287
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:224
@ SEGMENT_T
Definition: pns_item.h:105
@ DIFF_PAIR_T
Definition: pns_item.h:108
const LAYER_RANGE & Layers() const
Definition: pns_item.h:195
virtual ~ITEM()
Definition: pns_item.cpp:295
virtual const NODE * OwningNode() const
Definition: pns_item.cpp:316
bool OfKind(int aKindMask) const
Definition: pns_item.h:174
std::string KindStr() const
Definition: pns_item.cpp:277
virtual HOLE * Hole() const
Definition: pns_item.h:272
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:268
BOARD_ITEM * m_parent
Definition: pns_item.h:286
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:206
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:707
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:244
std::set< OBSTACLE > OBSTACLES
Definition: pns_node.h:218
const ITEM_OWNER * Owner() const
Return the owner of this item, or NULL if there's none.
Definition: pns_item.h:71
virtual int GetNetCode(NET_HANDLE aNet) const =0
virtual bool IsFlashedOnLayer(const PNS::ITEM *aItem, int aLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:217
static ROUTER * GetInstance()
Definition: pns_router.cpp:82
virtual int ClearanceEpsilon() const
Definition: pns_node.h:169
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:114
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:134
std::set< OBSTACLE > & obstacles
Definition: pns_node.h:133
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
CONSTRAINT_TYPE m_violatingConstraint
Definition: pns_node.h:96
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