KiCad PCB EDA Suite
PNS::SHOVE Class Reference

SHOVE. 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)
 
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 OPT< 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)
 
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)
 
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
 
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
 
int m_restrictSpringbackTagId
 
OPT_LINE m_newHead
 
LOGGER m_logger
 
VIAm_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

Enumerator
SH_OK 
SH_NULL 
SH_INCOMPLETE 
SH_HEAD_MODIFIED 
SH_TRY_WALK 

Definition at line 52 of file pns_shove.h.

Constructor & Destructor Documentation

◆ SHOVE()

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

Definition at line 149 of file pns_shove.cpp.

149  :
150  ALGO_BASE( aRouter )
151 {
152  m_forceClearance = -1;
153  m_root = aWorld;
154  m_currentNode = aWorld;
155  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
156 
157  // Initialize other temporary variables:
158  m_draggedVia = NULL;
159  m_iter = 0;
160  m_multiLineMode = false;
162 }
int m_restrictSpringbackTagId
Definition: pns_shove.h:169
NODE * m_root
Definition: pns_shove.h:167
#define NULL
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:45
VIA * m_draggedVia
Definition: pns_shove.h:174
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
bool m_multiLineMode
Definition: pns_shove.h:178
NODE * m_currentNode
Definition: pns_shove.h:168
int m_iter
Definition: pns_shove.h:176
int m_forceClearance
Definition: pns_shove.h:177

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.

166 {
167  std::unordered_set<LINE*> alreadyDeleted;
168  for( auto it : m_rootLineHistory )
169  {
170  auto it2 = alreadyDeleted.find( it.second );
171  if( it2 == alreadyDeleted.end() )
172  {
173  alreadyDeleted.insert( it.second );
174  delete it.second;
175  }
176  }
177 }
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:165

References m_rootLineHistory.

Member Function Documentation

◆ AddLockedSpringbackNode()

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

Definition at line 1761 of file pns_shove.cpp.

1762 {
1763  SPRINGBACK_TAG sp;
1764  sp.m_node = aNode;
1765  sp.m_locked = true;
1766 
1767  m_nodeStack.push_back(sp);
1768  return true;
1769 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162

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.

181 {
182  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
183 }
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Follow the joint map to assemble a line connecting two non-trivial joints starting from segment aSeg.
Definition: pns_node.cpp:907
NODE * m_currentNode
Definition: pns_shove.h:168

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.

195 {
196  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
197  checker.AddPolyline( aObstacleLine.CLine() );
198  checker.AddPolyline( aShovedLine.CLine().Reverse() );
199 
200  bool inside = checker.IsInside();
201 
202  return !inside;
203 }
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)

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.

1741 {
1742  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1743 }
NODE * m_root
Definition: pns_shove.h:167
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162

References m_nodeStack, and m_root.

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

◆ Dbg()

◆ findRootLine()

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

Definition at line 1639 of file pns_shove.cpp.

1640 {
1641  for( auto link : aLine->Links() )
1642  {
1643  if( auto seg = dyn_cast<SEGMENT*>( link ) )
1644  {
1645  auto it = m_rootLineHistory.find( seg );
1646 
1647  if( it != m_rootLineHistory.end() )
1648  return it->second;
1649  }
1650  }
1651 
1652  return nullptr;
1653 }
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:165

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.

76  {
77  if( aEnabled )
78  m_forceClearance = aClearance;
79  else
80  m_forceClearance = -1;
81  }
int m_forceClearance
Definition: pns_shove.h:177

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.

