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-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().item;
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
90void MEANDER_PLACER_BASE::cutTunedLine( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aTuneStart,
91 const VECTOR2I& aCursorPos, SHAPE_LINE_CHAIN& aPre,
92 SHAPE_LINE_CHAIN& aTuned, SHAPE_LINE_CHAIN& aPost )
93{
94 VECTOR2I cp ( aCursorPos );
95
96 if( cp == aTuneStart ) // we don't like tuning segments with 0 length
97 {
98 int idx = aOrigin.FindSegment( cp );
99
100 if( idx >= 0 )
101 {
102 const SEG& s = aOrigin.CSegment( idx );
103 cp += ( s.B - s.A ).Resize( 2 );
104 }
105 else
106 {
107 cp += VECTOR2I( 2, 5 ); // some arbitrary value that is not 45 degrees oriented
108 }
109 }
110
111 VECTOR2I n = aOrigin.NearestPoint( cp, false );
112 VECTOR2I m = aOrigin.NearestPoint( aTuneStart, false );
113
114 SHAPE_LINE_CHAIN l( aOrigin );
115 l.Split( n );
116 l.Split( m );
117
118 int i_start = l.Find( m );
119 int i_end = l.Find( n );
120
121 if( i_start > i_end )
122 {
123 l = l.Reverse();
124 i_start = l.Find( m );
125 i_end = l.Find( n );
126 }
127
128 aPre = l.Slice( 0, i_start );
129 aPost = l.Slice( i_end, -1 );
130 aTuned = l.Slice( i_start, i_end );
131
132 aTuned.Simplify();
133}
134
135
136int findAmplitudeBinarySearch( MEANDER_SHAPE& aCopy, int targetLength, int minAmp, int maxAmp )
137{
138 if( minAmp == maxAmp )
139 return maxAmp;
140
141 aCopy.Resize( minAmp );
142 int minLen = aCopy.CurrentLength();
143
144 aCopy.Resize( maxAmp );
145 int maxLen = aCopy.CurrentLength();
146
147 if( minLen > targetLength )
148 return 0;
149
150 if( maxLen < targetLength )
151 return 0;
152
153 int minError = minLen - targetLength;
154 int maxError = maxLen - targetLength;
155
156 if( std::abs( minError ) < LENGTH_TARGET_TOLERANCE
157 || std::abs( maxError ) < LENGTH_TARGET_TOLERANCE )
158 {
159 return std::abs( minError ) < std::abs( maxError ) ? minAmp : maxAmp;
160 }
161 else
162 {
163 int left =
164 findAmplitudeBinarySearch( aCopy, targetLength, minAmp, ( minAmp + maxAmp ) / 2 );
165
166 if( left )
167 return left;
168
169 int right =
170 findAmplitudeBinarySearch( aCopy, targetLength, ( minAmp + maxAmp ) / 2, maxAmp );
171
172 if( right )
173 return right;
174 }
175
176 return 0;
177}
178
179
180int findAmplitudeForLength( MEANDER_SHAPE* m, int targetLength, int minAmp, int maxAmp )
181{
182 MEANDER_SHAPE copy = *m;
183
184 // Try to keep the same baseline length
185 copy.SetTargetBaselineLength( m->BaselineLength() );
186
187 long long initialGuess = m->Amplitude() - ( m->CurrentLength() - targetLength ) / 2;
188
189 if( initialGuess >= minAmp && initialGuess <= maxAmp )
190 {
191 copy.Resize( minAmp );
192
193 if( std::abs( copy.CurrentLength() - targetLength ) < LENGTH_TARGET_TOLERANCE )
194 return initialGuess;
195 }
196
197 // The length is non-trivial, use binary search
198 return findAmplitudeBinarySearch( copy, targetLength, minAmp, maxAmp );
199}
200
201
202void MEANDER_PLACER_BASE::tuneLineLength( MEANDERED_LINE& aTuned, long long int aElongation )
203{
204 long long int maxElongation = 0;
205 long long int minElongation = 0;
206 bool finished = false;
207
208 for( MEANDER_SHAPE* m : aTuned.Meanders() )
209 {
210 if( m->Type() != MT_CORNER && m->Type() != MT_ARC )
211 {
212 MEANDER_SHAPE end = *m;
213 MEANDER_TYPE endType;
214
215 if( m->Type() == MT_START || m->Type() == MT_SINGLE )
216 endType = MT_SINGLE;
217 else
218 endType = MT_FINISH;
219
220 end.SetType( endType );
221 end.Recalculate();
222
223 long long int maxEndElongation = end.CurrentLength() - end.BaselineLength();
224
225 if( maxElongation + maxEndElongation > aElongation )
226 {
227 if( !finished )
228 {
229 m->SetType( endType );
230 m->Recalculate();
231
232 if( endType == MT_SINGLE )
233 {
234 // Check if we need to fit this meander
235 long long int endMinElongation =
236 ( m->MinTunableLength() - m->BaselineLength() );
237
238 if( minElongation + endMinElongation >= aElongation )
239 m->MakeEmpty();
240 }
241
242 finished = true;
243 }
244 else
245 {
246 m->MakeEmpty();
247 }
248 }
249
250 maxElongation += m->CurrentLength() - m->BaselineLength();
251 minElongation += m->MinTunableLength() - m->BaselineLength();
252 }
253 }
254
255 long long int remainingElongation = aElongation;
256 int meanderCount = 0;
257
258 for( MEANDER_SHAPE* m : aTuned.Meanders() )
259 {
260 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
261 {
262 remainingElongation -= m->CurrentLength() - m->BaselineLength();
263 meanderCount++;
264 }
265 }
266
267 long long int lenReductionLeft = -remainingElongation;
268 int meandersLeft = meanderCount;
269
270 if( lenReductionLeft < 0 || !meandersLeft )
271 return;
272
273 for( MEANDER_SHAPE* m : aTuned.Meanders() )
274 {
275 if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
276 {
277 long long int lenReductionHere = lenReductionLeft / meandersLeft;
278 long long int initialLen = m->CurrentLength();
279 int minAmpl = m->MinAmplitude();
280
281 int amp = findAmplitudeForLength( m, initialLen - lenReductionHere, minAmpl,
282 m->Amplitude() );
283
284 if( amp < minAmpl )
285 amp = minAmpl;
286
287 m->SetTargetBaselineLength( m->BaselineLength() );
288 m->Resize( amp );
289
290 lenReductionLeft -= initialLen - m->CurrentLength();
291 meandersLeft--;
292
293 if( !meandersLeft )
294 break;
295 }
296 }
297}
298
299
301{
302 int length = 0;
303 JOINT start;
304 JOINT end;
305
306 m_world->FindLineEnds( aLine, start, end );
307
308 // Extract the length of the pad to die for start and end pads
309 for( auto& link : start.LinkList() )
310 {
311 if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
312 {
313 // If there are overlapping pads, choose the first with a non-zero length
314 if( solid->GetPadToDie() > 0 )
315 {
316 length += solid->GetPadToDie();
317 break;
318 }
319 }
320 }
321
322 for( auto& link : end.LinkList() )
323 {
324 if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
325 {
326 if( solid->GetPadToDie() > 0 )
327 {
328 length += solid->GetPadToDie();
329 break;
330 }
331 }
332 }
333
334 return length;
335}
336
337
339{
340 return m_settings;
341}
342
343
345 long long int aValue, long long int aExpected, long long int aTolerance ) const
346{
347 if( aValue < aExpected - aTolerance )
348 return -1;
349 else if( aValue > aExpected + aTolerance )
350 return 1;
351 else
352 return 0;
353}
354
355
357{
358 if( aStartItem->Kind() == ITEM::SEGMENT_T )
359 {
360 return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
361 }
362 else
363 {
364 wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
365 ARC* arc = static_cast<ARC*>( aStartItem );
366
367 if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
368 ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
369 {
370 return arc->Anchor( 0 );
371 }
372 else
373 {
374 return arc->Anchor( 1 );
375 }
376 }
377}
378
379
380long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine, const SOLID* aStartPad, const SOLID* aEndPad ) const
381{
382 long long int total = 0;
383
384 if( aLine.Empty() )
385 return 0;
386
387 const ITEM* start_item = aLine[0];
388 const ITEM* end_item = aLine[aLine.Size() - 1];
389 bool start_via = false;
390 bool end_via = false;
391
392
398 start_via = aStartPad && ( !aStartPad->LayersOverlap( start_item ) );
399 end_via = aEndPad && ( !aEndPad->LayersOverlap( end_item ) );
400
401 for( int idx = 0; idx < aLine.Size(); idx++ )
402 {
403 const ITEM* item = aLine[idx];
404
405 if( const LINE* l = dyn_cast<const LINE*>( item ) )
406 {
407 total += l->CLine().Length();
408 }
409 else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
410 {
411 int layerPrev = aLine[idx - 1]->Layer();
412 int layerNext = aLine[idx + 1]->Layer();
413
414 if( layerPrev != layerNext )
415 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
416 }
417 }
418
419 if( start_via )
420 {
421 int layerPrev = aStartPad->Layer();
422 int layerNext = start_item->Layer();
423
424 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
425 }
426
427 if( end_via )
428 {
429 int layerPrev = end_item->Layer();
430 int layerNext = aEndPad->Layer();
431
432 total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
433 }
434
435 return total;
436}
437
438}
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:132
virtual int Layer() const
Definition: pns_item.h:160
@ 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:140
bool LayersOverlap(const ITEM *aOther) const
Return true if the set of layers spanned by aOther overlaps our layers.
Definition: pns_item.h:165
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:412
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:515
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.
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
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:59
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:78
int m_step
Length PadToDie.
Definition: pns_meander.h:87
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:81
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:84
The geometry of a single meander.
Definition: pns_meander.h:115
int Amplitude() const
Definition: pns_meander.h:174
void SetType(MEANDER_TYPE aType)
Set the type of the meander.
Definition: pns_meander.h:142
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:1085
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:214
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:176
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
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:412
MINOPTMAX< int > m_Value
Definition: pns_node.h:70
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618