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 return m_settings;
257}
258
259
261{
262 if( aStartItem->Kind() == ITEM::SEGMENT_T )
263 {
264 return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
265 }
266 else
267 {
268 wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
269 ARC* arc = static_cast<ARC*>( aStartItem );
270
271 if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
272 ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
273 {
274 return arc->Anchor( 0 );
275 }
276 else
277 {
278 return arc->Anchor( 1 );
279 }
280 }
281}
282
283
284long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine, const SOLID* aStartPad, const SOLID* aEndPad ) const
285{
286 if( aLine.Empty() )
287 return 0;
288
289 ROUTER_IFACE* iface = Router()->GetInterface();
290 return iface->CalculateRoutedPathLength( aLine, aStartPad, aEndPad, m_settings.m_netClass );
291}
292
293
294int64_t MEANDER_PLACER_BASE::lineDelay( const ITEM_SET& aLine, const SOLID* aStartPad, const SOLID* aEndPad ) const
295{
296 if( aLine.Empty() )
297 return 0;
298
299 ROUTER_IFACE* iface = Router()->GetInterface();
300 return iface->CalculateRoutedPathDelay( aLine, aStartPad, aEndPad, m_settings.m_netClass );
301}
302}
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
virtual VECTOR2I Anchor(int n) const override
Definition: pns_arc.h:100
bool Empty() const
Definition: pns_itemset.h:82
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:173
@ SEGMENT_T
Definition: pns_item.h:107
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:447
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:550
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.
int64_t lineDelay(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad) const
Calculate the total delay of the line represented by an item set (tracks and vias)
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)
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:93
int m_step
Length PadToDie.
Definition: pns_meander.h:102
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:96
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:99
The geometry of a single meander.
Definition: pns_meander.h:150
int Amplitude() const
Definition: pns_meander.h:209
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
virtual const ITEM_SET Traces()=0
Function Traces()
virtual int CurrentLayer() const =0
Function CurrentLayer()
virtual long long int CalculateRoutedPathLength(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad, const NETCLASS *aNetClass)=0
virtual int64_t CalculateRoutedPathDelay(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad, const NETCLASS *aNetClass)=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:232
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:194
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:393
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