KiCad PCB EDA Suite
pns_meander_placer_base.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 
23 #include "pns_meander.h"
24 #include "pns_router.h"
25 #include "pns_solid.h"
26 #include "pns_arc.h"
27 
28 namespace PNS {
29 
31  PLACEMENT_ALGO( aRouter )
32 {
33  m_world = NULL;
34  m_currentWidth = 0;
35  m_padToDieLength = 0;
36 }
37 
38 
40 {
41 }
42 
43 
45 {
46  int a = m_settings.m_maxAmplitude + aSign * m_settings.m_step;
47  a = std::max( a, m_settings.m_minAmplitude );
48 
50 }
51 
52 
54 {
55  int s = m_settings.m_spacing + aSign * m_settings.m_step;
56  s = std::max( s, 2 * m_currentWidth );
57 
59 }
60 
61 
63 {
64  m_settings = aSettings;
65 }
66 
67 
68 void MEANDER_PLACER_BASE::cutTunedLine( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aTuneStart,
69  const VECTOR2I& aCursorPos, SHAPE_LINE_CHAIN& aPre,
70  SHAPE_LINE_CHAIN& aTuned, SHAPE_LINE_CHAIN& aPost )
71 {
72  VECTOR2I cp ( aCursorPos );
73 
74  if( cp == aTuneStart ) // we don't like tuning segments with 0 length
75  {
76  int idx = aOrigin.FindSegment( cp );
77 
78  if( idx >= 0 )
79  {
80  const SEG& s = aOrigin.CSegment( idx );
81  cp += (s.B - s.A).Resize(2);
82  }
83  else
84  {
85  cp += VECTOR2I (2, 5); // some arbitrary value that is not 45 degrees oriented
86  }
87  }
88 
89  VECTOR2I n = aOrigin.NearestPoint( cp, false );
90  VECTOR2I m = aOrigin.NearestPoint( aTuneStart, false );
91 
92  SHAPE_LINE_CHAIN l( aOrigin );
93  l.Split( n );
94  l.Split( m );
95 
96  int i_start = l.Find( m );
97  int i_end = l.Find( n );
98 
99  if( i_start > i_end )
100  {
101  l = l.Reverse();
102  i_start = l.Find( m );
103  i_end = l.Find( n );
104  }
105 
106  aPre = l.Slice( 0, i_start );
107  aPost = l.Slice( i_end, -1 );
108  aTuned = l.Slice( i_start, i_end );
109 
110  aTuned.Simplify();
111 }
112 
113 
114 void MEANDER_PLACER_BASE::tuneLineLength( MEANDERED_LINE& aTuned, long long int aElongation )
115 {
116  long long int remaining = aElongation;
117  bool finished = false;
118 
119  for( MEANDER_SHAPE* m : aTuned.Meanders() )
120  {
121  if( m->Type() != MT_CORNER )
122  {
123  if( remaining >= 0 )
124  remaining -= m->MaxTunableLength() - m->BaselineLength();
125 
126  if( remaining < 0 )
127  {
128  if( !finished )
129  {
130  MEANDER_TYPE newType;
131 
132  if( m->Type() == MT_START || m->Type() == MT_SINGLE )
133  newType = MT_SINGLE;
134  else
135  newType = MT_FINISH;
136 
137  m->SetType( newType );
138  m->Recalculate();
139 
140  finished = true;
141  }
142  else
143  {
144  m->MakeEmpty();
145  }
146  }
147  }
148  }
149 
150  remaining = aElongation;
151  int meanderCount = 0;
152 
153  for( MEANDER_SHAPE* m : aTuned.Meanders() )
154  {
155  if( m->Type() != MT_CORNER && m->Type() != MT_EMPTY )
156  {
157  if(remaining >= 0)
158  {
159  remaining -= m->MaxTunableLength() - m->BaselineLength();
160  meanderCount ++;
161  }
162  }
163  }
164 
165  long long int balance = 0;
166 
167  if( meanderCount )
168  balance = -remaining / meanderCount;
169 
170  if( balance >= 0 )
171  {
172  for( MEANDER_SHAPE* m : aTuned.Meanders() )
173  {
174  if( m->Type() != MT_CORNER && m->Type() != MT_EMPTY )
175  {
176  m->Resize( std::max( m->Amplitude() - balance / 2,
177  (long long int) m_settings.m_minAmplitude ) );
178  }
179  }
180  }
181 }
182 
183 
185 {
186  int length = 0;
187  JOINT start;
188  JOINT end;
189 
190  m_world->FindLineEnds( aLine, start, end );
191 
192  // Extract the length of the pad to die for start and end pads
193  for( auto& link : start.LinkList() )
194  {
195  if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
196  {
197  // If there are overlapping pads, choose the first with a non-zero length
198  if( solid->GetPadToDie() > 0 )
199  {
200  length += solid->GetPadToDie();
201  break;
202  }
203  }
204  }
205 
206  for( auto& link : end.LinkList() )
207  {
208  if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
209  {
210  if( solid->GetPadToDie() > 0 )
211  {
212  length += solid->GetPadToDie();
213  break;
214  }
215  }
216  }
217 
218  return length;
219 }
220 
221 
223 {
224  return m_settings;
225 }
226 
227 
229  long long int aValue, long long int aExpected, long long int aTolerance ) const
230 {
231  if( aValue < aExpected - aTolerance )
232  return -1;
233  else if( aValue > aExpected + aTolerance )
234  return 1;
235  else
236  return 0;
237 }
238 
239 
241 {
242  if( aStartItem->Kind() == ITEM::SEGMENT_T )
243  {
244  return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
245  }
246  else
247  {
248  wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
249  ARC* arc = static_cast<ARC*>( aStartItem );
250 
251  if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
252  ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
253  {
254  return arc->Anchor( 0 );
255  }
256  else
257  {
258  return arc->Anchor( 1 );
259  }
260  }
261 }
262 
263 
264 long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine ) const
265 {
266  long long int total = 0;
267 
268  for( int idx = 0; idx < aLine.Size(); idx++ )
269  {
270  const ITEM* item = aLine[idx];
271 
272  if( const LINE* l = dyn_cast<const LINE*>( item ) )
273  {
274  total += l->CLine().Length();
275  }
276  else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
277  {
278  int layerPrev = aLine[idx - 1]->Layer();
279  int layerNext = aLine[idx + 1]->Layer();
280 
281  if( layerPrev != layerNext )
282  total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
283  }
284  }
285 
286  return total;
287 }
288 
289 }
int Find(const VECTOR2I &aP) const
Function Find()
int GetTotalPadToDieLength(const LINE &aLine) const
Base class for PNS router board items.
Definition: pns_item.h:55
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
int Split(const VECTOR2I &aP)
Function Split()
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:76
The geometry of a single meander.
Definition: pns_meander.h:100
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
MEANDER_TYPE
Shapes of available meanders.
Definition: pns_meander.h:37
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1005
int Size() const
Definition: pns_itemset.h:163
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:60
Dimensions for the meandering algorithm.
Definition: pns_meander.h:57
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
virtual void UpdateSettings(const MEANDER_SETTINGS &aSettings)
int m_currentWidth
Meander settings.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Finds a point on the line chain that is closest to point aP.
int m_padToDieLength
Width of the meandered trace(s).
Represents a 2D point on a given set of layers and belonging to a certain net, that links together a ...
Definition: pns_joint.h:42
int m_step
Length PadToDie.
Definition: pns_meander.h:82
ROUTER * m_router
Definition: pns_algo_base.h:87
#define NULL
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:442
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.
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...
const LINKED_ITEMS & LinkList() const
Definition: pns_joint.h:195
virtual void SpacingStep(int aSign)
Increase/decrease the current meandering spacing by one step.
VECTOR2I getSnappedStartPoint(LINKED_ITEM *aStartItem, VECTOR2I aStartPoint)
Represent a set of meanders fitted over a single or two lines.
Definition: pns_meander.h:366
Definition: seg.h:41
MEANDER_SETTINGS m_settings
The current end point.
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
virtual int StackupHeight(int aFirstLayer, int aSecondLayer) const =0
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:49
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:126
virtual void AmplitudeStep(int aSign)
Increase/decreases the current meandering amplitude by one step.
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:80
Push and Shove diff pair dimensions (gap) settings dialog.
virtual const MEANDER_SETTINGS & MeanderSettings() const
Return the current meandering configuration.
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
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.
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:78
VECTOR2I B
Definition: seg.h:50