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;
40  m_currentNode = NULL;
41 
42  // Init temporary variables (do not leave uninitialized members)
43  m_initialSegment = NULL;
44  m_lastLength = 0;
46 }
47 
48 
50 {
51 }
52 
53 
55 {
56  return m_currentTraceP;
57 }
58 
59 
60 NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
61 {
62  if( !m_currentNode )
63  return m_world;
64 
65  return m_currentNode;
66 }
67 
68 
69 bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
70 {
71  VECTOR2I p;
72 
73  if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T ) )
74  {
75  Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
76  return false;
77  }
78 
79  m_initialSegment = static_cast<SEGMENT*>( aStartItem );
80 
81  p = m_initialSegment->Seg().NearestPoint( aP );
82 
83  m_currentNode=NULL;
84  m_currentStart = p;
85 
86  m_world = Router()->GetWorld()->Branch();
87 
88  TOPOLOGY topo( m_world );
89 
91  {
92  Router()->SetFailureReason( _( "Unable to find complementary differential pair "
93  "net for length tuning. Make sure the names of the nets belonging "
94  "to a differential pair end with either _N/_P or +/-." ) );
95  return false;
96  }
97 
98  if( m_originPair.Gap() < 0 )
99  m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
100 
101  if( !m_originPair.PLine().SegmentCount() ||
103  return false;
104 
107 
111 
114 
116 
117  return true;
118 }
119 
120 
122 {
123 }
124 
125 
127 {
128  long long int totalP = m_padToDieLenth;
129  long long int totalN = m_padToDieLenth;
130 
131  for( const ITEM* item : m_tunedPathP.CItems() )
132  {
133  if( const LINE* l = dyn_cast<const LINE*>( item ) )
134  totalP += l->CLine().Length();
135 
136  }
137 
138  for( const ITEM* item : m_tunedPathN.CItems() )
139  {
140  if( const LINE* l = dyn_cast<const LINE*>( item ) )
141  totalN += l->CLine().Length();
142  }
143 
144  return std::max( totalP, totalN );
145 }
146 
147 
149 {
150  const VECTOR2I a( ( aCoupledSegs.coupledP.A + aCoupledSegs.coupledN.A ) / 2 );
151  const VECTOR2I b( ( aCoupledSegs.coupledP.B + aCoupledSegs.coupledN.B ) / 2 );
152 
153  return SEG( a, b );
154 }
155 
156 
158 {
159  VECTOR2I midp = ( aPair.coupledP.A + aPair.coupledN.A ) / 2;
160 
161  //DrawDebugPoint(midp, 6);
162 
163  return aPair.coupledP.Side( midp ) > 0;
164 }
165 
166 
167 bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
168 {
169 // return false;
170 
171  DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
172 
173  if( m_currentNode )
174  delete m_currentNode;
175 
177 
178  SHAPE_LINE_CHAIN preP, tunedP, postP;
179  SHAPE_LINE_CHAIN preN, tunedN, postN;
180 
181  cutTunedLine( m_originPair.CP(), m_currentStart, aP, preP, tunedP, postP );
182  cutTunedLine( m_originPair.CN(), m_currentStart, aP, preN, tunedN, postN );
183 
184  DIFF_PAIR tuned( m_originPair );
185 
186  tuned.SetShape( tunedP, tunedN );
187 
188  tuned.CoupledSegmentPairs( coupledSegments );
189 
190  if( coupledSegments.size() == 0 )
191  return false;
192 
193  //Router()->DisplayDebugLine( tuned.CP(), 5, 20000 );
194  //Router()->DisplayDebugLine( tuned.CN(), 4, 20000 );
195 
196  //Router()->DisplayDebugLine( m_originPair.CP(), 5, 20000 );
197  //Router()->DisplayDebugLine( m_originPair.CN(), 4, 20000 );
198 
199  m_result = MEANDERED_LINE( this, true );
200  m_result.SetWidth( tuned.Width() );
201 
202  int offset = ( tuned.Gap() + tuned.Width() ) / 2;
203 
204  if( pairOrientation( coupledSegments[0] ) )
205  offset *= -1;
206 
207  m_result.SetBaselineOffset( offset );
208 
209  for( const ITEM* item : m_tunedPathP.CItems() )
210  {
211  if( const LINE* l = dyn_cast<const LINE*>( item ) )
212  Dbg()->AddLine( l->CLine(), 5, 10000 );
213  }
214 
215  for( const ITEM* item : m_tunedPathN.CItems() )
216  {
217  if( const LINE* l = dyn_cast<const LINE*>( item ) )
218  Dbg()->AddLine( l->CLine(), 5, 10000 );
219  }
220 
221  int curIndexP = 0, curIndexN = 0;
222 
223  for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
224  {
225  SEG base = baselineSegment( sp );
226 
227  Dbg()->AddSegment( base, 3 );
228 
229  while( sp.indexP >= curIndexP )
230  {
231  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
232  curIndexP++;
233  }
234 
235  while( sp.indexN >= curIndexN )
236  {
237  m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
238  curIndexN++;
239  }
240 
241  m_result.MeanderSegment( base );
242  }
243 
244  while( curIndexP < tunedP.PointCount() )
245  m_result.AddCorner( tunedP.CPoint( curIndexP++ ), tunedN.CPoint( curIndexN ) );
246 
247  while( curIndexN < tunedN.PointCount() )
248  m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN++ ) );
249 
250  long long int dpLen = origPathLength();
251 
253 
255  {
257  m_lastLength = dpLen;
258  }
259  else
260  {
261  m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
263  }
264 
265  if( m_lastStatus != TOO_LONG )
266  {
267  tunedP.Clear();
268  tunedN.Clear();
269 
270  for( MEANDER_SHAPE* m : m_result.Meanders() )
271  {
272  if( m->Type() != MT_EMPTY )
273  {
274  tunedP.Append( m->CLine( 0 ) );
275  tunedN.Append( m->CLine( 1 ) );
276  }
277  }
278 
279  m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
280 
282 
283  if( comp > 0 )
285  else if( comp < 0 )
287  else
289  }
290 
292  m_finalShapeP.Append( preP );
293  m_finalShapeP.Append( tunedP );
294  m_finalShapeP.Append( postP );
296 
298  m_finalShapeN.Append( preN );
299  m_finalShapeN.Append( tunedN );
300  m_finalShapeN.Append( postN );
302 
303  return true;
304 }
305 
306 
307 bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
308 {
311 
312  m_currentNode->Add( lP );
313  m_currentNode->Add( lN );
314 
316 
317  return true;
318 }
319 
320 
322 {
323  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
324  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
325 
326  if( m_currentNode->CheckColliding( &l1 ) )
327  return false;
328 
329  if( m_currentNode->CheckColliding( &l2 ) )
330  return false;
331 
332  int w = aShape->Width();
333  int clearance = w + m_settings.m_spacing;
334 
335  return m_result.CheckSelfIntersections( aShape, clearance );
336 }
337 
338 
340 {
343 
344  ITEM_SET traces;
345 
346  traces.Add( &m_currentTraceP );
347  traces.Add( &m_currentTraceN );
348 
349  return traces;
350 }
351 
352 
354 {
355  return m_currentEnd;
356 }
357 
358 
360 {
361  return m_initialSegment->Layers().Start();
362 }
363 
364 
365 const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS_T aUnits ) const
366 {
367  wxString status;
368 
369  switch( m_lastStatus )
370  {
371  case TOO_LONG:
372  status = _( "Too long: " );
373  break;
374  case TOO_SHORT:
375  status = _("Too short: " );
376  break;
377  case TUNED:
378  status = _( "Tuned: " );
379  break;
380  default:
381  return _( "?" );
382  }
383 
384  status += ::MessageTextFromValue( aUnits, m_lastLength, false );
385  status += "/";
386  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength, false );
387  status += " (gap: ";
388  status += ::MessageTextFromValue( aUnits, m_originPair.Gap(), false );
389  status += ")";
390 
391  return status;
392 }
393 
394 
396 {
397  return m_lastStatus;
398 }
399 
400 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
401 {
402  std::vector<int> rv;
403  rv.push_back( m_originPair.NetP() );
404  rv.push_back( m_originPair.NetN() );
405  return rv;
406 }
407 
408 }
int GetTotalPadToDieLength(const LINE &aLine) const
Class ITEM.
Definition: pns_item.h:53
Class MEANDER_PLACER_BASE.
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:49
SEGMENT * GetLink(int aIndex) const
Definition: pns_line.h:219
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Function FixRoute()
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Function CheckSelfIntersections()
Class NODE.
Definition: pns_node.h:140
Class 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:145
const std::vector< int > CurrentNets() const override
Function CurrentNets()
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Function AddCorner()
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:93
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:104
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()
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)
wxString MessageTextFromValue(EDA_UNITS_T aUnits, int aValue, bool aUseMils)
Definition: base_units.cpp:125
const ITEM_SET Traces() override
Function Traces()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0)
const wxString TuningInfo(EDA_UNITS_T aUnits) const override
Function TuningInfo()
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
virtual void AddSegment(SEG aS, int aColor)
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:70
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:216
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:374
void tuneLineLength(MEANDERED_LINE &aTuned, long long int aElongation)
Function tuneLineLength()
#define _(s)
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:715
Class MEANDERED_LINE.
Definition: pns_meander.h:398
int m_padToDieLenth
total length added by pad to die size
Definition: seg.h:36
Class DIFF_PAIR.
const SHAPE_LINE_CHAIN & CP() const
TUNING_STATUS TuningStatus() const override
Function TuningStatus()
MEANDER_SETTINGS m_settings
meandering settings
int m_lengthTolerance
allowable tuning error
Definition: pns_meander.h:93
void CommitRouting(NODE *aNode)
Definition: pns_router.cpp:356
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:421
int compareWithTolerance(long long int aValue, long long int aExpected, long long int aTolerance=0) const
Function compareWithTolerance()
VECTOR2I A
Definition: seg.h:44
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:132
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)
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * GetWorld() const
Definition: pns_router.h:146
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:590
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()
EDA_UNITS_T
Definition: common.h:133
const LAYER_RANGE & Layers() const
Definition: pns_item.h:150
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:130
VECTOR2I B
Definition: seg.h:45