KiCad PCB EDA Suite
PNS::OPTIMIZER Class Reference

Perform various optimizations of the lines being routed, attempting to make the lines shorter and less cornery. More...

#include <pns_optimizer.h>

Classes

struct  CACHE_VISITOR
 
struct  CACHED_ITEM
 

Public Types

enum  OptimizationEffort {
  MERGE_SEGMENTS = 0x01, SMART_PADS = 0x02, MERGE_OBTUSE = 0x04, FANOUT_CLEANUP = 0x08,
  KEEP_TOPOLOGY = 0x10, PRESERVE_VERTEX = 0x20, RESTRICT_VERTEX_RANGE = 0x40, MERGE_COLINEAR = 0x80,
  RESTRICT_AREA = 0x100
}
 

Public Member Functions

 OPTIMIZER (NODE *aWorld)
 Optimizer. More...
 
 ~OPTIMIZER ()
 A quick shortcut to optimize a line without creating and setting up an optimizer. More...
 
bool Optimize (LINE *aLine, LINE *aResult=NULL)
 
bool Optimize (DIFF_PAIR *aPair)
 
void SetWorld (NODE *aNode)
 
void CacheRemove (ITEM *aItem)
 
void ClearCache (bool aStaticOnly=false)
 
void SetCollisionMask (int aMask)
 
void SetEffortLevel (int aEffort)
 
void SetPreserveVertex (const VECTOR2I &aV)
 
void SetRestrictVertexRange (int aStart, int aEnd)
 
void SetRestrictArea (const BOX2I &aArea, bool aStrict=true)
 
void ClearConstraints ()
 
void AddConstraint (OPT_CONSTRAINT *aConstraint)
 

Static Public Member Functions

static bool Optimize (LINE *aLine, int aEffortLevel, NODE *aWorld, const VECTOR2I aV=VECTOR2I(0, 0))
 

Private Types

typedef std::vector< SHAPE_LINE_CHAINBREAKOUT_LIST
 

Private Member Functions

bool mergeObtuse (LINE *aLine)
 
bool mergeFull (LINE *aLine)
 
bool mergeColinear (LINE *aLine)
 
bool runSmartPads (LINE *aLine)
 
