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 <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
22 #include "pns_meander_placer_base.h"
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
MEANDER_PLACER_BASE(ROUTER * aRouter)30 MEANDER_PLACER_BASE::MEANDER_PLACER_BASE( ROUTER* aRouter ) :
31 PLACEMENT_ALGO( aRouter )
32 {
33 m_world = nullptr;
34 m_currentWidth = 0;
35 m_padToDieLength = 0;
36 }
37
38
~MEANDER_PLACER_BASE()39 MEANDER_PLACER_BASE::~MEANDER_PLACER_BASE()
40 {
41 }
42
43
AmplitudeStep(int aSign)44 void MEANDER_PLACER_BASE::AmplitudeStep( int aSign )
45 {
46 int a = m_settings.m_maxAmplitude + aSign * m_settings.m_step;
47 a = std::max( a, m_settings.m_minAmplitude );
48
49 m_settings.m_maxAmplitude = a;
50 }
51
52
SpacingStep(int aSign)53 void MEANDER_PLACER_BASE::SpacingStep( int aSign )
54 {
55 int s = m_settings.m_spacing + aSign * m_settings.m_step;
56 s = std::max( s, m_currentWidth + Clearance() );
57
58 m_settings.m_spacing = s;
59 }
60
61
Clearance()62 int MEANDER_PLACER_BASE::Clearance()
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
70 Router()->GetRuleResolver()->QueryConstraint( PNS::CONSTRAINT_TYPE::CT_CLEARANCE, itemToCheck,
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
UpdateSettings(const MEANDER_SETTINGS & aSettings)79 void MEANDER_PLACER_BASE::UpdateSettings( const MEANDER_SETTINGS& aSettings )
80 {
81 m_settings = aSettings;
82 }
83
84
cutTunedLine(const SHAPE_LINE_CHAIN & aOrigin,const VECTOR2I & aTuneStart,const VECTOR2I & aCursorPos,SHAPE_LINE_CHAIN & aPre,SHAPE_LINE_CHAIN & aTuned,SHAPE_LINE_CHAIN & aPost)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
tuneLineLength(MEANDERED_LINE & aTuned,long long int aElongation)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
GetTotalPadToDieLength(const LINE & aLine) const201 int MEANDER_PLACER_BASE::GetTotalPadToDieLength( const LINE& aLine ) const
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
MeanderSettings() const239 const MEANDER_SETTINGS& MEANDER_PLACER_BASE::MeanderSettings() const
240 {
241 return m_settings;
242 }
243
244
compareWithTolerance(long long int aValue,long long int aExpected,long long int aTolerance) const245 int MEANDER_PLACER_BASE::compareWithTolerance(
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
getSnappedStartPoint(LINKED_ITEM * aStartItem,VECTOR2I aStartPoint)257 VECTOR2I MEANDER_PLACER_BASE::getSnappedStartPoint( LINKED_ITEM* aStartItem, VECTOR2I aStartPoint )
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
lineLength(const ITEM_SET & aLine) const281 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 }
307