KiCad PCB EDA Suite
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 <core/optional.h>
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"
29 #include "pns_dp_meander_placer.h"
30 #include "pns_diff_pair.h"
31 #include "pns_router.h"
32 #include "pns_solid.h"
33 
34 namespace 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 
63 NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
64 {
65  if( !m_currentNode )
66  return m_world;
67 
68  return m_currentNode;
69 }
70 
71 
72 bool 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 
103  SOLID* padA = nullptr;
104  SOLID* padB = nullptr;
105 
106  m_tunedPathP = topo.AssembleTuningPath( m_originPair.PLine().GetLink( 0 ), &padA, &padB );
107 
108  m_padToDieP = 0;
109 
110  if( padA )
111  m_padToDieP += padA->GetPadToDie();
112 
113  if( padB )
114  m_padToDieP += padB->GetPadToDie();
115 
116  m_tunedPathN = topo.AssembleTuningPath( m_originPair.NLine().GetLink( 0 ), &padA, &padB );
117 
118  m_padToDieN = 0;
119 
120  if( padA )
121  m_padToDieN += padA->GetPadToDie();
122 
123  if( padB )
124  m_padToDieN += padB->GetPadToDie();
125 
127 
130 
132 
133  return true;
134 }
135 
136 
138 {
139 }
140 
141 
143 {
144  long long int totalP = m_padToDieLength + lineLength( m_tunedPathP );
145  long long int totalN = m_padToDieLength + lineLength( m_tunedPathN );
146  return std::max( totalP, totalN );
147 }
148 
149 
151 {
152  const VECTOR2I a( ( aCoupledSegs.coupledP.A + aCoupledSegs.coupledN.A ) / 2 );
153  const VECTOR2I b( ( aCoupledSegs.coupledP.B + aCoupledSegs.coupledN.B ) / 2 );
154 
155  return SEG( a, b );
156 }
157 
158 
160 {
161  VECTOR2I midp = ( aPair.coupledP.A + aPair.coupledN.A ) / 2;
162 
163  //DrawDebugPoint(midp, 6);
164 
165  return aPair.coupledP.Side( midp ) > 0;
166 }
167 
168 
169 bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
170 {
171 // return false;
172 
173  DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
174 
175  if( m_currentNode )
176  delete m_currentNode;
177 
179 
180  SHAPE_LINE_CHAIN preP, tunedP, postP;
181  SHAPE_LINE_CHAIN preN, tunedN, postN;
182 
183  cutTunedLine( m_originPair.CP(), m_currentStart, aP, preP, tunedP, postP );
184  cutTunedLine( m_originPair.CN(), m_currentStart, aP, preN, tunedN, postN );
185 
186  DIFF_PAIR tuned( m_originPair );
187 
188  tuned.SetShape( tunedP, tunedN );
189 
190  tuned.CoupledSegmentPairs( coupledSegments );
191 
192  if( coupledSegments.size() == 0 )
193  return false;
194 
195  m_result = MEANDERED_LINE( this, true );
196  m_result.SetWidth( tuned.Width() );
197 
198  int offset = ( tuned.Gap() + tuned.Width() ) / 2;
199 
200  if( pairOrientation( coupledSegments[0] ) )
201  offset *= -1;
202 
203  m_result.SetBaselineOffset( offset );
204 
205  for( const ITEM* item : m_tunedPathP.CItems() )
206  {
207  if( const LINE* l = dyn_cast<const LINE*>( item ) )
208  PNS_DBG( Dbg(), AddLine, l->CLine(), YELLOW, 10000, "tuned-path-p" );
209  }
210 
211  for( const ITEM* item : m_tunedPathN.CItems() )
212  {
213  if( const LINE* l = dyn_cast<const LINE*>( item ) )
214  PNS_DBG( Dbg(), AddLine, l->CLine(), YELLOW, 10000, "tuned-path-n" );
215  }
216 
217  int curIndexP = 0, curIndexN = 0;
218 
219  for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
220  {
221  SEG base = baselineSegment( sp );
222 
223  PNS_DBG( Dbg(), AddSegment, base, GREEN, "dp-baseline" );
224 
225  while( sp.indexP >= curIndexP && curIndexP != -1 )
226  {
227  if( tunedP.IsArcSegment( curIndexP ) )
228  {
229  ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
230 
231  m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
232  }
233  else
234  {
235  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
236  }
237 
238  curIndexP = tunedP.NextShape( curIndexP );
239  }
240 
241  while( sp.indexN >= curIndexN && curIndexN != -1 )
242  {
243  if( tunedN.IsArcSegment( curIndexN ) )
244  {
245  ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
246 
247  m_result.AddPtAndArc( tunedP.CPoint( sp.indexP ), tunedN.Arc( arcIndex ) );
248  }
249  else
250  {
251  m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
252  }
253 
254  curIndexN = tunedN.NextShape( curIndexN );
255  }
256 
257  m_result.MeanderSegment( base, base.Side( aP ) < 0 );
258  }
259 
260  while( curIndexP < tunedP.PointCount() && curIndexP != -1 )
261  {
262  if( tunedP.IsArcSegment( curIndexP ) )
263  {
264  ssize_t arcIndex = tunedP.ArcIndex( curIndexP );
265 
266  m_result.AddArcAndPt( tunedP.Arc( arcIndex ), tunedN.CPoint( curIndexN ) );
267  }
268  else
269  {
270  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
271  }
272 
273  curIndexP = tunedP.NextShape( curIndexP );
274  }
275 
276  while( curIndexN < tunedN.PointCount() && curIndexN != -1 )
277  {
278  if( tunedN.IsArcSegment( curIndexN ) )
279  {
280  ssize_t arcIndex = tunedN.ArcIndex( curIndexN );
281 
282  m_result.AddPtAndArc( tunedP.CPoint( -1 ), tunedN.Arc( arcIndex ) );
283  }
284  else
285  {
286  m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN ) );
287  }
288 
289  curIndexN = tunedN.NextShape( curIndexN );
290  }
291 
292  long long int dpLen = origPathLength();
293 
295 
297  {
299  m_lastLength = dpLen;
300  }
301  else
302  {
303  m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
305  }
306 
307  if( m_lastStatus != TOO_LONG )
308  {
309  tunedP.Clear();
310  tunedN.Clear();
311 
312  for( MEANDER_SHAPE* m : m_result.Meanders() )
313  {
314  if( m->Type() != MT_EMPTY )
315  {
316  tunedP.Append( m->CLine( 0 ) );
317  tunedN.Append( m->CLine( 1 ) );
318  }
319  }
320 
321  m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
322 
325 
326  if( comp > 0 )
328  else if( comp < 0 )
330  else
332  }
333 
335  m_finalShapeP.Append( preP );
336  m_finalShapeP.Append( tunedP );
337  m_finalShapeP.Append( postP );
339 
341  m_finalShapeN.Append( preN );
342  m_finalShapeN.Append( tunedN );
343  m_finalShapeN.Append( postN );
345 
346  return true;
347 }
348 
349 
350 bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
351 {
354 
355  m_currentNode->Add( lP );
356  m_currentNode->Add( lN );
357 
358  CommitPlacement();
359 
360  return true;
361 }
362 
363 
365 {
367  return true;
368 }
369 
370 
372 {
373  return m_originPair.CP().SegmentCount() > 0 || m_originPair.CN().SegmentCount() > 0;
374 }
375 
376 
378 {
379  if( m_currentNode )
381 
382  m_currentNode = nullptr;
383  return true;
384 }
385 
386 
388 {
389  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
390  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
391 
392  if( m_currentNode->CheckColliding( &l1 ) )
393  return false;
394 
395  if( m_currentNode->CheckColliding( &l2 ) )
396  return false;
397 
398  int w = aShape->Width();
399  int clearance = w + m_settings.m_spacing;
400 
401  return m_result.CheckSelfIntersections( aShape, clearance );
402 }
403 
404 
406 {
409 
410  ITEM_SET traces;
411 
412  traces.Add( &m_currentTraceP );
413  traces.Add( &m_currentTraceN );
414 
415  return traces;
416 }
417 
418 
420 {
421  return m_currentEnd;
422 }
423 
424 
426 {
427  return m_initialSegment->Layers().Start();
428 }
429 
430 
431 const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
432 {
433  wxString status;
434 
435  switch( m_lastStatus )
436  {
437  case TOO_LONG:
438  status = _( "Too long: " );
439  break;
440  case TOO_SHORT:
441  status = _("Too short: " );
442  break;
443  case TUNED:
444  status = _( "Tuned: " );
445  break;
446  default:
447  return _( "?" );
448  }
449 
450  status += ::MessageTextFromValue( aUnits, m_lastLength );
451  status += "/";
452  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength );
453  status += " (gap: ";
454  status += ::MessageTextFromValue( aUnits, m_originPair.Gap() );
455  status += ")";
456 
457  return status;
458 }
459 
460 
462 {
463  return m_lastStatus;
464 }
465 
466 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
467 {
468  std::vector<int> rv;
469  rv.push_back( m_originPair.NetP() );
470  rv.push_back( m_originPair.NetN() );
471  return rv;
472 }
473 
474 }
Base class for PNS router board items.
Definition: pns_item.h:55
Base class for Single trace & Differential pair meandering tools, as both of them share a lot of code...
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
wxString MessageTextFromValue(EDA_UNITS aUnits, int aValue, bool aAddUnitLabel, EDA_DATA_TYPE aType)
Convert a value to a string using double notation.
Definition: base_units.cpp:104
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...
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Check if the given shape is intersecting with any other meander in the current line.
Keep the router "world" - i.e.
Definition: pns_node.h:146
The geometry of a single meander.
Definition: pns_meander.h:110
Implementation of conversion functions that require both schematic and board internal units.
int Gap() const
int SegmentCount() const
Definition: pns_line.h:139
const std::vector< int > CurrentNets() const override
Function CurrentNets()
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Create a dummy meander shape representing a line corner.
void CommitRouting()
Definition: pns_router.cpp:707
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
int Width() const
const SHAPE_LINE_CHAIN & CN() const
void AddPtAndArc(const VECTOR2I &aPt1, const SHAPE_ARC &aArc2)
Create a dummy meander shape representing an arc corner.
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...
int Width() const
Definition: pns_meander.h:282
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
VECTOR2I m_currentStart
Current world state.
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
TUNING_STATUS
< Result of the length tuning operation
void AddArcAndPt(const SHAPE_ARC &aArc1, const VECTOR2I &aPt2)
Create a dummy meander shape representing an arc corner.
int m_currentWidth
Meander settings.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Start routing a single track at point aP, taking item aStartItem as anchor (unless NULL).
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
bool CheckFit(MEANDER_SHAPE *aShape) override
Checks if it's OK to place the shape aShape (i.e.
int Start() const
Definition: pns_layerset.h:82
void SetWidth(int aWidth)
Set the line width.
Definition: pns_meander.h:466
int NetP() const
bool pairOrientation(const DIFF_PAIR::COUPLED_SEGMENTS &aPair)
const SEG baselineSegment(const DIFF_PAIR::COUPLED_SEGMENTS &aCoupledSegs)
const ITEM_SET Traces() override
Function Traces()
Definition: color4d.h:67
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
int m_padToDieLength
Width of the meandered trace(s).
void SetGap(int aGap)
std::vector< COUPLED_SEGMENTS > COUPLED_SEGMENTS_VEC
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Return the most recent world state.
long long int origPathLength() const
Current routing start point (end of tail, beginning of head).
void KillChildren()
Definition: pns_node.cpp:1405
int GetPadToDie() const
Definition: pns_solid.h:104
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:489
Definition: color4d.h:57
long long int lineLength(const ITEM_SET &aLine) const
Calculate the total length of the line represented by an item set (tracks and vias)
NODE * m_world
Total length added by pad to die size.
#define PNS_DBG(dbg, method,...)
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:232
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:202
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...
#define _(s)
int SegmentCount() const
Return the number of segments in this line chain.
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:385
Definition: seg.h:40
EDA_UNITS
Definition: eda_units.h:38
Basic class for a differential pair.
const SHAPE_LINE_CHAIN & CP() const
const wxString TuningInfo(EDA_UNITS aUnits) const override
Return a string describing the status and length of the tuned traces.
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
TUNING_STATUS TuningStatus() const override
Return the tuning status (too short, too long, etc.) of the trace(s) being tuned.
MEANDER_SETTINGS m_settings
The current end point.
int m_lengthTolerance
Target skew value for diff pair de-skewing.
Definition: pns_meander.h:101
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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:450
int compareWithTolerance(long long int aValue, long long int aExpected, long long int aTolerance=0) const
Compare aValue against aExpected with given tolerance.
VECTOR2I A
Definition: seg.h:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:138
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:92
const ENTRIES & CItems() const
Definition: pns_itemset.h:136
void Clear()
Remove all points from the line chain.
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:83
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).
int CurrentLayer() const override
Function CurrentLayer()
int NetN() const
DP_MEANDER_PLACER(ROUTER *aRouter)
bool HasPlacedAnything() const override
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * GetWorld() const
Definition: pns_router.h:153
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:481
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
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.
const LAYER_RANGE & Layers() const
Definition: pns_item.h:154
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
VECTOR2I B
Definition: seg.h:49