KiCad PCB EDA Suite
PNS::SHOVE Class Reference

The actual Push and Shove algorithm. More...

#include <pns_shove.h>

Inheritance diagram for PNS::SHOVE:
PNS::ALGO_BASE

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 LOGGERLogger () 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)
 
NODECurrentNode ()
 
const LINE NewHead () const
 
void SetInitialLine (LINE &aInitial)
 
bool AddLockedSpringbackNode (NODE *aNode)
 
void UnlockSpringbackNode (NODE *aNode)
 
bool RewindSpringbackTo (NODE *aNode)
 
bool RewindToLastLockedNode ()
 
void DisablePostShoveOptimizations (int aMask)
 
void SetSpringbackDoNotTouchNode (NODE *aNode)
 
ROUTERRouter () const
 Return current router settings. More...
 
ROUTING_SETTINGSSettings () 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_DECORATORDbg () const
 
const BOX2IVisibleViewArea () const
 

Protected Attributes

DEBUG_DECORATORm_debugDecorator
 
ROUTERm_router
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINHULL_SET
 
typedef std::optional< LINEOPT_LINE
 
typedef std::pair< LINE, LINELINE_PAIR
 
typedef std::vector< LINE_PAIRLINE_PAIR_VEC
 

Private Member Functions

SHOVE_STATUS shoveLineToHullSet (const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
 
NODEreduceSpringback (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, OBSTACLE &aObstacleInfo)
 
SHOVE_STATUS onCollidingVia (ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
 
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=nullptr)
 
void replaceItems (ITEM *aOld, std::unique_ptr< ITEM > aNew)
 
void replaceLine (LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
 
LINEfindRootLine (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
 
bool fixupViaCollisions (const LINE *aCurrent, OBSTACLE &obs)
 
void sanityCheck (LINE *aOld, LINE *aNew)
 

Private Attributes

OPT_BOX2I m_affectedArea
 
std::vector< SPRINGBACK_TAGm_nodeStack
 
std::vector< LINEm_lineStack
 
std::vector< LINEm_optimizerQueue
 
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
 
NODEm_root
 
NODEm_currentNode
 
NODEm_springbackDoNotTouchNode
 
int m_restrictSpringbackTagId
 
OPT_LINE m_newHead
 
LOGGER m_logger
 
VIAm_draggedVia
 
int m_iter
 
int m_forceClearance
 
bool m_multiLineMode
 
int m_optFlagDisableMask
 

Detailed Description

The actual Push and Shove algorithm.

Definition at line 45 of file pns_shove.h.

Member Typedef Documentation

◆ HULL_SET

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

Definition at line 96 of file pns_shove.h.

◆ LINE_PAIR

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

Definition at line 98 of file pns_shove.h.

◆ LINE_PAIR_VEC

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

Definition at line 99 of file pns_shove.h.

◆ OPT_LINE

typedef std::optional<LINE> PNS::SHOVE::OPT_LINE
private

Definition at line 97 of file pns_shove.h.

Member Enumeration Documentation

◆ SHOVE_STATUS

Enumerator
SH_OK 
SH_NULL 
SH_INCOMPLETE 
SH_HEAD_MODIFIED 
SH_TRY_WALK 

Definition at line 49 of file pns_shove.h.

50 {
51 SH_OK = 0,
52 SH_NULL,
56 };
@ SH_INCOMPLETE
Definition: pns_shove.h:53
@ SH_HEAD_MODIFIED
Definition: pns_shove.h:54
@ SH_TRY_WALK
Definition: pns_shove.h:55

Constructor & Destructor Documentation

◆ SHOVE()

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

Definition at line 157 of file pns_shove.cpp.

157 :
158 ALGO_BASE( aRouter )
159{
161 m_forceClearance = -1;
162 m_root = aWorld;
163 m_currentNode = aWorld;
164 SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
165
166 // Initialize other temporary variables:
167 m_draggedVia = nullptr;
168 m_iter = 0;
169 m_multiLineMode = false;
172}
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Assign a debug decorator allowing this algo to draw extra graphics for visual debugging.
Definition: pns_algo_base.h:73
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:45
int m_iter
Definition: pns_shove.h:183
NODE * m_currentNode
Definition: pns_shove.h:174
int m_forceClearance
Definition: pns_shove.h:184
int m_restrictSpringbackTagId
Definition: pns_shove.h:176
NODE * m_root
Definition: pns_shove.h:173
NODE * m_springbackDoNotTouchNode
Definition: pns_shove.h:175
bool m_multiLineMode
Definition: pns_shove.h:185
int m_optFlagDisableMask
Definition: pns_shove.h:187
VIA * m_draggedVia
Definition: pns_shove.h:181

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

◆ ~SHOVE()

PNS::SHOVE::~SHOVE ( )

Definition at line 175 of file pns_shove.cpp.

176{
177 std::unordered_set<LINE*> alreadyDeleted;
178
179 for( auto it : m_rootLineHistory )
180 {
181 auto it2 = alreadyDeleted.find( it.second );
182
183 if( it2 == alreadyDeleted.end() )
184 {
185 alreadyDeleted.insert( it.second );
186 delete it.second;
187 }
188 }
189}
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:171

References m_rootLineHistory.

Member Function Documentation

◆ AddLockedSpringbackNode()

bool PNS::SHOVE::AddLockedSpringbackNode ( NODE aNode)

Definition at line 1973 of file pns_shove.cpp.

1974{
1975 SPRINGBACK_TAG sp;
1976 sp.m_node = aNode;
1977 sp.m_locked = true;
1978
1979 m_nodeStack.push_back(sp);
1980 return true;
1981}
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:168

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 = nullptr 
)
private

Definition at line 192 of file pns_shove.cpp.

193{
194 return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
195}
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=nullptr, bool aStopAtLockedJoints=false, bool aFollowLockedSegments=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:999

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 206 of file pns_shove.cpp.

208{
209 SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
210 checker.AddPolyline( aObstacleLine.CLine() );
211 checker.AddPolyline( aShovedLine.CLine().Reverse() );
212
213 bool inside = checker.IsInside();
214
215 return !inside;
216}
A dynamic state checking if a point lies within polygon with a dynamically built outline ( with each ...

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

Referenced by shoveLineToHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1952 of file pns_shove.cpp.

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

References m_nodeStack, and m_root.

◆ Dbg()

◆ DisablePostShoveOptimizations()

void PNS::SHOVE::DisablePostShoveOptimizations ( int  aMask)

Definition at line 2042 of file pns_shove.cpp.

2043{
2044 m_optFlagDisableMask = aMask;
2045}

References m_optFlagDisableMask.

◆ findRootLine()

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

Definition at line 1842 of file pns_shove.cpp.

1843{
1844 for( auto link : aLine->Links() )
1845 {
1846 if( auto seg = dyn_cast<SEGMENT*>( link ) )
1847 {
1848 auto it = m_rootLineHistory.find( seg );
1849
1850 if( it != m_rootLineHistory.end() )
1851 return it->second;
1852 }
1853 }
1854
1855 return nullptr;
1856}

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

Referenced by runOptimizer().

◆ fixupViaCollisions()

bool PNS::SHOVE::fixupViaCollisions ( const LINE aCurrent,
OBSTACLE obs 
)
private

Definition at line 1246 of file pns_shove.cpp.

1247{
1248 // if the current obstacle is a via, consider also the lines connected to it
1249 // if their widths are larger or equal than the via diameter, the shove algorithm
1250 // will very likely fail in the subsequent iterations (as our base assumption is track
1251 // ends can never move on their own, only dragged by force-propagated vias
1252
1253 // our colliding item is a via: just find the max width of the traces connected to it
1254 if( obs.m_item->OfKind( ITEM::VIA_T ) )
1255 {
1256 VIA* v = static_cast<VIA*>( obs.m_item );
1257 int maxw = 0;
1258 JOINT* jv = m_currentNode->FindJoint( v->Pos(), v );
1259
1260 for( auto link : jv->Links() )
1261 {
1262 if( link.item->OfKind( ITEM::SEGMENT_T ) ) // consider segments ...
1263 {
1264 auto seg = static_cast<SEGMENT*>( link.item );
1265 maxw = std::max( seg->Width(), maxw );
1266 }
1267 else if( link.item->OfKind( ITEM::ARC_T ) ) // ... or arcs
1268 {
1269 auto arc = static_cast<ARC*>( link.item );
1270 maxw = std::max( arc->Width(), maxw );
1271 }
1272 }
1273
1274 obs.m_maxFanoutWidth = 0;
1275
1276 if( maxw > 0 && maxw >= v->Diameter() )
1277 {
1278 obs.m_maxFanoutWidth = maxw + 1;
1279 PNS_DBG( Dbg(), Message,
1280 wxString::Format( "Fixup via: new-w %d via-w %d", maxw, v->Diameter() ) );
1281
1282 return true;
1283 }
1284 return false;
1285 }
1286
1287
1288 // our colliding item is a segment. check if it has a via on either of the ends.
1289 if( !obs.m_item->OfKind( ITEM::SEGMENT_T ) )
1290 return false;
1291
1292 auto s = static_cast<SEGMENT*>( obs.m_item );
1293
1294 JOINT* ja = m_currentNode->FindJoint( s->Seg().A, s );
1295 JOINT* jb = m_currentNode->FindJoint( s->Seg().B, s );
1296
1297 VIA* vias[] = { ja->Via(), jb->Via() };
1298
1299 for( int i = 0; i < 2; i++ )
1300 {
1301 VIA* v = vias[i];
1302
1303 // via diameter is larger than the segment width - cool, the force propagation algo
1304 // will be able to deal with it, no need to intervene
1305 if( !v || v->Diameter() > s->Width() )
1306 continue;
1307
1308 VIA vtest( *v );
1309 vtest.SetDiameter( s->Width() );
1310
1311 // enlarge the via to the width of the segment
1312 if( vtest.Collide( aCurrent, m_currentNode ) )
1313 {
1314 // if colliding, drop the segment in the shove iteration loop and force-propagate the via instead
1315 obs.m_item = v;
1316 obs.m_maxFanoutWidth = s->Width() + 1;
1317 return true;
1318 }
1319 }
1320 return false;
1321}
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
@ SEGMENT_T
Definition: pns_item.h:66
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1197
#define PNS_DBG(dbg, method,...)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:200
@ VIA
Normal via.
Definition: router_tool.cpp:89

References PNS::ITEM::ARC_T, PNS::ITEM::Collide(), PNS::ALGO_BASE::Dbg(), PNS::VIA::Diameter(), PNS::NODE::FindJoint(), Format(), PNS::JOINT::Links(), m_currentNode, PNS::OBSTACLE::m_item, PNS::OBSTACLE::m_maxFanoutWidth, PNS::ITEM::OfKind(), PNS_DBG, PNS::VIA::Pos(), PNS::ITEM::SEGMENT_T, PNS::VIA::SetDiameter(), PNS::JOINT::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ ForceClearance()

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

Definition at line 74 of file pns_shove.h.

75 {
76 if( aEnabled )
77 m_forceClearance = aClearance;
78 else
80 }

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 132 of file pns_shove.cpp.

133{
134 if( m_forceClearance >= 0 )
135 return m_forceClearance;
136
137 return m_currentNode->GetClearance( aA, aB );
138}
int GetClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:103

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 141 of file pns_shove.cpp.

142{
143 if( m_forceClearance >= 0 )
144 return m_forceClearance;
145
146 return m_currentNode->GetHoleClearance( aA, aB );
147}
int GetHoleClearance(const ITEM *aA, const ITEM *aB, bool aUseClearanceEpsilon=true) const
Definition: pns_node.cpp:115

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

◆ Logger()

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

Reimplemented from PNS::ALGO_BASE.

Definition at line 61 of file pns_shove.h.

62 {
63 return &m_logger;
64 }
LOGGER m_logger
Definition: pns_shove.h:180

References m_logger.

◆ NewHead()

const LINE PNS::SHOVE::NewHead ( ) const

Definition at line 1958 of file pns_shove.cpp.

1959{
1960 assert( m_newHead );
1961
1962 return *m_newHead;
1963}
OPT_LINE m_newHead
Definition: pns_shove.h:178

References m_newHead.

◆ onCollidingArc()

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

Definition at line 560 of file pns_shove.cpp.

561{
562 int segIndex;
563 LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
564 LINE shovedLine( obstacleLine );
565 ARC tmp( *aObstacleArc );
566
567 if( obstacleLine.HasLockedSegments() )
568 return SH_TRY_WALK;
569
570 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
571
572 const double extensionWalkThreshold = 1.0;
573
574 double obsLen = obstacleLine.CLine().Length();
575 double shovedLen = shovedLine.CLine().Length();
576 double extensionFactor = 0.0;
577
578 if( obsLen != 0.0f )
579 extensionFactor = shovedLen / obsLen - 1.0;
580
581 if( extensionFactor > extensionWalkThreshold )
582 return SH_TRY_WALK;
583
584 assert( obstacleLine.LayersOverlap( &shovedLine ) );
585
586 PNS_DBG( Dbg(), AddItem, &tmp, WHITE, 10000, wxT( "obstacle-arc" ) );
587 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
588 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxT( "obstacle-line" ) );
589 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
590
591 if( rv == SH_OK )
592 {
593 if( shovedLine.Marker() & MK_HEAD )
594 {
595 if( m_multiLineMode )
596 return SH_INCOMPLETE;
597
598 m_newHead = shovedLine;
599 }
600
601 int rank = aCurrent.Rank();
602 shovedLine.SetRank( rank - 1 );
603
604 sanityCheck( &obstacleLine, &shovedLine );
605 replaceLine( obstacleLine, shovedLine );
606
607 if( !pushLineStack( shovedLine ) )
608 rv = SH_INCOMPLETE;
609 }
610
611 return rv;
612}
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:405
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=nullptr)
Definition: pns_shove.cpp:192
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1196
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:62
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:150
@ WHITE
Definition: color4d.h:48
@ BLUE
Definition: color4d.h:56
@ GREEN
Definition: color4d.h:57
@ RED
Definition: color4d.h:59
@ MK_HEAD
Definition: pns_item.h:41

References assembleLine(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, ShoveObstacleLine(), and WHITE.

Referenced by shoveIteration().

◆ onCollidingLine()

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

Definition at line 618 of file pns_shove.cpp.

619{
620 LINE shovedLine( aObstacle );
621
622 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
623
624 PNS_DBG( Dbg(), AddItem, &aObstacle, RED, 100000, wxT( "obstacle-line" ) );
625 PNS_DBG( Dbg(), AddItem, &aCurrent, GREEN, 150000, wxT( "current-line" ) );
626 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 200000, wxT( "shoved-line" ) );
627
628 if( rv == SH_OK )
629 {
630 if( shovedLine.Marker() & MK_HEAD )
631 {
632 if( m_multiLineMode )
633 return SH_INCOMPLETE;
634
635 m_newHead = shovedLine;
636 }
637
638 sanityCheck( &aObstacle, &shovedLine );
639 replaceLine( aObstacle, shovedLine );
640
641 int rank = aObstacle.Rank();
642 shovedLine.SetRank( rank - 1 );
643
644
645 if( !pushLineStack( shovedLine ) )
646 {
647 rv = SH_INCOMPLETE;
648 }
649 }
650
651 return rv;
652}

References BLUE, PNS::ALGO_BASE::Dbg(), GREEN, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), PNS::LINE::Rank(), RED, 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 496 of file pns_shove.cpp.