bool mergeStep (LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
 
bool fanoutCleanup (LINE *aLine)
 
bool mergeDpSegments (DIFF_PAIR *aPair)
 
bool mergeDpStep (DIFF_PAIR *aPair, bool aTryP, int step)
 
bool checkColliding (ITEM *aItem, bool aUpdateCache=true)
 
bool checkColliding (LINE *aLine, const SHAPE_LINE_CHAIN &aOptPath)
 
void cacheAdd (ITEM *aItem, bool aIsStatic)
 
void removeCachedSegments (LINE *aLine, int aStartVertex=0, int aEndVertex=-1)
 
bool checkConstraints (int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
 
BREAKOUT_LIST circleBreakouts (int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
 
BREAKOUT_LIST rectBreakouts (int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
 
BREAKOUT_LIST customBreakouts (int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
 
BREAKOUT_LIST computeBreakouts (int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
 
int smartPadsSingle (LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)
 
ITEMfindPadOrVia (int aLayer, int aNet, const VECTOR2I &aP) const
 

Private Attributes

SHAPE_INDEX_LIST< ITEM * > m_cache
 
std::vector< OPT_CONSTRAINT * > m_constraints
 
std::unordered_map< ITEM *, CACHED_ITEMm_cacheTags
 
NODEm_world
 
int m_collisionKindMask
 
int m_effortLevel
 
VECTOR2I m_preservedVertex
 
std::pair< int, int > m_restrictedVertexRange
 
BOX2I m_restrictArea
 
bool m_restrictAreaIsStrict
 

Static Private Attributes

static const int MaxCachedItems = 256
 

Detailed Description

Perform various optimizations of the lines being routed, attempting to make the lines shorter and less cornery.

There are 3 kinds of optimizations so far:

  • Merging obtuse segments (MERGE_OBTUSE): tries to join together as many obtuse segments as possible without causing collisions.
  • Rerouting path between pair of line corners with a 2-segment "\__" line and iteratively repeating the procedure as long as the total cost of the line keeps decreasing.
  • "Smart Pads" - that is, rerouting pad/via exits to make them look nice (SMART_PADS).

Definition at line 94 of file pns_optimizer.h.

Member Typedef Documentation

◆ BREAKOUT_LIST

typedef std::vector<SHAPE_LINE_CHAIN> PNS::OPTIMIZER::BREAKOUT_LIST
private

Definition at line 160 of file pns_optimizer.h.

Member Enumeration Documentation

◆ OptimizationEffort

Enumerator
MERGE_SEGMENTS 

Reduce corner cost iteratively.

SMART_PADS 

Reroute pad exits.

MERGE_OBTUSE 

Reduce corner cost by merging obtuse segments.

FANOUT_CLEANUP 

Simplify pad-pad and pad-via connections if possible.

KEEP_TOPOLOGY 
PRESERVE_VERTEX 
RESTRICT_VERTEX_RANGE 
MERGE_COLINEAR 

Merge co-linear segments.

RESTRICT_AREA 

Definition at line 97 of file pns_optimizer.h.

98  {
99  MERGE_SEGMENTS = 0x01,
100  SMART_PADS = 0x02,
101  MERGE_OBTUSE = 0x04,
102  FANOUT_CLEANUP = 0x08,
103  KEEP_TOPOLOGY = 0x10,
104  PRESERVE_VERTEX = 0x20,
105  RESTRICT_VERTEX_RANGE = 0x40,
106  MERGE_COLINEAR = 0x80,
107  RESTRICT_AREA = 0x100
108  };
Simplify pad-pad and pad-via connections if possible.
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
Reduce corner cost by merging obtuse segments.
Merge co-linear segments.
Reroute pad exits.

Constructor & Destructor Documentation

◆ OPTIMIZER()

PNS::OPTIMIZER::OPTIMIZER ( NODE aWorld)

Optimizer.

Definition at line 120 of file pns_optimizer.cpp.

120  :
121  m_world( aWorld ),
124  m_restrictAreaIsStrict( false )
125 {
126 }
bool m_restrictAreaIsStrict
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99

◆ ~OPTIMIZER()

PNS::OPTIMIZER::~OPTIMIZER ( )

A quick shortcut to optimize a line without creating and setting up an optimizer.

Definition at line 129 of file pns_optimizer.cpp.

130 {
131 }

Member Function Documentation

◆ AddConstraint()

void PNS::OPTIMIZER::AddConstraint ( OPT_CONSTRAINT aConstraint)

Definition at line 414 of file pns_optimizer.cpp.

415 {
416  m_constraints.push_back( aConstraint );
417 }
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

Referenced by Optimize().

◆ cacheAdd()

void PNS::OPTIMIZER::cacheAdd ( ITEM aItem,
bool  aIsStatic = false 
)
private

Definition at line 162 of file pns_optimizer.cpp.

163 {
164  if( m_cacheTags.find( aItem ) != m_cacheTags.end() )
165  return;
166 
167  m_cache.Add( aItem );
168  m_cacheTags[aItem].m_hits = 1;
169  m_cacheTags[aItem].m_isStatic = aIsStatic;
170 }
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References m_cache, and m_cacheTags.

◆ CacheRemove()

void PNS::OPTIMIZER::CacheRemove ( ITEM aItem)

Definition at line 192 of file pns_optimizer.cpp.

193 {
194  if( aItem->Kind() == ITEM::LINE_T )
195  removeCachedSegments( static_cast<LINE*>( aItem ) );
196 }
void removeCachedSegments(LINE *aLine, int aStartVertex=0, int aEndVertex=-1)

References PNS::ITEM::Kind(), PNS::ITEM::LINE_T, and removeCachedSegments().

◆ checkColliding() [1/2]

bool PNS::OPTIMIZER::checkColliding ( ITEM aItem,
bool  aUpdateCache = true 
)
private

Definition at line 397 of file pns_optimizer.cpp.

398 {
399  CACHE_VISITOR v( aItem, m_world, m_collisionKindMask );
400 
401  return static_cast<bool>( m_world->CheckColliding( aItem ) );
402 }
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:425

References PNS::NODE::CheckColliding(), m_collisionKindMask, and m_world.

Referenced by checkColliding(), mergeObtuse(), mergeStep(), and smartPadsSingle().

◆ checkColliding() [2/2]

bool PNS::OPTIMIZER::checkColliding ( LINE aLine,
const SHAPE_LINE_CHAIN aOptPath 
)
private

Definition at line 434 of file pns_optimizer.cpp.

435 {
436  LINE tmp( *aLine, aOptPath );
437 
438  return checkColliding( &tmp );
439 }
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)

References checkColliding().

◆ checkConstraints()

bool PNS::OPTIMIZER::checkConstraints ( int  aVertex1,
int  aVertex2,
LINE aOriginLine,
const SHAPE_LINE_CHAIN aCurrentPath,
const SHAPE_LINE_CHAIN aReplacement 
)
private

Definition at line 420 of file pns_optimizer.cpp.

423 {
424  for( OPT_CONSTRAINT* c : m_constraints )
425  {
426  if( !c->Check( aVertex1, aVertex2, aOriginLine, aCurrentPath, aReplacement ) )
427  return false;
428  }
429 
430  return true;
431 }
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

Referenced by mergeStep().

◆ circleBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::circleBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 718 of file pns_optimizer.cpp.

720 {
721  BREAKOUT_LIST breakouts;
722 
723  for( int angle = 0; angle < 360; angle += 45 )
724  {
725  const SHAPE_CIRCLE* cir = static_cast<const SHAPE_CIRCLE*>( aShape );
727  VECTOR2I p0 = cir->GetCenter();
728  VECTOR2I v0( cir->GetRadius() * M_SQRT2, 0 );
729 
730  l.Append( p0 );
731  l.Append( p0 + v0.Rotate( angle * M_PI / 180.0 ) );
732  breakouts.push_back( l );
733  }
734 
735  return breakouts;
736 }
int GetRadius() const
Definition: shape_circle.h:107
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), and VECTOR2< T >::Rotate().

Referenced by computeBreakouts().

◆ ClearCache()

void PNS::OPTIMIZER::ClearCache ( bool  aStaticOnly = false)

Definition at line 199 of file pns_optimizer.cpp.

200 {
201  if( !aStaticOnly )
202  {
203  m_cacheTags.clear();
204  m_cache.Clear();
205  return;
206  }
207 
208  for( auto i = m_cacheTags.begin(); i!= m_cacheTags.end(); ++i )
209  {
210  if( i->second.m_isStatic )
211  {
212  m_cache.Remove( i->first );
213  m_cacheTags.erase( i->first );
214  }
215  }
216 }
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References m_cache, and m_cacheTags.

◆ ClearConstraints()

void PNS::OPTIMIZER::ClearConstraints ( )

Definition at line 405 of file pns_optimizer.cpp.

406 {
407  for( OPT_CONSTRAINT* c : m_constraints )
408  delete c;
409 
410  m_constraints.clear();
411 }
std::vector< OPT_CONSTRAINT * > m_constraints

References m_constraints.

◆ computeBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::computeBreakouts ( int  aWidth,
const ITEM aItem,
bool  aPermitDiagonal 
) const
private

Definition at line 836 of file pns_optimizer.cpp.

838 {
839  switch( aItem->Kind() )
840  {
841  case ITEM::VIA_T:
842  {
843  const VIA* via = static_cast<const VIA*>( aItem );
844  return circleBreakouts( aWidth, via->Shape(), aPermitDiagonal );
845  }
846 
847  case ITEM::SOLID_T:
848  {
849  const SHAPE* shape = aItem->Shape();
850 
851  switch( shape->Type() )
852  {
853  case SH_RECT:
854  return rectBreakouts( aWidth, shape, aPermitDiagonal );
855 
856  case SH_SEGMENT:
857  {
858  const SHAPE_SEGMENT* seg = static_cast<const SHAPE_SEGMENT*> (shape);
859  const SHAPE_RECT rect = ApproximateSegmentAsRect ( *seg );
860  return rectBreakouts( aWidth, &rect, aPermitDiagonal );
861  }
862 
863  case SH_CIRCLE:
864  return circleBreakouts( aWidth, shape, aPermitDiagonal );
865 
866  case SH_SIMPLE:
867  return customBreakouts( aWidth, aItem, aPermitDiagonal );
868 
869  default:
870  break;
871  }
872 
873  break;
874  }
875 
876  default:
877  break;
878  }
879 
880  return BREAKOUT_LIST();
881 }
Definition: track.h:343
BREAKOUT_LIST circleBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST rectBreakouts(int aWidth, const SHAPE *aShape, bool aPermitDiagonal) const
BREAKOUT_LIST customBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
An abstract shape on 2D plane.
Definition: shape.h:116
circle
Definition: shape.h:46
SHAPE_RECT ApproximateSegmentAsRect(const SHAPE_SEGMENT &aSeg)
Definition: pns_utils.cpp:225
axis-aligned rectangle
Definition: shape.h:43
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST
simple polygon
Definition: shape.h:47
SHAPE_TYPE Type() const
Return the type of the shape.
Definition: shape.h:94
line segment
Definition: shape.h:44

References PNS::ApproximateSegmentAsRect(), circleBreakouts(), customBreakouts(), PNS::ITEM::Kind(), rectBreakouts(), SH_CIRCLE, SH_RECT, SH_SEGMENT, SH_SIMPLE, PNS::ITEM::Shape(), PNS::ITEM::SOLID_T, SHAPE_BASE::Type(), via, and PNS::ITEM::VIA_T.

Referenced by smartPadsSingle().

◆ customBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::customBreakouts ( int  aWidth,
const ITEM aItem,
bool  aPermitDiagonal 
) const
private

Definition at line 739 of file pns_optimizer.cpp.

741 {
742  BREAKOUT_LIST breakouts;
743  const SHAPE_SIMPLE* convex = static_cast<const SHAPE_SIMPLE*>( aItem->Shape() );
744 
745  BOX2I bbox = convex->BBox( 0 );
746  VECTOR2I p0 = static_cast<const SOLID*>( aItem )->Pos();
747  // must be large enough to guarantee intersecting the convex polygon
748  int length = std::max( bbox.GetWidth(), bbox.GetHeight() ) / 2 + 5;
749 
750  for( int angle = 0; angle < 360; angle += ( aPermitDiagonal ? 45 : 90 ) )
751  {
753  VECTOR2I v0( p0 + VECTOR2I( length, 0 ).Rotate( angle * M_PI / 180.0 ) );
754  SHAPE_LINE_CHAIN::INTERSECTIONS intersections;
755  int n = convex->Vertices().Intersect( SEG( p0, v0 ), intersections );
756  // if n == 1 intersected a segment
757  // if n == 2 intersected the common point of 2 segments
758  // n == 0 can not happen I think, but...
759  if( n > 0 )
760  {
761  l.Append( p0 );
762 
763  // for a breakout distance relative to the distance between
764  // center and polygon edge
765  //l.Append( intersections[0].p + (v0 - p0).Resize( (intersections[0].p - p0).EuclideanNorm() * 0.4 ) );
766 
767  // for an absolute breakout distance, e.g. 0.1 mm
768  //l.Append( intersections[0].p + (v0 - p0).Resize( 100000 ) );
769 
770  // for the breakout right on the polygon edge
771  l.Append( intersections[0].p );
772 
773  breakouts.push_back( l );
774  }
775  }
776 
777  return breakouts;
778 }
SHAPE_SIMPLE.
Definition: shape_simple.h:43
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_simple.h:82
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const SHAPE_LINE_CHAIN & Vertices() const
Function Vertices()
Definition: shape_simple.h:133
Definition: seg.h:41
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_SIMPLE::BBox(), SHAPE_LINE_CHAIN::Intersect(), PNS::ITEM::Shape(), and SHAPE_SIMPLE::Vertices().

Referenced by computeBreakouts().

◆ fanoutCleanup()

bool PNS::OPTIMIZER::fanoutCleanup ( LINE aLine)
private

Definition at line 1065 of file pns_optimizer.cpp.

1066 {
1067  if( aLine->PointCount() < 3 )
1068  return false;
1069 
1070  VECTOR2I p_start = aLine->CPoint( 0 ), p_end = aLine->CPoint( -1 );
1071 
1072  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1073  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1074 
1075  int thr = aLine->Width() * 10;
1076  int len = aLine->CLine().Length();
1077 
1078  if( !startPad )
1079  return false;
1080 
1081  bool startMatch = startPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1082  bool endMatch = false;
1083 
1084  if(endPad)
1085  {
1086  endMatch = endPad->OfKind( ITEM::VIA_T | ITEM::SOLID_T );
1087  }
1088  else
1089  {
1090  endMatch = aLine->EndsWithVia();
1091  }
1092 
1093  if( startMatch && endMatch && len < thr )
1094  {
1095  for( int i = 0; i < 2; i++ )
1096  {
1097  SHAPE_LINE_CHAIN l2 = DIRECTION_45().BuildInitialTrace( p_start, p_end, i );
1098  LINE repl;
1099  repl = LINE( *aLine, l2 );
1100 
1101  if( !m_world->CheckColliding( &repl ) )
1102  {
1103  aLine->SetShape( repl.CLine() );
1104  return true;
1105  }
1106  }
1107  }
1108 
1109  return false;
1110 }
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
SHAPE_LINE_CHAIN.
OPT_OBSTACLE CheckColliding(const ITEM *aItem, int aKindMask=ITEM::ANY_T)
Check if the item collides with anything else in the world, and if found, returns the obstacle.
Definition: pns_node.cpp:425
bool OfKind(int aKindMask) const
Return true if the item's type matches the mask aKindMask.
Definition: pns_item.h:134

References DIRECTION_45::BuildInitialTrace(), PNS::NODE::CheckColliding(), PNS::LINE::CLine(), PNS::LINE::CPoint(), PNS::LINE::EndsWithVia(), findPadOrVia(), PNS::ITEM::Layer(), SHAPE_LINE_CHAIN::Length(), m_world, PNS::ITEM::Net(), PNS::ITEM::OfKind(), PNS::LINE::PointCount(), PNS::LINE::SetShape(), PNS::ITEM::SOLID_T, PNS::ITEM::VIA_T, and PNS::LINE::Width().

Referenced by Optimize().

◆ findPadOrVia()

ITEM * PNS::OPTIMIZER::findPadOrVia ( int  aLayer,
int  aNet,
const VECTOR2I aP 
) const
private

Definition at line 884 of file pns_optimizer.cpp.

885 {
886  JOINT* jt = m_world->FindJoint( aP, aLayer, aNet );
887 
888  if( !jt )
889  return NULL;
890 
891  for( ITEM* item : jt->LinkList() )
892  {
893  if( item->OfKind( ITEM::VIA_T | ITEM::SOLID_T ) )
894  return item;
895  }
896 
897  return NULL;
898 }
#define NULL
JOINT * FindJoint(const VECTOR2I &aPos, int aLayer, int aNet)
Search for a joint at a given position, layer and belonging to given net.
Definition: pns_node.cpp:1046

References PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_world, NULL, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.

Referenced by fanoutCleanup(), and runSmartPads().

◆ mergeColinear()

bool PNS::OPTIMIZER::mergeColinear ( LINE aLine)
private

Definition at line 562 of file pns_optimizer.cpp.

563 {
564  SHAPE_LINE_CHAIN& line = aLine->Line();
565  const std::vector<ssize_t> shapes = line.CShapes();
566 
567  int nSegs = line.SegmentCount();
568 
569  for( int segIdx = 0; segIdx < line.SegmentCount() - 1; ++segIdx )
570  {
571  SEG s1 = line.CSegment( segIdx );
572  SEG s2 = line.CSegment( segIdx + 1 );
573 
574  // Skip zero-length segs caused by abutting arcs
575  if( s1.SquaredLength() == 0 || s2.SquaredLength() == 0 )
576  continue;
577 
578  if( s1.Collinear( s2 ) )
579  {
580  // We should not see a collinear vertex inside an arc
581  wxASSERT( shapes[segIdx + 1] < 0 );
582  line.Remove( segIdx + 1 );
583  }
584  }
585 
586  return line.SegmentCount() < nSegs;
587 }
ecoord SquaredLength() const
Definition: seg.h:360
const std::vector< ssize_t > & CShapes() const
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
int SegmentCount() const
Function SegmentCount()
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:273
Definition: seg.h:41
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.

References SEG::Collinear(), SHAPE_LINE_CHAIN::CSegment(), SHAPE_LINE_CHAIN::CShapes(), PNS::LINE::Line(), SHAPE_LINE_CHAIN::Remove(), SHAPE_LINE_CHAIN::SegmentCount(), and SEG::SquaredLength().

Referenced by Optimize().

◆ mergeDpSegments()

bool PNS::OPTIMIZER::mergeDpSegments ( DIFF_PAIR aPair)
private

Definition at line 1286 of file pns_optimizer.cpp.

1287 {
1288  int step_p = aPair->CP().SegmentCount() - 2;
1289  int step_n = aPair->CN().SegmentCount() - 2;
1290 
1291  while( 1 )
1292  {
1293  int n_segs_p = aPair->CP().SegmentCount();
1294  int n_segs_n = aPair->CN().SegmentCount();
1295 
1296  int max_step_p = n_segs_p - 2;
1297  int max_step_n = n_segs_n - 2;
1298 
1299  if( step_p > max_step_p )
1300  step_p = max_step_p;
1301 
1302  if( step_n > max_step_n )
1303  step_n = max_step_n;
1304 
1305  if( step_p < 1 && step_n < 1 )
1306  break;
1307 
1308  bool found_anything_p = false;
1309  bool found_anything_n = false;
1310 
1311  if( step_p > 1 )
1312  found_anything_p = mergeDpStep( aPair, true, step_p );
1313 
1314  if( step_n > 1 )
1315  found_anything_n = mergeDpStep( aPair, false, step_n );
1316 
1317  if( !found_anything_n && !found_anything_p )
1318  {
1319  step_n--;
1320  step_p--;
1321  }
1322  }
1323  return true;
1324 }
bool mergeDpStep(DIFF_PAIR *aPair, bool aTryP, int step)

References PNS::DIFF_PAIR::CN(), PNS::DIFF_PAIR::CP(), mergeDpStep(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by Optimize().

◆ mergeDpStep()

bool PNS::OPTIMIZER::mergeDpStep ( DIFF_PAIR aPair,
bool  aTryP,
int  step 
)
private

Definition at line 1223 of file pns_optimizer.cpp.

1224 {
1225  int n = 1;
1226 
1227  SHAPE_LINE_CHAIN currentPath = aTryP ? aPair->CP() : aPair->CN();
1228  SHAPE_LINE_CHAIN coupledPath = aTryP ? aPair->CN() : aPair->CP();
1229 
1230  int n_segs = currentPath.SegmentCount() - 1;
1231 
1232  int64_t clenPre = aPair->CoupledLength( currentPath, coupledPath );
1233  int64_t budget = clenPre / 10; // fixme: come up with somethig more intelligent here...
1234 
1235  while( n < n_segs - step )
1236  {
1237  const SEG s1 = currentPath.CSegment( n );
1238  const SEG s2 = currentPath.CSegment( n + step );
1239 
1240  DIRECTION_45 dir1( s1 );
1241  DIRECTION_45 dir2( s2 );
1242 
1243  if( dir1.IsObtuse( dir2 ) )
1244  {
1245  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B,
1246  dir1.IsDiagonal() );
1247  SHAPE_LINE_CHAIN newRef;
1248  SHAPE_LINE_CHAIN newCoup;
1249  int64_t deltaCoupled = -1, deltaUni = -1;
1250 
1251  newRef = currentPath;
1252  newRef.Replace( s1.Index(), s2.Index(), bypass );
1253 
1254  deltaUni = aPair->CoupledLength ( newRef, coupledPath ) - clenPre + budget;
1255 
1256  if( coupledBypass( m_world, aPair, aTryP, newRef, bypass, coupledPath, newCoup ) )
1257  {
1258  deltaCoupled = aPair->CoupledLength( newRef, newCoup ) - clenPre + budget;
1259 
1260  if( deltaCoupled >= 0 )
1261  {
1262  newRef.Simplify();
1263  newCoup.Simplify();
1264 
1265  aPair->SetShape( newRef, newCoup, !aTryP );
1266  return true;
1267  }
1268  }
1269  else if( deltaUni >= 0 && verifyDpBypass( m_world, aPair, aTryP, newRef, coupledPath ) )
1270  {
1271  newRef.Simplify();
1272  coupledPath.Simplify();
1273 
1274  aPair->SetShape( newRef, coupledPath, !aTryP );
1275  return true;
1276  }
1277  }
1278 
1279  n++;
1280  }
1281 
1282  return false;
1283 }
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:373
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
bool coupledBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aRef, const SHAPE_LINE_CHAIN &aRefBypass, const SHAPE_LINE_CHAIN &aCoupled, SHAPE_LINE_CHAIN &aNewCoupled)
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:41
bool verifyDpBypass(NODE *aNode, DIFF_PAIR *aPair, bool aRefIsP, const SHAPE_LINE_CHAIN &aNewRef, const SHAPE_LINE_CHAIN &aNewCoupled)
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:49
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
VECTOR2I B
Definition: seg.h:50

References SEG::A, SEG::B, DIRECTION_45::BuildInitialTrace(), PNS::DIFF_PAIR::CN(), PNS::coupledBypass(), PNS::DIFF_PAIR::CoupledLength(), PNS::DIFF_PAIR::CP(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), DIRECTION_45::IsDiagonal(), DIRECTION_45::IsObtuse(), m_world, SHAPE_LINE_CHAIN::Replace(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::DIFF_PAIR::SetShape(), SHAPE_LINE_CHAIN::Simplify(), and PNS::verifyDpBypass().

Referenced by mergeDpSegments().

◆ mergeFull()

bool PNS::OPTIMIZER::mergeFull ( LINE aLine)
private

Definition at line 522 of file pns_optimizer.cpp.

523 {
524  SHAPE_LINE_CHAIN& line = aLine->Line();
525  int step = line.SegmentCount() - 1;
526 
527  int segs_pre = line.SegmentCount();
528 
529  line.Simplify();
530 
531  if( step < 0 )
532  return false;
533 
534  SHAPE_LINE_CHAIN current_path( line );
535 
536  while( 1 )
537  {
538  int n_segs = current_path.SegmentCount();
539  int max_step = n_segs - 2;
540 
541  if( step > max_step )
542  step = max_step;
543 
544  if( step < 1 )
545  break;
546 
547  bool found_anything = mergeStep( aLine, current_path, step );
548 
549  if( !found_anything )
550  step--;
551 
552  if( !step )
553  break;
554  }
555 
556  aLine->SetShape( current_path );
557 
558  return current_path.SegmentCount() < segs_pre;
559 }
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
bool mergeStep(LINE *aLine, SHAPE_LINE_CHAIN &aCurrentLine, int step)
int SegmentCount() const
Function SegmentCount()
SHAPE_LINE_CHAIN.

References PNS::LINE::Line(), mergeStep(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().

Referenced by Optimize().

◆ mergeObtuse()

bool PNS::OPTIMIZER::mergeObtuse ( LINE aLine)
private

Definition at line 442 of file pns_optimizer.cpp.

443 {
444  SHAPE_LINE_CHAIN& line = aLine->Line();
445 
446  int step = line.PointCount() - 3;
447  int iter = 0;
448  int segs_pre = line.SegmentCount();
449 
450  if( step < 0 )
451  return false;
452 
453  SHAPE_LINE_CHAIN current_path( line );
454 
455  while( 1 )
456  {
457  iter++;
458  int n_segs = current_path.SegmentCount();
459  int max_step = n_segs - 2;
460 
461  if( step > max_step )
462  step = max_step;
463 
464  if( step < 2 )
465  {
466  line = current_path;
467  return current_path.SegmentCount() < segs_pre;
468  }
469 
470  bool found_anything = false;
471 
472  for( int n = 0; n < n_segs - step; n++ )
473  {
474  const SEG s1 = current_path.CSegment( n );
475  const SEG s2 = current_path.CSegment( n + step );
476  SEG s1opt, s2opt;
477 
478  if( DIRECTION_45( s1 ).IsObtuse( DIRECTION_45( s2 ) ) )
479  {
480  VECTOR2I ip = *s1.IntersectLines( s2 );
481 
482  s1opt = SEG( s1.A, ip );
483  s2opt = SEG( ip, s2.B );
484 
485  if( DIRECTION_45( s1opt ).IsObtuse( DIRECTION_45( s2opt ) ) )
486  {
487  SHAPE_LINE_CHAIN opt_path;
488  opt_path.Append( s1opt.A );
489  opt_path.Append( s1opt.B );
490  opt_path.Append( s2opt.B );
491 
492  LINE opt_track( *aLine, opt_path );
493 
494  if( !checkColliding( &opt_track ) )
495  {
496  current_path.Replace( s1.Index() + 1, s2.Index(), ip );
497  // removeCachedSegments(aLine, s1.Index(), s2.Index());
498  n_segs = current_path.SegmentCount();
499  found_anything = true;
500  break;
501  }
502  }
503  }
504  }
505 
506  if( !found_anything )
507  {
508  if( step <= 2 )
509  {
510  line = current_path;
511  return line.SegmentCount() < segs_pre;
512  }
513 
514  step--;
515  }
516  }
517 
518  return line.SegmentCount() < segs_pre;
519 }
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:373
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:208
int PointCount() const
Function PointCount()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:41
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:49
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
VECTOR2I B
Definition: seg.h:50

References SEG::A, SHAPE_LINE_CHAIN::Append(), SEG::B, checkColliding(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), SEG::IntersectLines(), PNS::LINE::Line(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Replace(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by Optimize().

◆ mergeStep()

bool PNS::OPTIMIZER::mergeStep ( LINE aLine,
SHAPE_LINE_CHAIN aCurrentLine,
int  step 
)
private

Definition at line 653 of file pns_optimizer.cpp.

654 {
655  int n_segs = aCurrentPath.SegmentCount();
656 
657  int cost_orig = COST_ESTIMATOR::CornerCost( aCurrentPath );
658 
659  if( aLine->SegmentCount() < 2 )
660  return false;
661 
662  DIRECTION_45 orig_start( aLine->CSegment( 0 ) );
663  DIRECTION_45 orig_end( aLine->CSegment( -1 ) );
664 
665 
666  for( int n = 0; n < n_segs - step; n++ )
667  {
668  // Do not attempt to merge false segments that are part of an arc
669  if( aCurrentPath.isArc( n ) || aCurrentPath.isArc( static_cast<std::size_t>( n ) + step ) )
670  continue;
671 
672  const SEG s1 = aCurrentPath.CSegment( n );
673  const SEG s2 = aCurrentPath.CSegment( n + step );
674 
676  SHAPE_LINE_CHAIN* picked = NULL;
677  int cost[2];
678 
679  for( int i = 0; i < 2; i++ )
680  {
681  SHAPE_LINE_CHAIN bypass = DIRECTION_45().BuildInitialTrace( s1.A, s2.B, i );
682  cost[i] = INT_MAX;
683 
684  bool ok = false;
685 
686  if( !checkColliding( aLine, bypass ) )
687  {
688  //printf("Chk-constraints: %d %d\n", n, n+step+1 );
689  ok = checkConstraints ( n, n + step + 1, aLine, aCurrentPath, bypass );
690  }
691 
692  if( ok )
693  {
694  path[i] = aCurrentPath;
695  path[i].Replace( s1.Index(), s2.Index(), bypass );
696  path[i].Simplify();
697  cost[i] = COST_ESTIMATOR::CornerCost( path[i] );
698  }
699  }
700 
701  if( cost[0] < cost_orig && cost[0] < cost[1] )
702  picked = &path[0];
703  else if( cost[1] < cost_orig )
704  picked = &path[1];
705 
706  if( picked )
707  {
708  n_segs = aCurrentPath.SegmentCount();
709  aCurrentPath = *picked;
710  return true;
711  }
712  }
713 
714  return false;
715 }
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:373
bool checkConstraints(int aVertex1, int aVertex2, LINE *aOriginLine, const SHAPE_LINE_CHAIN &aCurrentPath, const SHAPE_LINE_CHAIN &aReplacement)
#define NULL
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
Definition: seg.h:41
SHAPE_LINE_CHAIN.
VECTOR2I A
Definition: seg.h:49
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
VECTOR2I B
Definition: seg.h:50

References SEG::A, SEG::B, DIRECTION_45::BuildInitialTrace(), checkColliding(), checkConstraints(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CSegment(), SHAPE_LINE_CHAIN::CSegment(), SEG::Index(), SHAPE_LINE_CHAIN::isArc(), NULL, path, PNS::LINE::SegmentCount(), and SHAPE_LINE_CHAIN::SegmentCount().

Referenced by mergeFull().

◆ Optimize() [1/3]

bool PNS::OPTIMIZER::Optimize ( LINE aLine,
int  aEffortLevel,
NODE aWorld,
const VECTOR2I  aV = VECTOR2I(0, 0) 
)
static

Definition at line 1049 of file pns_optimizer.cpp.

1050 {
1051  OPTIMIZER opt( aWorld );
1052 
1054 
1055  opt.SetEffortLevel( aEffortLevel );
1056  opt.SetCollisionMask( -1 );
1057 
1058  if( aEffortLevel & OPTIMIZER::PRESERVE_VERTEX )
1059  opt.SetPreserveVertex( aV );
1060 
1061  return opt.Optimize( aLine );
1062 }
static DEBUG_DECORATOR * g_dbg
OPTIMIZER(NODE *aWorld)
Optimizer.
virtual DEBUG_DECORATOR * GetDebugDecorator()=0
ROUTER_IFACE * GetInterface() const
Definition: pns_router.h:210
static ROUTER * GetInstance()
Definition: pns_router.cpp:79

References PNS::g_dbg, PNS::ROUTER_IFACE::GetDebugDecorator(), PNS::ROUTER::GetInstance(), PNS::ROUTER::GetInterface(), Optimize(), PRESERVE_VERTEX, SetCollisionMask(), SetEffortLevel(), and SetPreserveVertex().

Referenced by Optimize(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::optimizeTailHeadTransition(), PNS::LINE_PLACER::rhShoveOnly(), PNS::LINE_PLACER::rhWalkOnly(), PNS::WALKAROUND::Route(), PNS::SHOVE::runOptimizer(), PNS::LINE_PLACER::simplifyNewLine(), and PNS::DIFF_PAIR_PLACER::tryWalkDp().

◆ Optimize() [2/3]

bool PNS::OPTIMIZER::Optimize ( LINE aLine,
LINE aResult = NULL 
)

Definition at line 590 of file pns_optimizer.cpp.

591 {
592  if( !aResult )
593  {
594  aResult = aLine;
595  }
596  else
597  {
598  *aResult = *aLine;
599  aResult->ClearLinks();
600  }
601 
602  bool hasArcs = aLine->ArcCount();
603  bool rv = false;
604 
606  {
607  auto c = new PRESERVE_VERTEX_CONSTRAINT( m_world, m_preservedVertex );
608  AddConstraint( c );
609  }
610 
612  {
613  auto c = new RESTRICT_VERTEX_RANGE_CONSTRAINT( m_world, m_restrictedVertexRange.first,
614  m_restrictedVertexRange.second );
615  AddConstraint( c );
616  }
617 
619  {
620  auto c = new AREA_CONSTRAINT( m_world, m_restrictArea, m_restrictAreaIsStrict );
621  AddConstraint( c );
622  }
623 
625  {
626  auto c = new KEEP_TOPOLOGY_CONSTRAINT( m_world );
627  AddConstraint( c );
628  }
629 
630  // TODO: Fix for arcs
631  if( !hasArcs && m_effortLevel & MERGE_SEGMENTS )
632  rv |= mergeFull( aResult );
633 
634  // TODO: Fix for arcs
635  if( !hasArcs && m_effortLevel & MERGE_OBTUSE )
636  rv |= mergeObtuse( aResult );
637 
639  rv |= mergeColinear( aResult );
640 
641  // TODO: Fix for arcs
642  if( !hasArcs && m_effortLevel & SMART_PADS )
643  rv |= runSmartPads( aResult );
644 
645  // TODO: Fix for arcs
646  if( !hasArcs && m_effortLevel & FANOUT_CLEANUP )
647  rv |= fanoutCleanup( aResult );
648 
649  return rv;
650 }
Simplify pad-pad and pad-via connections if possible.
bool runSmartPads(LINE *aLine)
bool mergeFull(LINE *aLine)
bool m_restrictAreaIsStrict
void AddConstraint(OPT_CONSTRAINT *aConstraint)
bool mergeObtuse(LINE *aLine)
Reduce corner cost iteratively.
Definition: pns_optimizer.h:99
VECTOR2I m_preservedVertex
Reduce corner cost by merging obtuse segments.
bool fanoutCleanup(LINE *aLine)
bool mergeColinear(LINE *aLine)
Merge co-linear segments.
std::pair< int, int > m_restrictedVertexRange
Reroute pad exits.

References AddConstraint(), PNS::LINE::ArcCount(), PNS::LINK_HOLDER::ClearLinks(), FANOUT_CLEANUP, fanoutCleanup(), KEEP_TOPOLOGY, m_effortLevel, m_preservedVertex, m_restrictArea, m_restrictAreaIsStrict, m_restrictedVertexRange, m_world, MERGE_COLINEAR, MERGE_OBTUSE, MERGE_SEGMENTS, mergeColinear(), mergeFull(), mergeObtuse(), PRESERVE_VERTEX, RESTRICT_AREA, RESTRICT_VERTEX_RANGE, runSmartPads(), and SMART_PADS.

◆ Optimize() [3/3]

bool PNS::OPTIMIZER::Optimize ( DIFF_PAIR aPair)

Definition at line 1327 of file pns_optimizer.cpp.

1328 {
1329  return mergeDpSegments( aPair );
1330 }
bool mergeDpSegments(DIFF_PAIR *aPair)

References mergeDpSegments().

◆ rectBreakouts()

OPTIMIZER::BREAKOUT_LIST PNS::OPTIMIZER::rectBreakouts ( int  aWidth,
const SHAPE aShape,
bool  aPermitDiagonal 
) const
private

Definition at line 781 of file pns_optimizer.cpp.

783 {
784  const SHAPE_RECT* rect = static_cast<const SHAPE_RECT*>(aShape);
785  VECTOR2I s = rect->GetSize();
786  VECTOR2I c = rect->GetPosition() + VECTOR2I( s.x / 2, s.y / 2 );
787  BREAKOUT_LIST breakouts;
788 
789  VECTOR2I d_offset;
790 
791  d_offset.x = ( s.x > s.y ) ? ( s.x - s.y ) / 2 : 0;
792  d_offset.y = ( s.x < s.y ) ? ( s.y - s.x ) / 2 : 0;
793 
794  VECTOR2I d_vert = VECTOR2I( 0, s.y / 2 + aWidth );
795  VECTOR2I d_horiz = VECTOR2I( s.x / 2 + aWidth, 0 );
796 
797  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_horiz } ) );
798  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_horiz } ) );
799  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c + d_vert } ) );
800  breakouts.emplace_back( SHAPE_LINE_CHAIN( { c, c - d_vert } ) );
801 
802  if( aPermitDiagonal )
803  {
804  int l = aWidth + std::min( s.x, s.y ) / 2;
805  VECTOR2I d_diag;
806 
807  if( s.x >= s.y )
808  {
809  breakouts.emplace_back(
810  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
811  breakouts.emplace_back(
812  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset - VECTOR2I( -l, l ) } ) );
813  breakouts.emplace_back(
814  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset + VECTOR2I( -l, l ) } ) );
815  breakouts.emplace_back(
816  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
817  }
818  else
819  {
820  // fixme: this could be done more efficiently
821  breakouts.emplace_back(
822  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( l, l ) } ) );
823  breakouts.emplace_back(
824  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( -l, l ) } ) );
825  breakouts.emplace_back(
826  SHAPE_LINE_CHAIN( { c, c + d_offset, c + d_offset + VECTOR2I( -l, l ) } ) );
827  breakouts.emplace_back(
828  SHAPE_LINE_CHAIN( { c, c - d_offset, c - d_offset - VECTOR2I( l, l ) } ) );
829  }
830  }
831 
832  return breakouts;
833 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
const VECTOR2I GetSize() const
Definition: shape_rect.h:124
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:116
SHAPE_LINE_CHAIN.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References SHAPE_RECT::GetPosition(), SHAPE_RECT::GetSize(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by computeBreakouts().

◆ removeCachedSegments()

void PNS::OPTIMIZER::removeCachedSegments ( LINE aLine,
int  aStartVertex = 0,
int  aEndVertex = -1 
)
private

Definition at line 173 of file pns_optimizer.cpp.

174 {
175  if( !aLine->IsLinked() )
176  return;
177 
178  auto links = aLine->Links();
179 
180  if( aEndVertex < 0 )
181  aEndVertex += aLine->PointCount();
182 
183  for( int i = aStartVertex; i < aEndVertex - 1; i++ )
184  {
185  LINKED_ITEM* s = links[i];
186  m_cacheTags.erase( s );
187  m_cache.Remove( s );
188  }
189 }
std::unordered_map< ITEM *, CACHED_ITEM > m_cacheTags
SHAPE_INDEX_LIST< ITEM * > m_cache

References PNS::LINK_HOLDER::IsLinked(), PNS::LINK_HOLDER::Links(), m_cache, m_cacheTags, and PNS::LINE::PointCount().

Referenced by CacheRemove().

◆ runSmartPads()

bool PNS::OPTIMIZER::runSmartPads ( LINE aLine)
private

Definition at line 1022 of file pns_optimizer.cpp.

1023 {
1024  SHAPE_LINE_CHAIN& line = aLine->Line();
1025 
1026  if( line.PointCount() < 3 )
1027  return false;
1028 
1029  VECTOR2I p_start = line.CPoint( 0 ), p_end = line.CPoint( -1 );
1030 
1031  ITEM* startPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_start );
1032  ITEM* endPad = findPadOrVia( aLine->Layer(), aLine->Net(), p_end );
1033 
1034  int vtx = -1;
1035 
1036  if( startPad )
1037  vtx = smartPadsSingle( aLine, startPad, false, 3 );
1038 
1039  if( endPad )
1040  smartPadsSingle( aLine, endPad, true,
1041  vtx < 0 ? line.PointCount() - 1 : line.PointCount() - 1 - vtx );
1042 
1043  aLine->Line().Simplify();
1044 
1045  return true;
1046 }
ITEM * findPadOrVia(int aLayer, int aNet, const VECTOR2I &aP) const
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
int smartPadsSingle(LINE *aLine, ITEM *aPad, bool aEnd, int aEndVertex)

