pns_node.h

Go to the documentation of this file.

/*
 * KiRouter - a push-and-(sometimes-)shove PCB router
 *
 * Copyright (C) 2013-2014 CERN
 * Copyright The 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 <https://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,
    CT_PHYSICAL_HOLE_CLEARANCE = 13
};

 
struct CONSTRAINT
{
    CONSTRAINT_TYPE m_Type;
    MINOPTMAX<int>  m_Value;
    bool            m_Allowed;
    wxString        m_RuleName;
    wxString        m_FromName;
    wxString        m_ToName;
    bool            m_IsTimeDomain;
};
 

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;
    }
};
 
typedef std::function<bool(const ITEM* aTestItem, const ITEM* aRefItem)> COLLISION_FILTER_FUNC;
 
struct COLLISION_SEARCH_OPTIONS
{
    bool m_differentNetsOnly = true;
    int m_overrideClearance = -1;
    int m_limitCount = -1;
    int m_kindMask = -1;
    bool m_useClearanceEpsilon = true;
    COLLISION_FILTER_FUNC m_filter = nullptr;
    int m_layer = -1;
};
 
 
struct COLLISION_SEARCH_CONTEXT
{
    COLLISION_SEARCH_CONTEXT( std::set<OBSTACLE>& aObs,
                              const COLLISION_SEARCH_OPTIONS aOpts = COLLISION_SEARCH_OPTIONS() ) :
        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 bool HasUserDefinedPhysicalConstraint() { return false; }
 
    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; }
 
    virtual const SHAPE_LINE_CHAIN& HullCache( const ITEM* aItem, int aClearance,
                                               int aWalkaroundThickness, int aLayer )
    {
        static SHAPE_LINE_CHAIN empty;
        empty = aItem->Hull( aClearance, aWalkaroundThickness, aLayer );
        return empty;
    }
};
 
 
class OBSTACLE_VISITOR
{
public:
    OBSTACLE_VISITOR( const ITEM* aItem );
 
    virtual ~OBSTACLE_VISITOR()
    {
    }
 
    void SetWorld( const NODE* aNode, const NODE* aOverride = nullptr );
 
    void SetLayerContext( int aLayer ) { m_layerContext = aLayer; }
    void ClearLayerContext() { m_layerContext = std::nullopt; }
 
    virtual bool operator()( ITEM* aCandidate ) = 0;
 
protected:
    bool visit( ITEM* aCandidate );
 
protected:
    const ITEM* m_item;             
 
    const NODE* m_node;             
    const NODE* m_override;         
    std::optional<int> m_layerContext;
};
 
 
class LAYER_CONTEXT_SETTER
{
public:
    LAYER_CONTEXT_SETTER( OBSTACLE_VISITOR& aVisitor, int aLayer ) :
            m_visitor( aVisitor )
    {
        m_visitor.SetLayerContext( aLayer );
    }
 
    ~LAYER_CONTEXT_SETTER()
    {
        m_visitor.ClearLayerContext();
    }
 
private:
    OBSTACLE_VISITOR& m_visitor;
};

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 BeginBulkAdd();

    void FinalizeBulkAdd();

    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,
                     PNS_LAYER_RANGE aLayerMask = PNS_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, bool aAllowRedundantSegments = false );

    NODE* Branch();

    const LINE AssembleLine( LINKED_ITEM* aSeg, int* aOriginSegmentIndex = nullptr,
                             bool aStopAtLockedJoints = false,
                             bool aFollowLockedSegments = false,
                             bool aAllowSegmentSizeMismatch = true );

    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*> FindItemsByParent( const BOARD_ITEM* 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 );
    }
 
    const std::unordered_set<ITEM*>& GetOverrides() const
    {
        return m_override;
    }
 
    VIA* FindViaByHandle ( const VIA_HANDLE& handle ) const;
 
private:
    void add( ITEM* aItem, bool aAllowRedundant = false );

    NODE( const NODE& aB );
    NODE& operator=( const NODE& aB );

    JOINT& touchJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet );

    void linkJoint( const VECTOR2I& aPos, const PNS_LAYER_RANGE& aLayers, NET_HANDLE aNet,
                    ITEM* aWhere );

    void unlinkJoint( const VECTOR2I& aPos, const PNS_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 PNS_LAYER_RANGE& lr,
                                   NET_HANDLE aNet );
    SEGMENT* findRedundantSegment( SEGMENT* aSeg );
 
    ARC* findRedundantArc( const VECTOR2I& A, const VECTOR2I& B, const PNS_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,
                     bool aAllowSegmentSizeMismatch );
 
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