connectivity_items.h

Go to the documentation of this file.

/*
 * This program source code file is part of KICAD, a free EDA CAD application.
 *
 * Copyright (C) 2013-2017 CERN
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * @author Maciej Suminski <[email protected]>
 * @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 2
 * 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 PCBNEW_CONNECTIVITY_ITEMS_H
#define PCBNEW_CONNECTIVITY_ITEMS_H
 
#include <geometry/rtree/packed_rtree.h>
#include <geometry/shape_poly_set.h>
 
#include <algorithm>
#include <atomic>
#include <deque>
#include <functional>
#include <memory>
#include <vector>
 
#include <connectivity/connectivity_rtree.h>
#include <connectivity/connectivity_data.h>
 
class CN_ITEM;
class CN_CLUSTER;
class PCB_SHAPE;
 

class CN_ANCHOR
{
public:
    CN_ANCHOR( const VECTOR2I& aPos, CN_ITEM* aItem ) :
            m_pos( aPos ),
            m_item( aItem ),
            m_tag( -1 ),
            m_noline( false )
    { }
 
    bool Valid() const;
 
    bool Dirty() const;
 
    CN_ITEM* Item() const { return m_item; }
    void SetItem( CN_ITEM* aItem ) { m_item = aItem; }
 
    BOARD_CONNECTED_ITEM* Parent() const;
 
    const VECTOR2I& Pos() const { return m_pos; }
 
    void Move( const VECTOR2I& aPos )
    {
        m_pos += aPos;
    }
 
     unsigned int Dist( const CN_ANCHOR& aSecond )
    {
        return ( m_pos - aSecond.Pos() ).EuclideanNorm();
    }

    int GetTag() const { return m_tag; }
    void SetTag( int aTag ) { m_tag = aTag; }

    const bool& GetNoLine() const { return m_noline; }
    void SetNoLine( bool aEnable ) { m_noline = aEnable; }
 
    const std::shared_ptr<CN_CLUSTER>& GetCluster() const { return m_cluster; }
    void SetCluster( std::shared_ptr<CN_CLUSTER>& aCluster ) { m_cluster = aCluster; }

    bool IsDangling() const;

    int ConnectedItemsCount() const;
 
    // Tag used for unconnected items.
    static const int TAG_UNCONNECTED = -1;
 
private:
    VECTOR2I    m_pos;             
    CN_ITEM*    m_item;            
    int         m_tag;             
    bool        m_noline;          
 
    std::shared_ptr<CN_CLUSTER> m_cluster;     
};
 
 

class CN_ITEM
{
public:
    void Dump();
 
    CN_ITEM( BOARD_CONNECTED_ITEM* aParent, bool aCanChangeNet, int aAnchorCount = 2 )
    {
        m_parent = aParent;
        m_canChangeNet = aCanChangeNet;
        m_valid = true;
        m_dirty = true;
        m_anchors.reserve( std::max( 6, aAnchorCount ) );
        m_start_layer = 0;
        m_end_layer = std::numeric_limits<int>::max();
        m_connected.reserve( 8 );
    }
 
    virtual ~CN_ITEM()
    {
        for( const std::shared_ptr<CN_ANCHOR>& anchor : m_anchors )
            anchor->SetItem( nullptr );
    };
 
    std::shared_ptr<CN_ANCHOR> AddAnchor( const VECTOR2I& aPos )
    {
        m_anchors.emplace_back( std::make_shared<CN_ANCHOR>( aPos, this ) );
        return m_anchors.at( m_anchors.size() - 1 );
    }
 
    std::vector<std::shared_ptr<CN_ANCHOR>>& Anchors() { return m_anchors; }
 
    void SetValid( bool aValid ) { m_valid = aValid; }
    bool Valid() const { return m_valid; }
 
    void SetDirty( bool aDirty ) { m_dirty.store( aDirty, std::memory_order_release ); }
    bool Dirty() const { return m_dirty.load( std::memory_order_acquire ); }

    void SetLayers( int aStartLayer, int aEndLayer )
    {
        // Copper layer ids do not run in stack order, so store the ordinal.  The R-tree keys
        // on this, and an ordinal keeps a through item's span 31 wide rather than INT_MAX
        // wide.  A span that large overflows the int64 volume the tree splits on, which
        // wrecks the split and leaves queries walking most of the tree.
        m_start_layer = static_cast<int>( CopperLayerToOrdinal( ToLAYER_ID( aStartLayer ) ) );
        m_end_layer = static_cast<int>( CopperLayerToOrdinal( ToLAYER_ID( aEndLayer ) ) );
    }

    void SetLayer( int aLayer ) { SetLayers( aLayer, aLayer ); }

    int StartLayer() const { return m_start_layer; }
    int EndLayer() const { return m_end_layer; }

    virtual int Layer() const
    {
        return StartLayer();
    }

    static PCB_LAYER_ID BoardLayerFromOrdinal( int aOrdinal )
    {
        if( aOrdinal <= 0 )
            return F_Cu;
 
        if( aOrdinal >= MAX_CU_LAYERS - 1 )
            return B_Cu;
 
        return ToLAYER_ID( B_Cu + 2 * aOrdinal );
    }

    PCB_LAYER_ID GetBoardLayer() const { return BoardLayerFromOrdinal( Layer() ); }
 
    const BOX2I& BBox()
    {
        if( m_dirty.load( std::memory_order_acquire ) && m_valid )
        {
            std::lock_guard<std::mutex> lock( m_listLock );
 
            if( m_dirty.load( std::memory_order_relaxed ) && m_valid )
            {
                m_bbox = m_parent->GetBoundingBox();
                m_dirty.store( false, std::memory_order_release );
            }
        }
 
        return m_bbox;
    }
 
    BOARD_CONNECTED_ITEM* Parent() const { return m_parent; }
 
    const std::vector<CN_ITEM*>& ConnectedItems() const { return m_connected; }
    void ClearConnections() { m_connected.clear(); }
 
    bool CanChangeNet() const { return m_canChangeNet; }
 
    void Connect( CN_ITEM* b )
    {
        std::lock_guard<std::mutex> lock( m_listLock );
 
        auto i = std::lower_bound( m_connected.begin(), m_connected.end(), b );
 
        if( i != m_connected.end() && *i == b )
          return;
 
        m_connected.insert( i, b );
    }
 
    void RemoveInvalidRefs();
 
    virtual int AnchorCount() const;
    virtual const VECTOR2I GetAnchor( int n ) const;
 
    int Net() const
    {
        return ( !m_parent || !m_valid ) ? -1 : m_parent->GetNetCode();
    }

    void SetListIndex( int aIndex ) { m_listIndex = aIndex; }
    int  ListIndex() const { return m_listIndex; }
 
protected:
    std::atomic<bool> m_dirty;       
    int             m_start_layer;   
    int             m_end_layer;     
    BOX2I           m_bbox;          
 
private:
    BOARD_CONNECTED_ITEM*                    m_parent;
 
    std::vector<CN_ITEM*>                    m_connected;   
    std::vector<std::shared_ptr<CN_ANCHOR>>  m_anchors;
 
    bool            m_canChangeNet;  
 
    bool            m_valid;         
 
    int             m_listIndex = -1;    
 
    std::mutex      m_listLock;      
};
 
 
/*
 * Represents a single outline of a zone fill on a particular layer.  \a aSubpolyIndex indicates
 * which outline in the fill's SHAPE_POLY_SET.
 */
