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

100  :
101  ALGO_BASE( aRouter )
102 {
103  m_forceClearance = -1;
104  m_root = aWorld;
105  m_currentNode = aWorld;
106  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
107 
108  // Initialize other temporary variables:
109  m_draggedVia = NULL;
110  m_iter = 0;
111  m_multiLineMode = false;
113 }
int m_restrictSpringbackTagId
Definition: pns_shove.h:166
NODE * m_root
Definition: pns_shove.h:164
#define NULL
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:45
VIA * m_draggedVia
Definition: pns_shove.h:171
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:175
NODE * m_currentNode
Definition: pns_shove.h:165
int m_iter
Definition: pns_shove.h:173
int m_forceClearance
Definition: pns_shove.h:174

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

117 {
118 }

Member Function Documentation

◆ AddLockedSpringbackNode()

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

Definition at line 1685 of file pns_shove.cpp.

1686 {
1687  SPRINGBACK_TAG sp;
1688  sp.m_node = aNode;
1689  sp.m_locked = true;
1690 
1691  m_nodeStack.push_back(sp);
1692  return true;
1693 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160

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

122 {
123  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
124 }
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:912
NODE * m_currentNode
Definition: pns_shove.h:165

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

136 {
137  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurLine.CPoint( 0) );
138  checker.AddPolyline( aObstacleLine.CLine() );
139  checker.AddPolyline( aShovedLine.CLine().Reverse() );
140 
141  bool inside = checker.IsInside();
142 
143  return !inside;
144 }
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 1664 of file pns_shove.cpp.

1665 {
1666  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1667 }
NODE * m_root
Definition: pns_shove.h:164
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160

References m_nodeStack, and m_root.

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

◆ Dbg()

◆ 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:174

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