497{
498 int segIndex;
499 LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
500 LINE shovedLine( obstacleLine );
501 SEGMENT tmp( *aObstacleSeg );
502
503 if( obstacleLine.HasLockedSegments() )
504 {
505 PNS_DBG(Dbg(), Message, "try walk (locked segments)");
506 return SH_TRY_WALK;
507 }
508
509 SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
510
511 const double extensionWalkThreshold = 1.0;
512
513 double obsLen = obstacleLine.CLine().Length();
514 double shovedLen = shovedLine.CLine().Length();
515 double extensionFactor = 0.0;
516
517 if( obsLen != 0.0f )
518 extensionFactor = shovedLen / obsLen - 1.0;
519
520 if( extensionFactor > extensionWalkThreshold )
521 return SH_TRY_WALK;
522
523 assert( obstacleLine.LayersOverlap( &shovedLine ) );
524
525 if( Dbg() )
526 {
527 PNS_DBG( Dbg(), AddItem, aObstacleSeg, BLUE, 0, wxT( "shove-changed-area" ) );
528 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxString::Format( "current-line [l %d v %d]", aCurrent.Layer(), aCurrent.EndsWithVia() ) );
529 PNS_DBG( Dbg(), AddItem, &obstacleLine, GREEN, 10000, wxString::Format( "obstacle-line [l %d v %d]", obstacleLine.Layer(), obstacleLine.EndsWithVia() ) );
530 PNS_DBG( Dbg(), AddItem, &shovedLine, BLUE, 10000, wxT( "shoved-line" ) );
531 }
532
533 if( rv == SH_OK )
534 {
535 if( shovedLine.Marker() & MK_HEAD )
536 {
537 if( m_multiLineMode )
538 return SH_INCOMPLETE;
539
540 m_newHead = shovedLine;
541 }
542
543 int rank = aCurrent.Rank();
544 shovedLine.SetRank( rank - 1 );
545
546 sanityCheck( &obstacleLine, &shovedLine );
547 replaceLine( obstacleLine, shovedLine );
548
549 if( !pushLineStack( shovedLine ) )
550 rv = SH_INCOMPLETE;
551 }
552
553 return rv;
554}

