KiCad PCB EDA Suite
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-2022 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 <zone.h>
23#include "pns_node.h"
24#include "pns_item.h"
25#include "pns_line.h"
26#include "pns_router.h"
27
29
30namespace PNS {
31
32bool ITEM::collideSimple( const ITEM* aOther, const NODE* aNode, bool aDifferentNetsOnly, int aOverrideClearance ) const
33{
35 const SHAPE* shapeA = Shape();
36 const SHAPE* holeA = Hole();
37 int lineWidthA = 0;
38 const SHAPE* shapeB = aOther->Shape();
39 const SHAPE* holeB = aOther->Hole();
40 int lineWidthB = 0;
41
42 // Sadly collision routines ignore SHAPE_POLY_LINE widths so we have to pass them in as part
43 // of the clearance value.
44 if( m_kind == LINE_T )
45 lineWidthA = static_cast<const LINE*>( this )->Width() / 2;
46
47 if( aOther->m_kind == LINE_T )
48 lineWidthB = static_cast<const LINE*>( aOther )->Width() / 2;
49
50 // same nets? no collision!
51 if( aDifferentNetsOnly && m_net == aOther->m_net && m_net >= 0 && aOther->m_net >= 0 )
52 return false;
53
54 // a pad associated with a "free" pin (NIC) doesn't have a net until it has been used
55 if( aDifferentNetsOnly && ( IsFreePad() || aOther->IsFreePad() ) )
56 return false;
57
58 // check if we are not on completely different layers first
59 if( !m_layers.Overlaps( aOther->m_layers ) )
60 return false;
61
62 auto checkKeepout =
63 []( const ZONE* aKeepout, const BOARD_ITEM* aOther )
64 {
65 if( aKeepout->GetDoNotAllowTracks() && aOther->IsType( { PCB_ARC_T, PCB_TRACE_T } ) )
66 return true;
67
68 if( aKeepout->GetDoNotAllowVias() && aOther->Type() == PCB_VIA_T )
69 return true;
70
71 if( aKeepout->GetDoNotAllowPads() && aOther->Type() == PCB_PAD_T )
72 return true;
73
74 // Incomplete test, but better than nothing:
75 if( aKeepout->GetDoNotAllowFootprints() && aOther->Type() == PCB_PAD_T )
76 {
77 return !aKeepout->GetParentFootprint()
78 || aKeepout->GetParentFootprint() != aOther->GetParentFootprint();
79 }
80
81 return false;
82 };
83
84 const ZONE* zoneA = dynamic_cast<ZONE*>( Parent() );
85 const ZONE* zoneB = dynamic_cast<ZONE*>( aOther->Parent() );
86
87 if( zoneA && aOther->Parent() && !checkKeepout( zoneA, aOther->Parent() ) )
88 return false;
89
90 if( zoneB && Parent() && !checkKeepout( zoneB, Parent() ) )
91 return false;
92
93 bool thisNotFlashed = !iface->IsFlashedOnLayer( this, aOther->Layer() );
94 bool otherNotFlashed = !iface->IsFlashedOnLayer( aOther, Layer() );
95
97 || ( thisNotFlashed || otherNotFlashed ) )
98 && ( holeA || holeB ) )
99 {
100 int holeClearance = aNode->GetHoleClearance( this, aOther );
101
102 if( holeClearance >= 0 && holeA && holeA->Collide( shapeB, holeClearance + lineWidthB ) )
103 {
104 Mark( Marker() | MK_HOLE );
105 return true;
106 }
107
108 if( holeB && holeClearance >= 0 && holeB->Collide( shapeA, holeClearance + lineWidthA ) )
109 {
110 aOther->Mark( aOther->Marker() | MK_HOLE );
111 return true;
112 }
113
114 if( holeA && holeB )
115 {
116 int holeToHoleClearance = aNode->GetHoleToHoleClearance( this, aOther );
117
118 if( holeToHoleClearance >= 0 && holeA->Collide( holeB, holeToHoleClearance ) )
119 {
120 Mark( Marker() | MK_HOLE );
121 aOther->Mark( aOther->Marker() | MK_HOLE );
122 return true;
123 }
124 }
125 }
126
127 if( !aOther->Layers().IsMultilayer() && thisNotFlashed )
128 return false;
129
130 if( !Layers().IsMultilayer() && otherNotFlashed )
131 return false;
132
133 int clearance = aOverrideClearance >= 0 ? aOverrideClearance : aNode->GetClearance( this, aOther );
134
135 if( clearance >= 0 )
136 {
137 bool checkCastellation = ( m_parent && m_parent->GetLayer() == Edge_Cuts );
138 bool checkNetTie = aNode->GetRuleResolver()->IsInNetTie( this );
139
140 if( checkCastellation || checkNetTie )
141 {
142 // Slow method
143 int actual;
144 VECTOR2I pos;
145
146 if( shapeA->Collide( shapeB, clearance + lineWidthA, &actual, &pos ) )
147 {
148 if( checkCastellation && aNode->QueryEdgeExclusions( pos ) )
149 return false;
150
151 if( checkNetTie && aNode->GetRuleResolver()->IsNetTieExclusion( aOther, pos, this ) )
152 return false;
153
154 return true;
155 }
156 }
157 else
158 {
159 // Fast method
160 if( shapeA->Collide( shapeB, clearance + lineWidthA + lineWidthB ) )
161 return true;
162 }
163 }
164
165 return false;
166}
167
168
169bool ITEM::Collide( const ITEM* aOther, const NODE* aNode, bool aDifferentNetsOnly, int aOverrideClearance ) const
170{
171 if( collideSimple( aOther, aNode, aDifferentNetsOnly, aOverrideClearance ) )
172 return true;
173
174 // Special cases for "head" lines with vias attached at the end. Note that this does not
175 // support head-line-via to head-line-via collisions, but you can't route two independent
176 // tracks at once so it shouldn't come up.
177
178 if( m_kind == LINE_T )
179 {
180 const LINE* line = static_cast<const LINE*>( this );
181
182 if( line->EndsWithVia() && line->Via().collideSimple( aOther, aNode, aDifferentNetsOnly, aOverrideClearance ) )
183 return true;
184 }
185
186 if( aOther->m_kind == LINE_T )
187 {
188 const LINE* line = static_cast<const LINE*>( aOther );
189
190 if( line->EndsWithVia() && line->Via().collideSimple( this, aNode, aDifferentNetsOnly, aOverrideClearance ) )
191 return true;
192 }
193
194 return false;
195}
196
197
198std::string ITEM::KindStr() const
199{
200 switch( m_kind )
201 {
202 case ARC_T: return "arc";
203 case LINE_T: return "line";
204 case SEGMENT_T: return "segment";
205 case VIA_T: return "via";
206 case JOINT_T: return "joint";
207 case SOLID_T: return "solid";
208 case DIFF_PAIR_T: return "diff-pair";
209 default: return "unknown";
210 }
211}
212
213
215{
216}
217
218const std::string ITEM::Format() const
219{
220 std::stringstream ss;
221 ss << KindStr() << " ";
222 ss << "net " << m_net << " ";
223 ss << "layers " << m_layers.Start() << " " << m_layers.End();
224 return ss.str();
225}
226
227}
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:58
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:180
BOARD_ITEM_CONTAINER * GetParentFootprint() const
Definition: board_item.cpp:239
int Start() const
Definition: pns_layerset.h:82
bool IsMultilayer() const
Definition: pns_layerset.h:77
int End() const
Definition: pns_layerset.h:87
bool Overlaps(const LAYER_RANGE &aOther) const
Definition: pns_layerset.h:67
Base class for PNS router board items.
Definition: pns_item.h:56
BOARD_ITEM * Parent() const
Definition: pns_item.h:151
bool IsFreePad() const
Definition: pns_item.h:238
PnsKind m_kind
Definition: pns_item.h:254
virtual const std::string Format() const
Definition: pns_item.cpp:218
int m_net
Definition: pns_item.h:261
bool Collide(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly=true, int aOverrideClearance=-1) const
Check for a collision (clearance violation) with between us and item aOther.
Definition: pns_item.cpp:169
virtual const SHAPE * Hole() const
Definition: pns_item.h:207
LAYER_RANGE m_layers
Definition: pns_item.h:258
virtual int Layer() const
Definition: pns_item.h:160
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:202
@ SOLID_T
Definition: pns_item.h:63
@ LINE_T
Definition: pns_item.h:64
@ SEGMENT_T
Definition: pns_item.h:66
@ DIFF_PAIR_T
Definition: pns_item.h:69
@ JOINT_T
Definition: pns_item.h:65
const LAYER_RANGE & Layers() const
Definition: pns_item.h:156
virtual ~ITEM()
Definition: pns_item.cpp:214
bool collideSimple(const ITEM *aOther, const NODE *aNode, bool aDifferentNetsOnly, int aOverrideClearance) const
Definition: pns_item.cpp:32
std::string KindStr() const
Returns the kind of the item, as string.
Definition: pns_item.cpp:198
virtual void Mark(int aMarker) const
Definition: pns_item.h:212
virtual int Marker() const
Definition: pns_item.h:214
BOARD_ITEM * m_parent
Definition: pns_item.h:256
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
const VIA & Via() const
Definition: pns_line.h:199
bool EndsWithVia() const
Definition: pns_line.h:194
Keep the router "world" - i.e.
Definition: pns_node.h:156
COLLISION_QUERY_SCOPE GetCollisionQueryScope() const
Definition: pns_node.h:421
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:103
@ CQS_ALL_RULES
check all rules
Definition: pns_node.h:162
bool QueryEdgeExclusions(const VECTOR2I &aPos) const
Definition: pns_node.cpp:734
int GetHoleToHoleClearance(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:127
RULE_RESOLVER * GetRuleResolver() const
Return the number of joints.
Definition: pns_node.h:197
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:115
virtual bool IsFlashedOnLayer(const PNS::ITEM *aItem, int aLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:211
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
virtual bool IsNetTieExclusion(const PNS::ITEM *aItem, const VECTOR2I &aCollisionPos, const PNS::ITEM *aCollidingItem)=0
virtual bool IsInNetTie(const ITEM *aA)=0
An abstract shape on 2D plane.
Definition: shape.h:123
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:178
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
Handle a list of polygons defining a copper zone.
Definition: zone.h:57
bool GetDoNotAllowVias() const
Definition: zone.h:699
bool GetDoNotAllowPads() const
Definition: zone.h:701
bool GetDoNotAllowTracks() const
Definition: zone.h:700
bool GetDoNotAllowFootprints() const
Definition: zone.h:702
@ Edge_Cuts
Definition: layer_ids.h:113
Push and Shove diff pair dimensions (gap) settings dialog.
@ MK_HOLE
Definition: pns_item.h:45
VECTOR2I::extended_type ecoord
Definition: pns_item.cpp:28
@ PCB_VIA_T
class PCB_VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:102
@ PCB_PAD_T
class PAD, a pad in a footprint
Definition: typeinfo.h:87
@ PCB_ARC_T
class PCB_ARC, an arc track segment on a copper layer
Definition: typeinfo.h:103
@ PCB_TRACE_T
class PCB_TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:101