diff options
Diffstat (limited to 'pcbnew/router/pns_diff_pair.cpp')
| -rw-r--r-- | pcbnew/router/pns_diff_pair.cpp | 870 |
1 files changed, 870 insertions, 0 deletions
diff --git a/pcbnew/router/pns_diff_pair.cpp b/pcbnew/router/pns_diff_pair.cpp new file mode 100644 index 0000000..771928b --- /dev/null +++ b/pcbnew/router/pns_diff_pair.cpp @@ -0,0 +1,870 @@ +/* + * KiRouter - a push-and-(sometimes-)shove PCB router + * + * Copyright (C) 2013-2015 CERN + * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation, either version 3 of the License, or (at your + * option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <boost/foreach.hpp> + +#include <cstdio> +#include <cstdlib> +#include <limits> + +#include <geometry/shape.h> +#include <geometry/shape_rect.h> +#include <geometry/shape_circle.h> +#include <geometry/shape_segment.h> + +#include "direction.h" + +#include "pns_diff_pair.h" +#include "pns_router.h" +#include "pns_solid.h" +#include "pns_utils.h" + + +class PNS_LINE; + +PNS_DP_PRIMITIVE_PAIR::PNS_DP_PRIMITIVE_PAIR( PNS_ITEM* aPrimP, PNS_ITEM* aPrimN ) +{ + m_primP = aPrimP->Clone(); + m_primN = aPrimN->Clone(); + + m_anchorP = m_primP->Anchor( 0 ); + m_anchorN = m_primN->Anchor( 0 ); +} + + +void PNS_DP_PRIMITIVE_PAIR::SetAnchors( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN ) +{ + m_anchorP = aAnchorP; + m_anchorN = aAnchorN; +} + + +PNS_DP_PRIMITIVE_PAIR::PNS_DP_PRIMITIVE_PAIR( const VECTOR2I& aAnchorP, const VECTOR2I& aAnchorN ) +{ + m_anchorP = aAnchorP; + m_anchorN = aAnchorN; + m_primP = m_primN = NULL; +} + + +PNS_DP_PRIMITIVE_PAIR::PNS_DP_PRIMITIVE_PAIR( const PNS_DP_PRIMITIVE_PAIR& aOther ) +{ + m_primP = m_primN = NULL; + + if( aOther.m_primP ) + m_primP = aOther.m_primP->Clone(); + + if( aOther.m_primN ) + m_primN = aOther.m_primN->Clone(); + + m_anchorP = aOther.m_anchorP; + m_anchorN = aOther.m_anchorN; +} + + +PNS_DP_PRIMITIVE_PAIR& PNS_DP_PRIMITIVE_PAIR::operator=( const PNS_DP_PRIMITIVE_PAIR& aOther ) +{ + if( aOther.m_primP ) + m_primP = aOther.m_primP->Clone(); + if( aOther.m_primN ) + m_primN = aOther.m_primN->Clone(); + + m_anchorP = aOther.m_anchorP; + m_anchorN = aOther.m_anchorN; + + return *this; +} + + +PNS_DP_PRIMITIVE_PAIR::~PNS_DP_PRIMITIVE_PAIR() +{ + delete m_primP; + delete m_primN; +} + + +bool PNS_DP_PRIMITIVE_PAIR::Directional() const +{ + if( !m_primP ) + return false; + + return m_primP->OfKind( PNS_ITEM::SEGMENT ); +} + + +DIRECTION_45 PNS_DP_PRIMITIVE_PAIR::anchorDirection( PNS_ITEM* aItem, const VECTOR2I& aP ) const +{ + if( !aItem->OfKind ( PNS_ITEM::SEGMENT ) ) + return DIRECTION_45(); + + PNS_SEGMENT* s = static_cast<PNS_SEGMENT*>( aItem ); + + if( s->Seg().A == aP ) + return DIRECTION_45( s->Seg().A - s->Seg().B ); + else + return DIRECTION_45( s->Seg().B - s->Seg().A ); +} + + +DIRECTION_45 PNS_DP_PRIMITIVE_PAIR::DirP() const +{ + return anchorDirection( m_primP, m_anchorP ); +} + + +DIRECTION_45 PNS_DP_PRIMITIVE_PAIR::DirN() const +{ + return anchorDirection( m_primN, m_anchorN ); +} + + +static void drawGw( VECTOR2I p, int color ) +{ + SHAPE_LINE_CHAIN l; + + l.Append( p - VECTOR2I( -50000, -50000 ) ); + l.Append( p + VECTOR2I( -50000, -50000 ) ); + + l.Clear(); + l.Append( p - VECTOR2I( 50000, -50000 ) ); + l.Append( p + VECTOR2I( 50000, -50000 ) ); +} + + +static DIRECTION_45::AngleType angle( const VECTOR2I &a, const VECTOR2I &b ) +{ + DIRECTION_45 dir_a( a ); + DIRECTION_45 dir_b( b ); + + return dir_a.Angle( dir_b ); +} + + +static bool checkGap( const SHAPE_LINE_CHAIN &p, const SHAPE_LINE_CHAIN &n, int gap ) +{ + int i, j; + + for( i = 0; i < p.SegmentCount(); i++ ) + { + for( j = 0; j < n.SegmentCount() ; j++ ) + { + int dist = p.CSegment( i ).Distance( n.CSegment( j ) ); + + if( dist < gap - 100 ) + return false; + } + } + + return true; +} + + +void PNS_DP_GATEWAY::Reverse() +{ + m_entryN = m_entryN.Reverse(); + m_entryP = m_entryP.Reverse(); +} + + +bool PNS_DIFF_PAIR::BuildInitial( PNS_DP_GATEWAY& aEntry, PNS_DP_GATEWAY &aTarget, bool aPrefDiagonal ) +{ + SHAPE_LINE_CHAIN p = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorP(), aTarget.AnchorP(), aPrefDiagonal ); + SHAPE_LINE_CHAIN n = DIRECTION_45().BuildInitialTrace ( aEntry.AnchorN(), aTarget.AnchorN(), aPrefDiagonal ); + + int mask = aEntry.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE; + + SHAPE_LINE_CHAIN sum_n, sum_p; + m_p = p; + m_n = n; + + if( aEntry.HasEntryLines() ) + { + if( !aEntry.Entry().CheckConnectionAngle( *this, mask ) ) + return false; + + sum_p = aEntry.Entry().CP(); + sum_n = aEntry.Entry().CN(); + sum_p.Append( p ); + sum_n.Append( n ); + } + else + { + sum_p = p; + sum_n = n; + } + + mask = aTarget.AllowedAngles() | DIRECTION_45::ANG_STRAIGHT | DIRECTION_45::ANG_OBTUSE; + + m_p = sum_p; + m_n = sum_n; + + if( aTarget.HasEntryLines() ) + { + PNS_DP_GATEWAY t(aTarget) ; + t.Reverse(); + + if( !CheckConnectionAngle( t.Entry(), mask ) ) + return false; + + sum_p.Append( t.Entry().CP() ); + sum_n.Append( t.Entry().CN() ); + } + + m_p = sum_p; + m_n = sum_n; + + if( !checkGap ( p, n, m_gapConstraint ) ) + return false; + + if( p.SelfIntersecting() || n.SelfIntersecting() ) + return false; + + if( p.Intersects( n ) ) + return false; + + return true; +} + + +bool PNS_DIFF_PAIR::CheckConnectionAngle( const PNS_DIFF_PAIR& aOther, int aAllowedAngles ) const +{ + bool checkP, checkN; + + if( m_p.SegmentCount() == 0 || aOther.m_p.SegmentCount() == 0 ) + checkP = true; + else + { + DIRECTION_45 p0( m_p.CSegment( -1 ) ); + DIRECTION_45 p1( aOther.m_p.CSegment( 0 ) ); + + checkP = ( p0.Angle( p1 ) & aAllowedAngles ) != 0; + } + + if( m_n.SegmentCount() == 0 || aOther.m_n.SegmentCount() == 0 ) + checkN = true; + else + { + DIRECTION_45 n0( m_n.CSegment( -1 ) ); + DIRECTION_45 n1( aOther.m_n.CSegment( 0 ) ); + + checkN = ( n0.Angle( n1 ) & aAllowedAngles ) != 0; + } + + return checkP && checkN; +} + + +const PNS_DIFF_PAIR PNS_DP_GATEWAY::Entry() const +{ + return PNS_DIFF_PAIR( m_entryP, m_entryN, 0 ); +} + + +void PNS_DP_GATEWAYS::BuildOrthoProjections( PNS_DP_GATEWAYS& aEntries, + const VECTOR2I& aCursorPos, int aOrthoScore ) +{ + BOOST_FOREACH( PNS_DP_GATEWAY g, aEntries.Gateways() ) + { + VECTOR2I midpoint( ( g.AnchorP() + g.AnchorN() ) / 2 ); + SEG guide_s( midpoint, midpoint + VECTOR2I( 1, 0 ) ); + SEG guide_d( midpoint, midpoint + VECTOR2I( 1, 1 ) ); + + VECTOR2I proj_s = guide_s.LineProject( aCursorPos ); + VECTOR2I proj_d = guide_d.LineProject( aCursorPos ); + + int dist_s = ( proj_s - aCursorPos ).EuclideanNorm(); + int dist_d = ( proj_d - aCursorPos ).EuclideanNorm(); + + + VECTOR2I proj = ( dist_s < dist_d ? proj_s : proj_d ); + + PNS_DP_GATEWAYS targets( m_gap ); + + targets.m_viaGap = m_viaGap; + targets.m_viaDiameter = m_viaDiameter; + targets.m_fitVias = m_fitVias; + + targets.BuildForCursor( proj ); + + BOOST_FOREACH( PNS_DP_GATEWAY t, targets.Gateways() ) + { + t.SetPriority( aOrthoScore ); + m_gateways.push_back( t ); + } + } +} + + +bool PNS_DP_GATEWAYS::FitGateways( PNS_DP_GATEWAYS& aEntry, PNS_DP_GATEWAYS& aTarget, + bool aPrefDiagonal, PNS_DIFF_PAIR& aDp ) +{ + std::vector<DP_CANDIDATE> candidates; + + BOOST_FOREACH( PNS_DP_GATEWAY g_entry, aEntry.Gateways() ) + { + BOOST_FOREACH( PNS_DP_GATEWAY g_target, aTarget.Gateways() ) + { + for( int attempt = 0; attempt < 2; attempt++ ) + { + PNS_DIFF_PAIR l( m_gap ); + + if( l.BuildInitial( g_entry, g_target, aPrefDiagonal ^ ( attempt ? true : false ) ) ) + { + int score = ( attempt == 1 ? -3 : 0 ); + score +=g_entry.Priority(); + score +=g_target.Priority(); + + DP_CANDIDATE c; + c.score = score; + c.p = l.CP(); + c.n = l.CN(); + candidates.push_back( c ); + } + } + } + } + + int bestScore = -1000; + DP_CANDIDATE best; + bool found = false; + + BOOST_FOREACH( DP_CANDIDATE c, candidates ) + { + if( c.score > bestScore ) + { + bestScore = c.score; + best = c; + found = true; + } + } + + if( found ) + { + aDp.SetGap( m_gap ); + aDp.SetShape( best.p, best.n ); + return true; + } + + return false; +} + + +bool PNS_DP_GATEWAYS::checkDiagonalAlignment( const VECTOR2I& a, const VECTOR2I& b ) const +{ + VECTOR2I dir ( std::abs (a.x - b.x), std::abs ( a.y - b.y )); + + return (dir.x == 0 && dir.y != 0) || (dir.x == dir.y) || (dir.y == 0 && dir.x != 0); +} + + +void PNS_DP_GATEWAYS::BuildFromPrimitivePair( PNS_DP_PRIMITIVE_PAIR aPair, bool aPreferDiagonal ) +{ + VECTOR2I majorDirection; + VECTOR2I p0_p, p0_n; + int orthoFanDistance; + int diagFanDistance; + const SHAPE* shP = NULL; + + if( aPair.PrimP() == NULL ) + { + BuildGeneric( aPair.AnchorP(), aPair.AnchorN(), true ); + return; + } + + const int pvMask = PNS_ITEM::SOLID | PNS_ITEM::VIA; + + if( aPair.PrimP()->OfKind( pvMask ) && aPair.PrimN()->OfKind( pvMask ) ) + { + p0_p = aPair.AnchorP(); + p0_n = aPair.AnchorN(); + + shP = aPair.PrimP()->Shape(); + } + else if( aPair.PrimP()->OfKind( PNS_ITEM::SEGMENT ) && aPair.PrimN()->OfKind( PNS_ITEM::SEGMENT ) ) + { + buildDpContinuation( aPair, aPreferDiagonal ); + + return; + } + + majorDirection = ( p0_p - p0_n ).Perpendicular(); + + if( shP == NULL ) + return; + + switch( shP->Type() ) + { + case SH_RECT: + { + int w = static_cast<const SHAPE_RECT*>( shP )->GetWidth(); + int h = static_cast<const SHAPE_RECT*>( shP )->GetHeight(); + + if( w < h ) + std::swap( w, h ); + + orthoFanDistance = w * 3/4; + diagFanDistance = ( w - h ) / 2; + break; + } + + case SH_SEGMENT: + { + int w = static_cast<const SHAPE_SEGMENT*>( shP )->GetWidth(); + SEG s = static_cast<const SHAPE_SEGMENT*>( shP )->GetSeg(); + + orthoFanDistance = w + ( s.B - s.A ).EuclideanNorm() / 2; + diagFanDistance = ( s.B - s.A ).EuclideanNorm() / 2; + break; + } + + default: + BuildGeneric ( p0_p, p0_n, true ); + return; + } + + if( checkDiagonalAlignment( p0_p, p0_n ) ) + { + int padDist = ( p0_p - p0_n ).EuclideanNorm(); + + for( int k = 0; k < 2; k++ ) + { + VECTOR2I dir, dp, dv; + + if( k == 0 ) + { + dir = majorDirection.Resize( orthoFanDistance ); + int d = ( padDist - m_gap ) / 2; + + dp = dir.Resize( d ); + dv = ( p0_n - p0_p ).Resize( d ); + } + else + { + dir = majorDirection.Resize( diagFanDistance ); + int d = ( padDist - m_gap ) / 2; + dp = dir.Resize( d ); + dv = ( p0_n - p0_p ).Resize( d ); + } + + for( int i = 0; i < 2; i++ ) + { + int sign = i ? -1 : 1; + + VECTOR2I gw_p( p0_p + sign * ( dir + dp ) + dv ); + VECTOR2I gw_n( p0_n + sign * ( dir + dp ) - dv ); + + SHAPE_LINE_CHAIN entryP( p0_p, p0_p + sign * dir, gw_p ); + SHAPE_LINE_CHAIN entryN( p0_n, p0_n + sign * dir, gw_n ); + + PNS_DP_GATEWAY gw( gw_p, gw_n, false ); + + gw.SetEntryLines( entryP, entryN ); + gw.SetPriority( 100 - k ); + m_gateways.push_back( gw ); + } + } + } + + BuildGeneric( p0_p, p0_n, true ); +} + + +void PNS_DP_GATEWAYS::BuildForCursor( const VECTOR2I& aCursorPos ) +{ + int gap = m_fitVias ? m_viaGap + m_viaDiameter : m_gap; + + for( int attempt = 0; attempt < 2; attempt++ ) + { + for( int i = 0; i < 4; i++ ) + { + VECTOR2I dir; + + if( !attempt ) + { + dir = VECTOR2I( gap, gap ).Resize( gap / 2 ); + + if( i % 2 == 0 ) + dir.x = -dir.x; + + if( i / 2 == 0 ) + dir.y = -dir.y; + } + else + { + if( i /2 == 0 ) + dir = VECTOR2I( gap / 2 * ( ( i % 2 ) ? -1 : 1 ), 0 ); + else + dir = VECTOR2I( 0, gap / 2 * ( ( i % 2 ) ? -1 : 1) ); + } + + if( m_fitVias ) + BuildGeneric( aCursorPos + dir, aCursorPos - dir, true, true ); + else + m_gateways.push_back( PNS_DP_GATEWAY( aCursorPos + dir, + aCursorPos - dir, attempt ? true : false ) ); + + drawGw ( aCursorPos + dir, 2 ); + drawGw ( aCursorPos - dir, 3 ); + } + } +} + + +void PNS_DP_GATEWAYS::buildEntries( const VECTOR2I& p0_p, const VECTOR2I& p0_n ) +{ + BOOST_FOREACH( PNS_DP_GATEWAY &g, m_gateways ) + { + if( !g.HasEntryLines() ) + { + SHAPE_LINE_CHAIN lead_p = DIRECTION_45().BuildInitialTrace ( g.AnchorP(), p0_p, g.IsDiagonal() ).Reverse(); + SHAPE_LINE_CHAIN lead_n = DIRECTION_45().BuildInitialTrace ( g.AnchorN(), p0_n, g.IsDiagonal() ).Reverse(); + g.SetEntryLines( lead_p, lead_n ); + } + } +} + + +void PNS_DP_GATEWAYS::buildDpContinuation( PNS_DP_PRIMITIVE_PAIR aPair, bool aIsDiagonal ) +{ + PNS_DP_GATEWAY gw( aPair.AnchorP(), aPair.AnchorN(), aIsDiagonal ); + gw.SetPriority( 100 ); + m_gateways.push_back( gw ); + + if( !aPair.Directional() ) + return; + + DIRECTION_45 dP = aPair.DirP(); + DIRECTION_45 dN = aPair.DirN(); + + int gap = ( aPair.AnchorP() - aPair.AnchorN() ).EuclideanNorm(); + + VECTOR2I vdP = aPair.AnchorP() + dP.Left().ToVector(); + VECTOR2I vdN = aPair.AnchorN() + dN.Left().ToVector(); + + PNS_SEGMENT* sP = static_cast<PNS_SEGMENT*>( aPair.PrimP() ); + + VECTOR2I t1, t2; + + if( sP->Seg().Side( vdP ) == sP->Seg().Side( vdN ) ) + { + t1 = aPair.AnchorP() + dP.Left().ToVector().Resize( gap ); + t2 = aPair.AnchorN() + dP.Right().ToVector().Resize( gap ); + } + else + { + t1 = aPair.AnchorP() + dP.Right().ToVector().Resize( gap ); + t2 = aPair.AnchorN() + dP.Left().ToVector().Resize( gap ); + } + + PNS_DP_GATEWAY gwL( t2, aPair.AnchorN(), !aIsDiagonal ); + SHAPE_LINE_CHAIN ep = dP.BuildInitialTrace( aPair.AnchorP(), t2, !aIsDiagonal ); + + gwL.SetPriority( 10 ); + gwL.SetEntryLines( ep , SHAPE_LINE_CHAIN() ); + + m_gateways.push_back( gwL ); + + PNS_DP_GATEWAY gwR( aPair.AnchorP(), t1, !aIsDiagonal ); + SHAPE_LINE_CHAIN en = dP.BuildInitialTrace( aPair.AnchorN(), t1, !aIsDiagonal ); + gwR.SetPriority( 10) ; + gwR.SetEntryLines( SHAPE_LINE_CHAIN(), en ); + + m_gateways.push_back( gwR ); +} + + +void PNS_DP_GATEWAYS::BuildGeneric( const VECTOR2I& p0_p, const VECTOR2I& p0_n, bool aBuildEntries, bool aViaMode ) +{ + SEG st_p[2], st_n[2]; + SEG d_n[2], d_p[2]; + + const int padToGapThreshold = 3; + int padDist = ( p0_p - p0_p ).EuclideanNorm(); + + st_p[0] = SEG(p0_p + VECTOR2I( -100, 0 ), p0_p + VECTOR2I( 100, 0 ) ); + st_n[0] = SEG(p0_n + VECTOR2I( -100, 0 ), p0_n + VECTOR2I( 100, 0 ) ); + st_p[1] = SEG(p0_p + VECTOR2I( 0, -100 ), p0_p + VECTOR2I( 0, 100 ) ); + st_n[1] = SEG(p0_n + VECTOR2I( 0, -100 ), p0_n + VECTOR2I( 0, 100 ) ); + d_p[0] = SEG( p0_p + VECTOR2I( -100, -100 ), p0_p + VECTOR2I( 100, 100 ) ); + d_p[1] = SEG( p0_p + VECTOR2I( 100, -100 ), p0_p + VECTOR2I( -100, 100 ) ); + d_n[0] = SEG( p0_n + VECTOR2I( -100, -100 ), p0_n + VECTOR2I( 100, 100 ) ); + d_n[1] = SEG( p0_n + VECTOR2I( 100, -100 ), p0_n + VECTOR2I( -100, 100 ) ); + + // midpoint exit & side-by exits + for( int i = 0; i < 2; i++ ) + { + bool straightColl = st_p[i].Collinear( st_n[i] ); + bool diagColl = d_p[i].Collinear( d_n[i] ); + + if( straightColl || diagColl ) + { + VECTOR2I dir = ( p0_n - p0_p ).Resize( m_gap / 2 ); + VECTOR2I m = ( p0_p + p0_n ) / 2; + int prio = ( padDist > padToGapThreshold * m_gap ? 2 : 1); + + if( !aViaMode ) + { + m_gateways.push_back( PNS_DP_GATEWAY( m - dir, m + dir, diagColl, DIRECTION_45::ANG_RIGHT, prio ) ); + + dir = ( p0_n - p0_p ).Resize( m_gap ); + m_gateways.push_back( PNS_DP_GATEWAY( p0_p - dir, p0_p - dir + dir.Perpendicular(), diagColl ) ); + m_gateways.push_back( PNS_DP_GATEWAY( p0_p - dir, p0_p - dir - dir.Perpendicular(), diagColl ) ); + m_gateways.push_back( PNS_DP_GATEWAY( p0_n + dir + dir.Perpendicular(), p0_n + dir, diagColl ) ); + m_gateways.push_back( PNS_DP_GATEWAY( p0_n + dir - dir.Perpendicular(), p0_n + dir, diagColl ) ); + } + } + } + + for( int i = 0; i < 2; i++ ) + { + for( int j = 0; j < 2; j++ ) + { + OPT_VECTOR2I ips[2]; + + ips[0] = d_n[i].IntersectLines( d_p[j] ); + ips[1] = st_p[i].IntersectLines( st_n[j] ); + + if( d_n[i].Collinear( d_p[j] ) ) + ips[0] = boost::none; + if( st_p[i].Collinear( st_p[j] ) ) + ips[1] = boost::none; + + // diagonal-diagonal and straight-straight cases - the most typical case if the pads + // are on the same straight/diagonal line + for( int k = 0; k < 2; k++ ) + { + if( ips[k] ) + { + const VECTOR2I m( *ips[k] ); + + if( m != p0_p && m != p0_n ) + { + int prio = ( padDist > padToGapThreshold * m_gap ? 10 : 20 ); + VECTOR2I g_p( ( p0_p - m ).Resize( (double) m_gap * M_SQRT1_2 ) ); + VECTOR2I g_n( ( p0_n - m ).Resize( (double) m_gap * M_SQRT1_2 ) ); + + m_gateways.push_back( PNS_DP_GATEWAY( m + g_p, m + g_n, k == 0 ? true : false, DIRECTION_45::ANG_OBTUSE, prio ) ); + } + } + } + + ips[0] = st_n[i].IntersectLines( d_p[j] ); + ips[1] = st_p[i].IntersectLines( d_n[j] ); + +// diagonal-straight cases: 8 possibilities of "weirder" exists + for( int k = 0; k < 2; k++ ) + { + if( ips[k] ) + { + const VECTOR2I m( *ips[k] ); + + if( !aViaMode && m != p0_p && m != p0_n ) + { + VECTOR2I g_p, g_n; + + g_p = ( p0_p - m ).Resize( (double) m_gap * M_SQRT2 ); + g_n = ( p0_n - m ).Resize( (double) m_gap ); + + if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE ) + m_gateways.push_back( PNS_DP_GATEWAY( m + g_p, m + g_n, true ) ); + + g_p = ( p0_p - m ).Resize( m_gap ); + g_n = ( p0_n - m ).Resize( (double) m_gap * M_SQRT2 ); + + if( angle( g_p, g_n ) != DIRECTION_45::ANG_ACUTE ) + m_gateways.push_back( PNS_DP_GATEWAY( m + g_p, m + g_n, true ) ); + } + } + } + } + } + + if( aBuildEntries ) + buildEntries( p0_p, p0_n ); +} + + +PNS_DP_PRIMITIVE_PAIR PNS_DIFF_PAIR::EndingPrimitives() +{ + if( m_hasVias ) + return PNS_DP_PRIMITIVE_PAIR( &m_via_p, &m_via_n ); + else + { + const PNS_LINE lP( PLine() ); + const PNS_LINE lN( NLine() ); + + PNS_SEGMENT sP( lP, lP.CSegment( -1 ) ); + PNS_SEGMENT sN( lN, lN.CSegment( -1 ) ); + + PNS_DP_PRIMITIVE_PAIR dpair( &sP, &sN ); + dpair.SetAnchors( sP.Seg().B, sN.Seg().B ); + + return dpair; + } +} + + +bool commonParallelProjection( SEG n, SEG p, SEG &pClip, SEG& nClip ) +{ + SEG n_proj_p( p.LineProject( n.A ), p.LineProject( n.B ) ); + + int64_t t_a = 0; + int64_t t_b = p.TCoef( p.B ); + + int64_t tproj_a = p.TCoef( n_proj_p.A ); + int64_t tproj_b = p.TCoef( n_proj_p.B ); + + if( t_b < t_a ) + std::swap( t_b, t_a ); + + if( tproj_b < tproj_a ) + std::swap( tproj_b, tproj_a ); + + if( t_b <= tproj_a ) + return false; + + if( t_a >= tproj_b ) + return false; + + int64_t t[4] = { 0, p.TCoef( p.B ), p.TCoef( n_proj_p.A ), p.TCoef( n_proj_p.B ) }; + std::vector<int64_t> tv( t, t + 4 ); + std::sort( tv.begin(), tv.end() ); // fixme: awful and disgusting way of finding 2 midpoints + + int64_t pLenSq = p.SquaredLength(); + + VECTOR2I dp = p.B - p.A; + pClip.A.x = p.A.x + rescale( (int64_t)dp.x, tv[1], pLenSq ); + pClip.A.y = p.A.y + rescale( (int64_t)dp.y, tv[1], pLenSq ); + + pClip.B.x = p.A.x + rescale( (int64_t)dp.x, tv[2], pLenSq ); + pClip.B.y = p.A.y + rescale( (int64_t)dp.y, tv[2], pLenSq ); + + nClip.A = n.LineProject( pClip.A ); + nClip.B = n.LineProject( pClip.B ); + + return true; +} + + +double PNS_DIFF_PAIR::Skew() const +{ + return m_p.Length() - m_n.Length(); +} + + +void PNS_DIFF_PAIR::CoupledSegmentPairs( COUPLED_SEGMENTS_VEC& aPairs ) const +{ + SHAPE_LINE_CHAIN p( m_p ); + SHAPE_LINE_CHAIN n( m_n ); + + p.Simplify(); + n.Simplify(); + + for( int i = 0; i < p.SegmentCount(); i++ ) + { + for( int j = 0; j < n.SegmentCount(); j++ ) + { + SEG sp = p.CSegment( i ); + SEG sn = n.CSegment( j ); + + SEG p_clip, n_clip; + + int64_t dist = std::abs( sp.Distance( sn ) - m_width ); + + if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) && commonParallelProjection( sp, sn, p_clip, n_clip ) ) + { + const COUPLED_SEGMENTS spair( p_clip, sp, i, n_clip, sn, j ); + aPairs.push_back( spair ); + } + } + } +} + + +int64_t PNS_DIFF_PAIR::CoupledLength( const SHAPE_LINE_CHAIN& aP, const SHAPE_LINE_CHAIN& aN ) const +{ + int64_t total = 0; + + for( int i = 0; i < aP.SegmentCount(); i++ ) + { + for( int j = 0; j < aN.SegmentCount(); j++ ) + { + SEG sp = aP.CSegment( i ); + SEG sn = aN.CSegment( j ); + + SEG p_clip, n_clip; + + int64_t dist = std::abs( sp.Distance(sn) - m_width ); + + if( sp.ApproxParallel( sn ) && m_gapConstraint.Matches( dist ) && + commonParallelProjection( sp, sn, p_clip, n_clip ) ) + total += p_clip.Length(); + } + } + + return total; +} + + +double PNS_DIFF_PAIR::CoupledLength() const +{ + COUPLED_SEGMENTS_VEC pairs; + + CoupledSegmentPairs( pairs ); + + double l = 0.0; + for( unsigned int i = 0; i < pairs.size(); i++ ) + l += pairs[i].coupledP.Length(); + + return l; +} + + +double PNS_DIFF_PAIR::CoupledLengthFactor() const +{ + double t = TotalLength(); + + if( t == 0.0 ) + return 0.0; + + return CoupledLength() / t; +} + + +double PNS_DIFF_PAIR::TotalLength() const +{ + double lenP = m_p.Length(); + double lenN = m_n.Length(); + + return (lenN + lenP ) / 2.0; +} + + +int PNS_DIFF_PAIR::CoupledLength ( const SEG& aP, const SEG& aN ) const +{ + SEG p_clip, n_clip; + int64_t dist = std::abs( aP.Distance( aN ) - m_width ); + + if( aP.ApproxParallel( aN ) && m_gapConstraint.Matches( dist ) && + commonParallelProjection ( aP, aN, p_clip, n_clip ) ) + return p_clip.Length(); + + return 0; +} |