References SHAPE_LINE_CHAIN::CPoint(), findPadOrVia(), PNS::ITEM::Layer(), PNS::LINE::Line(), PNS::ITEM::Net(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::Simplify(), and smartPadsSingle().

Referenced by Optimize().

◆ SetCollisionMask()

void PNS::OPTIMIZER::SetCollisionMask ( int  aMask)
inline

Definition at line 125 of file pns_optimizer.h.

126  {
127  m_collisionKindMask = aMask;
128  }

References m_collisionKindMask.

Referenced by Optimize(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::SHOVE::runOptimizer().

◆ SetEffortLevel()

void PNS::OPTIMIZER::SetEffortLevel ( int  aEffort)
inline

◆ SetPreserveVertex()

void PNS::OPTIMIZER::SetPreserveVertex ( const VECTOR2I aV)
inline

◆ SetRestrictArea()

void PNS::OPTIMIZER::SetRestrictArea ( const BOX2I aArea,
bool  aStrict = true 
)
inline

Definition at line 148 of file pns_optimizer.h.

149  {
150  m_restrictArea = aArea;
151  m_restrictAreaIsStrict = aStrict;
152  }
bool m_restrictAreaIsStrict

References m_restrictArea, and m_restrictAreaIsStrict.

Referenced by PNS::DRAGGER::optimizeAndUpdateDraggedLine(), and PNS::SHOVE::runOptimizer().

◆ SetRestrictVertexRange()

void PNS::OPTIMIZER::SetRestrictVertexRange ( int  aStart,
int  aEnd 
)
inline

Definition at line 141 of file pns_optimizer.h.

142  {
143  m_restrictedVertexRange.first = aStart;
144  m_restrictedVertexRange.second = aEnd;
146  }
std::pair< int, int > m_restrictedVertexRange

References m_effortLevel, m_restrictedVertexRange, and RESTRICT_VERTEX_RANGE.

◆ SetWorld()

void PNS::OPTIMIZER::SetWorld ( NODE aNode)
inline

Definition at line 121 of file pns_optimizer.h.

121 { m_world = aNode; }

References m_world.

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

◆ smartPadsSingle()

int PNS::OPTIMIZER::smartPadsSingle ( LINE aLine,
ITEM aPad,
bool  aEnd,
int  aEndVertex 
)
private

Definition at line 901 of file pns_optimizer.cpp.

902 {
903  DIRECTION_45 dir;
904 
905  const int ForbiddenAngles = DIRECTION_45::ANG_ACUTE | DIRECTION_45::ANG_RIGHT |
907 
908  typedef std::tuple<int, long long int, SHAPE_LINE_CHAIN> RtVariant;
909  std::vector<RtVariant> variants;
910 
911  SOLID* solid = dyn_cast<SOLID*>( aPad );
912 
913  // don't do optimized connections for offset pads
914  if( solid && solid->Offset() != VECTOR2I( 0, 0 ) )
915  return -1;
916 
917  // don't do optimization on vias, they are always round at the moment and the optimizer
918  // will possibly mess up an intended via exit posture
919  if( aPad->Kind() == ITEM::VIA_T )
920  return -1;
921 
922  BREAKOUT_LIST breakouts = computeBreakouts( aLine->Width(), aPad, true );
923  SHAPE_LINE_CHAIN line = ( aEnd ? aLine->CLine().Reverse() : aLine->CLine() );
924  int p_end = std::min( aEndVertex, std::min( 3, line.PointCount() - 1 ) );
925 
926  // Start at 1 to find a potentially better breakout (0 is the pad connection)
927  for( int p = 1; p <= p_end; p++ )
928  {
929  // If the line is contained inside the pad, don't optimize
930  if( solid && solid->Shape() && !solid->Shape()->Collide(
931  SEG( line.CPoint( 0 ), line.CPoint( p ) ), aLine->Width() / 2 ) )
932  {
933  continue;
934  }
935 
936  for( SHAPE_LINE_CHAIN & breakout : breakouts )
937  {
938  for( int diag = 0; diag < 2; diag++ )
939  {
941  SHAPE_LINE_CHAIN connect = dir.BuildInitialTrace(
942  breakout.CPoint( -1 ), line.CPoint( p ), diag == 0 );
943 
944  DIRECTION_45 dir_bkout( breakout.CSegment( -1 ) );
945 
946  if( !connect.SegmentCount() )
947  continue;
948 
949  int ang1 = dir_bkout.Angle( DIRECTION_45( connect.CSegment( 0 ) ) );
950 
951  if( ang1 & ForbiddenAngles )
952  continue;
953 
954  if( breakout.Length() > line.Length() )
955  continue;
956 
957  v = breakout;
958  v.Append( connect );
959 
960  for( int i = p + 1; i < line.PointCount(); i++ )
961  v.Append( line.CPoint( i ) );
962 
963  LINE tmp( *aLine, v );
964  int cc = tmp.CountCorners( ForbiddenAngles );
965 
966  if( cc == 0 )
967  {
968  RtVariant vp;
969  std::get<0>( vp ) = p;
970  std::get<1>( vp ) = breakout.Length();
971  std::get<2>( vp ) = aEnd ? v.Reverse() : v;
972  std::get<2>( vp ).Simplify();
973  variants.push_back( vp );
974  }
975  }
976  }
977  }
978 
979  // We attempt to minimize the corner cost (minimizes the segments and types of corners)
980  // but given two, equally valid costs, we want to pick the longer pad exit. The logic
981  // here is that if the pad is oblong, the track should not exit the shorter side and parallel
982  // the pad but should follow the pad's preferential direction before exiting.
983  // The baseline guess is to start with the existing line the user has drawn.
984  int min_cost = COST_ESTIMATOR::CornerCost( *aLine );
985  long long int max_length = 0;
986  bool found = false;
987  int p_best = -1;
988  SHAPE_LINE_CHAIN l_best;
989 
990  for( RtVariant& vp : variants )
991  {
992  LINE tmp( *aLine, std::get<2>( vp ) );
993  int cost = COST_ESTIMATOR::CornerCost( std::get<2>( vp ) );
994  long long int len = std::get<1>( vp );
995 
996  if( !checkColliding( &tmp ) )
997  {
998  if( cost < min_cost || ( cost == min_cost && len > max_length ) )
999  {
1000  l_best = std::get<2>( vp );
1001  p_best = std::get<0>( vp );
1002  found = true;
1003 
1004  if( cost <= min_cost )
1005  max_length = std::max<int>( len, max_length );
1006 
1007  min_cost = std::min( cost, min_cost );
1008  }
1009  }
1010  }
1011 
1012  if( found )
1013  {
1014  aLine->SetShape( l_best );
1015  return p_best;
1016  }
1017 
1018  return -1;
1019 }
BREAKOUT_LIST computeBreakouts(int aWidth, const ITEM *aItem, bool aPermitDiagonal) const
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:169
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:36
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, bool aFillet=false) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:41
const SEG CSegment(int aIndex) const
Function CSegment()
SHAPE_LINE_CHAIN.
bool checkColliding(ITEM *aItem, bool aUpdateCache=true)
static int CornerCost(const SEG &aA, const SEG &aB)
Cost Estimator Methods.
std::vector< SHAPE_LINE_CHAIN > BREAKOUT_LIST

References DIRECTION_45::ANG_ACUTE, DIRECTION_45::ANG_HALF_FULL, DIRECTION_45::ANG_RIGHT, DIRECTION_45::ANG_UNDEFINED, DIRECTION_45::Angle(), SHAPE_LINE_CHAIN::Append(), DIRECTION_45::BuildInitialTrace(), checkColliding(), PNS::LINE::CLine(), SHAPE::Collide(), computeBreakouts(), PNS::COST_ESTIMATOR::CornerCost(), PNS::LINE::CountCorners(), SHAPE_LINE_CHAIN::CSegment(), PNS::ITEM::Kind(), PNS::SOLID::Offset(), SHAPE_LINE_CHAIN::Reverse(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), PNS::SOLID::Shape(), SHAPE_LINE_CHAIN::Simplify(), PNS::ITEM::VIA_T, and PNS::LINE::Width().

Referenced by runSmartPads().

Member Data Documentation

◆ m_cache

SHAPE_INDEX_LIST<ITEM*> PNS::OPTIMIZER::m_cache
private

Definition at line 199 of file pns_optimizer.h.

Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().

◆ m_cacheTags

std::unordered_map<ITEM*, CACHED_ITEM> PNS::OPTIMIZER::m_cacheTags
private

Definition at line 201 of file pns_optimizer.h.

Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().

◆ m_collisionKindMask

int PNS::OPTIMIZER::m_collisionKindMask
private

Definition at line 204 of file pns_optimizer.h.

Referenced by checkColliding(), and SetCollisionMask().

◆ m_constraints

std::vector<OPT_CONSTRAINT*> PNS::OPTIMIZER::m_constraints
private

Definition at line 200 of file pns_optimizer.h.

Referenced by AddConstraint(), checkConstraints(), and ClearConstraints().

◆ m_effortLevel

int PNS::OPTIMIZER::m_effortLevel
private

◆ m_preservedVertex

VECTOR2I PNS::OPTIMIZER::m_preservedVertex
private

Definition at line 207 of file pns_optimizer.h.

Referenced by Optimize(), and SetPreserveVertex().

◆ m_restrictArea

BOX2I PNS::OPTIMIZER::m_restrictArea
private

Definition at line 209 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictArea().

◆ m_restrictAreaIsStrict

bool PNS::OPTIMIZER::m_restrictAreaIsStrict
private

Definition at line 210 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictArea().

◆ m_restrictedVertexRange

std::pair<int, int> PNS::OPTIMIZER::m_restrictedVertexRange
private

Definition at line 208 of file pns_optimizer.h.

Referenced by Optimize(), and SetRestrictVertexRange().

◆ m_world

NODE* PNS::OPTIMIZER::m_world
private

◆ MaxCachedItems

const int PNS::OPTIMIZER::MaxCachedItems = 256
staticprivate

Definition at line 158 of file pns_optimizer.h.


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