PNS::SHOVE Class Reference

SHOVE. More...

#include <pns_shove.h>

Inheritance diagram for PNS::SHOVE:

Classes
struct	SPRINGBACK_TAG

Public Types
enum	SHOVE_STATUS {   SH_OK = 0, SH_NULL, SH_INCOMPLETE, SH_HEAD_MODIFIED,   SH_TRY_WALK }

Public Member Functions
	SHOVE (NODE *aWorld, ROUTER *aRouter)
	~SHOVE ()
virtual LOGGER *	Logger () override
SHOVE_STATUS	ShoveLines (const LINE &aCurrentHead)
SHOVE_STATUS	ShoveMultiLines (const ITEM_SET &aHeadSet)
SHOVE_STATUS	ShoveDraggingVia (const VIA_HANDLE aOldVia, const VECTOR2I &aWhere, VIA_HANDLE &aNewVia)
SHOVE_STATUS	ShoveObstacleLine (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
void	ForceClearance (bool aEnabled, int aClearance)
NODE *	CurrentNode ()
const LINE	NewHead () const
void	SetInitialLine (LINE &aInitial)
bool	AddLockedSpringbackNode (NODE *aNode)
void	UnlockSpringbackNode (NODE *aNode)
bool	RewindSpringbackTo (NODE *aNode)
ROUTER *	Router () const
	Return current router settings. More...
ROUTING_SETTINGS &	Settings () const
	Return the logger object, allowing to dump geometry to a file. More...
void	SetLogger (LOGGER *aLogger)
void	SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
	Assign a debug decorator allowing this algo to draw extra graphics for visual debugging. More...
DEBUG_DECORATOR *	Dbg () const
const BOX2I &	VisibleViewArea () const

Protected Attributes
DEBUG_DECORATOR *	m_debugDecorator
ROUTER *	m_router

Private Types
typedef std::vector< SHAPE_LINE_CHAIN >	HULL_SET
typedef OPT< LINE >	OPT_LINE
typedef std::pair< LINE, LINE >	LINE_PAIR
typedef std::vector< LINE_PAIR >	LINE_PAIR_VEC

Private Member Functions
SHOVE_STATUS	shoveLineToHullSet (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
NODE *	reduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
bool	pushSpringback (NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
SHOVE_STATUS	shoveLineFromLoneVia (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
bool	checkShoveDirection (const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
SHOVE_STATUS	onCollidingArc (LINE &aCurrent, ARC *aObstacleArc)
SHOVE_STATUS	onCollidingLine (LINE &aCurrent, LINE &aObstacle)
SHOVE_STATUS	onCollidingSegment (LINE &aCurrent, SEGMENT *aObstacleSeg)
SHOVE_STATUS	onCollidingSolid (LINE &aCurrent, ITEM *aObstacle)
SHOVE_STATUS	onCollidingVia (ITEM *aCurrent, VIA *aObstacleVia)
SHOVE_STATUS	onReverseCollidingVia (LINE &aCurrent, VIA *aObstacleVia)
SHOVE_STATUS	pushOrShoveVia (VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
OPT_BOX2I	totalAffectedArea () const
void	unwindLineStack (LINKED_ITEM *aSeg)
void	unwindLineStack (ITEM *aItem)
void	runOptimizer (NODE *aNode)
bool	pushLineStack (const LINE &aL, bool aKeepCurrentOnTop=false)
void	popLineStack ()
LINE	assembleLine (const LINKED_ITEM *aSeg, int *aIndex=NULL)
void	replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)
void	replaceLine (LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
LINE *	findRootLine (LINE *aLine)
SHOVE_STATUS	shoveIteration (int aIter)
SHOVE_STATUS	shoveMainLoop ()
int	getClearance (const ITEM *aA, const ITEM *aB) const
int	getHoleClearance (const ITEM *aA, const ITEM *aB) const
void	sanityCheck (LINE *aOld, LINE *aNew)

Private Attributes
OPT_BOX2I	m_affectedArea
std::vector< SPRINGBACK_TAG >	m_nodeStack
std::vector< LINE >	m_lineStack
std::vector< LINE >	m_optimizerQueue
std::unordered_map< const LINKED_ITEM *, LINE * >	m_rootLineHistory
NODE *	m_root
NODE *	m_currentNode
int	m_restrictSpringbackTagId
OPT_LINE	m_newHead
LOGGER	m_logger
VIA *	m_draggedVia
int	m_iter
int	m_forceClearance
bool	m_multiLineMode

Detailed Description

SHOVE.

The actual Push and Shove algorithm.

Definition at line 48 of file pns_shove.h.

Member Typedef Documentation

HULL_SET

typedef std::vector<SHAPE_LINE_CHAIN> PNS::SHOVE::HULL_SET

private

Definition at line 94 of file pns_shove.h.

LINE_PAIR

typedef std::pair<LINE, LINE> PNS::SHOVE::LINE_PAIR

private

Definition at line 96 of file pns_shove.h.

LINE_PAIR_VEC

typedef std::vector<LINE_PAIR> PNS::SHOVE::LINE_PAIR_VEC

private

Definition at line 97 of file pns_shove.h.

OPT_LINE

typedef OPT<LINE> PNS::SHOVE::OPT_LINE

private

Definition at line 95 of file pns_shove.h.

Member Enumeration Documentation

SHOVE_STATUS

enum PNS::SHOVE::SHOVE_STATUS

Enumerator
SH_OK
SH_NULL
SH_INCOMPLETE
SH_HEAD_MODIFIED
SH_TRY_WALK

Definition at line 52 of file pns_shove.h.

    {
        SH_OK = 0,
        SH_NULL,
        SH_INCOMPLETE,
        SH_HEAD_MODIFIED,
        SH_TRY_WALK
    };

Constructor & Destructor Documentation

SHOVE()

PNS::SHOVE::SHOVE	(	NODE *	aWorld,
		ROUTER *	aRouter
	)

Definition at line 149 of file pns_shove.cpp.

                                            :
    ALGO_BASE( aRouter )
{
    m_forceClearance = -1;
    m_root = aWorld;
    m_currentNode = aWorld;
    SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );

    // Initialize other temporary variables:
    m_draggedVia = NULL;
    m_iter = 0;
    m_multiLineMode = false;
    m_restrictSpringbackTagId = 0;
}

References PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInterface(), m_currentNode, m_draggedVia, m_forceClearance, m_iter, m_multiLineMode, m_restrictSpringbackTagId, m_root, NULL, and PNS::ALGO_BASE::SetDebugDecorator().

~SHOVE()

PNS::SHOVE::~SHOVE

(

)

Definition at line 165 of file pns_shove.cpp.

{
    std::unordered_set<LINE*> alreadyDeleted;
    for( auto it : m_rootLineHistory )
    {
        auto it2 = alreadyDeleted.find( it.second );
        if( it2 == alreadyDeleted.end() )
        {
            alreadyDeleted.insert( it.second );
            delete it.second;
        }
    }
}

References m_rootLineHistory.

Member Function Documentation

AddLockedSpringbackNode()

bool PNS::SHOVE::AddLockedSpringbackNode

(

NODE *

aNode

)

Definition at line 1761 of file pns_shove.cpp.

{
    SPRINGBACK_TAG sp;
    sp.m_node = aNode;
    sp.m_locked = true;

    m_nodeStack.push_back(sp);
    return true;
}

References PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, and m_nodeStack.

assembleLine()

LINE PNS::SHOVE::assembleLine ( const LINKED_ITEM *  aSeg, int *  aIndex = NULL  )

private

Definition at line 180 of file pns_shove.cpp.

{
    return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
}

References PNS::NODE::AssembleLine(), and m_currentNode.

Referenced by onCollidingArc(), onCollidingSegment(), onReverseCollidingVia(), pushOrShoveVia(), and shoveIteration().

checkShoveDirection()

bool PNS::SHOVE::checkShoveDirection ( const LINE &  aCurLine, const LINE &  aObstacleLine, const LINE &  aShovedLine  ) const

private

Definition at line 193 of file pns_shove.cpp.

{
    SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
    checker.AddPolyline( aObstacleLine.CLine() );
    checker.AddPolyline( aShovedLine.CLine().Reverse() );

    bool inside = checker.IsInside();

    return !inside;
}

References SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER::AddPolyline(), PNS::LINE::CLine(), PNS::LINE::CPoint(), and SHAPE_LINE_CHAIN::Reverse().

Referenced by shoveLineToHullSet().

CurrentNode()

NODE * PNS::SHOVE::CurrentNode

(

)

Definition at line 1740 of file pns_shove.cpp.

{
    return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
}

References m_nodeStack, and m_root.

Referenced by PNS::DIFF_PAIR_PLACER::rhShoveOnly().

Dbg()

DEBUG_DECORATOR* PNS::ALGO_BASE::Dbg ( ) const

inlineinherited

Definition at line 78 of file pns_algo_base.h.

    {
        return m_debugDecorator;
    }

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by PNS::MEANDER_PLACER::doMove(), PNS::COMPONENT_DRAGGER::Drag(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dragWalkaround(), PNS::MEANDER_SKEW_PLACER::Move(), PNS::DP_MEANDER_PLACER::Move(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), replaceLine(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), runOptimizer(), shoveIteration(), ShoveLines(), shoveLineToHullSet(), ShoveObstacleLine(), PNS::WALKAROUND::singleStep(), PNS::DRAGGER::Start(), and PNS::DRAGGER::tryWalkaround().

findRootLine()

LINE * PNS::SHOVE::findRootLine ( LINE *  aLine )

private

Definition at line 1639 of file pns_shove.cpp.

{
    for( auto link : aLine->Links() )
    {
        if( auto seg = dyn_cast<SEGMENT*>( link ) )
        {
            auto it = m_rootLineHistory.find( seg );

            if( it != m_rootLineHistory.end() )
                return it->second;
        }
    }

    return nullptr;
}

References PNS::LINK_HOLDER::Links(), and m_rootLineHistory.

Referenced by runOptimizer().

ForceClearance()

void PNS::SHOVE::ForceClearance ( bool  aEnabled, int  aClearance  )

inline

Definition at line 75 of file pns_shove.h.

    {
        if( aEnabled )
            m_forceClearance = aClearance;
        else
            m_forceClearance = -1;
    }

References m_forceClearance.

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk().

getClearance()

int PNS::SHOVE::getClearance ( const ITEM *  aA, const ITEM *  aB  ) const

private

Definition at line 125 of file pns_shove.cpp.

{
    if( m_forceClearance >= 0 )
        return m_forceClearance;

    return m_currentNode->GetClearance( aA, aB );
}

References PNS::NODE::GetClearance(), m_currentNode, and m_forceClearance.

Referenced by onCollidingVia(), shoveLineFromLoneVia(), and ShoveObstacleLine().

getHoleClearance()

int PNS::SHOVE::getHoleClearance ( const ITEM *  aA, const ITEM *  aB  ) const

private

Definition at line 133 of file pns_shove.cpp.

{
    if( m_forceClearance >= 0 )
        return m_forceClearance;

    return m_currentNode->GetHoleClearance( aA, aB );
}

References PNS::NODE::GetHoleClearance(), m_currentNode, and m_forceClearance.

Referenced by shoveLineFromLoneVia(), and ShoveObstacleLine().

Logger()

virtual LOGGER* PNS::SHOVE::Logger ( )

inlineoverridevirtual

Reimplemented from PNS::ALGO_BASE.

Definition at line 64 of file pns_shove.h.

    {
        return &m_logger;
    }

References m_logger.

NewHead()

const LINE PNS::SHOVE::NewHead

(

)

const

Definition at line 1746 of file pns_shove.cpp.

{
    assert( m_newHead );

    return *m_newHead;
}

References m_newHead.

onCollidingArc()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingArc ( LINE &  aCurrent, ARC *  aObstacleArc  )

private

Definition at line 522 of file pns_shove.cpp.

{
    int segIndex;
    LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
    LINE shovedLine( obstacleLine );
    ARC tmp( *aObstacleArc );

    if( obstacleLine.HasLockedSegments() )
        return SH_TRY_WALK;

    SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );

    const double extensionWalkThreshold = 1.0;

    double obsLen = obstacleLine.CLine().Length();
    double shovedLen = shovedLine.CLine().Length();
    double extensionFactor = 0.0;

    if( obsLen != 0.0f )
        extensionFactor = shovedLen / obsLen - 1.0;

    if( extensionFactor > extensionWalkThreshold )
        return SH_TRY_WALK;

    assert( obstacleLine.LayersOverlap( &shovedLine ) );

    if ( Dbg() )
    {
        Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
        Dbg()->AddLine( tmp.CLine(), 0, 10000, "obstacle-segment" );
        Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
        Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
        Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
        Dbg()->EndGroup();
    }

    if( rv == SH_OK )
    {
        if( shovedLine.Marker() & MK_HEAD )
        {
            if( m_multiLineMode )
                return SH_INCOMPLETE;

            m_newHead = shovedLine;
        }

        int rank = aCurrent.Rank();
        shovedLine.SetRank( rank - 1 );

        sanityCheck( &obstacleLine, &shovedLine );
        replaceLine( obstacleLine, shovedLine );

        if( !pushLineStack( shovedLine ) )
            rv = SH_INCOMPLETE;
    }

    return rv;
}

References PNS::DEBUG_DECORATOR::AddLine(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::ARC::CLine(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, and ShoveObstacleLine().

Referenced by shoveIteration().

onCollidingLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingLine ( LINE &  aCurrent, LINE &  aObstacle  )

private

Definition at line 585 of file pns_shove.cpp.

{
    LINE shovedLine( aObstacle );

    SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );

    Dbg()->BeginGroup( "on-colliding-line" );
    Dbg()->AddLine( aObstacle.CLine(), 1, 100000, "obstacle-line" );
    Dbg()->AddLine( aCurrent.CLine(), 2, 150000, "current-line" );
    Dbg()->AddLine( shovedLine.CLine(), 3, 200000, "shoved-line" );

    if( rv == SH_OK )
    {
        if( shovedLine.Marker() & MK_HEAD )
        {
            if( m_multiLineMode )
                return SH_INCOMPLETE;

            m_newHead = shovedLine;
        }

        sanityCheck( &aObstacle, &shovedLine );
        replaceLine( aObstacle, shovedLine );

        int rank = aObstacle.Rank();
        shovedLine.SetRank( rank - 1 );


        if( !pushLineStack( shovedLine ) )
        {
            rv = SH_INCOMPLETE;
        }
    }

    return rv;
}

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and ShoveObstacleLine().

Referenced by shoveIteration().

onCollidingSegment()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSegment ( LINE &  aCurrent, SEGMENT *  aObstacleSeg  )

private

Definition at line 455 of file pns_shove.cpp.

{
    int segIndex;
    LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
    LINE shovedLine( obstacleLine );
    SEGMENT tmp( *aObstacleSeg );

    if( obstacleLine.HasLockedSegments() )
        return SH_TRY_WALK;

    SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );

    const double extensionWalkThreshold = 1.0;

    double obsLen = obstacleLine.CLine().Length();
    double shovedLen = shovedLine.CLine().Length();
    double extensionFactor = 0.0;

    if( obsLen != 0.0f )
        extensionFactor = shovedLen / obsLen - 1.0;

    if( extensionFactor > extensionWalkThreshold )
        return SH_TRY_WALK;

    assert( obstacleLine.LayersOverlap( &shovedLine ) );

    if( Dbg() )
    {
        Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d", m_iter ).ToStdString() );
        Dbg()->AddSegment( tmp.Seg(), 0, "obstacle-segment" );
        Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
        Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
        Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
        if( rv == SH_OK )
            Dbg()->Message("Shove success");
        else
            Dbg()->Message("Shove FAIL");
        Dbg()->EndGroup();
    }

    if( rv == SH_OK )
    {
        if( shovedLine.Marker() & MK_HEAD )
        {
            if( m_multiLineMode )
                return SH_INCOMPLETE;

            m_newHead = shovedLine;
        }

        int rank = aCurrent.Rank();
        shovedLine.SetRank( rank - 1 );

        sanityCheck( &obstacleLine, &shovedLine );
        replaceLine( obstacleLine, shovedLine );

        if( !pushLineStack( shovedLine ) )
            rv = SH_INCOMPLETE;
    }

    return rv;
}

References PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::AddSegment(), assembleLine(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), Format(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_iter, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::SEGMENT::Seg(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, and ShoveObstacleLine().

Referenced by shoveIteration().

onCollidingSolid()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSolid ( LINE &  aCurrent, ITEM *  aObstacle  )

private

Definition at line 626 of file pns_shove.cpp.

{
    WALKAROUND walkaround( m_currentNode, Router() );
    LINE walkaroundLine( aCurrent );

    if( aCurrent.EndsWithVia() )
    {
        VIA vh = aCurrent.Via();
        VIA* via = NULL;
        JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );

        if( !jtStart )
            return SH_INCOMPLETE;

        for( ITEM* item : jtStart->LinkList() )
        {
            if( item->OfKind( ITEM::VIA_T ) )
            {
                via = (VIA*) item;
                break;
            }
        }

        if( via && via->Collide( aObstacle, m_currentNode ) )
            return onCollidingVia( aObstacle, via );
    }

    TOPOLOGY topo( m_currentNode );

    std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );

    walkaround.SetSolidsOnly( false );
    walkaround.RestrictToSet( true, cluster );
    walkaround.SetIterationLimit( 16 ); // fixme: make configurable

    int currentRank = aCurrent.Rank();
    int nextRank;

    bool success = false;

    for( int attempt = 0; attempt < 2; attempt++ )
    {
        if( attempt == 1 || Settings().JumpOverObstacles() )
        {

            nextRank = currentRank - 1;
            walkaround.SetSingleDirection( true );
        }
        else
        {
            nextRank = currentRank + 10000;
            walkaround.SetSingleDirection( false );
        }


        WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );

        if( status != WALKAROUND::DONE )
            continue;

        walkaroundLine.ClearLinks();
        walkaroundLine.Unmark();
        walkaroundLine.Line().Simplify();

        if( walkaroundLine.HasLoops() )
            continue;

        if( aCurrent.Marker() & MK_HEAD )
        {
            walkaroundLine.Mark( MK_HEAD );

            if( m_multiLineMode )
                continue;

            m_newHead = walkaroundLine;
        }

        sanityCheck( &aCurrent, &walkaroundLine );

        if( !m_lineStack.empty() )
        {
            LINE lastLine = m_lineStack.front();

            if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
            {
                LINE dummy( lastLine );

                if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
                {
                    success = true;
                    break;
                }
            } else {
                success = true;
                break;
            }
        }
    }

    if(!success)
        return SH_INCOMPLETE;

    replaceLine( aCurrent, walkaroundLine );
    walkaroundLine.SetRank( nextRank );

    if( Dbg() )
    {
        Dbg()->BeginGroup( "on-colliding-solid" );
        Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
        Dbg()->AddLine( walkaroundLine.CLine(), 3, 10000, "walk-line" );
        Dbg()->EndGroup();
    }

    popLineStack();

    if( !pushLineStack( walkaroundLine ) )
        return SH_INCOMPLETE;

    return SH_OK;
}

References PNS::DEBUG_DECORATOR::AddLine(), PNS::TOPOLOGY::AssembleCluster(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, dummy(), PNS::DEBUG_DECORATOR::EndGroup(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), m_currentNode, m_lineStack, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, NULL, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), PNS::WALKAROUND::RestrictToSet(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), sanityCheck(), PNS::WALKAROUND::SetIterationLimit(), PNS::LINE::SetRank(), PNS::WALKAROUND::SetSingleDirection(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, ShoveObstacleLine(), SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), PNS::LINE::Via(), via, and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

onCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingVia ( ITEM *  aCurrent, VIA *  aObstacleVia  )

private

Definition at line 944 of file pns_shove.cpp.

{
    int clearance = getClearance( aCurrent, aObstacleVia );
    VECTOR2I mtv;
    int rank = -1;

    bool lineCollision = false;
    bool viaCollision = false;
    VECTOR2I mtvLine, mtvVia;


    if( aCurrent->OfKind( ITEM::LINE_T ) )
    {
        LINE* currentLine = (LINE*) aCurrent;

#if 0
        m_logger.NewGroup( "push-via-by-line", m_iter );
        m_logger.Log( currentLine, 4, "current" );
#endif

        lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(), clearance + currentLine->Width() / 2, &mtvLine );
 
        // Check the via if present. Via takes priority.
        if( currentLine->EndsWithVia() )
        {
            const VIA& currentVia = currentLine->Via();
            int        viaClearance = getClearance( &currentVia, aObstacleVia );

            viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance, &mtvVia );
        }
    }
    else if( aCurrent->OfKind( ITEM::SOLID_T ) )
    {
       // TODO: is this possible at all? We don't shove solids.
       return SH_INCOMPLETE;
    }

    // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
    if( viaCollision )
        mtv = mtvVia;
    else if ( lineCollision )
        mtv = -mtvLine;
    else
        mtv = VECTOR2I(0, 0);

    return pushOrShoveVia( aObstacleVia, -mtv, rank );
}

References SHAPE::Collide(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::OfKind(), pushOrShoveVia(), SH_INCOMPLETE, PNS::VIA::Shape(), PNS::LINE::Shape(), PNS::ITEM::SOLID_T, PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by onCollidingSolid(), and shoveIteration().

onReverseCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onReverseCollidingVia ( LINE &  aCurrent, VIA *  aObstacleVia  )

private

Definition at line 996 of file pns_shove.cpp.

{
    int n = 0;
    LINE cur( aCurrent );
    cur.ClearLinks();

    JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
    LINE shoved( aCurrent );
    shoved.ClearLinks();

    cur.RemoveVia();
    unwindLineStack( &aCurrent );

    for( ITEM* item : jt->LinkList() )
    {
        if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
        {
            LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
            LINE head = assembleLine( li );

            head.AppendVia( *aObstacleVia );

            SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );

            if( st != SH_OK )
            {
#if 0
                m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
                m_logger.Log( aObstacleVia, 0, "the-via" );
                m_logger.Log( &aCurrent, 1, "current-line" );
                m_logger.Log( &shoved, 3, "shoved-line" );
#endif

                return st;
            }

            cur.SetShape( shoved.CLine() );
            n++;
        }
    }

    if( !n )
    {
#if 0
        m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
        m_logger.Log( aObstacleVia, 0, "the-via" );
        m_logger.Log( &aCurrent, 1, "current-line" );
#endif

        LINE head( aCurrent );
        head.Line().Clear();
        head.AppendVia( *aObstacleVia );
        head.ClearLinks();

        SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );

        if( st != SH_OK )
            return st;

        cur.SetShape( shoved.CLine() );
    }

    if( aCurrent.EndsWithVia() )
        shoved.AppendVia( aCurrent.Via() );

#if 0
    m_logger.NewGroup( "on-reverse-via", m_iter );
    m_logger.Log( aObstacleVia, 0, "the-via" );
    m_logger.Log( &aCurrent, 1, "current-line" );
    m_logger.Log( &shoved, 3, "shoved-line" );
#endif
    int currentRank = aCurrent.Rank();
    replaceLine( aCurrent, shoved );

    if( !pushLineStack( shoved ) )
        return SH_INCOMPLETE;

    shoved.SetRank( currentRank );

    return SH_OK;
}

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_logger, PNS::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, ShoveObstacleLine(), unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

popLineStack()

void PNS::SHOVE::popLineStack ( )

private

Definition at line 1132 of file pns_shove.cpp.

{
    LINE& l = m_lineStack.back();

    for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
    {
        bool found = false;

        for( LINKED_ITEM* s : l.Links() )
        {
            if( i->ContainsLink( s ) )
            {
                i = m_optimizerQueue.erase( i );
                found = true;
                break;
            }
        }

        if( !found )
            i++;
    }

    m_lineStack.pop_back();
}

References PNS::LINK_HOLDER::Links(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

pushLineStack()

bool PNS::SHOVE::pushLineStack ( const LINE &  aL, bool  aKeepCurrentOnTop = false  )

private

Definition at line 1113 of file pns_shove.cpp.

{
    if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
        return false;

    if( aKeepCurrentOnTop && m_lineStack.size() > 0)
    {
        m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
    }
    else
    {
        m_lineStack.push_back( aL );
    }

    m_optimizerQueue.push_back( aL );

    return true;
}

References PNS::LINE::IsLinkedChecked(), m_lineStack, m_optimizerQueue, and PNS::LINE::SegmentCount().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), ShoveLines(), shoveMainLoop(), and ShoveMultiLines().

pushOrShoveVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::pushOrShoveVia ( VIA *  aVia, const VECTOR2I &  aForce, int  aCurrentRank  )

private

Definition at line 817 of file pns_shove.cpp.

{
    LINE_PAIR_VEC draggedLines;
    VECTOR2I p0( aVia->Pos() );
    JOINT* jt = m_currentNode->FindJoint( p0, aVia );
    VECTOR2I p0_pushed( p0 + aForce );

    // nothing to do...
    if ( aForce.x == 0 && aForce.y == 0 )
        return SH_OK;

    if( !jt )
    {
        wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
        return SH_INCOMPLETE;
    }

    if( aVia->IsLocked() )
        return SH_TRY_WALK;

    if( jt->IsLocked() )
        return SH_INCOMPLETE;

    // make sure pushed via does not overlap with any existing joint
    while( true )
    {
        JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );

        if( !jt_next )
            break;

        p0_pushed += aForce.Resize( 2 );
    }

    std::unique_ptr<VIA> pushedVia = Clone( *aVia );
    pushedVia->SetPos( p0_pushed );
    pushedVia->Mark( aVia->Marker() );

    for( ITEM* item : jt->LinkList() )
    {
        if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
        {
            LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
            LINE_PAIR lp;
            int segIndex;

            lp.first = assembleLine( li, &segIndex );

            if( lp.first.HasLockedSegments() )
                return SH_TRY_WALK;

            assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );

            if( segIndex == 0 )
                lp.first.Reverse();

            lp.second = lp.first;
            lp.second.ClearLinks();
            lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
            lp.second.AppendVia( *pushedVia );
            draggedLines.push_back( lp );
        }
    }

