KiCad PCB EDA Suite
pns_via.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-2020 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_via.h"
23#include "pns_node.h"
24#include "pns_utils.h"
25#include "pns_router.h"
26#include "pns_debug_decorator.h"
27
28#include <geometry/shape_rect.h>
29#include <math/box2.h>
30
31namespace PNS {
32
33bool VIA::PushoutForce( NODE* aNode, const ITEM* aOther, VECTOR2I& aForce )
34{
35 int clearance = aNode->GetClearance( this, aOther );
36 VECTOR2I elementForces[4], force;
37 size_t nf = 0;
38
40 {
41 int holeClearance = aNode->GetHoleClearance( this, aOther );
42 int hole2holeClearance = aNode->GetHoleToHoleClearance( this, aOther );
43
44 if( aOther->Hole() )
45 {
46 aOther->Hole()->Collide( Shape(), holeClearance, &elementForces[nf++] );
47 aOther->Hole()->Collide( Hole(), hole2holeClearance, &elementForces[nf++] );
48 }
49
50 aOther->Shape()->Collide( Hole(), holeClearance, &elementForces[nf++] );
51 }
52
53 aOther->Shape()->Collide( Shape(), clearance, &elementForces[nf++] );
54
55 for( size_t i = 0; i < nf; i++ )
56 {
57 if( elementForces[i].SquaredEuclideanNorm() > force.SquaredEuclideanNorm() )
58 force = elementForces[i];
59 }
60
61 aForce = force;
62
63 return ( force != VECTOR2I( 0, 0 ) );
64}
65
66bool VIA::PushoutForce( NODE* aNode, const VECTOR2I& aDirection, VECTOR2I& aForce,
67 int aCollisionMask, int aMaxIterations )
68{
69 int iter = 0;
70 VIA mv( *this );
71 VECTOR2I totalForce;
72
74 PNS_DBG( dbg, AddPoint, Pos(), YELLOW, 100000, wxString::Format( "via-force-init-pos, iter %d", aMaxIterations ) );
75
76 while( iter < aMaxIterations )
77 {
78 NODE::OPT_OBSTACLE obs = aNode->CheckColliding( &mv, aCollisionMask );
79
80 if( !obs )
81 break;
82
83 VECTOR2I force;
84 bool collFound = mv.PushoutForce( aNode, obs->m_item, force );
85
86 if( !collFound )
87 {
88 if( obs )
89 {
90 // might happen (although rarely) that we see a collision, but the MTV
91 // is zero... Assume force propagation has failed in such case.
92 return false;
93 }
94 PNS_DBG( dbg, Message, wxString::Format( "no-coll %d", iter ) );
95 break;
96 }
97
98 const int threshold = Diameter() / 4; // another stupid heuristic.
99 const int forceMag = force.EuclideanNorm();
100
101 // We've been through a lot of iterations already and our pushout force is still too big?
102 // Perhaps the barycentric force goes in the wrong direction, let's try to move along
103 // the 'lead' vector instead (usually backwards to the cursor)
104 if( iter > aMaxIterations / 2 && forceMag > threshold )
105 {
106 VECTOR2I l = aDirection.Resize( threshold );
107 totalForce += l;
108
110 ff.Append( mv.Pos() );
111 ff.Append( mv.Pos() + l );
112
113 mv.SetPos( mv.Pos() + l );
114
115 PNS_DBG( dbg, AddShape, &ff, YELLOW, 100000, "via-force-lead" );
116 }
117 else if( collFound ) // push along the minmum translation vector
118 {
119 // Limit the force magnitude to, say, 25% of the via diameter
120 // This adds a few iterations for large areas (e.g. keepouts)
121 // But makes the algorithm more predictable and less 'jumpy'
122 if( forceMag > threshold )
123 {
124 force.Resize( threshold );
125 }
126
127 totalForce += force;
128
130 ff.Append( mv.Pos() );
131 ff.Append( mv.Pos() + force );
132
133 mv.SetPos( mv.Pos() + force );
134
135 PNS_DBG( dbg, AddShape, &ff, WHITE, 100000, "via-force-coll" );
136 }
137
138 iter++;
139 }
140
141 if( iter == aMaxIterations )
142 return false;
143
144 PNS_DBG( dbg, AddPoint, ( Pos() + totalForce ), WHITE, 1000000, "via-force-new" );
145
146 aForce = totalForce;
147
148 return true;
149}
150
151
152const SHAPE_LINE_CHAIN VIA::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
153{
154 int cl = ( aClearance + aWalkaroundThickness / 2 );
155 int width = m_diameter;
156
157 if( !ROUTER::GetInstance()->GetInterface()->IsFlashedOnLayer( this, aLayer ) )
158 width = m_hole.GetRadius() * 2;
159
160 // Chamfer = width * ( 1 - sqrt(2)/2 ) for equilateral octagon
161 return OctagonalHull( m_pos - VECTOR2I( width / 2, width / 2 ),
162 VECTOR2I( width, width ),
163 cl, ( 2 * cl + width ) * ( 1.0 - M_SQRT1_2 ) );
164}
165
166
167const SHAPE_LINE_CHAIN VIA::HoleHull( int aClearance, int aWalkaroundThickness, int aLayer ) const
168{
169 int cl = ( aClearance + aWalkaroundThickness / 2 );
170 int width = m_hole.GetRadius() * 2;
171
172 // Chamfer = width * ( 1 - sqrt(2)/2 ) for equilateral octagon
173 return OctagonalHull( m_pos - VECTOR2I( width / 2, width / 2 ), VECTOR2I( width, width ), cl,
174 ( 2 * cl + width ) * ( 1.0 - M_SQRT1_2 ) );
175}
176
177
179{
180 VIA* v = new VIA();
181
182 v->SetNet( Net() );
183 v->SetLayers( Layers() );
184 v->m_pos = m_pos;
186 v->m_drill = m_drill;
188 v->m_hole = SHAPE_CIRCLE( m_pos, m_drill / 2 );
189 v->m_rank = m_rank;
190 v->m_marker = m_marker;
191 v->m_viaType = m_viaType;
192 v->m_parent = m_parent;
193 v->m_isFree = m_isFree;
195
196 return v;
197}
198
199
200OPT_BOX2I VIA::ChangedArea( const VIA* aOther ) const
201{
202 if ( aOther->Pos() != Pos() )
203 {
204 BOX2I tmp = Shape()->BBox();
205 tmp.Merge( aOther->Shape()->BBox() );
206 return tmp;
207 }
208
209 return OPT_BOX2I();
210}
211
212
214{
215 VIA_HANDLE h;
216 h.pos = Pos();
217 h.layers = Layers();
218 h.net = Net();
219 h.valid = true;
220 return h;
221}
222
223
224const std::string VIA::Format( ) const
225{
226 std::stringstream ss;
227 ss << ITEM::Format() << " drill " << m_drill << " ";
228 ss << m_shape.Format( false );
229 return ss.str();
230}
231
232}
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:850
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
Base class for PNS router board items.
Definition: pns_item.h:56
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:157
virtual const std::string Format() const
Definition: pns_item.cpp:218
bool m_isVirtual
Definition: pns_item.h:265
virtual const SHAPE * Hole() const
Definition: pns_item.h:207
void SetNet(int aNet)
Definition: pns_item.h:153
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:202
const LAYER_RANGE & Layers() const
Definition: pns_item.h:156
int m_marker
Definition: pns_item.h:262
int Net() const
Definition: pns_item.h:154
BOARD_ITEM * m_parent
Definition: pns_item.h:256
int m_rank
Definition: pns_item.h:263
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
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:472
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:166
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
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:115
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
virtual bool IsFlashedOnLayer(const PNS::ITEM *aItem, int aLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:214
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
VIA()
Definition: pns_via.h:52
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:200
int m_drill
Definition: pns_via.h:167
const VECTOR2I & Pos() const
Definition: pns_via.h:100
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_via.h:136
const SHAPE_LINE_CHAIN HoleHull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:167
int Diameter() const
Definition: pns_via.h:112
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:213
virtual const std::string Format() const override
Definition: pns_via.cpp:224
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
Definition: pns_via.cpp:66
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:102
int m_diameter
Definition: pns_via.h:166
VIATYPE m_viaType
Definition: pns_via.h:171
VECTOR2I m_pos
Definition: pns_via.h:168
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:152
bool m_isFree
Definition: pns_via.h:172
SHAPE_CIRCLE m_hole
Definition: pns_via.h:170
const SHAPE_CIRCLE * Hole() const override
Definition: pns_via.h:138
SHAPE_CIRCLE m_shape
Definition: pns_via.h:169
VIA * Clone() const override
Return a deep copy of the item.
Definition: pns_via.cpp:178
int GetRadius() const
Definition: shape_circle.h:108
virtual const std::string Format(bool aCplusPlus=true) const override
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
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
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:300
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378
@ WHITE
Definition: color4d.h:48
@ YELLOW
Definition: color4d.h:67
Push and Shove diff pair dimensions (gap) settings dialog.
const SHAPE_LINE_CHAIN OctagonalHull(const VECTOR2I &aP0, const VECTOR2I &aSize, int aClearance, int aChamfer)
Definition: pns_utils.cpp:36
#define PNS_DBG(dbg, method,...)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
VECTOR2I pos
Definition: pns_via.h:44
LAYER_RANGE layers
Definition: pns_via.h:45
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618