KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 The 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
33 PLACEMENT_ALGO( aRouter )
34{
35 m_world = nullptr;
37 m_startPad_n = nullptr;
38 m_startPad_p = nullptr;
39 m_endPad_n = nullptr;
40 m_endPad_p = nullptr;
41}
42
43
45{
46}
47
48
50{
52 a = std::max( a, m_settings.m_minAmplitude );
53
55}
56
57
59{
60 int s = m_settings.m_spacing + aSign * m_settings.m_step;
61 s = std::max( s, m_currentWidth + Clearance() );
62
64}
65
66
68{
69 // Assumption: All tracks are part of the same net class.
70 // It shouldn't matter which track we pick. They should all have the same clearance if
71 // they are part of the same net class. Therefore, pick the first one on the list.
72 ITEM* itemToCheck = Traces().CItems().front();
73 PNS::CONSTRAINT constraint;
74
76 nullptr, CurrentLayer(), &constraint );
77
78 wxCHECK_MSG( constraint.m_Value.HasMin(), m_currentWidth, wxT( "No minimum clearance?" ) );
79
80 return constraint.m_Value.Min();
81}
82
83
85{
86 m_settings = aSettings;
87}
88
89
90int findAmplitudeBinarySearch( MEANDER_SHAPE& aCopy, int targetLength, int minAmp, int maxAmp )
91{
92 if( minAmp == maxAmp )
93 return maxAmp;
94
95 aCopy.Resize( minAmp );
96 int minLen = aCopy.CurrentLength();
97
98 aCopy.Resize( maxAmp );
99 int maxLen = aCopy.CurrentLength();
100
101 if( minLen > targetLength )
102 return 0;
103
104 if( maxLen < targetLength )
105 return 0;
106
107 int minError = minLen - targetLength;
108 int maxError = maxLen - targetLength;
109
110 if( std::abs( minError ) < LENGTH_TARGET_TOLERANCE
111 || std::abs( maxError ) < LENGTH_TARGET_TOLERANCE )
112 {
113 return std::abs( minError ) < std::abs( maxError ) ? minAmp : maxAmp;
114 }
115 else
116 {
117 int left =
118 findAmplitudeBinarySearch( aCopy, targetLength, minAmp, ( minAmp + maxAmp ) / 2 );
119
120 if( left )
121 return left;
122
123 int right =
124 findAmplitudeBinarySearch( aCopy, targetLength, ( minAmp + maxAmp ) / 2, maxAmp );
125
126 if( right )
127 return right;
128 }
129
130 return 0;
131}
132
133
134int findAmplitudeForLength( MEANDER_SHAPE* m, int targetLength, int minAmp, int maxAmp )
135{
136 MEANDER_SHAPE copy = *m;
137
138 // Try to keep the same baseline length
139 copy.SetTargetBaselineLength( m->BaselineLength() );
140
141 long long initialGuess = m->Amplitude() - ( m->CurrentLength() - targetLength ) / 2;
142
143 if( initialGuess >= minAmp && initialGuess <= maxAmp )
144 {
145 copy.Resize( minAmp );
146
147 if( std::abs( copy.CurrentLength() - targetLength ) < LENGTH_TARGET_TOLERANCE )
148 return initialGuess;
149 }
150
151 // The length is non-trivial, use binary search
152 return findAmplitudeBinarySearch( copy, targetLength, minAmp, maxAmp );
153}
154
155
156void MEANDER_PLACER_BASE::tuneLineLength( MEANDERED_LINE& aTuned, long long int aElongation )
157{
158 long long int maxElongation = 0;
159 long long int minElongation = 0;
160 bool finished = false;
161
162 for( MEANDER_SHAPE* m : aTuned.Meanders() )
163 {
164 if( m->Type() != MT_CORNER && m->Type() != MT_ARC )
165 {
166 MEANDER_SHAPE end = *m;
167 MEANDER_TYPE endType;
168
169 if( m->Type() == MT_START || m->Type() == MT_SINGLE )
170 endType = MT_SINGLE;
171 else
172 endType = MT_FINISH;
173
174 end.SetType( endType );
175 end.Recalculate();
176
177 long long int maxEndElongation = end.CurrentLength() - end.BaselineLength();
178
179 if( maxElongation + maxEndElongation > aElongation )
180 {
181 if( !finished )
182 {
183 m->SetType( endType );
184 m->Recalculate();
185
186 if( endType == MT_SINGLE )
187 {
188 // Check if we need to fit this meander
189 long long int endMinElongation =
190 ( m->MinTunableLength() - m->BaselineLength() );
191
192 if( minElongation + endMinElongation >= aElongation )
193 m->MakeEmpty();
194 }
195
196 finished = true;
197 }
198 else
199 {
200 m->MakeEmpty();
201 }
202 }
203
204 maxElongation += m->CurrentLength() - m->BaselineLength();
205 minElongation += m->MinTunableLength() - m->BaselineLength();
206 }
207 }
208
209 long long int remainingElongation = aElongation;
210 int meanderCount = 0;
211
212 for( MEANDER_SHAPE* m : aTuned.Meanders() )
213 {
214 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
215 {
216 remainingElongation -= m->CurrentLength() - m->BaselineLength();
217 meanderCount++;
218 }
219 }
220
221 long long int lenReductionLeft = -remainingElongation;
222 int meandersLeft = meanderCount;
223
224 if( lenReductionLeft < 0 || !meandersLeft )
225 return;
226
227 for( MEANDER_SHAPE* m : aTuned.Meanders() )
228 {
229 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
230 {
231 long long int lenReductionHere = lenReductionLeft / meandersLeft;
232 long long int initialLen = m->CurrentLength();
233 int minAmpl = m->MinAmplitude();
234
235 int amp = findAmplitudeForLength( m, initialLen - lenReductionHere, minAmpl,
236 m->Amplitude() );
237
238 if( amp < minAmpl )
239 amp = minAmpl;
240
241 m->SetTargetBaselineLength( m->BaselineLength() );
242 m->Resize( amp );
243
244 lenReductionLeft -= initialLen - m->CurrentLength();
245 meandersLeft--;
246
247 if( !meandersLeft )
248 break;
249 }
250 }
251}
252
253
255{
256 int length = 0;
257 JOINT start;
258 JOINT end;
259
260 m_world->FindLineEnds( aLine, start, end );
261
262 // Extract the length of the pad to die for start and end pads
263 for( auto& link : start.LinkList() )
264 {
265 if( const SOLID* solid = dyn_cast<const SOLID*>( link ) )
266 {
267 // If there are overlapping pads, choose the first with a non-zero length
268 if( solid->GetPadToDie() > 0 )
269 {
270 length += solid->GetPadToDie();
271 break;
272 }
273 }
274 }
275
276 for( auto& link : end.LinkList() )
277 {
278 if( const SOLID* solid = dyn_cast<const SOLID*>( link ) )
279 {
280 if( solid->GetPadToDie() > 0 )
281 {
282 length += solid->GetPadToDie();
283 break;
284 }
285 }
286 }
287
288 return length;
289}
290
291
293{
294 return m_settings;
295}
296
297
299{
300 if( aStartItem->Kind() == ITEM::SEGMENT_T )
301 {
302 return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
303 }
304 else
305 {
306 wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
307 ARC* arc = static_cast<ARC*>( aStartItem );
308
309 if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
310 ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
311 {
312 return arc->Anchor( 0 );
313 }
314 else
315 {
316 return arc->Anchor( 1 );
317 }
318 }
319}
320
321
322long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine, const SOLID* aStartPad, const SOLID* aEndPad ) const
323{
324 long long int total = 0;
325
326 if( aLine.Empty() )
327 return 0;
328
329 const ITEM* start_item = aLine[0];
330 const ITEM* end_item = aLine[aLine.Size() - 1];
331 bool start_via = false;
332 bool end_via = false;
333
334
340 start_via = aStartPad && ( !aStartPad->LayersOverlap( start_item ) );
341 end_via = aEndPad && ( !aEndPad->LayersOverlap( end_item ) );
342
343 for( int idx = 0; idx < aLine.Size(); idx++ )
344 {
345 const ITEM* item = aLine[idx];
346
347 if( const LINE* l = dyn_cast<const LINE*>( item ) )
348 {
349 total += l->CLine().Length();
350 }
351 else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
352 {
353 int layerPrev = aLine[idx - 1]->Layer();
354 int layerNext = aLine[idx + 1]->Layer();
355
356 if( layerPrev != layerNext )
357 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
358 }
359 }
360
361 if( start_via )
362 {
363 int layerPrev = aStartPad->Layer();
364 int layerNext = start_item->Layer();
365
366 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
367 }
368
369 if( end_via )
370 {
371 int layerPrev = end_item->Layer();
372 int layerNext = aEndPad->Layer();
373
374 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
375 }
376
377 return total;
378}
379
380}
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:100
bool Empty() const
Definition: pns_itemset.h:82
int Size() const
Definition: pns_itemset.h:112
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:98
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:171
virtual int Layer() const
Definition: pns_item.h:204
@ SEGMENT_T
Definition: pns_item.h:107
bool OfKind(int aKindMask) const
Definition: pns_item.h:179
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:209
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 std::vector< ITEM * > & LinkList() const
Definition: pns_joint.h:303
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:62
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:425
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:528
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.
MEANDER_SETTINGS m_settings
The current end point.
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
Width of the meandered trace(s).
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:68
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:83
int m_step
Length PadToDie.
Definition: pns_meander.h:92
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:86
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:89
The geometry of a single meander.
Definition: pns_meander.h:128
int Amplitude() const
Definition: pns_meander.h:187
long long int CurrentLength() const
void Resize(int aAmpl)
Change the amplitude of the meander shape to aAmpl and recalculates the resulting line chain.
int BaselineLength() const
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1133
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:223
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:185
virtual bool QueryConstraint(CONSTRAINT_TYPE aType, const ITEM *aItemA, const ITEM *aItemB, int aLayer, CONSTRAINT *aConstraint)=0
Push and Shove diff pair dimensions (gap) settings dialog.
MEANDER_TYPE
Shapes of available meanders.
Definition: pns_meander.h:38
@ MT_ARC
Definition: pns_meander.h:46
@ MT_START
Definition: pns_meander.h:40
@ MT_FINISH
Definition: pns_meander.h:41
@ MT_EMPTY
Definition: pns_meander.h:47
@ MT_CORNER
Definition: pns_meander.h:45
@ MT_SINGLE
Definition: pns_meander.h:39
int findAmplitudeForLength(MEANDER_SHAPE *m, int targetLength, int minAmp, int maxAmp)
const int LENGTH_TARGET_TOLERANCE
int findAmplitudeBinarySearch(MEANDER_SHAPE &aCopy, int targetLength, int minAmp, int maxAmp)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
An abstract function object, returning a design rule (clearance, diff pair gap, etc) required between...
Definition: pns_node.h:73
MINOPTMAX< int > m_Value
Definition: pns_node.h:75
VECTOR2I end
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695