#if 0
    m_logger.Log( aVia, 0, "obstacle-via" );
#endif

    pushedVia->SetRank( aCurrentRank - 1 );

#if 0
    m_logger.Log( pushedVia.get(), 1, "pushed-via" );
#endif

    if( aVia->Marker() & MK_HEAD )      // push
    {
        m_draggedVia = pushedVia.get();
    }
    else
    {                                   // shove
        if( jt->IsStitchingVia() )
            pushLineStack( LINE( *pushedVia ) );
    }

    replaceItems( aVia, std::move( pushedVia ) );

    for( LINE_PAIR lp : draggedLines )
    {
        if( lp.first.Marker() & MK_HEAD )
        {
            lp.second.Mark( MK_HEAD );

            if( m_multiLineMode )
                return SH_INCOMPLETE;

            m_newHead = lp.second;
        }

        unwindLineStack( &lp.first );

        if( lp.second.SegmentCount() )
        {
            replaceLine( lp.first, lp.second );
            lp.second.SetRank( aCurrentRank - 1 );

            if( !pushLineStack( lp.second, true ) )
                return SH_INCOMPLETE;
        }
        else
        {
            m_currentNode->Remove( lp.first );
        }

#if 0
        m_logger.Log( &lp.first, 2, "fan-pre" );
        m_logger.Log( &lp.second, 3, "fan-post" );
#endif
    }

    return SH_OK;
}

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::NODE::FindJoint(), PNS::ITEM::IsLocked(), PNS::LOGGER::Log(), m_currentNode, m_draggedVia, m_logger, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS::VIA::Pos(), pushLineStack(), PNS::NODE::Remove(), replaceItems(), replaceLine(), VECTOR2< T >::Resize(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_OK, SH_TRY_WALK, unwindLineStack(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by onCollidingVia(), and ShoveDraggingVia().

pushSpringback()

bool PNS::SHOVE::pushSpringback ( NODE *  aNode, const OPT_BOX2I &  aAffectedArea, VIA *  aDraggedVia  )

private

Definition at line 780 of file pns_shove.cpp.

{
    SPRINGBACK_TAG st;
    OPT_BOX2I prev_area;

    if( !m_nodeStack.empty() )
        prev_area = m_nodeStack.back().m_affectedArea;

    if( aDraggedVia )
    {
        st.m_draggedVia = aDraggedVia->MakeHandle();
    }

    st.m_node = aNode;

    if( aAffectedArea )
    {
        if( prev_area )
            st.m_affectedArea = prev_area->Merge( *aAffectedArea );
        else
            st.m_affectedArea = aAffectedArea;
    } else
        st.m_affectedArea = prev_area;

    st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
    st.m_locked = false;

    m_nodeStack.push_back( st );

    return true;
}

References PNS::SHOVE::SPRINGBACK_TAG::m_affectedArea, PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, PNS::SHOVE::SPRINGBACK_TAG::m_seq, and PNS::VIA::MakeHandle().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

reduceSpringback()

NODE * PNS::SHOVE::reduceSpringback ( const ITEM_SET &  aHeadSet, VIA_HANDLE &  aDraggedVia  )

private

Definition at line 752 of file pns_shove.cpp.

{
    while( !m_nodeStack.empty() )
    {
        SPRINGBACK_TAG& spTag = m_nodeStack.back();

        OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );

        if( !obs && !spTag.m_locked )
        {
            aDraggedVia = spTag.m_draggedVia;
            aDraggedVia.valid = true;

            delete spTag.m_node;
            m_nodeStack.pop_back();
        }
        else
           break;
    }

    return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
}

References PNS::NODE::CheckColliding(), PNS::SHOVE::SPRINGBACK_TAG::m_draggedVia, PNS::SHOVE::SPRINGBACK_TAG::m_locked, PNS::SHOVE::SPRINGBACK_TAG::m_node, m_nodeStack, m_root, and PNS::VIA_HANDLE::valid.

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

replaceItems()

void PNS::SHOVE::replaceItems ( ITEM *  aOld, std::unique_ptr< ITEM >  aNew  )

private

Definition at line 49 of file pns_shove.cpp.

{
    OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );

    if( changed_area )
        m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;

    m_currentNode->Replace( aOld, std::move( aNew ) );
}

