![]() |
KiCad PCB EDA Suite
|
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_CHAIN > | BREAKOUT_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) |
ITEM * | findPadOrVia (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_ITEM > | m_cacheTags |
NODE * | m_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 |
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:
Definition at line 94 of file pns_optimizer.h.
|
private |
Definition at line 160 of file pns_optimizer.h.
Definition at line 97 of file pns_optimizer.h.
PNS::OPTIMIZER::OPTIMIZER | ( | NODE * | aWorld | ) |
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.
void PNS::OPTIMIZER::AddConstraint | ( | OPT_CONSTRAINT * | aConstraint | ) |
Definition at line 414 of file pns_optimizer.cpp.
References m_constraints.
Referenced by Optimize().
|
private |
Definition at line 162 of file pns_optimizer.cpp.
References m_cache, and m_cacheTags.
void PNS::OPTIMIZER::CacheRemove | ( | ITEM * | aItem | ) |
Definition at line 192 of file pns_optimizer.cpp.
References PNS::ITEM::Kind(), PNS::ITEM::LINE_T, and removeCachedSegments().
|
private |
Definition at line 397 of file pns_optimizer.cpp.
References PNS::NODE::CheckColliding(), m_collisionKindMask, and m_world.
Referenced by checkColliding(), mergeObtuse(), mergeStep(), and smartPadsSingle().
|
private |
Definition at line 434 of file pns_optimizer.cpp.
References checkColliding().
|
private |
Definition at line 420 of file pns_optimizer.cpp.
References m_constraints.
Referenced by mergeStep().
|
private |
Definition at line 718 of file pns_optimizer.cpp.
References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_CIRCLE::GetCenter(), SHAPE_CIRCLE::GetRadius(), and VECTOR2< T >::Rotate().
Referenced by computeBreakouts().
void PNS::OPTIMIZER::ClearCache | ( | bool | aStaticOnly = false | ) |
Definition at line 199 of file pns_optimizer.cpp.
References m_cache, and m_cacheTags.
void PNS::OPTIMIZER::ClearConstraints | ( | ) |
Definition at line 405 of file pns_optimizer.cpp.
References m_constraints.
|
private |
Definition at line 836 of file pns_optimizer.cpp.
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().
|
private |
Definition at line 739 of file pns_optimizer.cpp.
References PNS::angle(), SHAPE_LINE_CHAIN::Append(), SHAPE_SIMPLE::BBox(), SHAPE_LINE_CHAIN::Intersect(), PNS::ITEM::Shape(), and SHAPE_SIMPLE::Vertices().
Referenced by computeBreakouts().
|
private |
Definition at line 1065 of file pns_optimizer.cpp.
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().
Definition at line 884 of file pns_optimizer.cpp.
References PNS::NODE::FindJoint(), PNS::JOINT::LinkList(), m_world, NULL, PNS::ITEM::SOLID_T, and PNS::ITEM::VIA_T.
Referenced by fanoutCleanup(), and runSmartPads().
|
private |
Definition at line 562 of file pns_optimizer.cpp.
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().
|
private |
Definition at line 1286 of file pns_optimizer.cpp.
References PNS::DIFF_PAIR::CN(), PNS::DIFF_PAIR::CP(), mergeDpStep(), and SHAPE_LINE_CHAIN::SegmentCount().
Referenced by Optimize().
|
private |
Definition at line 1223 of file pns_optimizer.cpp.
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().
|
private |
Definition at line 522 of file pns_optimizer.cpp.
References PNS::LINE::Line(), mergeStep(), SHAPE_LINE_CHAIN::SegmentCount(), PNS::LINE::SetShape(), and SHAPE_LINE_CHAIN::Simplify().
Referenced by Optimize().
|
private |
Definition at line 442 of file pns_optimizer.cpp.
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().
|
private |
Definition at line 653 of file pns_optimizer.cpp.
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().
|
static |
Definition at line 1049 of file pns_optimizer.cpp.
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().
Definition at line 590 of file pns_optimizer.cpp.
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.
bool PNS::OPTIMIZER::Optimize | ( | DIFF_PAIR * | aPair | ) |
Definition at line 1327 of file pns_optimizer.cpp.
References mergeDpSegments().
|
private |
Definition at line 781 of file pns_optimizer.cpp.
References SHAPE_RECT::GetPosition(), SHAPE_RECT::GetSize(), VECTOR2< T >::x, and VECTOR2< T >::y.
Referenced by computeBreakouts().
|
private |
Definition at line 173 of file pns_optimizer.cpp.
References PNS::LINK_HOLDER::IsLinked(), PNS::LINK_HOLDER::Links(), m_cache, m_cacheTags, and PNS::LINE::PointCount().
Referenced by CacheRemove().
|
private |
Definition at line 1022 of file pns_optimizer.cpp.
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().
|
inline |
Definition at line 125 of file pns_optimizer.h.
References m_collisionKindMask.
Referenced by Optimize(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::SHOVE::runOptimizer().
|
inline |
Definition at line 130 of file pns_optimizer.h.
References m_effortLevel.
Referenced by Optimize(), PNS::DRAGGER::optimizeAndUpdateDraggedLine(), PNS::LINE_PLACER::rhShoveOnly(), and PNS::SHOVE::runOptimizer().
|
inline |
Definition at line 135 of file pns_optimizer.h.
References m_effortLevel, m_preservedVertex, and PRESERVE_VERTEX.
Referenced by Optimize(), and PNS::DRAGGER::optimizeAndUpdateDraggedLine().
|
inline |
Definition at line 148 of file pns_optimizer.h.
References m_restrictArea, and m_restrictAreaIsStrict.
Referenced by PNS::DRAGGER::optimizeAndUpdateDraggedLine(), and PNS::SHOVE::runOptimizer().
|
inline |
Definition at line 141 of file pns_optimizer.h.
References m_effortLevel, m_restrictedVertexRange, and RESTRICT_VERTEX_RANGE.
|
inline |
Definition at line 121 of file pns_optimizer.h.
References m_world.
Referenced by PNS::LINE_PLACER::rhShoveOnly().
|
private |
Definition at line 901 of file pns_optimizer.cpp.
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().
|
private |
Definition at line 199 of file pns_optimizer.h.
Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().
|
private |
Definition at line 201 of file pns_optimizer.h.
Referenced by cacheAdd(), ClearCache(), and removeCachedSegments().
|
private |
Definition at line 204 of file pns_optimizer.h.
Referenced by checkColliding(), and SetCollisionMask().
|
private |
Definition at line 200 of file pns_optimizer.h.
Referenced by AddConstraint(), checkConstraints(), and ClearConstraints().
|
private |
Definition at line 205 of file pns_optimizer.h.
Referenced by Optimize(), SetEffortLevel(), SetPreserveVertex(), and SetRestrictVertexRange().
|
private |
Definition at line 207 of file pns_optimizer.h.
Referenced by Optimize(), and SetPreserveVertex().
|
private |
Definition at line 209 of file pns_optimizer.h.
Referenced by Optimize(), and SetRestrictArea().
|
private |
Definition at line 210 of file pns_optimizer.h.
Referenced by Optimize(), and SetRestrictArea().
|
private |
Definition at line 208 of file pns_optimizer.h.
Referenced by Optimize(), and SetRestrictVertexRange().
|
private |
Definition at line 203 of file pns_optimizer.h.
Referenced by checkColliding(), fanoutCleanup(), findPadOrVia(), mergeDpStep(), Optimize(), and SetWorld().
|
staticprivate |
Definition at line 158 of file pns_optimizer.h.