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