KiCad PCB EDA Suite
PNS::SHOVE Class Reference

Class 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 (VIA *aVia, const VECTOR2I &aWhere, VIA **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)
 
ROUTERRouter () const
 

Returns the instance of our router

More...
 
ROUTING_SETTINGSSettings () const
 

Returns current router settings

More...
 
void SetDebugDecorator (DEBUG_DECORATOR *aDecorator)
 Function SetDebugDecorator. More...
 
DEBUG_DECORATORDbg () const
 

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)
 
bool reduceSpringback (const ITEM_SET &aHeadItems)
 
bool pushSpringback (NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
 
SHOVE_STATUS walkaroundLoneVia (LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
 
bool checkBumpDirection (const LINE &aCurrent, const LINE &aShoved) const
 
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 pushVia (VIA *aVia, const VECTOR2I &aForce, int aCurrentRank, bool aDryRun=false)
 
OPT_BOX2I totalAffectedArea () const
 
void unwindStack (SEGMENT *aSeg)
 
void unwindStack (ITEM *aItem)
 
void runOptimizer (NODE *aNode)
 
bool pushLine (const LINE &aL, bool aKeepCurrentOnTop=false)
 
void popLine ()
 
LINE assembleLine (const SEGMENT *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_affectedAreaSum
 
std::vector< SPRINGBACK_TAGm_nodeStack
 
std::vector< LINEm_lineStack
 
std::vector< LINEm_optimizerQueue
 
NODEm_root
 
NODEm_currentNode
 
OPT_LINE m_newHead
 
LOGGER m_logger
 
VIAm_draggedVia
 
ITEM_SET m_draggedViaHeadSet
 
int m_iter
 
int m_forceClearance
 
bool m_multiLineMode
 

Detailed Description

Class SHOVE.

The actual Push and Shove algorithm.

Definition at line 46 of file pns_shove.h.

Member Typedef Documentation

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

Definition at line 89 of file pns_shove.h.

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

Definition at line 91 of file pns_shove.h.

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

Definition at line 92 of file pns_shove.h.

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

Definition at line 90 of file pns_shove.h.

Member Enumeration Documentation

Enumerator
SH_OK 
SH_NULL 
SH_INCOMPLETE 
SH_HEAD_MODIFIED 
SH_TRY_WALK 

Definition at line 50 of file pns_shove.h.

Constructor & Destructor Documentation

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

Definition at line 88 of file pns_shove.cpp.

References m_currentNode, m_draggedVia, m_forceClearance, m_iter, m_multiLineMode, and m_root.

88  :
89  ALGO_BASE( aRouter )
90 {
91  m_forceClearance = -1;
92  m_root = aWorld;
93  m_currentNode = aWorld;
94 
95  // Initialize other temporary variables:
96  m_draggedVia = NULL;
97  m_iter = 0;
98  m_multiLineMode = false;
99 }
NODE * m_root
Definition: pns_shove.h:148
ALGO_BASE(ROUTER *aRouter)
Definition: pns_algo_base.h:42
VIA * m_draggedVia
Definition: pns_shove.h:154
bool m_multiLineMode
Definition: pns_shove.h:159
NODE * m_currentNode
Definition: pns_shove.h:149
int m_iter
Definition: pns_shove.h:157
int m_forceClearance
Definition: pns_shove.h:158
PNS::SHOVE::~SHOVE ( )

Definition at line 102 of file pns_shove.cpp.

103 {
104 }

Member Function Documentation

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

Definition at line 107 of file pns_shove.cpp.

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

Referenced by onCollidingSegment(), onReverseCollidingVia(), pushVia(), and shoveIteration().

108 {
109  return m_currentNode->AssembleLine( const_cast<SEGMENT*>( aSeg ), aIndex, true );
110 }
const LINE AssembleLine(SEGMENT *aSeg, int *aOriginSegmentIndex=NULL, bool aStopAtLockedJoints=false)
Function AssembleLine()
Definition: pns_node.cpp:832
NODE * m_currentNode
Definition: pns_shove.h:149
bool PNS::SHOVE::checkBumpDirection ( const LINE aCurrent,
const LINE aShoved 
) const
private

Definition at line 116 of file pns_shove.cpp.

References SEG::A, SEG::B, PNS::LINE::CLine(), PNS::LINE::CSegment(), dist, getClearance(), PNS_HULL_MARGIN, SHAPE_LINE_CHAIN::PointOnEdge(), and PNS::LINE::Width().

Referenced by processHullSet().

117 {
118  const SEG& ss = aCurrent.CSegment( 0 );
119 
120  int dist = getClearance( &aCurrent, &aShoved ) + PNS_HULL_MARGIN;
121 
122  dist += aCurrent.Width() / 2;
123  dist += aShoved.Width() / 2;
124 
125  const VECTOR2I ps = ss.A - ( ss.B - ss.A ).Resize( dist );
126 
127  return !aShoved.CLine().PointOnEdge( ps );
128 }
static const int dist[10][10]
Definition: dist.cpp:57
#define PNS_HULL_MARGIN
Class LINE.
Definition: pns_line.h:58
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:72
Definition: seg.h:36
VECTOR2I A
Definition: seg.h:46
VECTOR2I B
Definition: seg.h:47
NODE * PNS::SHOVE::CurrentNode ( )

Definition at line 1393 of file pns_shove.cpp.

References m_nodeStack, and m_root.

Referenced by PNS::DRAGGER::dragMarkObstacles(), PNS::DRAGGER::dragShove(), and PNS::DIFF_PAIR_PLACER::rhShoveOnly().

1394 {
1395  return m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1396 }
NODE * m_root
Definition: pns_shove.h:148
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
void PNS::SHOVE::ForceClearance ( bool  aEnabled,
int  aClearance 
)
inline

Definition at line 74 of file pns_shove.h.

References m_forceClearance.

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

75  {
76  if( aEnabled )
77  m_forceClearance = aClearance;
78  else
79  m_forceClearance = -1;
80  }
int m_forceClearance
Definition: pns_shove.h:158
int PNS::SHOVE::getClearance ( const ITEM aA,
const ITEM aB 
) const
private

Definition at line 72 of file pns_shove.cpp.

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

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

73 {
74  if( m_forceClearance >= 0 )
75  return m_forceClearance;
76 
77  return m_currentNode->GetClearance( aA, aB );
78 }
int GetClearance(const ITEM *aA, const ITEM *aB) const
Returns the expected clearance between items a and b.
Definition: pns_node.cpp:98
NODE * m_currentNode
Definition: pns_shove.h:149
int m_forceClearance
Definition: pns_shove.h:158
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 62 of file pns_shove.h.

References m_logger.

Referenced by PNS::DRAGGER::Logger().

63  {
64  return &m_logger;
65  }
LOGGER m_logger
Definition: pns_shove.h:153
const LINE PNS::SHOVE::NewHead ( ) const

Definition at line 1399 of file pns_shove.cpp.

References m_newHead.

Referenced by PNS::DRAGGER::dragShove().

1400 {
1401  assert( m_newHead );
1402 
1403  return *m_newHead;
1404 }
OPT_LINE m_newHead
Definition: pns_shove.h:151
SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingLine ( LINE aCurrent,
LINE aObstacle 
)
private

Definition at line 373 of file pns_shove.cpp.

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

Referenced by shoveIteration().

374 {
375  LINE shovedLine( aObstacle );
376 
377  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, aObstacle, shovedLine );
378 
379  #ifdef DEBUG
380  m_logger.NewGroup( "on-colliding-line", m_iter );
381  m_logger.Log( &aObstacle, 0, "obstacle-line" );
382  m_logger.Log( &aCurrent, 1, "current-line" );
383  m_logger.Log( &shovedLine, 3, "shoved-line" );
384  #endif
385 
386  if( rv == SH_OK )
387  {
388  if( shovedLine.Marker() & MK_HEAD )
389  {
390  if( m_multiLineMode )
391  return SH_INCOMPLETE;
392 
393  m_newHead = shovedLine;
394  }
395 
396  sanityCheck( &aObstacle, &shovedLine );
397  replaceLine( aObstacle, shovedLine );
398 
399  int rank = aObstacle.Rank();
400  shovedLine.SetRank( rank - 1 );
401 
402 
403  if( !pushLine( shovedLine ) )
404  {
405  rv = SH_INCOMPLETE;
406  }
407  }
408 
409  return rv;
410 }
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:81
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSegment ( LINE aCurrent,
SEGMENT aObstacleSeg 
)
private

Definition at line 315 of file pns_shove.cpp.

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, PNS::LOGGER::NewGroup(), ProcessSingleLine(), pushLine(), PNS::LINE::Rank(), replaceLine(), sanityCheck(), PNS::LINE::SetRank(), SH_INCOMPLETE, SH_OK, and SH_TRY_WALK.

Referenced by shoveIteration().

316 {
317  int segIndex;
318  LINE obstacleLine = assembleLine( aObstacleSeg, &segIndex );
319  LINE shovedLine( obstacleLine );
320  SEGMENT tmp( *aObstacleSeg );
321 
322  if( obstacleLine.HasLockedSegments() )
323  return SH_TRY_WALK;
324 
325  SHOVE_STATUS rv = ProcessSingleLine( aCurrent, obstacleLine, shovedLine );
326 
327  const double extensionWalkThreshold = 1.0;
328 
329  double obsLen = obstacleLine.CLine().Length();
330  double shovedLen = shovedLine.CLine().Length();
331  double extensionFactor = 0.0;
332 
333  if( obsLen != 0.0f )
334  extensionFactor = shovedLen / obsLen - 1.0;
335 
336  if( extensionFactor > extensionWalkThreshold )
337  return SH_TRY_WALK;
338 
339  assert( obstacleLine.LayersOverlap( &shovedLine ) );
340 
341 #ifdef DEBUG
342  m_logger.NewGroup( "on-colliding-segment", m_iter );
343  m_logger.Log( &tmp, 0, "obstacle-segment" );
344  m_logger.Log( &aCurrent, 1, "current-line" );
345  m_logger.Log( &obstacleLine, 2, "obstacle-line" );
346  m_logger.Log( &shovedLine, 3, "shoved-line" );
347 #endif
348 
349  if( rv == SH_OK )
350  {
351  if( shovedLine.Marker() & MK_HEAD )
352  {
353  if( m_multiLineMode )
354  return SH_INCOMPLETE;
355 
356  m_newHead = shovedLine;
357  }
358 
359  int rank = aCurrent.Rank();
360  shovedLine.SetRank( rank - 1 );
361 
362  sanityCheck( &obstacleLine, &shovedLine );
363  replaceLine( obstacleLine, shovedLine );
364 
365  if( !pushLine( shovedLine ) )
366  rv = SH_INCOMPLETE;
367  }
368 
369  return rv;
370 }
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:81
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingSolid ( LINE aCurrent,
ITEM aObstacle 
)
private

Definition at line 412 of file pns_shove.cpp.

References PNS::TOPOLOGY::AssembleCluster(), PNS::NODE::CheckColliding(), PNS::LINE::ClearSegmentLinks(), 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, PNS::LOGGER::NewGroup(), onCollidingVia(), popLine(), PNS::VIA::Pos(), ProcessSingleLine(), pushLine(), 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().

413 {
414  WALKAROUND walkaround( m_currentNode, Router() );
415  LINE walkaroundLine( aCurrent );
416 
417  if( aCurrent.EndsWithVia() )
418  {
419  VIA vh = aCurrent.Via();
420  VIA* via = NULL;
421  JOINT* jtStart = m_currentNode->FindJoint( vh.Pos(), &aCurrent );
422 
423  if( !jtStart )
424  return SH_INCOMPLETE;
425 
426  for( ITEM* item : jtStart->LinkList() )
427  {
428  if( item->OfKind( ITEM::VIA_T ) )
429  {
430  via = (VIA*) item;
431  break;
432  }
433  }
434 
435  if( via && m_currentNode->CheckColliding( via, aObstacle ) )
436  return onCollidingVia( aObstacle, via );
437  }
438 
439  TOPOLOGY topo( m_currentNode );
440 
441  std::set<ITEM*> cluster = topo.AssembleCluster( aObstacle, aCurrent.Layers().Start() );
442 
443 #ifdef DEBUG
444  m_logger.NewGroup( "on-colliding-solid-cluster", m_iter );
445  for( ITEM* item : cluster )
446  {
447  m_logger.Log( item, 0, "cluster-entry" );
448  }
449 #endif
450 
451  walkaround.SetSolidsOnly( false );
452  walkaround.RestrictToSet( true, cluster );
453  walkaround.SetIterationLimit( 16 ); // fixme: make configurable
454 
455  int currentRank = aCurrent.Rank();
456  int nextRank;
457 
458  bool success = false;
459 
460  for( int attempt = 0; attempt < 2; attempt++ )
461  {
462  if( attempt == 1 || Settings().JumpOverObstacles() )
463  {
464 
465  nextRank = currentRank - 1;
466  walkaround.SetSingleDirection( true );
467  }
468  else
469  {
470  nextRank = currentRank + 10000;
471  walkaround.SetSingleDirection( false );
472  }
473 
474 
475  WALKAROUND::WALKAROUND_STATUS status = walkaround.Route( aCurrent, walkaroundLine, false );
476 
477  if( status != WALKAROUND::DONE )
478  continue;
479 
480  walkaroundLine.ClearSegmentLinks();
481  walkaroundLine.Unmark();
482  walkaroundLine.Line().Simplify();
483 
484  if( walkaroundLine.HasLoops() )
485  continue;
486 
487  if( aCurrent.Marker() & MK_HEAD )
488  {
489  walkaroundLine.Mark( MK_HEAD );
490 
491  if( m_multiLineMode )
492  continue;
493 
494  m_newHead = walkaroundLine;
495  }
496 
497  sanityCheck( &aCurrent, &walkaroundLine );
498 
499  if( !m_lineStack.empty() )
500  {
501  LINE lastLine = m_lineStack.front();
502 
503  if( m_currentNode->CheckColliding( &lastLine, &walkaroundLine ) )
504  {
505  LINE dummy( lastLine );
506 
507  if( ProcessSingleLine( walkaroundLine, lastLine, dummy ) == SH_OK )
508  {
509  success = true;
510  break;
511  }
512  } else {
513  success = true;
514  break;
515  }
516  }
517  }
518 
519  if(!success)
520  return SH_INCOMPLETE;
521 
522  replaceLine( aCurrent, walkaroundLine );
523  walkaroundLine.SetRank( nextRank );
524 
525 #ifdef DEBUG
526  m_logger.NewGroup( "on-colliding-solid", m_iter );
527  m_logger.Log( aObstacle, 0, "obstacle-solid" );
528  m_logger.Log( &aCurrent, 1, "current-line" );
529  m_logger.Log( &walkaroundLine, 3, "walk-line" );
530 #endif
531 
532  popLine();
533 
534  if( !pushLine( walkaroundLine ) )
535  return SH_INCOMPLETE;
536 
537  return SH_OK;
538 }
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
ROUTING_SETTINGS & Settings() const
Returns current router settings
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:713
void sanityCheck(LINE *aOld, LINE *aNew)
Definition: pns_shove.cpp:81
ROUTER * Router() const
Returns the instance of our router
Definition: pns_algo_base.h:49
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
void popLine()
Definition: pns_shove.cpp:898
static LIB_PART * dummy()
Used when a LIB_PART is not found in library to draw a dummy shape This component is a 400 mils squar...
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
SHOVE::SHOVE_STATUS PNS::SHOVE::onCollidingVia ( ITEM aCurrent,
VIA aObstacleVia 
)
private

Definition at line 713 of file pns_shove.cpp.

References CollideShapes(), PNS::LINE::EndsWithVia(), VECTOR2< T >::EuclideanNorm(), getClearance(), PNS::ITEM::LINE_T, PNS::LOGGER::Log(), m_iter, m_logger, PNS::LOGGER::NewGroup(), PNS::ITEM::OfKind(), PNS_HULL_MARGIN, pushVia(), PNS::LINE::Rank(), PNS::ITEM::Rank(), SH_OK, PNS::LINE::Shape(), PNS::VIA::Shape(), PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, PNS::LINE::Via(), and PNS::LINE::Width().

Referenced by onCollidingSolid(), and shoveIteration().

714 {
715  int clearance = getClearance( aCurrent, aObstacleVia ) ;
716  LINE_PAIR_VEC draggedLines;
717  bool colLine = false, colVia = false;
718  LINE* currentLine = NULL;
719  VECTOR2I mtvLine, mtvVia, mtv, mtvSolid;
720  int rank = -1;
721 
722  if( aCurrent->OfKind( ITEM::LINE_T ) )
723  {
724 #ifdef DEBUG
725  m_logger.NewGroup( "push-via-by-line", m_iter );
726  m_logger.Log( aCurrent, 4, "current" );
727 #endif
728 
729  currentLine = (LINE*) aCurrent;
730  colLine = CollideShapes( aObstacleVia->Shape(), currentLine->Shape(),
731  clearance + currentLine->Width() / 2 + PNS_HULL_MARGIN,
732  true, mtvLine );
733 
734  if( currentLine->EndsWithVia() )
735  colVia = CollideShapes( currentLine->Via().Shape(), aObstacleVia->Shape(),
736  clearance + PNS_HULL_MARGIN, true, mtvVia );
737 
738  if( !colLine && !colVia )
739  return SH_OK;
740 
741  if( colLine && colVia )
742  mtv = mtvVia.EuclideanNorm() > mtvLine.EuclideanNorm() ? mtvVia : mtvLine;
743  else if( colLine )
744  mtv = mtvLine;
745  else
746  mtv = mtvVia;
747 
748  rank = currentLine->Rank();
749  }
750  else if( aCurrent->OfKind( ITEM::SOLID_T ) )
751  {
752  CollideShapes( aObstacleVia->Shape(), aCurrent->Shape(),
753  clearance + PNS_HULL_MARGIN, true, mtvSolid );
754  mtv = -mtvSolid;
755  rank = aCurrent->Rank() + 10000;
756  }
757 
758  return pushVia( aObstacleVia, mtv, rank );
759 }
#define PNS_HULL_MARGIN
Class LINE.
Definition: pns_line.h:58
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:72
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:92
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
SHOVE_STATUS pushVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank, bool aDryRun=false)
Definition: pns_shove.cpp:592
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
bool CollideShapes(const SHAPE *aA, const SHAPE *aB, int aClearance, bool aNeedMTV, VECTOR2I &aMTV)
SHOVE::SHOVE_STATUS PNS::SHOVE::onReverseCollidingVia ( LINE aCurrent,
VIA aObstacleVia 
)
private

Definition at line 762 of file pns_shove.cpp.

References PNS::LINE::AppendVia(), assembleLine(), SHAPE_LINE_CHAIN::Clear(), PNS::LINE::ClearSegmentLinks(), 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::LOGGER::NewGroup(), PNS::VIA::Pos(), ProcessSingleLine(), pushLine(), PNS::LINE::Rank(), PNS::LINE::RemoveVia(), replaceLine(), PNS::ITEM::SEGMENT_T, PNS::LINE::SetRank(), PNS::LINE::SetShape(), SH_INCOMPLETE, SH_OK, unwindStack(), and PNS::LINE::Via().

Referenced by shoveIteration().

763 {
764  int n = 0;
765  LINE cur( aCurrent );
766  cur.ClearSegmentLinks();
767 
768  JOINT* jt = m_currentNode->FindJoint( aObstacleVia->Pos(), aObstacleVia );
769  LINE shoved( aCurrent );
770  shoved.ClearSegmentLinks();
771 
772  cur.RemoveVia();
773  unwindStack( &aCurrent );
774 
775  for( ITEM* item : jt->LinkList() )
776  {
777  if( item->OfKind( ITEM::SEGMENT_T ) && item->LayersOverlap( &aCurrent ) )
778  {
779  SEGMENT* seg = (SEGMENT*) item;
780  LINE head = assembleLine( seg );
781 
782  head.AppendVia( *aObstacleVia );
783 
784  SHOVE_STATUS st = ProcessSingleLine( head, cur, shoved );
785 
786  if( st != SH_OK )
787  {
788 #ifdef DEBUG
789  m_logger.NewGroup( "on-reverse-via-fail-shove", m_iter );
790  m_logger.Log( aObstacleVia, 0, "the-via" );
791  m_logger.Log( &aCurrent, 1, "current-line" );
792  m_logger.Log( &shoved, 3, "shoved-line" );
793 #endif
794 
795  return st;
796  }
797 
798  cur.SetShape( shoved.CLine() );
799  n++;
800  }
801  }
802 
803  if( !n )
804  {
805 #ifdef DEBUG
806  m_logger.NewGroup( "on-reverse-via-fail-lonevia", m_iter );
807  m_logger.Log( aObstacleVia, 0, "the-via" );
808  m_logger.Log( &aCurrent, 1, "current-line" );
809 #endif
810 
811  LINE head( aCurrent );
812  head.Line().Clear();
813  head.AppendVia( *aObstacleVia );
814  head.ClearSegmentLinks();
815 
816  SHOVE_STATUS st = ProcessSingleLine( head, aCurrent, shoved );
817 
818  if( st != SH_OK )
819  return st;
820 
821  cur.SetShape( shoved.CLine() );
822  }
823 
824  if( aCurrent.EndsWithVia() )
825  shoved.AppendVia( aCurrent.Via() );
826 
827 #ifdef DEBUG
828  m_logger.NewGroup( "on-reverse-via", m_iter );
829  m_logger.Log( aObstacleVia, 0, "the-via" );
830  m_logger.Log( &aCurrent, 1, "current-line" );
831  m_logger.Log( &shoved, 3, "shoved-line" );
832 #endif
833  int currentRank = aCurrent.Rank();
834  replaceLine( aCurrent, shoved );
835 
836  if( !pushLine( shoved ) )
837  return SH_INCOMPLETE;
838 
839  shoved.SetRank( currentRank );
840 
841  return SH_OK;
842 }
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
SHOVE_STATUS ProcessSingleLine(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:259
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:845
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
NODE * m_currentNode
Definition: pns_shove.h:149
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
void PNS::SHOVE::popLine ( )
private

Definition at line 898 of file pns_shove.cpp.

References PNS::LINE::LinkedSegments(), m_lineStack, and m_optimizerQueue.

Referenced by onCollidingSolid(), and shoveIteration().

899 {
900  LINE& l = m_lineStack.back();
901 
902  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end(); )
903  {
904  bool found = false;
905 
906  for( SEGMENT *s : l.LinkedSegments() )
907  {
908  if( i->ContainsSegment( s ) )
909  {
910  i = m_optimizerQueue.erase( i );
911  found = true;
912  break;
913  }
914  }
915 
916  if( !found )
917  i++;
918  }
919 
920  m_lineStack.pop_back();
921 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
SHOVE::SHOVE_STATUS PNS::SHOVE::processHullSet ( LINE aCurrent,
LINE aObstacle,
LINE aShoved,
const HULL_SET hulls 
)
private

Definition at line 161 of file pns_shove.cpp.

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

163 {
164  const SHAPE_LINE_CHAIN& obs = aObstacle.CLine();
165 
166  int attempt;
167 
168  for( attempt = 0; attempt < 4; attempt++ )
169  {
170  bool invertTraversal = ( attempt >= 2 );
171  bool clockwise = attempt % 2;
172  int vFirst = -1, vLast = -1;
173 
174  SHAPE_LINE_CHAIN path;
175  LINE l( aObstacle );
176 
177  for( int i = 0; i < (int) aHulls.size(); i++ )
178  {
179  const SHAPE_LINE_CHAIN& hull = aHulls[invertTraversal ? aHulls.size() - 1 - i : i];
180 
181  l.Walkaround( hull, path, clockwise );
182  path.Simplify();
183  l.SetShape( path );
184  }
185 
186  for( int i = 0; i < std::min( path.PointCount(), obs.PointCount() ); i++ )
187  {
188  if( path.CPoint( i ) != obs.CPoint( i ) )
189  {
190  vFirst = i;
191  break;
192  }
193  }
194 
195  int k = obs.PointCount() - 1;
196  for( int i = path.PointCount() - 1; i >= 0 && k >= 0; i--, k-- )
197  {
198  if( path.CPoint( i ) != obs.CPoint( k ) )
199  {
200  vLast = i;
201  break;
202  }
203  }
204 
205  if( ( vFirst < 0 || vLast < 0 ) && !path.CompareGeometry( aObstacle.CLine() ) )
206  {
207  wxLogTrace( "PNS", "attempt %d fail vfirst-last", attempt );
208  continue;
209  }
210 
211  if( path.CPoint( -1 ) != obs.CPoint( -1 ) || path.CPoint( 0 ) != obs.CPoint( 0 ) )
212  {
213  wxLogTrace( "PNS", "attempt %d fail vend-start\n", attempt );
214  continue;
215  }
216 
217  if( !checkBumpDirection( aCurrent, l ) )
218  {
219  wxLogTrace( "PNS", "attempt %d fail direction-check", attempt );
220  aShoved.SetShape( l.CLine() );
221 
222  continue;
223  }
224 
225  if( path.SelfIntersecting() )
226  {
227  wxLogTrace( "PNS", "attempt %d fail self-intersect", attempt );
228  continue;
229  }
230 
231  bool colliding = m_currentNode->CheckColliding( &l, &aCurrent, ITEM::ANY_T, m_forceClearance );
232 
233  if( ( aCurrent.Marker() & MK_HEAD ) && !colliding )
234  {
235  JOINT* jtStart = m_currentNode->FindJoint( aCurrent.CPoint( 0 ), &aCurrent );
236 
237  for( ITEM* item : jtStart->LinkList() )
238  {
239  if( m_currentNode->CheckColliding( item, &l ) )
240  colliding = true;
241  }
242  }
243 
244  if( colliding )
245  {
246  wxLogTrace( "PNS", "attempt %d fail coll-check", attempt );
247  continue;
248  }
249 
250  aShoved.SetShape( l.CLine() );
251 
252  return SH_OK;
253  }
254 
255  return SH_INCOMPLETE;
256 }
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
bool checkBumpDirection(const LINE &aCurrent, const LINE &aShoved) const
Definition: pns_shove.cpp:116
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
Class SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
NODE * m_currentNode
Definition: pns_shove.h:149
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int m_forceClearance
Definition: pns_shove.h:158
#define min(a, b)
Definition: auxiliary.h:85
SHOVE::SHOVE_STATUS PNS::SHOVE::ProcessSingleLine ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)

Definition at line 259 of file pns_shove.cpp.

References PNS::LINE::ClearSegmentLinks(), PNS::LINE::CSegment(), PNS::LINE::EndsWithVia(), getClearance(), PNS::VIA::Hull(), PNS::ITEM::LayersOverlap(), PNS::LINE::LinkedSegments(), PNS::LINE::Mark(), PNS::LINE::Marker(), PNS::MK_HEAD, processHullSet(), PNS::LINE::SegmentCount(), PNS::LINE::Via(), walkaroundLoneVia(), and PNS::LINE::Width().

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

261 {
262  aShoved.ClearSegmentLinks();
263 
264  bool obstacleIsHead = false;
265 
266  for( SEGMENT* s : aObstacle.LinkedSegments() )
267  {
268  if( s->Marker() & MK_HEAD )
269  {
270  obstacleIsHead = true;
271  break;
272  }
273  }
274 
275  SHOVE_STATUS rv;
276 
277  bool viaOnEnd = aCurrent.EndsWithVia();
278 
279  if( viaOnEnd && ( !aCurrent.LayersOverlap( &aObstacle ) || aCurrent.SegmentCount() == 0 ) )
280  {
281  rv = walkaroundLoneVia( aCurrent, aObstacle, aShoved );
282  }
283  else
284  {
285  int w = aObstacle.Width();
286  int n_segs = aCurrent.SegmentCount();
287 
288  int clearance = getClearance( &aCurrent, &aObstacle ) + 1;
289 
290  HULL_SET hulls;
291 
292  hulls.reserve( n_segs + 1 );
293 
294  for( int i = 0; i < n_segs; i++ )
295  {
296  SEGMENT seg( aCurrent, aCurrent.CSegment( i ) );
297  SHAPE_LINE_CHAIN hull = seg.Hull( clearance, w );
298 
299  hulls.push_back( hull );
300  }
301 
302  if( viaOnEnd )
303  hulls.push_back( aCurrent.Via().Hull( clearance, w ) );
304 
305  rv = processHullSet( aCurrent, aObstacle, aShoved, hulls );
306  }
307 
308  if( obstacleIsHead )
309  aShoved.Mark( aShoved.Marker() | MK_HEAD );
310 
311  return rv;
312 }
SHOVE_STATUS processHullSet(LINE &aCurrent, LINE &aObstacle, LINE &aShoved, const HULL_SET &hulls)
Definition: pns_shove.cpp:161
int getClearance(const ITEM *aA, const ITEM *aB) const
Definition: pns_shove.cpp:72
std::vector< SHAPE_LINE_CHAIN > HULL_SET
Definition: pns_shove.h:89
Class SHAPE_LINE_CHAIN.
SHOVE_STATUS walkaroundLoneVia(LINE &aCurrent, LINE &aObstacle, LINE &aShoved)
Definition: pns_shove.cpp:131
bool PNS::SHOVE::pushLine ( const LINE aL,
bool  aKeepCurrentOnTop = false 
)
private

Definition at line 879 of file pns_shove.cpp.

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

Referenced by onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), pushVia(), shoveIteration(), ShoveLines(), and ShoveMultiLines().

