Horizon
pns_diff_pair.h
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 
23 #ifndef __PNS_DIFF_PAIR_H
24 #define __PNS_DIFF_PAIR_H
25 
26 #include <vector>
27 
28 #include "pns_line.h"
29 #include "pns_via.h"
30 #include "pns_link_holder.h"
31 
32 #include "ranged_num.h"
33 
34 namespace PNS {
35 
36 class DIFF_PAIR;
37 
44 {
45 public:
46  DP_GATEWAY( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN, bool aIsDiagonal,
47  int aAllowedEntryAngles = DIRECTION_45::ANG_OBTUSE, int aPriority = 0 ) :
48  m_anchorP( aAnchorP ),
49  m_anchorN( aAnchorN ), m_isDiagonal( aIsDiagonal ),
50  m_allowedEntryAngles( aAllowedEntryAngles ), m_priority( aPriority )
51  {
52  m_hasEntryLines = false;
53  }
54 
55  ~DP_GATEWAY()
56  {
57  }
58 
62  bool IsDiagonal() const
63  {
64  return m_isDiagonal;
65  }
66 
67  const VECTOR2I& AnchorP() const { return m_anchorP; }
68 
69  const VECTOR2I& AnchorN() const { return m_anchorN; }
70 
74  int AllowedAngles () const { return m_allowedEntryAngles; }
75 
79  int Priority() const
80  {
81  return m_priority;
82  }
83 
84  void SetPriority(int aPriority)
85  {
86  m_priority = aPriority;
87  }
88 
89  void SetEntryLines( const SHAPE_LINE_CHAIN& aEntryP, const SHAPE_LINE_CHAIN& aEntryN )
90  {
91  m_entryP = aEntryP;
92  m_entryN = aEntryN;
93  m_hasEntryLines = true;
94  }
95 
96  const SHAPE_LINE_CHAIN& EntryP() const { return m_entryP; }
97  const SHAPE_LINE_CHAIN& EntryN() const { return m_entryN; }
98  const DIFF_PAIR Entry() const ;
99 
100  void Reverse();
101 
102  bool HasEntryLines () const
103  {
104  return m_hasEntryLines;
105  }
106 
107 private:
108  SHAPE_LINE_CHAIN m_entryP, m_entryN;
109  bool m_hasEntryLines;
110  VECTOR2I m_anchorP, m_anchorN;
111  bool m_isDiagonal;
112  int m_allowedEntryAngles;
113  int m_priority;
114 };
115 
120 {
121 public:
123  m_primP( nullptr ), m_primN( nullptr ) {};
124 
125  DP_PRIMITIVE_PAIR( const DP_PRIMITIVE_PAIR& aOther );
126  DP_PRIMITIVE_PAIR( ITEM* aPrimP, ITEM* aPrimN );
127  DP_PRIMITIVE_PAIR( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN );
128 
130 
131  void SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN );
132 
133  const VECTOR2I& AnchorP() const { return m_anchorP; }
134  const VECTOR2I& AnchorN() const { return m_anchorN; }
135 
136  DP_PRIMITIVE_PAIR& operator=( const DP_PRIMITIVE_PAIR& aOther );
137 
138  ITEM* PrimP() const { return m_primP; }
139  ITEM* PrimN() const { return m_primN; }
140 
141  bool Directional() const;
142 
143  DIRECTION_45 DirP() const;
144  DIRECTION_45 DirN() const;
145 
146 
147  void CursorOrientation( const VECTOR2I& aCursorPos, VECTOR2I& aMidpoint,
148  VECTOR2I& aDirection ) const;
149 
150  void dump()
151  {
152  printf( "-- Prim-P %p anchor [%d, %d]\n", m_primP, m_anchorP.x, m_anchorP.y );
153  printf( "-- Prim-N %p anchor [%d, %d]\n", m_primN, m_anchorN.x, m_anchorN.y );
154  }
155 
156 private:
157  DIRECTION_45 anchorDirection( const ITEM* aItem, const VECTOR2I& aP ) const;
158 
159  ITEM* m_primP;
160  ITEM* m_primN;
161  VECTOR2I m_anchorP, m_anchorN;
162 };
163 
168 {
169 public:
170  DP_GATEWAYS( int aGap ):
171  m_gap( aGap ),
172  m_viaGap( aGap )
173  {
174  // Do not leave uninitialized members, and keep static analyzer quiet:
175  m_viaDiameter = 0;
176  m_fitVias = true;
177  }
178 
179  void Clear() { m_gateways.clear(); }
180 
181  void SetFitVias( bool aEnable, int aDiameter = 0, int aViaGap = -1 )
182  {
183  m_fitVias = aEnable;
184  m_viaDiameter = aDiameter;
185 
186  if( aViaGap < 0 )
187  m_viaGap = m_gap;
188  else
189  m_viaGap = aViaGap;
190  }
191 
192 
193  void BuildForCursor( const VECTOR2I& aCursorPos );
194  void BuildOrthoProjections( DP_GATEWAYS& aEntries, const VECTOR2I& aCursorPos,
195  int aOrthoScore );
196  void BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries = false,
197  bool aViaMode = false );
198  void BuildFromPrimitivePair( const DP_PRIMITIVE_PAIR& aPair, bool aPreferDiagonal );
199 
200  bool FitGateways( DP_GATEWAYS& aEntry, DP_GATEWAYS& aTarget, bool aPrefDiagonal,
201  DIFF_PAIR& aDp );
202 
203  std::vector<DP_GATEWAY>& Gateways() { return m_gateways; }
204 
205  const std::vector<DP_GATEWAY>& CGateways() const { return m_gateways; }
206 
207  void FilterByOrientation( int aAngleMask, DIRECTION_45 aRefOrientation );
208 
209 private:
210  struct DP_CANDIDATE
211  {
212  SHAPE_LINE_CHAIN p, n;
213  VECTOR2I gw_p, gw_n;
214  int score;
215  };
216 
217  bool checkDiagonalAlignment( const VECTOR2I& a, const VECTOR2I& b ) const;
218  void buildDpContinuation( const DP_PRIMITIVE_PAIR& aPair, bool aIsDiagonal );
219  void buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n );
220 
221  int m_gap;
222  int m_viaGap;
223  int m_viaDiameter;
224  bool m_fitVias;
225 
226  std::vector<DP_GATEWAY> m_gateways;
227 };
228 
229 
234 class DIFF_PAIR : public LINK_HOLDER
235 {
236 public:
238  {
239  COUPLED_SEGMENTS ( const SEG& aCoupledP, const SEG& aParentP, int aIndexP,
240  const SEG& aCoupledN, const SEG& aParentN, int aIndexN ) :
241  coupledP( aCoupledP ),
242  coupledN( aCoupledN ),
243  parentP( aParentP ),
244  parentN( aParentN ),
245  indexP( aIndexP ),
246  indexN( aIndexN )
247  {}
248 
249  SEG coupledP;
250  SEG coupledN;
251  SEG parentP;
252  SEG parentN;
253  int indexP;
254  int indexN;
255  };
256 
257  typedef std::vector<COUPLED_SEGMENTS> COUPLED_SEGMENTS_VEC;
258 
259  DIFF_PAIR() :
260  LINK_HOLDER( ITEM::DIFF_PAIR_T ),
261  m_hasVias( false )
262  {
263  // Initialize some members, to avoid uninitialized variables.
264  m_net_p = 0;
265  m_net_n = 0;;
266  m_width = 0;
267  m_gap = 0;
268  m_viaGap = 0;
269  m_maxUncoupledLength = 0;
270  m_chamferLimit = 0;
271  }
272 
273  DIFF_PAIR( int aGap ) :
274  LINK_HOLDER( ITEM::DIFF_PAIR_T ),
275  m_hasVias( false )
276  {
277  m_gapConstraint = aGap;
278 
279  // Initialize other members, to avoid uninitialized variables.
280  m_net_p = 0;
281  m_net_n = 0;;
282  m_width = 0;
283  m_gap = 0;
284  m_viaGap = 0;
285  m_maxUncoupledLength = 0;
286  m_chamferLimit = 0;
287  }
288 
289  DIFF_PAIR( const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN& aN, int aGap = 0 ) :
290  LINK_HOLDER( ITEM::DIFF_PAIR_T ),
291  m_n( aN ),
292  m_p( aP ),
293  m_hasVias( false )
294  {
295  m_gapConstraint = aGap;
296 
297  // Initialize other members, to avoid uninitialized variables.
298  m_net_p = 0;
299  m_net_n = 0;;
300  m_width = 0;
301  m_gap = 0;
302  m_viaGap = 0;
303  m_maxUncoupledLength = 0;
304  m_chamferLimit = 0;
305  }
306 
307  DIFF_PAIR( const LINE &aLineP, const LINE &aLineN, int aGap = 0 ) :
308  LINK_HOLDER( ITEM::DIFF_PAIR_T ),
309  m_line_p( aLineP ),
310  m_line_n( aLineN ),
311  m_hasVias( false )
312  {
313  m_gapConstraint = aGap;
314  m_net_p = aLineP.Net();
315  m_net_n = aLineN.Net();
316  m_p = aLineP.CLine();
317  m_n = aLineN.CLine();
318 
319  // Do not leave uninitialized members, and keep static analyzer quiet:
320  m_width = 0;
321  m_gap = 0;
322  m_viaGap = 0;
323  m_maxUncoupledLength = 0;
324  m_chamferLimit = 0;
325  }
326 
327  static inline bool ClassOf( const ITEM* aItem )
328  {
329  return aItem && ITEM::DIFF_PAIR_T == aItem->Kind();
330  }
331 
332  DIFF_PAIR* Clone() const override
333  {
334  assert( false );
335  return nullptr;
336  }
337 
338  virtual void ClearLinks() override
339  {
340  m_links.clear();
341  m_line_p.ClearLinks();
342  m_line_n.ClearLinks();
343  }
344 
345  static DIFF_PAIR* AssembleDp( LINE *aLine );
346 
347  void SetShape( const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN& aN, bool aSwapLanes = false )
348  {
349  if( aSwapLanes )
350  {
351  m_p = aN;
352  m_n = aP;
353  }
354  else
355  {
356  m_p = aP;
357  m_n = aN;
358  }
359  }
360 
361  void SetShape( const DIFF_PAIR& aPair )
362  {
363  m_p = aPair.m_p;
364  m_n = aPair.m_n;
365  }
366 
367  void SetNets( int aP, int aN )
368  {
369  m_net_p = aP;
370  m_net_n = aN;
371  }
372 
373  void SetWidth( int aWidth )
374  {
375  m_width = aWidth;
376  m_n.SetWidth( aWidth );
377  m_p.SetWidth( aWidth );
378  }
379 
380  int Width() const { return m_width; }
381 
382  void SetGap( int aGap )
383  {
384  m_gap = aGap;
385  m_gapConstraint = RANGED_NUM<int>( m_gap, 10000, 10000 );
386  }
387 
388  int Gap() const
389  {
390  return m_gap;
391  }
392 
393  void AppendVias( const VIA &aViaP, const VIA& aViaN )
394  {
395  m_hasVias = true;
396  m_via_p = aViaP;
397  m_via_n = aViaN;
398  }
399 
400  void RemoveVias()
401  {
402  m_hasVias = false;
403  }
404 
405  bool EndsWithVias() const
406  {
407  return m_hasVias;
408  }
409 
410  void SetViaDiameter( int aDiameter )
411  {
412  m_via_p.SetDiameter( aDiameter );
413  m_via_n.SetDiameter( aDiameter );
414  }
415 
416  void SetViaDrill( int aDrill )
417  {
418  m_via_p.SetDrill( aDrill );
419  m_via_n.SetDrill( aDrill );
420  }
421 
422  int NetP() const
423  {
424  return m_net_p;
425  }
426 
427  int NetN() const
428  {
429  return m_net_n;
430  }
431 
432  LINE& PLine()
433  {
434  if( !m_line_p.IsLinked() )
435  updateLine( m_line_p, m_p, m_net_p, m_via_p );
436 
437  return m_line_p;
438  }
439 
440  LINE& NLine()
441  {
442  if( !m_line_n.IsLinked() )
443  updateLine( m_line_n, m_n, m_net_n, m_via_n );
444 
445  return m_line_n;
446  }
447 
448  DP_PRIMITIVE_PAIR EndingPrimitives();
449 
450  double CoupledLength() const;
451  double TotalLength() const;
452  double CoupledLengthFactor() const;
453  double Skew() const;
454 
455  void CoupledSegmentPairs( COUPLED_SEGMENTS_VEC& aPairs ) const;
456 
457  void Clear()
458  {
459  m_n.Clear();
460  m_p.Clear();
461  }
462 
463  void Append( const DIFF_PAIR& aOther )
464  {
465  m_n.Append( aOther.m_n );
466  m_p.Append( aOther.m_p );
467  }
468 
469  bool Empty() const
470  {
471  return ( m_n.SegmentCount() == 0 ) || ( m_p.SegmentCount() == 0 );
472  }
473 
474  const SHAPE_LINE_CHAIN& CP() const { return m_p; }
475  const SHAPE_LINE_CHAIN& CN() const { return m_n; }
476 
477  bool BuildInitial( const DP_GATEWAY& aEntry, const DP_GATEWAY& aTarget, bool aPrefDiagonal );
478  bool CheckConnectionAngle( const DIFF_PAIR &aOther, int allowedAngles ) const;
479  int CoupledLength( const SEG& aP, const SEG& aN ) const;
480 
481  int64_t CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const;
482 
483  const RANGED_NUM<int> GapConstraint() const
484  {
485  return m_gapConstraint;
486  }
487 
488 private:
489  void updateLine( LINE &aLine, const SHAPE_LINE_CHAIN& aShape, int aNet, const VIA& aVia )
490  {
491  aLine.SetShape( aShape );
492  aLine.SetWidth( m_width );
493  aLine.SetNet( aNet );
494  aLine.SetLayer( Layers().Start() );
495 
496  if( m_hasVias )
497  aLine.AppendVia( aVia );
498  else
499  aLine.RemoveVia();
500  }
501 
502  SHAPE_LINE_CHAIN m_n, m_p;
503  LINE m_line_p, m_line_n;
504  VIA m_via_p, m_via_n;
505 
506  bool m_hasVias;
507  int m_net_p, m_net_n;
508  int m_width;
509  int m_gap;
510  int m_viaGap;
511  int m_maxUncoupledLength;
512  int m_chamferLimit;
513  RANGED_NUM<int> m_gapConstraint;
514 };
515 
516 }
517 
518 #endif
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
Basic class for a differential pair.
Definition: pns_diff_pair.h:235
DIFF_PAIR * Clone() const override
Return a deep copy of the item.
Definition: pns_diff_pair.h:332
virtual void ClearLinks() override
Return the number of segments that were assembled together to form this line.
Definition: pns_diff_pair.h:338
A set of gateways calculated for the cursor or starting/ending primitive pair.
Definition: pns_diff_pair.h:168
Define a "gateway" for routing a differential pair - e.g.
Definition: pns_diff_pair.h:44
bool IsDiagonal() const
Definition: pns_diff_pair.h:62
int AllowedAngles() const
Definition: pns_diff_pair.h:74
int Priority() const
Definition: pns_diff_pair.h:79
Store starting/ending primitives (pads, vias or segments) for a differential pair.
Definition: pns_diff_pair.h:120
Base class for PNS router board items.
Definition: pns_item.h:57
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:61
Definition: seg.h:41
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition: shape_line_chain.h:81
void Clear()
Remove all points from the line chain.
Definition: shape_line_chain.h:242
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Definition: shape_line_chain.h:495
int SegmentCount() const
Return the number of segments in this line chain.
Definition: shape_line_chain.h:295
void SetWidth(int aWidth)
Set the width of all segments in the chain.
Definition: shape_line_chain.h:275
Definition: pns_diff_pair.h:238