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 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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 = NULL;
41 
42  m_padToDieP = 0;
43  m_padToDieN = 0;
44 
45  // Init temporary variables (do not leave uninitialized members)
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 belonging "
92  "to a differential pair end with either _N/_P or +/-." ) );
93  return false;
94  }
95 
96  if( m_originPair.Gap() < 0 )
97  m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
98 
99  if( !m_originPair.PLine().SegmentCount() ||
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 )
226  {
227  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
228  curIndexP++;
229  }
230 
231  while( sp.indexN >= curIndexN )
232  {
233  m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
234  curIndexN++;
235  }
236 
237  m_result.MeanderSegment( base );
238  }
239 
240  while( curIndexP < tunedP.PointCount() )
241  m_result.AddCorner( tunedP.CPoint( curIndexP++ ), tunedN.CPoint( curIndexN ) );
242 
243  while( curIndexN < tunedN.PointCount() )
244  m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN++ ) );
245 
246  long long int dpLen = origPathLength();
247 
249 
251  {
253  m_lastLength = dpLen;
254  }
255  else
256  {
257  m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
259  }
260 
261  if( m_lastStatus != TOO_LONG )
262  {
263  tunedP.Clear();
264  tunedN.Clear();
265 
266  for( MEANDER_SHAPE* m : m_result.Meanders() )
267  {
268  if( m->Type() != MT_EMPTY )
269  {
270  tunedP.Append( m->CLine( 0 ) );
271  tunedN.Append( m->CLine( 1 ) );
272  }
273  }
274 
275  m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
276 
278 
279  if( comp > 0 )
281  else if( comp < 0 )
283  else
285  }
286 
288  m_finalShapeP.Append( preP );
289  m_finalShapeP.Append( tunedP );
290  m_finalShapeP.Append( postP );
292 
294  m_finalShapeN.Append( preN );
295  m_finalShapeN.Append( tunedN );
296  m_finalShapeN.Append( postN );
298 
299  return true;
300 }
301 
302 
303 bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
304 {
307 
308  m_currentNode->Add( lP );
309  m_currentNode->Add( lN );
310 
311  CommitPlacement();
312 
313  return true;
314 }
315 
316 
318 {
320  return true;
321 }
322 
323 
325 {
326  return m_originPair.CP().SegmentCount() > 0 ||
327  m_originPair.CN().SegmentCount() > 0;
328 }
329 
330 
332 {
333  if( m_currentNode )
335 
337  return true;
338 }
339 
340 
342 {
343  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
344  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
345 
346  if( m_currentNode->CheckColliding( &l1 ) )
347  return false;
348 
349  if( m_currentNode->CheckColliding( &l2 ) )
350  return false;
351 
352  int w = aShape->Width();
353  int clearance = w + m_settings.m_spacing;
354 
355  return m_result.CheckSelfIntersections( aShape, clearance );
356 }
357 
358 
360 {
363 
364  ITEM_SET traces;
365 
366  traces.Add( &m_currentTraceP );
367  traces.Add( &m_currentTraceN );
368 
369  return traces;
370 }
371 
372 
374 {
375  return m_currentEnd;
376 }
377 
378 
380 {
381  return m_initialSegment->Layers().Start();
382 }
383 
384 
385 const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
386 {
387  wxString status;
388 
389  switch( m_lastStatus )
390  {
391  case TOO_LONG:
392  status = _( "Too long: " );
393  break;
394  case TOO_SHORT:
395  status = _("Too short: " );
396  break;
397  case TUNED:
398  status = _( "Tuned: " );
399  break;
400  default:
401  return _( "?" );
402  }
403 
404  status += ::MessageTextFromValue( aUnits, m_lastLength );
405  status += "/";
406  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength );
407  status += " (gap: ";
408  status += ::MessageTextFromValue( aUnits, m_originPair.Gap() );
409  status += ")";
410 
411  return status;
412 }
413 
414 
416 {
417  return m_lastStatus;
418 }
419 
420 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
421 {
422  std::vector<int> rv;
423  rv.push_back( m_originPair.NetP() );
424  rv.push_back( m_originPair.NetN() );
425  return rv;
426 }
427 
428 }
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:103
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:144
The geometry of a single meander.
Definition: pns_meander.h:100
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)
Function Simplify()
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:694
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
int Width() const
const SHAPE_LINE_CHAIN & CN() const
void MeanderSegment(const SEG &aSeg, int aBaseIndex=0)
Fit maximum amplitude meanders on a given segment and adds to the current line.
Definition: pns_meander.cpp:45
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:263
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:127
TUNING_STATUS
< Result of the length tuning operation
int m_currentWidth
Meander settings.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
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:810
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:420
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:1369
#define NULL
int GetPadToDie() const
Definition: pns_solid.h:104
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:442
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:213
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:205
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
Function SegmentCount()
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:366
Definition: seg.h:40
EDA_UNITS
Definition: eda_units.h:38
DIFF_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.
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:92
SHAPE_LINE_CHAIN.
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:433
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:136
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:86
const ENTRIES & CItems() const
Definition: pns_itemset.h:139
void Clear()
Function Clear() Removes all points from the line chain.
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:80
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:434
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:621
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:152
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