KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_diff_pair.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 The 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
22#include <cstdio>
23#include <cstdlib>
24#include <cmath>
25#include <limits>
26
27#include <algorithm>
28
29#include <geometry/shape_rect.h>
30
31#include "pns_diff_pair.h"
32#include "pns_router.h"
33
34namespace PNS {
35
36class LINE;
37
38
40{
41 m_primP = aPrimP->Clone();
42 m_primN = aPrimN->Clone();
43
44 m_anchorP = m_primP->Anchor( 0 );
45 m_anchorN = m_primN->Anchor( 0 );
46}
47
48
49void DP_PRIMITIVE_PAIR::SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN )
50{
51 m_anchorP = aAnchorP;
52 m_anchorN = aAnchorN;
53}
54
55
56DP_PRIMITIVE_PAIR::DP_PRIMITIVE_PAIR( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN )
57{
58 m_anchorP = aAnchorP;
59 m_anchorN = aAnchorN;
60 m_primP = m_primN = nullptr;
61}
62
63
65{
66 m_primP = m_primN = nullptr;
67
68 if( aOther.m_primP )
69 m_primP = aOther.m_primP->Clone();
70
71 if( aOther.m_primN )
72 m_primN = aOther.m_primN->Clone();
73
74 m_anchorP = aOther.m_anchorP;
75 m_anchorN = aOther.m_anchorN;
76}
77
78
80{
81 if( aOther.m_primP )
82 m_primP = aOther.m_primP->Clone();
83
84 if( aOther.m_primN )
85 m_primN = aOther.m_primN->Clone();
86
87 m_anchorP = aOther.m_anchorP;
88 m_anchorN = aOther.m_anchorN;
89
90 return *this;
91}
92
93
99
100
102{
103 if( !m_primP )
104 return false;
105
106 return m_primP->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T );
107}
108
109
111{
112 if( !aItem->OfKind ( ITEM::SEGMENT_T | ITEM::ARC_T ) )
113 return DIRECTION_45();
114
115 if( aItem->Anchor( 0 ) == aP )
116 return DIRECTION_45( aItem->Anchor( 0 ) - aItem->Anchor( 1 ) );
117 else
118 return DIRECTION_45( aItem->Anchor( 1 ) - aItem->Anchor( 0 ) );
119}
120
121
122void DP_PRIMITIVE_PAIR::CursorOrientation( const VECTOR2I& aCursorPos, VECTOR2I& aMidpoint,
123 VECTOR2I& aDirection ) const
124{
125 assert( m_primP && m_primN );
126
127 VECTOR2I aP, aN;
128
129 if( m_primP->OfKind( ITEM::SEGMENT_T ) && m_primN->OfKind( ITEM::SEGMENT_T ) )
130 {
131 aP = m_primP->Anchor( 1 );
132 aN = m_primN->Anchor( 1 );
133
134 // If both segments are parallel, use that as the direction. Otherwise, fall back on the
135 // direction perpendicular to the anchor points.
136 const SEG& segP = static_cast<SEGMENT*>( m_primP )->Seg();
137 const SEG& segN = static_cast<SEGMENT*>( m_primN )->Seg();
138
139 if( ( segP.B != segP.A ) && ( segN.B != segN.A ) && segP.ApproxParallel( segN ) )
140 {
141 aMidpoint = ( aP + aN ) / 2;
142 aDirection = segP.B - segP.A;
143 aDirection = aDirection.Resize( ( aP - aN ).EuclideanNorm() );
144 return;
145 }
146 }
147 else
148 {
149 aP = m_primP->Anchor( 0 );
150 aN = m_primN->Anchor( 0 );
151 }
152
153 aMidpoint = ( aP + aN ) / 2;
154 aDirection = ( aP - aN ).Perpendicular();
155
156 if( aDirection.Dot( aCursorPos - aMidpoint ) < 0 )
157 aDirection = -aDirection;
158}
159
160
165
166
171
172
173static DIRECTION_45::AngleType angle( const VECTOR2I &a, const VECTOR2I &b )
174{
175 DIRECTION_45 dir_a( a );
176 DIRECTION_45 dir_b( b );
177
178 return dir_a.Angle( dir_b );
179}
180
181
182static bool checkGap( const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap )
183{
184 SEG::ecoord gap_sq = SEG::Square( gap - 100 );
185
186 for( int i = 0; i < p.SegmentCount(); i++ )
187 {
188 for( int j = 0; j < n.SegmentCount() ; j++ )
189 {
190 SEG::ecoord dist_sq = p.CSegment( i ).SquaredDistance( n.CSegment( j ) );
191
192 if( dist_sq < gap_sq )
193 return false;
194 }
195 }
196
197 return true;
198}
199
200
202{
203 m_entryN = m_entryN.Reverse();
204 m_entryP = m_entryP.Reverse();
205}
206
207
208bool DIFF_PAIR::BuildInitial( const DP_GATEWAY& aEntry, const DP_GATEWAY &aTarget,
209 bool aPrefDiagonal )
210{
212 aPrefDiagonal );
214 aPrefDiagonal );
215
217
218 m_p = p;
219 m_n = n;
220
221 if( aEntry.HasEntryLines() )
222 {
223 if( !aEntry.Entry().CheckConnectionAngle( *this, mask ) )
224 return false;
225
226 m_p = aEntry.Entry().CP();
227 m_n = aEntry.Entry().CN();
228 m_p.Append( p );
229 m_n.Append( n );
230 }
231 else
232 {
233 m_p = p;
234 m_n = n;
235 }
236
238
239 if( aTarget.HasEntryLines() )
240 {
241 DP_GATEWAY t( aTarget );
242 t.Reverse();
243
244 if( !CheckConnectionAngle( t.Entry(), mask ) )
245 return false;
246
247 m_p.Append( t.Entry().CP() );
248 m_n.Append( t.Entry().CN() );
249 }
250
251 if( !checkGap( p, n, m_gapConstraint ) )
252 return false;
253
254 if( p.SelfIntersecting() || n.SelfIntersecting() )
255 return false;
256
257 if( p.Intersects( n ) )
258 return false;
259
260 return true;
261}
262
263
264bool DIFF_PAIR::CheckConnectionAngle( const DIFF_PAIR& aOther, int aAllowedAngles ) const
265{
266 bool checkP, checkN;
267
268 if( m_p.SegmentCount() == 0 || aOther.m_p.SegmentCount() == 0 )
269 {
270 checkP = true;
271 }
272 else
273 {
274 DIRECTION_45 p0( m_p.CSegment( -1 ) );
275 DIRECTION_45 p1( aOther.m_p.CSegment( 0 ) );
276
277 checkP = ( p0.Angle( p1 ) & aAllowedAngles ) != 0;
278 }
279
280 if( m_n.SegmentCount() == 0 || aOther.m_n.SegmentCount() == 0 )
281 {
282 checkN = true;
283 }
284 else
285 {
286 DIRECTION_45 n0( m_n.CSegment( -1 ) );
287 DIRECTION_45 n1( aOther.m_n.CSegment( 0 ) );
288
289 checkN = ( n0.Angle( n1 ) & aAllowedAngles ) != 0;
290 }
291
292 return checkP && checkN;
293}
294
295
297{
298 return DIFF_PAIR( m_entryP, m_entryN, 0 );
299}
300
301
302void DP_GATEWAYS::BuildOrthoProjections( DP_GATEWAYS& aEntries, const VECTOR2I& aCursorPos,
303 int aOrthoScore )
304{
305 for( const DP_GATEWAY& g : aEntries.Gateways() )
306 {
307 VECTOR2I midpoint( ( g.AnchorP() + g.AnchorN() ) / 2 );
308 SEG guide_s( midpoint, midpoint + VECTOR2I( 1, 0 ) );
309 SEG guide_d( midpoint, midpoint + VECTOR2I( 1, 1 ) );
310
311 VECTOR2I proj_s = guide_s.LineProject( aCursorPos );
312 VECTOR2I proj_d = guide_d.LineProject( aCursorPos );
313
314 int dist_s = ( proj_s - aCursorPos ).EuclideanNorm();
315 int dist_d = ( proj_d - aCursorPos ).EuclideanNorm();
316
317 VECTOR2I proj = ( dist_s < dist_d ? proj_s : proj_d );
318
319 DP_GATEWAYS targets( m_gap );
320
321 targets.m_viaGap = m_viaGap;
323 targets.m_fitVias = m_fitVias;
324
325 targets.BuildForCursor( proj );
326
327 for( DP_GATEWAY t : targets.Gateways() )
328 {
329 t.SetPriority( aOrthoScore );
330 m_gateways.push_back( t );
331 }
332 }
333}
334
335
336bool DP_GATEWAYS::FitGateways( DP_GATEWAYS& aEntry, DP_GATEWAYS& aTarget, bool aPrefDiagonal,
337 DIFF_PAIR& aDp )
338{
339 DP_CANDIDATE best;
340
341 int bestScore = -1000;
342 bool found = false;
343
344 for( const DP_GATEWAY& g_entry : aEntry.Gateways() )
345 {
346 for( const DP_GATEWAY& g_target : aTarget.Gateways() )
347 {
348 for( bool preferred : { false, true } )
349 {
350 int score = preferred ? 0 : -3;
351 score += g_entry.Priority();
352 score += g_target.Priority();
353
354 if( score >= bestScore )
355 {
356 DIFF_PAIR l( m_gap );
357
358 if( l.BuildInitial( g_entry, g_target, preferred ? aPrefDiagonal
359 : !aPrefDiagonal ) )
360 {
361 best.p = l.CP();
362 best.n = l.CN();
363 bestScore = score;
364 found = true;
365 }
366 }
367 }
368 }
369 }
370
371
372 if( found )
373 {
374 aDp.SetGap( m_gap );
375 aDp.SetShape( best.p, best.n );
376 return true;
377 }
378
379 return false;
380}
381
382
384{
385 VECTOR2I dir( std::abs (a.x - b.x), std::abs ( a.y - b.y ) );
386
387 return (dir.x == 0 && dir.y != 0) || (dir.x == dir.y) || (dir.y == 0 && dir.x != 0);
388}
389
390
391void DP_GATEWAYS::FilterByOrientation( int aAngleMask, DIRECTION_45 aRefOrientation )
392{
393 std::erase_if( m_gateways,
394 [aAngleMask, aRefOrientation]( const DP_GATEWAY& dp )
395 {
396 DIRECTION_45 orient( dp.AnchorP() - dp.AnchorN() );
397 return ( orient.Angle( aRefOrientation ) & aAngleMask );
398 } );
399}
400
401static VECTOR2I makeGapVector( VECTOR2I dir, int length )
402{
403 int l = length / 2;
404 VECTOR2I rv;
405
406 if( dir.EuclideanNorm() == 0 )
407 return dir;
408
409 do
410 {
411 rv = dir.Resize( l );
412 l++;
413 } while( ( rv * 2 ).EuclideanNorm() < length );
414
415 return rv;
416}
417
418void DP_GATEWAYS::BuildFromPrimitivePair( const DP_PRIMITIVE_PAIR& aPair, bool aPreferDiagonal )
419{
420 VECTOR2I majorDirection;
421 VECTOR2I p0_p, p0_n;
422 int orthoFanDistance = 0;
423 int diagFanDistance = 0;
424 const SHAPE* shP = nullptr;
425
426 if( aPair.PrimP() == nullptr )
427 {
428 BuildGeneric( aPair.AnchorP(), aPair.AnchorN(), true );
429 return;
430 }
431
432 const int pvMask = ITEM::SOLID_T | ITEM::VIA_T;
433
434 if( aPair.PrimP()->OfKind( pvMask ) && aPair.PrimN()->OfKind( pvMask ) )
435 {
436 p0_p = aPair.AnchorP();
437 p0_n = aPair.AnchorN();
438
439 // TODO(JE) padstacks
440 shP = aPair.PrimP()->Shape( -1 );
441 }
442 else if( aPair.PrimP()->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T )
443 && aPair.PrimN()->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
444 {
445 buildDpContinuation( aPair, aPreferDiagonal );
446
447 return;
448 }
449
450 majorDirection = ( p0_p - p0_n ).Perpendicular();
451
452 if( shP == nullptr )
453 return;
454
455 switch( shP->Type() )
456 {
457 case SH_CIRCLE:
458 BuildGeneric ( p0_p, p0_n, true );
459 return;
460
461 case SH_RECT:
462 {
463 int w = static_cast<const SHAPE_RECT*>( shP )->GetWidth();
464 int h = static_cast<const SHAPE_RECT*>( shP )->GetHeight();
465
466 if( w < h )
467 std::swap( w, h );
468
469 orthoFanDistance = ( w + 1 )* 3 / 2;
470 diagFanDistance = ( w - h );
471 break;
472 }
473
474 case SH_SEGMENT:
475 {
476 int w = static_cast<const SHAPE_SEGMENT*>( shP )->GetWidth();
477 SEG s = static_cast<const SHAPE_SEGMENT*>( shP )->GetSeg();
478
479 orthoFanDistance = w + ( s.B - s.A ).EuclideanNorm();
480 diagFanDistance = ( s.B - s.A ).EuclideanNorm();
481 break;
482 }
483
484 case SH_SIMPLE:
485 case SH_COMPOUND:
486 {
487 BOX2I bbox = shP->BBox();
488 int w = bbox.GetWidth();
489 int h = bbox.GetHeight();
490
491 if( w < h )
492 std::swap( w, h );
493
494 orthoFanDistance = ( w + 1 )* 3 / 2;
495 diagFanDistance = ( w - h );
496 break;
497 }
498
499 default:
500 wxFAIL_MSG( wxString::Format( wxT( "Unsupported starting primitive: %d (%s)." ),
501 shP->Type(),
502 SHAPE_TYPE_asString( shP->Type() ) ) );
503 break;
504 }
505
506 if( checkDiagonalAlignment( p0_p, p0_n ) )
507 {
508 int padDist = ( p0_p - p0_n ).EuclideanNorm();
509
510 for( int k = 0; k < 2; k++ )
511 {
512 VECTOR2I dir, dp, dv;
513
514 if( k == 0 )
515 dir = makeGapVector( majorDirection, orthoFanDistance );
516 else
517 dir = makeGapVector( majorDirection, diagFanDistance );
518
519 int d = std::max( 0, padDist - m_gap );
520 dp = makeGapVector( dir, d );
521 dv = makeGapVector( p0_n - p0_p, d );
522
523 for( int i = 0; i < 2; i++ )
524 {
525 int sign = i ? -1 : 1;
526
527 VECTOR2I gw_p( p0_p + sign * ( dir + dp ) + dv );
528 VECTOR2I gw_n( p0_n + sign * ( dir + dp ) - dv );
529
530 SHAPE_LINE_CHAIN entryP( { p0_p, p0_p + sign * dir, gw_p } );
531 SHAPE_LINE_CHAIN entryN( { p0_n, p0_n + sign * dir, gw_n } );
532
533 DP_GATEWAY gw( gw_p, gw_n, false );
534
535 gw.SetEntryLines( entryP, entryN );
536 gw.SetPriority( 100 - k );
537 m_gateways.push_back( gw );
538 }
539 }
540 }
541
542 BuildGeneric( p0_p, p0_n, true );
543}
544
545
546void DP_GATEWAYS::BuildForCursor( const VECTOR2I& aCursorPos )
547{
548 int gap = m_fitVias ? m_viaGap + m_viaDiameter : m_gap;
549
550 for( bool diagonal : { false, true } )
551 {
552 for( int i = 0; i < 4; i++ )
553 {
554 VECTOR2I dir;
555
556 if( !diagonal )
557 {
558 dir = makeGapVector( VECTOR2I( gap, gap ), gap );
559
560 if( i % 2 == 0 )
561 dir.x = -dir.x;
562
563 if( i / 2 == 0 )
564 dir.y = -dir.y;
565 }
566 else
567 {
568 if( i /2 == 0 )
569 dir = VECTOR2I( (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1 ), 0 );
570 else
571 dir = VECTOR2I( 0, (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1 ) );
572 }
573
574 if( m_fitVias )
575 BuildGeneric( aCursorPos + dir, aCursorPos - dir, true, true );
576 else
577 m_gateways.emplace_back( aCursorPos + dir, aCursorPos - dir, diagonal );
578 }
579 }
580}
581
582
583void DP_GATEWAYS::buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n )
584{
585 for( DP_GATEWAY &g : m_gateways )
586 {
587 if( !g.HasEntryLines() )
588 {
589 SHAPE_LINE_CHAIN lead_p = DIRECTION_45().BuildInitialTrace ( g.AnchorP(), p0_p,
590 g.IsDiagonal() ).Reverse();
591 SHAPE_LINE_CHAIN lead_n = DIRECTION_45().BuildInitialTrace ( g.AnchorN(), p0_n,
592 g.IsDiagonal() ).Reverse();
593 g.SetEntryLines( lead_p, lead_n );
594 }
595 }
596}
597
598
599void DP_GATEWAYS::buildDpContinuation( const DP_PRIMITIVE_PAIR& aPair, bool aIsDiagonal )
600{
601 DP_GATEWAY gw( aPair.AnchorP(), aPair.AnchorN(), aIsDiagonal );
602 gw.SetPriority( 100 );
603 m_gateways.push_back( gw );
604
605 if( !aPair.Directional() )
606 return;
607
608 // If we're at a "normal" angle (cardinal or 45-degree-diagonal), then add gateways that angle
609 // the anchor points by 22.5-degrees for connection to tracks which are at +/- 45 degrees from
610 // the existing direction.
611
612 int EPSILON = 5; // 0.005um
613 double SIN_22_5 = 0.38268; // sin(22.5)
614 double SIN_23_5 = 0.39875; // sin(23.5)
615
616 auto addAngledGateways =
617 [&]( int length, int priority )
618 {
619 SHAPE_LINE_CHAIN entryLineP;
620 entryLineP.Append( aPair.AnchorP() );
621 entryLineP.Append( aPair.AnchorP() + aPair.DirP().ToVector().Resize( length ) );
622 DP_GATEWAY gwExtendP( entryLineP.CLastPoint(), aPair.AnchorN(), aIsDiagonal );
623 gwExtendP.SetPriority( priority );
624 gwExtendP.SetEntryLines( entryLineP, SHAPE_LINE_CHAIN() );
625 m_gateways.push_back( gwExtendP );
626
627 SHAPE_LINE_CHAIN entryLineN;
628 entryLineN.Append( aPair.AnchorN() );
629 entryLineN.Append( aPair.AnchorN() + aPair.DirN().ToVector().Resize( length ) );
630 DP_GATEWAY gwExtendN( aPair.AnchorP(), entryLineN.CLastPoint(), aIsDiagonal );
631 gwExtendN.SetPriority( priority );
632 gwExtendN.SetEntryLines( SHAPE_LINE_CHAIN(), entryLineN );
633 m_gateways.push_back( gwExtendN );
634 };
635
636 VECTOR2I delta = aPair.AnchorP() - aPair.AnchorN();
637
638 if( abs( delta.x ) < EPSILON || abs( delta.y ) < EPSILON || abs( delta.x - delta.y ) < EPSILON )
639 {
640 addAngledGateways( KiROUND( (double) m_gap * SIN_22_5 ), 20 );
641
642 // fixme; sin(22.5) doesn't always work, so we also add some lower priority ones with a
643 // bit of wiggle room. See https://gitlab.com/kicad/code/kicad/-/issues/12459.
644 addAngledGateways( KiROUND( (double) m_gap * SIN_23_5 ), 5 );
645 }
646}
647
648
649void DP_GATEWAYS::BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries,
650 bool aViaMode )
651{
652 SEG st_p[2], st_n[2];
653 SEG d_n[2], d_p[2];
654
655 const int padToGapThreshold = 3;
656 int padDist = ( p0_n - p0_p ).EuclideanNorm();
657
658 st_p[0] = SEG(p0_p + VECTOR2I( -100, 0 ), p0_p + VECTOR2I( 100, 0 ) );
659 st_n[0] = SEG(p0_n + VECTOR2I( -100, 0 ), p0_n + VECTOR2I( 100, 0 ) );
660 st_p[1] = SEG(p0_p + VECTOR2I( 0, -100 ), p0_p + VECTOR2I( 0, 100 ) );
661 st_n[1] = SEG(p0_n + VECTOR2I( 0, -100 ), p0_n + VECTOR2I( 0, 100 ) );
662 d_p[0] = SEG( p0_p + VECTOR2I( -100, -100 ), p0_p + VECTOR2I( 100, 100 ) );
663 d_p[1] = SEG( p0_p + VECTOR2I( 100, -100 ), p0_p + VECTOR2I( -100, 100 ) );
664 d_n[0] = SEG( p0_n + VECTOR2I( -100, -100 ), p0_n + VECTOR2I( 100, 100 ) );
665 d_n[1] = SEG( p0_n + VECTOR2I( 100, -100 ), p0_n + VECTOR2I( -100, 100 ) );
666
667 // midpoint exit & side-by exits
668 for( int i = 0; i < 2; i++ )
669 {
670 bool straightColl = st_p[i].Collinear( st_n[i] );
671 bool diagColl = d_p[i].Collinear( d_n[i] );
672
673 if( straightColl || diagColl )
674 {
675 VECTOR2I dir = makeGapVector( p0_n - p0_p, m_gap / 2 );
676 VECTOR2I m = ( p0_p + p0_n ) / 2;
677 int prio = ( padDist > padToGapThreshold * m_gap ) ? 2 : 1;
678
679 if( !aViaMode )
680 {
681 m_gateways.emplace_back( m - dir, m + dir, diagColl, DIRECTION_45::ANG_RIGHT,
682 prio );
683
684 dir = makeGapVector( p0_n - p0_p, 2 * m_gap );
685 m_gateways.emplace_back( p0_p - dir, p0_p - dir + dir.Perpendicular(), diagColl );
686 m_gateways.emplace_back( p0_p - dir, p0_p - dir - dir.Perpendicular(), diagColl );
687 m_gateways.emplace_back( p0_n + dir + dir.Perpendicular(), p0_n + dir, diagColl );
688 m_gateways.emplace_back( p0_n + dir - dir.Perpendicular(), p0_n + dir, diagColl );
689 }
690 }
691 }
692
693 for( int i = 0; i < 2; i++ )
694 {
695 for( int j = 0; j < 2; j++ )
696 {
697 OPT_VECTOR2I ips[2];
698
699 ips[0] = d_n[i].IntersectLines( d_p[j] );
700 ips[1] = st_p[i].IntersectLines( st_n[j] );
701
702 if( d_n[i].Collinear( d_p[j] ) )
703 ips[0] = OPT_VECTOR2I();
704
705 if( st_p[i].Collinear( st_p[j] ) )
706 ips[1] = OPT_VECTOR2I();
707
708 // diagonal-diagonal and straight-straight cases - the most typical case if the pads
709 // are on the same straight/diagonal line
710 for( int k = 0; k < 2; k++ )
711 {
712 if( ips[k] )
713 {
714 const VECTOR2I m( *ips[k] );
715
716 if( m != p0_p && m != p0_n )
717 {
718 int prio = ( padDist > padToGapThreshold * m_gap ? 10 : 20 );
719 VECTOR2I g_p( ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
720 VECTOR2I g_n( ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
721
722 m_gateways.emplace_back( m + g_p, m + g_n, k == 0 ? true : false,
724 }
725 }
726 }
727
728 ips[0] = st_n[i].IntersectLines( d_p[j] );
729 ips[1] = st_p[i].IntersectLines( d_n[j] );
730
731 // diagonal-straight cases: 8 possibilities of "weirder" exists
732 for( int k = 0; k < 2; k++ )
733 {
734 if( ips[k] )
735 {
736 const VECTOR2I m( *ips[k] );
737
738 if( !aViaMode && m != p0_p && m != p0_n )
739 {
740 VECTOR2I g_p, g_n;
741
742 g_p = ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
743 g_n = ( p0_n - m ).Resize( ceil( (double) m_gap ) );
744
745 if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
746 m_gateways.emplace_back( m + g_p, m + g_n, true );
747
748 g_p = ( p0_p - m ).Resize( m_gap );
749 g_n = ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
750
751 if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
752 m_gateways.emplace_back( m + g_p, m + g_n, true );
753 }
754 }
755 }
756 }
757 }
758
759 if( aBuildEntries )
760 buildEntries( p0_p, p0_n );
761}
762
763
765{
766 if( m_hasVias )
767 {
768 return DP_PRIMITIVE_PAIR( &m_via_p, &m_via_n );
769 }
770 else
771 {
772 const LINE lP( PLine() );
773 const LINE lN( NLine() );
774
775 SEGMENT sP( lP, lP.CSegment( -1 ) );
776 SEGMENT sN( lN, lN.CSegment( -1 ) );
777
778 DP_PRIMITIVE_PAIR dpair( &sP, &sN );
779 dpair.SetAnchors( sP.Seg().B, sN.Seg().B );
780
781 return dpair;
782 }
783}
784
785
786bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
787{
788 SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
789
790 int64_t t_a = 0;
791 int64_t t_b = p.TCoef( p.B );
792
793 int64_t tproj_a = p.TCoef( n_proj_p.A );
794 int64_t tproj_b = p.TCoef( n_proj_p.B );
795
796 if( t_b < t_a )
797 std::swap( t_b, t_a );
798
799 if( tproj_b < tproj_a )
800 std::swap( tproj_b, tproj_a );
801
802 if( t_b <= tproj_a )
803 return false;
804
805 if( t_a >= tproj_b )
806 return false;
807
808 int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
809 std::vector<int64_t> tv( t, t + 4 );
810 std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
811
812 int64_t pLenSq = p.SquaredLength();
813
814 VECTOR2I dp = p.B - p.A;
815 pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
816 pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
817
818 pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
819 pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
820
821 nClip.A = n.LineProject( pClip.A );
822 nClip.B = n.LineProject( pClip.B );
823
824 return true;
825}
826
827
828double DIFF_PAIR::Skew() const
829{
830 return m_p.Length() - m_n.Length();
831}
832
833
835{
838
839 p.Simplify();
840 n.Simplify();
841
842 for( int i = 0; i < p.SegmentCount(); i++ )
843 {
844 for( int j = 0; j < n.SegmentCount(); j++ )
845 {
846 SEG sp = p.Segment( i );
847 SEG sn = n.Segment( j );
848
849 SEG p_clip, n_clip;
850
851 int64_t dist = std::abs( sp.Distance( sn ) - m_width );
852
853 if( sp.ApproxParallel( sn, 2 ) && m_gapConstraint.Matches( dist ) &&
854 commonParallelProjection( sp, sn, p_clip, n_clip ) )
855 {
856 const COUPLED_SEGMENTS spair( p_clip, sp, i, n_clip, sn, j );
857 aPairs.push_back( spair );
858 }
859 }
860 }
861}
862
863
864int64_t DIFF_PAIR::CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const
865{
866 int64_t total = 0;
867
868 for( int i = 0; i < aP.SegmentCount(); i++ )
869 {
870 for( int j = 0; j < aN.SegmentCount(); j++ )
871 {
872 SEG sp = aP.CSegment( i );
873 SEG sn = aN.CSegment( j );
874
875 SEG p_clip, n_clip;
876
877 int64_t dist = std::abs( sp.Distance(sn) - m_width );
878
879 if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) &&
880 commonParallelProjection( sp, sn, p_clip, n_clip ) )
881 total += p_clip.Length();
882 }
883 }
884
885 return total;
886}
887
888
890{
892
893 CoupledSegmentPairs( pairs );
894
895 double l = 0.0;
896
897 for( const COUPLED_SEGMENTS& pair : pairs )
898 l += pair.coupledP.Length();
899
900 return l;
901}
902
903
905{
906 double t = TotalLength();
907
908 if( t == 0.0 )
909 return 0.0;
910
911 return CoupledLength() / t;
912}
913
914
916{
917 double lenP = m_p.Length();
918 double lenN = m_n.Length();
919
920 return (lenN + lenP ) / 2.0;
921}
922
923
924int DIFF_PAIR::CoupledLength ( const SEG& aP, const SEG& aN ) const
925{
926 SEG p_clip, n_clip;
927 int64_t dist = std::abs( aP.Distance( aN ) - m_width );
928
929 if( aP.ApproxParallel( aN ) && m_gapConstraint.Matches( dist )
930 && commonParallelProjection ( aP, aN, p_clip, n_clip ) )
931 {
932 return p_clip.Length();
933 }
934
935 return 0;
936}
937
938}
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition box2.h:990
constexpr size_type GetWidth() const
Definition box2.h:214
constexpr size_type GetHeight() const
Definition box2.h:215
Represent route directions & corner angles in a 45-degree metric.
Definition direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
const VECTOR2I ToVector() const
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition direction45.h:78
Basic class for a differential pair.
bool CheckConnectionAngle(const DIFF_PAIR &aOther, int allowedAngles) const
SHAPE_LINE_CHAIN m_p
const SHAPE_LINE_CHAIN & CN() const
DP_PRIMITIVE_PAIR EndingPrimitives()
std::vector< COUPLED_SEGMENTS > COUPLED_SEGMENTS_VEC
double CoupledLength() const
bool BuildInitial(const DP_GATEWAY &aEntry, const DP_GATEWAY &aTarget, bool aPrefDiagonal)
double Skew() const
RANGED_NUM< int > m_gapConstraint
double TotalLength() const
double CoupledLengthFactor() const
void SetShape(const SHAPE_LINE_CHAIN &aP, const SHAPE_LINE_CHAIN &aN, bool aSwapLanes=false)
void SetGap(int aGap)
SHAPE_LINE_CHAIN m_n
const SHAPE_LINE_CHAIN & CP() const
void CoupledSegmentPairs(COUPLED_SEGMENTS_VEC &aPairs) const
void BuildFromPrimitivePair(const DP_PRIMITIVE_PAIR &aPair, bool aPreferDiagonal)
DP_GATEWAYS(int aGap)
bool FitGateways(DP_GATEWAYS &aEntry, DP_GATEWAYS &aTarget, bool aPrefDiagonal, DIFF_PAIR &aDp)
void BuildGeneric(const VECTOR2I &p0_p, const VECTOR2I &p0_n, bool aBuildEntries=false, bool aViaMode=false)
std::vector< DP_GATEWAY > & Gateways()
bool checkDiagonalAlignment(const VECTOR2I &a, const VECTOR2I &b) const
void BuildOrthoProjections(DP_GATEWAYS &aEntries, const VECTOR2I &aCursorPos, int aOrthoScore)
void buildDpContinuation(const DP_PRIMITIVE_PAIR &aPair, bool aIsDiagonal)
std::vector< DP_GATEWAY > m_gateways
void FilterByOrientation(int aAngleMask, DIRECTION_45 aRefOrientation)
void BuildForCursor(const VECTOR2I &aCursorPos)
void buildEntries(const VECTOR2I &p0_p, const VECTOR2I &p0_n)
Define a "gateway" for routing a differential pair - e.g.
SHAPE_LINE_CHAIN m_entryP
bool HasEntryLines() const
int AllowedAngles() const
const VECTOR2I & AnchorN() const
SHAPE_LINE_CHAIN m_entryN
void SetEntryLines(const SHAPE_LINE_CHAIN &aEntryP, const SHAPE_LINE_CHAIN &aEntryN)
const VECTOR2I & AnchorP() const
const DIFF_PAIR Entry() const
void SetPriority(int aPriority)
Store starting/ending primitives (pads, vias or segments) for a differential pair.
DIRECTION_45 DirN() const
const VECTOR2I & AnchorN() const
const VECTOR2I & AnchorP() const
DIRECTION_45 anchorDirection(const ITEM *aItem, const VECTOR2I &aP) const
void CursorOrientation(const VECTOR2I &aCursorPos, VECTOR2I &aMidpoint, VECTOR2I &aDirection) const
DP_PRIMITIVE_PAIR & operator=(const DP_PRIMITIVE_PAIR &aOther)
void SetAnchors(const VECTOR2I &aAnchorP, const VECTOR2I &aAnchorN)
DIRECTION_45 DirP() const
Base class for PNS router board items.
Definition pns_item.h:98
virtual const SHAPE * Shape(int aLayer) const
Return the geometrical shape of the item.
Definition pns_item.h:242
virtual ITEM * Clone() const =0
Return a deep copy of the item.
bool OfKind(int aKindMask) const
Definition pns_item.h:181
virtual VECTOR2I Anchor(int n) const
Definition pns_item.h:268
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition pns_line.h:62
const SEG CSegment(int aIdx) const
Set line width.
Definition pns_line.h:148
const SEG & Seg() const
Definition pns_segment.h:93
Definition seg.h:42
VECTOR2I A
Definition seg.h:49
ecoord SquaredDistance(const SEG &aSeg) const
Definition seg.cpp:80
VECTOR2I::extended_type ecoord
Definition seg.h:44
VECTOR2I B
Definition seg.h:50
int Length() const
Return the length (this).
Definition seg.h:343
static SEG::ecoord Square(int a)
Definition seg.h:123
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition seg.cpp:778
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition seg.h:286
ecoord TCoef(const VECTOR2I &aP) const
Definition seg.h:405
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition seg.h:220
ecoord SquaredLength() const
Definition seg.h:348
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition seg.cpp:673
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:656
SHAPE_TYPE Type() const
Return the type of the shape.
Definition shape.h:98
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
const std::optional< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
bool Intersects(const SEG &aSeg) const
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
An abstract shape on 2D plane.
Definition shape.h:126
virtual const BOX2I BBox(int aClearance=0) const =0
Compute a bounding box of the shape, with a margin of aClearance a collision.
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition vector2d.h:283
constexpr VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition vector2d.h:314
constexpr extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition vector2d.h:554
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition vector2d.h:385
#define EPSILON
Push and Shove diff pair dimensions (gap) settings dialog.
bool commonParallelProjection(SEG p, SEG n, SEG &pClip, SEG &nClip)
static VECTOR2I makeGapVector(VECTOR2I dir, int length)
static bool checkGap(const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap)
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:400
@ DIFF_PAIR
std::optional< VECTOR2I > OPT_VECTOR2I
Definition seg.h:39
@ SH_RECT
axis-aligned rectangle
Definition shape.h:47
@ SH_CIRCLE
circle
Definition shape.h:50
@ SH_SIMPLE
simple polygon
Definition shape.h:51
@ SH_SEGMENT
line segment
Definition shape.h:48
@ SH_COMPOUND
compound shape, consisting of multiple simple shapes
Definition shape.h:53
static wxString SHAPE_TYPE_asString(SHAPE_TYPE a)
Definition shape.h:59
int delta
constexpr int sign(T val)
Definition util.h:145
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition util.h:139
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695