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  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 
105 
108  m_padToDieLenth = std::max( m_padToDieP, m_padToDieN );
109 
112 
114 
115  return true;
116 }
117 
118 
120 {
121 }
122 
123 
125 {
126  long long int totalP = m_padToDieLenth;
127  long long int totalN = m_padToDieLenth;
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 
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  long long 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, bool aForceFinish )
306 {
309 
310  m_currentNode->Add( lP );
311  m_currentNode->Add( lN );
312 
313  CommitPlacement();
314 
315  return true;
316 }
317 
318 
320 {
322  return true;
323 }
324 
325 
327 {
328  return m_originPair.CP().SegmentCount() > 0 ||
329  m_originPair.CN().SegmentCount() > 0;
330 }
331 
332 
334 {
335  if( m_currentNode )
337 
339  return true;
340 }
341 
342 
344 {
345  LINE l1( m_originPair.PLine(), aShape->CLine( 0 ) );
346  LINE l2( m_originPair.NLine(), aShape->CLine( 1 ) );
347 
348  if( m_currentNode->CheckColliding( &l1 ) )
349  return false;
350 
351  if( m_currentNode->CheckColliding( &l2 ) )
352  return false;
353 
354  int w = aShape->Width();
355  int clearance = w + m_settings.m_spacing;
356 
357  return m_result.CheckSelfIntersections( aShape, clearance );
358 }
359 
360 
362 {
365 
366  ITEM_SET traces;
367 
368  traces.Add( &m_currentTraceP );
369  traces.Add( &m_currentTraceN );
370 
371  return traces;
372 }
373 
374 
376 {
377  return m_currentEnd;
378 }
379 
380 
382 {
383  return m_initialSegment->Layers().Start();
384 }
385 
386 
387 const wxString DP_MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
388 {
389  wxString status;
390 
391  switch( m_lastStatus )
392  {
393  case TOO_LONG:
394  status = _( "Too long: " );
395  break;
396  case TOO_SHORT:
397  status = _("Too short: " );
398  break;
399  case TUNED:
400  status = _( "Tuned: " );
401  break;
402  default:
403  return _( "?" );
404  }
405 
406  status += ::MessageTextFromValue( aUnits, m_lastLength );
407  status += "/";
408  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength );
409  status += " (gap: ";
410  status += ::MessageTextFromValue( aUnits, m_originPair.Gap() );
411  status += ")";
412 
413  return status;
414 }
415 
416 
418 {
419  return m_lastStatus;
420 }
421 
422 const std::vector<int> DP_MEANDER_PLACER::CurrentNets() const
423 {
424  std::vector<int> rv;
425  rv.push_back( m_originPair.NetP() );
426  rv.push_back( m_originPair.NetN() );
427  return rv;
428 }
429 
430 }
int GetTotalPadToDieLength(const LINE &aLine) const
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:125
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:149
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
The geometry of a single meander.
Definition: pns_meander.h:103
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:655
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:46
int Width() const
Definition: pns_meander.h:266
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:124
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:804
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:426
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()
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
Return the most recent world state.
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
long long int origPathLength() const
Current routing start point (end of tail, beginning of head).
void KillChildren()
Definition: pns_node.cpp:1292
#define NULL
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:448
NODE * m_world
Total length added by pad to die size.
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:216
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:210
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...
int SegmentCount() const
Function SegmentCount()
virtual void AddSegment(SEG aS, int aColor, const std::string aName="")
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
Pointer to world to search colliding items.
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:372
int m_padToDieLenth
Width of the meandered trace(s).
Definition: seg.h:41
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
Number of line segments for arc approximation.
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)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:427
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:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:87
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:81
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:158
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:440
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
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:150
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
VECTOR2I B
Definition: seg.h:50