References PNS::ChangedArea(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

Referenced by pushOrShoveVia().

replaceLine()

void PNS::SHOVE::replaceLine ( LINE &  aOld, LINE &  aNew, bool  aIncludeInChangedArea = true, NODE *  aNode = nullptr  )

private

Definition at line 59 of file pns_shove.cpp.

{
    if( aIncludeInChangedArea )
    {
        OPT_BOX2I changed_area = ChangedArea( aOld, aNew );

        if( changed_area )
        {
            if( Dbg() )
            {
                Dbg()->AddBox( *changed_area, 3, "shove-changed-area" );
            }

        m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
        }
    }

    bool  foundPredecessor = false;
    LINE* rootLine = nullptr;

    // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
    // of the affected tracks in a map. The optimizer can then query the pre-shove shape
    // for each shoved line and perform additional constraint checks (i.e. prevent overzealous optimizations)

    // Check if the shoved line already has an ancestor (e.g. line from a previous shove iteration/cursor movement)
    for( auto link : aOld.Links() )
    {
        auto oldLineIter = m_rootLineHistory.find( link );
        if( oldLineIter != m_rootLineHistory.end() )
        {
            rootLine = oldLineIter->second;
            foundPredecessor = true;
            break;
        }
    }

    // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
    if( !foundPredecessor )
    {
        for( auto link : aOld.Links() )
        {
            if( ! rootLine )
            {
                rootLine = aOld.Clone();
            }
            m_rootLineHistory[link] = rootLine;
        }
    }

    // Now update the NODE (calling Replace invalidates the Links() in a LINE)
    if( aNode )
    {
        aNode->Replace( aOld, aNew );
    }
    else
    {
        m_currentNode->Replace( aOld, aNew );
    }

    // point the Links() of the new line to its oldest ancestor
    for( auto link : aNew.Links() )
    {
        m_rootLineHistory[ link ] = rootLine;
    }
}

References PNS::DEBUG_DECORATOR::AddBox(), PNS::ChangedArea(), PNS::LINE::Clone(), PNS::ALGO_BASE::Dbg(), PNS::LINK_HOLDER::Links(), m_affectedArea, m_currentNode, m_rootLineHistory, and PNS::NODE::Replace().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), and runOptimizer().