References assembleLine(), BLUE, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), GREEN, PNS::LINE::HasLockedSegments(), PNS::ITEM::Layer(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), sanityCheck(), 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,
OBSTACLE aObstacleInfo 
)
private

Definition at line 658 of file pns_shove.cpp.

659{
660 WALKAROUND walkaround( m_currentNode, Router() );
661 LINE walkaroundLine( aCurrent );
662
663 if( aCurrent.EndsWithVia() )
664 {
665 VIA vh = aCurrent.Via();
666 VIA* via = nullptr;
667 JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
668
669 if( !jtStart )
670 return SH_INCOMPLETE;
671
672 for( ITEM* item : jtStart->LinkList() )
673 {
674 if( item->OfKind( ITEM::VIA_T ) )
675 {
676 via = (VIA*) item;
677 break;
678 }
679 }
680
681 if( via && via->Collide( aObstacle, m_currentNode ) )
682 return onCollidingVia( aObstacle, via, aObstacleInfo );
683 }
684
685 TOPOLOGY topo( m_currentNode );
686
687 std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
688
689
690
691 PNS_DBG( Dbg(), BeginGroup, "walk-cluster", 1 );
692
693 for( auto item : cluster )
694 {
695 PNS_DBG( Dbg(), AddItem, item, RED, 10000, wxT( "cl-item" ) );
696 }
697
698 PNS_DBGN( Dbg(), EndGroup );
699
700
701 walkaround.SetDebugDecorator( Dbg() );
702 walkaround.SetSolidsOnly( false );
703 walkaround.RestrictToSet( true, cluster );
704 walkaround.SetIterationLimit( 16 ); // fixme: make configurable
705
706 int currentRank = aCurrent.Rank();
707 int nextRank;
708
709 bool success = false;
710
711 for( int attempt = 0; attempt < 2; attempt++ )
712 {
713 if( attempt == 1 || Settings().JumpOverObstacles() )
714 {
715
716 nextRank = currentRank - 1;
717 }
718 else
719 {
720 nextRank = currentRank + 10000;
721 }
722
723
724 WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
725
726 if( status != WALKAROUND::DONE )
727 continue;
728
729 walkaroundLine.ClearLinks();
730 walkaroundLine.Unmark();
731 walkaroundLine.Line().Simplify();
732
733 if( walkaroundLine.HasLoops() )
734 continue;
735
736 if( aCurrent.Marker() & MK_HEAD )
737 {
738 walkaroundLine.Mark( MK_HEAD );
739
740 if( m_multiLineMode )
741 continue;
742
743 m_newHead = walkaroundLine;
744 }
745
746 sanityCheck( &aCurrent, &walkaroundLine );
747
748 if( !m_lineStack.empty() )
749 {
750 LINE lastLine = m_lineStack.front();
751
752 if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
753 {
754 LINE dummy( lastLine );
755
756 if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
757 {
758 success = true;
759 break;
760 }
761 }
762 else
763 {
764 success = true;
765 break;
766 }
767 }
768 }
769
770 if(!success)
771 return SH_INCOMPLETE;
772
773 replaceLine( aCurrent, walkaroundLine );
774 walkaroundLine.SetRank( nextRank );
775
776 PNS_DBG( Dbg(), AddItem, &aCurrent, RED, 10000, wxT( "current-line" ) );
777 PNS_DBG( Dbg(), AddItem, &walkaroundLine, BLUE, 10000, wxT( "walk-line" ) );
778
779 popLineStack();
780
781 if( !pushLineStack( walkaroundLine ) )
782 return SH_INCOMPLETE;
783
784 return SH_OK;
785}
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
std::vector< LINE > m_lineStack
Definition: pns_shove.h:169
void popLineStack()
Definition: pns_shove.cpp:1220
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:994
#define PNS_DBGN(dbg, method)
std::vector< FAB_LAYER_COLOR > dummy

References PNS::TOPOLOGY::AssembleCluster(), BLUE, PNS::LINK_HOLDER::ClearLinks(), PNS::ITEM::Collide(), PNS::ALGO_BASE::Dbg(), PNS::WALKAROUND::DONE, dummy, 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, onCollidingVia(), PNS_DBG, PNS_DBGN, popLineStack(), PNS::VIA::Pos(), pushLineStack(), PNS::LINE::Rank(), RED, replaceLine(), PNS::WALKAROUND::RestrictToSet(), PNS::WALKAROUND::Route(), PNS::ALGO_BASE::Router(), sanityCheck(), PNS::ALGO_BASE::SetDebugDecorator(), PNS::WALKAROUND::SetIterationLimit(), PNS::LINE::SetRank(), PNS::WALKAROUND::SetSolidsOnly(), PNS::ALGO_BASE::Settings(), SH_INCOMPLETE, SH_OK, ShoveObstacleLine(), SHAPE_LINE_CHAIN::Simplify(), LAYER_RANGE::Start(), PNS::LINE::Unmark(), via, PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingVia ( ITEM aCurrent,
VIA aObstacleVia,
OBSTACLE aObstacleInfo 
)
private

Definition at line 994 of file pns_shove.cpp.

995{
996 assert( aObstacleVia );
997
998 int clearance = getClearance( aCurrent, aObstacleVia );
999 VECTOR2I mtv;
1000 int rank = -1;
1001
1002 bool lineCollision = false;
1003 bool viaCollision = false;
1004 VECTOR2I mtvLine, mtvVia;
1005
1006 PNS_DBG( Dbg(), BeginGroup, "push-via-by-line", 1 );
1007
1008 if( aCurrent->OfKind( ITEM::LINE_T ) )
1009 {
1010 VIA vtmp ( *aObstacleVia );
1011
1012 if( aObstacleInfo.m_maxFanoutWidth > 0 && aObstacleInfo.m_maxFanoutWidth > aObstacleVia->Diameter() )
1013 {
1014 vtmp.SetDiameter( aObstacleInfo.m_maxFanoutWidth );
1015 }
1016
1017 LINE* currentLine = (LINE*) aCurrent;
1018
1019 PNS_DBG( Dbg(), AddItem, currentLine, LIGHTRED, 10000, wxT( "current-line" ) );
1020
1021 if( currentLine->EndsWithVia() )
1022 {
1023 PNS_DBG( Dbg(), AddItem, &currentLine->Via(), LIGHTRED, 10000, wxT( "current-line-via" ) );
1024 }
1025
1026 PNS_DBG( Dbg(), AddItem, &vtmp, LIGHTRED, 100000, wxT( "orig-via" ) );
1027
1028 lineCollision = vtmp.Shape()->Collide( currentLine->Shape(),
1029 clearance + currentLine->Width() / 2,
1030 &mtvLine );
1031
1032 // Check the via if present. Via takes priority.
1033 if( currentLine->EndsWithVia() )
1034 {
1035 const VIA& currentVia = currentLine->Via();
1036 int viaClearance = getClearance( &currentVia, &vtmp );
1037
1038 viaCollision = currentVia.Shape()->Collide( vtmp.Shape(), viaClearance, &mtvVia );
1039 }
1040 }
1041 else if( aCurrent->OfKind( ITEM::SOLID_T ) )
1042 {
1043 // TODO: is this possible at all? We don't shove solids.
1044 return SH_INCOMPLETE;
1045 }
1046
1047 // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
1048 if( viaCollision )
1049 mtv = -mtvVia;
1050 else if ( lineCollision )
1051 mtv = -mtvLine;
1052 else
1053 mtv = VECTOR2I(0, 0);
1054
1055 SHOVE::SHOVE_STATUS st = pushOrShoveVia( aObstacleVia, -mtv, aCurrent->Rank() );
1056 PNS_DBG(Dbg(), Message, wxString::Format("push-or-shove-via st %d", st ) );
1057
1058 PNS_DBGN( Dbg(), EndGroup );
1059
1060 return st;
1061}
@ SOLID_T
Definition: pns_item.h:63
@ LINE_T
Definition: pns_item.h:64
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:867
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:132
@ LIGHTRED
Definition: color4d.h:65
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References SHAPE::Collide(), PNS::ALGO_BASE::Dbg(), PNS::VIA::Diameter(), PNS::LINE::EndsWithVia(), Format(), getClearance(), LIGHTRED, PNS::ITEM::LINE_T, PNS::OBSTACLE::m_maxFanoutWidth, PNS::ITEM::OfKind(), PNS_DBG, PNS_DBGN, pushOrShoveVia(), PNS::ITEM::Rank(), PNS::VIA::SetDiameter(), SH_INCOMPLETE, PNS::LINE::Shape(), PNS::VIA::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 1067 of file pns_shove.cpp.