class CN_ZONE_LAYER : public CN_ITEM
{
    using TRI_RTREE = KIRTREE::PACKED_RTREE<const SHAPE*, int, 2>;
 
public:
    CN_ZONE_LAYER( ZONE* aParent, PCB_LAYER_ID aLayer, int aSubpolyIndex ) :
            CN_ITEM( aParent, false ),
            m_zone( aParent ),
            m_subpolyIndex( aSubpolyIndex ),
            m_layer( aLayer )
    {
        std::shared_ptr<SHAPE_POLY_SET> fillPoly = aParent->GetFilledPolysList( aLayer );
 
        if( fillPoly && aSubpolyIndex < fillPoly->OutlineCount() )
            m_outline = fillPoly->Outline( aSubpolyIndex );
 
        SetLayers( aLayer, aLayer );
    }
 
    void BuildRTree()
    {
        if( m_zone->IsTeardropArea() )
            return;
 
        m_triangulatedPolys.clear();
        m_rTree = TRI_RTREE();
 
        std::shared_ptr<SHAPE_POLY_SET> fillPoly = m_zone->GetFilledPolysList( m_layer );
 
        if( !fillPoly )
            return;
 
        size_t triangleCount = 0;
 
        for( unsigned int ii = 0; ii < fillPoly->TriangulatedPolyCount(); ++ii )
        {
            const auto* triangleSet = fillPoly->TriangulatedPolygon( ii );
 
            if( triangleSet->GetSourceOutlineIndex() != m_subpolyIndex )
                continue;
 
            // Deep copy the triangulated polygon. The copy constructor copies the vertex storage
            // and updates all TRI parent pointers to reference our owned copy. This ensures the
            // triangles remain valid even if the zone is refilled on another thread.
            m_triangulatedPolys.push_back(
                    std::make_unique<SHAPE_POLY_SET::TRIANGULATED_POLYGON>( *triangleSet ) );
 
            triangleCount += m_triangulatedPolys.back()->GetTriangleCount();
        }
 
        // A fill is triangulated once and then only queried, so pack the index in one pass
        // rather than run the R*-tree subtree choice once per triangle
        TRI_RTREE::Builder builder;
        builder.Reserve( triangleCount );
 
        for( const auto& triPoly : m_triangulatedPolys )
        {
            const std::deque<VECTOR2I>& verts = triPoly->Vertices();
 
            for( const SHAPE_POLY_SET::TRIANGULATED_POLYGON::TRI& tri : triPoly->Triangles() )
            {
                const VECTOR2I& va = verts[tri.a];
                const VECTOR2I& vb = verts[tri.b];
                const VECTOR2I& vc = verts[tri.c];
 
                // The box TRI::BBox() returns, without its out-of-line virtual call
                const int mmin[2] = { std::min( { va.x, vb.x, vc.x } ),
                                      std::min( { va.y, vb.y, vc.y } ) };
                const int mmax[2] = { std::max( { va.x, vb.x, vc.x } ),
                                      std::max( { va.y, vb.y, vc.y } ) };
 
                builder.Add( mmin, mmax, &tri );
            }
        }
 
        m_rTree = builder.Build();
    }
 