RewindSpringbackTo()

bool PNS::SHOVE::RewindSpringbackTo

(

NODE *

aNode

)

Definition at line 1772 of file pns_shove.cpp.

{
    bool found = false;

    auto iter = m_nodeStack.begin();

    while( iter != m_nodeStack.end() )
    {
        if ( iter->m_node == aNode )
        {
            found = true;
            break;
        }
        iter++;
    }

    if( !found )
        return false;

    auto start = iter;

    aNode->KillChildren();
    m_nodeStack.erase( start, m_nodeStack.end() );

    return true;
}

References PNS::NODE::KillChildren(), and m_nodeStack.

Router()

ROUTER* PNS::ALGO_BASE::Router ( ) const

inlineinherited

Return current router settings.

Definition at line 54 of file pns_algo_base.h.

References PNS::ALGO_BASE::m_router.

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), PNS::MEANDER_PLACER::CommitPlacement(), PNS::DP_MEANDER_PLACER::CommitPlacement(), PNS::DIFF_PAIR_PLACER::CommitPlacement(), PNS::LINE_PLACER::CommitPlacement(), PNS::COMPONENT_DRAGGER::FixRoute(), PNS::DRAGGER::FixRoute(), PNS::DIFF_PAIR_PLACER::initPlacement(), PNS::LINE_PLACER::initPlacement(), onCollidingSolid(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::MEANDER_SKEW_PLACER::Start(), PNS::MEANDER_PLACER::Start(), PNS::DP_MEANDER_PLACER::Start(), PNS::DRAGGER::Start(), PNS::DIFF_PAIR_PLACER::Start(), and PNS::DRAGGER::tryWalkaround().

runOptimizer()

void PNS::SHOVE::runOptimizer ( NODE *  aNode )

private

Definition at line 1656 of file pns_shove.cpp.

{
    OPTIMIZER optimizer( aNode );
    int optFlags = 0;
    int n_passes = 0;

    PNS_OPTIMIZATION_EFFORT effort = Settings().OptimizerEffort();

    OPT_BOX2I area = totalAffectedArea();

    int maxWidth = 0;

    for( LINE& line : m_optimizerQueue )
        maxWidth = std::max( line.Width(), maxWidth );

    if( area )
    {
        area->Inflate( maxWidth );
        area = area->Intersect( VisibleViewArea() );
    }

    switch( effort )
    {
    case OE_LOW:
        optFlags |= OPTIMIZER::MERGE_OBTUSE;
        n_passes = 1;
        break;

    case OE_MEDIUM:
        optFlags |= OPTIMIZER::MERGE_SEGMENTS;

        n_passes = 2;
        break;

    case OE_FULL:
        optFlags = OPTIMIZER::MERGE_SEGMENTS;
        n_passes = 2;
        break;

    default:
        break;
    }

    optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;

    if( area )
    {
        if( Dbg() )
        {
            Dbg()->AddBox( *area, 1, "opt-area" );
        }

        optFlags |= OPTIMIZER::RESTRICT_AREA;
        optimizer.SetRestrictArea( *area, false );
    }

    if( Settings().SmartPads() )
        optFlags |= OPTIMIZER::SMART_PADS;

    optimizer.SetEffortLevel( optFlags );
    optimizer.SetCollisionMask( ITEM::ANY_T );

    for( int pass = 0; pass < n_passes; pass++ )
    {
        std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );

        for( LINE& line : m_optimizerQueue)
        {
            if( !( line.Marker() & MK_HEAD ) )
            {
                LINE optimized;
                LINE* root = findRootLine( &line );

                if( optimizer.Optimize( &line, &optimized, root ) )
                {
                    replaceLine( line, optimized, false, aNode );
                    line = optimized; // keep links in the lines in the queue up to date
                }
            }
        }
    }
}

