pns_optimizer.h 5.08 KB
Newer Older
1 2 3
/*
 * KiRouter - a push-and-(sometimes-)shove PCB router
 *
4
 * Copyright (C) 2013-2014 CERN
5
 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6
 *
7 8 9 10
 * 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.
11
 *
12 13 14 15
 * 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.
16
 *
17
 * You should have received a copy of the GNU General Public License along
18
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
19
 */
20

21 22 23 24 25 26 27 28 29
#ifndef __PNS_OPTIMIZER_H
#define __PNS_OPTIMIZER_H

#include <boost/unordered_map.hpp>
#include <boost/shared_ptr.hpp>

#include <geometry/shape_index_list.h>
#include <geometry/shape_line_chain.h>

30 31
#include "range.h"

32 33 34 35 36 37 38 39
class PNS_NODE;
class PNS_LINE;
class PNS_ROUTER;

/**
 * Class PNS_COST_ESTIMATOR
 *
 * Calculates the cost of a given line, taking corner angles and total length into account.
40 41
 **/
class PNS_COST_ESTIMATOR
42
{
43 44 45 46
public:
    PNS_COST_ESTIMATOR() :
        m_lengthCost( 0 ),
        m_cornerCost( 0 )
47
    {}
48

49 50 51 52
    PNS_COST_ESTIMATOR( const PNS_COST_ESTIMATOR& aB ) :
        m_lengthCost( aB.m_lengthCost ),
        m_cornerCost( aB.m_cornerCost )
    {}
53 54 55

    ~PNS_COST_ESTIMATOR() {};

56
    static int CornerCost( const SEG& aA, const SEG& aB );
57 58 59 60 61 62 63 64
    static int CornerCost( const SHAPE_LINE_CHAIN& aLine );
    static int CornerCost( const PNS_LINE& aLine );

    void Add( PNS_LINE& aLine );
    void Remove( PNS_LINE& aLine );
    void Replace( PNS_LINE& aOldLine, PNS_LINE& aNewLine );

    bool IsBetter( PNS_COST_ESTIMATOR& aOther, double aLengthTollerance,
65
                   double aCornerTollerace ) const;
66 67 68 69 70 71 72

    double GetLengthCost() const { return m_lengthCost; }
    double GetCornerCost() const { return m_cornerCost; }

private:
    double m_lengthCost;
    int m_cornerCost;
73 74 75 76
};

/**
 * Class PNS_OPTIMIZER
77
 *
78 79
 * Performs various optimizations of the lines being routed, attempting to make the lines shorter
 * and less cornery. There are 3 kinds of optimizations so far:
80
 * - Merging obtuse segments (MERGE_OBTUSE): tries to join together as many
81 82 83
 *   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
84
 * - "Smart Pads" - that is, rerouting pad/via exits to make them look nice (SMART_PADS).
85
 **/
86
class PNS_OPTIMIZER
87
{
88 89 90 91 92
public:
    enum OptimizationEffort
    {
        MERGE_SEGMENTS  = 0x01,
        SMART_PADS      = 0x02,
93 94
        MERGE_OBTUSE    = 0x04,
        FANOUT_CLEANUP    = 0x08
95
    };
96

97 98
    PNS_OPTIMIZER( PNS_NODE* aWorld );
    ~PNS_OPTIMIZER();
99

100
    ///> a quick shortcut to optmize a line without creating and setting up an optimizer
101
    static bool Optimize( PNS_LINE* aLine, int aEffortLevel, PNS_NODE* aWorld);
102

103
    bool Optimize( PNS_LINE* aLine, PNS_LINE* aResult = NULL );
104

105 106 107 108
    void SetWorld( PNS_NODE* aNode ) { m_world = aNode; }
    void CacheStaticItem( PNS_ITEM* aItem );
    void CacheRemove( PNS_ITEM* aItem );
    void ClearCache( bool aStaticOnly = false );
109

110 111 112 113
    void SetCollisionMask( int aMask )
    {
        m_collisionKindMask = aMask;
    }
114

115 116 117 118
    void SetEffortLevel( int aEffort )
    {
        m_effortLevel = aEffort;
    }
119

120 121
private:
    static const int MaxCachedItems = 256;
122

123
    typedef std::vector<SHAPE_LINE_CHAIN> BREAKOUT_LIST;
124

125
    struct CACHE_VISITOR;
126

127
    struct CACHED_ITEM
128
    {
129 130
        int m_hits;
        bool m_isStatic;
131
    };
132

133 134 135 136 137
    bool mergeObtuse( PNS_LINE* aLine );
    bool mergeFull( PNS_LINE* aLine );
    bool removeUglyCorners( PNS_LINE* aLine );
    bool runSmartPads( PNS_LINE* aLine );
    bool mergeStep( PNS_LINE* aLine, SHAPE_LINE_CHAIN& aCurrentLine, int step );
138
    bool fanoutCleanup( PNS_LINE * aLine );
139

140 141
    bool checkColliding( PNS_ITEM* aItem, bool aUpdateCache = true );
    bool checkColliding( PNS_LINE* aLine, const SHAPE_LINE_CHAIN& aOptPath );
142

143 144
    void cacheAdd( PNS_ITEM* aItem, bool aIsStatic );
    void removeCachedSegments( PNS_LINE* aLine, int aStartVertex = 0, int aEndVertex = -1 );
145

146 147 148 149
    BREAKOUT_LIST circleBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
    BREAKOUT_LIST rectBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
    BREAKOUT_LIST ovalBreakouts( int aWidth, const SHAPE* aShape, bool aPermitDiagonal ) const;
    BREAKOUT_LIST computeBreakouts( int aWidth, const PNS_ITEM* aItem, bool aPermitDiagonal ) const;
150

151
    int smartPadsSingle( PNS_LINE* aLine, PNS_ITEM* aPad, bool aEnd, int aEndVertex );
152

153
    PNS_ITEM* findPadOrVia( int aLayer, int aNet, const VECTOR2I& aP ) const;
154

155
    SHAPE_INDEX_LIST<PNS_ITEM*> m_cache;
156

157
    typedef boost::unordered_map<PNS_ITEM*, CACHED_ITEM> CachedItemTags;
158 159 160 161 162
    CachedItemTags m_cacheTags;
    PNS_NODE* m_world;
    int m_collisionKindMask;
    int m_effortLevel;
    bool m_keepPostures;
163 164 165
};

#endif