KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_dp_meander_placer.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 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
22#include <optional>
23
24#include <base_units.h> // God forgive me doing this...
25
26#include "pns_node.h"
27#include "pns_itemset.h"
28#include "pns_topology.h"
30#include "pns_diff_pair.h"
31#include "pns_router.h"
32#include "pns_solid.h"
33
34namespace PNS {
35
37 MEANDER_PLACER_BASE( aRouter )
38{
39 m_world = nullptr;
40 m_currentNode = nullptr;
41
42 m_padToDieP = 0;
43 m_padToDieN = 0;
44
45 // Init temporary variables (do not leave uninitialized members)
46 m_initialSegment = nullptr;
47 m_lastLength = 0;
49}
50
51
53{
54}
55
56
58{
59 return m_currentTraceP;
60}
61
62
63NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
64{
65 if( !m_currentNode )
66 return m_world;
67
68 return m_currentNode;
69}
70
71
72bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
73{
74 if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
75 {
76 Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
77 return false;
78 }
79
80 m_initialSegment = static_cast<LINKED_ITEM*>( aStartItem );
81 m_currentNode = nullptr;
83
84 m_world = Router()->GetWorld()->Branch();
85
86 TOPOLOGY topo( m_world );
87
89 {
90 Router()->SetFailureReason( _( "Unable to find complementary differential pair "
91 "net for length tuning. Make sure the names of the nets "
92 "belonging to a differential pair end with either _N/_P "
93 "or +/-." ) );
94 return false;
95 }
96
97 if( m_originPair.Gap() < 0 )
98 m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
99
101 return false;
102
104
105 m_padToDieP = 0;
106
107 if( m_startPad_p )
109
110 if( m_endPad_p )
112
114
115 m_padToDieN = 0;
116
117 if( m_startPad_n )
119
120 if( m_endPad_n )
122
125
127
128 return true;
129}
130
131
133{
134}
135
136
138{
139 long long int totalP = m_padToDieP + lineLength( m_tunedPathP, m_startPad_p, m_endPad_p );
140 long long int totalN = m_padToDieN + lineLength( m_tunedPathN, m_startPad_n, m_endPad_n );
141 return std::max( totalP, totalN );
142}
143
144
146{
147 const VECTOR2I a( ( aCoupledSegs.coupledP.A + aCoupledSegs.coupledN.A ) / 2 );
148 const VECTOR2I b( ( aCoupledSegs.coupledP.B + aCoupledSegs.coupledN.B ) / 2 );
149
150 return SEG( a, b );
151}
152
153
155{
156 VECTOR2I midp = ( aPair.coupledP.A + aPair.coupledN.A ) / 2;
157
158 //DrawDebugPoint(midp, 6);
159
160 return aPair.coupledP.Side( midp ) > 0;
161}
162
163
164bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
165{
166// return false;
167
168 DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
169
170 if( m_currentNode )
171 delete m_currentNode;
172
174
175 SHAPE_LINE_CHAIN preP, tunedP, postP;
176 SHAPE_LINE_CHAIN preN, tunedN, postN;
177
178 cutTunedLine( m_originPair.CP(), m_currentStart, aP, preP, tunedP, postP );
179 cutTunedLine( m_originPair.CN(), m_currentStart, aP, preN, tunedN, postN );
180
181 auto updateStatus =
182 [&]()
183 {
186
187 if( comp > 0 )
189 else if( comp < 0 )
191 else
193 };
194
195 DIFF_PAIR tuned( m_originPair );
196
197 tuned.SetShape( tunedP, tunedN );
198
199 tuned.CoupledSegmentPairs( coupledSegments );
200
201 if( coupledSegments.size() == 0 )
202 {
203 // Tuning started at an uncoupled area of the DP; we won't get a valid result until the
204 // cursor is moved far enough along a coupled area. Prevent the track from disappearing and
205 // the length from being zero by just using the original.
209 updateStatus();
210
211 return false;
212 }
213
214 m_result = MEANDERED_LINE( this, true );
215 m_result.SetWidth( tuned.Width() );
216
217 int offset = ( tuned.Gap() + tuned.Width() ) / 2;
218
219 if( pairOrientation( coupledSegments[0] ) )
220 offset *= -1;
221
222 m_result.SetBaselineOffset( offset );
223
224 for( const ITEM* item : m_tunedPathP.CItems() )
225 {
226 if( const LINE* l = dyn_cast<const LINE*>( item ) )
227 {
228 PNS_DBG( Dbg(), AddShape, &l->CLine(), YELLOW, 10000, wxT( "tuned-path-p" ) );
229
230 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
231 }
232 }
233
234 for( const ITEM* item : m_tunedPathN.CItems() )
235 {
236 if( const LINE* l = dyn_cast<const LINE*>( item ) )
237 {
238 PNS_DBG( Dbg(), AddShape, &l->CLine(), YELLOW, 10000, wxT( "tuned-path-n" ) );
239
240 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
241 }
242 }
243
244 int curIndexP = 0, curIndexN = 0;
245
246 for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
247 {
248 SEG base = baselineSegment( sp );
249
250 PNS_DBG( Dbg(), AddShape, base, GREEN, 10000, wxT( "dp-baseline" ) );
251
252 while( sp.indexP >= curIndexP && curIndexP != -1 )
253 {
254 if( tunedP.IsArcSegment( curIndexP ) )
255 {
256 ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
257
258 m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
259 }
260 else
261 {
262 m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
263 }
264
265 curIndexP = tunedP.NextShape( curIndexP );
266 }
267
268 while( sp.indexN >= curIndexN && curIndexN != -1 )
269 {
270 if( tunedN.IsArcSegment( curIndexN ) )
271 {
272 ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
273
274 m_result.AddPtAndArc( tunedP.CPoint( sp.indexP ), tunedN.Arc( arcIndex ) );
275 }
276 else
277 {
278 m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
279 }
280
281 curIndexN = tunedN.NextShape( curIndexN );
282 }
283
284 m_result.MeanderSegment( base, base.Side( aP ) < 0 );
285 }
286
287 while( curIndexP < tunedP.PointCount() && curIndexP != -1 )
288 {
289 if( tunedP.IsArcSegment( curIndexP ) )
290 {
291 ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
292
293 m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
294 }
295 else
296 {
297 m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
298 }
299
300 curIndexP = tunedP.NextShape( curIndexP );
301 }
302
303 while( curIndexN < tunedN.PointCount() && curIndexN != -1 )
304 {
305 if( tunedN.IsArcSegment( curIndexN ) )
306 {
307 ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
308
309 m_result.AddPtAndArc( tunedP.CPoint( -1 ), tunedN.Arc( arcIndex ) );
310 }
311 else
312 {
313 m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN ) );
314 }
315
316 curIndexN = tunedN.NextShape( curIndexN );
317 }
318
319 long long int dpLen = origPathLength();
320
322
324 {
326 m_lastLength = dpLen;
327 }
328 else
329 {
330 m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
332 }
333
334 if( m_lastStatus != TOO_LONG )
335 {
336 tunedP.Clear();
337 tunedN.Clear();
338
339 for( MEANDER_SHAPE* m : m_result.Meanders() )
340 {
341 if( m->Type() != MT_EMPTY )
342 {
343 tunedP.Append( m->CLine( 0 ) );
344 tunedN.Append( m->CLine( 1 ) );
345 }
346 }
347
348 m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
349 updateStatus();
350 }
351
353 m_finalShapeP.Append( preP );
354 m_finalShapeP.Append( tunedP );
355 m_finalShapeP.Append( postP );
357
359 m_finalShapeN.Append( preN );
360 m_finalShapeN.Append( tunedN );
361 m_finalShapeN.Append( postN );
363
364 return true;
365}
366
367
368bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
369{
372
373 m_currentNode->Add( lP );
374 m_currentNode->Add( lN );
375
377
378 return true;
379}
380
381
383{
385 return true;
386}
387
388
390{
391 return m_originPair.CP().SegmentCount() > 0 || m_originPair.CN().SegmentCount() > 0;
392}
393
394
396{
397 if( m_currentNode )
399
400 m_currentNode = nullptr;
401 return true;
402}
403
404
406{
407 LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
408 LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
409
410 if( m_currentNode->CheckColliding( &l1 ) )
411 return false;
412
413 if( m_currentNode->CheckColliding( &l2 ) )
414 return false;
415
416 int w = aShape->Width();
417 int clearance = w + m_settings.m_spacing;
418
419 return m_result.CheckSelfIntersections( aShape, clearance );
420}
421
422
424{
427
428 ITEM_SET traces;
429
430 traces.Add( &m_currentTraceP );
431 traces.Add( &m_currentTraceN );
432
433 return traces;
434}
435
436
438{
439 return m_currentStart;
440}
441
442
444{
445 return m_currentEnd;
446}
447
448
450{
451 return m_initialSegment->Layers().Start();
452}
453
454
455const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
456{
457 wxString status;
458
459 switch( m_lastStatus )
460 {
461 case TOO_LONG:
462 status = _( "Too long: " );
463 break;
464 case TOO_SHORT:
465 status = _("Too short: " );
466 break;
467 case TUNED:
468 status = _( "Tuned: " );
469 break;
470 default:
471 return _( "?" );
472 }
473
475 status += wxT( "/" );
477 status += wxT( " (gap: " );
479 status += wxT( ")" );
480
481 return status;
482}
483
484
486{
487 return m_lastStatus;
488}
489
490
491const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
492{
493 std::vector<int> rv;
494 rv.push_back( m_originPair.NetP() );
495 rv.push_back( m_originPair.NetN() );
496 return rv;
497}
498
499}
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
int Start() const
Definition: pns_layerset.h:82
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Basic class for a differential pair.
const SHAPE_LINE_CHAIN & CN() const
int Width() const
std::vector< COUPLED_SEGMENTS > COUPLED_SEGMENTS_VEC
int NetN() const
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
int Gap() const
int NetP() const
void SetGap(int aGap)
const SHAPE_LINE_CHAIN & CP() const
void CoupledSegmentPairs(COUPLED_SEGMENTS_VEC &aPairs) const
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
bool CheckFit(MEANDER_SHAPE *aShape) override
Checks if it's OK to place the shape aShape (i.e.
const ITEM_SET Traces() override
Function Traces()
bool pairOrientation(const DIFF_PAIR::COUPLED_SEGMENTS &aPair)
const std::vector< int > CurrentNets() const override
Function CurrentNets()
DP_MEANDER_PLACER(ROUTER *aRouter)
VECTOR2I m_currentStart
Current world state.
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Commit the currently routed track to the parent node, taking aP as the final end point and aEndItem a...
int CurrentLayer() const override
Function CurrentLayer()
TUNING_STATUS TuningStatus() const override
Return the tuning status (too short, too long, etc.) of the trace(s) being tuned.
const SEG baselineSegment(const DIFF_PAIR::COUPLED_SEGMENTS &aCoupledSegs)
const wxString TuningInfo(EDA_UNITS aUnits) const override
Return a string describing the status and length of the tuned traces.
bool HasPlacedAnything() const override
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Move the end of the currently routed trace to the point aP, taking aEndItem as anchor (if not NULL).
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
const VECTOR2I & CurrentStart() const override
Function CurrentStart()
long long int origPathLength() const
Current routing start point (end of tail, beginning of head).
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:91
@ SEGMENT_T
Definition: pns_item.h:101
const LAYER_RANGE & Layers() const
Definition: pns_item.h:191
bool OfKind(int aKindMask) const
Definition: pns_item.h:170
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
int SegmentCount() const
Definition: pns_line.h:138
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:412
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:507
void SetWidth(int aWidth)
Set the line width.
Definition: pns_meander.h:492
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Create a dummy meander shape representing a line corner.
void MeanderSegment(const SEG &aSeg, bool aSide, int aBaseIndex=0)
Fit maximum amplitude meanders on a given segment and adds to the current line.
Definition: pns_meander.cpp:45
void AddArcAndPt(const SHAPE_ARC &aArc1, const VECTOR2I &aPt2)
Create a dummy meander shape representing an arc corner.
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Check if the given shape is intersecting with any other meander in the current line.
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:515
void AddPtAndArc(const VECTOR2I &aPt1, const SHAPE_ARC &aArc2)
Create a dummy meander shape representing an arc corner.
Base class for Single trace & Differential pair meandering tools, as both of them share a lot of code...
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...
TUNING_STATUS
< Result of the length tuning operation
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.
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)
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:93
int m_lengthTolerance
Target skew value for diff pair de-skewing.
Definition: pns_meander.h:105
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:84
The geometry of a single meander.
Definition: pns_meander.h:115
int Width() const
Definition: pns_meander.h:297
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:237
Keep the router "world" - i.e.
Definition: pns_node.h:198
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:132
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:382
void KillChildren()
Definition: pns_node.cpp:1435
bool Add(std::unique_ptr< SEGMENT > &&aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:620
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
virtual void DisplayPathLine(const SHAPE_LINE_CHAIN &aLine, int aImportance)=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:210
void CommitRouting()
Definition: pns_router.cpp:906
NODE * GetWorld() const
Definition: pns_router.h:161
int GetPadToDie() const
Definition: pns_solid.h:105
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
const ITEM_SET AssembleTuningPath(ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
int PointCount() const
Return the number of points (vertices) in this line chain.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
bool IsArcSegment(size_t aSegment) const
long long int Length() const
Return length of the line chain in Euclidean metric.
@ GREEN
Definition: color4d.h:56
@ YELLOW
Definition: color4d.h:66
#define _(s)
EDA_UNITS
Definition: eda_units.h:43
wxString MessageTextFromValue(const EDA_IU_SCALE &aIuScale, EDA_UNITS aUnits, double aValue, bool aAddUnitsText=true, EDA_DATA_TYPE aType=EDA_DATA_TYPE::DISTANCE)
A helper to convert the double length aValue to a string in inches, millimeters, or unscaled units.
Definition: eda_units.cpp:315
Push and Shove diff pair dimensions (gap) settings dialog.
@ MT_EMPTY
Definition: pns_meander.h:46
#define PNS_DBG(dbg, method,...)