References PNS::DEBUG_DECORATOR::AddBox(), PNS::ITEM::ANY_T, PNS::ALGO_BASE::Dbg(), findRootLine(), PNS::OPTIMIZER::LIMIT_CORNER_COUNT, m_optimizerQueue, PNS::OPTIMIZER::MERGE_OBTUSE, PNS::OPTIMIZER::MERGE_SEGMENTS, PNS::MK_HEAD, PNS::OE_FULL, PNS::OE_LOW, PNS::OE_MEDIUM, PNS::OPTIMIZER::Optimize(), PNS::ROUTING_SETTINGS::OptimizerEffort(), replaceLine(), PNS::OPTIMIZER::RESTRICT_AREA, PNS::OPTIMIZER::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, totalAffectedArea(), and PNS::ALGO_BASE::VisibleViewArea().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

sanityCheck()

void PNS::SHOVE::sanityCheck ( LINE *  aOld, LINE *  aNew  )

private

Definition at line 142 of file pns_shove.cpp.

{
    assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
    assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
}

References PNS::LINE::CPoint().

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), and onCollidingSolid().

SetDebugDecorator()

void PNS::ALGO_BASE::SetDebugDecorator ( DEBUG_DECORATOR *  aDecorator )

inlineinherited

Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.

Definition at line 73 of file pns_algo_base.h.

    {
        m_debugDecorator = aDecorator;
    }

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), SHOVE(), and PNS::DRAGGER::tryWalkaround().

SetInitialLine()

void PNS::SHOVE::SetInitialLine

(

LINE &

aInitial

)

Definition at line 1754 of file pns_shove.cpp.

{
    m_root = m_root->Branch();
    m_root->Remove( aInitial );
}

References PNS::NODE::Branch(), m_root, and PNS::NODE::Remove().

SetLogger()

void PNS::ALGO_BASE::SetLogger ( LOGGER *  aLogger )

inlineinherited

Definition at line 65 of file pns_algo_base.h.

    {
        m_logger = aLogger;
    }

References PNS::ALGO_BASE::m_logger.

Referenced by PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), and PNS::DRAGGER::tryWalkaround().

Settings()

ROUTING_SETTINGS & PNS::ALGO_BASE::Settings ( ) const

inherited

Return the logger object, allowing to dump geometry to a file.

Definition at line 28 of file pns_algo_base.cpp.

{
    return m_router->Settings();
}

References PNS::ALGO_BASE::m_router, and PNS::ROUTER::Settings().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), PNS::LINE_PLACER::buildInitialLine(), PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragShove(), PNS::DRAGGER::dragWalkaround(), PNS::COMPONENT_DRAGGER::FixRoute(), PNS::DRAGGER::FixRoute(), PNS::DIFF_PAIR_PLACER::FixRoute(), PNS::LINE_PLACER::FixRoute(), PNS::DIFF_PAIR_PLACER::initPlacement(), PNS::LINE_PLACER::initPlacement(), PNS::LINE_PLACER::Move(), onCollidingSolid(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::rhMarkObstacles(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::LINE_PLACER::routeStep(), runOptimizer(), shoveMainLoop(), PNS::DRAGGER::Start(), PNS::LINE_PLACER::Start(), and PNS::DRAGGER::tryWalkaround().

ShoveDraggingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveDraggingVia	(	const VIA_HANDLE	aOldVia,
		const VECTOR2I &	aWhere,
		VIA_HANDLE &	aNewVia
	)

Definition at line 1569 of file pns_shove.cpp.

{
     SHOVE_STATUS st = SH_OK;

    m_lineStack.clear();
    m_optimizerQueue.clear();
    m_newHead = OPT_LINE();
    m_draggedVia = NULL;

    VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );

    if( !viaToDrag )
        return SH_INCOMPLETE;

    // Pop NODEs containing previous shoves which are no longer necessary
    ITEM_SET headSet;

    VIA headVia ( *viaToDrag );
    headVia.SetPos( aWhere );
    headSet.Add( headVia );
    VIA_HANDLE prevViaHandle;
    NODE* parent = reduceSpringback( headSet, prevViaHandle );

    if( prevViaHandle.valid )
    {
        aNewVia = prevViaHandle;
        viaToDrag = findViaByHandle( parent, prevViaHandle );
    }

    // Create a new NODE to store this version of the world
    //
    m_currentNode = parent->Branch();
    m_currentNode->ClearRanks();

    viaToDrag->Mark( MK_HEAD );
    viaToDrag->SetRank( 100000 );

    // Push the via to its new location
    //
    st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );

    // Shove any colliding objects out of the way
    //
    if( st == SH_OK )
        st = shoveMainLoop();

    if( st == SH_OK )
        runOptimizer( m_currentNode );

    if( st == SH_OK || st == SH_HEAD_MODIFIED )
    {
        wxLogTrace( "PNS","setNewV %p", m_draggedVia );

        if (!m_draggedVia)
            m_draggedVia = viaToDrag;

        aNewVia = m_draggedVia->MakeHandle();

        pushSpringback( m_currentNode, m_affectedArea, viaToDrag );
    }
    else
    {
        delete m_currentNode;
        m_currentNode = parent;
    }

    return st;
}

