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 , LIMIT_CORNER_COUNT = 0x200 }

Public Member Functions
	OPTIMIZER (NODE *aWorld)

	~OPTIMIZER ()
	A quick shortcut to optimize a line without creating and setting up an optimizer. More...

bool	Optimize (LINE aLine, LINE aResult=nullptr, LINE *aRoot=nullptr)

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, NET_HANDLE 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

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 162 of file pns_optimizer.h.

Member Enumeration Documentation

◆ OptimizationEffort

enum PNS::OPTIMIZER::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
LIMIT_CORNER_COUNT	Do not attempt to optimize if the resulting line's corner count is outside the predefined range.

Definition at line 97 of file pns_optimizer.h.

Constructor & Destructor Documentation

◆ OPTIMIZER()

PNS::OPTIMIZER::OPTIMIZER ( NODE * aWorld )

Definition at line 112 of file pns_optimizer.cpp.

◆ ~OPTIMIZER()

PNS::OPTIMIZER::~OPTIMIZER ( )

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

Definition at line 121 of file pns_optimizer.cpp.

Member Function Documentation

◆ AddConstraint()

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

Definition at line 429 of file pns_optimizer.cpp.

References m_constraints.

Referenced by Optimize().

◆ cacheAdd()

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

private

Definition at line 154 of file pns_optimizer.cpp.

References m_cache, and m_cacheTags.

◆ CacheRemove()

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

Definition at line 184 of file pns_optimizer.cpp.

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 412 of file pns_optimizer.cpp.

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 449 of file pns_optimizer.cpp.

References checkColliding().

◆ checkConstraints()

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