KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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-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_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
39 aOther->Shape()->Collide( Shape(), clearance, &elementForces[nf++] );
40
41 for( size_t i = 0; i < nf; i++ )
42 {
43 if( elementForces[i].SquaredEuclideanNorm() > force.SquaredEuclideanNorm() )
44 force = elementForces[i];
45 }
46
47 aForce = force;
48
49 return ( force != VECTOR2I( 0, 0 ) );
50}
51
52bool VIA::PushoutForce( NODE* aNode, const VECTOR2I& aDirection, VECTOR2I& aForce,
53 int aCollisionMask, int aMaxIterations )
54{
55 int iter = 0;
56 VIA mv( *this );
57 VECTOR2I totalForce;
58
60 PNS_DBG( dbg, AddPoint, Pos(), YELLOW, 100000, wxString::Format( "via-force-init-pos, iter %d", aMaxIterations ) );
61
62 while( iter < aMaxIterations )
63 {
64 NODE::OPT_OBSTACLE obs = aNode->CheckColliding( &mv, aCollisionMask );
65
66 if( !obs )
67 break;
68
69 VECTOR2I force;
70 bool collFound = mv.PushoutForce( aNode, obs->m_item, force );
71
72 if( !collFound )
73 {
74 if( obs )
75 {
76 // might happen (although rarely) that we see a collision, but the MTV
77 // is zero... Assume force propagation has failed in such case.
78 return false;
79 }
80 PNS_DBG( dbg, Message, wxString::Format( "no-coll %d", iter ) );
81 break;
82 }
83
84 const int threshold = Diameter() / 4; // another stupid heuristic.
85 const int forceMag = force.EuclideanNorm();
86
87 // We've been through a lot of iterations already and our pushout force is still too big?
88 // Perhaps the barycentric force goes in the wrong direction, let's try to move along
89 // the 'lead' vector instead (usually backwards to the cursor)
90 if( iter > aMaxIterations / 2 && forceMag > threshold )
91 {
92 VECTOR2I l = aDirection.Resize( threshold );
93 totalForce += l;
94
96 ff.Append( mv.Pos() );
97 ff.Append( mv.Pos() + l );
98
99 mv.SetPos( mv.Pos() + l );
100
101 PNS_DBG( dbg, AddShape, &ff, YELLOW, 100000, "via-force-lead" );
102 }
103 else if( collFound ) // push along the minmum translation vector
104 {
105 // Limit the force magnitude to, say, 25% of the via diameter
106 // This adds a few iterations for large areas (e.g. keepouts)
107 // But makes the algorithm more predictable and less 'jumpy'
108 if( forceMag > threshold )
109 {
110 force.Resize( threshold );
111 }
112
113 totalForce += force;
114
116 ff.Append( mv.Pos() );
117 ff.Append( mv.Pos() + force );
118
119 mv.SetPos( mv.Pos() + force );
120
121 PNS_DBG( dbg, AddShape, &ff, WHITE, 100000, "via-force-coll" );
122 }
123
124 iter++;
125 }
126
127 if( iter == aMaxIterations )
128 return false;
129
130 PNS_DBG( dbg, AddPoint, ( Pos() + totalForce ), WHITE, 1000000, "via-force-new" );
131
132 aForce = totalForce;
133
134 return true;
135}
136
137
138const SHAPE_LINE_CHAIN VIA::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
139{
140 int cl = ( aClearance + aWalkaroundThickness / 2 );
141 int width = m_diameter;
142
143 if( m_hole && !ROUTER::GetInstance()->GetInterface()->IsFlashedOnLayer( this, aLayer ) )
144 width = m_hole->Radius() * 2;
145
146 // Chamfer = width * ( 1 - sqrt(2)/2 ) for equilateral octagon
147 return OctagonalHull( m_pos - VECTOR2I( width / 2, width / 2 ),
148 VECTOR2I( width, width ),
149 cl, ( 2 * cl + width ) * ( 1.0 - M_SQRT1_2 ) );
150}
151
152
154{
155 VIA* v = new VIA();
156
157 v->SetNet( Net() );
158 v->SetLayers( Layers() );
159 v->m_pos = m_pos;
161 v->m_drill = m_drill;
164 v->m_rank = m_rank;
165 v->m_marker = m_marker;
166 v->m_viaType = m_viaType;
167 v->m_parent = m_parent;
168 v->m_isFree = m_isFree;
170
171 return v;
172}
173
174
175OPT_BOX2I VIA::ChangedArea( const VIA* aOther ) const
176{
177 if( aOther->Pos() != Pos() )
178 {
179 BOX2I tmp = Shape()->BBox();
180 tmp.Merge( aOther->Shape()->BBox() );
181 return tmp;
182 }
183
184 return OPT_BOX2I();
185}
186
187
189{
190 VIA_HANDLE h;
191 h.pos = Pos();
192 h.layers = Layers();
193 h.net = Net();
194 h.valid = true;
195 return h;
196}
197
198
199const std::string VIA::Format( ) const
200{
201 std::stringstream ss;
202 ss << ITEM::Format() << " drill " << m_drill << " ";
203 ss << m_shape.Format( false );
204 return ss.str();
205}
206
207}
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
int Radius() const
Definition: pns_hole.cpp:103
static HOLE * MakeCircularHole(const VECTOR2I &pos, int radius)
Definition: pns_hole.cpp:131
Base class for PNS router board items.
Definition: pns_item.h:91
void SetLayers(const LAYER_RANGE &aLayers)
Definition: pns_item.h:192
virtual const std::string Format() const
Definition: pns_item.cpp:242
bool m_isVirtual
Definition: pns_item.h:289
void SetNet(int aNet)
Definition: pns_item.h:188
virtual int Net() const
Definition: pns_item.h:189
virtual const SHAPE * Shape() const
Return the geometrical shape of the item.
Definition: pns_item.h:220
const LAYER_RANGE & Layers() const
Definition: pns_item.h:191
int m_marker
Definition: pns_item.h:286
BOARD_ITEM * m_parent
Definition: pns_item.h:281
int m_rank
Definition: pns_item.h:287
Keep the router "world" - i.e.
Definition: pns_node.h:198
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:113
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:377
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:208
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
virtual bool IsFlashedOnLayer(const PNS::ITEM *aItem, int aLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
static ROUTER * GetInstance()
Definition: pns_router.cpp:78
VIA()
Definition: pns_via.h:53
OPT_BOX2I ChangedArea(const VIA *aOther) const
Definition: pns_via.cpp:175
int m_drill
Definition: pns_via.h:191
const VECTOR2I & Pos() const
Definition: pns_via.h:111
const SHAPE * Shape() const override
Return the geometrical shape of the item.
Definition: pns_via.h:151
virtual void SetHole(HOLE *aHole) override
Definition: pns_via.h:172
int Diameter() const
Definition: pns_via.h:125
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:188
virtual const std::string Format() const override
Definition: pns_via.cpp:199
bool PushoutForce(NODE *aNode, const VECTOR2I &aDirection, VECTOR2I &aForce, int aCollisionMask=ITEM::ANY_T, int aMaxIterations=10)
Definition: pns_via.cpp:52
void SetPos(const VECTOR2I &aPos)
Definition: pns_via.h:113
int m_diameter
Definition: pns_via.h:190
VIATYPE m_viaType
Definition: pns_via.h:194
HOLE * m_hole
Definition: pns_via.h:196
VECTOR2I m_pos
Definition: pns_via.h:192
const SHAPE_LINE_CHAIN Hull(int aClearance=0, int aWalkaroundThickness=0, int aLayer=-1) const override
Definition: pns_via.cpp:138
bool m_isFree
Definition: pns_via.h:195
SHAPE_CIRCLE m_shape
Definition: pns_via.h:193
VIA * Clone() const override
Return a deep copy of the item.
Definition: pns_via.cpp:153
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:179
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:272
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
@ WHITE
Definition: color4d.h:47
@ YELLOW
Definition: color4d.h:66
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,...)
VECTOR2I pos
Definition: pns_via.h:45
LAYER_RANGE layers
Definition: pns_via.h:46
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588