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