pns_node.h

Go to the documentation of this file.

/*
 * KiRouter - a push-and-(sometimes-)shove PCB router
 *
 * Copyright (C) 2013-2014 CERN
 * Copyright (C) 2016-2023 KiCad Developers, see AUTHORS.txt for contributors.
 *
 * @author Tomasz Wlostowski <[email protected]>
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef __PNS_NODE_H
#define __PNS_NODE_H
 
#include <vector>
#include <list>
#include <set>
#include <core/minoptmax.h>
 
#include <geometry/shape_line_chain.h>
#include <geometry/shape_index.h>
 
#include "pns_item.h"
#include "pns_joint.h"
#include "pns_itemset.h"
 
class ZONE;
namespace PNS {
 
class ARC;
class SEGMENT;
class LINE;
class SOLID;
class VIA;
class INDEX;
class ROUTER;
class NODE;
 
 
enum class CONSTRAINT_TYPE
{
 CT_CLEARANCE = 1,
 CT_DIFF_PAIR_GAP = 2,
 CT_LENGTH = 3,
 CT_WIDTH = 4,
 CT_VIA_DIAMETER = 5,
 CT_VIA_HOLE = 6,
 CT_HOLE_CLEARANCE = 7,
 CT_EDGE_CLEARANCE = 8,
 CT_HOLE_TO_HOLE = 9,
 CT_DIFF_PAIR_SKEW = 10,
 CT_MAX_UNCOUPLED = 11,
 CT_PHYSICAL_CLEARANCE = 12
};
 
struct CONSTRAINT
{
 CONSTRAINT_TYPE m_Type;
 MINOPTMAX<int> m_Value;
 bool m_Allowed;
 wxString m_RuleName;
 wxString m_FromName;
 wxString m_ToName;
};
 
 
struct OBSTACLE
{
 ITEM* m_head = nullptr; 
 ITEM* m_item = nullptr; 
 VECTOR2I m_ipFirst; 
 int m_clearance;
 VECTOR2I m_pos;
 int m_distFirst; 
 int m_maxFanoutWidth; 
 
 bool operator==(const OBSTACLE& other) const
 {
 return m_head == other.m_head && m_item == other.m_item;
 }
 
 bool operator<(const OBSTACLE& other) const
 {
 if( (uintptr_t)m_head < (uintptr_t)other.m_head )
 return true;
 else if ( m_head == other.m_head )
 return (uintptr_t)m_item < (uintptr_t)other.m_item;
 return false;
 }
};
 
 
struct COLLISION_SEARCH_OPTIONS
{
 bool m_differentNetsOnly = true;
 int m_overrideClearance = -1;
 int m_limitCount = -1;
 int m_kindMask = -1;
 bool m_useClearanceEpsilon = true;
 std::set<ITEM*>* m_restrictedSet = nullptr;
};
 
 
struct COLLISION_SEARCH_CONTEXT
{
 COLLISION_SEARCH_CONTEXT( std::set<OBSTACLE>& aObs, const COLLISION_SEARCH_OPTIONS aOpts ) :
 obstacles( aObs ),
 options( aOpts )
 {
 }
 
 std::set<OBSTACLE>& obstacles;
 const COLLISION_SEARCH_OPTIONS options;
};
 
 
class RULE_RESOLVER
{
public:
 virtual ~RULE_RESOLVER() {}
 
 virtual int Clearance( const ITEM* aA, const ITEM* aB, bool aUseClearanceEpsilon = true ) = 0;
 
 virtual NET_HANDLE DpCoupledNet( NET_HANDLE aNet ) = 0;
 virtual int DpNetPolarity( NET_HANDLE aNet ) = 0;
 virtual bool DpNetPair( const ITEM* aItem, NET_HANDLE& aNetP, NET_HANDLE& aNetN ) = 0;
 
 virtual int NetCode( NET_HANDLE aNet ) = 0;
 virtual wxString NetName( NET_HANDLE aNet ) = 0;
 
 virtual bool IsInNetTie( const ITEM* aA ) = 0;
 virtual bool IsNetTieExclusion( const ITEM* aItem, const VECTOR2I& aCollisionPos,
 const ITEM* aCollidingItem ) = 0;
 
 virtual bool IsDrilledHole( const PNS::ITEM* aItem ) = 0;
 virtual bool IsNonPlatedSlot( const PNS::ITEM* aItem ) = 0;
 
 virtual bool IsKeepout( const ITEM* aObstacle, const ITEM* aItem, bool* aEnforce ) = 0;
 
 virtual bool QueryConstraint( CONSTRAINT_TYPE aType, const ITEM* aItemA, const ITEM* aItemB,
 int aLayer, CONSTRAINT* aConstraint ) = 0;
 
 virtual void ClearCacheForItems( std::vector<const ITEM*>& aItems ) {}
 virtual void ClearCaches() {}
 virtual void ClearTemporaryCaches() {}
 
 virtual int ClearanceEpsilon() const { return 0; }
};
 
 
class OBSTACLE_VISITOR
{
public:
 OBSTACLE_VISITOR( const ITEM* aItem );
 
 virtual ~OBSTACLE_VISITOR()
 {
 }
 
 void SetWorld( const NODE* aNode, const NODE* aOverride = nullptr );
 
 virtual bool operator()( ITEM* aCandidate ) = 0;
 
protected:
 bool visit( ITEM* aCandidate );
 
protected:
 const ITEM* m_item; 
 
 const NODE* m_node; 
 const NODE* m_override; 
};
 
class NODE : public ITEM_OWNER
{
public:
 
 enum COLLISION_QUERY_SCOPE
 {
 CQS_ALL_RULES = 1, 
 CQS_IGNORE_HOLE_CLEARANCE = 2 
 };
 
 typedef std::optional<OBSTACLE> OPT_OBSTACLE;
 typedef std::vector<ITEM*> ITEM_VECTOR;
 typedef std::set<OBSTACLE> OBSTACLES;
 
 NODE();
 ~NODE();
 
 int GetClearance( const ITEM* aA, const ITEM* aB, bool aUseClearanceEpsilon = true ) const;
 
 int GetMaxClearance() const
 {
 return m_maxClearance;
 }
 
 void SetMaxClearance( int aClearance )
 {
 m_maxClearance = aClearance;
 }
 
 void SetRuleResolver( RULE_RESOLVER* aFunc )
 {
 m_ruleResolver = aFunc;
 }
 
 RULE_RESOLVER* GetRuleResolver() const
 {
 return m_ruleResolver;
 }
 
 int JointCount() const
 {
 return m_joints.size();
 }
 
 int Depth() const
 {
 return m_depth;
 }
 
 int QueryColliding( const ITEM* aItem, OBSTACLES& aObstacles,
 const COLLISION_SEARCH_OPTIONS& aOpts = COLLISION_SEARCH_OPTIONS() ) const;
 
 int QueryJoints( const BOX2I& aBox, std::vector<JOINT*>& aJoints,
 LAYER_RANGE aLayerMask = LAYER_RANGE::All(), int aKindMask = ITEM::ANY_T );
 
 OPT_OBSTACLE NearestObstacle( const LINE* aLine,
 const COLLISION_SEARCH_OPTIONS& aOpts = COLLISION_SEARCH_OPTIONS() );
 
 OPT_OBSTACLE CheckColliding( const ITEM* aItem, int aKindMask = ITEM::ANY_T );
 
 
 OPT_OBSTACLE CheckColliding( const ITEM_SET& aSet, int aKindMask = ITEM::ANY_T );
 
 OPT_OBSTACLE CheckColliding( const ITEM* aItem, const COLLISION_SEARCH_OPTIONS& aOpts );
 
 const ITEM_SET HitTest( const VECTOR2I& aPoint ) const;
 
 bool Add( std::unique_ptr<SEGMENT> aSegment, bool aAllowRedundant = false );
 void Add( std::unique_ptr<SOLID> aSolid );
 void Add( std::unique_ptr<VIA> aVia );
 bool Add( std::unique_ptr<ARC> aArc, bool aAllowRedundant = false );
 
 void Add( LINE& aLine, bool aAllowRedundant = false );
 
 void AddEdgeExclusion( std::unique_ptr<SHAPE> aShape );
 bool QueryEdgeExclusions( const VECTOR2I& aPos ) const;
 
 void Remove( ARC* aArc );
 void Remove( SOLID* aSolid );
 void Remove( VIA* aVia );
 void Remove( SEGMENT* aSegment );
 void Remove( ITEM* aItem );
 
 void Remove( LINE& aLine );
 
 void Replace( ITEM* aOldItem, std::unique_ptr< ITEM > aNewItem );
 void Replace( LINE& aOldLine, LINE& aNewLine );
 
 NODE* Branch();
 
 const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = nullptr,
 bool aStopAtLockedJoints = false,
 bool aFollowLockedSegments = false );
 
 void Dump( bool aLong = false );
 
 void GetUpdatedItems( ITEM_VECTOR& aRemoved, ITEM_VECTOR& aAdded );
 
 void Commit( NODE* aNode );
 
 const JOINT* FindJoint( const VECTOR2I& aPos, int aLayer, NET_HANDLE aNet ) const;
 
 void LockJoint( const VECTOR2I& aPos, const ITEM* aItem, bool aLock );
 
 const JOINT* FindJoint( const VECTOR2I& aPos, const ITEM* aItem ) const
 {
 return FindJoint( aPos, aItem->Layers().Start(), aItem->Net() );
 }
 
 int FindLinesBetweenJoints( const JOINT& aA, const JOINT& aB, std::vector<LINE>& aLines );
 
 void FindLineEnds( const LINE& aLine, JOINT& aA, JOINT& aB );
 
 void KillChildren();
 
 void AllItemsInNet( NET_HANDLE aNet, std::set<ITEM*>& aItems, int aKindMask = -1 );
 
 void ClearRanks( int aMarkerMask = MK_HEAD | MK_VIOLATION );
 
 void RemoveByMarker( int aMarker );
 
 ITEM* FindItemByParent( const BOARD_ITEM* aParent );
 
 std::vector<ITEM*> FindItemsByZone( const ZONE* aParent );
 
 bool HasChildren() const
 {
 return !m_children.empty();
 }
 
 NODE* GetParent() const
 {
 return m_parent;
 }
 
 bool Overrides( ITEM* aItem ) const
 {
 return m_override.find( aItem ) != m_override.end();
 }
 
 void FixupVirtualVias();
 
 void AddRaw( ITEM* aItem, bool aAllowRedundant = false )
 {
 add( aItem, aAllowRedundant );
 }
 
private:
 void add( ITEM* aItem, bool aAllowRedundant = false );
 
 NODE( const NODE& aB );
 NODE& operator=( const NODE& aB );
 
 JOINT& touchJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet );
 
 void linkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
 ITEM* aWhere );
 
 void unlinkJoint( const VECTOR2I& aPos, const LAYER_RANGE& aLayers, NET_HANDLE aNet,
 ITEM* aWhere );
 
 void addSolid( SOLID* aSeg );
 void addSegment( SEGMENT* aSeg );
 void addVia( VIA* aVia );
 void addArc( ARC* aVia );
 void addHole( HOLE* aHole );
 
 void removeSolidIndex( SOLID* aSeg );
 void removeSegmentIndex( SEGMENT* aSeg );
 void removeViaIndex( VIA* aVia );
 void removeArcIndex( ARC* aVia );
 
 void doRemove( ITEM* aItem );
 void unlinkParent();
 void releaseChildren();
 void releaseGarbage();
 void rebuildJoint( const JOINT* aJoint, const ITEM* aItem );
 
 bool isRoot() const
 {
 return m_parent == nullptr;
 }
 
 SEGMENT* findRedundantSegment( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
 NET_HANDLE aNet );
 SEGMENT* findRedundantSegment( SEGMENT* aSeg );
 
 ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const LAYER_RANGE& lr,
 NET_HANDLE aNet );
 ARC* findRedundantArc( ARC* aSeg );
 
 void followLine( LINKED_ITEM* aCurrent, bool aScanDirection, int& aPos, int aLimit,
 VECTOR2I* aCorners, LINKED_ITEM** aSegments, bool* aArcReversed,
 bool& aGuardHit, bool aStopAtLockedJoints, bool aFollowLockedSegments );
 
private:
 struct DEFAULT_OBSTACLE_VISITOR;
 typedef std::unordered_multimap<JOINT::HASH_TAG, JOINT, JOINT::JOINT_TAG_HASH> JOINT_MAP;
 typedef JOINT_MAP::value_type TagJointPair;
 
 JOINT_MAP m_joints; 
 
 NODE* m_parent; 
 NODE* m_root; 
 std::set<NODE*> m_children; 
 
 std::unordered_set<ITEM*> m_override; 
 
 int m_maxClearance; 
 RULE_RESOLVER* m_ruleResolver; 
 INDEX* m_index; 
 int m_depth; 
 
 std::vector< std::unique_ptr<SHAPE> > m_edgeExclusions;
 
 std::unordered_set<ITEM*> m_garbageItems;
};
 
}
 
#endif