1068{
1069 int n = 0;
1070 LINE cur( aCurrent );
1071 cur.ClearLinks();
1072
1073 JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1074 LINE shoved( aCurrent );
1075 shoved.ClearLinks();
1076
1077 cur.RemoveVia();
1078 unwindLineStack( &aCurrent );
1079
1080 for( ITEM* item : jt->LinkList() )
1081 {
1082 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1083 {
1084 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1085 LINE head = assembleLine( li );
1086
1087 head.AppendVia( *aObstacleVia );
1088
1089 SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1090
1091 if( st != SH_OK )
1092 {
1093#if 0
1094 m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1095 m_logger.Log( aObstacleVia, 0, "the-via" );
1096 m_logger.Log( &aCurrent, 1, "current-line" );
1097 m_logger.Log( &shoved, 3, "shoved-line" );
1098#endif
1099
1100 return st;
1101 }
1102
1103 cur.SetShape( shoved.CLine() );
1104 n++;
1105 }
1106 }
1107
1108 if( !n )
1109 {
1110#if 0
1111 m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1112 m_logger.Log( aObstacleVia, 0, "the-via" );
1113 m_logger.Log( &aCurrent, 1, "current-line" );
1114#endif
1115
1116 LINE head( aCurrent );
1117 head.Line().Clear();
1118 head.AppendVia( *aObstacleVia );
1119 head.ClearLinks();
1120
1121 SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1122
1123 if( st != SH_OK )
1124 return st;
1125
1126 cur.SetShape( shoved.CLine() );
1127 }
1128
1129 if( aCurrent.EndsWithVia() )
1130 shoved.AppendVia( aCurrent.Via() );
1131
1132#if 0
1133 m_logger.NewGroup( "on-reverse-via", m_iter );
1134 m_logger.Log( aObstacleVia, 0, "the-via" );
1135 m_logger.Log( &aCurrent, 1, "current-line" );
1136 m_logger.Log( &shoved, 3, "shoved-line" );
1137#endif
1138
1139 PNS_DBG( Dbg(), AddItem, aObstacleVia, YELLOW, 0, wxT( "rr-the-via" ) );
1140 PNS_DBG( Dbg(), AddItem, &aCurrent, BLUE, 0, wxT( "rr-current-line" ) );
1141 PNS_DBG( Dbg(), AddItem, &shoved, GREEN, 0, wxT( "rr-shoved-line" ) );
1142
1143 int currentRank = aCurrent.Rank();
1144 replaceLine( aCurrent, shoved );
1145
1146 if( !pushLineStack( shoved ) )
1147 return SH_INCOMPLETE;
1148
1149 shoved.SetRank( currentRank );
1150
1151 return SH_OK;
1152}
void Log(EVENT_TYPE evt, const VECTOR2I &pos=VECTOR2I(), const ITEM *item=nullptr, const SIZES_SETTINGS *sizes=nullptr)
Definition: pns_logger.cpp:64
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1155
@ YELLOW
Definition: color4d.h:67

References PNS::LINE::AppendVia(), PNS::ITEM::ARC_T, assembleLine(), BLUE, SHAPE_LINE_CHAIN::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), GREEN, PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_logger, PNS_DBG, 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(), PNS::LINE::Via(), and YELLOW.

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )
private

Definition at line 1220 of file pns_shove.cpp.

1221{
1222 LINE& l = m_lineStack.back();
1223
1224 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1225 {
1226 bool found = false;
1227
1228 for( LINKED_ITEM* s : l.Links() )
1229 {
1230 if( i->ContainsLink( s ) )
1231 {
1232 i = m_optimizerQueue.erase( i );
1233 found = true;
1234 break;
1235 }
1236 }
1237
1238 if( !found )
1239 i++;
1240 }
1241
1242 m_lineStack.pop_back();
1243}
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:170

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 1196 of file pns_shove.cpp.

1197{
1198 if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1199 {
1200 PNS_DBG( Dbg(), AddItem, &aL, BLUE, 10000, wxT( "push line stack failed" ) );
1201
1202 return false;
1203 }
1204
1205 if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1206 {
1207 m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1208 }
1209 else
1210 {
1211 m_lineStack.push_back( aL );
1212 }
1213
1214 m_optimizerQueue.push_back( aL );
1215
1216 return true;
1217}

References BLUE, PNS::ALGO_BASE::Dbg(), PNS::LINE::IsLinkedChecked(), m_lineStack, m_optimizerQueue, PNS_DBG, 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 867 of file pns_shove.cpp.

868{
869 LINE_PAIR_VEC draggedLines;
870 VECTOR2I p0( aVia->Pos() );
871 JOINT* jt = m_currentNode->FindJoint( p0, aVia );
872 VECTOR2I p0_pushed( p0 + aForce );
873
874 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "via force [%d %d]\n" ), aForce.x, aForce.y ) );
875
876 // nothing to do...
877 if ( aForce.x == 0 && aForce.y == 0 )
878 return SH_OK;
879
880 if( !jt )
881 {
882 PNS_DBG( Dbg(), Message,
883 wxString::Format( wxT( "weird, can't find the center-of-via joint\n" ) ) );
884 return SH_INCOMPLETE;
885 }
886
887 if( Settings().ShoveVias() == false || aVia->IsLocked() )
888 return SH_TRY_WALK;
889
890 if( jt->IsLocked() )
891 return SH_INCOMPLETE;
892
893 // make sure pushed via does not overlap with any existing joint
894 while( true )
895 {
896 JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
897
898 if( !jt_next )
899 break;
900
901 p0_pushed += aForce.Resize( 2 );
902 }
903
904 std::unique_ptr<VIA> pushedVia = Clone( *aVia );
905 pushedVia->SetPos( p0_pushed );
906 pushedVia->Mark( aVia->Marker() );
907
908 for( ITEM* item : jt->LinkList() )
909 {
910 if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
911 {
912 LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
913 LINE_PAIR lp;
914 int segIndex;
915
916 lp.first = assembleLine( li, &segIndex );
917
918 if( lp.first.HasLockedSegments() )
919 return SH_TRY_WALK;
920
921 assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
922
923 if( segIndex == 0 )
924 lp.first.Reverse();
925
926 lp.second = lp.first;
927 lp.second.ClearLinks();
928 lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
929 lp.second.AppendVia( *pushedVia );
930 draggedLines.push_back( lp );
931 }
932 }
933
934 pushedVia->SetRank( aCurrentRank - 1 );
935 PNS_DBG( Dbg(), Message, wxString::Format("PushViaRank %d\n", pushedVia->Rank() ) );
936
937 if( aVia->Marker() & MK_HEAD ) // push
938 {
939 m_draggedVia = pushedVia.get();
940 }
941 else
942 { // shove
943 if( jt->IsStitchingVia() )
944 pushLineStack( LINE( *pushedVia ) );
945 }
946
947 PNS_DBG( Dbg(), AddPoint, aVia->Pos(), LIGHTGREEN, 100000, "via-pre" );
948 PNS_DBG( Dbg(), AddPoint, pushedVia->Pos(), LIGHTRED, 100000, "via-post" );
949
950 replaceItems( aVia, std::move( pushedVia ) );
951
952 for( LINE_PAIR lp : draggedLines )
953 {
954 if( lp.first.Marker() & MK_HEAD )
955 {
956 lp.second.Mark( MK_HEAD );
957
958 if( m_multiLineMode )
959 return SH_INCOMPLETE;
960
961 m_newHead = lp.second;
962 }
963
964 unwindLineStack( &lp.first );
965
966 if( lp.second.SegmentCount() )
967 {
968 replaceLine( lp.first, lp.second );
969 lp.second.SetRank( aCurrentRank - 1 );
970
971
972 PNS_DBG( Dbg(), Message, wxString::Format("PushViaF %p %d\n", &lp.second, lp.second.SegmentCount() ) );
973
974 if( !pushLineStack( lp.second, true ) )
975 return SH_INCOMPLETE;
976 }
977 else
978 {
979 m_currentNode->Remove( lp.first );
980 }
981
982 PNS_DBG( Dbg(), AddItem, &lp.first, LIGHTGREEN, 10000, wxT( "fan-pre" ) );
983 PNS_DBG( Dbg(), AddItem, &lp.second, LIGHTRED, 10000, wxT( "fan-post" ) );
984 }
985
986 return SH_OK;
987}
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:889
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:98
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:51
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:99
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378
@ LIGHTGREEN
Definition: color4d.h:63
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:279

References PNS::ITEM::ARC_T, assembleLine(), PNS::Clone(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), Format(), PNS::ITEM::IsLocked(), PNS::JOINT::IsLocked(), PNS::JOINT::IsStitchingVia(), LIGHTGREEN, LIGHTRED, PNS::JOINT::LinkList(), m_currentNode, m_draggedVia, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS_DBG, PNS::VIA::Pos(), pushLineStack(), PNS::NODE::Remove(), replaceItems(), replaceLine(), VECTOR2< T >::Resize(), PNS::ITEM::SEGMENT_T, PNS::ALGO_BASE::Settings(), 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 827 of file pns_shove.cpp.

