KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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
32namespace 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;
44}
45
46
48{
49}
50
51
52NODE* MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
53{
54 if( !m_currentNode )
55 return m_world;
56
57 return m_currentNode;
58}
59
60
61bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
62{
63 if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
64 {
65 Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
66 return false;
67 }
68
69 m_initialSegment = static_cast<LINKED_ITEM*>( aStartItem );
70 m_currentNode = nullptr;
72
73 m_world = Router()->GetWorld()->Branch();
75
76 TOPOLOGY topo( m_world );
78
80
81 if( m_startPad_n )
83
84 if( m_endPad_n )
86
88
90 m_currentEnd = VECTOR2I( 0, 0 );
91
92 return true;
93}
94
95
96long long int MEANDER_PLACER::origPathLength() const
97{
99}
100
101
102bool MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
103{
104 return doMove( aP, aEndItem, m_settings.m_targetLength );
105}
106
107
108bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, long long int aTargetLength )
109{
110 SHAPE_LINE_CHAIN pre, tuned, post;
111
112 if( m_currentNode )
113 delete m_currentNode;
114
116
117 cutTunedLine( m_originLine.CLine(), m_currentStart, aP, pre, tuned, post );
118
119 m_result = MEANDERED_LINE( this, false );
122
123 for( int i = 0; i < tuned.SegmentCount(); i++ )
124 {
125 if( tuned.IsArcSegment( i ) )
126 {
127 ssize_t arcIndex = tuned.ArcIndex( i );
128 m_result.AddArc( tuned.Arc( arcIndex ) );
129 i = tuned.NextShape( i );
130
131 // NextShape will return -1 if last shape
132 if( i < 0 )
133 i = tuned.SegmentCount();
134
135 continue;
136 }
137
138 const SEG s = tuned.CSegment( i );
139 m_result.AddCorner( s.A );
140 m_result.MeanderSegment( s, s.Side( aP ) < 0 );
141 m_result.AddCorner( s.B );
142 }
143
144 long long int lineLen = origPathLength();
145
146 m_lastLength = lineLen;
148
149 if( compareWithTolerance( lineLen, aTargetLength, m_settings.m_lengthTolerance ) > 0 )
150 {
152 } else {
153 m_lastLength = lineLen - tuned.Length();
154 tuneLineLength( m_result, aTargetLength - lineLen );
155 }
156
157 for( const ITEM* item : m_tunedPath.CItems() )
158 {
159 if( const LINE* l = dyn_cast<const LINE*>( item ) )
160 {
161 PNS_DBG( Dbg(), AddItem, l, BLUE, 30000, wxT( "tuned-line" ) );
162
163 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
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
202bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
203{
204 if( !m_currentNode )
205 return false;
206
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
259{
260 return m_currentStart;
261}
262
264{
265 return m_currentEnd;
266}
267
269{
270 return m_initialSegment->Layers().Start();
271}
272
273
274const wxString MEANDER_PLACER::TuningInfo( EDA_UNITS aUnits ) const
275{
276 wxString status;
277
278 switch ( m_lastStatus )
279 {
280 case TOO_LONG:
281 status = _( "Too long: " );
282 break;
283 case TOO_SHORT:
284 status = _( "Too short: " );
285 break;
286 case TUNED:
287 status = _( "Tuned: " );
288 break;
289 default:
290 return _( "?" );
291 }
292
294 status += wxT( "/" );
296
297 return status;
298}
299
300
302{
303 return m_lastStatus;
304}
305
306}
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
int Start() const
Definition: pns_layerset.h:82
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTER * m_router
Definition: pns_algo_base.h:87
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
const std::vector< ITEM * > & CItems() const
Definition: pns_itemset.h:88
Base class for PNS router board items.
Definition: pns_item.h:91
@ SEGMENT_T
Definition: pns_item.h:101
const LAYER_RANGE & Layers() const
Definition: pns_item.h:191
bool OfKind(int aKindMask) const
Definition: pns_item.h:170
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:136
int SegmentCount() const
Definition: pns_line.h:138
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:155
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:412
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:507
void SetWidth(int aWidth)
Set the line width.
Definition: pns_meander.h:492
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Create a dummy meander shape representing a line corner.
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
void AddArc(const SHAPE_ARC &aArc1, const SHAPE_ARC &aArc2=SHAPE_ARC())
Create a dummy meander shape representing an arc corner.
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Check if the given shape is intersecting with any other meander in the current line.
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:515
Base class for Single trace & Differential pair meandering tools, as both of them share a lot of code...
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...
TUNING_STATUS
< Result of the length tuning operation
int m_currentWidth
Meander settings.
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.
MEANDER_SETTINGS m_settings
The current end point.
int compareWithTolerance(long long int aValue, long long int aExpected, long long int aTolerance=0) const
Compare aValue against aExpected with given tolerance.
NODE * m_world
Width of the meandered trace(s).
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
long long int lineLength(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad) const
Calculate the total length of the line represented by an item set (tracks and vias)
virtual const wxString TuningInfo(EDA_UNITS aUnits) const override
Return a string describing the status and length of the tuned traces.
virtual bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Function FixRoute()
TUNING_STATUS m_lastStatus
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
virtual long long int origPathLength() const
current routing start point (end of tail, beginning of head)
int CurrentLayer() const override
Function CurrentLayer()
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
const VECTOR2I & CurrentStart() const override
Function CurrentStart()
bool AbortPlacement() override
bool HasPlacedAnything() const override
NODE * CurrentNode(bool aLoopsRemoved=false) const override
Function CurrentNode()
LINKED_ITEM * m_initialSegment
Total length added by pad to die size.
SHAPE_LINE_CHAIN m_finalShape
const ITEM_SET Traces() override
Function Traces()
MEANDER_PLACER(ROUTER *aRouter)
bool doMove(const VECTOR2I &aP, ITEM *aEndItem, long long int aTargetLength)
bool CheckFit(MEANDER_SHAPE *aShape) override
Checks if it's OK to place the shape aShape (i.e.
VECTOR2I m_currentStart
Current world state.
virtual TUNING_STATUS TuningStatus() const override
Return the tuning status (too short, too long, etc.) of the trace(s) being tuned.
virtual bool Start(const VECTOR2I &aP, ITEM *aStartItem) override
Function Start()
bool CommitPlacement() override
long long int m_lastLength
long long int m_targetLength
Type of corners for the meandered line.
Definition: pns_meander.h:93
int m_lengthTolerance
Target skew value for diff pair de-skewing.
Definition: pns_meander.h:105
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:84
The geometry of a single meander.
Definition: pns_meander.h:115
int Width() const
Definition: pns_meander.h:297
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:237
Keep the router "world" - i.e.
Definition: pns_node.h:198
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:132
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:382
void KillChildren()
Definition: pns_node.cpp:1435
bool Add(std::unique_ptr< SEGMENT > &&aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:620
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:836
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:960
virtual void DisplayPathLine(const SHAPE_LINE_CHAIN &aLine, int aImportance)=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:215
void SetFailureReason(const wxString &aReason)
Definition: pns_router.h:210
void CommitRouting()
Definition: pns_router.cpp:906
NODE * GetWorld() const
Definition: pns_router.h:161
int GetPadToDie() const
Definition: pns_solid.h:105
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...
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_ARC & Arc(size_t aArc) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int NextShape(int aPointIndex, bool aForwards=true) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
long long int Length() const
Return length of the line chain in Euclidean metric.
@ BLUE
Definition: color4d.h:55
#define _(s)
EDA_UNITS
Definition: eda_units.h:43
wxString MessageTextFromValue(const EDA_IU_SCALE &aIuScale, EDA_UNITS aUnits, double aValue, bool aAddUnitsText=true, EDA_DATA_TYPE aType=EDA_DATA_TYPE::DISTANCE)
A helper to convert the double length aValue to a string in inches, millimeters, or unscaled units.
Definition: eda_units.cpp:315
Push and Shove diff pair dimensions (gap) settings dialog.
@ MT_EMPTY
Definition: pns_meander.h:46
#define PNS_DBG(dbg, method,...)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588