KiCad PCB EDA Suite
pns_meander.cpp
Go to the documentation of this file.
1 /*
2  * KiRouter - a push-and-(sometimes-)shove PCB router
3  *
4  * Copyright (C) 2013-2014 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 
22 #include <base_units.h> // God forgive me doing this...
23 
24 #include "pns_node.h"
25 #include "pns_itemset.h"
26 #include "pns_meander.h"
28 #include "pns_router.h"
29 #include "pns_debug_decorator.h"
30 
31 namespace PNS {
32 
34 {
35  return m_placer->MeanderSettings();
36 }
37 
38 
40 {
41  return m_placer->MeanderSettings();
42 }
43 
44 
45 void MEANDERED_LINE::MeanderSegment( const SEG& aBase, int aBaseIndex )
46 {
47  double base_len = aBase.Length();
48 
50 
51  bool side = true;
52  VECTOR2D dir( aBase.B - aBase.A );
53 
54  if( !m_dual )
55  AddCorner( aBase.A );
56 
57  bool turning = false;
58  bool started = false;
59 
60  m_last = aBase.A;
61 
62  do
63  {
65 
67  m.SetBaseIndex( aBaseIndex );
68 
69  double thr = (double) m.spacing();
70 
71  bool fail = false;
72  double remaining = base_len - ( m_last - aBase.A ).EuclideanNorm();
73 
74  if( remaining < Settings( ).m_step )
75  break;
76 
77  if( remaining > 3.0 * thr )
78  {
79  if( !turning )
80  {
81  for( int i = 0; i < 2; i++ )
82  {
83  if( m.Fit( MT_CHECK_START, aBase, m_last, i ) )
84  {
85  turning = true;
86  AddMeander( new MEANDER_SHAPE( m ) );
87  side = !i;
88  started = true;
89  break;
90  }
91  }
92 
93  if( !turning )
94  {
95  fail = true;
96 
97  for( int i = 0; i < 2; i++ )
98  {
99  if( m.Fit( MT_SINGLE, aBase, m_last, i ) )
100  {
101  AddMeander( new MEANDER_SHAPE( m ) );
102  fail = false;
103  started = false;
104  side = !i;
105  break;
106  }
107  }
108  }
109  } else {
110  bool rv = m.Fit( MT_CHECK_FINISH, aBase, m_last, side );
111 
112  if( rv )
113  {
114  m.Fit( MT_TURN, aBase, m_last, side );
115  AddMeander( new MEANDER_SHAPE( m ) );
116  started = true;
117  } else {
118  m.Fit( MT_FINISH, aBase, m_last, side );
119  started = false;
120  AddMeander( new MEANDER_SHAPE( m ) );
121  turning = false;
122  }
123 
124  side = !side;
125  }
126  } else if( started )
127  {
128  bool rv = m.Fit( MT_FINISH, aBase, m_last, side );
129  if( rv )
130  AddMeander( new MEANDER_SHAPE( m ) );
131 
132  break;
133 
134  } else {
135  fail = true;
136  }
137 
138  remaining = base_len - ( m_last - aBase.A ).EuclideanNorm( );
139 
140  if( remaining < Settings( ).m_step )
141  break;
142 
143  if( fail )
144  {
147  tmp.SetBaseIndex( aBaseIndex );
148 
149  int nextP = tmp.spacing() - 2 * tmp.cornerRadius() + Settings().m_step;
150  VECTOR2I pn = m_last + dir.Resize( nextP );
151 
152  if( aBase.Contains( pn ) && !m_dual )
153  {
154  AddCorner( pn );
155  } else
156  break;
157  }
158 
159 
160  } while( true );
161 
162  if( !m_dual )
163  AddCorner( aBase.B );
164 }
165 
166 
168 {
169  // TODO: fix diff-pair meandering so we can use non-100% radii
170  int rPercent = m_dual ? 100 : Settings().m_cornerRadiusPercentage;
171 
172  return (int64_t) spacing() * rPercent / 200;
173 }
174 
175 
177 {
178  if( !m_dual )
179  {
180  return std::max( m_width + m_placer->Clearance(), Settings().m_spacing );
181  }
182  else
183  {
184  int sp = m_width + m_placer->Clearance() + ( 2 * std::abs( m_baselineOffset ) );
185  return std::max( sp, Settings().m_spacing );
186  }
187 }
188 
189 
191 {
192  SHAPE_LINE_CHAIN lc;
193 
194  if( aDir.EuclideanNorm( ) == 0.0f )
195  {
196  lc.Append( aP );
197  return lc;
198  }
199 
200  VECTOR2D dir_u( aDir );
201  VECTOR2D dir_v( aDir.Perpendicular( ) );
202  VECTOR2D p = aP;
203  lc.Append( ( int ) p.x, ( int ) p.y );
204 
205 
206  // fixme: refactor
208  {
209  case MEANDER_STYLE_ROUND:
210  {
211  VECTOR2D center = aP + dir_v * ( aSide ? -1.0 : 1.0 );
212 
213  lc.Append( SHAPE_ARC( center, aP, ( aSide ? -90 : 90 ) ) );
214  }
215  break;
216 
218  {
219  double radius = (double) aDir.EuclideanNorm();
220  double correction = 0;
221  if( m_dual && radius > m_meanCornerRadius )
222  correction = (double)( -2 * abs(m_baselineOffset) ) * tan( 22.5 * M_PI / 180.0 );
223 
224  VECTOR2D dir_cu = dir_u.Resize( correction );
225  VECTOR2D dir_cv = dir_v.Resize( correction );
226 
227  p = aP - dir_cu;
228  lc.Append( ( int ) p.x, ( int ) p.y );
229  p = aP + dir_u + (dir_v + dir_cv) * ( aSide ? -1.0 : 1.0 );
230  lc.Append( ( int ) p.x, ( int ) p.y );
231  }
232  break;
233  }
234 
235  p = aP + dir_u + dir_v * ( aSide ? -1.0 : 1.0 );
236  lc.Append( ( int ) p.x, ( int ) p.y );
237 
238  return lc;
239 }
240 
241 
242 void MEANDER_SHAPE::start( SHAPE_LINE_CHAIN* aTarget, const VECTOR2D& aWhere, const VECTOR2D& aDir )
243 {
244  m_currentTarget = aTarget;
246  m_currentTarget->Append( aWhere );
247  m_currentDir = aDir;
248  m_currentPos = aWhere;
249 }
250 
251 
252 void MEANDER_SHAPE::forward( int aLength )
253 {
254  m_currentPos += m_currentDir.Resize( aLength );
256 }
257 
258 
259 void MEANDER_SHAPE::turn( int aAngle )
260 {
261  m_currentDir = m_currentDir.Rotate( (double) aAngle * M_PI / 180.0 );
262 }
263 
264 
265 void MEANDER_SHAPE::miter( int aRadius, bool aSide )
266 {
267  if( aRadius <= 0 )
268  {
269  turn( aSide ? -90 : 90 );
270  return;
271  }
272 
273  VECTOR2D dir = m_currentDir.Resize( (double) aRadius );
274  SHAPE_LINE_CHAIN lc = makeMiterShape( m_currentPos, dir, aSide );
275 
276  m_currentPos = lc.CPoint( -1 );
277  m_currentDir = dir.Rotate( aSide ? -M_PI / 2.0 : M_PI / 2.0 );
278 
279  m_currentTarget->Append( lc );
280 }
281 
282 
283 void MEANDER_SHAPE::uShape( int aSides, int aCorner, int aTop )
284 {
285  forward( aSides );
286  miter( aCorner, true );
287  forward( aTop );
288  miter( aCorner, true );
289  forward( aSides );
290 }
291 
292 
294  bool aSide, MEANDER_TYPE aType, int aAmpl, int aBaselineOffset )
295 {
296  int cr = cornerRadius();
297  int offset = aBaselineOffset;
298  int spc = spacing();
299 
300  if( aSide )
301  offset *= -1;
302 
303  VECTOR2D dir_u_b( aDir.Resize( offset ) );
304  VECTOR2D dir_v_b( dir_u_b.Perpendicular() );
305 
306  if( 2 * cr > aAmpl )
307  {
308  cr = aAmpl / 2;
309  }
310 
311  if( 2 * cr > spc )
312  {
313  cr = spc / 2;
314  }
315 
316  m_meanCornerRadius = cr;
317 
318  SHAPE_LINE_CHAIN lc;
319 
320  start( &lc, aP + dir_v_b, aDir );
321 
322  switch( aType )
323  {
324  case MT_EMPTY:
325  {
326  lc.Append( aP + dir_v_b + aDir );
327  break;
328  }
329  case MT_START:
330  {
331  miter( cr - offset, false );
332  uShape( aAmpl - 2 * cr + std::abs( offset ), cr + offset, spc - 2 * cr );
333  forward( std::min( cr - offset, cr + offset ) );
334  forward( std::abs( offset ) );
335 
336  break;
337  }
338 
339  case MT_FINISH:
340  {
341  start( &lc, aP - dir_u_b, aDir );
342  turn( 90 );
343  forward( std::min( cr - offset, cr + offset ) );
344  forward( std::abs( offset ) );
345  uShape( aAmpl - 2 * cr + std::abs( offset ), cr + offset, spc - 2 * cr );
346  miter( cr - offset, false );
347  break;
348  }
349 
350  case MT_TURN:
351  {
352  start( &lc, aP - dir_u_b, aDir );
353  turn( 90 );
354  forward( std::abs( offset ) );
355  uShape( aAmpl - cr, cr + offset, spc - 2 * cr );
356  forward( std::abs( offset ) );
357  break;
358  }
359 
360  case MT_SINGLE:
361  {
362  miter( cr - offset, false );
363  uShape( aAmpl - 2 * cr + std::abs( offset ), cr + offset, spc - 2 * cr );
364  miter( cr - offset, false );
365  lc.Append( aP + dir_v_b + aDir.Resize( 2 * spc ) );
366  break;
367  }
368 
369  default:
370  break;
371  }
372 
373  if( aSide )
374  {
375  SEG axis( aP, aP + aDir );
376 
377  lc.Mirror( axis );
378  }
379 
380  return lc;
381 }
382 
383 
385 {
386  for( int i = m_meanders.size() - 1; i >= 0; i-- )
387  {
388  MEANDER_SHAPE* m = m_meanders[i];
389 
390  if( m->Type() == MT_EMPTY || m->Type() == MT_CORNER )
391  continue;
392 
393  const SEG& b1 = aShape->BaseSegment();
394  const SEG& b2 = m->BaseSegment();
395 
396  if( b1.ApproxParallel( b2 ) )
397  continue;
398 
399  int n = m->CLine( 0 ).SegmentCount();
400 
401  for( int j = n - 1; j >= 0; j-- )
402  if( aShape->CLine( 0 ).Collide( m->CLine( 0 ) .CSegment( j ), aClearance ) )
403  return false;
404  }
405 
406  return true;
407 }
408 
409 
410 bool MEANDER_SHAPE::Fit( MEANDER_TYPE aType, const SEG& aSeg, const VECTOR2I& aP, bool aSide )
411 {
412  const MEANDER_SETTINGS& st = Settings();
413 
414  bool checkMode = false;
415  MEANDER_TYPE prim1, prim2;
416 
417  if( aType == MT_CHECK_START )
418  {
419  prim1 = MT_START;
420  prim2 = MT_TURN;
421  checkMode = true;
422  }
423  else if( aType == MT_CHECK_FINISH )
424  {
425  prim1 = MT_TURN;
426  prim2 = MT_FINISH;
427  checkMode = true;
428  }
429 
430  if( checkMode )
431  {
434 
437 
438  bool c1 = m1.Fit( prim1, aSeg, aP, aSide );
439  bool c2 = false;
440 
441  if( c1 )
442  c2 = m2.Fit( prim2, aSeg, m1.End(), !aSide );
443 
444  if( c1 && c2 )
445  {
446  m_type = prim1;
447  m_shapes[0] = m1.m_shapes[0];
448  m_shapes[1] = m1.m_shapes[1];
449  m_baseSeg =aSeg;
450  m_p0 = aP;
451  m_side = aSide;
452  m_amplitude = m1.Amplitude();
453  m_dual = m1.m_dual;
454  m_baseSeg = m1.m_baseSeg;
458  return true;
459  } else
460  return false;
461  }
462 
463  int minAmpl = st.m_minAmplitude;
464  int maxAmpl = st.m_maxAmplitude;
465 
466  if( m_dual )
467  {
468  minAmpl = std::max( minAmpl, 2 * std::abs( m_baselineOffset ) );
469  maxAmpl = std::max( maxAmpl, 2 * std::abs( m_baselineOffset ) );
470  }
471 
472  for( int ampl = maxAmpl; ampl >= minAmpl; ampl -= st.m_step )
473  {
474  if( m_dual )
475  {
476  m_shapes[0] = genMeanderShape( aP, aSeg.B - aSeg.A, aSide, aType, ampl, m_baselineOffset );
477  m_shapes[1] = genMeanderShape( aP, aSeg.B - aSeg.A, aSide, aType, ampl, -m_baselineOffset );
478  }
479  else
480  {
481  m_shapes[0] = genMeanderShape( aP, aSeg.B - aSeg.A, aSide, aType, ampl, 0 );
482  }
483 
484  m_type = aType;
485  m_baseSeg = aSeg;
486  m_p0 = aP;
487  m_side = aSide;
488  m_amplitude = ampl;
489 
491 
492  if( m_placer->CheckFit( this ) )
493  return true;
494  }
495 
496  return false;
497 }
498 
499 
501 {
503 
504  if( m_dual )
506 
508 }
509 
510 
511 void MEANDER_SHAPE::Resize( int aAmpl )
512 {
513  if( aAmpl < 0 )
514  return;
515 
516  m_amplitude = aAmpl;
517 
518  Recalculate();
519 }
520 
521 
523 {
525 
527 
528  m_type = MT_EMPTY;
529 
531 
532  if( m_dual )
534 }
535 
536 
537 void MEANDERED_LINE::AddCorner( const VECTOR2I& aA, const VECTOR2I& aB )
538 {
540 
541  m->MakeCorner( aA, aB );
542  m_last = aA;
543 
544  m_meanders.push_back( m );
545 }
546 
547 
549 {
550  SetType( MT_CORNER );
551  m_shapes[0].Clear();
552  m_shapes[1].Clear();
553  m_shapes[0].Append( aP1 );
554  m_shapes[1].Append( aP2 );
555  m_clippedBaseSeg.A = aP1;
556  m_clippedBaseSeg.B = aP1;
557 }
558 
559 
561 {
562  m_last = aShape->BaseSegment().B;
563  m_meanders.push_back( aShape );
564 }
565 
566 
568 {
569  for( MEANDER_SHAPE* m : m_meanders )
570  {
571  delete m;
572  }
573 
574  m_meanders.clear( );
575 }
576 
577 
579 {
580  return m_clippedBaseSeg.Length();
581 }
582 
583 
585 {
586  return CLine( 0 ).Length();
587 }
588 
589 
591 {
592  if( m_dual )
593  {
594  VECTOR2I midpA = ( CLine( 0 ).CPoint( 0 ) + CLine( 1 ).CPoint( 0 ) ) / 2;
595  VECTOR2I midpB = ( CLine( 0 ).CPoint( -1 ) + CLine( 1 ).CPoint( -1 ) ) / 2;
596 
599  }
600  else
601  {
602  m_clippedBaseSeg.A = m_baseSeg.LineProject( CLine( 0 ).CPoint( 0 ) );
603  m_clippedBaseSeg.B = m_baseSeg.LineProject( CLine( 0 ).CPoint( -1 ) );
604  }
605 }
606 
607 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int Length() const
Return the length (this).
Definition: seg.h:350
SHAPE_LINE_CHAIN genMeanderShape(VECTOR2D aP, VECTOR2D aDir, bool aSide, MEANDER_TYPE aType, int aAmpl, int aBaselineOffset=0)
Recalculate the clipped baseline after the parameters of the meander have been changed.
long long int Length() const
Return length of the line chain in Euclidean metric.
int m_minAmplitude
Maximum meandering amplitude.
Definition: pns_meander.h:76
void uShape(int aSides, int aCorner, int aTop)
Generate a 90-degree circular arc.
void SetBaselineOffset(int aOffset)
Set the parallel offset between the base segment and the meandered line.
Definition: pns_meander.h:283
bool CheckSelfIntersections(MEANDER_SHAPE *aShape, int aClearance)
Check if the given shape is intersecting with any other meander in the current line.
int BaselineLength() const
bool m_side
The actual shapes (0 used for single, both for dual).
Definition: pns_meander.h:353
The geometry of a single meander.
Definition: pns_meander.h:109
VECTOR2I End() const
Definition: pns_meander.h:214
Implementation of conversion functions that require both schematic and board internal units.
MEANDER_PLACER_BASE * m_placer
Definition: pns_meander.h:473
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
MEANDER_TYPE
Shapes of available meanders.
Definition: pns_meander.h:37
VECTOR2I m_p0
Base segment (unclipped).
Definition: pns_meander.h:344
void AddCorner(const VECTOR2I &aA, const VECTOR2I &aB=VECTOR2I(0, 0))
Create a dummy meander shape representing a line corner.
void MeanderSegment(const SEG &aSeg, int aBaseIndex=0)
Fit maximum amplitude meanders on a given segment and adds to the current line.
Definition: pns_meander.cpp:45
virtual int Clearance()
Return the clearance of the track(s) being length tuned.
SHAPE_LINE_CHAIN * m_currentTarget
Definition: pns_meander.h:368
std::vector< MEANDER_SHAPE * > m_meanders
Definition: pns_meander.h:474
void Clear()
Clear the line geometry, removing all corners and meanders.
int m_baseIndex
The current turtle direction.
Definition: pns_meander.h:359
MEANDER_TYPE Type() const
Definition: pns_meander.h:144
Dimensions for the meandering algorithm.
Definition: pns_meander.h:57
void Recalculate()
Recalculate the line chain representing the meander's shape.
virtual bool CheckFit(MEANDER_SHAPE *aShape)
Checks if it's OK to place the shape aShape (i.e.
MEANDER_STYLE m_cornerStyle
Rounding percentage (0 - 100).
Definition: pns_meander.h:94
const MEANDER_SETTINGS & Settings() const
Definition: pns_meander.cpp:39
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
void Resize(int aAmpl)
Change the amplitude of the meander shape to aAmpl and recalculates the resulting line chain.
void miter(int aRadius, bool aSide)
Tell the turtle to draw an U-like shape.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
void MakeCorner(VECTOR2I aP1, VECTOR2I aP2=VECTOR2I(0, 0))
Create a dummy meander shape representing a line corner.
int m_step
Length PadToDie.
Definition: pns_meander.h:85
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:268
bool ApproxParallel(const SEG &aSeg) const
Definition: seg.h:290
void start(SHAPE_LINE_CHAIN *aTarget, const VECTOR2D &aWhere, const VECTOR2D &aDir)
Move turtle forward by aLength.
void AddMeander(MEANDER_SHAPE *aShape)
Add a new meander shape to the meandered line.
MEANDER_TYPE m_type
The placer that placed this meander.
Definition: pns_meander.h:323
SHAPE_LINE_CHAIN makeMiterShape(VECTOR2D aP, VECTOR2D aDir, bool aSide)
Produce a meander shape of given type.
const SHAPE_LINE_CHAIN & CLine(int aShape) const
Definition: pns_meander.h:222
int m_cornerRadiusPercentage
Allowable tuning error.
Definition: pns_meander.h:97
int m_meanCornerRadius
First point of the meandered line.
Definition: pns_meander.h:341
const SEG & BaseSegment() const
Return the base segment the meander was fitted to.
Definition: pns_meander.h:249
void turn(int aAngle)
Tell the turtle to draw a mitered corner of given radius and turn direction.
MEANDER_PLACER_BASE * m_placer
Dual or single line.
Definition: pns_meander.h:326
int m_width
Amplitude of the meander.
Definition: pns_meander.h:332
SHAPE_LINE_CHAIN m_shapes[2]
Index of the meandered segment in the base line.
Definition: pns_meander.h:356
int MaxTunableLength() const
int SegmentCount() const
Return the number of segments in this line chain.
void forward(int aLength)
Turn the turtle by aAngle.
int m_baselineOffset
Average radius of meander corners (for correction of DP meanders).
Definition: pns_meander.h:338
const MEANDER_SETTINGS & Settings() const
Definition: pns_meander.cpp:33
int m_amplitude
Offset wrs the base segment (dual only).
Definition: pns_meander.h:335
bool Fit(MEANDER_TYPE aType, const SEG &aSeg, const VECTOR2I &aP, bool aSide)
Attempt to fit a meander of a given type onto a segment, avoiding collisions with other board feature...
Definition: seg.h:40
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
void MakeEmpty()
Replace the meander with straight bypass line(s), effectively clearing it.
VECTOR2< T > Rotate(double aAngle) const
Rotate the vector by a given angle.
Definition: vector2d.h:371
void SetBaseIndex(int aIndex)
Set an auxiliary index of the segment being meandered in its original LINE.
Definition: pns_meander.h:152
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
int cornerRadius() const
Return sanitized spacing value.
VECTOR2I A
Definition: seg.h:48
SEG m_baseSeg
Base segment (clipped).
Definition: pns_meander.h:347
void Clear()
Remove all points from the line chain.
void updateBaseSegment()
Return sanitized corner radius value.
bool m_dual
Width of the line.
Definition: pns_meander.h:329
int m_spacing
Amplitude/spacing adjustment step.
Definition: pns_meander.h:82
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
int spacing() const
The type of meander.
Push and Shove diff pair dimensions (gap) settings dialog.
VECTOR2D m_currentPos
The line the turtle is drawing on.
Definition: pns_meander.h:365
virtual const MEANDER_SETTINGS & MeanderSettings() const
Return the current meandering configuration.
void SetType(MEANDER_TYPE aType)
Set the type of the meander.
Definition: pns_meander.h:136
int Amplitude() const
Definition: pns_meander.h:168
SEG m_clippedBaseSeg
Side (true = right).
Definition: pns_meander.h:350
VECTOR2D m_currentDir
The current turtle position.
Definition: pns_meander.h:362
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both).
int m_maxAmplitude
Meandering period/spacing (see dialog picture for explanation).
Definition: pns_meander.h:79
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49