828{
829 SPRINGBACK_TAG st;
830 OPT_BOX2I prev_area;
831
832 if( !m_nodeStack.empty() )
833 prev_area = m_nodeStack.back().m_affectedArea;
834
835 if( aDraggedVia )
836 {
837 st.m_draggedVia = aDraggedVia->MakeHandle();
838 }
839
840 st.m_node = aNode;
841
842 if( aAffectedArea )
843 {
844 if( prev_area )
845 st.m_affectedArea = prev_area->Merge( *aAffectedArea );
846 else
847 st.m_affectedArea = aAffectedArea;
848 }
849 else
850 {
851 st.m_affectedArea = prev_area;
852 }
853
854 st.m_seq = ( m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1 );
855 st.m_locked = false;
856
857 m_nodeStack.push_back( st );
858
859 return true;
860}
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:850

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 792 of file pns_shove.cpp.

793{
794 while( !m_nodeStack.empty() )
795 {
796 SPRINGBACK_TAG& spTag = m_nodeStack.back();
797
798 // Prevent the springback algo from erasing NODEs that might contain items used by the ROUTER_TOOL/LINE_PLACER.
799 // I noticed this can happen for the endItem provided to LINE_PLACER::Move() and cause a nasty crash.
800 if( spTag.m_node == m_springbackDoNotTouchNode )
801 break;
802
803 std::optional<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
804
805 if( !obs && !spTag.m_locked )
806 {
807 aDraggedVia = spTag.m_draggedVia;
808 aDraggedVia.valid = true;
809
810 delete spTag.m_node;
811 m_nodeStack.pop_back();
812 }
813 else
814 {
815 break;
816 }
817 }
818
819 return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
820}

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, m_springbackDoNotTouchNode, 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 51 of file pns_shove.cpp.

52{
53 OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
54
55 if( changed_area )
56 m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
57
58 m_currentNode->Replace( aOld, std::move( aNew ) );
59}
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:854
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:158
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:358

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 62 of file pns_shove.cpp.

63{
64 if( aIncludeInChangedArea )
65 {
66 OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
67
68 if( changed_area )
69 {
70 SHAPE_RECT r( *changed_area );
71 PNS_DBG(Dbg(), AddShape, &r, BLUE, 0, wxT( "shove-changed-area" ) );
72
74 m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
75 }
76 }
77
78 bool foundPredecessor = false;
79 LINE* rootLine = nullptr;
80
81 // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
82 // of the affected tracks in a map. The optimizer can then query the pre-shove shape
83 // for each shoved line and perform additional constraint checks (i.e. prevent overzealous
84 // optimizations)
85
86 // Check if the shoved line already has an ancestor (e.g. line from a previous shove
87 // iteration/cursor movement)
88 for( auto link : aOld.Links() )
89 {
90 auto oldLineIter = m_rootLineHistory.find( link );
91
92 if( oldLineIter != m_rootLineHistory.end() )
93 {
94 rootLine = oldLineIter->second;
95 foundPredecessor = true;
96 break;
97 }
98 }
99
100 // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
101 if( !foundPredecessor )
102 {
103 for( auto link : aOld.Links() )
104 {
105 if( ! rootLine )
106 {
107 rootLine = aOld.Clone();
108 }
109
110 m_rootLineHistory[link] = rootLine;
111 }
112 }
113
114 // Now update the NODE (calling Replace invalidates the Links() in a LINE)
115 if( aNode )
116 {
117 aNode->Replace( aOld, aNew );
118 }
119 else
120 {
121 m_currentNode->Replace( aOld, aNew );
122 }
123
124 // point the Links() of the new line to its oldest ancestor
125 for( auto link : aNew.Links() )
126 {
127 m_rootLineHistory[ link ] = rootLine;
128 }
129}

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

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

◆ RewindSpringbackTo()

bool PNS::SHOVE::RewindSpringbackTo ( NODE aNode)

Definition at line 1984 of file pns_shove.cpp.

1985{
1986 bool found = false;
1987
1988 auto iter = m_nodeStack.begin();
1989
1990 while( iter != m_nodeStack.end() )
1991 {
1992 if ( iter->m_node == aNode )
1993 {
1994 found = true;
1995 break;
1996 }
1997
1998 iter++;
1999 }
2000
2001 if( !found )
2002 return false;
2003
2004 auto start = iter;
2005
2006 aNode->KillChildren();
2007 m_nodeStack.erase( start, m_nodeStack.end() );
2008
2009 return true;
2010}

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

◆ RewindToLastLockedNode()

bool PNS::SHOVE::RewindToLastLockedNode ( )

Definition at line 2013 of file pns_shove.cpp.

2014{
2015 if( m_nodeStack.empty() )
2016 return false;
2017
2018 while( !m_nodeStack.back().m_locked && m_nodeStack.size() > 1 )
2019 m_nodeStack.pop_back();
2020
2021 return m_nodeStack.back().m_locked;
2022}

References m_nodeStack.

◆ Router()

◆ runOptimizer()

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

Definition at line 1859 of file pns_shove.cpp.

1860{
1861 OPTIMIZER optimizer( aNode );
1862 int optFlags = 0;
1863 int n_passes = 0;
1864
1866
1868
1869 int maxWidth = 0;
1870
1871 for( LINE& line : m_optimizerQueue )
1872 maxWidth = std::max( line.Width(), maxWidth );
1873
1874 if( area )
1875 {
1876 area->Inflate( maxWidth );
1877 area = area->Intersect( VisibleViewArea() );
1878 }
1879
1880 switch( effort )
1881 {
1882 case OE_LOW:
1883 optFlags |= OPTIMIZER::MERGE_OBTUSE;
1884 n_passes = 1;
1885 break;
1886
1887 case OE_MEDIUM:
1888 optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1889
1890 n_passes = 2;
1891 break;
1892
1893 case OE_FULL:
1894 optFlags = OPTIMIZER::MERGE_SEGMENTS;
1895 n_passes = 2;
1896 break;
1897
1898 default:
1899 break;
1900 }
1901
1903
1904 if( area )
1905 {
1906 SHAPE_RECT r( *area );
1907
1908 PNS_DBG( Dbg(), AddShape, &r, BLUE, 0, wxT( "opt-area" ) );
1909
1910 optFlags |= OPTIMIZER::RESTRICT_AREA;
1911 optimizer.SetRestrictArea( *area, false );
1912 }
1913
1914 if( Settings().SmartPads() )
1915 optFlags |= OPTIMIZER::SMART_PADS;
1916
1917
1918 optimizer.SetEffortLevel( optFlags & ~m_optFlagDisableMask );
1919 optimizer.SetCollisionMask( ITEM::ANY_T );
1920
1921 for( int pass = 0; pass < n_passes; pass++ )
1922 {
1923 std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1924
1925 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "optimize %d lines, pass %d"), (int)m_optimizerQueue.size(), (int)pass ) );
1926
1927 for( LINE& line : m_optimizerQueue)
1928 {
1929 if( !( line.Marker() & MK_HEAD ) )
1930 {
1931 LINE optimized;
1932 LINE* root = findRootLine( &line );
1933
1934 if( optimizer.Optimize( &line, &optimized, root ) )
1935 {
1936 PNS_DBG( Dbg(), AddShape, &line.CLine(), BLUE, 0, wxT( "shove-pre-opt" ) );
1937 if( root )
1938 {
1939 PNS_DBG( Dbg(), AddItem, root, RED, 0, wxT( "shove-root-opt" ) );
1940 }
1941 replaceLine( line, optimized, false, aNode );
1942 line = optimized; // keep links in the lines in the queue up to date
1943
1944 PNS_DBG( Dbg(), AddShape, &line.CLine(), GREEN, 0, wxT( "shove-post-opt" ) );
1945 }
1946 }
1947 }
1948 }
1949}
const BOX2I & VisibleViewArea() const
@ LIMIT_CORNER_COUNT
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
@ SMART_PADS
Reroute pad exits.
@ MERGE_SEGMENTS
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
@ MERGE_OBTUSE
Reduce corner cost by merging obtuse segments.
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1842
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1549

References PNS::ITEM::ANY_T, BLUE, PNS::ALGO_BASE::Dbg(), findRootLine(), Format(), GREEN, PNS::OPTIMIZER::LIMIT_CORNER_COUNT, m_optFlagDisableMask, 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(), PNS_DBG, RED, 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 150 of file pns_shove.cpp.

151{
152 assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
153 assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
154}

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.

74 {
75 m_debugDecorator = aDecorator;
76 }

References PNS::ALGO_BASE::m_debugDecorator.

Referenced by onCollidingSolid(), PNS::LINE_PLACER::rhWalkBase(), SHOVE(), and PNS::DRAGGER::tryWalkaround().

◆ SetInitialLine()

void PNS::SHOVE::SetInitialLine ( LINE aInitial)

Definition at line 1966 of file pns_shove.cpp.

1967{
1968 m_root = m_root->Branch();
1969 m_root->Remove( aInitial );
1970}
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:139

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.

66 {
67 m_logger = aLogger;
68 }
LOGGER * m_logger
Definition: pns_algo_base.h:88

