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_utils.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  VECTOR2I p;
75 
76  if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T ) )
77  {
78  Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
79  return false;
80  }
81 
82  m_initialSegment = static_cast<SEGMENT*>( aStartItem );
83 
84  p = m_initialSegment->Seg().NearestPoint( aP );
85 
87  m_currentStart = p;
88 
89  m_world = Router()->GetWorld()->Branch();
90 
91  TOPOLOGY topo( m_world );
92 
94  {
95  Router()->SetFailureReason( _( "Unable to find complementary differential pair "
96  "net for length tuning. Make sure the names of the nets belonging "
97  "to a differential pair end with either _N/_P or +/-." ) );
98  return false;
99  }
100 
101  if( m_originPair.Gap() < 0 )
102  m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
103 
104  if( !m_originPair.PLine().SegmentCount() ||
106  return false;
107 
110 
113  m_padToDieLenth = std::max( m_padToDieP, m_padToDieN );
114 
117 
119 
120  return true;
121 }
122 
123 
125 {
126 }
127 
128 
130 {
131  long long int totalP = m_padToDieLenth;
132  long long int totalN = m_padToDieLenth;
133 
134  for( const ITEM* item : m_tunedPathP.CItems() )
135  {
136  if( const LINE* l = dyn_cast<const LINE*>( item ) )
137  totalP += l->CLine().Length();
138 
139  }
140 
141  for( const ITEM* item : m_tunedPathN.CItems() )
142  {
143  if( const LINE* l = dyn_cast<const LINE*>( item ) )
144  totalN += l->CLine().Length();
145  }
146 
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 
170 bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
171 {
172 // return false;
173 
174  DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
175 
176  if( m_currentNode )
177  delete m_currentNode;
178 
180 
181  SHAPE_LINE_CHAIN preP, tunedP, postP;
182  SHAPE_LINE_CHAIN preN, tunedN, postN;
183 
184  cutTunedLine( m_originPair.CP(), m_currentStart, aP, preP, tunedP, postP );
185  cutTunedLine( m_originPair.CN(), m_currentStart, aP, preN, tunedN, postN );
186 
187  DIFF_PAIR tuned( m_originPair );
188 
189  tuned.SetShape( tunedP, tunedN );
190 
191  tuned.CoupledSegmentPairs( coupledSegments );
192 
193  if( coupledSegments.size() == 0 )
194  return false;
195 
196  //Router()->DisplayDebugLine( tuned.CP(), 5, 20000 );
197  //Router()->DisplayDebugLine( tuned.CN(), 4, 20000 );
198 
199  //Router()->DisplayDebugLine( m_originPair.CP(), 5, 20000 );
200  //Router()->DisplayDebugLine( m_originPair.CN(), 4, 20000 );
201 
202  m_result = MEANDERED_LINE( this, true );
203  m_result.SetWidth( tuned.Width() );
204 
205  int offset = ( tuned.Gap() + tuned.Width() ) / 2;
206 
207  if( pairOrientation( coupledSegments[0] ) )
208  offset *= -1;
209 
210  m_result.SetBaselineOffset( offset );
211 
212  for( const ITEM* item : m_tunedPathP.CItems() )
213  {
214  if( const LINE* l = dyn_cast<const LINE*>( item ) )
215  Dbg()->AddLine( l->CLine(), 5, 10000 );
216  }
217 
218  for( const ITEM* item : m_tunedPathN.CItems() )
219  {
220  if( const LINE* l = dyn_cast<const LINE*>( item ) )
221  Dbg()->AddLine( l->CLine(), 5, 10000 );
222  }
223 
224  int curIndexP = 0, curIndexN = 0;
225 
226  for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
227  {
228  SEG base = baselineSegment( sp );
229 
230  Dbg()->AddSegment( base, 3 );
231 
232  while( sp.indexP >= curIndexP )
233  {
234  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
235  curIndexP++;
236  }
237 
238  while( sp.indexN >= curIndexN )
239  {
240  m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
241  curIndexN++;
242  }
243 
244  m_result.MeanderSegment( base );
245  }
246 
247  while( curIndexP < tunedP.PointCount() )
248  m_result.AddCorner( tunedP.CPoint( curIndexP++ ), tunedN.CPoint( curIndexN ) );
249 
250  while( curIndexN < tunedN.PointCount() )
251  m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN++ ) );
252 
253  long long int dpLen = origPathLength();
254 
256 
258  {
260  m_lastLength = dpLen;
261  }
262  else
263  {
264  m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
266  }
267 
268  if( m_lastStatus != TOO_LONG )
269  {
270  tunedP.Clear();
271  tunedN.Clear();
272 
273  for( MEANDER_SHAPE* m : m_result.Meanders() )
274  {
275  if( m->Type() != MT_EMPTY )
276  {
277  tunedP.Append( m->CLine( 0 ) );
278  tunedN.Append( m->CLine( 1 ) );
279  }
280  }
281 
282  m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
283 
285 
286  if( comp > 0 )
288  else if( comp < 0 )
290  else
292  }
293 
295  m_finalShapeP.Append( preP );
296  m_finalShapeP.Append( tunedP );
297  m_finalShapeP.Append( postP );
299 
301  m_finalShapeN.Append( preN );
302  m_finalShapeN.Append( tunedN );
303  m_finalShapeN.Append( postN );
305 
306  return true;
307 }
308 
309 
310 bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
311 {
314 
315  m_currentNode->Add( lP );
316  m_currentNode->Add( lN );
317 
318  CommitPlacement();
319 
320  return true;
321 }
322 
323 
325 {
327  return true;
328 }
329 
330 
332 {
333  return m_originPair.CP().SegmentCount() > 0 ||
334  m_originPair.CN().SegmentCount() > 0;
335 }
336 
337 
339 {
340  if( m_currentNode )
342 
344  return true;
345 }
346 
347 
349 {
350  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
351  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
352 
353  if( m_currentNode->CheckColliding( &l1 ) )
354  return false;
355 
356  if( m_currentNode->CheckColliding( &l2 ) )
357  return false;
358 
359  int w = aShape->Width();
360  int clearance = w + m_settings.m_spacing;
361 
362  return m_result.CheckSelfIntersections( aShape, clearance );
363 }
364 
365 
367 {
370 
371  ITEM_SET traces;
372 
373  traces.Add( &m_currentTraceP );
374  traces.Add( &m_currentTraceN );
375 
376  return traces;
377 }
378 
379 
381 {
382  return m_currentEnd;
383 }
384 
385 
387 {
388  return m_initialSegment->Layers().Start();
389 }
390 
391 
392 const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
393 {
394  wxString status;
395 
396  switch( m_lastStatus )
397  {
398  case TOO_LONG:
399  status = _( "Too long: " );
400  break;
401  case TOO_SHORT:
402  status = _("Too short: " );
403  break;
404  case TUNED:
405  status = _( "Tuned: " );
406  break;
407  default:
408  return _( "?" );
409  }
410 
411  status += ::MessageTextFromValue( aUnits, m_lastLength, false );
412  status += "/";
413  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength, false );
414  status += " (gap: ";
415  status += ::MessageTextFromValue( aUnits, m_originPair.Gap(), false );
416  status += ")";
417 
418  return status;
419 }
420 
421 
423 {
424  return m_lastStatus;
425 }
426 
427 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
428 {
429  std::vector<int> rv;
430  rv.push_back( m_originPair.NetP() );
431  rv.push_back( m_originPair.NetN() );
432  return rv;
433 }
434 
435 }
EDA_UNITS
Definition: common.h:198
int GetTotalPadToDieLength(const LINE &aLine) const
ITEM.
Definition: pns_item.h:53
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Function FixRoute()
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Function CheckSelfIntersections()
NODE.
Definition: pns_node.h:145
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
MEANDER_SETTINGS.
Definition: pns_meander.h:107
Implementation of conversion functions that require both schematic and board internal units.
int Gap() const
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:155
const std::vector< int > CurrentNets() const override
Function CurrentNets()
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Function AddCorner()
void CommitRouting()
Definition: pns_router.cpp:443
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
int Width() const
const SHAPE_LINE_CHAIN & CN() const
NODE * m_currentNode
Current world state
void MeanderSegment(const SEG &aSeg, int aBaseIndex=0)
Function MeanderSegment()
Definition: pns_meander.cpp:46
VECTOR2I m_currentEnd
current end point
int Width() const
Function Width()
Definition: pns_meander.h:308
const SEG & Seg() const
Definition: pns_segment.h:83
VECTOR2I m_currentStart
current routing start point (end of tail, beginning of head)
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
TUNING_STATUS
Result of the length tuning operation
int m_currentWidth
width of the meandered trace(s)
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
bool CheckFit(MEANDER_SHAPE *aShape) override
Function CheckFit()
int Start() const
Definition: pns_layerset.h:83
void SetWidth(int aWidth)
Function SetWidth()
Definition: pns_meander.h:460
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()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
void SetGap(int aGap)
std::vector< COUPLED_SEGMENTS > COUPLED_SEGMENTS_VEC
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
long long int origPathLength() const
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1288
#define NULL
std::vector< MEANDER_SHAPE * > & Meanders()
Function Meanders()
Definition: pns_meander.h:486
NODE * m_world
pointer to world to search colliding items
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Function CLine()
Definition: pns_meander.h:244
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:228
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
void tuneLineLength(MEANDERED_LINE &aTuned, long long int aElongation)
Function tuneLineLength()
int SegmentCount() const
Function SegmentCount()
virtual void AddSegment(SEG aS, int aColor, const std::string aName="")
MEANDERED_LINE.
Definition: pns_meander.h:398
int m_padToDieLenth
total length added by pad to die size
Definition: seg.h:39
DIFF_PAIR.
wxString MessageTextFromValue(EDA_UNITS aUnits, int aValue, bool aUseMils, EDA_DATA_TYPE aType)
Definition: base_units.cpp:124
const SHAPE_LINE_CHAIN & CP() const
const wxString TuningInfo(EDA_UNITS aUnits) const override
Function TuningInfo()
TUNING_STATUS TuningStatus() const override
Function TuningStatus()
MEANDER_SETTINGS m_settings
meandering settings
int m_lengthTolerance
allowable tuning error
Definition: pns_meander.h:93
#define _(s)
Definition: 3d_actions.cpp:33
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
int compareWithTolerance(long long int aValue, long long int aExpected, long long int aTolerance=0) const
Function compareWithTolerance()
VECTOR2I A
Definition: seg.h:47
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:133
long long int m_targetLength
desired length of the tuned line/diff pair (this is in nm, so allow more than board width)
Definition: pns_meander.h:87
const ENTRIES & CItems() const
Definition: pns_itemset.h:141
void Clear()
Function Clear() Removes all points from the line chain.
int m_spacing
meandering period/spacing (see dialog picture for explanation)
Definition: pns_meander.h:81
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
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:154
void SetBaselineOffset(int aOffset)
Function SetBaselineOffset()
Definition: pns_meander.h:476
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
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)
Function cutTunedLine()
const LAYER_RANGE & Layers() const
Definition: pns_item.h:151
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:138
VECTOR2I B
Definition: seg.h:48