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-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 
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 = nullptr;
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, m_currentWidth + Clearance() );
57 
59 }
60 
61 
63 {
64  // Assumption: All tracks are part of the same net class.
65  // It shouldn't matter which track we pick. They should all have the same clearance if
66  // they are part of the same net class. Therefore, pick the first one on the list.
67  ITEM* itemToCheck = Traces().CItems().front().item;
68  PNS::CONSTRAINT constraint;
69 
71  nullptr, CurrentLayer(), &constraint );
72 
73  wxCHECK_MSG( constraint.m_Value.HasMin(), m_currentWidth, "No minimum clearance?" );
74 
75  return constraint.m_Value.Min();
76 }
77 
78 
80 {
81  m_settings = aSettings;
82 }
83 
84 
85 void MEANDER_PLACER_BASE::cutTunedLine( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aTuneStart,
86  const VECTOR2I& aCursorPos, SHAPE_LINE_CHAIN& aPre,
87  SHAPE_LINE_CHAIN& aTuned, SHAPE_LINE_CHAIN& aPost )
88 {
89  VECTOR2I cp ( aCursorPos );
90 
91  if( cp == aTuneStart ) // we don't like tuning segments with 0 length
92  {
93  int idx = aOrigin.FindSegment( cp );
94 
95  if( idx >= 0 )
96  {
97  const SEG& s = aOrigin.CSegment( idx );
98  cp += ( s.B - s.A ).Resize( 2 );
99  }
100  else
101  {
102  cp += VECTOR2I( 2, 5 ); // some arbitrary value that is not 45 degrees oriented
103  }
104  }
105 
106  VECTOR2I n = aOrigin.NearestPoint( cp, false );
107  VECTOR2I m = aOrigin.NearestPoint( aTuneStart, false );
108 
109  SHAPE_LINE_CHAIN l( aOrigin );
110  l.Split( n );
111  l.Split( m );
112 
113  int i_start = l.Find( m );
114  int i_end = l.Find( n );
115 
116  if( i_start > i_end )
117  {
118  l = l.Reverse();
119  i_start = l.Find( m );
120  i_end = l.Find( n );
121  }
122 
123  aPre = l.Slice( 0, i_start );
124  aPost = l.Slice( i_end, -1 );
125  aTuned = l.Slice( i_start, i_end );
126 
127  aTuned.Simplify();
128 }
129 
130 
131 void MEANDER_PLACER_BASE::tuneLineLength( MEANDERED_LINE& aTuned, long long int aElongation )
132 {
133  long long int remaining = aElongation;
134  bool finished = false;
135 
136  for( MEANDER_SHAPE* m : aTuned.Meanders() )
137  {
138  if( m->Type() != MT_CORNER && m->Type() != MT_ARC )
139  {
140  if( remaining >= 0 )
141  remaining -= m->MaxTunableLength() - m->BaselineLength();
142 
143  if( remaining < 0 )
144  {
145  if( !finished )
146  {
147  MEANDER_TYPE newType;
148 
149  if( m->Type() == MT_START || m->Type() == MT_SINGLE )
150  newType = MT_SINGLE;
151  else
152  newType = MT_FINISH;
153 
154  m->SetType( newType );
155  m->Recalculate();
156 
157  finished = true;
158  }
159  else
160  {
161  m->MakeEmpty();
162  }
163  }
164  }
165  }
166 
167  remaining = aElongation;
168  int meanderCount = 0;
169 
170  for( MEANDER_SHAPE* m : aTuned.Meanders() )
171  {
172  if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
173  {
174  if(remaining >= 0)
175  {
176  remaining -= m->MaxTunableLength() - m->BaselineLength();
177  meanderCount ++;
178  }
179  }
180  }
181 
182  long long int balance = 0;
183 
184  if( meanderCount )
185  balance = -remaining / meanderCount;
186 
187  if( balance >= 0 )
188  {
189  for( MEANDER_SHAPE* m : aTuned.Meanders() )
190  {
191  if( m->Type() != MT_CORNER && m->Type() != MT_ARC && m->Type() != MT_EMPTY )
192  {
193  m->Resize( std::max( m->Amplitude() - balance / 2,
194  (long long int) m_settings.m_minAmplitude ) );
195  }
196  }
197  }
198 }
199 
200 
202 {
203  int length = 0;
204  JOINT start;
205  JOINT end;
206 
207  m_world->FindLineEnds( aLine, start, end );
208 
209  // Extract the length of the pad to die for start and end pads
210  for( auto& link : start.LinkList() )
211  {
212  if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
213  {
214  // If there are overlapping pads, choose the first with a non-zero length
215  if( solid->GetPadToDie() > 0 )
216  {
217  length += solid->GetPadToDie();
218  break;
219  }
220  }
221  }
222 
223  for( auto& link : end.LinkList() )
224  {
225  if( const SOLID* solid = dynamic_cast<const SOLID*>( link.item ) )
226  {
227  if( solid->GetPadToDie() > 0 )
228  {
229  length += solid->GetPadToDie();
230  break;
231  }
232  }
233  }
234 
235  return length;
236 }
237 
238 
240 {
241  return m_settings;
242 }
243 
244 
246  long long int aValue, long long int aExpected, long long int aTolerance ) const
247 {
248  if( aValue < aExpected - aTolerance )
249  return -1;
250  else if( aValue > aExpected + aTolerance )
251  return 1;
252  else
253  return 0;
254 }
255 
256 
258 {
259  if( aStartItem->Kind() == ITEM::SEGMENT_T )
260  {
261  return static_cast<SEGMENT*>( aStartItem )->Seg().NearestPoint( aStartPoint );
262  }
263  else
264  {
265  wxASSERT( aStartItem->Kind() == ITEM::ARC_T );
266  ARC* arc = static_cast<ARC*>( aStartItem );
267 
268  if( ( VECTOR2I( arc->Anchor( 0 ) - aStartPoint ) ).SquaredEuclideanNorm() <=
269  ( VECTOR2I( arc->Anchor( 1 ) - aStartPoint ) ).SquaredEuclideanNorm() )
270  {
271  return arc->Anchor( 0 );
272  }
273  else
274  {
275  return arc->Anchor( 1 );
276  }
277  }
278 }
279 
280 
281 long long int MEANDER_PLACER_BASE::lineLength( const ITEM_SET& aLine ) const
282 {
283  long long int total = 0;
284 
285  for( int idx = 0; idx < aLine.Size(); idx++ )
286  {
287  const ITEM* item = aLine[idx];
288 
289  if( const LINE* l = dyn_cast<const LINE*>( item ) )
290  {
291  total += l->CLine().Length();
292  }
293  else if( item->OfKind( ITEM::VIA_T ) && idx > 0 && idx < aLine.Size() - 1 )
294  {
295  int layerPrev = aLine[idx - 1]->Layer();
296  int layerNext = aLine[idx + 1]->Layer();
297 
298  if( layerPrev != layerNext )
299  total += m_router->GetInterface()->StackupHeight( layerPrev, layerNext );
300  }
301  }
302 
303  return total;
304 }
305 
306 }
int GetTotalPadToDieLength(const LINE &aLine) const
Base class for PNS router board items.
Definition: pns_item.h:55
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
int Split(const VECTOR2I &aP)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:77
bool HasMin() const
Definition: minoptmax.h:37
virtual const ITEM_SET Traces()=0
Function Traces()
The geometry of a single meander.
Definition: pns_meander.h:110
virtual bool QueryConstraint(CONSTRAINT_TYPE aType, const PNS::ITEM *aItemA, const PNS::ITEM *aItemB, int aLayer, PNS::CONSTRAINT *aConstraint)=0
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
MEANDER_TYPE
Shapes of available meanders.
Definition: pns_meander.h:37
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
RULE_RESOLVER * GetRuleResolver() const
Definition: pns_router.h:169
void FindLineEnds(const LINE &aLine, JOINT &aA, JOINT &aB)
Destroy all child nodes. Applicable only to the root node.
Definition: pns_node.cpp:1028
virtual int CurrentLayer() const =0
Function CurrentLayer()
virtual int Clearance()
Return the clearance of the track(s) being length tuned.
int Size() const
Definition: pns_itemset.h:160
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:58
T Min() const
Definition: minoptmax.h:33
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
virtual void UpdateSettings(const MEANDER_SETTINGS &aSettings)
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
int m_currentWidth
Meander settings.
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int m_padToDieLength
Width of the meandered trace(s).
A 2D point on a given set of layers and belonging to a certain net, that links together a number of b...
Definition: pns_joint.h:42
int m_step
Length PadToDie.
Definition: pns_meander.h:86
ROUTER * m_router
Definition: pns_algo_base.h:87
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
std::vector< MEANDER_SHAPE * > & Meanders()
Definition: pns_meander.h:489
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:385
Definition: seg.h:40
MEANDER_SETTINGS m_settings
The current end point.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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:48
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:138
const ENTRIES & CItems() const
Definition: pns_itemset.h:136
PnsKind Kind() const
Return the type (kind) of the item.
Definition: pns_item.h:130
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:83
MINOPTMAX< int > m_Value
Definition: pns_node.h:70
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:207
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:80
VECTOR2I B
Definition: seg.h:49