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 The 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 "pns_debug_decorator.h"
23#include "pns_itemset.h"
24#include "pns_meander_placer.h"
25#include "pns_node.h"
26#include "pns_router.h"
27#include "pns_solid.h"
28#include "pns_topology.h"
29
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;
42 m_lastDelay = 0;
46 m_netClass = nullptr;
47}
48
49
53
54
55NODE* MEANDER_PLACER::CurrentNode( bool aLoopsRemoved ) const
56{
57 if( !m_currentNode )
58 return m_world;
59
60 return m_currentNode;
61}
62
63
64bool MEANDER_PLACER::Start( const VECTOR2I& aP, ITEM* aStartItem )
65{
66 if( !aStartItem || !aStartItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
67 {
68 Router()->SetFailureReason( _( "Please select a track whose length you want to tune." ) );
69 return false;
70 }
71
72 m_initialSegment = static_cast<LINKED_ITEM*>( aStartItem );
73 m_currentNode = nullptr;
75
76 m_world = Router()->GetWorld()->Branch();
77 m_originLine = m_world->AssembleLine( m_initialSegment );
78
79 TOPOLOGY topo( m_world );
81
84
85 if( m_startPad_n )
86 {
87 m_padToDieLength += m_startPad_n->GetPadToDie();
88 m_padToDieDelay += m_startPad_n->GetPadToDieDelay();
89 }
90
91 if( m_endPad_n )
92 {
93 m_padToDieLength += m_endPad_n->GetPadToDie();
94 m_padToDieDelay += m_endPad_n->GetPadToDieDelay();
95 }
96
97 m_world->Remove( m_originLine );
98
100 m_currentEnd = VECTOR2I( 0, 0 );
101
102 const BOARD_CONNECTED_ITEM* conItem = static_cast<BOARD_CONNECTED_ITEM*>( aStartItem->GetSourceItem() );
103 m_netClass = conItem->GetEffectiveNetClass();
104
106
107 return true;
108}
109
110
115
116
121
122
124{
125 // If this is a time domain tuning, calculate the target length for the desired total delay
126 if( m_settings.m_isTimeDomain )
127 {
128 const int64_t curDelay = origPathDelay();
129
130 const int64_t desiredDelayMin = m_settings.m_targetLengthDelay.Min();
131 const int64_t desiredDelayOpt = m_settings.m_targetLengthDelay.Opt();
132 const int64_t desiredDelayMax = m_settings.m_targetLengthDelay.Max();
133
134 const int64_t delayDifferenceOpt = desiredDelayOpt - curDelay;
135
136 const int64_t curLength = origPathLength();
137 const int64_t lengthDiffMin = m_router->GetInterface()->CalculateLengthForDelay(
138 desiredDelayOpt - desiredDelayMin, m_currentWidth, false, m_router->Sizes().DiffPairGap(),
139 m_router->GetCurrentLayer(), m_netClass );
140 int64_t lengthDiffOpt = m_router->GetInterface()->CalculateLengthForDelay(
141 std::abs( delayDifferenceOpt ), m_currentWidth, false, m_router->Sizes().DiffPairGap(),
142 m_router->GetCurrentLayer(), m_netClass );
143 const int64_t lengthDiffMax = m_router->GetInterface()->CalculateLengthForDelay(
144 desiredDelayMax - desiredDelayOpt, m_currentWidth, false, m_router->Sizes().DiffPairGap(),
145 m_router->GetCurrentLayer(), m_netClass );
146
147 lengthDiffOpt = delayDifferenceOpt > 0 ? lengthDiffOpt : -lengthDiffOpt;
148
149 m_settings.m_targetLength.SetMin( curLength + lengthDiffOpt - lengthDiffMin );
150 m_settings.m_targetLength.SetOpt( curLength + lengthDiffOpt );
151 m_settings.m_targetLength.SetMax( curLength + lengthDiffOpt + lengthDiffMax );
152 }
153}
154
155
156bool MEANDER_PLACER::Move( const VECTOR2I& aP, ITEM* aEndItem )
157{
159
160 return doMove( aP, aEndItem, m_settings.m_targetLength.Opt(), m_settings.m_targetLength.Min(),
161 m_settings.m_targetLength.Max() );
162}
163
164
165bool MEANDER_PLACER::doMove( const VECTOR2I& aP, ITEM* aEndItem, long long int aTargetLength,
166 long long int aTargetMin, long long int aTargetMax )
167{
168 if( m_currentStart == aP )
169 return false;
170
171 if( m_currentNode )
172 delete m_currentNode;
173
174 m_currentNode = m_world->Branch();
175
176 SHAPE_LINE_CHAIN pre, tuned, post;
177
178 m_originLine.CLine().Split( m_currentStart, aP, pre, tuned, post );
179
180 m_result = MEANDERED_LINE( this, false );
181 m_result.SetWidth( m_originLine.Width() );
182 m_result.SetBaselineOffset( 0 );
183
184 for( int i = 0; i < tuned.SegmentCount(); i++ )
185 {
186 if( tuned.IsArcSegment( i ) )
187 {
188 ssize_t arcIndex = tuned.ArcIndex( i );
189 m_result.AddArc( tuned.Arc( arcIndex ) );
190 i = tuned.NextShape( i );
191
192 // NextShape will return -1 if last shape
193 if( i < 0 )
194 i = tuned.SegmentCount();
195
196 continue;
197 }
198
199 bool side = false;
200 const SEG s = tuned.CSegment( i );
201
202 if( m_settings.m_initialSide == 0 )
203 side = s.Side( aP ) < 0;
204 else
205 side = m_settings.m_initialSide < 0;
206
207 m_result.AddCorner( s.A );
208 m_result.MeanderSegment( s, side );
209 m_result.AddCorner( s.B );
210 }
211
212 long long int lineLen = origPathLength();
213 int64_t lineDelay = origPathDelay();
214
215 m_lastLength = lineLen;
218
219 if( lineLen > m_settings.m_targetLength.Max() )
220 {
222 }
223 else
224 {
225 m_lastLength = lineLen - tuned.Length();
226
227 if( m_settings.m_isTimeDomain )
228 {
230 - m_router->GetInterface()->CalculateDelayForShapeLineChain(
231 tuned, m_currentWidth, false, m_router->Sizes().DiffPairGap(),
232 m_router->GetCurrentLayer(), m_netClass );
233 }
234
235 tuneLineLength( m_result, aTargetLength - lineLen );
236 }
237
238 for( const ITEM* item : m_tunedPath.CItems() )
239 {
240 if( const LINE* l = dyn_cast<const LINE*>( item ) )
241 {
242 PNS_DBG( Dbg(), AddItem, l, BLUE, 30000, wxT( "tuned-line" ) );
243
244 m_router->GetInterface()->DisplayPathLine( l->CLine(), 1 );
245 }
246 }
247
248 if( m_lastStatus != TOO_LONG )
249 {
250 tuned.Clear();
251
252 for( MEANDER_SHAPE* m : m_result.Meanders() )
253 {
254 if( m->Type() != MT_EMPTY )
255 {
256 tuned.Append ( m->CLine( 0 ) );
257 }
258 }
259
260 m_lastLength += tuned.Length();
261
262 if( m_settings.m_isTimeDomain )
263 {
264 m_lastDelay += m_router->GetInterface()->CalculateDelayForShapeLineChain(
265 tuned, m_currentWidth, false, m_router->Sizes().DiffPairGap(), m_router->GetCurrentLayer(),
266 m_netClass );
267 }
268
269 if( m_lastLength > aTargetMax )
271 else if( m_lastLength < aTargetMin )
273 else
275 }
276
277 m_finalShape.Clear();
278
279 if( m_settings.m_keepEndpoints )
280 {
281 pre.Simplify();
282 tuned.Simplify();
283 post.Simplify();
284
285 m_finalShape.Append( pre );
286 m_finalShape.Append( tuned );
287 m_finalShape.Append( post );
288 }
289 else
290 {
291 m_finalShape.Append( pre );
292 m_finalShape.Append( tuned );
293 m_finalShape.Append( post );
294 m_finalShape.Simplify();
295 }
296
297 return true;
298}
299
300
301bool MEANDER_PLACER::FixRoute( const VECTOR2I& aP, ITEM* aEndItem, bool aForceFinish )
302{
303 if( !m_currentNode )
304 return false;
305
309
310 return true;
311}
312
313
315{
316 m_world->KillChildren();
317 return true;
318}
319
320
322{
323 return m_currentTrace.SegmentCount() > 0;
324}
325
326
328{
329 if( m_currentNode )
331
332 m_currentNode = nullptr;
333 return true;
334}
335
336
338{
339 LINE l( m_originLine, aShape->CLine( 0 ) );
340
341 if( m_currentNode->CheckColliding( &l ) )
342 return false;
343
344 int w = aShape->Width();
345 int clearance = w + m_settings.m_spacing;
346
347 return m_result.CheckSelfIntersections( aShape, clearance );
348}
349
350
356
358{
359 return m_tunedPath;
360}
361
363{
364 return m_currentStart;
365}
366
368{
369 return m_currentEnd;
370}
371
373{
374 return m_initialSegment->Layers().Start();
375}
376
377
379{
380 if( m_lastLength )
381 return m_lastLength;
382 else
383 return origPathLength();
384}
385
386
388{
389 if( m_lastDelay )
390 return m_lastDelay;
391 else
392 return origPathDelay();
393}
394
395
400
401}
A base class derived from BOARD_ITEM for items that can be connected and have a net,...
virtual NETCLASS * GetEffectiveNetClass() const
Return the NETCLASS for this item.
ROUTER * Router() const
Return current router settings.
ROUTER * m_router
DEBUG_DECORATOR * Dbg() const
Base class for PNS router board items.
Definition pns_item.h:98
BOARD_ITEM * GetSourceItem() const
Definition pns_item.h:202
bool OfKind(int aKindMask) const
Definition pns_item.h:181
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
Represent a set of meanders fitted over a single or two lines.
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.
MEANDER_SETTINGS m_settings
The current end point.
int64_t lineDelay(const ITEM_SET &aLine, const SOLID *aStartPad, const SOLID *aEndPad) const
Calculate the total delay of the line represented by an item set (tracks and vias)
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 bool FixRoute(const VECTOR2I &aP, ITEM *aEndItem, bool aForceFinish=false) override
Function FixRoute()
bool doMove(const VECTOR2I &aP, ITEM *aEndItem, long long int aTargetLength, long long int aTargetMin, long long int aTargetMax)
virtual bool Move(const VECTOR2I &aP, ITEM *aEndItem) override
Function Move()
virtual long long int origPathLength() const
int CurrentLayer() const override
Function CurrentLayer()
virtual void calculateTimeDomainTargets()
current routing start point (end of tail, beginning of head)
int m_padToDieDelay
The netclass for the placed segments.
const VECTOR2I & CurrentEnd() const override
Function CurrentEnd()
const VECTOR2I & CurrentStart() const override
Function CurrentStart()
long long int TuningLengthResult() const override
Return the resultant length or skew of the tuned traces.
bool AbortPlacement() override
int64_t TuningDelayResult() const override
Return the resultant delay or skew of the tuned traces.
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 TunedPath() override
const ITEM_SET Traces() override
Function Traces()
MEANDER_PLACER(ROUTER *aRouter)
virtual int64_t origPathDelay() const
bool CheckFit(MEANDER_SHAPE *aShape) override
Checks if it's OK to place the shape aShape (i.e.
VECTOR2I m_currentStart
Current world state.
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()
int m_padToDieLength
Total length added by pad to die size.
bool CommitPlacement() override
The geometry of a single meander.
int Width() const
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Keep the router "world" - i.e.
Definition pns_node.h:232
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition pns_node.cpp:143
void SetFailureReason(const wxString &aReason)
Definition pns_router.h:227
void CommitRouting()
NODE * GetWorld() const
Definition pns_router.h:178
const ITEM_SET AssembleTuningPath(ROUTER_IFACE *aRouterIface, 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
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 Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
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:56
#define _(s)
Push and Shove diff pair dimensions (gap) settings dialog.
@ MT_EMPTY
Definition pns_meander.h:47
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:400
#define PNS_DBG(dbg, method,...)
int clearance
Casted dyn_cast(From aObject)
A lightweight dynamic downcast.
Definition typeinfo.h:61
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695