    int SubpolyIndex() const { return m_subpolyIndex; }
 
    PCB_LAYER_ID GetLayer() const { return m_layer; }
 
    bool ContainsPoint( const VECTOR2I& p ) const
    {
        if( m_outline.PointCount() == 0 )
            return false;
 
        if( m_zone->IsTeardropArea() )
            return m_outline.Collide( p );
 
        int  min[2] = { p.x, p.y };
        int  max[2] = { p.x, p.y };
        bool collision = false;
 
        auto visitor =
                [&]( const SHAPE* aShape ) -> bool
                {
                    if( aShape->Collide( p ) )
                    {
                        collision = true;
                        return false;
                    }
 
                    return true;
                };
 
        m_rTree.Search( min, max, visitor );
 
        return collision;
    }
 
    PCB_LAYER_ID GetLayer() { return m_layer; }
 
    virtual int AnchorCount() const override;
    virtual const VECTOR2I GetAnchor( int n ) const override;
 
    bool HasValidOutline() const
    {
        return m_outline.PointCount() > 0;
    }
 
    const SHAPE_LINE_CHAIN& GetOutline() const
    {
        return m_outline;
    }
 
    int OutlinePointCount() const
    {
        return m_outline.PointCount();
    }
 
    const VECTOR2I& OutlinePoint( int aIndex ) const
    {
        return m_outline.CPoint( aIndex );
    }
 
    bool Collide( SHAPE* aRefShape ) const
    {
        if( m_outline.PointCount() == 0 )
            return false;
 
        if( m_zone->IsTeardropArea() )
            return aRefShape->Collide( &m_outline, 0 );
 
        BOX2I bbox = aRefShape->BBox();
        int  min[2] = { bbox.GetX(), bbox.GetY() };
        int  max[2] = { bbox.GetRight(), bbox.GetBottom() };
        bool collision = false;
 
        auto visitor =
                [&]( const SHAPE* aShape ) -> bool
                {
                    if( aRefShape->Collide( aShape ) )
                    {
                        collision = true;
                        return false;
                    }
 
                    return true;
                };
 
        m_rTree.Search( min, max, visitor );
 
        return collision;
    }
 
    bool HasSingleConnection();
 
private:
    ZONE*                               m_zone;
    int                                 m_subpolyIndex;
    PCB_LAYER_ID                        m_layer;
    SHAPE_LINE_CHAIN                    m_outline;       
    std::vector<std::unique_ptr<SHAPE_POLY_SET::TRIANGULATED_POLYGON>> m_triangulatedPolys;
    TRI_RTREE                                                          m_rTree;
};
 
 
 
 
class CN_LIST
{
public:
    CN_LIST()
    {
        m_dirty = false;
        m_hasInvalid = false;
    }
 
    void Clear()
    {
        for( CN_ITEM* item : m_items )
            delete item;
 
        m_items.clear();
        m_index.RemoveAll();
        m_bulkAdd = false;
    }

    bool StartBulkAdd()
    {
        if( !m_items.empty() || m_hasInvalid )
            return false;
 
        m_bulkAdd = true;
        return true;
    }

