1 /******************************************************************* 2 3 Part of the Fritzing project - http://fritzing.org 4 Copyright (c) 2007-2014 Fachhochschule Potsdam - http://fh-potsdam.de 5 6 Fritzing is free software: you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation, either version 3 of the License, or 9 (at your option) any later version. 10 11 Fritzing is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with Fritzing. If not, see <http://www.gnu.org/licenses/>. 18 19 ******************************************************************** 20 21 $Revision: 6955 $: 22 $Author: irascibl@gmail.com $: 23 $Date: 2013-04-06 23:14:37 +0200 (Sa, 06. Apr 2013) $ 24 25 ********************************************************************/ 26 27 #ifndef MAZEROUTER_H 28 #define MAZEROUTER_H 29 30 #include <QAction> 31 #include <QHash> 32 #include <QVector> 33 #include <QList> 34 #include <QSet> 35 #include <QPointF> 36 #include <QGraphicsItem> 37 #include <QLine> 38 #include <QProgressDialog> 39 #include <QUndoCommand> 40 #include <QPointer> 41 42 #include <limits> 43 #include <queue> 44 45 #include "../../viewgeometry.h" 46 #include "../../viewlayer.h" 47 #include "../../commands.h" 48 #include "../autorouter.h" 49 50 typedef quint64 GridValue; 51 52 struct GridPoint { 53 int x, y, z; 54 GridValue baseCost; 55 double qCost; 56 uchar flags; 57 58 bool operator<(const GridPoint&) const; 59 GridPoint(QPoint, int); 60 GridPoint(); 61 }; 62 63 struct PointZ { 64 QPointF p; 65 int z; 66 PointZPointZ67 PointZ(QPointF _p, int _z) { 68 p = _p; 69 z = _z; 70 } 71 }; 72 73 struct Net { 74 QList<class ConnectorItem *>* net; 75 QList< QList<ConnectorItem *> > subnets; 76 int pinsWithin; 77 int id; 78 }; 79 80 struct NetList { 81 QList<Net *> nets; 82 }; 83 84 struct Trace { 85 int netIndex; 86 int order; 87 uchar flags; 88 QList<GridPoint> gridPoints; 89 TraceTrace90 Trace() { 91 flags = 0; 92 } 93 }; 94 95 struct NetOrdering { 96 QList<int> order; 97 }; 98 99 struct Score { 100 NetOrdering ordering; 101 QMultiHash<int, Trace> traces; 102 QHash<int, int> routedCount; 103 QHash<int, int> viaCount; 104 int totalRoutedCount; 105 int totalViaCount; 106 int reorderNet; 107 bool anyUnrouted; 108 109 Score(); 110 void setOrdering(const NetOrdering &); 111 }; 112 113 struct Nearest { 114 int i, j; 115 double distance; 116 ConnectorItem * ic; 117 ConnectorItem * jc; 118 }; 119 120 struct Grid { 121 GridValue * data; 122 int x; 123 int y; 124 int z; 125 126 Grid(int x, int y, int layers); 127 128 GridValue at(int x, int y, int z) const; 129 void setAt(int x, int y, int z, GridValue value); 130 QList<QPoint> init(int x, int y, int z, int width, int height, const QImage &, GridValue value, bool collectPoints); 131 QList<QPoint> init4(int x, int y, int z, int width, int height, const QImage *, GridValue value, bool collectPoints); 132 void clear(); 133 void free(); 134 void copy(int fromIndex, int toIndex); 135 }; 136 137 138 struct NetElements { 139 QList<QDomElement> net; 140 QList<QDomElement> alsoNet; 141 QList<QDomElement> notNet; 142 }; 143 144 struct RouteThing { 145 QRectF r; 146 QRectF r4; 147 QList<ViewLayer::ViewLayerPlacement> layerSpecs; 148 Nearest nearest; 149 std::priority_queue<GridPoint> sourceQ; 150 std::priority_queue<GridPoint> targetQ; 151 QPoint gridSourcePoint; 152 QPoint gridTargetPoint; 153 GridValue sourceValue; 154 GridValue targetValue; 155 double bestDistanceToTarget; 156 double bestDistanceToSource; 157 GridPoint bestLocationToTarget; 158 GridPoint bestLocationToSource; 159 bool unrouted; 160 NetElements netElements[2]; 161 QSet<int> avoids; 162 }; 163 164 struct TraceThing { 165 QList<TraceWire *> newTraces; 166 QList<Via *> newVias; 167 QList<JumperItem *> newJumperItems; 168 QList<SymbolPaletteItem *> newNetLabels; 169 JumperItem * jumperItem; 170 SymbolPaletteItem * netLabel; 171 QPointF topLeft; 172 GridPoint nextTraceStart; 173 }; 174 175 struct ConnectionThing { 176 QMultiHash<ConnectorItem *, QPointer<ConnectorItem> > sd; 177 178 void add(ConnectorItem * s, ConnectorItem * d); 179 void remove(ConnectorItem * s); 180 void remove(ConnectorItem * s, ConnectorItem * d); 181 bool multi(ConnectorItem * s); 182 QList<ConnectorItem *> values(ConnectorItem * s); 183 }; 184 185 typedef bool (*JumperWillFitFunction)(GridPoint &, const Grid *, int halfSize); 186 typedef double (*CostFunction)(const QPoint & p1, const QPoint & p2); 187 188 //////////////////////////////////// 189 190 class MazeRouter : public Autorouter 191 { 192 Q_OBJECT 193 194 public: 195 MazeRouter(class PCBSketchWidget *, QGraphicsItem * board, bool adjustIf); 196 ~MazeRouter(void); 197 198 void start(); 199 200 protected: 201 void setUpWidths(double width); 202 int findPinsWithin(QList<ConnectorItem *> * net); 203 bool makeBoard(QImage *, double keepout, const QRectF & r); 204 bool makeMasters(QString &); 205 bool routeNets(NetList &, bool makeJumper, Score & currentScore, const QSizeF gridSize, QList<NetOrdering> & allOrderings); 206 bool routeOne(bool makeJumper, Score & currentScore, int netIndex, RouteThing &, QList<NetOrdering> & allOrderings); 207 void findNearestPair(QList< QList<ConnectorItem *> > & subnets, Nearest &); 208 void findNearestPair(QList< QList<ConnectorItem *> > & subnets, int i, QList<ConnectorItem *> & inet, Nearest &); 209 QList<QPoint> renderSource(QDomDocument * masterDoc, int z, ViewLayer::ViewLayerPlacement, Grid * grid, QList<QDomElement> & netElements, QList<ConnectorItem *> & subnet, GridValue value, bool clearElements, const QRectF & r); 210 QList<GridPoint> route(RouteThing &, int & viaCount); 211 void expand(GridPoint &, RouteThing &); 212 void expandOne(GridPoint &, RouteThing &, int dx, int dy, int dz, bool crossLayer); 213 bool viaWillFit(GridPoint &, Grid * grid); 214 QList<GridPoint> traceBack(GridPoint, Grid *, int & viaCount, GridValue sourceValue, GridValue targetValue); 215 GridPoint traceBackOne(GridPoint &, Grid *, int dx, int dy, int dz, GridValue sourceValue, GridValue targetValue); 216 void updateDisplay(int iz); 217 void updateDisplay(Grid *, int iz); 218 void updateDisplay(GridPoint &); 219 void clearExpansion(Grid * grid); 220 void prepSourceAndTarget(QDomDocument * masterdoc, RouteThing &, QList< QList<ConnectorItem *> > & subnets, int z, ViewLayer::ViewLayerPlacement); 221 bool moveBack(Score & currentScore, int index, QList<NetOrdering> & allOrderings); 222 void displayTrace(Trace &); 223 void initTraceDisplay(); 224 void traceObstacles(QList<Trace> & traces, int netIndex, Grid * grid, int ikeepout); 225 void traceAvoids(QList<Trace> & traces, int netIndex, RouteThing & routeThing); 226 bool routeNext(bool makeJumper, RouteThing &, QList< QList<ConnectorItem *> > & subnets, Score & currentScore, int netIndex, QList<NetOrdering> & allOrderings); 227 void cleanUpNets(NetList &); 228 void createTraces(NetList & netList, Score & bestScore, QUndoCommand * parentCommand); 229 void createTrace(Trace &, QList<GridPoint> &, TraceThing &, ConnectionThing &, Net *); 230 void removeColinear(QList<GridPoint> & gridPoints); 231 void removeSteps(QList<GridPoint> & gridPoints); 232 void removeStep(int ix, QList<GridPoint> & gridPoints); 233 ConnectorItem * findAnchor(GridPoint gp, TraceThing &, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already); 234 ConnectorItem * findAnchor(GridPoint gp, const QRectF &, TraceThing &, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already); 235 void addConnectionToUndo(ConnectorItem * from, ConnectorItem * to, QUndoCommand * parentCommand); 236 void addViaToUndo(Via *, QUndoCommand * parentCommand); 237 void addJumperToUndo(JumperItem *, QUndoCommand * parentCommand); 238 void routeJumper(int netIndex, RouteThing &, Score & currentScore); 239 void insertTrace(Trace & newTrace, int netIndex, Score & currentScore, int viaCount, bool incRouted); 240 SymbolPaletteItem * makeNetLabel(GridPoint & center, SymbolPaletteItem * pairedNetLabel, uchar traceFlags); 241 void addNetLabelToUndo(SymbolPaletteItem * netLabel, QUndoCommand * parentCommand); 242 GridPoint lookForJumper(GridPoint initial, GridValue targetValue, QPoint targetLocation); 243 void expandOneJ(GridPoint & gridPoint, std::priority_queue<GridPoint> & pq, int dx, int dy, int dz, GridValue targetValue, QPoint targetLocation, QSet<int> & already); 244 void removeOffBoardAnd(bool isPCBType, bool removeSingletons, bool bothSides); 245 void optimizeTraces(QList<int> & order, QMultiHash<int, QList< QPointer<TraceWire> > > &, QMultiHash<int, Via *> &, QMultiHash<int, JumperItem *> &, QMultiHash<int, SymbolPaletteItem *> &, NetList &, ConnectionThing &); 246 void reducePoints(QList<QPointF> & points, QPointF topLeft, QList<TraceWire *> & bundle, int startIndex, int endIndex, ConnectionThing &, int netIndex, ViewLayer::ViewLayerPlacement); 247 248 public slots: 249 void incCommandProgress(); 250 void setMaxCycles(int); 251 252 protected: 253 LayerList m_viewLayerIDs; 254 QHash<ViewLayer::ViewLayerPlacement, QDomDocument *> m_masterDocs; 255 double m_keepoutMils; 256 double m_keepoutGrid; 257 int m_keepoutGridInt; 258 int m_halfGridViaSize; 259 int m_halfGridJumperSize; 260 double m_gridPixels; 261 double m_standardWireWidth; 262 QImage * m_displayImage[2]; 263 QImage * m_boardImage; 264 QImage * m_spareImage; 265 QImage * m_spareImage2; 266 QGraphicsPixmapItem * m_displayItem[2]; 267 bool m_temporaryBoard; 268 CostFunction m_costFunction; 269 JumperWillFitFunction m_jumperWillFitFunction; 270 uint m_traceColors[2]; 271 Grid * m_grid; 272 int m_cleanupCount; 273 int m_netLabelIndex; 274 int m_commandCount; 275 }; 276 277 #endif 278