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 (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
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:97
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:167
virtual int Layer() const
Definition: pns_item.h:200
@ SEGMENT_T
Definition: pns_item.h:106
bool OfKind(int aKindMask) const
Definition: pns_item.h:175
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:205
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:273
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: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
void SetType(MEANDER_TYPE aType)
Set the type of the meander.
Definition: pns_meander.h:155
long long int CurrentLength() const
void Recalculate()
Recalculate the line chain representing the meander's shape.
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:1103
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
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:691