KiCad PCB EDA Suite
pns_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-2015 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 <base_units.h> // God forgive me doing this...
23 
24 #include "pns_node.h"
25 #include "pns_itemset.h"
26 #include "pns_topology.h"
27 #include "pns_meander_placer.h"
28 #include "pns_router.h"
29 #include "pns_debug_decorator.h"
30 
31 namespace PNS {
32 
34  MEANDER_PLACER_BASE( aRouter )
35 {
36  m_world = NULL;
37  m_currentNode = NULL;
38 
39  // Init temporary variables (do not leave uninitialized members)
40  m_initialSegment = NULL;
41  m_lastLength = 0;
43 }
44 
45 
47 {
48 }
49 
50 
51 NODE* MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
52 {
53  if( !m_currentNode )
54  return m_world;
55 
56  return m_currentNode;
57 }
58 
59 
60 bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
61 {
62  VECTOR2I p;
63 
64  if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T ) )
65  {
66  Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
67  return false;
68  }
69 
70  m_initialSegment = static_cast<SEGMENT*>( aStartItem );
71 
72  p = m_initialSegment->Seg().NearestPoint( aP );
73 
74  m_currentNode = NULL;
75  m_currentStart = p;
76 
77  m_world = Router()->GetWorld()->Branch();
79 
80  TOPOLOGY topo( m_world );
82 
84 
86  m_currentEnd = VECTOR2I( 0, 0 );
87 
88  return true;
89 }
90 
91 
93 {
94  int total = 0;
95  for( const ITEM* item : m_tunedPath.CItems() )
96  {
97  if( const LINE* l = dyn_cast<const LINE*>( item ) )
98  {
99  total += l->CLine().Length();
100  }
101  }
102 
103  return total;
104 }
105 
106 
107 bool MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
108 {
109  return doMove( aP, aEndItem, m_settings.m_targetLength );
110 }
111 
112 
113 bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, int aTargetLength )
114 {
115  SHAPE_LINE_CHAIN pre, tuned, post;
116 
117  if( m_currentNode )
118  delete m_currentNode;
119 
121 
122  cutTunedLine( m_originLine.CLine(), m_currentStart, aP, pre, tuned, post );
123 
124  m_result = MEANDERED_LINE( this, false );
125  m_result.SetWidth( m_originLine.Width() );
126  m_result.SetBaselineOffset( 0 );
127 
128  for( int i = 0; i < tuned.SegmentCount(); i++ )
129  {
130  const SEG s = tuned.CSegment( i );
131  m_result.AddCorner( s.A );
132  m_result.MeanderSegment( s );
133  m_result.AddCorner( s.B );
134  }
135 
136  int lineLen = origPathLength();
137 
138  m_lastLength = lineLen;
140 
141  if( compareWithTolerance( lineLen, aTargetLength, m_settings.m_lengthTolerance ) > 0 )
142  {
144  } else {
145  m_lastLength = lineLen - tuned.Length();
146  tuneLineLength( m_result, aTargetLength - lineLen );
147  }
148 
149  for( const ITEM* item : m_tunedPath.CItems() )
150  {
151  if( const LINE* l = dyn_cast<const LINE*>( item ) )
152  {
153  Dbg()->AddLine( l->CLine(), 5, 30000 );
154  }
155  }
156 
157  if( m_lastStatus != TOO_LONG )
158  {
159  tuned.Clear();
160 
161  for( MEANDER_SHAPE* m : m_result.Meanders() )
162  {
163  if( m->Type() != MT_EMPTY )
164  {
165  tuned.Append ( m->CLine( 0 ) );
166  }
167  }
168 
169  m_lastLength += tuned.Length();
170 
171  int comp = compareWithTolerance( m_lastLength - aTargetLength, 0, m_settings.m_lengthTolerance );
172 
173  if( comp > 0 )
175  else if( comp < 0 )
177  else
179  }
180 
182  m_finalShape.Append( pre );
183  m_finalShape.Append( tuned );
184  m_finalShape.Append( post );
186 
187  return true;
188 }
189 
190 
191 bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem )
192 {
193  if( !m_currentNode )
194  return false;
195 
198 
200  return true;
201 }
202 
203 
205 {
206  LINE l( m_originLine, aShape->CLine( 0 ) );
207 
208  if( m_currentNode->CheckColliding( &l ) )
209  return false;
210 
211  int w = aShape->Width();
212  int clearance = w + m_settings.m_spacing;
213 
214  return m_result.CheckSelfIntersections( aShape, clearance );
215 }
216 
217 
219 {
221  return ITEM_SET( &m_currentTrace );
222 }
223 
224 
226 {
227  return m_currentEnd;
228 }
229 
231 {
232  return m_initialSegment->Layers().Start();
233 }
234 
235 
236 const wxString MEANDER_PLACER::TuningInfo() const
237 {
238  wxString status;
239 
240  switch ( m_lastStatus )
241  {
242  case TOO_LONG:
243  status = _( "Too long: " );
244  break;
245  case TOO_SHORT:
246  status = _( "Too short: " );
247  break;
248  case TUNED:
249  status = _( "Tuned: " );
250  break;
251  default:
252  return _( "?" );
253  }
254 
255  status += LengthDoubleToString( (double) m_lastLength, false );
256  status += "/";
257  status += LengthDoubleToString( (double) m_settings.m_targetLength, false );
258 
259  return status;
260 }
261 
262 
264 {
265  return m_lastStatus;
266 }
267 
268 }
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:123
Class ITEM.
Definition: pns_item.h:53
Class MEANDER_PLACER_BASE.
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Function CheckSelfIntersections()
Class NODE.
Definition: pns_node.h:137
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
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...
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:70
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:834
TUNING_STATUS m_lastStatus
VECTOR2I m_currentEnd
current end point
MEANDER_PLACER(ROUTER *aRouter)
virtual int origPathLength() const
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
int Width() const
Returns line width
Definition: pns_line.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:109
TUNING_STATUS
Result of the length tuning operation
NODE * GetWorld() const
Definition: pns_router.h:143
int m_currentWidth
width of the meandered trace(s)
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
bool OfKind(int aKindMask) const
Function OfKind()
Definition: pns_item.h:130
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0)
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
virtual const wxString TuningInfo() const override
Function TuningInfo()
void tuneLineLength(MEANDERED_LINE &aTuned, int aElongation)
Function tuneLineLength()
const ITEM_SET Traces() override
Function Traces()
bool doMove(const VECTOR2I &aP, ITEM *aEndItem, int aTargetLength)
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:213
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
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
int CurrentLayer() const override
Function CurrentLayer()
Definition: seg.h:37
int compareWithTolerance(int aValue, int aExpected, int aTolerance=0) const
Function compareWithTolerance()
VECTOR2I m_currentStart
current routing start point (end of tail, beginning of head)
NODE * m_world
pointer to world to search colliding items
bool CheckFit(MEANDER_SHAPE *aShape) override
Function CheckFit()
virtual bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem) override
Function FixRoute()
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:326
NODE * m_currentNode
Current world state
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.
SHAPE_LINE_CHAIN m_finalShape
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
Push and Shove diff pair dimensions (gap) settings dialog.
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:596
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
virtual TUNING_STATUS TuningStatus() const override
Function TuningStatus()
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
VECTOR2I B
Definition: seg.h:48