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
 

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

More...
 
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 ProcessSingleLine (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
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
 

Returns the instance of our router

More...
 
ROUTING_SETTINGSSettings () const
 

Returns current router settings

More...
 
void SetLogger (LOGGER *aLogger)
 
void SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
 Function SetDebugDecorator. More...
 
DEBUG_DECORATORDbg () 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 processHullSet (LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
 
NODEreduceSpringback (const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
 
bool pushSpringback (NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
 
SHOVE_STATUS walkaroundLoneVia (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
bool checkBumpDirection (const LINE &aCurrent, const LINE &aObstacle, const LINE &aShoved) 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
 
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 83 of file pns_shove.cpp.

83  :
84  ALGO_BASE( aRouter )
85 {
86  m_forceClearance = -1;
87  m_root = aWorld;
88  m_currentNode = aWorld;
89  SetDebugDecorator( aRouter->GetInterface()->GetDebugDecorator() );
90 
91  // Initialize other temporary variables:
93  m_iter = 0;
94  m_multiLineMode = false;
96 }
int m_restrictSpringbackTagId
Definition: pns_shove.h:163
NODE * m_root
Definition: pns_shove.h:161
#define NULL
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:42
VIA * m_draggedVia
Definition: pns_shove.h:168
void SetDebugDecorator(DEBUG_DECORATOR *aDecorator)
Function SetDebugDecorator.
Definition: pns_algo_base.h:72
bool m_multiLineMode
Definition: pns_shove.h:172
NODE * m_currentNode
Definition: pns_shove.h:162
int m_iter
Definition: pns_shove.h:170
int m_forceClearance
Definition: pns_shove.h:171

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

100 {
101 }

Member Function Documentation

◆ AddLockedSpringbackNode()

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

Definition at line 1637 of file pns_shove.cpp.

1638 {
1639  SPRINGBACK_TAG sp;
1640  sp.m_node = aNode;
1641  sp.m_locked = true;
1642 
1643  m_nodeStack.push_back(sp);
1644  return true;
1645 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

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

105 {
106  return m_currentNode->AssembleLine( const_cast<LINKED_ITEM*>( aSeg ), aIndex, true );
107 }
const LINE AssembleLine(LINKED_ITEM *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:897
NODE * m_currentNode
Definition: pns_shove.h:162

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

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

◆ checkBumpDirection()

bool PNS::SHOVE::checkBumpDirection ( const LINE aCurrent,
const LINE aObstacle,
const LINE aShoved 
) const
private

Definition at line 117 of file pns_shove.cpp.

118 {
119  SHAPE_LINE_CHAIN::POINT_INSIDE_TRACKER checker( aCurrent.CPoint(0) );
120  checker.AddPolyline( aObstacle.CLine() );
121  checker.AddPolyline( aShoved.CLine().Reverse() );
122 
123  bool inside = checker.IsInside();
124 
125  return !inside;
126 }
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 processHullSet().

◆ CurrentNode()

NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1616 of file pns_shove.cpp.

1617 {
1618  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1619 }
NODE * m_root
Definition: pns_shove.h:161
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

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

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

68 {
69  if( m_forceClearance >= 0 )
70  return m_forceClearance;
71 
72  return m_currentNode->GetClearance( aA, aB );
73 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:97
NODE * m_currentNode
Definition: pns_shove.h:162
int m_forceClearance
Definition: pns_shove.h:171

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

Referenced by onCollidingVia(), ProcessSingleLine(), and walkaroundLoneVia().

◆ Logger()

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

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

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

References m_logger.

◆ NewHead()

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

Definition at line 1622 of file pns_shove.cpp.

1623 {
1624  assert( m_newHead );
1625 
1626  return *m_newHead;
1627 }
OPT_LINE m_newHead
Definition: pns_shove.h:165

References m_newHead.

◆ onCollidingArc()

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

Definition at line 403 of file pns_shove.cpp.

404 {
405  int segIndex;
406  LINE obstacleLine = assembleLine( aObstacleArc, &segIndex );
407  LINE shovedLine( obstacleLine );
408  ARC tmp( *aObstacleArc );
409 
410  if( obstacleLine.HasLockedSegments() )
411  return SH_TRY_WALK;
412 
413  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
414 
415  const double extensionWalkThreshold = 1.0;
416 
417  double obsLen = obstacleLine.CLine().Length();
418  double shovedLen = shovedLine.CLine().Length();
419  double extensionFactor = 0.0;
420 
421  if( obsLen != 0.0f )
422  extensionFactor = shovedLen / obsLen - 1.0;
423 
424  if( extensionFactor > extensionWalkThreshold )
425  return SH_TRY_WALK;
426 
427  assert( obstacleLine.LayersOverlap( &shovedLine ) );
428 
429 #if 0
430  m_logger.NewGroup( "on-colliding-segment", m_iter );
431  m_logger.Log( &tmp, 0, "obstacle-segment" );
432  m_logger.Log( &aCurrent, 1, "current-line" );
433  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
434  m_logger.Log( &shovedLine, 3, "shoved-line" );
435 #endif
436 
437  if( rv == SH_OK )
438  {
439  if( shovedLine.Marker() & MK_HEAD )
440  {
441  if( m_multiLineMode )
442  return SH_INCOMPLETE;
443 
444  m_newHead = shovedLine;
445  }
446 
447  int rank = aCurrent.Rank();
448  shovedLine.SetRank( rank - 1 );
449 
450  sanityCheck( &obstacleLine, &shovedLine );
451  replaceLine( obstacleLine, shovedLine );
452 
453  if( !pushLineStack( shovedLine ) )
454  rv = SH_INCOMPLETE;
455  }
456 
457  return rv;
458 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:104
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:274
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:76
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
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:167
int m_iter
Definition: pns_shove.h:170

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingLine()

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

Definition at line 464 of file pns_shove.cpp.

465 {
466  LINE shovedLine( aObstacle );
467 
468  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
469 
470  #if 0
471  m_logger.NewGroup( "on-colliding-line", m_iter );
472  m_logger.Log( &aObstacle, 0, "obstacle-line" );
473  m_logger.Log( &aCurrent, 1, "current-line" );
474  m_logger.Log( &shovedLine, 3, "shoved-line" );
475  #endif
476 
477  if( rv == SH_OK )
478  {
479  if( shovedLine.Marker() & MK_HEAD )
480  {
481  if( m_multiLineMode )
482  return SH_INCOMPLETE;
483 
484  m_newHead = shovedLine;
485  }
486 
487  sanityCheck( &aObstacle, &shovedLine );
488  replaceLine( aObstacle, shovedLine );
489 
490  int rank = aObstacle.Rank();
491  shovedLine.SetRank( rank - 1 );
492 
493 
494  if( !pushLineStack( shovedLine ) )
495  {
496  rv = SH_INCOMPLETE;
497  }
498  }
499 
500  return rv;
501 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:274
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:76
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
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:167
int m_iter
Definition: pns_shove.h:170

References PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, and SH_OK.

Referenced by shoveIteration().

◆ onCollidingSegment()

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

Definition at line 342 of file pns_shove.cpp.

343 {
344  int segIndex;
345  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
346  LINE shovedLine( obstacleLine );
347  SEGMENT tmp( *aObstacleSeg );
348 
349  if( obstacleLine.HasLockedSegments() )
350  return SH_TRY_WALK;
351 
352  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
353 
354  const double extensionWalkThreshold = 1.0;
355 
356  double obsLen = obstacleLine.CLine().Length();
357  double shovedLen = shovedLine.CLine().Length();
358  double extensionFactor = 0.0;
359 
360  if( obsLen != 0.0f )
361  extensionFactor = shovedLen / obsLen - 1.0;
362 
363  if( extensionFactor > extensionWalkThreshold )
364  return SH_TRY_WALK;
365 
366  assert( obstacleLine.LayersOverlap( &shovedLine ) );
367 
368 #if 0
369  m_logger.NewGroup( "on-colliding-segment", m_iter );
370  m_logger.Log( &tmp, 0, "obstacle-segment" );
371  m_logger.Log( &aCurrent, 1, "current-line" );
372  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
373  m_logger.Log( &shovedLine, 3, "shoved-line" );
374 #endif
375 
376  if( rv == SH_OK )
377  {
378  if( shovedLine.Marker() & MK_HEAD )
379  {
380  if( m_multiLineMode )
381  return SH_INCOMPLETE;
382 
383  m_newHead = shovedLine;
384  }
385 
386  int rank = aCurrent.Rank();
387  shovedLine.SetRank( rank - 1 );
388 
389  sanityCheck( &obstacleLine, &shovedLine );
390  replaceLine( obstacleLine, shovedLine );
391 
392  if( !pushLineStack( shovedLine ) )
393  rv = SH_INCOMPLETE;
394  }
395 
396  return rv;
397 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:104
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:274
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:76
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
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:167
int m_iter
Definition: pns_shove.h:170

References assembleLine(), PNS::LINE::CLine(), PNS::LINE::HasLockedSegments(), PNS::ITEM::LayersOverlap(), SHAPE_LINE_CHAIN::Length(), PNS::LOGGER::Log(), m_iter, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Marker(), PNS::MK_HEAD, ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

◆ onCollidingSolid()

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

Definition at line 507 of file pns_shove.cpp.

508 {
509  WALKAROUND walkaround( m_currentNode, Router() );
510  LINE walkaroundLine( aCurrent );
511 
512  if( aCurrent.EndsWithVia() )
513  {
514  VIA vh = aCurrent.Via();
515  VIA* via = NULL;
516  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
517 
518  if( !jtStart )
519  return SH_INCOMPLETE;
520 
521  for( ITEM* item : jtStart->LinkList() )
522  {
523  if( item->OfKind( ITEM::VIA_T ) )
524  {
525  via = (VIA*) item;
526  break;
527  }
528  }
529 
530  if( via && m_currentNode->CheckColliding( via, aObstacle ) )
531  return onCollidingVia( aObstacle, via );
532  }
533 
534  TOPOLOGY topo( m_currentNode );
535 
536  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
537 
538 #if 0
539  m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
540  for( ITEM* item : cluster )
541  {
542  m_logger.Log( item, 0, "cluster-entry" );
543  }
544 #endif
545 
546  walkaround.SetSolidsOnly( false );
547  walkaround.RestrictToSet( true, cluster );
548  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
549 
550  int currentRank = aCurrent.Rank();
551  int nextRank;
552 
553  bool success = false;
554 
555  for( int attempt = 0; attempt < 2; attempt++ )
556  {
557  if( attempt == 1 || Settings().JumpOverObstacles() )
558  {
559 
560  nextRank = currentRank - 1;
561  walkaround.SetSingleDirection( true );
562  }
563  else
564  {
565  nextRank = currentRank + 10000;
566  walkaround.SetSingleDirection( false );
567  }
568 
569 
570  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
571 
572  if( status != WALKAROUND::DONE )
573  continue;
574 
575  walkaroundLine.ClearLinks();
576  walkaroundLine.Unmark();
577  walkaroundLine.Line().Simplify();
578 
579  if( walkaroundLine.HasLoops() )
580  continue;
581 
582  if( aCurrent.Marker() & MK_HEAD )
583  {
584  walkaroundLine.Mark( MK_HEAD );
585 
586  if( m_multiLineMode )
587  continue;
588 
589  m_newHead = walkaroundLine;
590  }
591 
592  sanityCheck( &aCurrent, &walkaroundLine );
593 
594  if( !m_lineStack.empty() )
595  {
596  LINE lastLine = m_lineStack.front();
597 
598  if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
599  {
600  LINE dummy( lastLine );
601 
602  if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
603  {
604  success = true;
605  break;
606  }
607  } else {
608  success = true;
609  break;
610  }
611  }
612  }
613 
614  if(!success)
615  return SH_INCOMPLETE;
616 
617  replaceLine( aCurrent, walkaroundLine );
618  walkaroundLine.SetRank( nextRank );
619 
620 #if 0
621  m_logger.NewGroup( "on-colliding-solid", m_iter );
622  m_logger.Log( aObstacle, 0, "obstacle-solid" );
623  m_logger.Log( &aCurrent, 1, "current-line" );
624  m_logger.Log( &walkaroundLine, 3, "walk-line" );
625 #endif
626 
627  popLineStack();
628 
629  if( !pushLineStack( walkaroundLine ) )
630  return SH_INCOMPLETE;
631 
632  return SH_OK;
633 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:51
void popLineStack()
Definition: pns_shove.cpp:1043
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:274
ROUTING_SETTINGS & Settings() const
Returns current router settings
#define NULL
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:832
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:76
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1031
static LIB_PART * dummy()
Used to draw a dummy shape when a LIB_PART is not found in library.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References PNS::TOPOLOGY::AssembleCluster(), PNS::NODE::CheckColliding(), PNS::LINK_HOLDER::ClearLinks(), PNS::WALKAROUND::DONE, dummy(), PNS::LINE::EndsWithVia(), PNS::NODE::FindJoint(), PNS::LINE::HasLoops(), PNS::ITEM::Layers(), PNS::LINE::Line(), PNS::JOINT::LinkList(), PNS::LOGGER::Log(), m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, NULL, onCollidingVia(), popLineStack(), PNS::VIA::Pos(), ProcessSingleLine(), 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, 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 832 of file pns_shove.cpp.

833 {
834  int clearance = getClearance( aCurrent, aObstacleVia ) + PNS_HULL_MARGIN;
835  LINE_PAIR_VEC draggedLines;
836  bool lineCollision = false;
837  bool viaCollision = false;
838  bool holeCollision = false;
839  LINE* currentLine = NULL;
840  VECTOR2I mtvLine; // Minimum translation vector to correct line collisions
841  VECTOR2I mtvVia; // MTV to correct via collisions
842  VECTOR2I mtvHoles; // MTV to correct hole collisions
843  VECTOR2I mtvSolid; // MTV to correct solid collisions
844  VECTOR2I mtv; // Union of relevant MTVs (will correct all collisions)
845  int rank = -1;
846 
847  if( aCurrent->OfKind( ITEM::LINE_T ) )
848  {
849 #if 0
850  m_logger.NewGroup( "push-via-by-line", m_iter );
851  m_logger.Log( aCurrent, 4, "current" );
852 #endif
853 
854  currentLine = (LINE*) aCurrent;
855  lineCollision = aObstacleVia->Shape()->Collide( currentLine->Shape(),
856  clearance + currentLine->Width() / 2,
857  &mtvLine );
858 
859  if( currentLine->EndsWithVia() )
860  {
861  int currentNet = currentLine->Net();
862  int obstacleNet = aObstacleVia->Net();
863 
864  if( currentNet != obstacleNet && currentNet >= 0 && obstacleNet >= 0 )
865  {
866  viaCollision = currentLine->Via().Shape()->Collide( aObstacleVia->Shape(),
867  clearance, &mtvVia );
868  }
869 
870  // hole-to-hole is a mechanical constraint (broken drill bits), not an electrical
871  // one, so it has to be checked irrespective of matching nets.
872 
873  // temporarily removed hole-to-hole collision check due to conflicts with the springback algorithm...
874  // we need to figure out a better solution here - TW
875  holeCollision = false; //rr->CollideHoles( &currentLine->Via(), aObstacleVia, true, &mtvHoles );
876  }
877 
878  // These aren't /actually/ lengths as we don't bother to do the square-root part,
879  // but we're just comparing them to each other so it's faster this way.
880  ecoord lineMTVLength = lineCollision ? mtvLine.SquaredEuclideanNorm() : 0;
881  ecoord viaMTVLength = viaCollision ? mtvVia.SquaredEuclideanNorm() : 0;
882  ecoord holeMTVLength = holeCollision ? mtvHoles.SquaredEuclideanNorm() : 0;
883 
884  if( lineMTVLength >= viaMTVLength && lineMTVLength >= holeMTVLength )
885  mtv = mtvLine;
886  else if( viaMTVLength >= lineMTVLength && viaMTVLength >= holeMTVLength )
887  mtv = mtvVia;
888  else
889  mtv = mtvHoles;
890 
891  rank = currentLine->Rank();
892  }
893  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
894  {
895  aObstacleVia->Shape()->Collide( aCurrent->Shape(), clearance, &mtvSolid );
896  mtv = -mtvSolid;
897  rank = aCurrent->Rank() + 10000;
898  }
899 
900  return pushOrShoveVia( aObstacleVia, mtv, rank );
901 }
#define PNS_HULL_MARGIN
LINE.
Definition: pns_line.h:60
extended_type SquaredEuclideanNorm() const
Function Squared Euclidean Norm computes the squared euclidean norm of the vector,...
Definition: vector2d.h:306
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:705
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
#define NULL
VECTOR2I::extended_type ecoord
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:67
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

References SHAPE::Collide(), PNS::LINE::EndsWithVia(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::ITEM::Net(), NULL, PNS::ITEM::OfKind(), PNS_HULL_MARGIN, pushOrShoveVia(), PNS::ITEM::Rank(), PNS::LINE::Rank(), PNS::LINE::Shape(), PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, VECTOR2< T >::SquaredEuclideanNorm(), 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 907 of file pns_shove.cpp.

908 {
909  int n = 0;
910  LINE cur( aCurrent );
911  cur.ClearLinks();
912 
913  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
914  LINE shoved( aCurrent );
915  shoved.ClearLinks();
916 
917  cur.RemoveVia();
918  unwindLineStack( &aCurrent );
919 
920  for( ITEM* item : jt->LinkList() )
921  {
922  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) && item->LayersOverlap( &aCurrent ) )
923  {
924  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
925  LINE head = assembleLine( li );
926 
927  head.AppendVia( *aObstacleVia );
928 
929  SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
930 
931  if( st != SH_OK )
932  {
933 #if 0
934  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
935  m_logger.Log( aObstacleVia, 0, "the-via" );
936  m_logger.Log( &aCurrent, 1, "current-line" );
937  m_logger.Log( &shoved, 3, "shoved-line" );
938 #endif
939 
940  return st;
941  }
942 
943  cur.SetShape( shoved.CLine() );
944  n++;
945  }
946  }
947 
948  if( !n )
949  {
950 #if 0
951  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
952  m_logger.Log( aObstacleVia, 0, "the-via" );
953  m_logger.Log( &aCurrent, 1, "current-line" );
954 #endif
955 
956  LINE head( aCurrent );
957  head.Line().Clear();
958  head.AppendVia( *aObstacleVia );
959  head.ClearLinks();
960 
961  SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
962 
963  if( st != SH_OK )
964  return st;
965 
966  cur.SetShape( shoved.CLine() );
967  }
968 
969  if( aCurrent.EndsWithVia() )
970  shoved.AppendVia( aCurrent.Via() );
971 
972 #if 0
973  m_logger.NewGroup( "on-reverse-via", m_iter );
974  m_logger.Log( aObstacleVia, 0, "the-via" );
975  m_logger.Log( &aCurrent, 1, "current-line" );
976  m_logger.Log( &shoved, 3, "shoved-line" );
977 #endif
978  int currentRank = aCurrent.Rank();
979  replaceLine( aCurrent, shoved );
980 
981  if( !pushLineStack( shoved ) )
982  return SH_INCOMPLETE;
983 
984  shoved.SetRank( currentRank );
985 
986  return SH_OK;
987 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:104
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:990
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:274
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1031
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
NODE * m_currentNode
Definition: pns_shove.h:162
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

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(), ProcessSingleLine(), pushLineStack(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, unwindLineStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

◆ popLineStack()

void PNS::SHOVE::popLineStack ( )
private

Definition at line 1043 of file pns_shove.cpp.

1044 {
1045  LINE& l = m_lineStack.back();
1046 
1047  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
1048  {
1049  bool found = false;
1050 
1051  for( auto s : l.Links() )
1052  {
1053  if( i->ContainsLink( s ) )
1054  {
1055  i = m_optimizerQueue.erase( i );
1056  found = true;
1057  break;
1058  }
1059  }
1060 
1061  if( !found )
1062  i++;
1063  }
1064 
1065  m_lineStack.pop_back();
1066 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

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

Referenced by onCollidingSolid(), and shoveIteration().

◆ processHullSet()

SHOVE::SHOVE_STATUS PNS::SHOVE::processHullSet ( LINE aCurrent,
LINE aObstacle,
LINE aShoved,
const HULL_SET hulls 
)
private

Definition at line 165 of file pns_shove.cpp.

167 {
168  const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
169 
170  int attempt;
171 
172  for( attempt = 0; attempt < 4; attempt++ )
173  {
174  bool invertTraversal = ( attempt >= 2 );
175  bool clockwise = attempt % 2;
176  int vFirst = -1, vLast = -1;
177 
178  SHAPE_LINE_CHAIN path;
179  LINE l( aObstacle );
180 
181  for( int i = 0; i < (int) aHulls.size(); i++ )
182  {
183  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
184 
185  if( ! l.Walkaround( hull, path, clockwise ) )
186  return SH_INCOMPLETE;
187 
188  path.Simplify();
189  l.SetShape( path );
190  }
191 
192  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
193  {
194  if( path.CPoint( i ) != obs.CPoint( i ) )
195  {
196  vFirst = i;
197  break;
198  }
199  }
200 
201  int k = obs.PointCount() - 1;
202  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
203  {
204  if( path.CPoint( i ) != obs.CPoint( k ) )
205  {
206  vLast = i;
207  break;
208  }
209  }
210 
211  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
212  {
213  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
214  continue;
215  }
216 
217  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
218  {
219  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
220  continue;
221  }
222 
223  if( !checkBumpDirection( aCurrent, aObstacle, l ) )
224  {
225  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
226  aShoved.SetShape( l.CLine() );
227 
228  continue;
229  }
230 
231  if( path.SelfIntersecting() )
232  {
233  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
234  continue;
235  }
236 
237  bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
238 
239 #ifdef DEBUG
240  char str[128];
241  sprintf( str, "att-%d-shoved", attempt );
242  Dbg()->AddLine( l.CLine(), 3, 20000, str );
243 #endif
244 
245  if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
246  {
247  JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
248 
249  for( ITEM* item : jtStart->LinkList() )
250  {
251  if( m_currentNode->CheckColliding( item, &l ) )
252  colliding = true;
253  }
254  }
255 
256  if( colliding )
257  {
258  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
259  continue;
260  }
261 
262  aShoved.SetShape( l.CLine() );
263 
264  return SH_OK;
265  }
266 
267  return SH_INCOMPLETE;
268 }
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
bool checkBumpDirection(const LINE &aCurrent, const LINE &aObstacle, const LINE &aShoved) const
Definition: pns_shove.cpp:117
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1031
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
NODE * m_currentNode
Definition: pns_shove.h:162
int m_forceClearance
Definition: pns_shove.h:171
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const

References PNS::DEBUG_DECORATOR::AddLine(), PNS::ITEM::ANY_T, checkBumpDirection(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), SHAPE_LINE_CHAIN::CompareGeometry(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), PNS::ALGO_BASE::Dbg(), PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_currentNode, m_forceClearance, 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 ProcessSingleLine().

◆ ProcessSingleLine()

SHOVE::SHOVE_STATUS PNS::SHOVE::ProcessSingleLine ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)

Definition at line 274 of file pns_shove.cpp.

275 {
276  aShoved.ClearLinks();
277 
278  bool obstacleIsHead = false;
279 
280  for( auto s : aObstacle.Links() )
281  {
282  if( s->Marker() & MK_HEAD )
283  {
284  obstacleIsHead = true;
285  break;
286  }
287  }
288 
289  SHOVE_STATUS rv;
290 
291  bool viaOnEnd = aCurrent.EndsWithVia();
292 
293  if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
294  {
295  rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
296  }
297  else
298  {
299  int w = aObstacle.Width();
300  int n_segs = aCurrent.SegmentCount();
301 
302  int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
303 
304 #ifdef DEBUG
305  Dbg()->Message( wxString::Format( "shove process-single: cur net %d obs %d cl %d", aCurrent.Net(), aObstacle.Net(), clearance ) );
306 #endif
307 
308  HULL_SET hulls;
309 
310  hulls.reserve( n_segs + 1 );
311 
312  for( int i = 0; i < n_segs; i++ )
313  {
314  SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
315  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w, aObstacle.Layer() );
316 
317  hulls.push_back( hull );
318  }
319 
320  if( viaOnEnd )
321  hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
322 
323 #ifdef DEBUG
324  char str[128];
325  sprintf( str, "current-cl-%d", clearance );
326  Dbg()->AddLine( aCurrent.CLine(), 5, 20000, str );
327 #endif
328 
329  rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
330  }
331 
332  if( obstacleIsHead )
333  aShoved.Mark( aShoved.Marker() | MK_HEAD );
334 
335  return rv;
336 }
virtual void AddLine(const SHAPE_LINE_CHAIN &aLine, int aType=0, int aWidth=0, const std::string aName="")
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:165
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:94
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
virtual void Message(const wxString msg)
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, CPTREE &aTree)
Function Format outputs a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition: ptree.cpp:201
SHAPE_LINE_CHAIN.
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:67
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:129

References PNS::DEBUG_DECORATOR::AddLine(), PNS::LINK_HOLDER::ClearLinks(), PNS::LINE::CLine(), PNS::LINE::CSegment(), PNS::ALGO_BASE::Dbg(), PNS::LINE::EndsWithVia(), Format(), getClearance(), 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(), processHullSet(), PNS::LINE::SegmentCount(), PNS::LINE::Via(), walkaroundLoneVia(), and PNS::LINE::Width().

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

◆ pushLineStack()

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

Definition at line 1024 of file pns_shove.cpp.

1025 {
1026  if( !aL.IsLinkedChecked() && aL.SegmentCount() != 0 )
1027  return false;
1028 
1029  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
1030  {
1031  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
1032  }
1033  else
1034  {
1035  m_lineStack.push_back( aL );
1036  }
1037 
1038  m_optimizerQueue.push_back( aL );
1039 
1040  return true;
1041 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

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

706 {
707  LINE_PAIR_VEC draggedLines;
708  VECTOR2I p0( aVia->Pos() );
709  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
710  VECTOR2I p0_pushed( p0 + aForce );
711 
712  // nothing to do...
713  if ( aForce.x == 0 && aForce.y == 0 )
714  return SH_OK;
715 
716  if( !jt )
717  {
718  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
719  return SH_INCOMPLETE;
720  }
721 
722  if( aVia->IsLocked() )
723  return SH_TRY_WALK;
724 
725  if( jt->IsLocked() )
726  return SH_INCOMPLETE;
727 
728  // make sure pushed via does not overlap with any existing joint
729  while( true )
730  {
731  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
732 
733  if( !jt_next )
734  break;
735 
736  p0_pushed += aForce.Resize( 2 );
737  }
738 
739  std::unique_ptr<VIA> pushedVia = Clone( *aVia );
740  pushedVia->SetPos( p0_pushed );
741  pushedVia->Mark( aVia->Marker() );
742 
743  for( ITEM* item : jt->LinkList() )
744  {
745  if( item->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
746  {
747  LINKED_ITEM* li = static_cast<LINKED_ITEM*>( item );
748  LINE_PAIR lp;
749  int segIndex;
750 
751  lp.first = assembleLine( li, &segIndex );
752 
753  if( lp.first.HasLockedSegments() )
754  return SH_TRY_WALK;
755 
756  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
757 
758  if( segIndex == 0 )
759  lp.first.Reverse();
760 
761  lp.second = lp.first;
762  lp.second.ClearLinks();
763  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
764  lp.second.AppendVia( *pushedVia );
765  draggedLines.push_back( lp );
766  }
767  }
768 
769 #if 0
770  m_logger.Log( aVia, 0, "obstacle-via" );
771 #endif
772 
773  pushedVia->SetRank( aCurrentRank - 1 );
774 
775 #if 0
776  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
777 #endif
778 
779  if( aVia->Marker() & MK_HEAD ) // push
780  {
781  m_draggedVia = pushedVia.get();
782  }
783  else
784  { // shove
785  if( jt->IsStitchingVia() )
786  pushLineStack( LINE( *pushedVia ) );
787  }
788 
789  replaceItems( aVia, std::move( pushedVia ) );
790 
791  for( LINE_PAIR lp : draggedLines )
792  {
793  if( lp.first.Marker() & MK_HEAD )
794  {
795  lp.second.Mark( MK_HEAD );
796 
797  if( m_multiLineMode )
798  return SH_INCOMPLETE;
799 
800  m_newHead = lp.second;
801  }
802 
803  unwindLineStack( &lp.first );
804 
805  if( lp.second.SegmentCount() )
806  {
807  replaceLine( lp.first, lp.second );
808  lp.second.SetRank( aCurrentRank - 1 );
809 
810  if( !pushLineStack( lp.second, true ) )
811  return SH_INCOMPLETE;
812  }
813  else
814  {
815  m_currentNode->Remove( lp.first );
816  }
817 
818 #if 0
819  m_logger.Log( &lp.first, 2, "fan-pre" );
820  m_logger.Log( &lp.second, 3, "fan-post" );
821 #endif
822  }
823 
824  return SH_OK;
825 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:136
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:104
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:990
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:96
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:800
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:97
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:1031
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:276
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:392
VIA * m_draggedVia
Definition: pns_shove.h:168
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:57
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:47
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
NODE * m_currentNode
Definition: pns_shove.h:162
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
LOGGER m_logger
Definition: pns_shove.h:167

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

669 {
670  SPRINGBACK_TAG st;
671  OPT_BOX2I prev_area;
672 
673  if( !m_nodeStack.empty() )
674  prev_area = m_nodeStack.back().m_affectedArea;
675 
676  if( aDraggedVia )
677  {
678  st.m_draggedVia = aDraggedVia->MakeHandle();
679  }
680 
681  st.m_node = aNode;
682 
683  if( aAffectedArea )
684  {
685  if( prev_area )
686  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
687  else
688  st.m_affectedArea = aAffectedArea;
689  } else
690  st.m_affectedArea = prev_area;
691 
692  st.m_seq = (m_nodeStack.empty() ? 1 : m_nodeStack.back().m_seq + 1);
693  st.m_locked = false;
694 
695  m_nodeStack.push_back( st );
696 
697  return true;
698 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157
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 640 of file pns_shove.cpp.

641 {
642  while( !m_nodeStack.empty() )
643  {
644  SPRINGBACK_TAG& spTag = m_nodeStack.back();
645 
646  auto obs = spTag.m_node->CheckColliding( aHeadSet );
647 
648  if( !obs && !spTag.m_locked )
649  {
650  aDraggedVia = spTag.m_draggedVia;
651  aDraggedVia.valid = true;
652 
653  delete spTag.m_node;
654  m_nodeStack.pop_back();
655  }
656  else
657  break;
658  }
659 
660  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
661 }
NODE * m_root
Definition: pns_shove.h:161
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

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

48 {
49  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
50 
51  if( changed_area )
52  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
53 
54  m_currentNode->Replace( aOld, std::move( aNew ) );
55 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:770
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:162

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

58 {
59  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
60 
61  if( changed_area )
62  m_affectedArea = m_affectedArea ? m_affectedArea->Merge( *changed_area ) : *changed_area;
63 
64  m_currentNode->Replace( aOld, aNew );
65 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:290
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:770
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ChangedArea(), 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 1648 of file pns_shove.cpp.

1649 {
1650  bool found = false;
1651 
1652  auto iter = m_nodeStack.begin();
1653 
1654  while( iter != m_nodeStack.end() )
1655  {
1656  if ( iter->m_node == aNode )
1657  {
1658  found = true;
1659  break;
1660  }
1661  iter++;
1662  }
1663 
1664  if( !found )
1665  return false;
1666 
1667  auto start = iter;
1668 
1669  aNode->KillChildren();
1670  m_nodeStack.erase( start, m_nodeStack.end() );
1671 
1672  return true;
1673 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

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

◆ Router()

◆ runOptimizer()

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

Definition at line 1545 of file pns_shove.cpp.

1546 {
1547  OPTIMIZER optimizer( aNode );
1548  int optFlags = 0;
1549  int n_passes = 0;
1550 
1552 
1553  OPT_BOX2I area = totalAffectedArea();
1554 
1555  int maxWidth = 0;
1556 
1557  for( LINE& line : m_optimizerQueue )
1558  maxWidth = std::max( line.Width(), maxWidth );
1559 
1560  if( area )
1561  area->Inflate( 10 * maxWidth );
1562 
1563  switch( effort )
1564  {
1565  case OE_LOW:
1566  optFlags = OPTIMIZER::MERGE_OBTUSE;
1567  n_passes = 1;
1568  break;
1569 
1570  case OE_MEDIUM:
1571  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1572 
1573  if( area )
1574  optimizer.SetRestrictArea( *area );
1575 
1576  n_passes = 2;
1577  break;
1578 
1579  case OE_FULL:
1580  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1581  n_passes = 2;
1582  break;
1583 
1584  default:
1585  break;
1586  }
1587 
1588  if( Settings().SmartPads() )
1589  optFlags |= OPTIMIZER::SMART_PADS;
1590 
1591  optimizer.SetEffortLevel( optFlags );
1592  optimizer.SetCollisionMask( ITEM::ANY_T );
1593 
1594  for( int pass = 0; pass < n_passes; pass++ )
1595  {
1596  std::reverse( m_optimizerQueue.begin(), m_optimizerQueue.end() );
1597 
1598  for( LINE& line : m_optimizerQueue)
1599  {
1600  if( !( line.Marker() & MK_HEAD ) )
1601  {
1602  LINE optimized;
1603 
1604  if( optimizer.Optimize( &line, &optimized ) )
1605  {
1606  aNode->Remove( line );
1607  line.SetShape( optimized.CLine() );
1608  aNode->Add( line );
1609  }
1610  }
1611  }
1612  }
1613 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
ROUTING_SETTINGS & Settings() const
Returns current router settings
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1250
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
PNS_OPTIMIZATION_EFFORT
Optimization effort
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525

References PNS::NODE::Add(), PNS::ITEM::ANY_T, PNS::LINE::CLine(), 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::SetCollisionMask(), PNS::OPTIMIZER::SetEffortLevel(), PNS::OPTIMIZER::SetRestrictArea(), PNS::ALGO_BASE::Settings(), PNS::OPTIMIZER::SMART_PADS, and totalAffectedArea().

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

◆ sanityCheck()

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

Definition at line 76 of file pns_shove.cpp.

77 {
78  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
79  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
80 }

References PNS::LINE::CPoint().

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

◆ SetDebugDecorator()

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

Function SetDebugDecorator.

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

Definition at line 72 of file pns_algo_base.h.

73  {
74  m_debugDecorator = aDecorator;
75  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:83

References PNS::ALGO_BASE::m_debugDecorator.

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

◆ SetInitialLine()

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

Definition at line 1630 of file pns_shove.cpp.

1631 {
1632  m_root = m_root->Branch();
1633  m_root->Remove( aInitial );
1634 }
NODE * m_root
Definition: pns_shove.h:161
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
void Remove(ARC *aArc)
Function Remove()
Definition: pns_node.cpp:800

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

◆ SetLogger()

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

Definition at line 62 of file pns_algo_base.h.

63  {
64  m_logger = aLogger;
65  }
LOGGER * m_logger
Definition: pns_algo_base.h:85

References PNS::ALGO_BASE::m_logger.

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

◆ Settings()

◆ ShoveDraggingVia()

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

Definition at line 1473 of file pns_shove.cpp.

1474 {
1475  SHOVE_STATUS st = SH_OK;
1476 
1477  m_lineStack.clear();
1478  m_optimizerQueue.clear();
1479  m_newHead = OPT_LINE();
1480  m_draggedVia = NULL;
1481 
1482  auto viaToDrag = findViaByHandle( m_currentNode, aOldVia );
1483 
1484  if( !viaToDrag )
1485  {
1486  return SH_INCOMPLETE;
1487  }
1488 
1489  // Pop NODEs containing previous shoves which are no longer necessary
1490  ITEM_SET headSet;
1491 
1492  VIA headVia ( *viaToDrag );
1493  headVia.SetPos( aWhere );
1494  headSet.Add( headVia );
1495  VIA_HANDLE prevViaHandle;
1496  NODE* parent = reduceSpringback( headSet, prevViaHandle );
1497 
1498  if( prevViaHandle.valid )
1499  {
1500  aNewVia = prevViaHandle;
1501  viaToDrag = findViaByHandle( parent, prevViaHandle );
1502  }
1503 
1504  // Create a new NODE to store this version of the world
1505  //
1506  m_currentNode = parent->Branch();
1508 
1509  viaToDrag->Mark( MK_HEAD );
1510  viaToDrag->SetRank( 100000 );
1511 
1512  // Push the via to its new location
1513  //
1514  st = pushOrShoveVia( viaToDrag, ( aWhere - viaToDrag->Pos()), 0 );
1515 
1516  // Shove any colliding objects out of the way
1517  //
1518  if( st == SH_OK )
1519  st = shoveMainLoop();
1520 
1521  if( st == SH_OK )
1523 
1524  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1525  {
1526  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1527 
1528  if (!m_draggedVia)
1529  m_draggedVia = viaToDrag;
1530 
1531  aNewVia = m_draggedVia->MakeHandle();
1532 
1534  }
1535  else
1536  {
1537  delete m_currentNode;
1538  m_currentNode = parent;
1539  }
1540 
1541  return st;
1542 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1321
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
const VIA_HANDLE MakeHandle() const
Definition: pns_via.cpp:119
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
SHOVE_STATUS pushOrShoveVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank)
Definition: pns_shove.cpp:705
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:640
#define NULL
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1545
static VIA * findViaByHandle(NODE *aNode, const VIA_HANDLE &handle)
Definition: pns_shove.cpp:1454
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:668
VIA * m_draggedVia
Definition: pns_shove.h:168
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1210
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162

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::MK_HEAD, NULL, pushOrShoveVia(), pushSpringback(), reduceSpringback(), runOptimizer(), PNS::VIA::SetPos(), 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 1072 of file pns_shove.cpp.

1073 {
1074  LINE currentLine = m_lineStack.back();
1075  NODE::OPT_OBSTACLE nearest;
1076  SHOVE_STATUS st = SH_NULL;
1077 
1078 #ifdef DEBUG
1079  Dbg()->SetIteration( aIter );
1080 #endif
1081 
1082  for( ITEM::PnsKind search_order : { ITEM::SOLID_T, ITEM::VIA_T, ITEM::SEGMENT_T } )
1083  {
1084  nearest = m_currentNode->NearestObstacle( &currentLine, search_order );
1085 
1086  if( nearest )
1087  break;
1088  }
1089 
1090  if( !nearest )
1091  {
1092  m_lineStack.pop_back();
1093  return SH_OK;
1094  }
1095 
1096  ITEM* ni = nearest->m_item;
1097 
1098  unwindLineStack( ni );
1099 
1100  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
1101  {
1102  // Collision with a higher-ranking object (ie: one that we've already shoved)
1103  //
1104  switch( ni->Kind() )
1105  {
1106  case ITEM::VIA_T:
1107  {
1108  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
1109 
1110  if( currentLine.EndsWithVia()
1111  && m_currentNode->CheckColliding( &currentLine.Via(), (VIA*) ni ) )
1112  {
1113  st = SH_INCOMPLETE;
1114  }
1115  else
1116  {
1117  st = onReverseCollidingVia( currentLine, (VIA*) ni );
1118  }
1119 
1120  break;
1121  }
1122 
1123  case ITEM::SEGMENT_T:
1124  {
1125  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
1126  LINE revLine = assembleLine( static_cast<SEGMENT*>( ni ) );
1127 
1128  popLineStack();
1129  st = onCollidingLine( revLine, currentLine );
1130  if( !pushLineStack( revLine ) )
1131  return SH_INCOMPLETE;
1132 
1133  break;
1134  }
1135 
1136  case ITEM::ARC_T:
1137  {
1138  //TODO(snh): Handle Arc shove separate from track
1139  wxLogTrace( "PNS", "iter %d: reverse-collide-arc ", aIter );
1140  LINE revLine = assembleLine( static_cast<ARC*>( ni ) );
1141 
1142  popLineStack();
1143  st = onCollidingLine( revLine, currentLine );
1144  if( !pushLineStack( revLine ) )
1145  return SH_INCOMPLETE;
1146 
1147  break;
1148  }
1149 
1150  default:
1151  assert( false );
1152  }
1153  }
1154  else
1155  {
1156  // Collision with a lower-ranking object or a solid
1157  //
1158  switch( ni->Kind() )
1159  {
1160  case ITEM::SEGMENT_T:
1161  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
1162 
1163  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
1164 
1165  if( st == SH_TRY_WALK )
1166  st = onCollidingSolid( currentLine, ni );
1167 
1168  break;
1169 
1170  //TODO(snh): Customize Arc collide
1171  case ITEM::ARC_T:
1172  wxLogTrace( "PNS", "iter %d: collide-arc ", aIter );
1173 
1174  st = onCollidingArc( currentLine, static_cast<ARC*>( ni ) );
1175 
1176  if( st == SH_TRY_WALK )
1177  st = onCollidingSolid( currentLine, ni );
1178 
1179  break;
1180 
1181  case ITEM::VIA_T:
1182  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1183  st = onCollidingVia( &currentLine, (VIA*) ni );
1184 
1185  if( st == SH_TRY_WALK )
1186  st = onCollidingSolid( currentLine, ni );
1187 
1188  break;
1189 
1190  case ITEM::SOLID_T:
1191  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1192  st = onCollidingSolid( currentLine, (SOLID*) ni );
1193  break;
1194 
1195  default:
1196  break;
1197  }
1198  }
1199 
1200  return st;
1201 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
virtual void SetIteration(int iter)
LINE assembleLine(const LINKED_ITEM *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:104
void popLineStack()
Definition: pns_shove.cpp:1043
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:507
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:990
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:304
SHOVE_STATUS onCollidingArc(LINE &aCurrent, ARC *aObstacleArc)
Definition: pns_shove.cpp:403
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:464
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:907
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:832
DEBUG_DECORATOR * Dbg() const
Definition: pns_algo_base.h:77
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:342
PnsKind
Supported item types
Definition: pns_item.h:59
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:148
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162

References PNS::ITEM::ARC_T, assembleLine(), PNS::NODE::CheckColliding(), 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(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveMainLoop().

◆ ShoveLines()

SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveLines ( const LINE aCurrentHead)

Definition at line 1266 of file pns_shove.cpp.

1267 {
1268  SHOVE_STATUS st = SH_OK;
1269 
1270  m_multiLineMode = false;
1271 
1272  // empty head? nothing to shove...
1273 
1274  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1275  return SH_INCOMPLETE;
1276 
1277  LINE head( aCurrentHead );
1278  head.ClearLinks();
1279 
1280  m_lineStack.clear();
1281  m_optimizerQueue.clear();
1282  m_newHead = OPT_LINE();
1283 #if 0
1284  m_logger.Clear();
1285 #endif
1286 
1287  // Pop NODEs containing previous shoves which are no longer necessary
1288  //
1289  ITEM_SET headSet;
1290  headSet.Add( aCurrentHead );
1291 
1292  VIA_HANDLE dummyVia;
1293 
1294  NODE* parent = reduceSpringback( headSet, dummyVia );
1295 
1296  // Create a new NODE to store this version of the world
1297  //
1298  m_currentNode = parent->Branch();
1300  m_currentNode->Add( head );
1301 
1302  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1303 
1304  if( !head.EndsWithVia() )
1305  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1306 
1307  head.Mark( MK_HEAD );
1308  head.SetRank( 100000 );
1309 
1310 #if 0
1311  m_logger.NewGroup( "initial", 0 );
1312  m_logger.Log( &head, 0, "head" );
1313 #endif
1314 
1315  if( head.EndsWithVia() )
1316  {
1317  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1318  headVia->Mark( MK_HEAD );
1319  headVia->SetRank( 100000 );
1320  m_currentNode->Add( std::move( headVia ) );
1321  }
1322 
1323  if( !pushLineStack( head ) )
1324  {
1325  delete m_currentNode;
1326  m_currentNode = parent;
1327 
1328  return SH_INCOMPLETE;
1329  }
1330 
1331  st = shoveMainLoop();
1332 
1333  if( st == SH_OK )
1334  {
1336 
1337  if( m_newHead )
1339  else
1340  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1341  }
1342 
1344 
1345  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1346  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1347 
1348  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1349  {
1351  }
1352  else
1353  {
1354  delete m_currentNode;
1355 
1356  m_currentNode = parent;
1357  m_newHead = OPT_LINE();
1358  }
1359 
1360  if(m_newHead)
1361  m_newHead->Unmark();
1362 
1363  if( m_newHead && head.EndsWithVia() )
1364  {
1365  VIA v = head.Via();
1366  v.SetPos( m_newHead->CPoint( -1 ) );
1367  m_newHead->AppendVia(v);
1368  }
1369 
1370  return st;
1371 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1321
OPT< LINE > OPT_LINE
Definition: pns_shove.h:95
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:640
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1545
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:668
void Clear()
Definition: pns_logger.cpp:47
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:276
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1331
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1210
bool m_multiLineMode
Definition: pns_shove.h:172
OPT_LINE m_newHead
Definition: pns_shove.h:165
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
void Log(EVENT_TYPE evt, VECTOR2I pos, const ITEM *item=nullptr)
Definition: pns_logger.cpp:73
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:621
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:1061

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::LINK_HOLDER::ClearLinks(), PNS::NODE::ClearRanks(), PNS::Clone(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::NODE::LockJoint(), PNS::LOGGER::Log(), m_affectedArea, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_optimizerQueue, PNS::LINE::Mark(), 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(), and PNS::LINE::Via().

◆ shoveMainLoop()

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

Definition at line 1210 of file pns_shove.cpp.

1211 {
1212  SHOVE_STATUS st = SH_OK;
1213 
1215 
1216  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1218 
1219  int iterLimit = Settings().ShoveIterationLimit();
1220  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1221 
1222  m_iter = 0;
1223 
1224  timeLimit.Restart();
1225 
1226  if( m_lineStack.empty() && m_draggedVia )
1227  {
1228  // If we're shoving a free via then push a proxy LINE (with the via on the end) onto
1229  // the stack.
1231  }
1232 
1233  while( !m_lineStack.empty() )
1234  {
1235  st = shoveIteration( m_iter );
1236 
1237  m_iter++;
1238 
1239  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1240  {
1241  st = SH_INCOMPLETE;
1242  break;
1243  }
1244  }
1245 
1246  return st;
1247 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
int JointCount() const
Returns the number of joints
Definition: pns_node.h:182
NODE * m_root
Definition: pns_shove.h:161
ROUTING_SETTINGS & Settings() const
Returns current router settings
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:1072
VIA * m_draggedVia
Definition: pns_shove.h:168
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:525
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
int m_iter
Definition: pns_shove.h:170
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 1374 of file pns_shove.cpp.

1375 {
1376  SHOVE_STATUS st = SH_OK;
1377 
1378  m_multiLineMode = true;
1379 
1380  ITEM_SET headSet;
1381 
1382  for( const ITEM* item : aHeadSet.CItems() )
1383  {
1384  const LINE* headOrig = static_cast<const LINE*>( item );
1385 
1386  // empty head? nothing to shove...
1387  if( !headOrig->SegmentCount() )
1388  return SH_INCOMPLETE;
1389 
1390  headSet.Add( *headOrig );
1391  }
1392 
1393  m_lineStack.clear();
1394  m_optimizerQueue.clear();
1395 #if 0
1396  m_logger.Clear();
1397 #endif
1398 
1399  VIA_HANDLE dummyVia;
1400 
1401  NODE* parent = reduceSpringback( headSet, dummyVia );
1402 
1403  m_currentNode = parent->Branch();
1405  int n = 0;
1406 
1407  for( const ITEM* item : aHeadSet.CItems() )
1408  {
1409  const LINE* headOrig = static_cast<const LINE*>( item );
1410  LINE head( *headOrig );
1411  head.ClearLinks();
1412 
1413  m_currentNode->Add( head );
1414 
1415  head.Mark( MK_HEAD );
1416  head.SetRank( 100000 );
1417  n++;
1418 
1419  if( !pushLineStack( head ) )
1420  return SH_INCOMPLETE;
1421 
1422  if( head.EndsWithVia() )
1423  {
1424  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1425  headVia->Mark( MK_HEAD );
1426  headVia->SetRank( 100000 );
1427  m_currentNode->Add( std::move( headVia ) );
1428  }
1429  }
1430 
1431  st = shoveMainLoop();
1432 
1433  if( st == SH_OK )
1435 
1437 
1438  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1439  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1440 
1441  if( st == SH_OK )
1442  {
1444  }
1445  else
1446  {
1447  delete m_currentNode;
1448  m_currentNode = parent;
1449  }
1450 
1451  return st;
1452 }
bool pushLineStack(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:1024
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1321
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:106
NODE * reduceSpringback(const ITEM_SET &aHeadSet, VIA_HANDLE &aDraggedVia)
Definition: pns_shove.cpp:640
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1545
bool pushSpringback(NODE *aNode, const OPT_BOX2I &aAffectedArea, VIA *aDraggedVia)
Definition: pns_shove.cpp:668
void Clear()
Definition: pns_logger.cpp:47
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:276
void RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1331
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1210
bool m_multiLineMode
Definition: pns_shove.h:172
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158
NODE * m_currentNode
Definition: pns_shove.h:162
bool Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:621
LOGGER m_logger
Definition: pns_shove.h:167
int m_iter
Definition: pns_shove.h:170

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().

◆ totalAffectedArea()

OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const
private

Definition at line 1250 of file pns_shove.cpp.

1251 {
1252  OPT_BOX2I area;
1253 
1254  if( !m_nodeStack.empty() )
1255  area = m_nodeStack.back().m_affectedArea;
1256 
1257  if( area && m_affectedArea)
1258  area->Merge( *m_affectedArea );
1259  else if( !area )
1260  area = m_affectedArea;
1261 
1262  return area;
1263 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157
OPT_BOX2I m_affectedArea
Definition: pns_shove.h:150
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 1676 of file pns_shove.cpp.

1677 {
1678  auto iter = m_nodeStack.begin();
1679 
1680  while( iter != m_nodeStack.end() )
1681  {
1682  if ( iter->m_node == aNode )
1683  {
1684  iter->m_locked = false;
1685  break;
1686  }
1687  iter++;
1688  }
1689 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:157

References m_nodeStack.

◆ unwindLineStack() [1/2]

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

Definition at line 990 of file pns_shove.cpp.

991 {
992  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
993  {
994  if( i->ContainsLink( aSeg ) )
995  i = m_lineStack.erase( i );
996  else
997  i++;
998  }
999 
1000  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
1001  {
1002  if( i->ContainsLink( aSeg ) )
1003  i = m_optimizerQueue.erase( i );
1004  else
1005  i++;
1006  }
1007 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:158

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

1011 {
1012  if( aItem->OfKind( ITEM::SEGMENT_T | ITEM::ARC_T ) )
1013  unwindLineStack( static_cast<LINKED_ITEM*>( aItem ) );
1014  else if( aItem->OfKind( ITEM::LINE_T ) )
1015  {
1016  LINE* l = static_cast<LINE*>( aItem );
1017 
1018  for( auto seg : l->Links() )
1019  unwindLineStack( seg );
1020  }
1021 }
void unwindLineStack(LINKED_ITEM *aSeg)
Definition: pns_shove.cpp:990

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

◆ walkaroundLoneVia()

SHOVE::SHOVE_STATUS PNS::SHOVE::walkaroundLoneVia ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)
private

Definition at line 129 of file pns_shove.cpp.

130 {
131  int clearance = getClearance( &aCurrent, &aObstacle );
132  const SHAPE_LINE_CHAIN hull = aCurrent.Via().Hull( clearance, aObstacle.Width(), aCurrent.Layer() );
133  SHAPE_LINE_CHAIN path_cw;
134  SHAPE_LINE_CHAIN path_ccw;
135 
136  if( ! aObstacle.Walkaround( hull, path_cw, true ) )
137  return SH_INCOMPLETE;
138 
139  if( ! aObstacle.Walkaround( hull, path_ccw, false ) )
140  return SH_INCOMPLETE;
141 
142  const SHAPE_LINE_CHAIN& shortest = path_ccw.Length() < path_cw.Length() ? path_ccw : path_cw;
143 
144  if( shortest.PointCount() < 2 )
145  return SH_INCOMPLETE;
146 
147  if( aObstacle.CPoint( -1 ) != shortest.CPoint( -1 ) )
148  return SH_INCOMPLETE;
149 
150  if( aObstacle.CPoint( 0 ) != shortest.CPoint( 0 ) )
151  return SH_INCOMPLETE;
152 
153  aShoved.SetShape( shortest );
154 
155  if( m_currentNode->CheckColliding( &aShoved, &aCurrent ) )
156  return SH_INCOMPLETE;
157 
158  return SH_OK;
159 }
long long int Length() const
Function Length()
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:427
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:67
NODE * m_currentNode
Definition: pns_shove.h:162

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

Referenced by ProcessSingleLine().

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 83 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 168 of file pns_shove.h.

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

◆ m_forceClearance

int PNS::SHOVE::m_forceClearance
private

Definition at line 171 of file pns_shove.h.

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

◆ m_iter

◆ m_lineStack

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

◆ m_logger

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

Referenced by SHOVE().

◆ m_root

NODE* PNS::SHOVE::m_root
private

Definition at line 161 of file pns_shove.h.

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

◆ m_router

ROUTER* PNS::ALGO_BASE::m_router
protectedinherited

Definition at line 84 of file pns_algo_base.h.

Referenced by PNS::ALGO_BASE::Router(), and PNS::ALGO_BASE::Settings().


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