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-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  * Author: Tomasz Wlostowski <[email protected]>
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 {
37  m_currentNode = nullptr;
38 
39  // Init temporary variables (do not leave uninitialized members)
40  m_initialSegment = nullptr;
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  if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
63  {
64  Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
65  return false;
66  }
67 
68  m_initialSegment = static_cast<LINKED_ITEM*>( aStartItem );
69  m_currentNode = nullptr;
71 
72  m_world = Router()->GetWorld()->Branch();
74 
75  SOLID* padA = nullptr;
76  SOLID* padB = nullptr;
77 
78  TOPOLOGY topo( m_world );
79  m_tunedPath = topo.AssembleTuningPath( m_initialSegment, &padA, &padB );
80 
81  m_padToDieLength = 0;
82 
83  if( padA )
84  m_padToDieLength += padA->GetPadToDie();
85 
86  if( padB )
87  m_padToDieLength += padB->GetPadToDie();
88 
90 
92  m_currentEnd = VECTOR2I( 0, 0 );
93 
94  return true;
95 }
96 
97 
98 long long int MEANDER_PLACER::origPathLength() const
99 {
101 }
102 
103 
104 bool MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
105 {
106  return doMove( aP, aEndItem, m_settings.m_targetLength );
107 }
108 
109 
110 bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, long long int aTargetLength )
111 {
112  SHAPE_LINE_CHAIN pre, tuned, post;
113 
114  if( m_currentNode )
115  delete m_currentNode;
116 
118 
119  cutTunedLine( m_originLine.CLine(), m_currentStart, aP, pre, tuned, post );
120 
121  m_result = MEANDERED_LINE( this, false );
124 
125  for( int i = 0; i < tuned.SegmentCount(); i++ )
126  {
127  if( tuned.IsArcSegment( i ) )
128  {
129  ssize_t arcIndex = tuned.ArcIndex( i );
130  m_result.AddArc( tuned.Arc( arcIndex ) );
131  i = tuned.NextShape( i );
132 
133  // NextShape will return -1 if last shape
134  if( i < 0 )
135  i = tuned.SegmentCount();
136 
137  continue;
138  }
139 
140  const SEG s = tuned.CSegment( i );
141  m_result.AddCorner( s.A );
142  m_result.MeanderSegment( s, s.Side( aP ) < 0 );
143  m_result.AddCorner( s.B );
144  }
145 
146  long long int lineLen = origPathLength();
147 
148  m_lastLength = lineLen;
150 
151  if( compareWithTolerance( lineLen, aTargetLength, m_settings.m_lengthTolerance ) > 0 )
152  {
154  } else {
155  m_lastLength = lineLen - tuned.Length();
156  tuneLineLength( m_result, aTargetLength - lineLen );
157  }
158 
159  for( const ITEM* item : m_tunedPath.CItems() )
160  {
161  if( const LINE* l = dyn_cast<const LINE*>( item ) )
162  {
163  PNS_DBG( Dbg(), AddLine, l->CLine(), BLUE, 30000, "tuned-line" );
164  }
165  }
166 
167  if( m_lastStatus != TOO_LONG )
168  {
169  tuned.Clear();
170 
171  for( MEANDER_SHAPE* m : m_result.Meanders() )
172  {
173  if( m->Type() != MT_EMPTY )
174  {
175  tuned.Append ( m->CLine( 0 ) );
176  }
177  }
178 
179  m_lastLength += tuned.Length();
180 
181  int comp = compareWithTolerance( m_lastLength - aTargetLength, 0,
183 
184  if( comp > 0 )
186  else if( comp < 0 )
188  else
190  }
191 
193  m_finalShape.Append( pre );
194  m_finalShape.Append( tuned );
195  m_finalShape.Append( post );
197 
198  return true;
199 }
200 
201 
202 bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
203 {
204  if( !m_currentNode )
205  return false;
206 
209  CommitPlacement();
210 
211  return true;
212 }
213 
214 
216 {
218  return true;
219 }
220 
221 
223 {
224  return m_currentTrace.SegmentCount() > 0;
225 }
226 
227 
229 {
230  if( m_currentNode )
232 
233  m_currentNode = nullptr;
234  return true;
235 }
236 
237 
239 {
240  LINE l( m_originLine, aShape->CLine( 0 ) );
241 
242  if( m_currentNode->CheckColliding( &l ) )
243  return false;
244 
245  int w = aShape->Width();
246  int clearance = w + m_settings.m_spacing;
247 
248  return m_result.CheckSelfIntersections( aShape, clearance );
249 }
250 
251 
253 {
255  return ITEM_SET( &m_currentTrace );
256 }
257 
258 
260 {
261  return m_currentEnd;
262 }
263 
265 {
266  return m_initialSegment->Layers().Start();
267 }
268 
269 
270 const wxString MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
271 {
272  wxString status;
273 
274  switch ( m_lastStatus )
275  {
276  case TOO_LONG:
277  status = _( "Too long: " );
278  break;
279  case TOO_SHORT:
280  status = _( "Too short: " );
281  break;
282  case TUNED:
283  status = _( "Tuned: " );
284  break;
285  default:
286  return _( "?" );
287  }
288 
289  status += ::MessageTextFromValue( aUnits, m_lastLength );
290  status += "/";
291  status += ::MessageTextFromValue( aUnits, m_settings.m_targetLength );
292 
293  return status;
294 }
295 
296 
298 {
299  return m_lastStatus;
300 }
301 
302 }
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:137
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:104
virtual bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Function FixRoute()
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:146
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
The geometry of a single meander.
Definition: pns_meander.h:110
Implementation of conversion functions that require both schematic and board internal units.
int SegmentCount() const
Definition: pns_line.h:139
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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:707
TUNING_STATUS m_lastStatus
MEANDER_PLACER(ROUTER *aRouter)
long long int m_lastLength
LINKED_ITEM * m_initialSegment
const ITEM_SET AssembleTuningPath(ITEM *aStart, SOLID **aStartPad=nullptr, SOLID **aEndPad=nullptr)
Like AssembleTrivialPath, but follows the track length algorithm, which discards segments that are fu...
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
int Width() const
Definition: pns_meander.h:282
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:137
TUNING_STATUS
< Result of the length tuning operation
int m_currentWidth
Meander settings.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
int Start() const
Definition: pns_layerset.h:82
void SetWidth(int aWidth)
Set the line width.
Definition: pns_meander.h:466
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
int m_padToDieLength
Width of the meandered trace(s).
void KillChildren()
Definition: pns_node.cpp:1405
int GetPadToDie() const
Definition: pns_solid.h:104
void AddArc(const SHAPE_ARC &aArc1, const SHAPE_ARC &aArc2=SHAPE_ARC())
Create a dummy meander shape representing an arc corner.
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:489
const ITEM_SET Traces() override
Function Traces()
long long int lineLength(const ITEM_SET &aLine) const
Calculate the total length of the line represented by an item set (tracks and vias)
NODE * m_world
Total length added by pad to die size.
bool AbortPlacement() override
bool doMove(const VECTOR2I &aP, ITEM *aEndItem, long long int aTargetLength)
bool CommitPlacement() override
#define PNS_DBG(dbg, method,...)
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:232
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:202
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...
#define _(s)
bool HasPlacedAnything() const override
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:385
int CurrentLayer() const override
Function CurrentLayer()
Definition: seg.h:40
EDA_UNITS
Definition: eda_units.h:38
VECTOR2I m_currentStart
Current world state.
Definition: color4d.h:56
void MeanderSegment(const SEG &aSeg, bool aSide, int aBaseIndex=0)
Fit maximum amplitude meanders on a given segment and adds to the current line.
Definition: pns_meander.cpp:45
bool CheckFit(MEANDER_SHAPE *aShape) override
Checks if it's OK to place the shape aShape (i.e.
MEANDER_SETTINGS m_settings
The current end point.
int m_lengthTolerance
Target skew value for diff pair de-skewing.
Definition: pns_meander.h:101
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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:450
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:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:138
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:92
const ENTRIES & CItems() const
Definition: pns_itemset.h:136
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:156
void Clear()
Remove all points from the line chain.
SHAPE_LINE_CHAIN m_finalShape
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:83
Push and Shove diff pair dimensions (gap) settings dialog.
NODE * GetWorld() const
Definition: pns_router.h:153
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:481
virtual long long int origPathLength() const
current routing start point (end of tail, beginning of head)
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:638
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
virtual TUNING_STATUS TuningStatus() const override
Return the tuning status (too short, too long, etc.) of the trace(s) being tuned.
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:154
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:946
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
virtual const wxString TuningInfo(EDA_UNITS aUnits) const override
Return a string describing the status and length of the tuned traces.
VECTOR2I B
Definition: seg.h:49