References PNS::ALGO_BASE::m_logger.

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

◆ SetSpringbackDoNotTouchNode()

void PNS::SHOVE::SetSpringbackDoNotTouchNode ( NODE aNode)

Definition at line 2048 of file pns_shove.cpp.

2049{
2051}

References m_springbackDoNotTouchNode.

◆ Settings()

◆ ShoveDraggingVia()

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

Definition at line 1774 of file pns_shove.cpp.

1776{
1777 SHOVE_STATUS st = SH_OK;
1778
1779 m_lineStack.clear();
1780 m_optimizerQueue.clear();
1781 m_newHead = OPT_LINE();
1782 m_draggedVia = nullptr;
1783
1784 VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1785
1786 if( !viaToDrag )
1787 return SH_INCOMPLETE;
1788
1789 // Pop NODEs containing previous shoves which are no longer necessary
1790 ITEM_SET headSet;
1791
1792 VIA headVia ( *viaToDrag );
1793 headVia.SetPos( aWhere );
1794 headSet.Add( headVia );
1795 VIA_HANDLE prevViaHandle;
1796 NODE* parent = reduceSpringback( headSet, prevViaHandle );
1797
1798 if( prevViaHandle.valid )
1799 {
1800 aNewVia = prevViaHandle;
1801 viaToDrag = findViaByHandle( parent, prevViaHandle );
1802 }
1803
1804 // Create a new NODE to store this version of the world
1805 m_currentNode = parent->Branch();
1807
1808 viaToDrag->Mark( MK_HEAD );
1809 viaToDrag->SetRank( 100000 );
1810
1811 // Push the via to its new location
1812 st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1813
1814 // Shove any colliding objects out of the way
1815 if( st == SH_OK )
1816 st = shoveMainLoop();
1817
1818 if( st == SH_OK )
1820
1821 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1822 {
1823 wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1824
1825 if (!m_draggedVia)
1826 m_draggedVia = viaToDrag;
1827
1828 aNewVia = m_draggedVia->MakeHandle();
1829
1831 }
1832 else
1833 {
1834 delete m_currentNode;
1835 m_currentNode = parent;
1836 }
1837
1838 return st;
1839}
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1502
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1503
std::optional< LINE > OPT_LINE
Definition: pns_shove.h:97
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:792
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1859
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:827
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:213
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1754

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, 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 1326 of file pns_shove.cpp.

1327{
1328 LINE currentLine = m_lineStack.back();
1329 NODE::OPT_OBSTACLE nearest;
1330 SHOVE_STATUS st = SH_NULL;
1331
1332 if( Dbg() )
1333 {
1334 Dbg()->SetIteration( aIter );
1335 }
1336
1337 PNS_DBG( Dbg(), AddItem, &currentLine, RED, currentLine.Width(), wxString::Format( "current-coll-chk rank %d", currentLine.Rank() ) );
1338
1339 for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1340 {
1341 nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1342
1343 if( nearest )
1344 {
1345 PNS_DBG( Dbg(), Message,
1346 wxString::Format( wxT( "nearest %p %s rank %d" ), nearest->m_item,
1347 nearest->m_item->KindStr(), nearest->m_item->Rank() ) );
1348
1349 PNS_DBG( Dbg(), AddShape, nearest->m_item->Shape(), YELLOW, 10000, wxT("nearest") );
1350 }
1351
1352 if( nearest )
1353 break;
1354 }
1355
1356 if( !nearest )
1357 {
1358 m_lineStack.pop_back();
1359 PNS_DBG( Dbg(), Message, "no-nearest-item ");
1360 return SH_OK;
1361 }
1362
1363 bool viaFixup = fixupViaCollisions( &currentLine, *nearest );
1364
1365 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: VF %d", aIter, viaFixup?1:0 ) );
1366
1367
1368 ITEM* ni = nearest->m_item;
1369
1370 unwindLineStack( ni );
1371
1372 if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1373 {
1374 // Collision with a higher-ranking object (ie: one that we've already shoved)
1375 //
1376 switch( ni->Kind() )
1377 {
1378 case ITEM::VIA_T:
1379 {
1380 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-via", aIter ).ToStdString(), 0 );
1381
1382 if( currentLine.EndsWithVia() && nearest->m_item->Collide( &currentLine.Via(), m_currentNode ) )
1383 {
1384 st = SH_INCOMPLETE;
1385 }
1386 else
1387 {
1388 st = onReverseCollidingVia( currentLine, (VIA*) ni );
1389 }
1390
1391 PNS_DBGN( Dbg(), EndGroup );
1392
1393 break;
1394 }
1395
1396 case ITEM::SEGMENT_T:
1397 {
1398 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-segment ",
1399 aIter ).ToStdString(), 0 );
1400 LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1401
1402 popLineStack();
1403 st = onCollidingLine( revLine, currentLine );
1404
1405
1406 if( !pushLineStack( revLine ) )
1407 {
1408 return SH_INCOMPLETE;
1409 }
1410
1411
1412 PNS_DBGN( Dbg(), EndGroup );
1413
1414 break;
1415 }
1416
1417 case ITEM::ARC_T:
1418 {
1419 //TODO(snh): Handle Arc shove separate from track
1420 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: reverse-collide-arc ", aIter ).ToStdString(), 0 );
1421 LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1422
1423 popLineStack();
1424 st = onCollidingLine( revLine, currentLine );
1425
1426 PNS_DBGN( Dbg(), EndGroup );
1427
1428 if( !pushLineStack( revLine ) )
1429 return SH_INCOMPLETE;
1430
1431 break;
1432 }
1433
1434 default:
1435 assert( false );
1436 }
1437 }
1438 else
1439 {
1440 // Collision with a lower-ranking object or a solid
1441 //
1442 switch( ni->Kind() )
1443 {
1444 case ITEM::SEGMENT_T:
1445 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-segment ", aIter ), 0 );
1446
1447 st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1448
1449 if( st == SH_TRY_WALK )
1450 st = onCollidingSolid( currentLine, ni, *nearest );
1451
1452 PNS_DBGN( Dbg(), EndGroup );
1453
1454 break;
1455
1456 //TODO(snh): Customize Arc collide
1457 case ITEM::ARC_T:
1458 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-arc ", aIter ), 0 );
1459
1460 st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1461
1462 if( st == SH_TRY_WALK )
1463 st = onCollidingSolid( currentLine, ni, *nearest );
1464
1465 PNS_DBGN( Dbg(), EndGroup );
1466
1467 break;
1468
1469 case ITEM::VIA_T:
1470 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: collide-via (fixup: %d)", aIter, 0 ), 0 );
1471 st = onCollidingVia( &currentLine, (VIA*) ni, *nearest );
1472
1473 if( st == SH_TRY_WALK )
1474 st = onCollidingSolid( currentLine, ni, *nearest );
1475
1476 PNS_DBGN( Dbg(), EndGroup );
1477
1478 break;
1479
1480 case ITEM::SOLID_T:
1481 PNS_DBG( Dbg(), BeginGroup, wxString::Format( "iter %d: walk-solid ", aIter ), 0);
1482 st = onCollidingSolid( currentLine, (SOLID*) ni, *nearest );
1483
1484 PNS_DBGN( Dbg(), EndGroup );
1485
1486 break;
1487
1488 default:
1489 break;
1490 }
1491 }
1492
1493 return st;
1494}
virtual void SetIteration(int iter)
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:166
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=nullptr, bool aUseClearanceEpsilon=true)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:301
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:560
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:496
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:618
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:1067
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle, OBSTACLE &aObstacleInfo)
Definition: pns_shove.cpp:658
bool fixupViaCollisions(const LINE *aCurrent, OBSTACLE &obs)
Definition: pns_shove.cpp:1246

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

Referenced by shoveMainLoop().

◆ shoveLineFromLoneVia()

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

Definition at line 226 of file pns_shove.cpp.

228{
229 // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
230
231 int obstacleLineWidth = aObstacleLine.Width();
232 int clearance = getClearance( &aCurLine, &aObstacleLine );
233
234/* int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
235
236 if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
237 clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
238*/
239
240 SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
241 SHAPE_LINE_CHAIN path_cw;
242 SHAPE_LINE_CHAIN path_ccw;
243
244 if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
245 return SH_INCOMPLETE;
246
247 if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
248 return SH_INCOMPLETE;
249
250 const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
251
252 if( shortest.PointCount() < 2 )
253 return SH_INCOMPLETE;
254
255 if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
256 return SH_INCOMPLETE;
257
258 if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
259 return SH_INCOMPLETE;
260
261 aResultLine.SetShape( shortest );
262
263 if( aResultLine.Collide( &aCurLine, m_currentNode ) )
264 return SH_INCOMPLETE;
265
266 return SH_OK;
267}
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
long long int Length() const
Return length of the line chain in Euclidean metric.

References PNS::ITEM::Collide(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), getClearance(), 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 1565 of file pns_shove.cpp.

