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
95{
96 delete m_primP;
97 delete m_primN;
98}
99
100
102{
103 if( !m_primP )
104 return false;
105
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
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
162{
164}
165
166
168{
170}
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{
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}
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.
Definition: direction45.h:181
const VECTOR2I ToVector() const
Definition: direction45.h:287
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:78
Definition: line.h:36
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
A set of gateways calculated for the cursor or starting/ending primitive pair.
void BuildFromPrimitivePair(const DP_PRIMITIVE_PAIR &aPair, bool aPreferDiagonal)
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.
Definition: pns_diff_pair.h:44
SHAPE_LINE_CHAIN m_entryP
bool HasEntryLines() const
int AllowedAngles() const
Definition: pns_diff_pair.h:74
const VECTOR2I & AnchorN() const
Definition: pns_diff_pair.h:69
SHAPE_LINE_CHAIN m_entryN
void SetEntryLines(const SHAPE_LINE_CHAIN &aEntryP, const SHAPE_LINE_CHAIN &aEntryN)
Definition: pns_diff_pair.h:89
const VECTOR2I & AnchorP() const
Definition: pns_diff_pair.h:67
const DIFF_PAIR Entry() const
void SetPriority(int aPriority)
Definition: pns_diff_pair.h:84
Store starting/ending primitives (pads, vias or segments) for a differential pair.
DIRECTION_45 DirN() const
const VECTOR2I & AnchorN() const
ITEM * PrimN() 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)
ITEM * PrimP() const
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.
@ SEGMENT_T
Definition: pns_item.h:107
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
bool Matches(const T &aOther) const
Definition: ranged_num.h:44
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:780
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:675
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:658
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.
long long int Length() const
Return length of the line chain in Euclidean metric.
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