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_debug_decorator.h"
25 #include "pns_itemset.h"
26 #include "pns_meander_placer.h"
27 #include "pns_node.h"
28 #include "pns_router.h"
29 #include "pns_solid.h"
30 #include "pns_topology.h"
31 
32 namespace PNS {
33 
35  MEANDER_PLACER_BASE( aRouter )
36 {
38 
39  // Init temporary variables (do not leave uninitialized members)
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 
75  m_currentStart = p;
76 
77  m_world = Router()->GetWorld()->Branch();
79 
81 
82  TOPOLOGY topo( m_world );
84 
86 
88  m_currentEnd = VECTOR2I( 0, 0 );
89 
90  return true;
91 }
92 
93 
94 long long int MEANDER_PLACER::origPathLength() const
95 {
96  long long int total = m_padToDieLenth;
97  for( const ITEM* item : m_tunedPath.CItems() )
98  {
99  if( const LINE* l = dyn_cast<const LINE*>( item ) )
100  {
101  total += l->CLine().Length();
102  }
103  }
104 
105  return total;
106 }
107 
108 
109 bool MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
110 {
111  return doMove( aP, aEndItem, m_settings.m_targetLength );
112 }
113 
114 
115 bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, long long int aTargetLength )
116 {
117  SHAPE_LINE_CHAIN pre, tuned, post;
118 
119  if( m_currentNode )
120  delete m_currentNode;
121 
123 
124  cutTunedLine( m_originLine.CLine(), m_currentStart, aP, pre, tuned, post );
125 
126  m_result = MEANDERED_LINE( this, false );
129 
130  for( int i = 0; i < tuned.SegmentCount(); i++ )
131  {
132  const SEG s = tuned.CSegment( i );
133  m_result.AddCorner( s.A );
135  m_result.AddCorner( s.B );
136  }
137 
138  long long int lineLen = origPathLength();
139 
140  m_lastLength = lineLen;
142 
143  if( compareWithTolerance( lineLen, aTargetLength, m_settings.m_lengthTolerance ) > 0 )
144  {
146  } else {
147  m_lastLength = lineLen - tuned.Length();
148  tuneLineLength( m_result, aTargetLength - lineLen );
149  }
150 
151  for( const ITEM* item : m_tunedPath.CItems() )
152  {
153  if( const LINE* l = dyn_cast<const LINE*>( item ) )
154  {
155  Dbg()->AddLine( l->CLine(), 5, 30000 );
156  }
157  }
158 
159  if( m_lastStatus != TOO_LONG )
160  {
161  tuned.Clear();
162 
163  for( MEANDER_SHAPE* m : m_result.Meanders() )
164  {
165  if( m->Type() != MT_EMPTY )
166  {
167  tuned.Append ( m->CLine( 0 ) );
168  }
169  }
170 
171  m_lastLength += tuned.Length();
172 
173  int comp = compareWithTolerance( m_lastLength - aTargetLength, 0, m_settings.m_lengthTolerance );
174 
175  if( comp > 0 )
177  else if( comp < 0 )
179  else
181  }
182 
184  m_finalShape.Append( pre );
185  m_finalShape.Append( tuned );
186  m_finalShape.Append( post );
188 
189  return true;
190 }
191 
192 
193 bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
194 {
195  if( !m_currentNode )
196  return false;
197 
200  CommitPlacement();
201 
202  return true;
203 }
204 
205 
207 {
209  return true;
210 }
211 
212 
214 {
215  return m_currentTrace.SegmentCount() > 0;
216 }
217 
218 
220 {
221  if( m_currentNode )
223 
225  return true;
226 }
227 
228 
229 
231 {
232  LINE l( m_originLine, aShape->CLine( 0 ) );
233 
234  if( m_currentNode->CheckColliding( &l ) )
235  return false;
236 
237  int w = aShape->Width();
238  int clearance = w + m_settings.m_spacing;
239 
240  return m_result.CheckSelfIntersections( aShape, clearance );
241 }
242 
243 
245 {
247  return ITEM_SET( &m_currentTrace );
248 }
249 
250 
252 {
253  return m_currentEnd;
254 }
255 
257 {
258  return m_initialSegment->Layers().Start();
259 }
260 
261 
262 const wxString MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
263 {
264  wxString status;
265 
266  switch ( m_lastStatus )
267  {
268  case TOO_LONG:
269  status = _( "Too long: " );
270  break;
271  case TOO_SHORT:
272  status = _( "Too short: " );
273  break;
274  case TUNED:
275  status = _( "Tuned: " );
276  break;
277  default:
278  return _( "?" );
279  }
280 
281  status += ::MessageTextFromValue( aUnits, m_lastLength, false );
282  status += "/";
283  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength, false );
284 
285  return status;
286 }
287 
288 
290 {
291  return m_lastStatus;
292 }
293 
294 }
const SHAPE_LINE_CHAIN & CLine() const
Const accessor to the underlying shape
Definition: pns_line.h:144
EDA_UNITS
Definition: common.h:196
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
virtual 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="")
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
MEANDER_SETTINGS.
Definition: pns_meander.h:107
Implementation of conversion functions that require both schematic and board internal units.
int SegmentCount() const
Returns the number of segments in the line
Definition: pns_line.h:150
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Function AddCorner()
void CommitRouting()
Definition: pns_router.cpp:422
void MeanderSegment(const SEG &aSeg, int aBaseIndex=0)
Function MeanderSegment()
Definition: pns_meander.cpp:46
TUNING_STATUS m_lastStatus
VECTOR2I m_currentEnd
current end point
MEANDER_PLACER(ROUTER *aRouter)
long long int m_lastLength
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
int Width() const
Function Width()
Definition: pns_meander.h:308
const SEG & Seg() const
Definition: pns_segment.h:83
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
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()
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:796
int Start() const
Definition: pns_layerset.h:83
void SetWidth(int aWidth)
Function SetWidth()
Definition: pns_meander.h:460
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const ITEM_SET AssembleTrivialPath(ITEM *aStart)
void KillChildren()
Destroys all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1288
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:893
#define NULL
std::vector< MEANDER_SHAPE * > & Meanders()
Function Meanders()
Definition: pns_meander.h:486
const ITEM_SET Traces() override
Function Traces()
NODE * m_world
pointer to world to search colliding items
bool AbortPlacement() override
bool doMove(const VECTOR2I &aP, ITEM *aEndItem, long long int aTargetLength)
bool CommitPlacement() override
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:225
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:397
void tuneLineLength(MEANDERED_LINE &aTuned, long long int aElongation)
Function tuneLineLength()
std::unordered_set< SCH_ITEM * > ITEM_SET
Definition: sch_item.h:142
bool HasPlacedAnything() const override
MEANDERED_LINE.
Definition: pns_meander.h:398
int m_padToDieLenth
total length added by pad to die size
int CurrentLayer() const override
Function CurrentLayer()
Definition: seg.h:39
wxString MessageTextFromValue(EDA_UNITS aUnits, int aValue, bool aUseMils, EDA_DATA_TYPE aType)
Definition: base_units.cpp:124
VECTOR2I m_currentStart
current routing start point (end of tail, beginning of head)
bool CheckFit(MEANDER_SHAPE *aShape) override
Function CheckFit()
MEANDER_SETTINGS m_settings
meandering settings
int m_lengthTolerance
allowable tuning error
Definition: pns_meander.h:93
NODE * m_currentNode
Current world state
#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
int Width() const
Returns line width
Definition: pns_line.h:187
void Clear()
Function Clear() Removes all points from the line chain.
SHAPE_LINE_CHAIN m_finalShape
int m_spacing
meandering period/spacing (see dialog picture for explanation)
Definition: pns_meander.h:81
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * GetWorld() const
Definition: pns_router.h:152
void SetBaselineOffset(int aOffset)
Function SetBaselineOffset()
Definition: pns_meander.h:476
virtual long long int origPathLength() const
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:620
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 LAYER_RANGE & Layers() const
Definition: pns_item.h:151
virtual const wxString TuningInfo(EDA_UNITS aUnits) const override
Function TuningInfo()
VECTOR2I B
Definition: seg.h:48