1566{
1567 SHOVE_STATUS st = SH_OK;
1568
1569 m_multiLineMode = false;
1570
1571 PNS_DBG( Dbg(), Message,
1572 wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) )
1573
1574 // empty head? nothing to shove...
1575 if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1576 return SH_INCOMPLETE;
1577
1578 LINE head( aCurrentHead );
1579 head.ClearLinks();
1580
1581 m_lineStack.clear();
1582 m_optimizerQueue.clear();
1583 m_newHead = OPT_LINE();
1584
1585#if 0
1586 m_logger.Clear();
1587#endif
1588
1589 // Pop NODEs containing previous shoves which are no longer necessary
1590 //
1591 ITEM_SET headSet;
1592 headSet.Add( aCurrentHead );
1593
1594 VIA_HANDLE dummyVia;
1595
1596 NODE* parent = reduceSpringback( headSet, dummyVia );
1597
1598 // Create a new NODE to store this version of the world
1599 m_currentNode = parent->Branch();
1601 m_currentNode->Add( head );
1602
1603 m_currentNode->LockJoint( head.CPoint(0), &head, true );
1604
1605 if( !head.EndsWithVia() )
1606 m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1607
1608 head.Mark( MK_HEAD );
1609 head.SetRank( 100000 );
1610
1611 PNS_DBG( Dbg(), AddItem, &head, CYAN, 0, wxT( "head, after shove" ) );
1612
1613 if( head.EndsWithVia() )
1614 {
1615 std::unique_ptr< VIA >headVia = Clone( head.Via() );
1616 headVia->Mark( MK_HEAD );
1617 headVia->SetRank( 100000 );
1618 m_currentNode->Add( std::move( headVia ) );
1619 }
1620
1621 if( !pushLineStack( head ) )
1622 {
1623 delete m_currentNode;
1624 m_currentNode = parent;
1625
1626 return SH_INCOMPLETE;
1627 }
1628
1629 st = shoveMainLoop();
1630
1631 if( st == SH_OK )
1632 {
1634
1635 if( m_newHead )
1637 else
1639 }
1640
1642
1643 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1644 ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter ) );
1645
1646 if( st == SH_OK || st == SH_HEAD_MODIFIED )
1647 {
1649 }
1650 else
1651 {
1652 delete m_currentNode;
1653
1654 m_currentNode = parent;
1655 m_newHead = OPT_LINE();
1656 }
1657
1658 if(m_newHead)
1659 m_newHead->Unmark();
1660
1661 if( m_newHead && head.EndsWithVia() )
1662 {
1663 VIA v = head.Via();
1664 v.SetPos( m_newHead->CPoint( -1 ) );
1665 m_newHead->AppendVia(v);
1666 }
1667
1668 return st;
1669}
void Clear()
Definition: pns_logger.cpp:40
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1512
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:472
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:664
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1227
@ CYAN
Definition: color4d.h:58

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::Clone(), PNS::LINE::CPoint(), CYAN, PNS::ALGO_BASE::Dbg(), 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::MK_HEAD, PNS_DBG, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::VIA::SetPos(), PNS::LINE::SetRank(), SH_HEAD_MODIFIED, SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

◆ shoveLineToHullSet()

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

Definition at line 273 of file pns_shove.cpp.

275{
276 const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
277
278 int attempt;
279
280 PNS_DBG( Dbg(), BeginGroup, "shove-details", 1 );
281
282 for( attempt = 0; attempt < 4; attempt++ )
283 {
284 bool invertTraversal = ( attempt >= 2 );
285 bool clockwise = attempt % 2;
286 int vFirst = -1, vLast = -1;
287
288 LINE l( aObstacleLine );
289 SHAPE_LINE_CHAIN path( l.CLine() );
290
291 for( int i = 0; i < (int) aHulls.size(); i++ )
292 {
293 const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
294
295 PNS_DBG( Dbg(), AddShape, &hull, YELLOW, 10000, wxString::Format( "hull[%d]", i ) );
296 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path[%d]", i ) );
297 PNS_DBG( Dbg(), AddShape, &obs, LIGHTGRAY, aObstacleLine.Width(), wxString::Format( "obs[%d]", i ) );
298
299 if( !l.Walkaround( hull, path, clockwise ) )
300 {
301 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "Fail-Walk %s %s %d\n" ),
302 hull.Format().c_str(),
303 l.CLine().Format().c_str(),
304 clockwise? 1 : 0) );
305
306 PNS_DBGN( Dbg(), EndGroup );
307 return SH_INCOMPLETE;
308 }
309
310 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path-presimp[%d]", i ) );
311
312 path.Simplify();
313
314 PNS_DBG( Dbg(), AddShape, &path, WHITE, l.Width(), wxString::Format( "path-postsimp[%d]", i ) );
315
316 l.SetShape( path );
317 }
318
319 for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
320 {
321 if( path.CPoint( i ) != obs.CPoint( i ) )
322 {
323 vFirst = i;
324 break;
325 }
326 }
327
328 int k = obs.PointCount() - 1;
329
330 for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
331 {
332 if( path.CPoint( i ) != obs.CPoint( k ) )
333 {
334 vLast = i;
335 break;
336 }
337 }
338
339 if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
340 {
341 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vfirst-last" ),
342 attempt ) );
343 continue;
344 }
345
346 if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
347 {
348 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail vend-start\n" ),
349 attempt ) );
350 continue;
351 }
352
353 if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
354 {
355 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail direction-check" ),
356 attempt ) );
357 aResultLine.SetShape( l.CLine() );
358 continue;
359 }
360
361 if( path.SelfIntersecting() )
362 {
363 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail self-intersect" ),
364 attempt ) );
365 continue;
366 }
367
368 bool colliding = l.Collide( &aCurLine, m_currentNode );
369
370 if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
371 {
372 JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
373
374 for( ITEM* item : jtStart->LinkList() )
375 {
376 if( item->Collide( &l, m_currentNode ) )
377 colliding = true;
378 }
379 }
380
381 if( colliding )
382 {
383 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "attempt %d fail coll-check" ),
384 attempt ) );
385 continue;
386 }
387
388 aResultLine.SetShape( l.CLine() );
389
390 PNS_DBGN( Dbg(), EndGroup );
391
392 return SH_OK;
393 }
394
395 PNS_DBGN( Dbg(), EndGroup );
396
397 return SH_INCOMPLETE;
398}
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:206
const std::string Format(bool aCplusPlus=true) const override
@ LIGHTGRAY
Definition: color4d.h:47