880 {
881  if( !aL.IsLinkedChecked() )
882  return false;
883 
884  if( aKeepCurrentOnTop && m_lineStack.size() > 0)
885  {
886  m_lineStack.insert( m_lineStack.begin() + m_lineStack.size() - 1, aL );
887  }
888  else
889  {
890  m_lineStack.push_back( aL );
891  }
892 
893  m_optimizerQueue.push_back( aL );
894 
895  return true;
896 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
bool PNS::SHOVE::pushSpringback ( NODE aNode,
const ITEM_SET aHeadItems,
const COST_ESTIMATOR aCost,
const OPT_BOX2I aAffectedArea 
)
private

Definition at line 564 of file pns_shove.cpp.

References PNS::SHOVE::SPRINGBACK_TAG::m_affectedArea, PNS::SHOVE::SPRINGBACK_TAG::m_cost, PNS::SHOVE::SPRINGBACK_TAG::m_headItems, PNS::SHOVE::SPRINGBACK_TAG::m_node, and m_nodeStack.

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

566 {
567  SPRINGBACK_TAG st;
568  OPT_BOX2I prev_area;
569 
570  if( !m_nodeStack.empty() )
571  prev_area = m_nodeStack.back().m_affectedArea;
572 
573  st.m_node = aNode;
574  st.m_cost = aCost;
575  st.m_headItems = aHeadItems;
576 
577  if( aAffectedArea )
578  {
579  if( prev_area )
580  st.m_affectedArea = prev_area->Merge( *aAffectedArea );
581  else
582  st.m_affectedArea = aAffectedArea;
583  } else
584  st.m_affectedArea = prev_area;
585 
586  m_nodeStack.push_back( st );
587 
588  return true;
589 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
SHOVE::SHOVE_STATUS PNS::SHOVE::pushVia ( VIA aVia,
const VECTOR2I aForce,
int  aCurrentRank,
bool  aDryRun = false 
)
private

Definition at line 592 of file pns_shove.cpp.

References PNS::ITEM_SET::Add(), assembleLine(), PNS::ITEM_SET::Clear(), PNS::Clone(), PNS::NODE::FindJoint(), PNS::ITEM::IsLocked(), PNS::LOGGER::Log(), m_currentNode, m_draggedVia, m_draggedViaHeadSet, m_logger, m_multiLineMode, m_newHead, PNS::ITEM::Marker(), PNS::MK_HEAD, PNS::VIA::Pos(), pushLine(), PNS::NODE::Remove(), replaceItems(), replaceLine(), VECTOR2< T >::Resize(), SH_INCOMPLETE, SH_OK, SH_TRY_WALK, unwindStack(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by onCollidingVia(), and ShoveDraggingVia().

593 {
594  LINE_PAIR_VEC draggedLines;
595  VECTOR2I p0( aVia->Pos() );
596  JOINT* jt = m_currentNode->FindJoint( p0, aVia );
597  VECTOR2I p0_pushed( p0 + aForce );
598 
599  if( !jt )
600  {
601  wxLogTrace( "PNS", "weird, can't find the center-of-via joint\n" );
602  return SH_INCOMPLETE;
603  }
604 
605  if( aVia->IsLocked() )
606  return SH_TRY_WALK;
607 
608  if( jt->IsLocked() )
609  return SH_INCOMPLETE;
610 
611  while( aForce.x != 0 || aForce.y != 0 )
612  {
613  JOINT* jt_next = m_currentNode->FindJoint( p0_pushed, aVia );
614 
615  if( !jt_next )
616  break;
617 
618  p0_pushed += aForce.Resize( 2 ); // make sure pushed via does not overlap with any existing joint
619  }
620 
621  std::unique_ptr< VIA > pushedVia = Clone( *aVia );
622  pushedVia->SetPos( p0_pushed );
623  pushedVia->Mark( aVia->Marker() );
624 
625  for( ITEM* item : jt->LinkList() )
626  {
627  if( SEGMENT* seg = dyn_cast<SEGMENT*>( item ) )
628  {
629  LINE_PAIR lp;
630  int segIndex;
631 
632  lp.first = assembleLine( seg, &segIndex );
633 
634  if( lp.first.HasLockedSegments() )
635  return SH_TRY_WALK;
636 
637  assert( segIndex == 0 || ( segIndex == ( lp.first.SegmentCount() - 1 ) ) );
638 
639  if( segIndex == 0 )
640  lp.first.Reverse();
641 
642  lp.second = lp.first;
643  lp.second.ClearSegmentLinks();
644  lp.second.DragCorner( p0_pushed, lp.second.CLine().Find( p0 ) );
645  lp.second.AppendVia( *pushedVia );
646  draggedLines.push_back( lp );
647 
648  if( aVia->Marker() & MK_HEAD )
649  m_draggedViaHeadSet.Add( lp.second );
650  }
651  }
652 
653  m_draggedViaHeadSet.Add( pushedVia.get() );
654 
655  if( aDryRun )
656  return SH_OK;
657 
658 #ifdef DEBUG
659  m_logger.Log( aVia, 0, "obstacle-via" );
660 #endif
661 
662  pushedVia->SetRank( aCurrentRank - 1 );
663 
664 #ifdef DEBUG
665  m_logger.Log( pushedVia.get(), 1, "pushed-via" );
666 #endif
667 
668  if( aVia->Marker() & MK_HEAD )
669  {
670  m_draggedVia = pushedVia.get();
672  }
673 
674  replaceItems( aVia, std::move( pushedVia ) );
675 
676  for( LINE_PAIR lp : draggedLines )
677  {
678  if( lp.first.Marker() & MK_HEAD )
679  {
680  lp.second.Mark( MK_HEAD );
681 
682  if( m_multiLineMode )
683  return SH_INCOMPLETE;
684 
685  m_newHead = lp.second;
686  }
687 
688  unwindStack( &lp.first );
689 
690  if( lp.second.SegmentCount() )
691  {
692  replaceLine( lp.first, lp.second );
693  lp.second.SetRank( aCurrentRank - 1 );
694 
695  if( !pushLine( lp.second, true ) )
696  return SH_INCOMPLETE;
697  }
698  else
699  {
700  m_currentNode->Remove( lp.first );
701  }
702 
703 #ifdef DEBUG
704  m_logger.Log( &lp.first, 2, "fan-pre" );
705  m_logger.Log( &lp.second, 3, "fan-post" );
706 #endif
707  }
708 
709  return SH_OK;
710 }
bool IsLocked() const override
Function IsLocked.
Definition: class_track.h:138
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
VECTOR2< T > Resize(T aNewLength) const
Function Resize returns a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:387
ITEM_SET m_draggedViaHeadSet
Definition: pns_shove.h:155
std::pair< LINE, LINE > LINE_PAIR
Definition: pns_shove.h:91
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:845
void Add(const LINE &aLine)
Definition: pns_itemset.cpp:32
std::vector< LINE_PAIR > LINE_PAIR_VEC
Definition: pns_shove.h:92
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Function FindJoint()
Definition: pns_node.cpp:966
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:367
VIA * m_draggedVia
Definition: pns_shove.h:154
void replaceLine(LINE &aOld, LINE &aNew)
Definition: pns_shove.cpp:60
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
void replaceItems(ITEM *aOld, std::unique_ptr< ITEM > aNew)
Definition: pns_shove.cpp:48
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
NODE * m_currentNode
Definition: pns_shove.h:149
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
LOGGER m_logger
Definition: pns_shove.h:153
bool PNS::SHOVE::reduceSpringback ( const ITEM_SET aHeadItems)
private

Definition at line 541 of file pns_shove.cpp.

References PNS::NODE::CheckColliding(), PNS::SHOVE::SPRINGBACK_TAG::m_node, and m_nodeStack.

Referenced by ShoveLines(), and ShoveMultiLines().

542 {
543  bool rv = false;
544 
545  while( !m_nodeStack.empty() )
546  {
547  SPRINGBACK_TAG spTag = m_nodeStack.back();
548 
549  if( !spTag.m_node->CheckColliding( aHeadSet ) )
550  {
551  rv = true;
552 
553  delete spTag.m_node;
554  m_nodeStack.pop_back();
555  }
556  else
557  break;
558  }
559 
560  return rv;
561 }
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
void PNS::SHOVE::replaceItems ( ITEM aOld,
std::unique_ptr< ITEM aNew 
)
private

Definition at line 48 of file pns_shove.cpp.

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

Referenced by pushVia().

49 {
50  OPT_BOX2I changed_area = ChangedArea( aOld, aNew.get() );
51 
52  if( changed_area )
53  {
54  m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
55  }
56 
57  m_currentNode->Replace( aOld, std::move( aNew ) );
58 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:231
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:715
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
NODE * m_currentNode
Definition: pns_shove.h:149
void PNS::SHOVE::replaceLine ( LINE aOld,
LINE aNew 
)
private

Definition at line 60 of file pns_shove.cpp.

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

Referenced by onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onReverseCollidingVia(), and pushVia().

61 {
62  OPT_BOX2I changed_area = ChangedArea( aOld, aNew );
63 
64  if( changed_area )
65  {
66  m_affectedAreaSum = m_affectedAreaSum ? m_affectedAreaSum->Merge( *changed_area ) : *changed_area;
67  }
68 
69  m_currentNode->Replace( aOld, aNew );
70 }
OPT_BOX2I ChangedArea(const ITEM *aItemA, const ITEM *aItemB)
Definition: pns_utils.cpp:231
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
void Replace(ITEM *aOldItem, std::unique_ptr< ITEM > aNewItem)
Function Replace()
Definition: pns_node.cpp:715
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
NODE * m_currentNode
Definition: pns_shove.h:149
void PNS::SHOVE::runOptimizer ( NODE aNode)
private

Definition at line 1315 of file pns_shove.cpp.

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

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

1316 {
1317  OPTIMIZER optimizer( aNode );
1318  int optFlags = 0, n_passes = 0;
1319 
1321 
1322  OPT_BOX2I area = totalAffectedArea();
1323 
1324  int maxWidth = 0;
1325 
1326  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin();
1327  i != m_optimizerQueue.end(); ++i )
1328  {
1329  maxWidth = std::max( i->Width(), maxWidth );
1330  }
1331 
1332  if( area )
1333  {
1334  area->Inflate( 10 * maxWidth );
1335  }
1336 
1337  switch( effort )
1338  {
1339  case OE_LOW:
1340  optFlags = OPTIMIZER::MERGE_OBTUSE;
1341  n_passes = 1;
1342  break;
1343 
1344  case OE_MEDIUM:
1345  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1346 
1347  if( area )
1348  optimizer.SetRestrictArea( *area );
1349 
1350  n_passes = 2;
1351  break;
1352 
1353  case OE_FULL:
1354  optFlags = OPTIMIZER::MERGE_SEGMENTS;
1355  n_passes = 2;
1356  break;
1357 
1358  default:
1359  break;
1360  }
1361 
1362  if( Settings().SmartPads() )
1363  optFlags |= OPTIMIZER::SMART_PADS;
1364 
1365  optimizer.SetEffortLevel( optFlags );
1366  optimizer.SetCollisionMask( ITEM::ANY_T );
1367 
1368  for( int pass = 0; pass < n_passes; pass++ )
1369  {
1371 
1372  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin();
1373  i != m_optimizerQueue.end(); ++i )
1374  {
1375  LINE& line = *i;
1376 
1377  if( !( line.Marker() & MK_HEAD ) )
1378  {
1379  LINE optimized;
1380 
1381  if( optimizer.Optimize( &line, &optimized ) )
1382  {
1383  aNode->Remove( line );
1384  line.SetShape( optimized.CLine() );
1385  aNode->Add( line );
1386  }
1387  }
1388  }
1389  }
1390 }
PNS_OPTIMIZATION_EFFORT OptimizerEffort() const
Returns the optimizer effort. Bigger means cleaner traces, but slower routing.
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
ROUTING_SETTINGS & Settings() const
Returns current router settings
OPT_BOX2I totalAffectedArea() const
Definition: pns_shove.cpp:1061
#define max(a, b)
Definition: auxiliary.h:86
static void reverse(privcurve_t *curve)
Definition: trace.cpp:1025
PNS_OPTIMIZATION_EFFORT
Optimization effort
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
void PNS::SHOVE::sanityCheck ( LINE aOld,
LINE aNew 
)
private

Definition at line 81 of file pns_shove.cpp.

References PNS::LINE::CPoint().

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

82 {
83  assert( aOld->CPoint( 0 ) == aNew->CPoint( 0 ) );
84  assert( aOld->CPoint( -1 ) == aNew->CPoint( -1 ) );
85 }
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 65 of file pns_algo_base.h.

References PNS::ALGO_BASE::m_debugDecorator.

66  {
67  m_debugDecorator = aDecorator;
68  }
DEBUG_DECORATOR * m_debugDecorator
Definition: pns_algo_base.h:76
void PNS::SHOVE::SetInitialLine ( LINE aInitial)

Definition at line 1407 of file pns_shove.cpp.

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

Referenced by PNS::DRAGGER::startDragSegment().

1408 {
1409  m_root = m_root->Branch();
1410  m_root->Remove( aInitial );
1411 }
NODE * m_root
Definition: pns_shove.h:148
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
void Remove(SOLID *aSolid)
Function Remove()
Definition: pns_node.cpp:727
SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveDraggingVia ( VIA aVia,
const VECTOR2I aWhere,
VIA **  aNewVia 
)

Definition at line 1262 of file pns_shove.cpp.

References PNS::NODE::Branch(), PNS::ITEM_SET::Clear(), PNS::NODE::ClearRanks(), m_affectedAreaSum, m_currentNode, m_draggedVia, m_draggedViaHeadSet, m_lineStack, m_newHead, m_nodeStack, m_optimizerQueue, m_root, PNS::ITEM::Mark(), PNS::MK_HEAD, PNS::VIA::Pos(), pushSpringback(), pushVia(), runOptimizer(), SH_HEAD_MODIFIED, SH_OK, and shoveMainLoop().

Referenced by PNS::DRAGGER::dragShove().

1264 {
1265  SHOVE_STATUS st = SH_OK;
1266 
1267  m_lineStack.clear();
1268  m_optimizerQueue.clear();
1269  m_newHead = OPT_LINE();
1270  m_draggedVia = NULL;
1272 
1273  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1274 
1275  m_currentNode = parent;
1276 
1277  parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1278 
1279  m_currentNode = parent->Branch();
1281 
1282  aVia->Mark( MK_HEAD );
1283 
1284  st = pushVia( aVia, ( aWhere - aVia->Pos() ), 0 );
1285  st = shoveMainLoop();
1286 
1287  if( st == SH_OK )
1289 
1290  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1291  {
1292  if( aNewVia )
1293  {
1294  wxLogTrace( "PNS","setNewV %p", m_draggedVia );
1295  *aNewVia = m_draggedVia;
1296  }
1297 
1299  }
1300  else
1301  {
1302  if( aNewVia )
1303  {
1304  *aNewVia = nullptr;
1305  }
1306 
1307  delete m_currentNode;
1308  m_currentNode = parent;
1309  }
1310 
1311  return st;
1312 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1254
OPT< LINE > OPT_LINE
Definition: pns_shove.h:90
ITEM_SET m_draggedViaHeadSet
Definition: pns_shove.h:155
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
NODE * m_root
Definition: pns_shove.h:148
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1315
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
bool pushSpringback(NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:564
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
VIA * m_draggedVia
Definition: pns_shove.h:154
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1028
SHOVE_STATUS pushVia(VIA *aVia, const VECTOR2I &aForce, int aCurrentRank, bool aDryRun=false)
Definition: pns_shove.cpp:592
OPT_LINE m_newHead
Definition: pns_shove.h:151
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
SHOVE::SHOVE_STATUS PNS::SHOVE::shoveIteration ( int  aIter)
private

Definition at line 924 of file pns_shove.cpp.

References assembleLine(), PNS::NODE::CheckColliding(), PNS::LINE::EndsWithVia(), PNS::ITEM::Kind(), m_currentNode, m_lineStack, PNS::NODE::NearestObstacle(), PNS::ITEM::OfKind(), onCollidingLine(), onCollidingSegment(), onCollidingSolid(), onCollidingVia(), onReverseCollidingVia(), popLine(), pushLine(), PNS::LINE::Rank(), PNS::ITEM::Rank(), PNS::ITEM::SEGMENT_T, SH_INCOMPLETE, SH_NULL, SH_OK, SH_TRY_WALK, PNS::ITEM::SOLID_T, unwindStack(), PNS::LINE::Via(), and PNS::ITEM::VIA_T.

Referenced by shoveMainLoop().

925 {
926  LINE currentLine = m_lineStack.back();
927  NODE::OPT_OBSTACLE nearest;
928  SHOVE_STATUS st = SH_NULL;
929 
931 
932  for( int i = 0; i < 3; i++ )
933  {
934  nearest = m_currentNode->NearestObstacle( &currentLine, search_order[i] );
935 
936  if( nearest )
937  break;
938  }
939 
940  if( !nearest )
941  {
942  m_lineStack.pop_back();
943  return SH_OK;
944  }
945 
946  ITEM* ni = nearest->m_item;
947 
948  unwindStack( ni );
949 
950  if( !ni->OfKind( ITEM::SOLID_T ) && ni->Rank() >= 0 && ni->Rank() > currentLine.Rank() )
951  {
952  switch( ni->Kind() )
953  {
954  case ITEM::VIA_T:
955  {
956  VIA* revVia = (VIA*) ni;
957  wxLogTrace( "PNS", "iter %d: reverse-collide-via", aIter );
958 
959  if( currentLine.EndsWithVia() && m_currentNode->CheckColliding( &currentLine.Via(), revVia ) )
960  {
961  st = SH_INCOMPLETE;
962  }
963  else
964  {
965  st = onReverseCollidingVia( currentLine, revVia );
966  }
967 
968  break;
969  }
970 
971  case ITEM::SEGMENT_T:
972  {
973  SEGMENT* seg = (SEGMENT*) ni;
974  wxLogTrace( "PNS", "iter %d: reverse-collide-segment ", aIter );
975  LINE revLine = assembleLine( seg );
976 
977  popLine();
978  st = onCollidingLine( revLine, currentLine );
979  if( !pushLine( revLine ) )
980  return SH_INCOMPLETE;
981 
982  break;
983  }
984 
985  default:
986  assert( false );
987  }
988  }
989  else
990  { // "forward" collisions
991  switch( ni->Kind() )
992  {
993  case ITEM::SEGMENT_T:
994  wxLogTrace( "PNS", "iter %d: collide-segment ", aIter );
995 
996  st = onCollidingSegment( currentLine, (SEGMENT*) ni );
997 
998  if( st == SH_TRY_WALK )
999  {
1000  st = onCollidingSolid( currentLine, ni );
1001  }
1002  break;
1003 
1004  case ITEM::VIA_T:
1005  wxLogTrace( "PNS", "iter %d: shove-via ", aIter );
1006  st = onCollidingVia( &currentLine, (VIA*) ni );
1007 
1008  if( st == SH_TRY_WALK )
1009  {
1010  st = onCollidingSolid( currentLine, ni );
1011  }
1012  break;
1013 
1014  case ITEM::SOLID_T:
1015  wxLogTrace( "PNS", "iter %d: walk-solid ", aIter );
1016  st = onCollidingSolid( currentLine, (SOLID*) ni );
1017  break;
1018 
1019  default:
1020  break;
1021  }
1022  }
1023 
1024  return st;
1025 }
SHOVE_STATUS onCollidingSolid(LINE &aCurrent, ITEM *aObstacle)
Definition: pns_shove.cpp:412
LINE assembleLine(const SEGMENT *aSeg, int *aIndex=NULL)
Definition: pns_shove.cpp:107
OPT_OBSTACLE NearestObstacle(const LINE *aItem, int aKindMask=ITEM::ANY_T, const std::set< ITEM * > *aRestrictedSet=NULL)
Function NearestObstacle()
Definition: pns_node.cpp:302
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:845
SHOVE_STATUS onCollidingLine(LINE &aCurrent, LINE &aObstacle)
Definition: pns_shove.cpp:373
SHOVE_STATUS onReverseCollidingVia(LINE &aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:762
SHOVE_STATUS onCollidingVia(ITEM *aCurrent, VIA *aObstacleVia)
Definition: pns_shove.cpp:713
SHOVE_STATUS onCollidingSegment(LINE &aCurrent, SEGMENT *aObstacleSeg)
Definition: pns_shove.cpp:315
PnsKind
Supported item types
Definition: pns_item.h:59
void popLine()
Definition: pns_shove.cpp:898
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
OPT< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:140
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveLines ( const LINE aCurrentHead)

Definition at line 1078 of file pns_shove.cpp.

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::NODE::CheckColliding(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), PNS::NODE::LockJoint(), PNS::LOGGER::Log(), m_affectedAreaSum, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_newHead, m_nodeStack, m_optimizerQueue, m_root, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLine(), 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().

Referenced by PNS::DRAGGER::dragShove().

1079 {
1080  SHOVE_STATUS st = SH_OK;
1081 
1082  m_multiLineMode = false;
1083 
1084  // empty head? nothing to shove...
1085 
1086  if( !aCurrentHead.SegmentCount() && !aCurrentHead.EndsWithVia() )
1087  return SH_INCOMPLETE;
1088 
1089  LINE head( aCurrentHead );
1090  head.ClearSegmentLinks();
1091 
1092  m_lineStack.clear();
1093  m_optimizerQueue.clear();
1094  m_newHead = OPT_LINE();
1095  m_logger.Clear();
1096 
1097  ITEM_SET headSet;
1098  headSet.Add( aCurrentHead );
1099 
1100  reduceSpringback( headSet );
1101 
1102  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1103 
1104  m_currentNode = parent->Branch();
1106  m_currentNode->Add( head );
1107 
1108  m_currentNode->LockJoint( head.CPoint(0), &head, true );
1109 
1110  if( !head.EndsWithVia() )
1111  m_currentNode->LockJoint( head.CPoint( -1 ), &head, true );
1112 
1113  head.Mark( MK_HEAD );
1114  head.SetRank( 100000 );
1115 
1116  m_logger.NewGroup( "initial", 0 );
1117  m_logger.Log( &head, 0, "head" );
1118 
1119  if( head.EndsWithVia() )
1120  {
1121  std::unique_ptr< VIA >headVia = Clone( head.Via() );
1122  headVia->Mark( MK_HEAD );
1123  headVia->SetRank( 100000 );
1124  m_logger.Log( headVia.get(), 0, "head-via" );
1125  m_currentNode->Add( std::move( headVia ) );
1126  }
1127 
1128  if( !pushLine( head ) )
1129  {
1130  delete m_currentNode;
1131  m_currentNode = parent;
1132 
1133  return SH_INCOMPLETE;
1134  }
1135 
1136  st = shoveMainLoop();
1137 
1138  if( st == SH_OK )
1139  {
1141 
1142  if( m_newHead )
1144  else
1145  st = m_currentNode->CheckColliding( &head ) ? SH_INCOMPLETE : SH_OK;
1146  }
1147 
1149 
1150  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1151  ( ( st == SH_OK || st == SH_HEAD_MODIFIED ) ? "OK" : "FAILURE"), m_iter );
1152 
1153  if( st == SH_OK || st == SH_HEAD_MODIFIED )
1154  {
1155  pushSpringback( m_currentNode, headSet, COST_ESTIMATOR(), m_affectedAreaSum );
1156  }
1157  else
1158  {
1159  delete m_currentNode;
1160 
1161  m_currentNode = parent;
1162  m_newHead = OPT_LINE();
1163  }
1164 
1165  if(m_newHead)
1166  m_newHead->Unmark();
1167 
1168  if( m_newHead && head.EndsWithVia() )
1169  {
1170  VIA v = head.Via();
1171  v.SetPos( m_newHead->CPoint( -1 ) );
1172  m_newHead->AppendVia(v);
1173  }
1174 
1175  return st;
1176 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1254
bool reduceSpringback(const ITEM_SET &aHeadItems)
Definition: pns_shove.cpp:541
OPT< LINE > OPT_LINE
Definition: pns_shove.h:90
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
NODE * m_root
Definition: pns_shove.h:148
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1315
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:367
bool pushSpringback(NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:564
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Function CheckColliding()
Definition: pns_node.cpp:425
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1028
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
bool m_multiLineMode
Definition: pns_shove.h:159
OPT_LINE m_newHead
Definition: pns_shove.h:151
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
int RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1276
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
void LockJoint(const VECTOR2I &aPos, const ITEM *aItem, bool aLock)
Definition: pns_node.cpp:996
SHOVE::SHOVE_STATUS PNS::SHOVE::shoveMainLoop ( )
private

Definition at line 1028 of file pns_shove.cpp.

References PNS::TIME_LIMIT::Expired(), PNS::NODE::JointCount(), m_affectedAreaSum, m_currentNode, m_iter, m_lineStack, m_root, 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().

1029 {
1030  SHOVE_STATUS st = SH_OK;
1031 
1033 
1034  wxLogTrace( "PNS", "ShoveStart [root: %d jts, current: %d jts]", m_root->JointCount(),
1036 
1037  int iterLimit = Settings().ShoveIterationLimit();
1038  TIME_LIMIT timeLimit = Settings().ShoveTimeLimit();
1039 
1040  m_iter = 0;
1041 
1042  timeLimit.Restart();
1043 
1044  while( !m_lineStack.empty() )
1045  {
1046  st = shoveIteration( m_iter );
1047 
1048  m_iter++;
1049 
1050  if( st == SH_INCOMPLETE || timeLimit.Expired() || m_iter >= iterLimit )
1051  {
1052  st = SH_INCOMPLETE;
1053  break;
1054  }
1055  }
1056 
1057  return st;
1058 }
TIME_LIMIT ShoveTimeLimit() const
NODE * m_root
Definition: pns_shove.h:148
ROUTING_SETTINGS & Settings() const
Returns current router settings
SHOVE_STATUS shoveIteration(int aIter)
Definition: pns_shove.cpp:924
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
int JointCount() const
Returns the number of joints
Definition: pns_node.h:174
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
int m_iter
Definition: pns_shove.h:157
SHOVE::SHOVE_STATUS PNS::SHOVE::ShoveMultiLines ( const ITEM_SET aHeadSet)

Definition at line 1179 of file pns_shove.cpp.

References PNS::ITEM_SET::Add(), PNS::NODE::Add(), PNS::NODE::Branch(), PNS::ITEM_SET::CItems(), PNS::LOGGER::Clear(), PNS::NODE::ClearRanks(), PNS::LINE::ClearSegmentLinks(), PNS::Clone(), PNS::LINE::EndsWithVia(), PNS::LOGGER::Log(), m_affectedAreaSum, m_currentNode, m_iter, m_lineStack, m_logger, m_multiLineMode, m_nodeStack, m_optimizerQueue, m_root, PNS::LINE::Mark(), PNS::MK_HEAD, PNS::LOGGER::NewGroup(), pushLine(), 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().

1180 {
1181  SHOVE_STATUS st = SH_OK;
1182 
1183  m_multiLineMode = true;
1184 
1185  ITEM_SET headSet;
1186 
1187  for( const ITEM* item : aHeadSet.CItems() )
1188  {
1189  const LINE* headOrig = static_cast<const LINE*>( item );
1190 
1191  // empty head? nothing to shove...
1192  if( !headOrig->SegmentCount() )
1193  return SH_INCOMPLETE;
1194 
1195  headSet.Add( *headOrig );
1196  }
1197 
1198  m_lineStack.clear();
1199  m_optimizerQueue.clear();
1200  m_logger.Clear();
1201 
1202  reduceSpringback( headSet );
1203 
1204  NODE* parent = m_nodeStack.empty() ? m_root : m_nodeStack.back().m_node;
1205 
1206  m_currentNode = parent->Branch();
1208  int n = 0;
1209 
1210  for( const ITEM* item : aHeadSet.CItems() )
1211  {
1212  const LINE* headOrig = static_cast<const LINE*>( item );
1213  LINE head( *headOrig );
1214  head.ClearSegmentLinks();
1215 
1216  m_currentNode->Add( head );
1217 
1218  head.Mark( MK_HEAD );
1219  head.SetRank( 100000 );
1220  n++;
1221 
1222  if( !pushLine( head ) )
1223  return SH_INCOMPLETE;
1224 
1225  if( head.EndsWithVia() )
1226  {
1227  std::unique_ptr< VIA > headVia = Clone( head.Via() );
1228  headVia->Mark( MK_HEAD );
1229  headVia->SetRank( 100000 );
1230  m_logger.Log( headVia.get(), 0, "head-via" );
1231  m_currentNode->Add( std::move( headVia ) );
1232  }
1233  }
1234 
1235  m_logger.NewGroup( "initial", 0 );
1236  //m_logger.Log( head, 0, "head" );
1237 
1238  st = shoveMainLoop();
1239 
1240  if( st == SH_OK )
1242 
1244 
1245  wxLogTrace( "PNS", "Shove status : %s after %d iterations",
1246  ( st == SH_OK ? "OK" : "FAILURE"), m_iter );
1247 
1248  if( st == SH_OK )
1249  {
1250  pushSpringback( m_currentNode, ITEM_SET(), COST_ESTIMATOR(), m_affectedAreaSum );
1251  }
1252  else
1253  {
1254  delete m_currentNode;
1255  m_currentNode = parent;
1256  }
1257 
1258  return st;
1259 }
void ClearRanks(int aMarkerMask=MK_HEAD|MK_VIOLATION)
Definition: pns_node.cpp:1254
bool reduceSpringback(const ITEM_SET &aHeadItems)
Definition: pns_shove.cpp:541
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
NODE * m_root
Definition: pns_shove.h:148
NODE * Branch()
Function Branch()
Definition: pns_node.cpp:107
void NewGroup(const std::string &aName, int aIter=0)
Definition: pns_logger.cpp:55
void runOptimizer(NODE *aNode)
Definition: pns_shove.cpp:1315
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
void Clear()
Definition: pns_logger.cpp:48
std::unique_ptr< typename std::remove_const< T >::type > Clone(const T &aItem)
Definition: pns_item.h:367
bool pushSpringback(NODE *aNode, const ITEM_SET &aHeadItems, const COST_ESTIMATOR &aCost, const OPT_BOX2I &aAffectedArea)
Definition: pns_shove.cpp:564
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
SHOVE_STATUS shoveMainLoop()
Definition: pns_shove.cpp:1028
void Log(const ITEM *aItem, int aKind=0, const std::string aName=std::string())
Definition: pns_logger.cpp:75
bool m_multiLineMode
Definition: pns_shove.h:159
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
NODE * m_currentNode
Definition: pns_shove.h:149
int RemoveByMarker(int aMarker)
Definition: pns_node.cpp:1276
bool pushLine(const LINE &aL, bool aKeepCurrentOnTop=false)
Definition: pns_shove.cpp:879
void Add(std::unique_ptr< SEGMENT > aSegment, bool aAllowRedundant=false)
Function Add()
Definition: pns_node.cpp:594
LOGGER m_logger
Definition: pns_shove.h:153
int m_iter
Definition: pns_shove.h:157
OPT_BOX2I PNS::SHOVE::totalAffectedArea ( ) const
private

Definition at line 1061 of file pns_shove.cpp.

References m_affectedAreaSum, and m_nodeStack.

Referenced by runOptimizer().

1062 {
1063  OPT_BOX2I area;
1064  if( !m_nodeStack.empty() )
1065  area = m_nodeStack.back().m_affectedArea;
1066 
1067  if( area )
1068  {
1069  if( m_affectedAreaSum )
1070  area->Merge( *m_affectedAreaSum );
1071  } else
1072  area = m_affectedAreaSum;
1073 
1074  return area;
1075 }
OPT_BOX2I m_affectedAreaSum
Definition: pns_shove.h:137
std::vector< SPRINGBACK_TAG > m_nodeStack
Definition: pns_shove.h:144
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:471
void PNS::SHOVE::unwindStack ( SEGMENT aSeg)
private

Definition at line 845 of file pns_shove.cpp.

References m_lineStack, and m_optimizerQueue.

Referenced by onReverseCollidingVia(), pushVia(), shoveIteration(), and unwindStack().

846 {
847  for( std::vector<LINE>::iterator i = m_lineStack.begin(); i != m_lineStack.end() ; )
848  {
849  if( i->ContainsSegment( aSeg ) )
850  i = m_lineStack.erase( i );
851  else
852  i++;
853  }
854 
855  for( std::vector<LINE>::iterator i = m_optimizerQueue.begin(); i != m_optimizerQueue.end() ; )
856  {
857  if( i->ContainsSegment( aSeg ) )
858  i = m_optimizerQueue.erase( i );
859  else
860  i++;
861  }
862 }
std::vector< LINE > m_optimizerQueue
Definition: pns_shove.h:146
std::vector< LINE > m_lineStack
Definition: pns_shove.h:145
void PNS::SHOVE::unwindStack ( ITEM aItem)
private

Definition at line 865 of file pns_shove.cpp.

References PNS::ITEM::LINE_T, PNS::LINE::LinkedSegments(), PNS::ITEM::OfKind(), PNS::ITEM::SEGMENT_T, and unwindStack().

866 {
867  if( aItem->OfKind( ITEM::SEGMENT_T ) )
868  unwindStack( static_cast<SEGMENT*>( aItem ) );
869  else if( aItem->OfKind( ITEM::LINE_T ) )
870  {
871  LINE* l = static_cast<LINE*>( aItem );
872 
873  for( SEGMENT* seg : l->LinkedSegments() )
874  unwindStack( seg );
875  }
876 }
void unwindStack(SEGMENT *aSeg)
Definition: pns_shove.cpp:845
SHOVE::SHOVE_STATUS PNS::SHOVE::walkaroundLoneVia ( LINE aCurrent,
LINE aObstacle,
LINE aShoved 
)
private

Definition at line 131 of file pns_shove.cpp.

References PNS::NODE::CheckColliding(), PNS::LINE::CPoint(), SHAPE_LINE_CHAIN::CPoint(), getClearance(), PNS::VIA::Hull(), 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().

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

Member Data Documentation

OPT_BOX2I PNS::SHOVE::m_affectedAreaSum
private
VIA* PNS::SHOVE::m_draggedVia
private

Definition at line 154 of file pns_shove.h.

Referenced by pushVia(), SHOVE(), and ShoveDraggingVia().

ITEM_SET PNS::SHOVE::m_draggedViaHeadSet
private

Definition at line 155 of file pns_shove.h.

Referenced by pushVia(), and ShoveDraggingVia().

int PNS::SHOVE::m_forceClearance
private

Definition at line 158 of file pns_shove.h.

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

std::vector<LINE> PNS::SHOVE::m_lineStack
private
bool PNS::SHOVE::m_multiLineMode
private
OPT_LINE PNS::SHOVE::m_newHead
private
std::vector<SPRINGBACK_TAG> PNS::SHOVE::m_nodeStack
private
std::vector<LINE> PNS::SHOVE::m_optimizerQueue
private
NODE* PNS::SHOVE::m_root
private

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