    void FinishBulkAdd()
    {
        if( !m_bulkAdd )
            return;
 
        m_bulkAdd = false;
 
        std::vector<CN_RTREE<CN_ITEM*>::BULK_ENTRY> entries;
        entries.reserve( m_items.size() );
 
        for( CN_ITEM* item : m_items )
        {
            // BBox() clears the dirty flag that Add() deliberately leaves set
            bool         dirty = item->Dirty();
            const BOX2I& bbox = item->BBox();
 
            entries.push_back( { { item->StartLayer(), bbox.GetX(), bbox.GetY() },
                                 { item->EndLayer(), bbox.GetRight(), bbox.GetBottom() },
                                 item } );
 
            item->SetDirty( dirty );
        }
 
        m_index.BulkLoad( entries );
    }

    class BULK_ADD_SCOPE
    {
    public:
        explicit BULK_ADD_SCOPE( CN_LIST& aList ) : m_list( aList ) { m_list.StartBulkAdd(); }
        ~BULK_ADD_SCOPE() { m_list.FinishBulkAdd(); }
 
        BULK_ADD_SCOPE( const BULK_ADD_SCOPE& ) = delete;
        BULK_ADD_SCOPE& operator=( const BULK_ADD_SCOPE& ) = delete;
 
    private:
        CN_LIST& m_list;
    };
 
    std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
    std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
 
    std::vector<CN_ITEM*>::const_iterator begin() const { return m_items.begin(); }
    std::vector<CN_ITEM*>::const_iterator end() const { return m_items.end(); }
 
    CN_ITEM* operator[] ( int aIndex ) { return m_items[aIndex]; }
 
    template <class T>
    void FindNearby( CN_ITEM* aItem, T aFunc )
    {
        m_index.Query( aItem->BBox(), aItem->StartLayer(), aItem->EndLayer(), aFunc );
    }
 
    void SetHasInvalid( bool aInvalid = true ) { m_hasInvalid = aInvalid; }
 
    void SetDirty( bool aDirty = true ) { m_dirty = aDirty; }
    bool IsDirty() const { return m_dirty; }
 
    void RemoveInvalidItems( std::vector<CN_ITEM*>& aGarbage );
 
    void ClearDirtyFlags()
    {
        for( CN_ITEM* item : m_items )
            item->SetDirty( false );
 
        SetDirty( false );
    }
 
    int Size() const { return m_items.size(); }
 
    CN_ITEM* Add( PAD* pad );
    CN_ITEM* Add( PCB_TRACK* track );
    CN_ITEM* Add( PCB_ARC* track );
    CN_ITEM* Add( PCB_VIA* via );
    CN_ITEM* Add( CN_ZONE_LAYER* zitem );
    CN_ITEM* Add( PCB_SHAPE* shape );
 
    const std::vector<CN_ITEM*> Add( ZONE* zone, PCB_LAYER_ID aLayer );
 
protected:
    void addItemtoTree( CN_ITEM* item )
    {
        if( !m_bulkAdd )
            m_index.Insert( item );
    }

    void appendItem( CN_ITEM* aItem )
    {
        aItem->SetListIndex( static_cast<int>( m_items.size() ) );
        m_items.push_back( aItem );
    }
 
protected:
    std::vector<CN_ITEM*> m_items;
 
private:
    bool                  m_dirty;
    bool                  m_hasInvalid;
    bool                  m_bulkAdd = false;   
    CN_RTREE<CN_ITEM*>    m_index;
};
 
 
class CN_CLUSTER
{
public:
    CN_CLUSTER();
    ~CN_CLUSTER();
 
    bool HasValidNet() const { return m_originNet > 0; }
    int OriginNet() const { return m_originNet; }
 
    wxString OriginNetName() const;
 
    bool Contains( const CN_ITEM* aItem );
    bool Contains( const BOARD_CONNECTED_ITEM* aItem );
    void Dump();
 
    int Size() const { return m_items.size(); }
 
    bool IsOrphaned() const
    {
        return m_originPad == nullptr;
    }
 
    bool IsConflicting() const { return m_conflicting; }
 
    void Add( CN_ITEM* item );
 
    std::vector<CN_ITEM*>::iterator begin() { return m_items.begin(); };
    std::vector<CN_ITEM*>::iterator end() { return m_items.end(); };
 
private:
    bool                         m_conflicting;
    int                          m_originNet;
    CN_ITEM*                     m_originPad;
    std::vector<CN_ITEM*>        m_items;
    std::unordered_map<int, int> m_netRanks;
};
 
 
 
#endif /* PCBNEW_CONNECTIVITY_ITEMS_H */