References PNS::ITEM_SET::Add(), PNS::NODE::Branch(), PNS::NODE::ClearRanks(), PNS::findViaByHandle(), m_affectedArea, m_currentNode, m_draggedVia, m_lineStack, m_newHead, m_optimizerQueue, PNS::VIA::MakeHandle(), PNS::ITEM::Mark(), PNS::MK_HEAD, NULL, PNS::VIA::Pos(), pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), PNS::ITEM::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::VIA_HANDLE::valid.

shoveIteration()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveIteration ( int  aIter )

private

Definition at line 1161 of file pns_shove.cpp.

{
    LINE currentLine = m_lineStack.back();
    NODE::OPT_OBSTACLE nearest;
    SHOVE_STATUS st = SH_NULL;

#ifdef DEBUG
    Dbg()->SetIteration( aIter );
#endif

    for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
    {
         nearest = m_currentNode->NearestObstacle( &currentLine, search_order );

         if( nearest )
            break;
    }

    if( !nearest )
    {
        m_lineStack.pop_back();
        return SH_OK;
    }

    ITEM* ni = nearest->m_item;

    unwindLineStack( ni );

    if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
    {
        // Collision with a higher-ranking object (ie: one that we've already shoved)
        //
        switch( ni->Kind() )
        {
        case ITEM::VIA_T:
        {
            wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );

            if( currentLine.EndsWithVia() )
            {
                st = SH_INCOMPLETE;
            }
            else
            {
                st = onReverseCollidingVia( currentLine, (VIA*) ni );
            }

            break;
        }

        case ITEM::SEGMENT_T:
        {
            wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
            LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );

            popLineStack();
            st = onCollidingLine( revLine, currentLine );
            if( !pushLineStack( revLine ) )
                return SH_INCOMPLETE;

            break;
        }

        case ITEM::ARC_T:
        {
            //TODO(snh): Handle Arc shove separate from track
            wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
            LINE revLine = assembleLine( static_cast<ARC*>( ni ) );

            popLineStack();
            st = onCollidingLine( revLine, currentLine );
            if( !pushLineStack( revLine ) )
                return SH_INCOMPLETE;

            break;
        }

        default:
            assert( false );
        }
    }
    else
    {
        // Collision with a lower-ranking object or a solid
        //
        switch( ni->Kind() )
        {
        case ITEM::SEGMENT_T:
            wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );

            st = onCollidingSegment( currentLine, (SEGMENT*) ni );

            if( st == SH_TRY_WALK )
                st = onCollidingSolid( currentLine, ni );

            break;

            //TODO(snh): Customize Arc collide
        case ITEM::ARC_T:
            wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );

            st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );

            if( st == SH_TRY_WALK )
                st = onCollidingSolid( currentLine, ni );

            break;

        case ITEM::VIA_T:
            wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
            st = onCollidingVia( &currentLine, (VIA*) ni );

            if( st == SH_TRY_WALK )
                st = onCollidingSolid( currentLine, ni );

            break;

        case ITEM::SOLID_T:
            wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
            st = onCollidingSolid( currentLine, (SOLID*) ni );
            break;

        default:
            break;
        }
    }

    return st;
}

References PNS::ITEM::ARC_T, assembleLine(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), PNS::ITEM::Kind(), m_currentNode, m_lineStack, PNS::NODE::NearestObstacle(), PNS::ITEM::OfKind(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onCollidingVia(), onReverseCollidingVia(), popLineStack(), pushLineStack(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::ITEM::SEGMENT_T, PNS::DEBUG_DECORATOR::SetIteration(), SH_INCOMPLETE, SH_NULL, SH_OK, SH_TRY_WALK, PNS::ITEM::SOLID_T, unwindLineStack(), and PNS::ITEM::VIA_T.

Referenced by shoveMainLoop().

shoveLineFromLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineFromLoneVia ( const LINE &  aCurLine, const LINE &  aObstacleLine, LINE &  aResultLine  )

private

Definition at line 213 of file pns_shove.cpp.

{
    // Build a hull for aCurLine's via and re-walk aObstacleLine around it.

    int obstacleLineWidth = aObstacleLine.Width();
    int clearance = getClearance( &aCurLine, &aObstacleLine );
    int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );

    if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
        clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;

    SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
    SHAPE_LINE_CHAIN path_cw;
    SHAPE_LINE_CHAIN path_ccw;

    if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
        return SH_INCOMPLETE;

    if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
        return SH_INCOMPLETE;

    const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;

    if( shortest.PointCount() < 2 )
        return SH_INCOMPLETE;

    if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
        return SH_INCOMPLETE;

    if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
        return SH_INCOMPLETE;

    aResultLine.SetShape( shortest );

    if( aResultLine.Collide( &aCurLine, m_currentNode ) )
        return SH_INCOMPLETE;

    return SH_OK;
}

References PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::VIA::Diameter(), PNS::VIA::Drill(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), SHAPE_LINE_CHAIN::Length(), m_currentNode, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Via(), PNS::LINE::Walkaround(), and PNS::LINE::Width().

Referenced by ShoveObstacleLine().

ShoveLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveLines

(

const LINE &

aCurrentHead

)

Definition at line 1354 of file pns_shove.cpp.

{
    SHOVE_STATUS st = SH_OK;

    m_multiLineMode = false;

    if( Dbg() )
    {
        Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
    }

    // empty head? nothing to shove...

    if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
        return SH_INCOMPLETE;

    LINE head( aCurrentHead );
    head.ClearLinks();

    m_lineStack.clear();
    m_optimizerQueue.clear();
    m_newHead = OPT_LINE();
#if 0
    m_logger.Clear();
#endif

    // Pop NODEs containing previous shoves which are no longer necessary
    //
    ITEM_SET headSet;
    headSet.Add( aCurrentHead );

    VIA_HANDLE dummyVia;

    NODE* parent = reduceSpringback( headSet, dummyVia );

    // Create a new NODE to store this version of the world
    //
    m_currentNode = parent->Branch();
    m_currentNode->ClearRanks();
    m_currentNode->Add( head );

    m_currentNode->LockJoint( head.CPoint(0), &head, true );

    if( !head.EndsWithVia() )
        m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );

    head.Mark( MK_HEAD );
    head.SetRank( 100000 );

    if ( Dbg() )
    {

        Dbg()->BeginGroup( "initial" );
        Dbg()->AddLine(head.CLine(), 5, head.Width(), "head" );
        Dbg()->EndGroup();
    }

    if( head.EndsWithVia() )
    {
        std::unique_ptr< VIA >headVia = Clone( head.Via() );
        headVia->Mark( MK_HEAD );
        headVia->SetRank( 100000 );
        m_currentNode->Add( std::move( headVia ) );
    }

    if( !pushLineStack( head ) )
    {
        delete m_currentNode;
        m_currentNode = parent;

        return SH_INCOMPLETE;
    }

    st = shoveMainLoop();

    if( st == SH_OK )
    {
        runOptimizer( m_currentNode );

        if( m_newHead )
            st = m_currentNode->CheckColliding( &( *m_newHead ) ) ? SH_INCOMPLETE : SH_HEAD_MODIFIED;
        else
            st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
    }

    m_currentNode->RemoveByMarker( MK_HEAD );

    wxLogTrace( "PNS", "Shove status : %s after %d iterations",
           ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );

    if( st == SH_OK || st == SH_HEAD_MODIFIED )
    {
        pushSpringback( m_currentNode, m_affectedArea, nullptr );
    }
    else
    {
        delete m_currentNode;

        m_currentNode = parent;
        m_newHead = OPT_LINE();
    }

    if(m_newHead)
        m_newHead->Unmark();

    if( m_newHead && head.EndsWithVia() )
    {
        VIA v = head.Via();
        v.SetPos( m_newHead->CPoint( -1 ) );
        m_newHead->AppendVia(v);
    }

    return st;
}

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::DEBUG_DECORATOR::AddLine(), PNS::DEBUG_DECORATOR::BeginGroup(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::LINE::CLine(), PNS::Clone(), PNS::LINE::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::DEBUG_DECORATOR::EndGroup(), PNS::LINE::EndsWithVia(), Format(), PNS::NODE::LockJoint(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), PNS::LINE::Via(), and PNS::LINE::Width().

shoveLineToHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveLineToHullSet ( const LINE &  aCurLine, const LINE &  aObstacleLine, LINE &  aResultLine, const HULL_SET &  aHulls  )

private

Definition at line 258 of file pns_shove.cpp.

{
    const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();

    int attempt;

    for( attempt = 0; attempt < 4; attempt++ )
    {
        bool invertTraversal = ( attempt >= 2 );
        bool clockwise = attempt % 2;
        int vFirst = -1, vLast = -1;

        SHAPE_LINE_CHAIN path;
        LINE l( aObstacleLine );

        for( int i = 0; i < (int) aHulls.size(); i++ )
        {
            const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];

            if( ! l.Walkaround( hull, path, clockwise ) )
            {
                wxLogTrace("PNS", "Fail-Walk %s %s %d\n", hull.Format().c_str(), l.CLine().Format().c_str(), clockwise? 1:0);
                return SH_INCOMPLETE;
            }

            path.Simplify();
            l.SetShape( path );
        }

        for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
        {
            if( path.CPoint( i ) != obs.CPoint( i ) )
            {
                vFirst = i;
                break;
            }
        }

        int k = obs.PointCount() - 1;
        for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
        {
            if( path.CPoint( i ) != obs.CPoint( k ) )
            {
                vLast = i;
                break;
            }
        }

        if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
        {
            wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
            continue;
        }

        if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
        {
            wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
            continue;
        }

        if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
        {
            wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
            aResultLine.SetShape( l.CLine() );

            continue;
        }

        if( path.SelfIntersecting() )
        {
            wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
            continue;
        }

        bool colliding = l.Collide( &aCurLine, m_currentNode );

#ifdef DEBUG
        char str[128];
        sprintf( str, "att-%d-shoved", attempt );
        Dbg()->AddLine( l.CLine(), 3, 20000, str );
#endif

        if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
        {
            JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );

            for( ITEM* item : jtStart->LinkList() )
            {
                if( item->Collide( &l, m_currentNode ) )
                    colliding = true;
            }
        }

        if( colliding )
        {
            wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
            continue;
        }

        aResultLine.SetShape( l.CLine() );

        return SH_OK;
    }

    return SH_INCOMPLETE;
}