References 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(), Format(), LIGHTGRAY, PNS::JOINT::LinkList(), m_currentNode, PNS::LINE::Marker(), PNS::MK_HEAD, path, PNS_DBG, PNS_DBGN, SHAPE_LINE_CHAIN::PointCount(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, PNS::LINE::Walkaround(), WHITE, PNS::LINE::Width(), and YELLOW.

Referenced by ShoveObstacleLine().

◆ shoveMainLoop()

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

Definition at line 1503 of file pns_shove.cpp.

1504{
1505 SHOVE_STATUS st = SH_OK;
1506
1508
1509 PNS_DBG( Dbg(), Message, wxString::Format( "ShoveStart [root: %d jts, current: %d jts]",
1510 m_root->JointCount(),
1512
1513 int iterLimit = Settings().ShoveIterationLimit();
1514 TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1515
1516 m_iter = 0;
1517
1518 timeLimit.Restart();
1519
1520 if( m_lineStack.empty() && m_draggedVia )
1521 {
1522 // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1523 // the stack.
1525 }
1526
1527 while( !m_lineStack.empty() )
1528 {
1529 PNS_DBG( Dbg(), Message, wxString::Format( "iter %d: node %p stack %d ", m_iter,
1530 m_currentNode, (int) m_lineStack.size() ) );
1531
1532 st = shoveIteration( m_iter );
1533
1534 m_iter++;
1535
1536 if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1537 {
1538 PNS_DBG( Dbg(), Message, wxString::Format( "Fail [time limit expired: %d iter %d iter limit %d",
1539 timeLimit.Expired()?1:0, m_iter, iterLimit ) );
1540 st = SH_INCOMPLETE;
1541 break;
1542 }
1543 }
1544
1545 return st;
1546}
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:203
TIME_LIMIT ShoveTimeLimit() const
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1326

References PNS::ALGO_BASE::Dbg(), PNS::TIME_LIMIT::Expired(), Format(), PNS::NODE::JointCount(), m_affectedArea, m_currentNode, m_draggedVia, m_iter, m_lineStack, m_root, PNS_DBG, 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 1672 of file pns_shove.cpp.

1673{
1674 SHOVE_STATUS st = SH_OK;
1675
1676 m_multiLineMode = true;
1677
1678 ITEM_SET headSet;
1679
1680 for( const ITEM* item : aHeadSet.CItems() )
1681 {
1682 const LINE* headOrig = static_cast<const LINE*>( item );
1683
1684 // empty head? nothing to shove...
1685 if( !headOrig->SegmentCount() )
1686 return SH_INCOMPLETE;
1687
1688 headSet.Add( *headOrig );
1689 }
1690
1691 m_lineStack.clear();
1692 m_optimizerQueue.clear();
1693
1694#if 0
1695 m_logger.Clear();
1696#endif
1697
1698 VIA_HANDLE dummyVia;
1699
1700 NODE* parent = reduceSpringback( headSet, dummyVia );
1701
1702 m_currentNode = parent->Branch();
1704 int n = 0;
1705
1706 for( const ITEM* item : aHeadSet.CItems() )
1707 {
1708 const LINE* headOrig = static_cast<const LINE*>( item );
1709 LINE head( *headOrig );
1710 head.ClearLinks();
1711
1712 m_currentNode->Add( head );
1713
1714 head.Mark( MK_HEAD );
1715 head.SetRank( 100000 );
1716 n++;
1717
1718 if( !pushLineStack( head ) )
1719 return SH_INCOMPLETE;
1720
1721 if( head.EndsWithVia() )
1722 {
1723 std::unique_ptr< VIA > headVia = Clone( head.Via() );
1724 headVia->Mark( MK_HEAD );
1725 headVia->SetRank( 100000 );
1726 m_currentNode->Add( std::move( headVia ) );
1727 }
1728 }
1729
1730 st = shoveMainLoop();
1731
1732 if( st == SH_OK )
1734
1736
1737 PNS_DBG( Dbg(), Message, wxString::Format( "Shove status : %s after %d iterations",
1738 ( st == SH_OK ? "OK" : "FAILURE"), m_iter ) );
1739
1740 if( st == SH_OK )
1741 {
1743 }
1744 else
1745 {
1746 delete m_currentNode;
1747 m_currentNode = parent;
1748 }
1749
1750 return st;
1751}

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::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_optimizerQueue, PNS::LINE::Mark(), PNS::MK_HEAD, PNS_DBG, pushLineStack(), pushSpringback(), reduceSpringback(), PNS::NODE::RemoveByMarker(), runOptimizer(), PNS::LINE::SegmentCount(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, shoveMainLoop(), and PNS::LINE::Via().

◆ ShoveObstacleLine()

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

Definition at line 405 of file pns_shove.cpp.

407{
408 aResultLine.ClearLinks();
409
410 bool obstacleIsHead = false;
411
412 for( LINKED_ITEM* s : aObstacleLine.Links() )
413 {
414 if( s->Marker() & MK_HEAD )
415 {
416 obstacleIsHead = true;
417 break;
418 }
419 }
420
421 SHOVE_STATUS rv;
422 bool viaOnEnd = aCurLine.EndsWithVia();
423
424 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: voe1 %d voe2 %d" ),
425 aCurLine.EndsWithVia()?1:0, aObstacleLine.EndsWithVia()?1:0 ) );
426
427
428 if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
429 {
430 // Shove aObstacleLine to the hull of aCurLine's via.
431
432 rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
433 }
434 else
435 {
436 // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
437 // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
438 // hull it will be at the appropriate clearance.
439
440 int obstacleLineWidth = aObstacleLine.Width();
441 int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
442 int currentLineSegmentCount = aCurLine.SegmentCount();
443 HULL_SET hulls;
444
445 hulls.reserve( currentLineSegmentCount + 1 );
446
447 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove process-single: cur net %d obs %d cl %d" ),
448 aCurLine.Net(), aObstacleLine.Net(), clearance ) );
449
450 for( int i = 0; i < currentLineSegmentCount; i++ )
451 {
452 SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
453 int extra = 0;
454
455 // Arcs need additional clearance to ensure the hulls are always bigger than the arc
456 if( aCurLine.CLine().IsArcSegment( i ) )
458
459 if( extra > 0 )
460 {
461 PNS_DBG( Dbg(), Message, wxString::Format( wxT( "shove add-extra-clearance %d" ),
462 extra ) );
463 }
464
465 SHAPE_LINE_CHAIN hull =
466 seg.Hull( clearance + extra, obstacleLineWidth, aObstacleLine.Layer() );
467
468 hulls.push_back( hull );
469 }
470
471 if( viaOnEnd )
472 {
473 const VIA& via = aCurLine.Via();
474 int viaClearance = getClearance( &via, &aObstacleLine );
475 /*int holeClearance = getHoleClearance( &via, &aObstacleLine );
476
477 if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
478 viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;*/
479
480 hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
481 }
482
483 rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
484 }
485
486 if( obstacleIsHead )
487 aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
488
489 return rv;
490}
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:96
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:273
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:226
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:221

References PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), SHAPE_ARC::DefaultAccuracyForPCB(), PNS::LINE::EndsWithVia(), Format(), getClearance(), PNS::SEGMENT::Hull(), PNS::VIA::Hull(), SHAPE_LINE_CHAIN::IsArcSegment(), PNS::ITEM::Layer(), PNS::ITEM::LayersOverlap(), PNS::LINK_HOLDER::Links(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, PNS::ITEM::Net(), PNS_DBG, PNS::LINE::SegmentCount(), shoveLineFromLoneVia(), shoveLineToHullSet(), via, PNS::LINE::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 1549 of file pns_shove.cpp.

1550{
1551 OPT_BOX2I area;
1552
1553 if( !m_nodeStack.empty() )
1554 area = m_nodeStack.back().m_affectedArea;
1555
1556 if( area && m_affectedArea)
1557 area->Merge( *m_affectedArea );
1558 else if( !area )
1559 area = m_affectedArea;
1560
1561 return area;
1562}

References m_affectedArea, and m_nodeStack.

Referenced by runOptimizer().

◆ UnlockSpringbackNode()

void PNS::SHOVE::UnlockSpringbackNode ( NODE aNode)

Definition at line 2025 of file pns_shove.cpp.

2026{
2027 auto iter = m_nodeStack.begin();
2028
2029 while( iter != m_nodeStack.end() )
2030 {
2031 if ( iter->m_node == aNode )
2032 {
2033 iter->m_locked = false;
2034 break;
2035 }
2036
2037 iter++;
2038 }
2039}

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

Definition at line 1182 of file pns_shove.cpp.

1183{
1184 if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1185 unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1186 else if( aItem->OfKind( ITEM::LINE_T ) )
1187 {
1188 LINE* l = static_cast<LINE*>( aItem );
1189
1190 for( LINKED_ITEM* seg : l->Links() )
1191 unwindLineStack( seg );
1192 }
1193}

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

◆ unwindLineStack() [2/2]

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

Definition at line 1155 of file pns_shove.cpp.

1156{
1157 int d = 0;
1158
1159 for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1160 {
1161 if( i->ContainsLink( aSeg ) )
1162 {
1163 PNS_DBG(Dbg(), Message, wxString::Format("Unwind lc %d (depth %d/%d)", i->SegmentCount(), d, (int)m_lineStack.size() ) );
1164 i = m_lineStack.erase( i );
1165 }
1166 else
1167 i++;
1168
1169 d++;
1170 }
1171
1172 for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1173 {
1174 if( i->ContainsLink( aSeg ) )
1175 i = m_optimizerQueue.erase( i );
1176 else
1177 i++;
1178 }
1179}

References PNS::ALGO_BASE::Dbg(), Format(), m_lineStack, m_optimizerQueue, and PNS_DBG.

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

◆ VisibleViewArea()

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

Definition at line 40 of file pns_algo_base.cpp.

41{
42 return m_router->VisibleViewArea();
43}
const BOX2I & VisibleViewArea() const
Definition: pns_router.h:217

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

◆ m_currentNode

◆ 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 181 of file pns_shove.h.

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

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

Definition at line 184 of file pns_shove.h.

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

◆ m_iter

int PNS::SHOVE::m_iter
private

Definition at line 183 of file pns_shove.h.

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

◆ m_lineStack

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

◆ m_logger

LOGGER PNS::SHOVE::m_logger
private

Definition at line 180 of file pns_shove.h.

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

◆ m_multiLineMode

bool PNS::SHOVE::m_multiLineMode
private

◆ m_newHead

◆ m_nodeStack

◆ m_optFlagDisableMask

int PNS::SHOVE::m_optFlagDisableMask
private

Definition at line 187 of file pns_shove.h.

Referenced by DisablePostShoveOptimizations(), runOptimizer(), and SHOVE().

◆ m_optimizerQueue

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

◆ m_restrictSpringbackTagId

int PNS::SHOVE::m_restrictSpringbackTagId
private

Definition at line 176 of file pns_shove.h.

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 173 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 171 of file pns_shove.h.

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

◆ m_router

◆ m_springbackDoNotTouchNode

NODE* PNS::SHOVE::m_springbackDoNotTouchNode
private

Definition at line 175 of file pns_shove.h.

Referenced by reduceSpringback(), SetSpringbackDoNotTouchNode(), and SHOVE().


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