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}
coord_type GetHeight() const
Definition: box2.h:189
coord_type GetWidth() const
Definition: box2.h:188
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
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:224
@ SEGMENT_T
Definition: pns_item.h:105
bool OfKind(int aKindMask) const
Definition: pns_item.h:174
virtual VECTOR2I Anchor(int n) const
Definition: pns_item.h:236
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:326
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:403
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:388
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
ecoord SquaredLength() const
Definition: seg.h:331
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
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:312
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.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) 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.
SEG Segment(int aIndex)
Return a copy of the aIndex-th 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:265
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:279
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:465
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
#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:173
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:426
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
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129
int sign(T val)
Definition: util.h:124
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:85
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:118
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588