KiCad PCB EDA Suite
pns_meander_placer_base.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2015 CERN
5 * Copyright (C) 2016-2021 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
23#include "pns_meander.h"
24#include "pns_router.h"
25#include "pns_solid.h"
26#include "pns_arc.h"
27
28namespace PNS {
29
31 PLACEMENT_ALGO( aRouter )
32{
33 m_world = nullptr;
36 m_startPad_n = nullptr;
37 m_startPad_p = nullptr;
38 m_endPad_n = nullptr;
39 m_endPad_p = nullptr;
40}
41
42
44{
45}
46
47
49{
51 a = std::max( a, m_settings.m_minAmplitude );
52
54}
55
56
58{
59 int s = m_settings.m_spacing + aSign * m_settings.m_step;
60 s = std::max( s, m_currentWidth + Clearance() );
61
63}
64
65
67{
68 // Assumption: All tracks are part of the same net class.
69 // It shouldn't matter which track we pick. They should all have the same clearance if
70 // they are part of the same net class. Therefore, pick the first one on the list.
71 ITEM* itemToCheck = Traces().CItems().front().item;
72 PNS::CONSTRAINT constraint;
73
75 nullptr, CurrentLayer(), &constraint );
76
77 wxCHECK_MSG( constraint.m_Value.HasMin(), m_currentWidth, wxT( "No minimum clearance?" ) );
78
79 return constraint.m_Value.Min();
80}
81
82
84{
85 m_settings = aSettings;
86}
87
88
89void MEANDER_PLACER_BASE::cutTunedLine( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aTuneStart,
90 const VECTOR2I& aCursorPos, SHAPE_LINE_CHAIN& aPre,
91 SHAPE_LINE_CHAIN& aTuned, SHAPE_LINE_CHAIN& aPost )
92{
93 VECTOR2I cp ( aCursorPos );
94
95 if( cp == aTuneStart ) // we don't like tuning segments with 0 length
96 {
97 int idx = aOrigin.FindSegment( cp );
98
99 if( idx >= 0 )
100 {
101 const SEG& s = aOrigin.CSegment( idx );
102 cp += ( s.B - s.A ).Resize( 2 );
103 }
104 else
105 {
106 cp += VECTOR2I( 2, 5 ); // some arbitrary value that is not 45 degrees oriented
107 }
108 }
109
110 VECTOR2I n = aOrigin.NearestPoint( cp, false );
111 VECTOR2I m = aOrigin.NearestPoint( aTuneStart, false );
112
113 SHAPE_LINE_CHAIN l( aOrigin );
114 l.Split( n );
115 l.Split( m );
116
117 int i_start = l.Find( m );
118 int i_end = l.Find( n );
119
120 if( i_start > i_end )
121 {
122 l = l.Reverse();
123 i_start = l.Find( m );
124 i_end = l.Find( n );
125 }
126
127 aPre = l.Slice( 0, i_start );
128 aPost = l.Slice( i_end, -1 );
129 aTuned = l.Slice( i_start, i_end );
130
131 aTuned.Simplify();
132}
133
134
135void MEANDER_PLACER_BASE::tuneLineLength( MEANDERED_LINE& aTuned, long long int aElongation )
136{
137 long long int remaining = aElongation;
138 bool finished = false;
139
140 for( MEANDER_SHAPE* m : aTuned.Meanders() )
141 {
142 if( m->Type() != MT_CORNER && m->Type() != MT_ARC )
143 {
144 if( remaining >= 0 )
145 remaining -= m->MaxTunableLength() - m->BaselineLength();
146
147 if( remaining < 0 )
148 {
149 if( !finished )
150 {
151 MEANDER_TYPE newType;
152
153 if( m->Type() == MT_START || m->Type() == MT_SINGLE )
154 newType = MT_SINGLE;
155 else
156 newType = MT_FINISH;
157
158 m->SetType( newType );
159 m->Recalculate();
160
161 finished = true;
162 }
163 else
164 {
165 m->MakeEmpty();
166 }
167 }
168 }
169 }
170
171 remaining = aElongation;
172 int meanderCount = 0;
173
174 for( MEANDER_SHAPE* m : aTuned.Meanders() )
175 {
176 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
177 {
178 if(remaining >= 0)
179 {
180 remaining -= m->MaxTunableLength() - m->BaselineLength();
181 meanderCount ++;
182 }
183 }
184 }
185
186 long long int balance = 0;
187
188 if( meanderCount )
189 balance = -remaining / meanderCount;
190
191 if( balance >= 0 )
192 {
193 for( MEANDER_SHAPE* m : aTuned.Meanders() )
194 {
195 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
196 {
197 m->Resize( std::max( m->Amplitude() - balance / 2,
198 (long long int) m_settings.m_minAmplitude ) );
199 }
200 }
201 }
202}
203
204
206{
207 int length = 0;
208 JOINT start;
209 JOINT end;
210
211 m_world->FindLineEnds( aLine, start, end );
212
213 // Extract the length of the pad to die for start and end pads
214 for( auto& link : start.LinkList() )
215 {
216 if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
217 {
218 // If there are overlapping pads, choose the first with a non-zero length
219 if( solid->GetPadToDie() > 0 )
220 {
221 length += solid->GetPadToDie();
222 break;
223 }
224 }
225 }
226
227 for( auto& link : end.LinkList() )
228 {
229 if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
230 {
231 if( solid->GetPadToDie() > 0 )
232 {
233 length += solid->GetPadToDie();
234 break;
235 }
236 }
237 }
238
239 return length;
240}
241
242
244{
245 return m_settings;
246}
247
248
250 long long int aValue, long long int aExpected, long long int aTolerance ) const
251{
252 if( aValue < aExpected - aTolerance )
253 return -1;
254 else if( aValue > aExpected + aTolerance )
255 return 1;
256 else
257 return 0;
258}
259
260
262{
263 if( aStartItem->Kind() == ITEM::SEGMENT_T )
264 {
265 return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
266 }
267 else
268 {
269 wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
270 ARC* arc = static_cast<ARC*>( aStartItem );
271
272 if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
273 ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
274 {
275 return arc->Anchor( 0 );
276 }
277 else
278 {
279 return arc->Anchor( 1 );
280 }
281 }
282}
283
284
285long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine, const SOLID* aStartPad, const SOLID* aEndPad ) const
286{
287 long long int total = 0;
288
289 if( aLine.Empty() )
290 return 0;
291
292 const ITEM* start_item = aLine[0];
293 const ITEM* end_item = aLine[aLine.Size() - 1];
294 bool start_via = false;
295 bool end_via = false;
296
297
303 start_via = aStartPad && ( !aStartPad->LayersOverlap( start_item ) );
304 end_via = aEndPad && ( !aEndPad->LayersOverlap( end_item ) );
305
306 for( int idx = 0; idx < aLine.Size(); idx++ )
307 {
308 const ITEM* item = aLine[idx];
309
310 if( const LINE* l = dyn_cast<const LINE*>( item ) )
311 {
312 total += l->CLine().Length();
313 }
314 else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
315 {
316 int layerPrev = aLine[idx - 1]->Layer();
317 int layerNext = aLine[idx + 1]->Layer();
318
319 if( layerPrev != layerNext )
320 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
321 }
322 }
323
324 if( start_via )
325 {
326 int layerPrev = aStartPad->Layer();
327 int layerNext = start_item->Layer();
328
329 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
330 }
331
332 if( end_via )
333 {
334 int layerPrev = end_item->Layer();
335 int layerNext = aEndPad->Layer();
336
337 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
338 }
339
340 return total;
341}
342
343}
T Min() const
Definition: minoptmax.h:33
bool HasMin() const
Definition: minoptmax.h:37
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:99
bool Empty() const
Definition: pns_itemset.h:130
int Size() const
Definition: pns_itemset.h:160
const ENTRIES & CItems() const
Definition: pns_itemset.h:136
Base class for PNS router board items.
Definition: pns_item.h:56
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:130
virtual int Layer() const
Definition: pns_item.h:158
@ SEGMENT_T
Definition: pns_item.h:66
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:138
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:163
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:43
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:241
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:386
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:489
virtual void UpdateSettings(const MEANDER_SETTINGS &aSettings)
void tuneLineLength(MEANDERED_LINE &aTuned, long long int aElongation)
Take a set of meanders in aTuned and tunes their length to extend the original line length by aElonga...
virtual void SpacingStep(int aSign)
Increase/decrease the current meandering spacing by one step.
int m_currentWidth
Meander settings.
int m_padToDieLength
Width of the meandered trace(s).
void cutTunedLine(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aTuneStart, const VECTOR2I &aCursorPos, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aTuned, SHAPE_LINE_CHAIN &aPost)
Extract the part of a track to be meandered, depending on the starting point and the cursor position.
MEANDER_SETTINGS m_settings
The current end point.
int compareWithTolerance(long long int aValue, long long int aExpected, long long int aTolerance=0) const
Compare aValue against aExpected with given tolerance.
virtual int Clearance()
Return the clearance of the track(s) being length tuned.
virtual const MEANDER_SETTINGS & MeanderSettings() const
Return the current meandering configuration.
NODE * m_world
Total length added by pad to die size.
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
long long int lineLength(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad) const
Calculate the total length of the line represented by an item set (tracks and vias)
int GetTotalPadToDieLength(const LINE &aLine) const
virtual void AmplitudeStep(int aSign)
Increase/decreases the current meandering amplitude by one step.
Dimensions for the meandering algorithm.
Definition: pns_meander.h:59
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:77
int m_step
Length PadToDie.
Definition: pns_meander.h:86
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:80
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:83
The geometry of a single meander.
Definition: pns_meander.h:111
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1069
virtual const ITEM_SET Traces()=0
Function Traces()
virtual int CurrentLayer() const =0
Function CurrentLayer()
virtual int StackupHeight(int aFirstLayer, int aSecondLayer) const =0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:208
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:170
virtual bool QueryConstraint(CONSTRAINT_TYPE aType, const PNS::ITEM *aItemA, const PNS::ITEM *aItemB, int aLayer, PNS::CONSTRAINT *aConstraint)=0
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
Push and Shove diff pair dimensions (gap) settings dialog.
MEANDER_TYPE
Shapes of available meanders.
Definition: pns_meander.h:37
@ MT_ARC
Definition: pns_meander.h:45
@ MT_START
Definition: pns_meander.h:39
@ MT_FINISH
Definition: pns_meander.h:40
@ MT_EMPTY
Definition: pns_meander.h:46
@ MT_CORNER
Definition: pns_meander.h:44
@ MT_SINGLE
Definition: pns_meander.h:38
MINOPTMAX< int > m_Value
Definition: pns_node.h:70
VECTOR2< int > VECTOR2I
Definition: vector2d.h:607