1 /*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2015 CERN
5 * Copyright (C) 2016-2021 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22 #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
32 namespace PNS {
33
34 class LINE;
35
36
DP_PRIMITIVE_PAIR(ITEM * aPrimP,ITEM * aPrimN)37 DP_PRIMITIVE_PAIR::DP_PRIMITIVE_PAIR( ITEM* aPrimP, ITEM* aPrimN )
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
SetAnchors(const VECTOR2I & aAnchorP,const VECTOR2I & aAnchorN)47 void DP_PRIMITIVE_PAIR::SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN )
48 {
49 m_anchorP = aAnchorP;
50 m_anchorN = aAnchorN;
51 }
52
53
DP_PRIMITIVE_PAIR(const VECTOR2I & aAnchorP,const VECTOR2I & aAnchorN)54 DP_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
DP_PRIMITIVE_PAIR(const DP_PRIMITIVE_PAIR & aOther)62 DP_PRIMITIVE_PAIR::DP_PRIMITIVE_PAIR( const DP_PRIMITIVE_PAIR& aOther )
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
operator =(const DP_PRIMITIVE_PAIR & aOther)77 DP_PRIMITIVE_PAIR& DP_PRIMITIVE_PAIR::operator=( const DP_PRIMITIVE_PAIR& aOther )
78 {
79 if( aOther.m_primP )
80 m_primP = aOther.m_primP->Clone();
81 if( aOther.m_primN )
82 m_primN = aOther.m_primN->Clone();
83
84 m_anchorP = aOther.m_anchorP;
85 m_anchorN = aOther.m_anchorN;
86
87 return *this;
88 }
89
90
~DP_PRIMITIVE_PAIR()91 DP_PRIMITIVE_PAIR::~DP_PRIMITIVE_PAIR()
92 {
93 delete m_primP;
94 delete m_primN;
95 }
96
97
Directional() const98 bool DP_PRIMITIVE_PAIR::Directional() const
99 {
100 if( !m_primP )
101 return false;
102
103 return m_primP->OfKind( ITEM::SEGMENT_T );
104 }
105
106
anchorDirection(const ITEM * aItem,const VECTOR2I & aP) const107 DIRECTION_45 DP_PRIMITIVE_PAIR::anchorDirection( const ITEM* aItem, const VECTOR2I& aP ) const
108 {
109 if( !aItem->OfKind ( ITEM::SEGMENT_T | ITEM::ARC_T ) )
110 return DIRECTION_45();
111
112 if( aItem->Anchor( 0 ) == aP )
113 return DIRECTION_45( aItem->Anchor( 0 ) - aItem->Anchor( 1 ) );
114 else
115 return DIRECTION_45( aItem->Anchor( 1 ) - aItem->Anchor( 0 ) );
116 }
117
118
CursorOrientation(const VECTOR2I & aCursorPos,VECTOR2I & aMidpoint,VECTOR2I & aDirection) const119 void DP_PRIMITIVE_PAIR::CursorOrientation( const VECTOR2I& aCursorPos, VECTOR2I& aMidpoint,
120 VECTOR2I& aDirection ) const
121 {
122 assert( m_primP && m_primN );
123
124 VECTOR2I aP, aN;
125
126 if( m_primP->OfKind( ITEM::SEGMENT_T ) && m_primN->OfKind( ITEM::SEGMENT_T ) )
127 {
128 aP = m_primP->Anchor( 1 );
129 aN = m_primN->Anchor( 1 );
130
131 // If both segments are parallel, use that as the direction. Otherwise, fall back on the
132 // direction perpendicular to the anchor points.
133 const SEG& segP = static_cast<SEGMENT*>( m_primP )->Seg();
134 const SEG& segN = static_cast<SEGMENT*>( m_primN )->Seg();
135
136 if( ( segP.B != segP.A ) && ( segN.B != segN.A ) && segP.ApproxParallel( segN ) )
137 {
138 aMidpoint = ( aP + aN ) / 2;
139 aDirection = segP.B - segP.A;
140 aDirection = aDirection.Resize( ( aP - aN ).EuclideanNorm() );
141 return;
142 }
143 }
144 else
145 {
146 aP = m_primP->Anchor( 0 );
147 aN = m_primN->Anchor( 0 );
148 }
149
150 aMidpoint = ( aP + aN ) / 2;
151 aDirection = ( aP - aN ).Perpendicular();
152
153 if( aDirection.Dot( aCursorPos - aMidpoint ) < 0 )
154 aDirection = -aDirection;
155 }
156
157
DirP() const158 DIRECTION_45 DP_PRIMITIVE_PAIR::DirP() const
159 {
160 return anchorDirection( m_primP, m_anchorP );
161 }
162
163
DirN() const164 DIRECTION_45 DP_PRIMITIVE_PAIR::DirN() const
165 {
166 return anchorDirection( m_primN, m_anchorN );
167 }
168
169
angle(const VECTOR2I & a,const VECTOR2I & b)170 static DIRECTION_45::AngleType angle( const VECTOR2I &a, const VECTOR2I &b )
171 {
172 DIRECTION_45 dir_a( a );
173 DIRECTION_45 dir_b( b );
174
175 return dir_a.Angle( dir_b );
176 }
177
178
checkGap(const SHAPE_LINE_CHAIN & p,const SHAPE_LINE_CHAIN & n,int gap)179 static bool checkGap( const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap )
180 {
181 int i, j;
182
183 for( i = 0; i < p.SegmentCount(); i++ )
184 {
185 for( j = 0; j < n.SegmentCount() ; j++ )
186 {
187 int dist = p.CSegment( i ).Distance( n.CSegment( j ) );
188
189 if( dist < gap - 100 )
190 return false;
191 }
192 }
193
194 return true;
195 }
196
197
Reverse()198 void DP_GATEWAY::Reverse()
199 {
200 m_entryN = m_entryN.Reverse();
201 m_entryP = m_entryP.Reverse();
202 }
203
204
BuildInitial(const DP_GATEWAY & aEntry,const DP_GATEWAY & aTarget,bool aPrefDiagonal)205 bool DIFF_PAIR::BuildInitial( const DP_GATEWAY& aEntry, const DP_GATEWAY &aTarget,
206 bool aPrefDiagonal )
207 {
208 SHAPE_LINE_CHAIN p = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorP(), aTarget.AnchorP(),
209 aPrefDiagonal );
210 SHAPE_LINE_CHAIN n = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorN(), aTarget.AnchorN(),
211 aPrefDiagonal );
212
213 int mask = aEntry.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE;
214
215 SHAPE_LINE_CHAIN sum_n, sum_p;
216 m_p = p;
217 m_n = n;
218
219 if( aEntry.HasEntryLines() )
220 {
221 if( !aEntry.Entry().CheckConnectionAngle( *this, mask ) )
222 return false;
223
224 sum_p = aEntry.Entry().CP();
225 sum_n = aEntry.Entry().CN();
226 sum_p.Append( p );
227 sum_n.Append( n );
228 }
229 else
230 {
231 sum_p = p;
232 sum_n = n;
233 }
234
235 mask = aTarget.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE;
236
237 m_p = sum_p;
238 m_n = sum_n;
239
240 if( aTarget.HasEntryLines() )
241 {
242 DP_GATEWAY t(aTarget) ;
243 t.Reverse();
244
245 if( !CheckConnectionAngle( t.Entry(), mask ) )
246 return false;
247
248 sum_p.Append( t.Entry().CP() );
249 sum_n.Append( t.Entry().CN() );
250 }
251
252 m_p = sum_p;
253 m_n = sum_n;
254
255 if( !checkGap ( p, n, m_gapConstraint ) )
256 return false;
257
258 if( p.SelfIntersecting() || n.SelfIntersecting() )
259 return false;
260
261 if( p.Intersects( n ) )
262 return false;
263
264 return true;
265 }
266
267
CheckConnectionAngle(const DIFF_PAIR & aOther,int aAllowedAngles) const268 bool DIFF_PAIR::CheckConnectionAngle( const DIFF_PAIR& aOther, int aAllowedAngles ) const
269 {
270 bool checkP, checkN;
271
272 if( m_p.SegmentCount() == 0 || aOther.m_p.SegmentCount() == 0 )
273 checkP = true;
274 else
275 {
276 DIRECTION_45 p0( m_p.CSegment( -1 ) );
277 DIRECTION_45 p1( aOther.m_p.CSegment( 0 ) );
278
279 checkP = ( p0.Angle( p1 ) & aAllowedAngles ) != 0;
280 }
281
282 if( m_n.SegmentCount() == 0 || aOther.m_n.SegmentCount() == 0 )
283 {
284 checkN = true;
285 }
286 else
287 {
288 DIRECTION_45 n0( m_n.CSegment( -1 ) );
289 DIRECTION_45 n1( aOther.m_n.CSegment( 0 ) );
290
291 checkN = ( n0.Angle( n1 ) & aAllowedAngles ) != 0;
292 }
293
294 return checkP && checkN;
295 }
296
297
Entry() const298 const DIFF_PAIR DP_GATEWAY::Entry() const
299 {
300 return DIFF_PAIR( m_entryP, m_entryN, 0 );
301 }
302
303
BuildOrthoProjections(DP_GATEWAYS & aEntries,const VECTOR2I & aCursorPos,int aOrthoScore)304 void DP_GATEWAYS::BuildOrthoProjections( DP_GATEWAYS& aEntries, const VECTOR2I& aCursorPos,
305 int aOrthoScore )
306 {
307 for( const DP_GATEWAY& g : aEntries.Gateways() )
308 {
309 VECTOR2I midpoint( ( g.AnchorP() + g.AnchorN() ) / 2 );
310 SEG guide_s( midpoint, midpoint + VECTOR2I( 1, 0 ) );
311 SEG guide_d( midpoint, midpoint + VECTOR2I( 1, 1 ) );
312
313 VECTOR2I proj_s = guide_s.LineProject( aCursorPos );
314 VECTOR2I proj_d = guide_d.LineProject( aCursorPos );
315
316 int dist_s = ( proj_s - aCursorPos ).EuclideanNorm();
317 int dist_d = ( proj_d - aCursorPos ).EuclideanNorm();
318
319 VECTOR2I proj = ( dist_s < dist_d ? proj_s : proj_d );
320
321 DP_GATEWAYS targets( m_gap );
322
323 targets.m_viaGap = m_viaGap;
324 targets.m_viaDiameter = m_viaDiameter;
325 targets.m_fitVias = m_fitVias;
326
327 targets.BuildForCursor( proj );
328
329 for( DP_GATEWAY t : targets.Gateways() )
330 {
331 t.SetPriority( aOrthoScore );
332 m_gateways.push_back( t );
333 }
334 }
335 }
336
337
FitGateways(DP_GATEWAYS & aEntry,DP_GATEWAYS & aTarget,bool aPrefDiagonal,DIFF_PAIR & aDp)338 bool DP_GATEWAYS::FitGateways( DP_GATEWAYS& aEntry, DP_GATEWAYS& aTarget, bool aPrefDiagonal,
339 DIFF_PAIR& aDp )
340 {
341 DP_CANDIDATE best;
342
343 int n = 0;
344 int bestScore = -1000;
345 bool found = false;
346
347 for( const DP_GATEWAY& g_entry : aEntry.Gateways() )
348 {
349 for( const DP_GATEWAY& g_target : aTarget.Gateways() )
350 {
351 n++;
352
353 for( int attempt = 0; attempt < 2; attempt++ )
354 {
355 int score = ( attempt == 1 ? -3 : 0 );
356 score += g_entry.Priority();
357 score += g_target.Priority();
358
359 if( score < bestScore )
360 continue;
361
362 DIFF_PAIR l( m_gap );
363
364 if( l.BuildInitial( g_entry, g_target,
365 aPrefDiagonal ^ ( attempt ? true : false ) ) )
366 {
367 best.p = l.CP();
368 best.n = l.CN();
369 bestScore = score;
370 found = true;
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
checkDiagonalAlignment(const VECTOR2I & a,const VECTOR2I & b) const388 bool DP_GATEWAYS::checkDiagonalAlignment( const VECTOR2I& a, const VECTOR2I& b ) const
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
FilterByOrientation(int aAngleMask,DIRECTION_45 aRefOrientation)396 void DP_GATEWAYS::FilterByOrientation ( int aAngleMask, DIRECTION_45 aRefOrientation )
397 {
398 m_gateways.erase(
399 std::remove_if( m_gateways.begin(), m_gateways.end(),
400 [aAngleMask, aRefOrientation]( const DP_GATEWAY& dp)
401 {
402 DIRECTION_45 orient( dp.AnchorP() - dp.AnchorN() );
403 return ( orient.Angle( aRefOrientation ) & aAngleMask );
404 } ), m_gateways.end()
405 );
406 }
407
makeGapVector(VECTOR2I dir,int length)408 static VECTOR2I makeGapVector( VECTOR2I dir, int length )
409 {
410 int l = length / 2;
411 VECTOR2I rv;
412
413 if( dir.EuclideanNorm() == 0 )
414 return dir;
415
416 do
417 {
418 rv = dir.Resize( l );
419 l++;
420 } while( ( rv * 2 ).EuclideanNorm() < length );
421
422 return rv;
423 }
424
BuildFromPrimitivePair(const DP_PRIMITIVE_PAIR & aPair,bool aPreferDiagonal)425 void DP_GATEWAYS::BuildFromPrimitivePair( const DP_PRIMITIVE_PAIR& aPair, bool aPreferDiagonal )
426 {
427 VECTOR2I majorDirection;
428 VECTOR2I p0_p, p0_n;
429 int orthoFanDistance;
430 int diagFanDistance;
431 const SHAPE* shP = nullptr;
432
433 if( aPair.PrimP() == nullptr )
434 {
435 BuildGeneric( aPair.AnchorP(), aPair.AnchorN(), true );
436 return;
437 }
438
439 const int pvMask = ITEM::SOLID_T | ITEM::VIA_T;
440
441 if( aPair.PrimP()->OfKind( pvMask ) && aPair.PrimN()->OfKind( pvMask ) )
442 {
443 p0_p = aPair.AnchorP();
444 p0_n = aPair.AnchorN();
445
446 shP = aPair.PrimP()->Shape();
447 }
448 else if( aPair.PrimP()->OfKind( ITEM::SEGMENT_T ) && aPair.PrimN()->OfKind( ITEM::SEGMENT_T ) )
449 {
450 buildDpContinuation( aPair, aPreferDiagonal );
451
452 return;
453 }
454
455 majorDirection = ( p0_p - p0_n ).Perpendicular();
456
457 if( shP == nullptr )
458 return;
459
460 switch( shP->Type() )
461 {
462 case SH_RECT:
463 {
464 int w = static_cast<const SHAPE_RECT*>( shP )->GetWidth();
465 int h = static_cast<const SHAPE_RECT*>( shP )->GetHeight();
466
467 if( w < h )
468 std::swap( w, h );
469
470 orthoFanDistance = ( w + 1 )* 3 / 2;
471 diagFanDistance = ( w - h );
472 break;
473 }
474
475 case SH_SEGMENT:
476 {
477 int w = static_cast<const SHAPE_SEGMENT*>( shP )->GetWidth();
478 SEG s = static_cast<const SHAPE_SEGMENT*>( shP )->GetSeg();
479
480 orthoFanDistance = w + ( s.B - s.A ).EuclideanNorm();
481 diagFanDistance = ( s.B - s.A ).EuclideanNorm();
482 break;
483 }
484
485 default:
486 BuildGeneric ( p0_p, p0_n, true );
487 return;
488 }
489
490 if( checkDiagonalAlignment( p0_p, p0_n ) )
491 {
492 int padDist = ( p0_p - p0_n ).EuclideanNorm();
493
494 for( int k = 0; k < 2; k++ )
495 {
496 VECTOR2I dir, dp, dv;
497
498 if( k == 0 )
499 dir = makeGapVector( majorDirection, orthoFanDistance );
500 else
501 dir = makeGapVector( majorDirection, diagFanDistance );
502
503 int d = std::max( 0, padDist - m_gap );
504 dp = makeGapVector( dir, d );
505 dv = makeGapVector( p0_n - p0_p, d );
506
507 for( int i = 0; i < 2; i++ )
508 {
509 int sign = i ? -1 : 1;
510
511 VECTOR2I gw_p( p0_p + sign * ( dir + dp ) + dv );
512 VECTOR2I gw_n( p0_n + sign * ( dir + dp ) - dv );
513
514 SHAPE_LINE_CHAIN entryP( { p0_p, p0_p + sign * dir, gw_p } );
515 SHAPE_LINE_CHAIN entryN( { p0_n, p0_n + sign * dir, gw_n } );
516
517 DP_GATEWAY gw( gw_p, gw_n, false );
518
519 gw.SetEntryLines( entryP, entryN );
520 gw.SetPriority( 100 - k );
521 m_gateways.push_back( gw );
522 }
523 }
524 }
525
526 BuildGeneric( p0_p, p0_n, true );
527 }
528
529
BuildForCursor(const VECTOR2I & aCursorPos)530 void DP_GATEWAYS::BuildForCursor( const VECTOR2I& aCursorPos )
531 {
532 int gap = m_fitVias ? m_viaGap + m_viaDiameter : m_gap;
533
534 for( int attempt = 0; attempt < 2; attempt++ )
535 {
536 for( int i = 0; i < 4; i++ )
537 {
538 VECTOR2I dir;
539
540 if( !attempt )
541 {
542 dir = makeGapVector( VECTOR2I( gap, gap ), gap );
543
544 if( i % 2 == 0 )
545 dir.x = -dir.x;
546
547 if( i / 2 == 0 )
548 dir.y = -dir.y;
549 }
550 else
551 {
552 if( i /2 == 0 )
553 dir = VECTOR2I( (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1 ), 0 );
554 else
555 dir = VECTOR2I( 0, (gap + 1) / 2 * ( ( i % 2 ) ? -1 : 1) );
556 }
557
558 if( m_fitVias )
559 BuildGeneric( aCursorPos + dir, aCursorPos - dir, true, true );
560 else
561 m_gateways.emplace_back( aCursorPos + dir, aCursorPos - dir,
562 attempt ? true : false );
563
564 }
565 }
566 }
567
568
buildEntries(const VECTOR2I & p0_p,const VECTOR2I & p0_n)569 void DP_GATEWAYS::buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n )
570 {
571 for( DP_GATEWAY &g : m_gateways )
572 {
573 if( !g.HasEntryLines() )
574 {
575 SHAPE_LINE_CHAIN lead_p = DIRECTION_45().BuildInitialTrace ( g.AnchorP(), p0_p,
576 g.IsDiagonal() ).Reverse();
577 SHAPE_LINE_CHAIN lead_n = DIRECTION_45().BuildInitialTrace ( g.AnchorN(), p0_n,
578 g.IsDiagonal() ).Reverse();
579 g.SetEntryLines( lead_p, lead_n );
580 }
581 }
582 }
583
584
buildDpContinuation(const DP_PRIMITIVE_PAIR & aPair,bool aIsDiagonal)585 void DP_GATEWAYS::buildDpContinuation( const DP_PRIMITIVE_PAIR& aPair, bool aIsDiagonal )
586 {
587 DP_GATEWAY gw( aPair.AnchorP(), aPair.AnchorN(), aIsDiagonal );
588 gw.SetPriority( 100 );
589 m_gateways.push_back( gw );
590
591 if( !aPair.Directional() )
592 return;
593
594 DIRECTION_45 dP = aPair.DirP();
595 DIRECTION_45 dN = aPair.DirN();
596
597 int gap = ( aPair.AnchorP() - aPair.AnchorN() ).EuclideanNorm();
598
599 VECTOR2I vdP = aPair.AnchorP() + dP.Left().ToVector();
600 VECTOR2I vdN = aPair.AnchorN() + dN.Left().ToVector();
601
602 SEGMENT* sP = static_cast<SEGMENT*>( aPair.PrimP() );
603
604 VECTOR2I t1, t2;
605
606 auto vL = makeGapVector( dP.Left().ToVector(), ( gap + 1 ) / 2 );
607 auto vR = makeGapVector( dP.Right().ToVector(), ( gap + 1 ) / 2 );
608
609 if( sP->Seg().Side( vdP ) == sP->Seg().Side( vdN ) )
610 {
611 t1 = aPair.AnchorP() + vL;
612 t2 = aPair.AnchorN() + vR;
613 }
614 else
615 {
616 t1 = aPair.AnchorP() + vR;
617 t2 = aPair.AnchorN() + vL;
618 }
619
620 DP_GATEWAY gwL( t2, aPair.AnchorN(), !aIsDiagonal );
621 SHAPE_LINE_CHAIN ep = dP.BuildInitialTrace( aPair.AnchorP(), t2, !aIsDiagonal );
622 gwL.SetPriority( 10 );
623 gwL.SetEntryLines( ep , SHAPE_LINE_CHAIN() );
624
625 m_gateways.push_back( gwL );
626
627 DP_GATEWAY gwR( aPair.AnchorP(), t1, !aIsDiagonal );
628 SHAPE_LINE_CHAIN en = dP.BuildInitialTrace( aPair.AnchorN(), t1, !aIsDiagonal );
629 gwR.SetPriority( 10) ;
630 gwR.SetEntryLines( SHAPE_LINE_CHAIN(), en );
631
632 m_gateways.push_back( gwR );
633 }
634
635
BuildGeneric(const VECTOR2I & p0_p,const VECTOR2I & p0_n,bool aBuildEntries,bool aViaMode)636 void DP_GATEWAYS::BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries,
637 bool aViaMode )
638 {
639 SEG st_p[2], st_n[2];
640 SEG d_n[2], d_p[2];
641
642 const int padToGapThreshold = 3;
643 int padDist = ( p0_n - p0_p ).EuclideanNorm();
644
645 st_p[0] = SEG(p0_p + VECTOR2I( -100, 0 ), p0_p + VECTOR2I( 100, 0 ) );
646 st_n[0] = SEG(p0_n + VECTOR2I( -100, 0 ), p0_n + VECTOR2I( 100, 0 ) );
647 st_p[1] = SEG(p0_p + VECTOR2I( 0, -100 ), p0_p + VECTOR2I( 0, 100 ) );
648 st_n[1] = SEG(p0_n + VECTOR2I( 0, -100 ), p0_n + VECTOR2I( 0, 100 ) );
649 d_p[0] = SEG( p0_p + VECTOR2I( -100, -100 ), p0_p + VECTOR2I( 100, 100 ) );
650 d_p[1] = SEG( p0_p + VECTOR2I( 100, -100 ), p0_p + VECTOR2I( -100, 100 ) );
651 d_n[0] = SEG( p0_n + VECTOR2I( -100, -100 ), p0_n + VECTOR2I( 100, 100 ) );
652 d_n[1] = SEG( p0_n + VECTOR2I( 100, -100 ), p0_n + VECTOR2I( -100, 100 ) );
653
654 // midpoint exit & side-by exits
655 for( int i = 0; i < 2; i++ )
656 {
657 bool straightColl = st_p[i].Collinear( st_n[i] );
658 bool diagColl = d_p[i].Collinear( d_n[i] );
659
660 if( straightColl || diagColl )
661 {
662 VECTOR2I dir = makeGapVector( p0_n - p0_p, m_gap / 2 );
663 VECTOR2I m = ( p0_p + p0_n ) / 2;
664 int prio = ( padDist > padToGapThreshold * m_gap ? 2 : 1);
665
666 if( !aViaMode )
667 {
668 m_gateways.emplace_back( m - dir, m + dir, diagColl, DIRECTION_45::ANG_RIGHT,
669 prio );
670
671 dir = makeGapVector( p0_n - p0_p, 2 * m_gap );
672 m_gateways.emplace_back( p0_p - dir, p0_p - dir + dir.Perpendicular(), diagColl );
673 m_gateways.emplace_back( p0_p - dir, p0_p - dir - dir.Perpendicular(), diagColl );
674 m_gateways.emplace_back( p0_n + dir + dir.Perpendicular(), p0_n + dir, diagColl );
675 m_gateways.emplace_back( p0_n + dir - dir.Perpendicular(), p0_n + dir, diagColl );
676 }
677 }
678 }
679
680 for( int i = 0; i < 2; i++ )
681 {
682 for( int j = 0; j < 2; j++ )
683 {
684 OPT_VECTOR2I ips[2];
685
686 ips[0] = d_n[i].IntersectLines( d_p[j] );
687 ips[1] = st_p[i].IntersectLines( st_n[j] );
688
689 if( d_n[i].Collinear( d_p[j] ) )
690 ips[0] = OPT_VECTOR2I();
691
692 if( st_p[i].Collinear( st_p[j] ) )
693 ips[1] = OPT_VECTOR2I();
694
695 // diagonal-diagonal and straight-straight cases - the most typical case if the pads
696 // are on the same straight/diagonal line
697 for( int k = 0; k < 2; k++ )
698 {
699 if( ips[k] )
700 {
701 const VECTOR2I m( *ips[k] );
702
703 if( m != p0_p && m != p0_n )
704 {
705 int prio = ( padDist > padToGapThreshold * m_gap ? 10 : 20 );
706 VECTOR2I g_p( ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
707 VECTOR2I g_n( ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT1_2 ) ) );
708
709 m_gateways.emplace_back( m + g_p, m + g_n, k == 0 ? true : false,
710 DIRECTION_45::ANG_OBTUSE, prio );
711 }
712 }
713 }
714
715 ips[0] = st_n[i].IntersectLines( d_p[j] );
716 ips[1] = st_p[i].IntersectLines( d_n[j] );
717
718 // diagonal-straight cases: 8 possibilities of "weirder" exists
719 for( int k = 0; k < 2; k++ )
720 {
721 if( ips[k] )
722 {
723 const VECTOR2I m( *ips[k] );
724
725 if( !aViaMode && m != p0_p && m != p0_n )
726 {
727 VECTOR2I g_p, g_n;
728
729 g_p = ( p0_p - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
730 g_n = ( p0_n - m ).Resize( ceil( (double) m_gap ) );
731
732 if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
733 m_gateways.emplace_back( m + g_p, m + g_n, true );
734
735 g_p = ( p0_p - m ).Resize( m_gap );
736 g_n = ( p0_n - m ).Resize( ceil( (double) m_gap * M_SQRT2 ) );
737
738 if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE )
739 m_gateways.emplace_back( m + g_p, m + g_n, true );
740 }
741 }
742 }
743 }
744 }
745
746 if( aBuildEntries )
747 buildEntries( p0_p, p0_n );
748 }
749
750
EndingPrimitives()751 DP_PRIMITIVE_PAIR DIFF_PAIR::EndingPrimitives()
752 {
753 if( m_hasVias )
754 {
755 return DP_PRIMITIVE_PAIR( &m_via_p, &m_via_n );
756 }
757 else
758 {
759 const LINE lP( PLine() );
760 const LINE lN( NLine() );
761
762 SEGMENT sP( lP, lP.CSegment( -1 ) );
763 SEGMENT sN( lN, lN.CSegment( -1 ) );
764
765 DP_PRIMITIVE_PAIR dpair( &sP, &sN );
766 dpair.SetAnchors( sP.Seg().B, sN.Seg().B );
767
768 return dpair;
769 }
770 }
771
772
commonParallelProjection(SEG p,SEG n,SEG & pClip,SEG & nClip)773 bool commonParallelProjection( SEG p, SEG n, SEG &pClip, SEG& nClip )
774 {
775 SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) );
776
777 int64_t t_a = 0;
778 int64_t t_b = p.TCoef( p.B );
779
780 int64_t tproj_a = p.TCoef( n_proj_p.A );
781 int64_t tproj_b = p.TCoef( n_proj_p.B );
782
783 if( t_b < t_a )
784 std::swap( t_b, t_a );
785
786 if( tproj_b < tproj_a )
787 std::swap( tproj_b, tproj_a );
788
789 if( t_b <= tproj_a )
790 return false;
791
792 if( t_a >= tproj_b )
793 return false;
794
795 int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) };
796 std::vector<int64_t> tv( t, t + 4 );
797 std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints
798
799 int64_t pLenSq = p.SquaredLength();
800
801 VECTOR2I dp = p.B - p.A;
802 pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq );
803 pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq );
804
805 pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq );
806 pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq );
807
808 nClip.A = n.LineProject( pClip.A );
809 nClip.B = n.LineProject( pClip.B );
810
811 return true;
812 }
813
814
Skew() const815 double DIFF_PAIR::Skew() const
816 {
817 return m_p.Length() - m_n.Length();
818 }
819
820
CoupledSegmentPairs(COUPLED_SEGMENTS_VEC & aPairs) const821 void DIFF_PAIR::CoupledSegmentPairs( COUPLED_SEGMENTS_VEC& aPairs ) const
822 {
823 SHAPE_LINE_CHAIN p( m_p );
824 SHAPE_LINE_CHAIN n( m_n );
825
826 p.Simplify();
827 n.Simplify();
828
829 for( int i = 0; i < p.SegmentCount(); i++ )
830 {
831 for( int j = 0; j < n.SegmentCount(); j++ )
832 {
833 SEG sp = p.Segment( i );
834 SEG sn = n.Segment( j );
835
836 SEG p_clip, n_clip;
837
838 int64_t dist = std::abs( sp.Distance( sn ) - m_width );
839
840 if( sp.ApproxParallel( sn, 2 ) && m_gapConstraint.Matches( dist ) &&
841 commonParallelProjection( sp, sn, p_clip, n_clip ) )
842 {
843 const COUPLED_SEGMENTS spair( p_clip, sp, i, n_clip, sn, j );
844 aPairs.push_back( spair );
845 }
846 }
847 }
848 }
849
850
CoupledLength(const SHAPE_LINE_CHAIN & aP,const SHAPE_LINE_CHAIN & aN) const851 int64_t DIFF_PAIR::CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const
852 {
853 int64_t total = 0;
854
855 for( int i = 0; i < aP.SegmentCount(); i++ )
856 {
857 for( int j = 0; j < aN.SegmentCount(); j++ )
858 {
859 SEG sp = aP.CSegment( i );
860 SEG sn = aN.CSegment( j );
861
862 SEG p_clip, n_clip;
863
864 int64_t dist = std::abs( sp.Distance(sn) - m_width );
865
866 if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) &&
867 commonParallelProjection( sp, sn, p_clip, n_clip ) )
868 total += p_clip.Length();
869 }
870 }
871
872 return total;
873 }
874
875
CoupledLength() const876 double DIFF_PAIR::CoupledLength() const
877 {
878 COUPLED_SEGMENTS_VEC pairs;
879
880 CoupledSegmentPairs( pairs );
881
882 double l = 0.0;
883
884 for( unsigned int i = 0; i < pairs.size(); i++ )
885 l += pairs[i].coupledP.Length();
886
887 return l;
888 }
889
890
CoupledLengthFactor() const891 double DIFF_PAIR::CoupledLengthFactor() const
892 {
893 double t = TotalLength();
894
895 if( t == 0.0 )
896 return 0.0;
897
898 return CoupledLength() / t;
899 }
900
901
TotalLength() const902 double DIFF_PAIR::TotalLength() const
903 {
904 double lenP = m_p.Length();
905 double lenN = m_n.Length();
906
907 return (lenN + lenP ) / 2.0;
908 }
909
910
CoupledLength(const SEG & aP,const SEG & aN) const911 int DIFF_PAIR::CoupledLength ( const SEG& aP, const SEG& aN ) const
912 {
913 SEG p_clip, n_clip;
914 int64_t dist = std::abs( aP.Distance( aN ) - m_width );
915
916 if( aP.ApproxParallel( aN ) && m_gapConstraint.Matches( dist ) &&
917 commonParallelProjection ( aP, aN, p_clip, n_clip ) )
918 return p_clip.Length();
919
920 return 0;
921 }
922
923 }
924