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 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
22#include <optional>
23
24#include "pns_node.h"
25#include "pns_itemset.h"
26#include "pns_topology.h"
28#include "pns_diff_pair.h"
29#include "pns_router.h"
30#include "pns_solid.h"
31
32namespace PNS {
33
35 MEANDER_PLACER_BASE( aRouter )
36{
37 m_world = nullptr;
38 m_currentNode = nullptr;
39
40 m_padToDieP = 0;
41 m_padToDieN = 0;
42
43 // Init temporary variables (do not leave uninitialized members)
44 m_initialSegment = nullptr;
45 m_lastLength = 0;
47}
48
49
51{
52}
53
54
56{
57 return m_currentTraceP;
58}
59
60
62{
63 return m_originPair;
64}
65
66
67NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
68{
69 if( !m_currentNode )
70 return m_world;
71
72 return m_currentNode;
73}
74
75
76bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
77{
78 if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
79 {
80 Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
81 return false;
82 }
83
84 m_initialSegment = static_cast<LINKED_ITEM*>( aStartItem );
85 m_currentNode = nullptr;
87
88 m_world = Router()->GetWorld()->Branch();
89
90 TOPOLOGY topo( m_world );
91
93 {
94 Router()->SetFailureReason( _( "Unable to find complementary differential pair "
95 "net for length tuning. Make sure the names of the nets "
96 "belonging to a differential pair end with either _N/_P "
97 "or +/-." ) );
98 return false;
99 }
100
101 if( m_originPair.Gap() < 0 )
102 m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
103
105 return false;
106
107 m_tunedPathP = topo.AssembleTuningPath( Router()->GetInterface(), m_originPair.PLine().GetLink( 0 ), &m_startPad_p,
108 &m_endPad_p );
109
110 m_padToDieP = 0;
111
112 if( m_startPad_p )
114
115 if( m_endPad_p )
117
118 m_tunedPathN = topo.AssembleTuningPath( Router()->GetInterface(), m_originPair.NLine().GetLink( 0 ), &m_startPad_n,
119 &m_endPad_n );
120
121 m_padToDieN = 0;
122
123 if( m_startPad_n )
125
126 if( m_endPad_n )
128
131
133
134 return true;
135}
136
137
139{
140}
141
142
144{
145 long long int totalP = m_padToDieP + lineLength( m_tunedPathP, m_startPad_p, m_endPad_p );
146 long long int totalN = m_padToDieN + lineLength( m_tunedPathN, m_startPad_n, m_endPad_n );
147 return std::max( totalP, totalN );
148}
149
150
152{
153 const VECTOR2I a( ( aCoupledSegs.coupledP.A + aCoupledSegs.coupledN.A ) / 2 );
154 const VECTOR2I b( ( aCoupledSegs.coupledP.B + aCoupledSegs.coupledN.B ) / 2 );
155
156 return SEG( a, b );
157}
158
159
161{
162 VECTOR2I midp = ( aPair.coupledP.A + aPair.coupledN.A ) / 2;
163
164 //DrawDebugPoint(midp, 6);
165
166 return aPair.coupledP.Side( midp ) > 0;
167}
168
169
170bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
171{
172 if( m_currentStart == aP )
173 return false;
174
175 DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
176
177 if( m_currentNode )
178 delete m_currentNode;
179
181
182 SHAPE_LINE_CHAIN preP, tunedP, postP;
183 SHAPE_LINE_CHAIN preN, tunedN, postN;
184
185 m_originPair.CP().Split( m_currentStart, aP, preP, tunedP, postP );
186 m_originPair.CN().Split( m_currentStart, aP, preN, tunedN, postN );
187
188 auto updateStatus =
189 [&]()
190 {
195 else
197 };
198
199 DIFF_PAIR tuned( m_originPair );
200
201 tuned.SetShape( tunedP, tunedN );
202
203 tuned.CoupledSegmentPairs( coupledSegments );
204
205 if( coupledSegments.size() == 0 )
206 {
207 // Tuning started at an uncoupled area of the DP; we won't get a valid result until the
208 // cursor is moved far enough along a coupled area. Prevent the track from disappearing and
209 // the length from being zero by just using the original.
213 updateStatus();
214
215 return false;
216 }
217
218 m_result = MEANDERED_LINE( this, true );
219 m_result.SetWidth( tuned.Width() );
220
221 int offset = ( tuned.Gap() + tuned.Width() ) / 2;
222
223 if( pairOrientation( coupledSegments[0] ) )
224 offset *= -1;
225
226 m_result.SetBaselineOffset( offset );
227
228 for( const ITEM* item : m_tunedPathP.CItems() )
229 {
230 if( const LINE* l = dyn_cast<const LINE*>( item ) )
231 {
232 PNS_DBG( Dbg(), AddShape, &l->CLine(), YELLOW, 10000, wxT( "tuned-path-p" ) );
233
234 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
235 }
236 }
237
238 for( const ITEM* item : m_tunedPathN.CItems() )
239 {
240 if( const LINE* l = dyn_cast<const LINE*>( item ) )
241 {
242 PNS_DBG( Dbg(), AddShape, &l->CLine(), YELLOW, 10000, wxT( "tuned-path-n" ) );
243
244 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
245 }
246 }
247
248 int curIndexP = 0, curIndexN = 0;
249
250 for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
251 {
252 SEG base = baselineSegment( sp );
253 bool side = false;
254
255 if( m_settings.m_initialSide == 0 )
256 side = base.Side( aP ) < 0;
257 else
258 side = m_settings.m_initialSide < 0;
259
260 PNS_DBG( Dbg(), AddShape, base, GREEN, 10000, wxT( "dp-baseline" ) );
261
262 while( sp.indexP >= curIndexP && curIndexP != -1 )
263 {
264 if( tunedP.IsArcSegment( curIndexP ) )
265 {
266 ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
267
268 m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
269 }
270 else
271 {
272 m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
273 }
274
275 curIndexP = tunedP.NextShape( curIndexP );
276 }
277
278 while( sp.indexN >= curIndexN && curIndexN != -1 )
279 {
280 if( tunedN.IsArcSegment( curIndexN ) )
281 {
282 ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
283
284 m_result.AddPtAndArc( tunedP.CPoint( sp.indexP ), tunedN.Arc( arcIndex ) );
285 }
286 else
287 {
288 m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
289 }
290
291 curIndexN = tunedN.NextShape( curIndexN );
292 }
293
294 m_result.MeanderSegment( base, side );
295 }
296
297 while( curIndexP < tunedP.PointCount() && curIndexP != -1 )
298 {
299 if( tunedP.IsArcSegment( curIndexP ) )
300 {
301 ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
302
303 m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
304 }
305 else
306 {
307 m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
308 }
309
310 curIndexP = tunedP.NextShape( curIndexP );
311 }
312
313 while( curIndexN < tunedN.PointCount() && curIndexN != -1 )
314 {
315 if( tunedN.IsArcSegment( curIndexN ) )
316 {
317 ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
318
319 m_result.AddPtAndArc( tunedP.CPoint( -1 ), tunedN.Arc( arcIndex ) );
320 }
321 else
322 {
323 m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN ) );
324 }
325
326 curIndexN = tunedN.NextShape( curIndexN );
327 }
328
329 m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( -1 ) );
330
331 long long int dpLen = origPathLength();
332
334
335 if( dpLen > m_settings.m_targetLength.Max() )
336 {
338 m_lastLength = dpLen;
339 }
340 else
341 {
342 m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
344 }
345
346 if( m_lastStatus != TOO_LONG )
347 {
348 tunedP.Clear();
349 tunedN.Clear();
350
351 for( MEANDER_SHAPE* m : m_result.Meanders() )
352 {
353 if( m->Type() != MT_EMPTY )
354 {
355 tunedP.Append( m->CLine( 0 ) );
356 tunedN.Append( m->CLine( 1 ) );
357 }
358 }
359
360 m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
361 updateStatus();
362 }
363
366
368 {
369 preP.Simplify();
370 tunedP.Simplify();
371 postP.Simplify();
372
373 m_finalShapeP.Append( preP );
374 m_finalShapeP.Append( tunedP );
375 m_finalShapeP.Append( postP );
376
377 preN.Simplify();
378 tunedN.Simplify();
379 postN.Simplify();
380
381 m_finalShapeN.Append( preN );
382 m_finalShapeN.Append( tunedN );
383 m_finalShapeN.Append( postN );
384 }
385 else
386 {
387 m_finalShapeP.Append( preP );
388 m_finalShapeP.Append( tunedP );
389 m_finalShapeP.Append( postP );
391
392 m_finalShapeN.Append( preN );
393 m_finalShapeN.Append( tunedN );
394 m_finalShapeN.Append( postN );
396 }
397
398 return true;
399}
400
401
402bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
403{
406
407 m_currentNode->Add( lP );
408 m_currentNode->Add( lN );
409
411
412 return true;
413}
414
415
417{
419 return true;
420}
421
422
424{
425 return m_originPair.CP().SegmentCount() > 0 || m_originPair.CN().SegmentCount() > 0;
426}
427
428
430{
431 if( m_currentNode )
433
434 m_currentNode = nullptr;
435 return true;
436}
437
438
440{
441 LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
442 LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
443
444 if( m_currentNode->CheckColliding( &l1 ) )
445 return false;
446
447 if( m_currentNode->CheckColliding( &l2 ) )
448 return false;
449
450 int w = aShape->Width();
451 int clearance = w + w * 3;
452
453 return m_result.CheckSelfIntersections( aShape, clearance );
454}
455
456
458{
461
462 ITEM_SET traces;
463
464 traces.Add( &m_currentTraceP );
465 traces.Add( &m_currentTraceN );
466
467 return traces;
468}
469
470
472{
473 ITEM_SET lines;
474
475 for( ITEM* item : m_tunedPathN )
476 lines.Add( item );
477
478 for( ITEM* item : m_tunedPathP )
479 lines.Add( item );
480
481 return lines;
482}
483
484
486{
487 return m_currentStart;
488}
489
490
492{
493 return m_currentEnd;
494}
495
496
498{
499 return m_initialSegment->Layers().Start();
500}
501
502
504{
505 if( m_lastLength )
506 return m_lastLength;
507 else
508 return origPathLength();
509}
510
511
513{
514 return m_lastStatus;
515}
516
517
518const std::vector<NET_HANDLE> DP_MEANDER_PLACER::CurrentNets() const
519{
520 std::vector<NET_HANDLE> rv;
521 rv.push_back( m_originPair.NetP() );
522 rv.push_back( m_originPair.NetN() );
523 return rv;
524}
525
526}
T Min() const
Definition: minoptmax.h:33
T Max() const
Definition: minoptmax.h:34
T Opt() const
Definition: minoptmax.h:35
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
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
int Gap() const
NET_HANDLE NetP() const
void SetGap(int aGap)
const SHAPE_LINE_CHAIN & CP() const
void CoupledSegmentPairs(COUPLED_SEGMENTS_VEC &aPairs) const
NET_HANDLE NetN() 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)
long long int TuningResult() const override
Return the resultant length or skew of the tuned traces.
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 DIFF_PAIR & GetOriginPair()
const ITEM_SET TunedPath() override
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).
const std::vector< NET_HANDLE > CurrentNets() const override
Function CurrentNets()
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:33
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:98
const PNS_LAYER_RANGE & Layers() const
Definition: pns_item.h:212
@ SEGMENT_T
Definition: pns_item.h:107
bool OfKind(int aKindMask) const
Definition: pns_item.h:181
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:62
int SegmentCount() const
Definition: pns_line.h:140
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:425
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:520
void SetWidth(int aWidth)
Set the line width.
Definition: pns_meander.h:505
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.
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:528
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.
MEANDER_SETTINGS m_settings
The current end point.
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)
MEANDER_SIDE m_initialSide
Allowable tuning error.
Definition: pns_meander.h:115
MINOPTMAX< long long int > m_targetLength
Target skew value for diff pair de-skewing.
Definition: pns_meander.h:98
The geometry of a single meander.
Definition: pns_meander.h:128
int Width() const
Definition: pns_meander.h:310
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:250
Keep the router "world" - i.e.
Definition: pns_node.h:231
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:143
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:410
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:665
void KillChildren()
Definition: pns_node.cpp:1546
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:909
virtual void DisplayPathLine(const SHAPE_LINE_CHAIN &aLine, int aImportance)=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:223
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:218
void CommitRouting()
Definition: pns_router.cpp:921
NODE * GetWorld() const
Definition: pns_router.h:169
int GetPadToDie() const
Definition: pns_solid.h:116
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
const ITEM_SET AssembleTuningPath(ROUTER_IFACE *aRouterIface, ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
int Start() const
Definition: pns_layerset.h:86
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
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
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:57
@ YELLOW
Definition: color4d.h:67
#define _(s)
Push and Shove diff pair dimensions (gap) settings dialog.
@ MT_EMPTY
Definition: pns_meander.h:47
#define PNS_DBG(dbg, method,...)
int clearance