Horizon
pns_shove.h
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2014 CERN
5 * Copyright (C) 2016 KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#ifndef __PNS_SHOVE_H
23#define __PNS_SHOVE_H
24
25#include <vector>
26#include <stack>
27
28#include "pns_optimizer.h"
29#include "pns_routing_settings.h"
30#include "pns_algo_base.h"
31#include "pns_logger.h"
32#include "range.h"
33
34namespace PNS {
35
36class LINE;
37class NODE;
38class ROUTER;
39
46class SHOVE : public ALGO_BASE
47{
48public:
49
50 enum SHOVE_STATUS
51 {
52 SH_OK = 0,
53 SH_NULL,
54 SH_INCOMPLETE,
55 SH_HEAD_MODIFIED,
56 SH_TRY_WALK
57 };
58
59 SHOVE( NODE* aWorld, ROUTER* aRouter );
60 ~SHOVE();
61
62 virtual LOGGER* Logger() override
63 {
64 return &m_logger;
65 }
66
67 SHOVE_STATUS ShoveLines( const LINE& aCurrentHead );
68 SHOVE_STATUS ShoveMultiLines( const ITEM_SET& aHeadSet );
69
70 SHOVE_STATUS ShoveDraggingVia( VIA* aVia, const VECTOR2I& aWhere, VIA** aNewVia );
71 SHOVE_STATUS ProcessSingleLine( LINE& aCurrent, LINE& aObstacle,
72 LINE& aShoved );
73
74 void ForceClearance ( bool aEnabled, int aClearance )
75 {
76 if( aEnabled )
77 m_forceClearance = aClearance;
78 else
79 m_forceClearance = -1;
80 }
81
82 NODE* CurrentNode();
83
84 const LINE NewHead() const;
85
86 void SetInitialLine( LINE& aInitial );
87
88private:
89 typedef std::vector<SHAPE_LINE_CHAIN> HULL_SET;
90 typedef OPT<LINE> OPT_LINE;
91 typedef std::pair<LINE, LINE> LINE_PAIR;
92 typedef std::vector<LINE_PAIR> LINE_PAIR_VEC;
93
94 struct SPRINGBACK_TAG
95 {
96 int64_t m_length;
97 int m_segments;
98 VECTOR2I m_p;
99 NODE* m_node;
100 ITEM_SET m_headItems;
101 COST_ESTIMATOR m_cost;
102 OPT_BOX2I m_affectedArea;
103 };
104
105 SHOVE_STATUS processHullSet( LINE& aCurrent, LINE& aObstacle,
106 LINE& aShoved, const HULL_SET& hulls );
107
108 bool reduceSpringback( const ITEM_SET& aHeadItems );
109 bool pushSpringback( NODE* aNode, const ITEM_SET& aHeadItems,
110 const COST_ESTIMATOR& aCost, const OPT_BOX2I& aAffectedArea );
111
112 SHOVE_STATUS walkaroundLoneVia( LINE& aCurrent, LINE& aObstacle, LINE& aShoved );
113 bool checkBumpDirection( const LINE& aCurrent, const LINE& aShoved ) const;
114
115 SHOVE_STATUS onCollidingLine( LINE& aCurrent, LINE& aObstacle );
116 SHOVE_STATUS onCollidingSegment( LINE& aCurrent, SEGMENT* aObstacleSeg );
117 SHOVE_STATUS onCollidingSolid( LINE& aCurrent, ITEM* aObstacle );
118 SHOVE_STATUS onCollidingVia( ITEM* aCurrent, VIA* aObstacleVia );
119 SHOVE_STATUS onReverseCollidingVia( LINE& aCurrent, VIA* aObstacleVia );
120 SHOVE_STATUS pushVia( VIA* aVia, const VECTOR2I& aForce, int aCurrentRank, bool aDryRun = false );
121
122 OPT_BOX2I totalAffectedArea() const;
123
124 void unwindStack( SEGMENT* aSeg );
125 void unwindStack( ITEM* aItem );
126
127 void runOptimizer( NODE* aNode );
128
129 bool pushLine( const LINE& aL, bool aKeepCurrentOnTop = false );
130 void popLine();
131
132 LINE assembleLine( const SEGMENT* aSeg, int* aIndex = NULL );
133
134 void replaceItems( ITEM* aOld, std::unique_ptr< ITEM > aNew );
135 void replaceLine( LINE& aOld, LINE& aNew );
136
137 OPT_BOX2I m_affectedAreaSum;
138
139 SHOVE_STATUS shoveIteration( int aIter );
140 SHOVE_STATUS shoveMainLoop();
141
142 int getClearance( const ITEM* aA, const ITEM* aB ) const;
143
144 std::vector<SPRINGBACK_TAG> m_nodeStack;
145 std::vector<LINE> m_lineStack;
146 std::vector<LINE> m_optimizerQueue;
147
148 NODE* m_root;
149 NODE* m_currentNode;
150
151 OPT_LINE m_newHead;
152
153 LOGGER m_logger;
154 VIA* m_draggedVia;
155 ITEM_SET m_draggedViaHeadSet;
156
157 int m_iter;
158 int m_forceClearance;
159 bool m_multiLineMode;
160 void sanityCheck( LINE* aOld, LINE* aNew );
161};
162
163}
164
165#endif // __PNS_SHOVE_H
Class ALGO_BASE.
Definition: pns_algo_base.h:40
Definition: pns_itemset.h:40
Definition: pns_line.h:61
Definition: pns_logger.h:40
Class NODE.
Definition: pns_node.h:138
Definition: pns_router.h:113
Class SHOVE.
Definition: pns_shove.h:47
virtual LOGGER * Logger() override
‍Returns the logger object, allowing to dump geometry to a file.
Definition: pns_shove.h:62
Definition: pns_via.h:38