77 {
78  if( m_forceClearance >= 0 )
79  return m_forceClearance;
80 
81  return m_currentNode->GetClearance( aA, aB );
82 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:97
NODE * m_currentNode
Definition: pns_shove.h:165
int m_forceClearance
Definition: pns_shove.h:174

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

85 {
86  if( m_forceClearance >= 0 )
87  return m_forceClearance;
88 
89  return m_currentNode->GetHoleClearance( aA, aB );
90 }
int GetHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_node.cpp:106
NODE * m_currentNode
Definition: pns_shove.h:165
int m_forceClearance
Definition: pns_shove.h:174

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

Referenced by onCollidingVia(), 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:170

References m_logger.

◆ NewHead()

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

Definition at line 1670 of file pns_shove.cpp.

1671 {
1672  assert( m_newHead );
1673 
1674  return *m_newHead;
1675 }
OPT_LINE m_newHead
Definition: pns_shove.h:168

References m_newHead.

◆ onCollidingArc()

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

Definition at line 463 of file pns_shove.cpp.

464 {
465  int segIndex;
466  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
467  LINE shovedLine( obstacleLine );
468  ARC tmp( *aObstacleArc );
469 
470  if( obstacleLine.HasLockedSegments() )
471  return SH_TRY_WALK;
472 
473  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
474 
475  const double extensionWalkThreshold = 1.0;
476 
477  double obsLen = obstacleLine.CLine().Length();
478  double shovedLen = shovedLine.CLine().Length();
479  double extensionFactor = 0.0;
480 
481  if( obsLen != 0.0f )
482  extensionFactor = shovedLen / obsLen - 1.0;
483 
484  if( extensionFactor > extensionWalkThreshold )
485  return SH_TRY_WALK;
486 
487  assert( obstacleLine.LayersOverlap( &shovedLine ) );
488 
489  if ( Dbg() )
490  {
491  Dbg()->BeginGroup( wxString::Format( "on-colliding-arc-iter-%d", m_iter ).ToStdString() );
492  Dbg()->AddLine( tmp.CLine(), 0, 10000, "obstacle-segment" );
493  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
494  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
495  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
496  Dbg()->EndGroup();
497  }
498 
499  if( rv == SH_OK )
500  {
501  if( shovedLine.Marker() & MK_HEAD )
502  {
503  if( m_multiLineMode )
504  return SH_INCOMPLETE;
505 
506  m_newHead = shovedLine;
507  }
508 
509  int rank = aCurrent.Rank();
510  shovedLine.SetRank( rank - 1 );
511 
512  sanityCheck( &obstacleLine, &shovedLine );
513  replaceLine( obstacleLine, shovedLine );
514 
515  if( !pushLineStack( shovedLine ) )
516  rv = SH_INCOMPLETE;
517  }
518 
519  return rv;
520 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
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:312
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:93
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
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
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
int m_iter
Definition: pns_shove.h:173

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

527 {
528  LINE shovedLine( aObstacle );
529 
530  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, aObstacle, shovedLine );
531 
532  Dbg()->BeginGroup( "on-colliding-line" );
533  Dbg()->AddLine( aObstacle.CLine(), 1, 100000, "obstacle-line" );
534  Dbg()->AddLine( aCurrent.CLine(), 2, 150000, "current-line" );
535  Dbg()->AddLine( shovedLine.CLine(), 3, 200000, "shoved-line" );
536 
537  if( rv == SH_OK )
538  {
539  if( shovedLine.Marker() & MK_HEAD )
540  {
541  if( m_multiLineMode )
542  return SH_INCOMPLETE;
543 
544  m_newHead = shovedLine;
545  }
546 
547  sanityCheck( &aObstacle, &shovedLine );
548  replaceLine( aObstacle, shovedLine );
549 
550  int rank = aObstacle.Rank();
551  shovedLine.SetRank( rank - 1 );
552 
553 
554  if( !pushLineStack( shovedLine ) )
555  {
556  rv = SH_INCOMPLETE;
557  }
558  }
559 
560  return rv;
561 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
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:312
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:93
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
virtual void BeginGroup(const std::string name)
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168

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

397 {
398  int segIndex;
399  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
400  LINE shovedLine( obstacleLine );
401  SEGMENT tmp( *aObstacleSeg );
402 
403  if( obstacleLine.HasLockedSegments() )
404  return SH_TRY_WALK;
405 
406  SHOVE_STATUS rv = ShoveObstacleLine( aCurrent, obstacleLine, shovedLine );
407 
408  const double extensionWalkThreshold = 1.0;
409 
410  double obsLen = obstacleLine.CLine().Length();
411  double shovedLen = shovedLine.CLine().Length();
412  double extensionFactor = 0.0;
413 
414  if( obsLen != 0.0f )
415  extensionFactor = shovedLen / obsLen - 1.0;
416 
417  if( extensionFactor > extensionWalkThreshold )
418  return SH_TRY_WALK;
419 
420  assert( obstacleLine.LayersOverlap( &shovedLine ) );
421 
422  if( Dbg() )
423  {
424  Dbg()->BeginGroup( wxString::Format( "on-colliding-segment-iter-%d", m_iter ).ToStdString() );
425  Dbg()->AddSegment( tmp.Seg(), 0, "obstacle-segment" );
426  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
427  Dbg()->AddLine( obstacleLine.CLine(), 2, 10000, "obstacle-line" );
428  Dbg()->AddLine( shovedLine.CLine(), 3, 10000, "shoved-line" );
429  if( rv == SH_OK )
430  Dbg()->Message("Shove success");
431  else
432  Dbg()->Message("Shove FAIL");
433  Dbg()->EndGroup();
434  }
435 
436  if( rv == SH_OK )
437  {
438  if( shovedLine.Marker() & MK_HEAD )
439  {
440  if( m_multiLineMode )
441  return SH_INCOMPLETE;
442 
443  m_newHead = shovedLine;
444  }
445 
446  int rank = aCurrent.Rank();
447  shovedLine.SetRank( rank - 1 );
448 
449  sanityCheck( &obstacleLine, &shovedLine );
450  replaceLine( obstacleLine, shovedLine );
451 
452  if( !pushLineStack( shovedLine ) )
453  rv = SH_INCOMPLETE;
454  }
455 
456  return rv;
457 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
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:312
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:93
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
virtual void AddSegment(SEG aS, int aColor, const std::string aName="")
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)
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
int m_iter
Definition: pns_shove.h:173

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

568 {
569  WALKAROUND walkaround( m_currentNode, Router() );
570  LINE walkaroundLine( aCurrent );
571 
572  if( aCurrent.EndsWithVia() )
573  {
574  VIA vh = aCurrent.Via();
575  VIA* via = NULL;
576  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
577 
578  if( !jtStart )
579  return SH_INCOMPLETE;
580 
581  for( ITEM* item : jtStart->LinkList() )
582  {
583  if( item->OfKind( ITEM::VIA_T ) )
584  {
585  via = (VIA*) item;
586  break;
587  }
588  }
589 
590  if( via && via->Collide( aObstacle, m_currentNode ) )
591  return onCollidingVia( aObstacle, via );
592  }
593 
594  TOPOLOGY topo( m_currentNode );
595 
596  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
597 
598  walkaround.SetSolidsOnly( false );
599  walkaround.RestrictToSet( true, cluster );
600  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
601 
602  int currentRank = aCurrent.Rank();
603  int nextRank;
604 
605  bool success = false;
606 
607  for( int attempt = 0; attempt < 2; attempt++ )
608  {
609  if( attempt == 1 || Settings().JumpOverObstacles() )
610  {
611 
612  nextRank = currentRank - 1;
613  walkaround.SetSingleDirection( true );
614  }
615  else
616  {
617  nextRank = currentRank + 10000;
618  walkaround.SetSingleDirection( false );
619  }
620 
621 
622  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
623 
624  if( status != WALKAROUND::DONE )
625  continue;
626 
627  walkaroundLine.ClearLinks();
628  walkaroundLine.Unmark();
629  walkaroundLine.Line().Simplify();
630 
631  if( walkaroundLine.HasLoops() )
632  continue;
633 
634  if( aCurrent.Marker() & MK_HEAD )
635  {
636  walkaroundLine.Mark( MK_HEAD );
637 
638  if( m_multiLineMode )
639  continue;
640 
641  m_newHead = walkaroundLine;
642  }
643 
644  sanityCheck( &aCurrent, &walkaroundLine );
645 
646  if( !m_lineStack.empty() )
647  {
648  LINE lastLine = m_lineStack.front();
649 
650  if( lastLine.Collide( &walkaroundLine, m_currentNode ) )
651  {
652  LINE dummy( lastLine );
653 
654  if( ShoveObstacleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
655  {
656  success = true;
657  break;
658  }
659  } else {
660  success = true;
661  break;
662  }
663  }
664  }
665 
666  if(!success)
667  return SH_INCOMPLETE;
668 
669  replaceLine( aCurrent, walkaroundLine );
670  walkaroundLine.SetRank( nextRank );
671 
672  if( Dbg() )
673  {
674  Dbg()->BeginGroup( "on-colliding-solid" );
675  Dbg()->AddLine( aCurrent.CLine(), 1, 10000, "current-line" );
676  Dbg()->AddLine( walkaroundLine.CLine(), 3, 10000, "walk-line" );
677  Dbg()->EndGroup();
678  }
679 
680  popLineStack();
681 
682  if( !pushLineStack( walkaroundLine ) )
683  return SH_INCOMPLETE;
684 
685  return SH_OK;
686 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
ROUTER * Router() const
Return current router settings.
Definition: pns_algo_base.h:54
Definition: track.h:343
void popLineStack()
Definition: pns_shove.cpp:1075
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:312
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:885
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:93
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:1027
virtual void BeginGroup(const std::string name)
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165

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(), and PNS::ITEM::VIA_T.

Referenced by shoveIteration().

◆ onCollidingVia()

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

Definition at line 885 of file pns_shove.cpp.

886 {
887  int clearance = getClearance( aCurrent, aObstacleVia );
888  LINE_PAIR_VEC draggedLines;
889  VECTOR2I mtv;
890  int rank = -1;
891 
892  SHAPE_COMPOUND shape;
893 
894  if( aCurrent->OfKind( ITEM::LINE_T ) )
895  {
896  LINE* currentLine = (LINE*) aCurrent;
897 
898 #if 0
899  m_logger.NewGroup( "push-via-by-line", m_iter );
900  m_logger.Log( currentLine, 4, "current" );
901 #endif
902 
903  shape.AddShape( currentLine->Shape()->Clone() );
904 
905  // SHAPE_LINE_CHAIN collisions don't currently pay any attention to the line-chain's
906  // width, so we have to add it to the clearance.
907  clearance += currentLine->Width() / 2;
908 
909  // Add a second shape for the via (if any)
910  if( currentLine->EndsWithVia() )
911  {
912  const VIA& currentVia = currentLine->Via();
913  int viaClearance = getClearance( &currentVia, aObstacleVia );
914  int holeClearance = getHoleClearance( &currentVia, aObstacleVia );
915  int effectiveRadius = std::max( currentVia.Diameter() / 2 + viaClearance,
916  currentVia.Drill() / 2 + holeClearance );
917 
918  // Since we have to run the collision with the line's clearance + 1/2 its width (as
919  // it's the only way to take the SHAPE_LINE_CHAIN's width into account), we need to
920  // subtract that clearance back out of the via's effective radius.
921  shape.AddShape( new SHAPE_CIRCLE( currentVia.Pos(), effectiveRadius - clearance ) );
922  }
923  }
924  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
925  {
926  shape.AddShape( aCurrent->Shape()->Clone() );
927  }
928 
929  aObstacleVia->Shape()->Collide( &shape, clearance + PNS_HULL_MARGIN, &mtv );
930  rank = aCurrent->Rank() + 10000;
931 
932  return pushOrShoveVia( aObstacleVia, mtv, rank );
933 }
Definition: track.h:343
#define PNS_HULL_MARGIN
Definition: pns_line.h:44
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:758
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:76
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:84
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:170
int m_iter
Definition: pns_shove.h:173
void AddShape(SHAPE *aShape)

References SHAPE_COMPOUND::AddShape(), SHAPE::Clone(), SHAPE::Collide(), PNS::VIA::Diameter(), PNS::VIA::Drill(), PNS::LINE::EndsWithVia(), getClearance(), getHoleClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::OfKind(), PNS_HULL_MARGIN, PNS::VIA::Pos(), pushOrShoveVia(), PNS::ITEM::Rank(), PNS::VIA::Shape(), PNS::LINE::Shape(), PNS::ITEM::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 939 of file pns_shove.cpp.

940 {
941  int n = 0;
942  LINE cur( aCurrent );
943  cur.ClearLinks();
944 
945  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
946  LINE shoved( aCurrent );
947  shoved.ClearLinks();
948 
949  cur.RemoveVia();
950  unwindLineStack( &aCurrent );
951 
952  for( ITEM* item : jt->LinkList() )
953  {
954  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
955  {
956  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
957  LINE head = assembleLine( li );
958 
959  head.AppendVia( *aObstacleVia );
960 
961  SHOVE_STATUS st = ShoveObstacleLine( head, cur, shoved );
962 
963  if( st != SH_OK )
964  {
965 #if 0
966  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
967  m_logger.Log( aObstacleVia, 0, "the-via" );
968  m_logger.Log( &aCurrent, 1, "current-line" );
969  m_logger.Log( &shoved, 3, "shoved-line" );
970 #endif
971 
972  return st;
973  }
974 
975  cur.SetShape( shoved.CLine() );
976  n++;
977  }
978  }
979 
980  if( !n )
981  {
982 #if 0
983  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
984  m_logger.Log( aObstacleVia, 0, "the-via" );
985  m_logger.Log( &aCurrent, 1, "current-line" );
986 #endif
987 
988  LINE head( aCurrent );
989  head.Line().Clear();
990  head.AppendVia( *aObstacleVia );
991  head.ClearLinks();
992 
993  SHOVE_STATUS st = ShoveObstacleLine( head, aCurrent, shoved );
994 
995  if( st != SH_OK )
996  return st;
997 
998  cur.SetShape( shoved.CLine() );
999  }
1000 
1001  if( aCurrent.EndsWithVia() )
1002  shoved.AppendVia( aCurrent.Via() );
1003 
1004 #if 0
1005  m_logger.NewGroup( "on-reverse-via", m_iter );
1006  m_logger.Log( aObstacleVia, 0, "the-via" );
1007  m_logger.Log( &aCurrent, 1, "current-line" );
1008  m_logger.Log( &shoved, 3, "shoved-line" );
1009 #endif
1010  int currentRank = aCurrent.Rank();
1011  replaceLine( aCurrent, shoved );
1012 
1013  if( !pushLineStack( shoved ) )
1014  return SH_INCOMPLETE;
1015 
1016  shoved.SetRank( currentRank );
1017 
1018  return SH_OK;
1019 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1022
SHOVE_STATUS ShoveObstacleLine(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:312
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:1027
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
NODE * m_currentNode
Definition: pns_shove.h:165
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:170
int m_iter
Definition: pns_shove.h:173

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

1076 {
1077  LINE& l = m_lineStack.back();
1078 
1079  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1080  {
1081  bool found = false;
1082 
1083  for( LINKED_ITEM* s : l.Links() )
1084  {
1085  if( i->ContainsLink( s ) )
1086  {
1087  i = m_optimizerQueue.erase( i );
1088  found = true;
1089  break;
1090  }
1091  }
1092 
1093  if( !found )
1094  i++;
1095  }
1096 
1097  m_lineStack.pop_back();
1098 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161

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

1057 {
1058  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1059  return false;
1060 
1061  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1062  {
1063  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1064  }
1065  else
1066  {
1067  m_lineStack.push_back( aL );
1068  }
1069 
1070  m_optimizerQueue.push_back( aL );
1071 
1072  return true;
1073 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161

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

759 {
760  LINE_PAIR_VEC draggedLines;
761  VECTOR2I p0( aVia->Pos() );
762  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
763  VECTOR2I p0_pushed( p0 + aForce );
764 
765  // nothing to do...
766  if ( aForce.x == 0 && aForce.y == 0 )
767  return SH_OK;
768 
769  if( !jt )
770  {
771  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
772  return SH_INCOMPLETE;
773  }
774 
775  if( aVia->IsLocked() )
776  return SH_TRY_WALK;
777 
778  if( jt->IsLocked() )
779  return SH_INCOMPLETE;
780 
781  // make sure pushed via does not overlap with any existing joint
782  while( true )
783  {
784  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
785 
786  if( !jt_next )
787  break;
788 
789  p0_pushed += aForce.Resize( 2 );
790  }
791 
792  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
793  pushedVia->SetPos( p0_pushed );
794  pushedVia->Mark( aVia->Marker() );
795 
796  for( ITEM* item : jt->LinkList() )
797  {
798  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
799  {
800  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
801  LINE_PAIR lp;
802  int segIndex;
803 
804  lp.first = assembleLine( li, &segIndex );
805 
806  if( lp.first.HasLockedSegments() )
807  return SH_TRY_WALK;
808 
809  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
810 
811  if( segIndex == 0 )
812  lp.first.Reverse();
813 
814  lp.second = lp.first;
815  lp.second.ClearLinks();
816  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
817  lp.second.AppendVia( *pushedVia );
818  draggedLines.push_back( lp );
819  }
820  }
821 
822 #if 0
823  m_logger.Log( aVia, 0, "obstacle-via" );
824 #endif
825 
826  pushedVia->SetRank( aCurrentRank - 1 );
827 
828 #if 0
829  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
830 #endif
831 
832  if( aVia->Marker() & MK_HEAD ) // push
833  {
834  m_draggedVia = pushedVia.get();
835  }
836  else
837  { // shove
838  if( jt->IsStitchingVia() )
839  pushLineStack( LINE( *pushedVia ) );
840  }
841 
842  replaceItems( aVia, std::move( pushedVia ) );
843 
844  for( LINE_PAIR lp : draggedLines )
845  {
846  if( lp.first.Marker() & MK_HEAD )
847  {
848  lp.second.Mark( MK_HEAD );
849 
850  if( m_multiLineMode )
851  return SH_INCOMPLETE;
852 
853  m_newHead = lp.second;
854  }
855 
856  unwindLineStack( &lp.first );
857 
858  if( lp.second.SegmentCount() )
859  {
860  replaceLine( lp.first, lp.second );
861  lp.second.SetRank( aCurrentRank - 1 );
862 
863  if( !pushLineStack( lp.second, true ) )
864  return SH_INCOMPLETE;
865  }
866  else
867  {
868  m_currentNode->Remove( lp.first );
869  }
870 
871 #if 0
872  m_logger.Log( &lp.first, 2, "fan-pre" );
873  m_logger.Log( &lp.second, 3, "fan-post" );
874 #endif
875  }
876 
877  return SH_OK;
878 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1022
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:804
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:1027
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:171
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:257
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:59
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:49
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
NODE * m_currentNode
Definition: pns_shove.h:165
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:170

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

722 {
723  SPRINGBACK_TAG st;
724  OPT_BOX2I prev_area;
725 
726  if( !m_nodeStack.empty() )
727  prev_area = m_nodeStack.back().m_affectedArea;
728 
729  if( aDraggedVia )
730  {
731  st.m_draggedVia = aDraggedVia->MakeHandle();
732  }
733 
734  st.m_node = aNode;
735 
736  if( aAffectedArea )
737  {
738  if( prev_area )
739  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
740  else
741  st.m_affectedArea = aAffectedArea;
742  } else
743  st.m_affectedArea = prev_area;
744 
745  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
746  st.m_locked = false;
747 
748  m_nodeStack.push_back( st );
749 
750  return true;
751 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160
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 693 of file pns_shove.cpp.

694 {
695  while( !m_nodeStack.empty() )
696  {
697  SPRINGBACK_TAG& spTag = m_nodeStack.back();
698 
699  OPT<OBSTACLE> obs = spTag.m_node->CheckColliding( aHeadSet );
700 
701  if( !obs && !spTag.m_locked )
702  {
703  aDraggedVia = spTag.m_draggedVia;
704  aDraggedVia.valid = true;
705 
706  delete spTag.m_node;
707  m_nodeStack.pop_back();
708  }
709  else
710  break;
711  }
712 
713  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
714 }
NODE * m_root
Definition: pns_shove.h:164
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160
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:769
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:165

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

Referenced by pushOrShoveVia().

◆ replaceLine()

void PNS::SHOVE::replaceLine ( LINE aOld,
LINE aNew 
)
private

Definition at line 59 of file pns_shove.cpp.

60 {
61  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
62 
63  if( changed_area )
64  {
65  if( Dbg() )
66  {
67  Dbg()->AddBox( *changed_area, 3, "shove-changed-area" );
68  }
69 
70  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
71  }
72 
73  m_currentNode->Replace( aOld, aNew );
74 }
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
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Replace an item with another one.
Definition: pns_node.cpp:769
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:165

References PNS::DEBUG_DECORATOR::AddBox(), PNS::ChangedArea(), PNS::ALGO_BASE::Dbg(), m_affectedArea, m_currentNode, and PNS::NODE::Replace().

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

◆ RewindSpringbackTo()

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

Definition at line 1696 of file pns_shove.cpp.

1697 {
1698  bool found = false;
1699 
1700  auto iter = m_nodeStack.begin();
1701 
1702  while( iter != m_nodeStack.end() )
1703  {
1704  if ( iter->m_node == aNode )
1705  {
1706  found = true;
1707  break;
1708  }
1709  iter++;
1710  }
1711 
1712  if( !found )
1713  return false;
1714 
1715  auto start = iter;
1716 
1717  aNode->KillChildren();
1718  m_nodeStack.erase( start, m_nodeStack.end() );
1719 
1720  return true;
1721 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160

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

◆ Router()

◆ runOptimizer()

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

Definition at line 1582 of file pns_shove.cpp.

1583 {
1584  OPTIMIZER optimizer( aNode );
1585  int optFlags = 0;
1586  int n_passes = 0;
1587 
1589 
1590  OPT_BOX2I area = totalAffectedArea();
1591 
1592  int maxWidth = 0;
1593 
1594  for( LINE& line : m_optimizerQueue )
1595  maxWidth = std::max( line.Width(), maxWidth );
1596 
1597  if( area )
1598  {
1599  area->Inflate( maxWidth );
1600  area = area->Intersect( VisibleViewArea() );
1601  }
1602 
1603  switch( effort )
1604  {
1605  case OE_LOW:
1606  optFlags |= OPTIMIZER::MERGE_OBTUSE;
1607  n_passes = 1;
1608  break;
1609 
1610  case OE_MEDIUM:
1611  optFlags |= OPTIMIZER::MERGE_SEGMENTS;
1612 
1613  n_passes = 2;
1614  break;
1615 
1616  case OE_FULL:
1617  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1618  n_passes = 2;
1619  break;
1620 
1621  default:
1622  break;
1623  }
1624 
1625  if( area )
1626  {
1627  if( Dbg() )
1628  {
1629  Dbg()->AddBox( *area, 1, "opt-area" );
1630  }
1631 
1632  optFlags |= OPTIMIZER::RESTRICT_AREA;
1633  optimizer.SetRestrictArea( *area, false );
1634  }
1635 
1636  if( Settings().SmartPads() )
1637  optFlags |= OPTIMIZER::SMART_PADS;
1638 
1639  optimizer.SetEffortLevel( optFlags );
1640  optimizer.SetCollisionMask( ITEM::ANY_T );
1641 
1642  for( int pass = 0; pass < n_passes; pass++ )
1643  {
1644  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1645 
1646  for( LINE& line : m_optimizerQueue)
1647  {
1648  if( !( line.Marker() & MK_HEAD ) )
1649  {
1650  LINE optimized;
1651 
1652  if( optimizer.Optimize( &line, &optimized ) )
1653  {
1654  aNode->Remove( line );
1655  line.SetShape( optimized.CLine() );
1656  aNode->Add( line );
1657  }
1658  }
1659  }
1660  }
1661 }
virtual void AddBox(BOX2I aB, int aColor, const std::string aName="")
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1281
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
const BOX2I & VisibleViewArea() const
Reduce corner cost by merging obtuse segments.
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
Reroute pad exits.

References PNS::NODE::Add(), PNS::DEBUG_DECORATOR::AddBox(), PNS::ITEM::ANY_T, PNS::LINE::CLine(), PNS::ALGO_BASE::Dbg(), 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::NODE::Remove(), 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 93 of file pns_shove.cpp.

94 {
95  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
96  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
97 }

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

1679 {
1680  m_root = m_root->Branch();
1681  m_root->Remove( aInitial );
1682 }
NODE * m_root
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
void Remove(ARC *aArc)
Remove an item from this branch.
Definition: pns_node.cpp:804

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

1513 {
1514  SHOVE_STATUS st = SH_OK;
1515 
1516  m_lineStack.clear();
1517  m_optimizerQueue.clear();
1518  m_newHead = OPT_LINE();
1519  m_draggedVia = NULL;
1520 
1521  VIA* viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1522 
1523  if( !viaToDrag )
1524  return SH_INCOMPLETE;
1525 
1526  // Pop NODEs containing previous shoves which are no longer necessary
1527  ITEM_SET headSet;
1528 
1529  VIA headVia ( *viaToDrag );
1530  headVia.SetPos( aWhere );
1531  headSet.Add( headVia );
1532  VIA_HANDLE prevViaHandle;
1533  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1534 
1535  if( prevViaHandle.valid )
1536  {
1537  aNewVia = prevViaHandle;
1538  viaToDrag = findViaByHandle( parent, prevViaHandle );
1539  }
1540 
1541  // Create a new NODE to store this version of the world
1542  //
1543  m_currentNode = parent->Branch();
1545 
1546  viaToDrag->Mark( MK_HEAD );
1547  viaToDrag->SetRank( 100000 );
1548 
1549  // Push the via to its new location
1550  //
1551  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos() ), 0 );
1552 
1553  // Shove any colliding objects out of the way
1554  //
1555  if( st == SH_OK )
1556  st = shoveMainLoop();
1557 
1558  if( st == SH_OK )
1560 
1561  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1562  {
1563  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1564 
1565  if (!m_draggedVia)
1566  m_draggedVia = viaToDrag;
1567 
1568  aNewVia = m_draggedVia->MakeHandle();
1569 
1571  }
1572  else
1573  {
1574  delete m_currentNode;
1575  m_currentNode = parent;
1576  }
1577 
1578  return st;
1579 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1327
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:162
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:758
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:693
#define NULL
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1582
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1493
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:721
VIA * m_draggedVia
Definition: pns_shove.h:171
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1241
OPT_LINE m_newHead
Definition: pns_shove.h:168
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165

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

1105 {
1106  LINE currentLine = m_lineStack.back();
1107  NODE::OPT_OBSTACLE nearest;
1108  SHOVE_STATUS st = SH_NULL;
1109 
1110 #ifdef DEBUG
1111  Dbg()->SetIteration( aIter );
1112 #endif
1113 
1114  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1115  {
1116  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1117 
1118  if( nearest )
1119  break;
1120  }
1121 
1122  if( !nearest )
1123  {
1124  m_lineStack.pop_back();
1125  return SH_OK;
1126  }
1127 
1128  ITEM* ni = nearest->m_item;
1129 
1130  unwindLineStack( ni );
1131 
1132  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1133  {
1134  // Collision with a higher-ranking object (ie: one that we've already shoved)
1135  //
1136  switch( ni->Kind() )
1137  {
1138  case ITEM::VIA_T:
1139  {
1140  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1141 
1142  if( currentLine.EndsWithVia() )
1143  {
1144  st = SH_INCOMPLETE;
1145  }
1146  else
1147  {
1148  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1149  }
1150 
1151  break;
1152  }
1153 
1154  case ITEM::SEGMENT_T:
1155  {
1156  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1157  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1158 
1159  popLineStack();
1160  st = onCollidingLine( revLine, currentLine );
1161  if( !pushLineStack( revLine ) )
1162  return SH_INCOMPLETE;
1163 
1164  break;
1165  }
1166 
1167  case ITEM::ARC_T:
1168  {
1169  //TODO(snh): Handle Arc shove separate from track
1170  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1171  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1172 
1173  popLineStack();
1174  st = onCollidingLine( revLine, currentLine );
1175  if( !pushLineStack( revLine ) )
1176  return SH_INCOMPLETE;
1177 
1178  break;
1179  }
1180 
1181  default:
1182  assert( false );
1183  }
1184  }
1185  else
1186  {
1187  // Collision with a lower-ranking object or a solid
1188  //
1189  switch( ni->Kind() )
1190  {
1191  case ITEM::SEGMENT_T:
1192  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1193 
1194  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1195 
1196  if( st == SH_TRY_WALK )
1197  st = onCollidingSolid( currentLine, ni );
1198 
1199  break;
1200 
1201  //TODO(snh): Customize Arc collide
1202  case ITEM::ARC_T:
1203  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1204 
1205  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1206 
1207  if( st == SH_TRY_WALK )
1208  st = onCollidingSolid( currentLine, ni );
1209 
1210  break;
1211 
1212  case ITEM::VIA_T:
1213  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1214  st = onCollidingVia( &currentLine, (VIA*) ni );
1215 
1216  if( st == SH_TRY_WALK )
1217  st = onCollidingSolid( currentLine, ni );
1218 
1219  break;
1220 
1221  case ITEM::SOLID_T:
1222  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1223  st = onCollidingSolid( currentLine, (SOLID*) ni );
1224  break;
1225 
1226  default:
1227  break;
1228  }
1229  }
1230 
1231  return st;
1232 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
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:285
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:121
Definition: track.h:343
void popLineStack()
Definition: pns_shove.cpp:1075
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:567
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1022
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:463
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:526
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:939
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:885
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:396
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:152
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165

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

156 {
157  // Build a hull for aCurLine's via and re-walk aObstacleLine around it.
158 
159  int obstacleLineWidth = aObstacleLine.Width();
160  int clearance = getClearance( &aCurLine, &aObstacleLine );
161  int holeClearance = getHoleClearance( &aCurLine.Via(), &aObstacleLine );
162 
163  if( holeClearance + aCurLine.Via().Drill() / 2 > clearance + aCurLine.Via().Diameter() / 2 )
164  clearance = holeClearance + aCurLine.Via().Drill() / 2 - aCurLine.Via().Diameter() / 2;
165 
166  SHAPE_LINE_CHAIN hull = aCurLine.Via().Hull( clearance, obstacleLineWidth, aCurLine.Layer() );
167  SHAPE_LINE_CHAIN path_cw;
168  SHAPE_LINE_CHAIN path_ccw;
169 
170  if( ! aObstacleLine.Walkaround( hull, path_cw, true ) )
171  return SH_INCOMPLETE;
172 
173  if( ! aObstacleLine.Walkaround( hull, path_ccw, false ) )
174  return SH_INCOMPLETE;
175 
176  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
177 
178  if( shortest.PointCount() < 2 )
179  return SH_INCOMPLETE;
180 
181  if( aObstacleLine.CPoint( -1 ) != shortest.CPoint( -1 ) )
182  return SH_INCOMPLETE;
183 
184  if( aObstacleLine.CPoint( 0 ) != shortest.CPoint( 0 ) )
185  return SH_INCOMPLETE;
186 
187  aResultLine.SetShape( shortest );
188 
189  if( aResultLine.Collide( &aCurLine, m_currentNode ) )
190  return SH_INCOMPLETE;
191 
192  return SH_OK;
193 }
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:76
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:84
NODE * m_currentNode
Definition: pns_shove.h:165

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

1298 {
1299  SHOVE_STATUS st = SH_OK;
1300 
1301  m_multiLineMode = false;
1302 
1303  if( Dbg() )
1304  {
1305  Dbg()->Message( wxString::Format( "Shove start, lc = %d", aCurrentHead.SegmentCount() ) );
1306  }
1307 
1308  // empty head? nothing to shove...
1309 
1310  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1311  return SH_INCOMPLETE;
1312 
1313  LINE head( aCurrentHead );
1314  head.ClearLinks();
1315 
1316  m_lineStack.clear();
1317  m_optimizerQueue.clear();
1318  m_newHead = OPT_LINE();
1319 #if 0
1320  m_logger.Clear();
1321 #endif
1322 
1323  // Pop NODEs containing previous shoves which are no longer necessary
1324  //
1325  ITEM_SET headSet;
1326  headSet.Add( aCurrentHead );
1327 
1328  VIA_HANDLE dummyVia;
1329 
1330  NODE* parent = reduceSpringback( headSet, dummyVia );
1331 
1332  // Create a new NODE to store this version of the world
1333  //
1334  m_currentNode = parent->Branch();
1336  m_currentNode->Add( head );
1337 
1338  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1339 
1340  if( !head.EndsWithVia() )
1341  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1342 
1343  head.Mark( MK_HEAD );
1344  head.SetRank( 100000 );
1345 
1346  if ( Dbg() )
1347  {
1348 
1349  Dbg()->BeginGroup( "initial" );
1350  Dbg()->AddLine(head.CLine(), 5, head.Width(), "head" );
1351  Dbg()->EndGroup();
1352  }
1353 
1354  if( head.EndsWithVia() )
1355  {
1356  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1357  headVia->Mark( MK_HEAD );
1358  headVia->SetRank( 100000 );
1359  m_currentNode->Add( std::move( headVia ) );
1360  }
1361 
1362  if( !pushLineStack( head ) )
1363  {
1364  delete m_currentNode;
1365  m_currentNode = parent;
1366 
1367  return SH_INCOMPLETE;
1368  }
1369 
1370  st = shoveMainLoop();
1371 
1372  if( st == SH_OK )
1373  {
1375 
1376  if( m_newHead )
1378  else
1379  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1380  }
1381 
1383 
1384  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1385  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1386 
1387  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1388  {
1390  }
1391  else
1392  {
1393  delete m_currentNode;
1394 
1395  m_currentNode = parent;
1396  m_newHead = OPT_LINE();
1397  }
1398 
1399  if(m_newHead)
1400  m_newHead->Unmark();
1401 
1402  if( m_newHead && head.EndsWithVia() )
1403  {
1404  VIA v = head.Via();
1405  v.SetPos( m_newHead->CPoint( -1 ) );
1406  m_newHead->AppendVia(v);
1407  }
1408 
1409  return st;
1410 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1327
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
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:162
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:693
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1582
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:78
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:721
void Clear()
Definition: pns_logger.cpp:47
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:1337
virtual void BeginGroup(const std::string name)
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
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:427
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1241
bool m_multiLineMode
Definition: pns_shove.h:175
OPT_LINE m_newHead
Definition: pns_shove.h:168
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
LOGGER m_logger
Definition: pns_shove.h:170
int m_iter
Definition: pns_shove.h:173
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1057

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

201 {
202  const SHAPE_LINE_CHAIN& obs = aObstacleLine.CLine();
203 
204  int attempt;
205 
206  for( attempt = 0; attempt < 4; attempt++ )
207  {
208  bool invertTraversal = ( attempt >= 2 );
209  bool clockwise = attempt % 2;
210  int vFirst = -1, vLast = -1;
211 
212  SHAPE_LINE_CHAIN path;
213  LINE l( aObstacleLine );
214 
215  for( int i = 0; i < (int) aHulls.size(); i++ )
216  {
217  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
218 
219  if( ! l.Walkaround( hull, path, clockwise ) )
220  {
221  wxLogTrace("PNS", "Fail-Walk %s %s %d\n", hull.Format().c_str(), l.CLine().Format().c_str(), clockwise? 1:0);
222  return SH_INCOMPLETE;
223  }
224 
225  path.Simplify();
226  l.SetShape( path );
227  }
228 
229  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
230  {
231  if( path.CPoint( i ) != obs.CPoint( i ) )
232  {
233  vFirst = i;
234  break;
235  }
236  }
237 
238  int k = obs.PointCount() - 1;
239  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
240  {
241  if( path.CPoint( i ) != obs.CPoint( k ) )
242  {
243  vLast = i;
244  break;
245  }
246  }
247 
248  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacleLine.CLine() ) )
249  {
250  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
251  continue;
252  }
253 
254  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
255  {
256  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
257  continue;
258  }
259 
260  if( !checkShoveDirection( aCurLine, aObstacleLine, l ) )
261  {
262  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
263  aResultLine.SetShape( l.CLine() );
264 
265  continue;
266  }
267 
268  if( path.SelfIntersecting() )
269  {
270  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
271  continue;
272  }
273 
274  bool colliding = l.Collide( &aCurLine, m_currentNode );
275 
276 #ifdef DEBUG
277  char str[128];
278  sprintf( str, "att-%d-shoved", attempt );
279  Dbg()->AddLine( l.CLine(), 3, 20000, str );
280 #endif
281 
282  if(( aCurLine.Marker() & MK_HEAD ) && !colliding )
283  {
284  JOINT* jtStart = m_currentNode->FindJoint( aCurLine.CPoint( 0 ), &aCurLine );
285 
286  for( ITEM* item : jtStart->LinkList() )
287  {
288  if( item->Collide( &l, m_currentNode ) )
289  colliding = true;
290  }
291  }
292 
293  if( colliding )
294  {
295  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
296  continue;
297  }
298 
299  aResultLine.SetShape( l.CLine() );
300 
301  return SH_OK;
302  }
303 
304  return SH_INCOMPLETE;
305 }
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
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:1027
SHAPE_LINE_CHAIN.
bool checkShoveDirection(const LINE &aCurLine, const LINE &aObstacleLine, const LINE &aShovedLine) const
Definition: pns_shove.cpp:134
NODE * m_currentNode
Definition: pns_shove.h:165
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const

References PNS::DEBUG_DECORATOR::AddLine(), checkShoveDirection(), PNS::LINE::CLine(), PNS::ITEM::Collide(), SHAPE_LINE_CHAIN::CompareGeometry(), 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, SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SelfIntersecting(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, SHAPE_LINE_CHAIN::Simplify(), and PNS::LINE::Walkaround().

Referenced by ShoveObstacleLine().

◆ shoveMainLoop()

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

Definition at line 1241 of file pns_shove.cpp.

1242 {
1243  SHOVE_STATUS st = SH_OK;
1244 
1246 
1247  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1249 
1250  int iterLimit = Settings().ShoveIterationLimit();
1251  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1252 
1253  m_iter = 0;
1254 
1255  timeLimit.Restart();
1256 
1257  if( m_lineStack.empty() && m_draggedVia )
1258  {
1259  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1260  // the stack.
1262  }
1263 
1264  while( !m_lineStack.empty() )
1265  {
1266  st = shoveIteration( m_iter );
1267 
1268  m_iter++;
1269 
1270  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1271  {
1272  st = SH_INCOMPLETE;
1273  break;
1274  }
1275  }
1276 
1277  return st;
1278 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
int JointCount() const
Return the number of nodes in the inheritance chain (wrs to the root node).
Definition: pns_node.h:188
NODE * m_root
Definition: pns_shove.h:164
ROUTING_SETTINGS & Settings() const
Return the logger object, allowing to dump geometry to a file.
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1104
VIA * m_draggedVia
Definition: pns_shove.h:171
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165
int m_iter
Definition: pns_shove.h:173
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 1413 of file pns_shove.cpp.

1414 {
1415  SHOVE_STATUS st = SH_OK;
1416 
1417  m_multiLineMode = true;
1418 
1419  ITEM_SET headSet;
1420 
1421  for( const ITEM* item : aHeadSet.CItems() )
1422  {
1423  const LINE* headOrig = static_cast<const LINE*>( item );
1424 
1425  // empty head? nothing to shove...
1426  if( !headOrig->SegmentCount() )
1427  return SH_INCOMPLETE;
1428 
1429  headSet.Add( *headOrig );
1430  }
1431 
1432  m_lineStack.clear();
1433  m_optimizerQueue.clear();
1434 #if 0
1435  m_logger.Clear();
1436 #endif
1437 
1438  VIA_HANDLE dummyVia;
1439 
1440  NODE* parent = reduceSpringback( headSet, dummyVia );
1441 
1442  m_currentNode = parent->Branch();
1444  int n = 0;
1445 
1446  for( const ITEM* item : aHeadSet.CItems() )
1447  {
1448  const LINE* headOrig = static_cast<const LINE*>( item );
1449  LINE head( *headOrig );
1450  head.ClearLinks();
1451 
1452  m_currentNode->Add( head );
1453 
1454  head.Mark( MK_HEAD );
1455  head.SetRank( 100000 );
1456  n++;
1457 
1458  if( !pushLineStack( head ) )
1459  return SH_INCOMPLETE;
1460 
1461  if( head.EndsWithVia() )
1462  {
1463  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1464  headVia->Mark( MK_HEAD );
1465  headVia->SetRank( 100000 );
1466  m_currentNode->Add( std::move( headVia ) );
1467  }
1468  }
1469 
1470  st = shoveMainLoop();
1471 
1472  if( st == SH_OK )
1474 
1476 
1477  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1478  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1479 
1480  if( st == SH_OK )
1481  {
1483  }
1484  else
1485  {
1486  delete m_currentNode;
1487  m_currentNode = parent;
1488  }
1489 
1490  return st;
1491 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION|MK_HOLE)
Definition: pns_node.cpp:1327
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1056
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
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:693
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1582
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:721
void Clear()
Definition: pns_logger.cpp:47
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1337
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
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:1241
bool m_multiLineMode
Definition: pns_shove.h:175
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161
NODE * m_currentNode
Definition: pns_shove.h:165
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Add an item to the current node.
Definition: pns_node.cpp:615
LOGGER m_logger
Definition: pns_shove.h:170
int m_iter
Definition: pns_shove.h:173

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

314 {
315  aResultLine.ClearLinks();
316 
317  bool obstacleIsHead = false;
318 
319  for( LINKED_ITEM* s : aObstacleLine.Links() )
320  {
321  if( s->Marker() & MK_HEAD )
322  {
323  obstacleIsHead = true;
324  break;
325  }
326  }
327 
328  SHOVE_STATUS rv;
329  bool viaOnEnd = aCurLine.EndsWithVia();
330 
331  if( viaOnEnd && ( !aCurLine.LayersOverlap( &aObstacleLine ) || aCurLine.SegmentCount() == 0 ) )
332  {
333  // Shove aObstacleLine to the hull of aCurLine's via.
334 
335  rv = shoveLineFromLoneVia( aCurLine, aObstacleLine, aResultLine );
336  }
337  else
338  {
339  // Build a set of hulls around the segments of aCurLine. Hulls are at the clearance
340  // distance + aObstacleLine's linewidth so that when re-walking aObstacleLine along the
341  // hull it will be at the appropriate clearance.
342 
343  int obstacleLineWidth = aObstacleLine.Width();
344  int clearance = getClearance( &aCurLine, &aObstacleLine ) + 1;
345  int currentLineSegmentCount = aCurLine.SegmentCount();
346  HULL_SET hulls;
347 
348  hulls.reserve( currentLineSegmentCount + 1 );
349 
350 #ifdef DEBUG
351  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d",
352  aCurLine.Net(),
353  aObstacleLine.Net(),
354  clearance ) );
355 #endif
356 
357  for( int i = 0; i < currentLineSegmentCount; i++ )
358  {
359  SEGMENT seg( aCurLine, aCurLine.CSegment( i ) );
360  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, obstacleLineWidth, aObstacleLine.Layer() );
361 
362  hulls.push_back( hull );
363  }
364 
365  if( viaOnEnd )
366  {
367  const VIA& via = aCurLine.Via();
368  int viaClearance = getClearance( &via, &aObstacleLine );
369  int holeClearance = getHoleClearance( &via, &aObstacleLine );
370 
371  if( holeClearance + via.Drill() / 2 > viaClearance + via.Diameter() / 2 )
372  viaClearance = holeClearance + via.Drill() / 2 - via.Diameter() / 2;
373 
374  hulls.push_back( aCurLine.Via().Hull( viaClearance, obstacleLineWidth ) );
375  }
376 
377 #ifdef DEBUG
378  char str[128];
379  sprintf( str, "current-cl-%d", clearance );
380  Dbg()->AddLine( aCurLine.CLine(), 5, 20000, str );
381 #endif
382 
383  rv = shoveLineToHullSet( aCurLine, aObstacleLine, aResultLine, hulls );
384  }
385 
386  if( obstacleIsHead )
387  aResultLine.Mark( aResultLine.Marker() | MK_HEAD );
388 
389  return rv;
390 }
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:199
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.
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:76
int getHoleClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:84
SHOVE_STATUS shoveLineFromLoneVia(const LINE &aCurLine, const LINE &aObstacleLine, LINE &aResultLine)
Definition: pns_shove.cpp:154

References PNS::DEBUG_DECORATOR::AddLine(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::VIA::Diameter(), PNS::VIA::Drill(), 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(), 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 1281 of file pns_shove.cpp.

1282 {
1283  OPT_BOX2I area;
1284 
1285  if( !m_nodeStack.empty() )
1286  area = m_nodeStack.back().m_affectedArea;
1287 
1288  if( area && m_affectedArea)
1289  area->Merge( *m_affectedArea );
1290  else if( !area )
1291  area = m_affectedArea;
1292 
1293  return area;
1294 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:152
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 1724 of file pns_shove.cpp.

1725 {
1726  auto iter = m_nodeStack.begin();
1727 
1728  while( iter != m_nodeStack.end() )
1729  {
1730  if ( iter->m_node == aNode )
1731  {
1732  iter->m_locked = false;
1733  break;
1734  }
1735  iter++;
1736  }
1737 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:160

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

Definition at line 1022 of file pns_shove.cpp.

1023 {
1024  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
1025  {
1026  if( i->ContainsLink( aSeg ) )
1027  i = m_lineStack.erase( i );
1028  else
1029  i++;
1030  }
1031 
1032  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1033  {
1034  if( i->ContainsLink( aSeg ) )
1035  i = m_optimizerQueue.erase( i );
1036  else
1037  i++;
1038  }
1039 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:162
std::vector< LINE > m_lineStack
Definition: pns_shove.h:161

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

1043 {
1044  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1045  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1046  else if( aItem->OfKind( ITEM::LINE_T ) )
1047  {
1048  LINE* l = static_cast<LINE*>( aItem );
1049 
1050  for( LINKED_ITEM* seg : l->Links() )
1051  unwindLineStack( seg );
1052  }
1053 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:1022

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  auto bb = m_router->VisibleViewArea();
42  return m_router->VisibleViewArea();
43 }
ROUTER * m_router
Definition: pns_algo_base.h:87
const BOX2I & VisibleViewArea() const
Definition: pns_router.h:225

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

Referenced by 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 171 of file pns_shove.h.

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

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

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

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 164 of file pns_shove.h.

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

◆ m_router


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