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 <boost/optional.hpp>
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 
36 using boost::optional;
37 
39  MEANDER_PLACER_BASE( aRouter )
40 {
41  m_world = NULL;
42  m_currentNode = NULL;
43 
44  // Init temporary variables (do not leave uninitialized members)
45  m_initialSegment = NULL;
46  m_lastLength = 0;
48 }
49 
50 
52 {
53 }
54 
55 
57 {
58  return m_currentTraceP;
59 }
60 
61 
62 NODE* DP_MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
63 {
64  if( !m_currentNode )
65  return m_world;
66 
67  return m_currentNode;
68 }
69 
70 
71 bool DP_MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
72 {
73  VECTOR2I p;
74 
75  if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T ) )
76  {
77  Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
78  return false;
79  }
80 
81  m_initialSegment = static_cast<SEGMENT*>( aStartItem );
82 
83  p = m_initialSegment->Seg().NearestPoint( aP );
84 
85  m_currentNode=NULL;
86  m_currentStart = p;
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 belonging "
96  "to a differential pair end with either _N/_P or +/-." ) );
97  return false;
98  }
99 
100  if( m_originPair.Gap() < 0 )
101  m_originPair.SetGap( Router()->Sizes().DiffPairGap() );
102 
103  if( !m_originPair.PLine().SegmentCount() ||
105  return false;
106 
109 
112 
114 
115  return true;
116 }
117 
118 
120 {
121 }
122 
123 
125 {
126  int totalP = 0;
127  int totalN = 0;
128 
129  for( const ITEM* item : m_tunedPathP.CItems() )
130  {
131  if( const LINE* l = dyn_cast<const LINE*>( item ) )
132  totalP += l->CLine().Length();
133 
134  }
135 
136  for( const ITEM* item : m_tunedPathN.CItems() )
137  {
138  if( const LINE* l = dyn_cast<const LINE*>( item ) )
139  totalN += l->CLine().Length();
140  }
141 
142  return std::max( totalP, totalN );
143 }
144 
145 
147 {
148  const VECTOR2I a( ( aCoupledSegs.coupledP.A + aCoupledSegs.coupledN.A ) / 2 );
149  const VECTOR2I b( ( aCoupledSegs.coupledP.B + aCoupledSegs.coupledN.B ) / 2 );
150 
151  return SEG( a, b );
152 }
153 
154 
155 static bool pairOrientation( const DIFF_PAIR::COUPLED_SEGMENTS& aPair )
156 {
157  VECTOR2I midp = ( aPair.coupledP.A + aPair.coupledN.A ) / 2;
158 
159  //DrawDebugPoint(midp, 6);
160 
161  return aPair.coupledP.Side( midp ) > 0;
162 }
163 
164 
165 bool DP_MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
166 {
167 // return false;
168 
169  DIFF_PAIR::COUPLED_SEGMENTS_VEC coupledSegments;
170 
171  if( m_currentNode )
172  delete m_currentNode;
173 
175 
176  SHAPE_LINE_CHAIN preP, tunedP, postP;
177  SHAPE_LINE_CHAIN preN, tunedN, postN;
178 
179  cutTunedLine( m_originPair.CP(), m_currentStart, aP, preP, tunedP, postP );
180  cutTunedLine( m_originPair.CN(), m_currentStart, aP, preN, tunedN, postN );
181 
182  DIFF_PAIR tuned( m_originPair );
183 
184  tuned.SetShape( tunedP, tunedN );
185 
186  tuned.CoupledSegmentPairs( coupledSegments );
187 
188  if( coupledSegments.size() == 0 )
189  return false;
190 
191  //Router()->DisplayDebugLine( tuned.CP(), 5, 20000 );
192  //Router()->DisplayDebugLine( tuned.CN(), 4, 20000 );
193 
194  //Router()->DisplayDebugLine( m_originPair.CP(), 5, 20000 );
195  //Router()->DisplayDebugLine( m_originPair.CN(), 4, 20000 );
196 
197  m_result = MEANDERED_LINE( this, true );
198  m_result.SetWidth( tuned.Width() );
199 
200  int offset = ( tuned.Gap() + tuned.Width() ) / 2;
201 
202  if( !pairOrientation( coupledSegments[0] ) )
203  offset *= -1;
204 
205  m_result.SetBaselineOffset( offset );
206 
207  for( const ITEM* item : m_tunedPathP.CItems() )
208  {
209  if( const LINE* l = dyn_cast<const LINE*>( item ) )
210  Dbg()->AddLine( l->CLine(), 5, 10000 );
211  }
212 
213  for( const ITEM* item : m_tunedPathN.CItems() )
214  {
215  if( const LINE* l = dyn_cast<const LINE*>( item ) )
216  Dbg()->AddLine( l->CLine(), 5, 10000 );
217  }
218 
219  int curIndexP = 0, curIndexN = 0;
220 
221  for( const DIFF_PAIR::COUPLED_SEGMENTS& sp : coupledSegments )
222  {
223  SEG base = baselineSegment( sp );
224 
225  Dbg()->AddSegment( base, 3 );
226 
227  while( sp.indexP >= curIndexP )
228  {
229  m_result.AddCorner( tunedP.CPoint( curIndexP ), tunedN.CPoint( curIndexN ) );
230  curIndexP++;
231  }
232 
233  while( sp.indexN >= curIndexN )
234  {
235  m_result.AddCorner( tunedP.CPoint( sp.indexP ), tunedN.CPoint( curIndexN ) );
236  curIndexN++;
237  }
238 
239  m_result.MeanderSegment( base );
240  }
241 
242  while( curIndexP < tunedP.PointCount() )
243  m_result.AddCorner( tunedP.CPoint( curIndexP++ ), tunedN.CPoint( curIndexN ) );
244 
245  while( curIndexN < tunedN.PointCount() )
246  m_result.AddCorner( tunedP.CPoint( -1 ), tunedN.CPoint( curIndexN++ ) );
247 
248  int dpLen = origPathLength();
249 
251 
253  {
255  m_lastLength = dpLen;
256  }
257  else
258  {
259  m_lastLength = dpLen - std::max( tunedP.Length(), tunedN.Length() );
261  }
262 
263  if( m_lastStatus != TOO_LONG )
264  {
265  tunedP.Clear();
266  tunedN.Clear();
267 
268  for( MEANDER_SHAPE* m : m_result.Meanders() )
269  {
270  if( m->Type() != MT_EMPTY )
271  {
272  tunedP.Append( m->CLine( 0 ) );
273  tunedN.Append( m->CLine( 1 ) );
274  }
275  }
276 
277  m_lastLength += std::max( tunedP.Length(), tunedN.Length() );
278 
280 
281  if( comp > 0 )
283  else if( comp < 0 )
285  else
287  }
288 
290  m_finalShapeP.Append( preP );
291  m_finalShapeP.Append( tunedP );
292  m_finalShapeP.Append( postP );
294 
296  m_finalShapeN.Append( preN );
297  m_finalShapeN.Append( tunedN );
298  m_finalShapeN.Append( postN );
300 
301  return true;
302 }
303 
304 
305 bool DP_MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
306 {
309 
310  m_currentNode->Add( lP );
311  m_currentNode->Add( lN );
312 
314 
315  return true;
316 }
317 
318 
320 {
321  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
322  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
323 
324  if( m_currentNode->CheckColliding( &l1 ) )
325  return false;
326 
327  if( m_currentNode->CheckColliding( &l2 ) )
328  return false;
329 
330  int w = aShape->Width();
331  int clearance = w + m_settings.m_spacing;
332 
333  return m_result.CheckSelfIntersections( aShape, clearance );
334 }
335 
336 
338 {
341 
342  ITEM_SET traces;
343 
344  traces.Add( &m_currentTraceP );
345  traces.Add( &m_currentTraceN );
346 
347  return traces;
348 }
349 
350 
352 {
353  return m_currentEnd;
354 }
355 
356 
358 {
359  return m_initialSegment->Layers().Start();
360 }
361 
362 
363 const wxString DP_MEANDER_PLACER::TuningInfo() const
364 {
365  wxString status;
366 
367  switch( m_lastStatus )
368  {
369  case TOO_LONG:
370  status = _( "Too long: " );
371  break;
372  case TOO_SHORT:
373  status = _("Too short: " );
374  break;
375  case TUNED:
376  status = _( "Tuned: " );
377  break;
378  default:
379  return _( "?" );
380  }
381 
382  status += LengthDoubleToString( (double) m_lastLength, false );
383  status += "/";
384  status += LengthDoubleToString( (double) m_settings.m_targetLength, false );
385  status += " (gap: ";
386  status += LengthDoubleToString( (double) m_originPair.Gap(), false );
387  status += ")";
388 
389  return status;
390 }
391 
392 
394 {
395  return m_lastStatus;
396 }
397 
398 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
399 {
400  std::vector<int> rv;
401  rv.push_back( m_originPair.NetP() );
402  rv.push_back( m_originPair.NetN() );
403  return rv;
404 }
405 
406 }
Class ITEM.
Definition: pns_item.h:53
Class MEANDER_PLACER_BASE.
int NetP() const
int Width() const
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Function CheckSelfIntersections()
Class NODE.
Definition: pns_node.h:137
const ENTRIES & CItems() const
Definition: pns_itemset.h:138
const LAYER_RANGE & Layers() const
Function Layers()
Definition: pns_item.h:207
Class MEANDER_SETTINGS.
Definition: pns_meander.h:104
Implementation of conversion functions that require both schematic and board internal units...
const std::vector< int > CurrentNets() const override
Function CurrentNets()
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:123
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Function AddCorner()
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:70
const DIFF_PAIR AssembleDiffPair(SEGMENT *aStart)
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
NODE * m_world
pointer to world to search colliding items
const SHAPE_LINE_CHAIN & CN() const
VECTOR2I m_currentStart
current routing start point (end of tail, beginning of head)
SEGMENT * GetLink(int aIndex) const
Definition: pns_line.h:203
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:109
TUNING_STATUS
Result of the length tuning operation
NODE * GetWorld() const
Definition: pns_router.h:134
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()
void SetWidth(int aWidth)
Function SetWidth()
Definition: pns_meander.h:457
const wxString TuningInfo() const override
Function TuningInfo()
const SEG baselineSegment(const DIFF_PAIR::COUPLED_SEGMENTS &aCoupledSegs)
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
int NetN() const
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)
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)
virtual void AddSegment(SEG aS, int aColor)
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:129
int Gap() const
std::vector< MEANDER_SHAPE * > & Meanders()
Function Meanders()
Definition: pns_meander.h:483
void tuneLineLength(MEANDERED_LINE &aTuned, int aElongation)
Function tuneLineLength()
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:204
wxString LengthDoubleToString(double aValue, bool aConvertToMils)
Function LengthDoubleToString is a helper to convert the double length aValue to a string in inches...
Definition: base_units.cpp:122
bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem) override
Function FixRoute()
static bool pairOrientation(const DIFF_PAIR::COUPLED_SEGMENTS &aPair)
int Start() const
Definition: pns_layerset.h:83
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:49
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:729
Class MEANDERED_LINE.
Definition: pns_meander.h:395
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:355
Definition: seg.h:37
Class DIFF_PAIR.
int compareWithTolerance(int aValue, int aExpected, int aTolerance=0) const
Function compareWithTolerance()
TUNING_STATUS TuningStatus() const override
Function TuningStatus()
MEANDER_SETTINGS m_settings
meandering settings
int m_lengthTolerance
allowable tuning error
Definition: pns_meander.h:90
void CommitRouting(NODE *aNode)
Definition: pns_router.cpp:324
#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:427
VECTOR2I A
Definition: seg.h:47
void Clear()
Function Clear() Removes all points from the line chain.
const SEG & Seg() const
Definition: pns_segment.h:93
int m_targetLength
desired length of the tuned line/diff pair
Definition: pns_meander.h:84
int m_spacing
meandering period/spacing (see dialog picture for explanation)
Definition: pns_meander.h:80
int Width() const
Function Width()
Definition: pns_meander.h:305
bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
int CurrentLayer() const override
Function CurrentLayer()
DP_MEANDER_PLACER(ROUTER *aRouter)
Push and Shove diff pair dimensions (gap) settings dialog.
void SetBaselineOffset(int aOffset)
Function SetBaselineOffset()
Definition: pns_meander.h:473
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
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 SHAPE_LINE_CHAIN & CLine(int aShape) const
Function CLine()
Definition: pns_meander.h:241
const SHAPE_LINE_CHAIN & CP() const
VECTOR2I B
Definition: seg.h:48