126 {
127  if( m_forceClearance >= 0 )
128  return m_forceClearance;
129 
130  return m_currentNode->GetClearance( aA, aB );
131 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:97
NODE * m_currentNode
Definition: pns_shove.h:168
int m_forceClearance
Definition: pns_shove.h:177

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.

134 {
135  if( m_forceClearance >= 0 )
136  return m_forceClearance;
137 
138  return m_currentNode->GetHoleClearance( aA, aB );
139 }
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:106
NODE * m_currentNode
Definition: pns_shove.h:168
int m_forceClearance
Definition: pns_shove.h:177

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.

65  {
66  return &m_logger;
67  }
LOGGER m_logger
Definition: pns_shove.h:173

References m_logger.

◆ NewHead()

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

Definition at line 1746 of file pns_shove.cpp.

1747 {
1748  assert( m_newHead );
1749 
1750  return *m_newHead;
1751 }
OPT_LINE m_newHead
Definition: pns_shove.h:171

References m_newHead.

◆ onCollidingArc()

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

Definition at line 522 of file pns_shove.cpp.

523 {
524  int segIndex;
525  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
526  LINE shovedLine( obstacleLine );
527  ARC tmp( *aObstacleArc );
528 
529  if( obstacleLine.HasLockedSegments() )
530  return SH_TRY_WALK;
531 
532  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
533 
534  const double extensionWalkThreshold = 1.0;
535 
536  double obsLen = obstacleLine.CLine().Length();
537  double shovedLen = shovedLine.CLine().Length();
538  double extensionFactor = 0.0;
539 
540  if( obsLen != 0.0f )
541  extensionFactor = shovedLen / obsLen - 1.0;
542 
543  if( extensionFactor > extensionWalkThreshold )
544  return SH_TRY_WALK;
545 
546  assert( obstacleLine.LayersOverlap( &shovedLine ) );
547 
548  if ( Dbg() )
549  {
550  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
551  Dbg()->AddLine( tmp.CLine(), 0, 10000, "obstacle-segment" );
552  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
553  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
554  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
555  Dbg()->EndGroup();
556  }
557 
558  if( rv == SH_OK )
559  {
560  if( shovedLine.Marker() & MK_HEAD )
561  {
562  if( m_multiLineMode )
563  return SH_INCOMPLETE;
564 
565  m_newHead = shovedLine;
566  }
567 
568  int rank = aCurrent.Rank();
569  shovedLine.SetRank( rank - 1 );
570 
571  sanityCheck( &obstacleLine, &shovedLine );
572  replaceLine( obstacleLine, shovedLine );
573 
574  if( !pushLineStack( shovedLine ) )
575  rv = SH_INCOMPLETE;
576  }
577 
578  return rv;
579 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:180
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:371
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:142
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
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
virtual void BeginGroup(const std::string name)
Definition: track.h:262
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171
int m_iter
Definition: pns_shove.h:176

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.

586 {
587  LINE shovedLine( aObstacle );
588 
589  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
590 
591  Dbg()->BeginGroup( "on-colliding-line" );
592  Dbg()->AddLine( aObstacle.CLine(), 1, 100000, "obstacle-line" );
593  Dbg()->AddLine( aCurrent.CLine(), 2, 150000, "current-line" );
594  Dbg()->AddLine( shovedLine.CLine(), 3, 200000, "shoved-line" );
595 
596  if( rv == SH_OK )
597  {
598  if( shovedLine.Marker() & MK_HEAD )
599  {
600  if( m_multiLineMode )
601  return SH_INCOMPLETE;
602 
603  m_newHead = shovedLine;
604  }
605 
606  sanityCheck( &aObstacle, &shovedLine );
607  replaceLine( aObstacle, shovedLine );
608 
609  int rank = aObstacle.Rank();
610  shovedLine.SetRank( rank - 1 );
611 
612 
613  if( !pushLineStack( shovedLine ) )
614  {
615  rv = SH_INCOMPLETE;
616  }
617  }
618 
619  return rv;
620 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:371
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:142
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
virtual void BeginGroup(const std::string name)
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171

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.

456 {
457  int segIndex;
458  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
459  LINE shovedLine( obstacleLine );
460  SEGMENT tmp( *aObstacleSeg );
461 
462  if( obstacleLine.HasLockedSegments() )
463  return SH_TRY_WALK;
464 
465  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
466 
467  const double extensionWalkThreshold = 1.0;
468 
469  double obsLen = obstacleLine.CLine().Length();
470  double shovedLen = shovedLine.CLine().Length();
471  double extensionFactor = 0.0;
472 
473  if( obsLen != 0.0f )
474  extensionFactor = shovedLen / obsLen - 1.0;
475 
476  if( extensionFactor > extensionWalkThreshold )
477  return SH_TRY_WALK;
478 
479  assert( obstacleLine.LayersOverlap( &shovedLine ) );
480 
481  if( Dbg() )
482  {
483  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d", m_iter ).ToStdString() );
484  Dbg()->AddSegment( tmp.Seg(), 0, "obstacle-segment" );
485  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
486  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
487  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
488  if( rv == SH_OK )
489  Dbg()->Message("Shove success");
490  else
491  Dbg()->Message("Shove FAIL");
492  Dbg()->EndGroup();
493  }
494 
495  if( rv == SH_OK )
496  {
497  if( shovedLine.Marker() & MK_HEAD )
498  {
499  if( m_multiLineMode )
500  return SH_INCOMPLETE;
501 
502  m_newHead = shovedLine;
503  }
504 
505  int rank = aCurrent.Rank();
506  shovedLine.SetRank( rank - 1 );
507 
508  sanityCheck( &obstacleLine, &shovedLine );
509  replaceLine( obstacleLine, shovedLine );
510 
511  if( !pushLineStack( shovedLine ) )
512  rv = SH_INCOMPLETE;
513  }
514 
515  return rv;
516 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:180
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:371
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:142
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
virtual void AddSegment(SEG aS, int aColor, const std::string aName="")
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
virtual void Message(const wxString msg)
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
virtual void BeginGroup(const std::string name)
usual segment : line with rounded ends
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171
int m_iter
Definition: pns_shove.h:176

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.

627 {
628  WALKAROUND walkaround( m_currentNode, Router() );
629  LINE walkaroundLine( aCurrent );
630 
631  if( aCurrent.EndsWithVia() )
632  {
633  VIA vh = aCurrent.Via();
634  VIA* via = NULL;
635  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
636 
637  if( !jtStart )
638  return SH_INCOMPLETE;
639 
640  for( ITEM* item : jtStart->LinkList() )
641  {
642  if( item->OfKind( ITEM::VIA_T ) )
643  {
644  via = (VIA*) item;
645  break;
646  }
647  }
648 
649  if( via && via->Collide( aObstacle, m_currentNode ) )
650  return onCollidingVia( aObstacle, via );
651  }
652 
653  TOPOLOGY topo( m_currentNode );
654 
655  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
656 
657  walkaround.SetSolidsOnly( false );
658  walkaround.RestrictToSet( true, cluster );
659  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
660 
661  int currentRank = aCurrent.Rank();
662  int nextRank;
663 
664  bool success = false;
665 
666  for( int attempt = 0; attempt < 2; attempt++ )
667  {
668  if( attempt == 1 || Settings().JumpOverObstacles() )
669  {
670 
671  nextRank = currentRank - 1;
672  walkaround.SetSingleDirection( true );
673  }
674  else
675  {
676  nextRank = currentRank + 10000;
677  walkaround.SetSingleDirection( false );
678  }
679 
680 
681  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
682 
683  if( status != WALKAROUND::DONE )
684  continue;
685 
686  walkaroundLine.ClearLinks();
687  walkaroundLine.Unmark();
688  walkaroundLine.Line().Simplify();
689 
690  if( walkaroundLine.HasLoops() )
691  continue;
692 
693  if( aCurrent.Marker() & MK_HEAD )
694  {
695  walkaroundLine.Mark( MK_HEAD );
696 
697  if( m_multiLineMode )
698  continue;
699 
700  m_newHead = walkaroundLine;
701  }
702 
703  sanityCheck( &aCurrent, &walkaroundLine );
704 
705  if( !m_lineStack.empty() )
706  {
707  LINE lastLine = m_lineStack.front();
708 
709  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
710  {
711  LINE dummy( lastLine );
712 
713  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
714  {
715  success = true;
716  break;
717  }
718  } else {
719  success = true;
720  break;
721  }
722  }
723  }
724 
725  if(!success)
726  return SH_INCOMPLETE;
727 
728  replaceLine( aCurrent, walkaroundLine );
729  walkaroundLine.SetRank( nextRank );
730 
731  if( Dbg() )
732  {
733  Dbg()->BeginGroup( "on-colliding-solid" );
734  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
735  Dbg()->AddLine( walkaroundLine.CLine(), 3, 10000, "walk-line" );
736  Dbg()->EndGroup();
737  }
738 
739  popLineStack();
740 
741  if( !pushLineStack( walkaroundLine ) )
742  return SH_INCOMPLETE;
743 
744  return SH_OK;
745 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
Definition: track.h:343
void popLineStack()
Definition: pns_shove.cpp:1132
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
Definition: sch_symbol.cpp:69
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:371
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:944
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:142
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
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:1041
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
virtual void BeginGroup(const std::string name)
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168

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.

945 {
946  int clearance = getClearance( aCurrent, aObstacleVia );
947  VECTOR2I mtv;
948  int rank = -1;
949 
950  bool lineCollision = false;
951  bool viaCollision = false;
952  VECTOR2I mtvLine, mtvVia;
953 
954 
955  if( aCurrent->OfKind( ITEM::LINE_T ) )
956  {
957  LINE* currentLine = (LINE*) aCurrent;
958 
959 #if 0
960  m_logger.NewGroup( "push-via-by-line", m_iter );
961  m_logger.Log( currentLine, 4, "current" );
962 #endif
963 
964  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(), clearance + currentLine->Width() / 2, &mtvLine );
965 
966  // Check the via if present. Via takes priority.
967  if( currentLine->EndsWithVia() )
968  {
969  const VIA& currentVia = currentLine->Via();
970  int viaClearance = getClearance( &currentVia, aObstacleVia );
971 
972  viaCollision = aObstacleVia->Shape()->Collide( currentVia.Shape(), viaClearance, &mtvVia );
973  }
974  }
975  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
976  {
977  // TODO: is this possible at all? We don't shove solids.
978  return SH_INCOMPLETE;
979  }
980 
981  // fixme: we may have a sign issue in Collide(CIRCLE, LINE_CHAIN)
982  if( viaCollision )
983  mtv = mtvVia;
984  else if ( lineCollision )
985  mtv = -mtvLine;
986  else
987  mtv = VECTOR2I(0, 0);
988 
989  return pushOrShoveVia( aObstacleVia, -mtv, rank );
990 }
Definition: track.h:343
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:817
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:125
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:65
LOGGER m_logger
Definition: pns_shove.h:173
int m_iter
Definition: pns_shove.h:176

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.

997 {
998  int n = 0;
999  LINE cur( aCurrent );
1000  cur.ClearLinks();
1001 
1002  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
1003  LINE shoved( aCurrent );
1004  shoved.ClearLinks();
1005 
1006  cur.RemoveVia();
1007  unwindLineStack( &aCurrent );
1008 
1009  for( ITEM* item : jt->LinkList() )
1010  {
1011  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
1012  {
1013  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
1014  LINE head = assembleLine( li );
1015 
1016  head.AppendVia( *aObstacleVia );
1017 
1018  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
1019 
1020  if( st != SH_OK )
1021  {
1022 #if 0
1023  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
1024  m_logger.Log( aObstacleVia, 0, "the-via" );
1025  m_logger.Log( &aCurrent, 1, "current-line" );
1026  m_logger.Log( &shoved, 3, "shoved-line" );
1027 #endif
1028 
1029  return st;
1030  }
1031 
1032  cur.SetShape( shoved.CLine() );
1033  n++;
1034  }
1035  }
1036 
1037  if( !n )
1038  {
1039 #if 0
1040  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
1041  m_logger.Log( aObstacleVia, 0, "the-via" );
1042  m_logger.Log( &aCurrent, 1, "current-line" );
1043 #endif
1044 
1045  LINE head( aCurrent );
1046  head.Line().Clear();
1047  head.AppendVia( *aObstacleVia );
1048  head.ClearLinks();
1049 
1050  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
1051 
1052  if( st != SH_OK )
1053  return st;
1054 
1055  cur.SetShape( shoved.CLine() );
1056  }
1057 
1058  if( aCurrent.EndsWithVia() )
1059  shoved.AppendVia( aCurrent.Via() );
1060 
1061 #if 0
1062  m_logger.NewGroup( "on-reverse-via", m_iter );
1063  m_logger.Log( aObstacleVia, 0, "the-via" );
1064  m_logger.Log( &aCurrent, 1, "current-line" );
1065  m_logger.Log( &shoved, 3, "shoved-line" );
1066 #endif
1067  int currentRank = aCurrent.Rank();
1068  replaceLine( aCurrent, shoved );
1069 
1070  if( !pushLineStack( shoved ) )
1071  return SH_INCOMPLETE;
1072 
1073  shoved.SetRank( currentRank );
1074 
1075  return SH_OK;
1076 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:180
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1079
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:371
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:1041
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
NODE * m_currentNode
Definition: pns_shove.h:168
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:65
LOGGER m_logger
Definition: pns_shove.h:173
int m_iter
Definition: pns_shove.h:176

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.

1133 {
1134  LINE& l = m_lineStack.back();
1135 
1136  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1137  {
1138  bool found = false;
1139 
1140  for( LINKED_ITEM* s : l.Links() )
1141  {
1142  if( i->ContainsLink( s ) )
1143  {
1144  i = m_optimizerQueue.erase( i );
1145  found = true;
1146  break;
1147  }
1148  }
1149 
1150  if( !found )
1151  i++;
1152  }
1153 
1154  m_lineStack.pop_back();
1155 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163

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.

1114 {
1115  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1116  return false;
1117 
1118  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1119  {
1120  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1121  }
1122  else
1123  {
1124  m_lineStack.push_back( aL );
1125  }
1126 
1127  m_optimizerQueue.push_back( aL );
1128 
1129  return true;
1130 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163

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.

818 {
819  LINE_PAIR_VEC draggedLines;
820  VECTOR2I p0( aVia->Pos() );
821  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
822  VECTOR2I p0_pushed( p0 + aForce );
823 
824  // nothing to do...
825  if ( aForce.x == 0 && aForce.y == 0 )
826  return SH_OK;
827 
828  if( !jt )
829  {
830  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
831  return SH_INCOMPLETE;
832  }
833 
834  if( aVia->IsLocked() )
835  return SH_TRY_WALK;
836 
837  if( jt->IsLocked() )
838  return SH_INCOMPLETE;
839 
840  // make sure pushed via does not overlap with any existing joint
841  while( true )
842  {
843  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
844 
845  if( !jt_next )
846  break;
847 
848  p0_pushed += aForce.Resize( 2 );
849  }
850 
851  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
852  pushedVia->SetPos( p0_pushed );
853  pushedVia->Mark( aVia->Marker() );
854 
855  for( ITEM* item : jt->LinkList() )
856  {
857  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
858  {
859  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
860  LINE_PAIR lp;
861  int segIndex;
862 
863  lp.first = assembleLine( li, &segIndex );
864 
865  if( lp.first.HasLockedSegments() )
866  return SH_TRY_WALK;
867 
868  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
869 
870  if( segIndex == 0 )
871  lp.first.Reverse();
872 
873  lp.second = lp.first;
874  lp.second.ClearLinks();
875  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
876  lp.second.AppendVia( *pushedVia );
877  draggedLines.push_back( lp );
878  }
879  }
880 
881 #if 0
882  m_logger.Log( aVia, 0, "obstacle-via" );
883 #endif
884 
885  pushedVia->SetRank( aCurrentRank - 1 );
886 
887 #if 0
888  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
889 #endif
890 
891  if( aVia->Marker() & MK_HEAD ) // push
892  {
893  m_draggedVia = pushedVia.get();
894  }
895  else
896  { // shove
897  if( jt->IsStitchingVia() )
898  pushLineStack( LINE( *pushedVia ) );
899  }
900 
901  replaceItems( aVia, std::move( pushedVia ) );
902 
903  for( LINE_PAIR lp : draggedLines )
904  {
905  if( lp.first.Marker() & MK_HEAD )
906  {
907  lp.second.Mark( MK_HEAD );
908 
909  if( m_multiLineMode )
910  return SH_INCOMPLETE;
911 
912  m_newHead = lp.second;
913  }
914 
915  unwindLineStack( &lp.first );
916 
917  if( lp.second.SegmentCount() )
918  {
919  replaceLine( lp.first, lp.second );
920  lp.second.SetRank( aCurrentRank - 1 );
921 
922  if( !pushLineStack( lp.second, true ) )
923  return SH_INCOMPLETE;
924  }
925  else
926  {
927  m_currentNode->Remove( lp.first );
928  }
929 
930 #if 0
931  m_logger.Log( &lp.first, 2, "fan-pre" );
932  m_logger.Log( &lp.second, 3, "fan-post" );
933 #endif
934  }
935 
936  return SH_OK;
937 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:180
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1079
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:797
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
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:1041
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
virtual bool IsLocked() const
Definition: board_item.h:249
VIA * m_draggedVia
Definition: pns_shove.h:174
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:49
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171
NODE * m_currentNode
Definition: pns_shove.h:168
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:65
LOGGER m_logger
Definition: pns_shove.h:173

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.

781 {
782  SPRINGBACK_TAG st;
783  OPT_BOX2I prev_area;
784 
785  if( !m_nodeStack.empty() )
786  prev_area = m_nodeStack.back().m_affectedArea;
787 
788  if( aDraggedVia )
789  {
790  st.m_draggedVia = aDraggedVia->MakeHandle();
791  }
792 
793  st.m_node = aNode;
794 
795  if( aAffectedArea )
796  {
797  if( prev_area )
798  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
799  else
800  st.m_affectedArea = aAffectedArea;
801  } else
802  st.m_affectedArea = prev_area;
803 
804  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
805  st.m_locked = false;
806 
807  m_nodeStack.push_back( st );
808 
809  return true;
810 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525

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.

753 {
754  while( !m_nodeStack.empty() )
755  {
756  SPRINGBACK_TAG& spTag = m_nodeStack.back();
757 
758  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
759 
760  if( !obs && !spTag.m_locked )
761  {
762  aDraggedVia = spTag.m_draggedVia;
763  aDraggedVia.valid = true;
764 
765  delete spTag.m_node;
766  m_nodeStack.pop_back();
767  }
768  else
769  break;
770  }
771 
772  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
773 }
NODE * m_root
Definition: pns_shove.h:167
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162
boost::optional< T > OPT
Definition: optional.h:7

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.

50 {
51  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
52 
53  if( changed_area )
54  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
55 
56  m_currentNode->Replace( aOld, std::move( aNew ) );
57 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:299
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:762
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:168

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.

60 {
61  if( aIncludeInChangedArea )
62  {
63  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
64 
65  if( changed_area )
66  {
67  if( Dbg() )
68  {
69  Dbg()->AddBox( *changed_area, 3, "shove-changed-area" );
70  }
71 
72  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
73  }
74  }
75 
76  bool foundPredecessor = false;
77  LINE* rootLine = nullptr;
78 
79  // Keep track of the 'root lines', i.e. the unmodified (pre-shove) versions
80  // of the affected tracks in a map. The optimizer can then query the pre-shove shape
81  // for each shoved line and perform additional constraint checks (i.e. prevent overzealous optimizations)
82 
83  // Check if the shoved line already has an ancestor (e.g. line from a previous shove iteration/cursor movement)
84  for( auto link : aOld.Links() )
85  {
86  auto oldLineIter = m_rootLineHistory.find( link );
87  if( oldLineIter != m_rootLineHistory.end() )
88  {
89  rootLine = oldLineIter->second;
90  foundPredecessor = true;
91  break;
92  }
93  }
94 
95  // If found, use it, otherwise, create new entry in the map (we have a genuine new 'root' line)
96  if( !foundPredecessor )
97  {
98  for( auto link : aOld.Links() )
99  {
100  if( ! rootLine )
101  {
102  rootLine = aOld.Clone();
103  }
104  m_rootLineHistory[link] = rootLine;
105  }
106  }
107 
108  // Now update the NODE (calling Replace invalidates the Links() in a LINE)
109  if( aNode )
110  {
111  aNode->Replace( aOld, aNew );
112  }
113  else
114  {
115  m_currentNode->Replace( aOld, aNew );
116  }
117 
118  // point the Links() of the new line to its oldest ancestor
119  for( auto link : aNew.Links() )
120  {
121  m_rootLineHistory[ link ] = rootLine;
122  }
123 }
virtual void AddBox(BOX2I aB, int aColor, const std::string aName="")
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:299
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
std::unordered_map< const LINKED_ITEM *, LINE * > m_rootLineHistory
Definition: pns_shove.h:165
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:762
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:168

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.

1773 {
1774  bool found = false;
1775 
1776  auto iter = m_nodeStack.begin();
1777 
1778  while( iter != m_nodeStack.end() )
1779  {
1780  if ( iter->m_node == aNode )
1781  {
1782  found = true;
1783  break;
1784  }
1785  iter++;
1786  }
1787 
1788  if( !found )
1789  return false;
1790 
1791  auto start = iter;
1792 
1793  aNode->KillChildren();
1794  m_nodeStack.erase( start, m_nodeStack.end() );
1795 
1796  return true;
1797 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162

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

◆ Router()

◆ runOptimizer()

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

Definition at line 1656 of file pns_shove.cpp.

1657 {
1658  OPTIMIZER optimizer( aNode );
1659  int optFlags = 0;
1660  int n_passes = 0;
1661 
1663 
1664  OPT_BOX2I area = totalAffectedArea();
1665 
1666  int maxWidth = 0;
1667 
1668  for( LINE& line : m_optimizerQueue )
1669  maxWidth = std::max( line.Width(), maxWidth );
1670 
1671  if( area )
1672  {
1673  area->Inflate( maxWidth );
1674  area = area->Intersect( VisibleViewArea() );
1675  }
1676 
1677  switch( effort )
1678  {
1679  case OE_LOW:
1680  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1681  n_passes = 1;
1682  break;
1683 
1684  case OE_MEDIUM:
1685  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1686 
1687  n_passes = 2;
1688  break;
1689 
1690  case OE_FULL:
1691  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1692  n_passes = 2;
1693  break;
1694 
1695  default:
1696  break;
1697  }
1698 
1699  optFlags |= OPTIMIZER::LIMIT_CORNER_COUNT;
1700 
1701  if( area )
1702  {
1703  if( Dbg() )
1704  {
1705  Dbg()->AddBox( *area, 1, "opt-area" );
1706  }
1707 
1708  optFlags |= OPTIMIZER::RESTRICT_AREA;
1709  optimizer.SetRestrictArea( *area, false );
1710  }
1711 
1712  if( Settings().SmartPads() )
1713  optFlags |= OPTIMIZER::SMART_PADS;
1714 
1715  optimizer.SetEffortLevel( optFlags );
1716  optimizer.SetCollisionMask( ITEM::ANY_T );
1717 
1718  for( int pass = 0; pass < n_passes; pass++ )
1719  {
1720  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1721 
1722  for( LINE& line : m_optimizerQueue)
1723  {
1724  if( !( line.Marker() & MK_HEAD ) )
1725  {
1726  LINE optimized;
1727  LINE* root = findRootLine( &line );
1728 
1729  if( optimizer.Optimize( &line, &optimized, root ) )
1730  {
1731  replaceLine( line, optimized, false, aNode );
1732  line = optimized; // keep links in the lines in the queue up to date
1733  }
1734  }
1735  }
1736  }
1737 }
LINE * findRootLine(LINE *aLine)
Definition: pns_shove.cpp:1639
virtual void AddBox(BOX2I aB, int aColor, const std::string aName="")
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1338
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Set the optimizer effort. Bigger means cleaner traces, but slower routing.
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
void replaceLine(LINE &aOld, LINE &aNew, bool aIncludeInChangedArea=true, NODE *aNode=nullptr)
Definition: pns_shove.cpp:59
const BOX2I & VisibleViewArea() const
Reduce corner cost by merging obtuse segments.
Do not attempt to optimize if the resulting line's corner count is outside the predefined range.
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
Reroute pad exits.

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.

143 {
144  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
145  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
146 }

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  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:86

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.

1755 {
1756  m_root = m_root->Branch();
1757  m_root->Remove( aInitial );
1758 }
NODE * m_root
Definition: pns_shove.h:167
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:797

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::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), and PNS::DRAGGER::tryWalkaround().

◆ Settings()

◆ 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.

1570 {
1571  SHOVE_STATUS st = SH_OK;
1572 
1573  m_lineStack.clear();
1574  m_optimizerQueue.clear();
1575  m_newHead = OPT_LINE();
1576  m_draggedVia = NULL;
1577 
1578  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1579 
1580  if( !viaToDrag )
1581  return SH_INCOMPLETE;
1582 
1583  // Pop NODEs containing previous shoves which are no longer necessary
1584  ITEM_SET headSet;
1585 
1586  VIA headVia ( *viaToDrag );
1587  headVia.SetPos( aWhere );
1588  headSet.Add( headVia );
1589  VIA_HANDLE prevViaHandle;
1590  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1591 
1592  if( prevViaHandle.valid )
1593  {
1594  aNewVia = prevViaHandle;
1595  viaToDrag = findViaByHandle( parent, prevViaHandle );
1596  }
1597 
1598  // Create a new NODE to store this version of the world
1599  //
1600  m_currentNode = parent->Branch();
1602 
1603  viaToDrag->Mark( MK_HEAD );
1604  viaToDrag->SetRank( 100000 );
1605 
1606  // Push the via to its new location
1607  //
1608  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1609 
1610  // Shove any colliding objects out of the way
1611  //
1612  if( st == SH_OK )
1613  st = shoveMainLoop();
1614 
1615  if( st == SH_OK )
1617 
1618  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1619  {
1620  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1621 
1622  if (!m_draggedVia)
1623  m_draggedVia = viaToDrag;
1624 
1625  aNewVia = m_draggedVia->MakeHandle();
1626 
1628  }
1629  else
1630  {
1631  delete m_currentNode;
1632  m_currentNode = parent;
1633  }
1634 
1635  return st;
1636 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1341
Definition: track.h:343
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:120
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:817
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:752
#define NULL
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1656
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1550
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:780
VIA * m_draggedVia
Definition: pns_shove.h:174
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1298
OPT_LINE m_newHead
Definition: pns_shove.h:171
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168

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.

1162 {
1163  LINE currentLine = m_lineStack.back();
1164  NODE::OPT_OBSTACLE nearest;
1165  SHOVE_STATUS st = SH_NULL;
1166 
1167 #ifdef DEBUG
1168  Dbg()->SetIteration( aIter );
1169 #endif
1170 
1171  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1172  {
1173  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1174 
1175  if( nearest )
1176  break;
1177  }
1178 
1179  if( !nearest )
1180  {
1181  m_lineStack.pop_back();
1182  return SH_OK;
1183  }
1184 
1185  ITEM* ni = nearest->m_item;
1186 
1187  unwindLineStack( ni );
1188 
1189  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1190  {
1191  // Collision with a higher-ranking object (ie: one that we've already shoved)
1192  //
1193  switch( ni->Kind() )
1194  {
1195  case ITEM::VIA_T:
1196  {
1197  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1198 
1199  if( currentLine.EndsWithVia() )
1200  {
1201  st = SH_INCOMPLETE;
1202  }
1203  else
1204  {
1205  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1206  }
1207 
1208  break;
1209  }
1210 
1211  case ITEM::SEGMENT_T:
1212  {
1213  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1214  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1215 
1216  popLineStack();
1217  st = onCollidingLine( revLine, currentLine );
1218  if( !pushLineStack( revLine ) )
1219  return SH_INCOMPLETE;
1220 
1221  break;
1222  }
1223 
1224  case ITEM::ARC_T:
1225  {
1226  //TODO(snh): Handle Arc shove separate from track
1227  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1228  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1229 
1230  popLineStack();
1231  st = onCollidingLine( revLine, currentLine );
1232  if( !pushLineStack( revLine ) )
1233  return SH_INCOMPLETE;
1234 
1235  break;
1236  }
1237 
1238  default:
1239  assert( false );
1240  }
1241  }
1242  else
1243  {
1244  // Collision with a lower-ranking object or a solid
1245  //
1246  switch( ni->Kind() )
1247  {
1248  case ITEM::SEGMENT_T:
1249  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1250 
1251  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1252 
1253  if( st == SH_TRY_WALK )
1254  st = onCollidingSolid( currentLine, ni );
1255 
1256  break;
1257 
1258  //TODO(snh): Customize Arc collide
1259  case ITEM::ARC_T:
1260  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1261 
1262  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1263 
1264  if( st == SH_TRY_WALK )
1265  st = onCollidingSolid( currentLine, ni );
1266 
1267  break;
1268 
1269  case ITEM::VIA_T:
1270  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1271  st = onCollidingVia( &currentLine, (VIA*) ni );
1272 
1273  if( st == SH_TRY_WALK )
1274  st = onCollidingSolid( currentLine, ni );
1275 
1276  break;
1277 
1278  case ITEM::SOLID_T:
1279  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1280  st = onCollidingSolid( currentLine, (SOLID*) ni );
1281  break;
1282 
1283  default:
1284  break;
1285  }
1286  }
1287 
1288  return st;
1289 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
virtual void SetIteration(int iter)
OPT_OBSTACLE NearestObstacle(const LINE *aLine, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:278
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:180
Definition: track.h:343
void popLineStack()
Definition: pns_shove.cpp:1132
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:626
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1079
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:522
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:585
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:996
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:944
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:455
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:147
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168

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.

215 {
216  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
217 
218  int obstacleLineWidth = aObstacleLine.Width();
219  int clearance = getClearance( &aCurLine, &aObstacleLine );
220  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
221 
222  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
223  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
224 
225  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
226  SHAPE_LINE_CHAIN path_cw;
227  SHAPE_LINE_CHAIN path_ccw;
228 
229  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
230  return SH_INCOMPLETE;
231 
232  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
233  return SH_INCOMPLETE;
234 
235  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
236 
237  if( shortest.PointCount() < 2 )
238  return SH_INCOMPLETE;
239 
240  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
241  return SH_INCOMPLETE;
242 
243  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
244  return SH_INCOMPLETE;
245 
246  aResultLine.SetShape( shortest );
247 
248  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
249  return SH_INCOMPLETE;
250 
251  return SH_OK;
252 }
long long int Length() const
Function Length()
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:125
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:133
NODE * m_currentNode
Definition: pns_shove.h:168

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.

1355 {
1356  SHOVE_STATUS st = SH_OK;
1357 
1358  m_multiLineMode = false;
1359 
1360  if( Dbg() )
1361  {
1362  Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
1363  }
1364 
1365  // empty head? nothing to shove...
1366 
1367  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1368  return SH_INCOMPLETE;
1369 
1370  LINE head( aCurrentHead );
1371  head.ClearLinks();
1372 
1373  m_lineStack.clear();
1374  m_optimizerQueue.clear();
1375  m_newHead = OPT_LINE();
1376 #if 0
1377  m_logger.Clear();
1378 #endif
1379 
1380  // Pop NODEs containing previous shoves which are no longer necessary
1381  //
1382  ITEM_SET headSet;
1383  headSet.Add( aCurrentHead );
1384 
1385  VIA_HANDLE dummyVia;
1386 
1387  NODE* parent = reduceSpringback( headSet, dummyVia );
1388 
1389  // Create a new NODE to store this version of the world
1390  //
1391  m_currentNode = parent->Branch();
1393  m_currentNode->Add( head );
1394 
1395  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1396 
1397  if( !head.EndsWithVia() )
1398  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1399 
1400  head.Mark( MK_HEAD );
1401  head.SetRank( 100000 );
1402 
1403  if ( Dbg() )
1404  {
1405 
1406  Dbg()->BeginGroup( "initial" );
1407  Dbg()->AddLine(head.CLine(), 5, head.Width(), "head" );
1408  Dbg()->EndGroup();
1409  }
1410 
1411  if( head.EndsWithVia() )
1412  {
1413  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1414  headVia->Mark( MK_HEAD );
1415  headVia->SetRank( 100000 );
1416  m_currentNode->Add( std::move( headVia ) );
1417  }
1418 
1419  if( !pushLineStack( head ) )
1420  {
1421  delete m_currentNode;
1422  m_currentNode = parent;
1423 
1424  return SH_INCOMPLETE;
1425  }
1426 
1427  st = shoveMainLoop();
1428 
1429  if( st == SH_OK )
1430  {
1432 
1433  if( m_newHead )
1435  else
1436  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1437  }
1438 
1440 
1441  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1442  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1443 
1444  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1445  {
1447  }
1448  else
1449  {
1450  delete m_currentNode;
1451 
1452  m_currentNode = parent;
1453  m_newHead = OPT_LINE();
1454  }
1455 
1456  if(m_newHead)
1457  m_newHead->Unmark();
1458 
1459  if( m_newHead && head.EndsWithVia() )
1460  {
1461  VIA v = head.Via();
1462  v.SetPos( m_newHead->CPoint( -1 ) );
1463  m_newHead->AppendVia(v);
1464  }
1465 
1466  return st;
1467 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1341
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
Definition: track.h:343
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:752
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1656
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:780
void Clear()
Definition: pns_logger.cpp:38
virtual void Message(const wxString msg)
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
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1351
virtual void BeginGroup(const std::string name)
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
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:420
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1298
bool m_multiLineMode
Definition: pns_shove.h:178
OPT_LINE m_newHead
Definition: pns_shove.h:171
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:608
LOGGER m_logger
Definition: pns_shove.h:173
int m_iter
Definition: pns_shove.h:176
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1071

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.

260 {
261  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
262 
263  int attempt;
264 
265  for( attempt = 0; attempt < 4; attempt++ )
266  {
267  bool invertTraversal = ( attempt >= 2 );
268  bool clockwise = attempt % 2;
269  int vFirst = -1, vLast = -1;
270 
272  LINE l( aObstacleLine );
273 
274  for( int i = 0; i < (int) aHulls.size(); i++ )
275  {
276  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
277 
278  if( ! l.Walkaround( hull, path, clockwise ) )
279  {
280  wxLogTrace("PNS", "Fail-Walk %s %s %d\n", hull.Format().c_str(), l.CLine().Format().c_str(), clockwise? 1:0);
281  return SH_INCOMPLETE;
282  }
283 
284  path.Simplify();
285  l.SetShape( path );
286  }
287 
288  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
289  {
290  if( path.CPoint( i ) != obs.CPoint( i ) )
291  {
292  vFirst = i;
293  break;
294  }
295  }
296 
297  int k = obs.PointCount() - 1;
298  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
299  {
300  if( path.CPoint( i ) != obs.CPoint( k ) )
301  {
302  vLast = i;
303  break;
304  }
305  }
306 
307  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
308  {
309  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
310  continue;
311  }
312 
313  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
314  {
315  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
316  continue;
317  }
318 
319  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
320  {
321  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
322  aResultLine.SetShape( l.CLine() );
323 
324  continue;
325  }
326 
327  if( path.SelfIntersecting() )
328  {
329  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
330  continue;
331  }
332 
333  bool colliding = l.Collide( &aCurLine, m_currentNode );
334 
335 #ifdef DEBUG
336  char str[128];
337  sprintf( str, "att-%d-shoved", attempt );
338  Dbg()->AddLine( l.CLine(), 3, 20000, str );
339 #endif
340 
341  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
342  {
343  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
344 
345  for( ITEM* item : jtStart->LinkList() )
346  {
347  if( item->Collide( &l, m_currentNode ) )
348  colliding = true;
349  }
350  }
351 
352  if( colliding )
353  {
354  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
355  continue;
356  }
357 
358  aResultLine.SetShape( l.CLine() );
359 
360  return SH_OK;
361  }
362 
363  return SH_INCOMPLETE;
364 }
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
const std::string Format() const override
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:1041
SHAPE_LINE_CHAIN.
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:193
NODE * m_currentNode
Definition: pns_shove.h:168

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.

1299 {
1300  SHOVE_STATUS st = SH_OK;
1301 
1303 
1304  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1306 
1307  int iterLimit = Settings().ShoveIterationLimit();
1308  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1309 
1310  m_iter = 0;
1311 
1312  timeLimit.Restart();
1313 
1314  if( m_lineStack.empty() && m_draggedVia )
1315  {
1316  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1317  // the stack.
1319  }
1320 
1321  while( !m_lineStack.empty() )
1322  {
1323  st = shoveIteration( m_iter );
1324 
1325  m_iter++;
1326 
1327  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1328  {
1329  st = SH_INCOMPLETE;
1330  break;
1331  }
1332  }
1333 
1334  return st;
1335 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:183
NODE * m_root
Definition: pns_shove.h:167
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1161
VIA * m_draggedVia
Definition: pns_shove.h:174
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168
int m_iter
Definition: pns_shove.h:176
TIME_LIMIT ShoveTimeLimit() const

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.

1471 {
1472  SHOVE_STATUS st = SH_OK;
1473 
1474  m_multiLineMode = true;
1475 
1476  ITEM_SET headSet;
1477 
1478  for( const ITEM* item : aHeadSet.CItems() )
1479  {
1480  const LINE* headOrig = static_cast<const LINE*>( item );
1481 
1482  // empty head? nothing to shove...
1483  if( !headOrig->SegmentCount() )
1484  return SH_INCOMPLETE;
1485 
1486  headSet.Add( *headOrig );
1487  }
1488 
1489  m_lineStack.clear();
1490  m_optimizerQueue.clear();
1491 #if 0
1492  m_logger.Clear();
1493 #endif
1494 
1495  VIA_HANDLE dummyVia;
1496 
1497  NODE* parent = reduceSpringback( headSet, dummyVia );
1498 
1499  m_currentNode = parent->Branch();
1501  int n = 0;
1502 
1503  for( const ITEM* item : aHeadSet.CItems() )
1504  {
1505  const LINE* headOrig = static_cast<const LINE*>( item );
1506  LINE head( *headOrig );
1507  head.ClearLinks();
1508 
1509  m_currentNode->Add( head );
1510 
1511  head.Mark( MK_HEAD );
1512  head.SetRank( 100000 );
1513  n++;
1514 
1515  if( !pushLineStack( head ) )
1516  return SH_INCOMPLETE;
1517 
1518  if( head.EndsWithVia() )
1519  {
1520  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1521  headVia->Mark( MK_HEAD );
1522  headVia->SetRank( 100000 );
1523  m_currentNode->Add( std::move( headVia ) );
1524  }
1525  }
1526 
1527  st = shoveMainLoop();
1528 
1529  if( st == SH_OK )
1531 
1533 
1534  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1535  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1536 
1537  if( st == SH_OK )
1538  {
1540  }
1541  else
1542  {
1543  delete m_currentNode;
1544  m_currentNode = parent;
1545  }
1546 
1547  return st;
1548 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1341
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1113
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
NODE * Branch()
Create a lightweight copy (called branch) of self that tracks the changes (added/removed items) wrs t...
Definition: pns_node.cpp:124
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:752
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1656
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:780
void Clear()
Definition: pns_logger.cpp:38
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1351
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1298
bool m_multiLineMode
Definition: pns_shove.h:178
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163
NODE * m_currentNode
Definition: pns_shove.h:168
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:608
LOGGER m_logger
Definition: pns_shove.h:173
int m_iter
Definition: pns_shove.h:176

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.

373 {
374  aResultLine.ClearLinks();
375 
376  bool obstacleIsHead = false;
377 
378  for( LINKED_ITEM* s : aObstacleLine.Links() )
379  {
380  if( s->Marker() & MK_HEAD )
381  {
382  obstacleIsHead = true;
383  break;
384  }
385  }
386 
387  SHOVE_STATUS rv;
388  bool viaOnEnd = aCurLine.EndsWithVia();
389 
390  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
391  {
392  // Shove aObstacleLine to the hull of aCurLine's via.
393 
394  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
395  }
396  else
397  {
398  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
399  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
400  // hull it will be at the appropriate clearance.
401 
402  int obstacleLineWidth = aObstacleLine.Width();
403  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
404  int currentLineSegmentCount = aCurLine.SegmentCount();
405  HULL_SET hulls;
406 
407  hulls.reserve( currentLineSegmentCount + 1 );
408 
409 #ifdef DEBUG
410  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
411  aCurLine.Net(),
412  aObstacleLine.Net(),
413  clearance ) );
414 #endif
415 
416  for( int i = 0; i < currentLineSegmentCount; i++ )
417  {
418  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
419  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
420 
421  hulls.push_back( hull );
422  }
423 
424  if( viaOnEnd )
425  {
426  const VIA& via = aCurLine.Via();
427  int viaClearance = getClearance( &via, &aObstacleLine );
428  int holeClearance = getHoleClearance( &via, &aObstacleLine );
429 
430  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
431  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
432 
433  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
434  }
435 
436 #ifdef DEBUG
437  char str[128];
438  sprintf( str, "current-cl-%d", clearance );
439  Dbg()->AddLine( aCurLine.CLine(), 5, 20000, str );
440 #endif
441 
442  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
443  }
444 
445  if( obstacleIsHead )
446  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
447 
448  return rv;
449 }
Definition: track.h:343
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHOVE_STATUS shoveLineToHullSet(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine, const HULL_SET &aHulls)
Definition: pns_shove.cpp:258
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
virtual void Message(const wxString msg)
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
SHAPE_LINE_CHAIN.
usual segment : line with rounded ends
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:125
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:133
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:213

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.

1339 {
1340  OPT_BOX2I area;
1341 
1342  if( !m_nodeStack.empty() )
1343  area = m_nodeStack.back().m_affectedArea;
1344 
1345  if( area && m_affectedArea)
1346  area->Merge( *m_affectedArea );
1347  else if( !area )
1348  area = m_affectedArea;
1349 
1350  return area;
1351 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:154
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525

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.

1801 {
1802  auto iter = m_nodeStack.begin();
1803 
1804  while( iter != m_nodeStack.end() )
1805  {
1806  if ( iter->m_node == aNode )
1807  {
1808  iter->m_locked = false;
1809  break;
1810  }
1811  iter++;
1812  }
1813 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:162

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

Definition at line 1079 of file pns_shove.cpp.

1080 {
1081  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1082  {
1083  if( i->ContainsLink( aSeg ) )
1084  i = m_lineStack.erase( i );
1085  else
1086  i++;
1087  }
1088 
1089  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1090  {
1091  if( i->ContainsLink( aSeg ) )
1092  i = m_optimizerQueue.erase( i );
1093  else
1094  i++;
1095  }
1096 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:164
std::vector< LINE > m_lineStack
Definition: pns_shove.h:163

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.

1100 {
1101  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1102  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1103  else if( aItem->OfKind( ITEM::LINE_T ) )
1104  {
1105  LINE* l = static_cast<LINE*>( aItem );
1106 
1107  for( LINKED_ITEM* seg : l->Links() )
1108  unwindLineStack( seg );
1109  }
1110 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1079

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.

40 {
41  return m_router->VisibleViewArea();
42 }
ROUTER * m_router
Definition: pns_algo_base.h:87
const BOX2I & VisibleViewArea() const
Definition: pns_router.h:220

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 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

◆ m_lineStack

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

◆ m_logger

LOGGER PNS::SHOVE::m_logger
private

◆ m_multiLineMode

bool PNS::SHOVE::m_multiLineMode
private

◆ m_newHead

◆ m_nodeStack

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

◆ m_optimizerQueue

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

◆ 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


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