References PNS::DEBUG_DECORATOR::AddLine(), checkShoveDirection(), PNS::LINE::CLine(), PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), SHAPE_LINE_CHAIN::Format(), PNS::JOINT::LinkList(), m_currentNode, PNS::LINE::Marker(), PNS::MK_HEAD, path, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, and PNS::LINE::Walkaround().

Referenced by ShoveObstacleLine().

shoveMainLoop()

SHOVE::SHOVE_STATUS PNS::SHOVE::shoveMainLoop ( )

private

Definition at line 1298 of file pns_shove.cpp.

{
    SHOVE_STATUS st = SH_OK;

    m_affectedArea = OPT_BOX2I();

    wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
           m_currentNode->JointCount() );

    int iterLimit = Settings().ShoveIterationLimit();
    TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();

    m_iter = 0;

    timeLimit.Restart();

    if( m_lineStack.empty() && m_draggedVia )
    {
        // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
        // the stack.
        pushLineStack( LINE( *m_draggedVia ) );
    }

    while( !m_lineStack.empty() )
    {
        st = shoveIteration( m_iter );

        m_iter++;

        if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
        {
            st = SH_INCOMPLETE;
            break;
        }
    }

    return st;
}

References PNS::TIME_LIMIT::Expired(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, pushLineStack(), PNS::TIME_LIMIT::Restart(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, shoveIteration(), PNS::ROUTING_SETTINGS::ShoveIterationLimit(), and PNS::ROUTING_SETTINGS::ShoveTimeLimit().

Referenced by ShoveDraggingVia(), ShoveLines(), and ShoveMultiLines().

ShoveMultiLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveMultiLines

(

const ITEM_SET &

aHeadSet

)

Definition at line 1470 of file pns_shove.cpp.

{
    SHOVE_STATUS st = SH_OK;

    m_multiLineMode = true;

    ITEM_SET headSet;

    for( const ITEM* item : aHeadSet.CItems() )
    {
        const LINE* headOrig = static_cast<const LINE*>( item );

        // empty head? nothing to shove...
        if( !headOrig->SegmentCount() )
            return SH_INCOMPLETE;

        headSet.Add( *headOrig );
    }

    m_lineStack.clear();
    m_optimizerQueue.clear();
#if 0
    m_logger.Clear();
#endif

    VIA_HANDLE dummyVia;

    NODE* parent = reduceSpringback( headSet, dummyVia );

    m_currentNode = parent->Branch();
    m_currentNode->ClearRanks();
    int n = 0;

    for( const ITEM* item : aHeadSet.CItems() )
    {
        const LINE* headOrig = static_cast<const LINE*>( item );
        LINE head( *headOrig );
        head.ClearLinks();

        m_currentNode->Add( head );

        head.Mark( MK_HEAD );
        head.SetRank( 100000 );
        n++;

        if( !pushLineStack( head ) )
            return SH_INCOMPLETE;

        if( head.EndsWithVia() )
        {
            std::unique_ptr< VIA > headVia = Clone( head.Via() );
            headVia->Mark( MK_HEAD );
            headVia->SetRank( 100000 );
            m_currentNode->Add( std::move( headVia ) );
        }
    }

    st = shoveMainLoop();

    if( st == SH_OK )
        runOptimizer( m_currentNode );

    m_currentNode->RemoveByMarker( MK_HEAD );

    wxLogTrace( "PNS", "Shove status : %s after %d iterations",
           ( st == SH_OK ? "OK" : "FAILURE"), m_iter );

    if( st == SH_OK )
    {
        pushSpringback( m_currentNode, m_affectedArea, nullptr );
    }
    else
    {
        delete m_currentNode;
        m_currentNode = parent;
    }

    return st;
}

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::ITEM_SET::CItems(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::Clone(), PNS::LINE::EndsWithVia(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

Referenced by PNS::DIFF_PAIR_PLACER::rhShoveOnly().

ShoveObstacleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveObstacleLine	(	const LINE &	aCurLine,
		const LINE &	aObstacleLine,
		LINE &	aResultLine
	)

Definition at line 371 of file pns_shove.cpp.

{
    aResultLine.ClearLinks();

    bool obstacleIsHead = false;

    for( LINKED_ITEM* s : aObstacleLine.Links() )
    {
        if( s->Marker() & MK_HEAD )
        {
            obstacleIsHead = true;
            break;
        }
    }

    SHOVE_STATUS rv;
    bool viaOnEnd = aCurLine.EndsWithVia();

    if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
    {
        // Shove aObstacleLine to the hull of aCurLine's via.

        rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
    }
    else
    {
        // Build a set of hulls around the segments of aCurLine.  Hulls are at the clearance
        // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
        // hull it will be at the appropriate clearance.

        int      obstacleLineWidth = aObstacleLine.Width();
        int      clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
        int      currentLineSegmentCount = aCurLine.SegmentCount();
        HULL_SET hulls;

        hulls.reserve( currentLineSegmentCount + 1 );

#ifdef DEBUG
        Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
                                          aCurLine.Net(),
                                          aObstacleLine.Net(),
                                          clearance ) );
#endif

        for( int i = 0; i < currentLineSegmentCount; i++ )
        {
            SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
            SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );

            hulls.push_back( hull );
        }

        if( viaOnEnd )
        {
            const VIA& via = aCurLine.Via();
            int viaClearance = getClearance( &via, &aObstacleLine );
            int holeClearance = getHoleClearance( &via, &aObstacleLine );

            if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
                viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;

            hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
        }

#ifdef DEBUG
        char str[128];
        sprintf( str, "current-cl-%d", clearance );
        Dbg()->AddLine( aCurLine.CLine(), 5, 20000, str );
#endif

        rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
    }

    if( obstacleIsHead )
        aResultLine.Mark( aResultLine.Marker() | MK_HEAD );

    return rv;
}

References PNS::DEBUG_DECORATOR::AddLine(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), getClearance(), getHoleClearance(), PNS::VIA::Hull(), PNS::ITEM::Layer(), PNS::ITEM::LayersOverlap(), PNS::LINK_HOLDER::Links(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::DEBUG_DECORATOR::Message(), PNS::MK_HEAD, PNS::ITEM::Net(), PNS::LINE::SegmentCount(), shoveLineFromLoneVia(), shoveLineToHullSet(), PNS::LINE::Via(), via, and PNS::LINE::Width().

Referenced by PNS::DIFF_PAIR_PLACER::attemptWalk(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), and onReverseCollidingVia().

totalAffectedArea()

OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const

private

Definition at line 1338 of file pns_shove.cpp.

{
    OPT_BOX2I area;

    if( !m_nodeStack.empty() )
        area = m_nodeStack.back().m_affectedArea;

    if( area  && m_affectedArea)
        area->Merge( *m_affectedArea );
    else if( !area )
        area = m_affectedArea;

    return area;
}

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

UnlockSpringbackNode()

void PNS::SHOVE::UnlockSpringbackNode

(

NODE *

aNode

)

Definition at line 1800 of file pns_shove.cpp.

{
    auto iter = m_nodeStack.begin();

    while( iter != m_nodeStack.end() )
    {
        if ( iter->m_node == aNode )
        {
            iter->m_locked = false;
            break;
        }
        iter++;
    }
}

References m_nodeStack.

unwindLineStack() [1/2]

void PNS::SHOVE::unwindLineStack ( LINKED_ITEM *  aSeg )

private

Definition at line 1079 of file pns_shove.cpp.

{
    for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
    {
        if( i->ContainsLink( aSeg ) )
            i = m_lineStack.erase( i );
        else
            i++;
    }

    for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
    {
        if( i->ContainsLink( aSeg ) )
            i = m_optimizerQueue.erase( i );
        else
            i++;
    }
}

References m_lineStack, and m_optimizerQueue.

Referenced by onReverseCollidingVia(), pushOrShoveVia(), shoveIteration(), and unwindLineStack().

unwindLineStack() [2/2]

void PNS::SHOVE::unwindLineStack ( ITEM *  aItem )

private

Definition at line 1099 of file pns_shove.cpp.

{
    if( aItem->OfKind( ITEM::SEGMENT_T  | ITEM::ARC_T ) )
        unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
    else if( aItem->OfKind( ITEM::LINE_T ) )
    {
        LINE* l = static_cast<LINE*>( aItem );

        for( LINKED_ITEM* seg : l->Links() )
            unwindLineStack( seg );
    }
}

References PNS::ITEM::ARC_T, PNS::ITEM::LINE_T, PNS::LINK_HOLDER::Links(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindLineStack().

VisibleViewArea()

const BOX2I & PNS::ALGO_BASE::VisibleViewArea ( ) const

inherited

Definition at line 39 of file pns_algo_base.cpp.

{
    return m_router->VisibleViewArea();
}

References PNS::ALGO_BASE::m_router, and PNS::ROUTER::VisibleViewArea().

Referenced by PNS::DRAGGER::optimizeAndUpdateDraggedLine(), and runOptimizer().

Member Data Documentation

m_affectedArea

OPT_BOX2I PNS::SHOVE::m_affectedArea

private

Definition at line 154 of file pns_shove.h.

Referenced by replaceItems(), replaceLine(), ShoveDraggingVia(), ShoveLines(), shoveMainLoop(), ShoveMultiLines(), and totalAffectedArea().

m_currentNode

NODE* PNS::SHOVE::m_currentNode

private

Definition at line 168 of file pns_shove.h.

Referenced by assembleLine(), getClearance(), getHoleClearance(), onCollidingSolid(), onReverseCollidingVia(), pushOrShoveVia(), replaceItems(), replaceLine(), SHOVE(), ShoveDraggingVia(), shoveIteration(), shoveLineFromLoneVia(), ShoveLines(), shoveLineToHullSet(), shoveMainLoop(), and ShoveMultiLines().

m_debugDecorator

DEBUG_DECORATOR* PNS::ALGO_BASE::m_debugDecorator

protectedinherited

Definition at line 86 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Dbg(), and PNS::ALGO_BASE::SetDebugDecorator().

m_draggedVia

VIA* PNS::SHOVE::m_draggedVia

private

Definition at line 174 of file pns_shove.h.

Referenced by pushOrShoveVia(), SHOVE(), ShoveDraggingVia(), and shoveMainLoop().

m_forceClearance

int PNS::SHOVE::m_forceClearance

private

Definition at line 177 of file pns_shove.h.

Referenced by ForceClearance(), getClearance(), getHoleClearance(), and SHOVE().

m_iter

int PNS::SHOVE::m_iter

private

Definition at line 176 of file pns_shove.h.

Referenced by onCollidingArc(), onCollidingSegment(), onCollidingVia(), onReverseCollidingVia(), SHOVE(), ShoveLines(), shoveMainLoop(), and ShoveMultiLines().

m_lineStack

std::vector<LINE> PNS::SHOVE::m_lineStack

private

Definition at line 163 of file pns_shove.h.

Referenced by onCollidingSolid(), popLineStack(), pushLineStack(), ShoveDraggingVia(), shoveIteration(), ShoveLines(), shoveMainLoop(), ShoveMultiLines(), and unwindLineStack().

m_logger

LOGGER PNS::SHOVE::m_logger

private

Definition at line 173 of file pns_shove.h.

Referenced by Logger(), onCollidingVia(), onReverseCollidingVia(), pushOrShoveVia(), ShoveLines(), and ShoveMultiLines().

m_multiLineMode

bool PNS::SHOVE::m_multiLineMode

private

Definition at line 178 of file pns_shove.h.

Referenced by onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), pushOrShoveVia(), SHOVE(), ShoveLines(), and ShoveMultiLines().

m_newHead

OPT_LINE PNS::SHOVE::m_newHead

private

Definition at line 171 of file pns_shove.h.

Referenced by NewHead(), onCollidingArc(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), pushOrShoveVia(), ShoveDraggingVia(), and ShoveLines().

m_nodeStack

std::vector<SPRINGBACK_TAG> PNS::SHOVE::m_nodeStack

private

Definition at line 162 of file pns_shove.h.

Referenced by AddLockedSpringbackNode(), CurrentNode(), pushSpringback(), reduceSpringback(), RewindSpringbackTo(), totalAffectedArea(), and UnlockSpringbackNode().

m_optimizerQueue

std::vector<LINE> PNS::SHOVE::m_optimizerQueue

private

Definition at line 164 of file pns_shove.h.

Referenced by popLineStack(), pushLineStack(), runOptimizer(), ShoveDraggingVia(), ShoveLines(), ShoveMultiLines(), and unwindLineStack().

m_restrictSpringbackTagId

int PNS::SHOVE::m_restrictSpringbackTagId

private

Definition at line 169 of file pns_shove.h.

Referenced by SHOVE().

m_root

NODE* PNS::SHOVE::m_root

private

Definition at line 167 of file pns_shove.h.

Referenced by CurrentNode(), reduceSpringback(), SetInitialLine(), SHOVE(), and shoveMainLoop().

m_rootLineHistory

std::unordered_map<const LINKED_ITEM*, LINE*> PNS::SHOVE::m_rootLineHistory

private

Definition at line 165 of file pns_shove.h.

Referenced by findRootLine(), replaceLine(), and ~SHOVE().

m_router

ROUTER* PNS::ALGO_BASE::m_router

protectedinherited

Definition at line 87 of file pns_algo_base.h.

Referenced by PNS::MEANDER_PLACER_BASE::lineLength(), PNS::ALGO_BASE::Router(), PNS::ALGO_BASE::Settings(), PNS::DIFF_PAIR_PLACER::updateLeadingRatLine(), PNS::LINE_PLACER::updateLeadingRatLine(), and PNS::ALGO_BASE::VisibleViewArea().

---

The documentation for this class was generated from the following files:

• pns_shove.h
• pns_shove.cpp