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
12 Fritzing is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Fritzing. If not, see <http://www.gnu.org/licenses/>.
19
20 ********************************************************************
21
22 $Revision: 6966 $:
23 $Author: irascibl@gmail.com $:
24 $Date: 2013-04-15 11:25:51 +0200 (Mo, 15. Apr 2013) $
25
26 ********************************************************************/
27
28
29 // with lots of suggestions from http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD/unit6.pdf
30 // and some help from http://workbench.lafayette.edu/~nestorj/cadapplets/MazeApplet/src/
31 // more (unused) suggestions at http://embedded.eecs.berkeley.edu/Alumni/pinhong/ee244/4-routing.PDF
32
33 // TODO:
34 //
35 // jumper placement must be away from vias and vv
36 // how to create test case
37 //
38 // test if source touches target
39 //
40 // add max cycles to settings dialog?
41 //
42 // figure out what is taking so long once the router is creating traces
43 // change connection is calling ratsnestconnect for every pair and calls collectEqualPotential
44 //
45 // net reordering/rip-up-and-reroute
46 // is there a better way than move back by one?
47 //
48 // raster back to vector
49 // curve-fitting? use a bezier? http://kobus.ca/seminars/ugrad/NM5_curve_s02.pdf
50 //
51 // dynamic cost function based on distance to any target point?
52 //
53 // allow multiple routes to reach GridTarget--eliminate all queued GridPoints with greater cost
54 //
55 // what happens with expanded schematic frame?
56 //
57
58 #include "mazerouter.h"
59 #include "../../sketch/pcbsketchwidget.h"
60 #include "../../debugdialog.h"
61 #include "../../items/virtualwire.h"
62 #include "../../items/tracewire.h"
63 #include "../../items/jumperitem.h"
64 #include "../../items/symbolpaletteitem.h"
65 #include "../../items/via.h"
66 #include "../../items/resizableboard.h"
67 #include "../../utils/graphicsutils.h"
68 #include "../../utils/graphutils.h"
69 #include "../../utils/textutils.h"
70 #include "../../utils/folderutils.h"
71 #include "../../connectors/connectoritem.h"
72 #include "../../items/moduleidnames.h"
73 #include "../../processeventblocker.h"
74 #include "../../svg/groundplanegenerator.h"
75 #include "../../svg/svgfilesplitter.h"
76 #include "../../fsvgrenderer.h"
77 #include "../drc.h"
78 #include "../../connectors/svgidlayer.h"
79
80 #include <QApplication>
81 #include <QMessageBox>
82 #include <QSettings>
83
84 #include <qmath.h>
85 #include <limits>
86
87 //////////////////////////////////////
88
89 static const int OptimizeFactor = 2;
90
91 //static int routeNumber = 0;
92
93 static QString CancelledMessage;
94
95 static const int DefaultMaxCycles = 100;
96
97 static const GridValue GridBoardObstacle = std::numeric_limits<GridValue>::max();
98 static const GridValue GridPartObstacle = GridBoardObstacle - 1;
99 static const GridValue GridSource = GridBoardObstacle - 2;
100 static const GridValue GridTarget = GridBoardObstacle - 3;
101 static const GridValue GridAvoid = GridBoardObstacle - 4;
102 static const GridValue GridTempObstacle = GridBoardObstacle - 5;
103 static const GridValue GridSourceFlag = (GridBoardObstacle / 2) + 1;
104
105 static const uint Layer1Cost = 100;
106 static const uint CrossLayerCost = 100;
107 static const uint ViaCost = 2000;
108 static const uint AvoidCost = 7;
109
110 static const uchar GridPointDone = 1;
111 static const uchar GridPointStepYPlus = 2;
112 static const uchar GridPointStepYMinus = 4;
113 static const uchar GridPointStepXPlus = 8;
114 static const uchar GridPointStepXMinus = 16;
115 static const uchar GridPointStepStart = 32;
116 static const uchar GridPointJumperLeft = 64;
117 static const uchar GridPointJumperRight = 128;
118 //static const uchar GridPointNorth = 2;
119 //static const uchar GridPointEast = 4;
120 //static const uchar GridPointSouth = 8;
121 //static const uchar GridPointWest = 16;
122
123 static const uchar JumperStart = 1;
124 static const uchar JumperEnd = 2;
125 static const uchar JumperLeft = 4;
126 static const uchar JumperRight = 8;
127
128 static const double MinTraceManhattanLength = 0.1; // pixels
129
130 ////////////////////////////////////////////////////////////////////
131
getStepPoint(QPointF p,uchar flags,double gridPixels)132 QPointF getStepPoint(QPointF p, uchar flags, double gridPixels) {
133 if ((flags & GridPointStepXPlus) != 0) {
134 p.setX(p.x() + (gridPixels / 2));
135 return p;
136 }
137 if ((flags & GridPointStepXMinus) != 0) {
138 p.setX(p.x() - (gridPixels / 2));
139 return p;
140 }
141 if ((flags & GridPointStepYPlus) != 0) {
142 p.setY(p.y() + (gridPixels / 2));
143 return p;
144 }
145 p.setY(p.y() - (gridPixels / 2));
146 return p;
147 }
148
getStepFlag(GridPoint & gp1,GridPoint & gp2)149 uchar getStepFlag(GridPoint & gp1, GridPoint & gp2) {
150 if (gp1.y == gp2.y) {
151 double avg = (gp1.x + gp2.x) / 2.0;
152 return (avg > gp1.x) ? GridPointStepXPlus : GridPointStepXMinus;
153 }
154
155 double avg = (gp1.y + gp2.y) / 2.0;
156 return (avg > gp1.y) ? GridPointStepYPlus : GridPointStepYMinus;
157
158 }
159
getPixelCenter(GridPoint & gp,QPointF & topLeft,double gridPixels)160 QPointF getPixelCenter(GridPoint & gp, QPointF & topLeft, double gridPixels) {
161 return QPointF((gp.x * gridPixels) + topLeft.x() + (gridPixels / 2), (gp.y * gridPixels) + topLeft.y() + (gridPixels / 2));
162 }
163
getColor(GridValue val)164 uint getColor(GridValue val) {
165 if (val == GridBoardObstacle) return 0xff000000;
166 else if (val == GridPartObstacle) return 0xff404040;
167 else if (val == 0) return 0;
168 else if (val == GridSource) return 0xff00ff00;
169 else if (val == GridTarget) return 0xffff0000;
170 else if (val == GridAvoid) return 0xff808080;
171 else if (val == GridTempObstacle) return 0xff00ffff;
172 else if (val & GridSourceFlag) return 0xff60d060;
173 else return 0xffff6060;
174 }
175
fastCopy(QImage * from,QImage * to)176 void fastCopy(QImage * from, QImage * to) {
177 uchar * fromBits = from->scanLine(0);
178 uchar * toBits = to->scanLine(0);
179 long bytes = from->bytesPerLine() * from->height();
180 memcpy(toBits, fromBits, bytes);
181 }
182
atLeast(const QPointF & p1,const QPointF & p2)183 bool atLeast(const QPointF & p1, const QPointF & p2) {
184 return (qAbs(p1.x() - p2.x()) >= MinTraceManhattanLength) || (qAbs(p1.y() - p2.y()) >= MinTraceManhattanLength);
185 }
186
printOrder(const QString & msg,QList<int> & order)187 void printOrder(const QString & msg, QList<int> & order) {
188 QString string(msg);
189 foreach (int i, order) {
190 string += " " + QString::number(i);
191 }
192 DebugDialog::debug(string);
193 }
194
getPartID(const QDomElement & element)195 QString getPartID(const QDomElement & element) {
196 QString partID = element.attribute("partID");
197 if (!partID.isEmpty()) return partID;
198
199 QDomNode parent = element.parentNode();
200 if (parent.isNull()) return "";
201
202 return getPartID(parent.toElement());
203 }
204
idsMatch(const QDomElement & element,QMultiHash<QString,QString> & partIDs)205 bool idsMatch(const QDomElement & element, QMultiHash<QString, QString> & partIDs) {
206 QString partID = getPartID(element);
207 QStringList IDs = partIDs.values(partID);
208 if (IDs.count() == 0) return false;
209
210 QDomElement tempElement = element;
211 while (tempElement.attribute("partID").isEmpty()) {
212 QString id = tempElement.attribute("id");
213 if (!id.isEmpty() && IDs.contains(id)) return true;
214
215 tempElement = tempElement.parentNode().toElement();
216 }
217
218 return false;
219 }
220
byPinsWithin(Net * n1,Net * n2)221 bool byPinsWithin(Net * n1, Net * n2)
222 {
223 if (n1->pinsWithin < n2->pinsWithin) return true;
224 if (n1->pinsWithin > n2->pinsWithin) return false;
225
226 return n1->net->count() <= n2->net->count();
227 }
228
byOrder(Trace & t1,Trace & t2)229 bool byOrder(Trace & t1, Trace & t2) {
230 return (t1.order < t2.order);
231 }
232
233 /*
234 inline double initialCost(QPoint p1, QPoint p2) {
235 //return qAbs(p1.x() - p2.x()) + qAbs(p1.y() - p2.y());
236 return qSqrt(GraphicsUtils::distanceSqd(p1, p2));
237 }
238 */
239
distanceCost(const QPoint & p1,const QPoint & p2)240 inline double distanceCost(const QPoint & p1, const QPoint & p2) {
241 return GraphicsUtils::distanceSqd(p1, p2);
242 }
243
manhattanCost(const QPoint & p1,const QPoint & p2)244 inline double manhattanCost(const QPoint & p1, const QPoint & p2) {
245 return qMax(qAbs(p1.x() - p2.x()), qAbs(p1.y() - p2.y()));
246 }
247
gridPointInt(Grid * grid,GridPoint & gp)248 inline int gridPointInt(Grid * grid, GridPoint & gp) {
249 return (gp.z * grid->x * grid->y) + (gp.y * grid->x) + gp.x;
250 }
251
jumperWillFit(GridPoint & gridPoint,const Grid * grid,int halfSize)252 bool jumperWillFit(GridPoint & gridPoint, const Grid * grid, int halfSize) {
253 for (int z = 0; z < grid->z; z++) {
254 for (int y = -halfSize; y <= halfSize; y++) {
255 int py = gridPoint.y + y;
256 if (py < 0) return false;
257 if (py >= grid->y) return false;
258
259 for (int x = -halfSize; x <= halfSize; x++) {
260 int px = x + gridPoint.x;
261 if (px < 0) return false;
262 if (px >= grid->x) return false;
263
264 GridValue val = grid->at(px, py, z);
265 if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridAvoid|| val == GridTempObstacle) return false;
266 }
267 }
268 }
269
270 return true;
271 }
272
schematicJumperWillFitAux(GridPoint & gridPoint,const Grid * grid,int halfSize,int xl,int xr)273 bool schematicJumperWillFitAux(GridPoint & gridPoint, const Grid * grid, int halfSize, int xl, int xr) {
274 int underCount = 0;
275 for (int y = -halfSize; y <= halfSize; y++) {
276 if (y < 0) return false;
277 if (y >= grid->y) return false;
278
279 for (int x = xl; x <= xr; x++) {
280 if (x < 0) return false;
281 if (x >= grid->x) return false;
282
283 GridValue val = grid->at(gridPoint.x + x, gridPoint.y + y, 0);
284 if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridAvoid|| val == GridTempObstacle) {
285 return false;
286 }
287
288 if (val < gridPoint.baseCost) {
289 if (++underCount > xr - xl) return false;
290 }
291 }
292 }
293
294 return true;
295 }
296
schematicJumperWillFit(GridPoint & gridPoint,const Grid * grid,int halfSize)297 bool schematicJumperWillFit(GridPoint & gridPoint, const Grid * grid, int halfSize)
298 {
299 if (schematicJumperWillFitAux(gridPoint, grid, halfSize, -(halfSize * 2), 0)) {
300 gridPoint.flags |= GridPointJumperLeft;
301 return true;
302 }
303 if (schematicJumperWillFitAux(gridPoint, grid, halfSize, 0, halfSize * 2)) {
304 gridPoint.flags |= GridPointJumperRight;
305 return true;
306 }
307
308 return false;
309 }
310
initMarkers(Markers & markers,bool pcbType)311 void initMarkers(Markers & markers, bool pcbType) {
312 markers.outID = DRC::NotNet;
313 markers.inTerminalID = pcbType ? DRC::AlsoNet : DRC::Net;
314 markers.inSvgID = DRC::Net;
315 markers.inSvgAndID = pcbType ? DRC::Net : DRC::AlsoNet;
316 markers.inNoID = DRC::Net;
317 }
318
319 ////////////////////////////////////////////////////////////////////
320
operator <(const GridPoint & other) const321 bool GridPoint::operator<(const GridPoint& other) const {
322 // make sure lower cost is first
323 return qCost > other.qCost;
324 }
325
GridPoint(QPoint p,int zed)326 GridPoint::GridPoint(QPoint p, int zed) {
327 z = zed;
328 x = p.x();
329 y = p.y();
330 flags = 0;
331 }
332
GridPoint()333 GridPoint::GridPoint()
334 {
335 flags = 0;
336 }
337
338 ////////////////////////////////////////////////////////////////////
339
Grid(int sx,int sy,int sz)340 Grid::Grid(int sx, int sy, int sz) {
341 x = sx;
342 y = sy;
343 z = sz;
344
345 data = (GridValue *) malloc(x * y * z * sizeof(GridValue)); // calloc initializes grid to 0
346 }
347
at(int sx,int sy,int sz) const348 GridValue Grid::at(int sx, int sy, int sz) const {
349 return *(data + (sz * y * x) + (sy * x) + sx);
350 }
351
setAt(int sx,int sy,int sz,GridValue value)352 void Grid::setAt(int sx, int sy, int sz, GridValue value) {
353 *(data + (sz * y * x) + (sy * x) + sx) = value;
354 }
355
init(int sx,int sy,int sz,int width,int height,const QImage & image,GridValue value,bool collectPoints)356 QList<QPoint> Grid::init(int sx, int sy, int sz, int width, int height, const QImage & image, GridValue value, bool collectPoints) {
357 QList<QPoint> points;
358 const uchar * bits1 = image.constScanLine(0);
359 int bytesPerLine = image.bytesPerLine();
360 for (int iy = sy; iy < sy + height; iy++) {
361 int offset = iy * bytesPerLine;
362 for (int ix = sx; ix < sx + width; ix++) {
363 int byteOffset = (ix >> 3) + offset;
364 uchar mask = DRC::BitTable[ix & 7];
365
366 //if (routeNumber > 40) {
367 // DebugDialog::debug(QString("image %1 %2, %3").arg(image.width()).arg(image.height()).arg(image.isNull()));
368 // DebugDialog::debug(QString("init point %1 %2 %3").arg(ix).arg(iy).arg(sz));
369 // DebugDialog::debug(QString("init grid %1 %2 %3, %4").arg(x).arg(y).arg(z).arg((long) data, 0, 16));
370 //}
371 if ((*(bits1 + byteOffset)) & mask) continue;
372
373 //if (routeNumber > 40) DebugDialog::debug("after mask");
374
375 setAt(ix, iy, sz, value);
376 //if (routeNumber > 40)
377 // DebugDialog::debug("set");
378 if (collectPoints) {
379 points.append(QPoint(ix, iy));
380 }
381 }
382 }
383
384 return points;
385 }
386
387
init4(int sx,int sy,int sz,int width,int height,const QImage * image,GridValue value,bool collectPoints)388 QList<QPoint> Grid::init4(int sx, int sy, int sz, int width, int height, const QImage * image, GridValue value, bool collectPoints) {
389 // pixels are 4 x 4 bits
390 QList<QPoint> points;
391 const uchar * bits1 = image->constScanLine(0);
392 int bytesPerLine = image->bytesPerLine();
393 for (int iy = sy; iy < sy + height; iy++) {
394 int offset = iy * bytesPerLine * 4;
395 for (int ix = sx; ix < sx + width; ix++) {
396 int byteOffset = (ix >> 1) + offset;
397 uchar mask = ix & 1 ? 0x0f : 0xf0;
398
399 if ((*(bits1 + byteOffset) & mask) != mask) ;
400 else if ((*(bits1 + byteOffset + bytesPerLine) & mask) != mask) ;
401 else if ((*(bits1 + byteOffset + bytesPerLine + bytesPerLine) & mask) != mask) ;
402 else if ((*(bits1 + byteOffset + bytesPerLine + bytesPerLine + bytesPerLine) & mask) != mask) ;
403 else continue; // "pixel" is all white
404
405 setAt(ix, iy, sz, value);
406 if (collectPoints) {
407 points.append(QPoint(ix, iy));
408 }
409 }
410 }
411
412 return points;
413 }
414
copy(int fromIndex,int toIndex)415 void Grid::copy(int fromIndex, int toIndex) {
416 memcpy(((uchar *) data) + toIndex * x * y * sizeof(GridValue), ((uchar *) data) + fromIndex * x * y * sizeof(GridValue), x * y * sizeof(GridValue));
417 }
418
clear()419 void Grid::clear() {
420 memset(data, 0, x * y * z * sizeof(GridValue));
421 }
422
free()423 void Grid::free() {
424 if (data) {
425 ::free(data);
426 data = NULL;
427 }
428 }
429
430 ////////////////////////////////////////////////////////////////////
431
Score()432 Score::Score() {
433 totalRoutedCount = totalViaCount = 0;
434 anyUnrouted = false;
435 reorderNet = -1;
436 }
437
setOrdering(const NetOrdering & _ordering)438 void Score::setOrdering(const NetOrdering & _ordering) {
439 reorderNet = -1;
440 if (ordering.order.count() > 0) {
441 bool remove = false;
442 for (int i = 0; i < ordering.order.count(); i++) {
443 if (!remove && (ordering.order.at(i) == _ordering.order.at(i))) continue;
444
445 remove = true;
446 int netIndex = ordering.order.at(i);
447 traces.remove(netIndex);
448 int c = routedCount.value(netIndex);
449 routedCount.remove(netIndex);
450 totalRoutedCount -= c;
451 c = viaCount.value(netIndex);
452 viaCount.remove(netIndex);
453 totalViaCount -= c;
454 }
455 }
456 ordering = _ordering;
457 //printOrder("new ", ordering.order);
458 }
459
460 ////////////////////////////////////////////////////////////////////
461
462 static const long IDs[] = { 1452191, 9781580, 9781600, 9781620, 9781640, 9781660, 9781680, 9781700 };
hasID(ConnectorItem * s)463 static inline bool hasID(ConnectorItem * s) {
464 for (unsigned int i = 0; i < sizeof(IDs) / sizeof(long); i++) {
465 if (s->attachedToID() == IDs[i]) return true;
466 }
467
468 return false;
469 }
470
471
472
add(ConnectorItem * s,ConnectorItem * d)473 void ConnectionThing::add(ConnectorItem * s, ConnectorItem * d) {
474 //if (hasID(s) || hasID(d)) {
475 // s->debugInfo("addc");
476 // d->debugInfo("\t");
477 //}
478
479 sd.insert(s, d);
480 sd.insert(d, s);
481 }
482
remove(ConnectorItem * s)483 void ConnectionThing::remove(ConnectorItem * s) {
484 //if (hasID(s)) {
485 // s->debugInfo("remc");
486 //}
487 sd.remove(s);
488 }
489
remove(ConnectorItem * s,ConnectorItem * d)490 void ConnectionThing::remove(ConnectorItem * s, ConnectorItem * d) {
491 //if (hasID(s) || hasID(d)) {
492 // s->debugInfo("remc");
493 // d->debugInfo("\t");
494 //}
495 sd.remove(s, d);
496 sd.remove(d, s);
497 }
498
multi(ConnectorItem * s)499 bool ConnectionThing::multi(ConnectorItem * s) {
500 //if (hasID(s)) {
501 // s->debugInfo("mulc");
502 //}
503 return sd.values(s).count() > 1;
504 }
505
values(ConnectorItem * s)506 QList<ConnectorItem *> ConnectionThing::values(ConnectorItem * s) {
507 //if (hasID(s)) {
508 // s->debugInfo("valc");
509 //}
510 QList<ConnectorItem *> result;
511 foreach (ConnectorItem * d, sd.values(s)) {
512 if (d == NULL) continue;
513 if (sd.values(d).count() == 0) continue;
514 result << d;
515 //if (hasID(s)) d->debugInfo("\t");
516 }
517 return result;
518 }
519
520 ////////////////////////////////////////////////////////////////////
521
MazeRouter(PCBSketchWidget * sketchWidget,QGraphicsItem * board,bool adjustIf)522 MazeRouter::MazeRouter(PCBSketchWidget * sketchWidget, QGraphicsItem * board, bool adjustIf) : Autorouter(sketchWidget)
523 {
524 m_netLabelIndex = -1;
525 m_grid = NULL;
526 m_displayItem[0] = m_displayItem[1] = NULL;
527 m_boardImage = m_spareImage = m_spareImage2 = m_displayImage[0] = m_displayImage[1] = NULL;
528
529 CancelledMessage = tr("Autorouter was cancelled.");
530
531 QSettings settings;
532 m_maxCycles = settings.value(MaxCyclesName, DefaultMaxCycles).toInt();
533
534 m_bothSidesNow = sketchWidget->routeBothSides();
535 m_pcbType = sketchWidget->autorouteTypePCB();
536 m_board = board;
537 m_temporaryBoard = false;
538
539 if (m_board) {
540 m_maxRect = m_board->sceneBoundingRect();
541 }
542 else {
543 QRectF itemsBoundingRect;
544 foreach(QGraphicsItem *item, m_sketchWidget->scene()->items()) {
545 if (!item->isVisible()) continue;
546
547 itemsBoundingRect |= item->sceneBoundingRect();
548 }
549 m_maxRect = itemsBoundingRect; // itemsBoundingRect is not reliable. m_sketchWidget->scene()->itemsBoundingRect();
550 if (adjustIf) {
551 m_maxRect.adjust(-m_maxRect.width() / 2, -m_maxRect.height() / 2, m_maxRect.width() / 2, m_maxRect.height() / 2);
552 }
553 m_board = new QGraphicsRectItem(m_maxRect);
554 m_board->setVisible(false);
555 m_sketchWidget->scene()->addItem(m_board);
556 m_temporaryBoard = true;
557 }
558
559 m_standardWireWidth = m_sketchWidget->getAutorouterTraceWidth();
560
561 /*
562 // for debugging leave the last result hanging around
563 QList<QGraphicsPixmapItem *> pixmapItems;
564 foreach (QGraphicsItem * item, m_sketchWidget->scene()->items()) {
565 QGraphicsPixmapItem * pixmapItem = dynamic_cast<QGraphicsPixmapItem *>(item);
566 if (pixmapItem) pixmapItems << pixmapItem;
567 }
568 foreach (QGraphicsPixmapItem * pixmapItem, pixmapItems) {
569 delete pixmapItem;
570 }
571 */
572
573 ViewGeometry vg;
574 vg.setWireFlags(m_sketchWidget->getTraceFlag());
575 ViewLayer::ViewLayerID bottom = sketchWidget->getWireViewLayerID(vg, ViewLayer::NewBottom);
576 m_viewLayerIDs << bottom;
577 if (m_bothSidesNow) {
578 ViewLayer::ViewLayerID top = sketchWidget->getWireViewLayerID(vg, ViewLayer::NewTop);
579 m_viewLayerIDs.append(top);
580 }
581 }
582
~MazeRouter()583 MazeRouter::~MazeRouter()
584 {
585 foreach (QDomDocument * doc, m_masterDocs) {
586 delete doc;
587 }
588 if (m_displayItem[0]) {
589 delete m_displayItem[0];
590 }
591 if (m_displayItem[1]) {
592 delete m_displayItem[1];
593 }
594 if (m_displayImage[0]) {
595 delete m_displayImage[0];
596 }
597 if (m_displayImage[1]) {
598 delete m_displayImage[1];
599 }
600 if (m_temporaryBoard && m_board != NULL) {
601 delete m_board;
602 }
603 if (m_grid) {
604 m_grid->free();
605 delete m_grid;
606 }
607 if (m_boardImage) {
608 delete m_boardImage;
609 }
610 if (m_spareImage) {
611 delete m_spareImage;
612 }
613 if (m_spareImage2) {
614 delete m_spareImage2;
615 }
616 }
617
start()618 void MazeRouter::start()
619 {
620 if (m_pcbType) {
621 if (m_board == NULL) {
622 QMessageBox::warning(NULL, QObject::tr("Fritzing"), QObject::tr("Cannot autoroute: no board (or multiple boards) found"));
623 return;
624 }
625 m_jumperWillFitFunction = jumperWillFit;
626 m_costFunction = distanceCost;
627 m_traceColors[0] = 0xa0F28A00;
628 m_traceColors[1] = 0xa0FFCB33;
629 }
630 else {
631 m_jumperWillFitFunction = schematicJumperWillFit;
632 m_costFunction = manhattanCost;
633 m_traceColors[0] = m_traceColors[1] = 0xa0303030;
634 }
635
636 m_keepoutPixels = m_sketchWidget->getKeepout(); // 15 mils space (in pixels)
637 m_gridPixels = qMax(m_standardWireWidth, m_keepoutPixels);
638 m_keepoutMils = m_keepoutPixels * GraphicsUtils::StandardFritzingDPI / GraphicsUtils::SVGDPI;
639 m_keepoutGrid = m_keepoutPixels / m_gridPixels;
640 m_keepoutGridInt = qCeil(m_keepoutGrid);
641
642 double ringThickness, holeSize;
643 m_sketchWidget->getViaSize(ringThickness, holeSize);
644 int gridViaSize = qCeil((ringThickness + ringThickness + holeSize + m_keepoutPixels + m_keepoutPixels) / m_gridPixels);
645 m_halfGridViaSize = gridViaSize / 2;
646
647 QSizeF jumperSize = m_sketchWidget->jumperItemSize();
648 int gridJumperSize = qCeil((qMax(jumperSize.width(), jumperSize.height()) + m_keepoutPixels + m_keepoutPixels) / m_gridPixels);
649 m_halfGridJumperSize = gridJumperSize / 2;
650
651 emit setMaximumProgress(m_maxCycles);
652 emit setProgressMessage("");
653 emit setCycleMessage("round 1 of:");
654 emit setCycleCount(m_maxCycles);
655
656 m_sketchWidget->ensureTraceLayersVisible();
657
658 QHash<ConnectorItem *, int> indexer;
659 m_sketchWidget->collectAllNets(indexer, m_allPartConnectorItems, false, m_bothSidesNow);
660
661 removeOffBoardAnd(m_pcbType, true, m_bothSidesNow);
662
663 if (m_allPartConnectorItems.count() == 0) {
664 QString message = m_pcbType ? QObject::tr("No connections (on the PCB) to route.") : QObject::tr("No connections to route.");
665 QMessageBox::information(NULL, QObject::tr("Fritzing"), message);
666 Autorouter::cleanUpNets();
667 return;
668 }
669
670 QUndoCommand * parentCommand = new QUndoCommand("Autoroute");
671 new CleanUpWiresCommand(m_sketchWidget, CleanUpWiresCommand::UndoOnly, parentCommand);
672 new CleanUpRatsnestsCommand(m_sketchWidget, CleanUpWiresCommand::UndoOnly, parentCommand);
673
674 initUndo(parentCommand);
675
676 NetList netList;
677 int totalToRoute = 0;
678 for (int i = 0; i < m_allPartConnectorItems.count(); i++) {
679 Net * net = new Net;
680 net->net = m_allPartConnectorItems[i];
681
682 //foreach (ConnectorItem * connectorItem, *(net->net)) {
683 // connectorItem->debugInfo("all parts");
684 //}
685
686 QList<ConnectorItem *> todo;
687 todo.append(*(net->net));
688 while (todo.count() > 0) {
689 ConnectorItem * first = todo.takeFirst();
690 QList<ConnectorItem *> equi;
691 equi.append(first);
692 ConnectorItem::collectEqualPotential(equi, m_bothSidesNow, (ViewGeometry::RatsnestFlag | ViewGeometry::NormalFlag | ViewGeometry::PCBTraceFlag | ViewGeometry::SchematicTraceFlag) ^ m_sketchWidget->getTraceFlag());
693 foreach (ConnectorItem * equ, equi) {
694 todo.removeOne(equ);
695 //equ->debugInfo("equi");
696 }
697 net->subnets.append(equi);
698 }
699
700 if (net->subnets.count() < 2) {
701 // net is already routed
702 continue;
703 }
704
705 net->pinsWithin = findPinsWithin(net->net);
706 netList.nets << net;
707 totalToRoute += net->net->count() - 1;
708 }
709
710 qSort(netList.nets.begin(), netList.nets.end(), byPinsWithin);
711 NetOrdering initialOrdering;
712 int ix = 0;
713 foreach (Net * net, netList.nets) {
714 // id is the same as the order in netList
715 initialOrdering.order << ix;
716 net->id = ix++;
717 }
718
719 if (m_bothSidesNow) {
720 emit wantBothVisible();
721 }
722
723 ProcessEventBlocker::processEvents(); // to keep the app from freezing
724 if (m_cancelled || m_stopTracing) {
725 restoreOriginalState(parentCommand);
726 cleanUpNets(netList);
727 return;
728 }
729
730 QSizeF gridSize(m_maxRect.width() / m_gridPixels, m_maxRect.height() / m_gridPixels);
731 QSize boardImageSize(qCeil(gridSize.width()), qCeil(gridSize.height()));
732 m_grid = new Grid(boardImageSize.width(), boardImageSize.height(), m_bothSidesNow ? 2 : 1);
733 if (m_grid->data == NULL) {
734 QMessageBox::information(NULL, QObject::tr("Fritzing"), "Out of memory--unable to proceed");
735 restoreOriginalState(parentCommand);
736 cleanUpNets(netList);
737 return;
738 }
739
740 m_boardImage = new QImage(boardImageSize.width() * 4, boardImageSize.height() * 4, QImage::Format_Mono);
741 m_spareImage = new QImage(boardImageSize.width() * 4, boardImageSize.height() * 4, QImage::Format_Mono);
742 if (m_temporaryBoard) {
743 m_boardImage->fill(0xffffffff);
744 }
745 else {
746 m_boardImage->fill(0);
747 QRectF r4(QPointF(0, 0), gridSize * 4);
748 makeBoard(m_boardImage, m_keepoutGrid * 4, r4);
749 }
750 GraphicsUtils::drawBorder(m_boardImage, 4);
751
752 ProcessEventBlocker::processEvents(); // to keep the app from freezing
753 if (m_cancelled || m_stopTracing) {
754 restoreOriginalState(parentCommand);
755 cleanUpNets(netList);
756 return;
757 }
758
759 m_displayImage[0] = new QImage(boardImageSize, QImage::Format_ARGB32);
760 m_displayImage[0]->fill(0);
761 m_displayImage[1] = new QImage(boardImageSize, QImage::Format_ARGB32);
762 m_displayImage[1]->fill(0);
763
764 QString message;
765 bool gotMasters = makeMasters(message);
766 if (m_cancelled || m_stopTracing || !gotMasters) {
767 restoreOriginalState(parentCommand);
768 cleanUpNets(netList);
769 return;
770 }
771
772 QList<NetOrdering> allOrderings;
773 allOrderings << initialOrdering;
774 Score bestScore;
775 Score currentScore;
776 int run = 0;
777 for (; run < m_maxCycles && run < allOrderings.count(); run++) {
778 QString msg= tr("best so far: %1 of %2 routed").arg(bestScore.totalRoutedCount).arg(totalToRoute);
779 if (m_pcbType) {
780 msg += tr(" with %n vias", "", bestScore.totalViaCount);
781 }
782 emit setProgressMessage(msg);
783 emit setCycleMessage(tr("round %1 of:").arg(run + 1));
784 emit setProgressValue(run);
785 ProcessEventBlocker::processEvents();
786 currentScore.setOrdering(allOrderings.at(run));
787 currentScore.anyUnrouted = false;
788 routeNets(netList, false, currentScore, gridSize, allOrderings);
789 if (bestScore.ordering.order.count() == 0) {
790 bestScore = currentScore;
791 }
792 else {
793 if (currentScore.totalRoutedCount > bestScore.totalRoutedCount) {
794 bestScore = currentScore;
795 }
796 else if (currentScore.totalRoutedCount == bestScore.totalRoutedCount && currentScore.totalViaCount < bestScore.totalViaCount) {
797 bestScore = currentScore;
798 }
799 }
800 if (m_cancelled || bestScore.anyUnrouted == false || m_stopTracing) break;
801 }
802
803 emit disableButtons();
804
805 //DebugDialog::debug("done running");
806
807
808 if (m_cancelled) {
809 doCancel(parentCommand);
810 return;
811 }
812
813 if (m_stopTracing) {
814 QString msg = tr("Routing stopped!");
815 msg += " ";
816 if (m_useBest) msg += tr("Use best so far...");
817 emit setProgressMessage(msg);
818 if (m_useBest) {
819 routeNets(netList, true, bestScore, gridSize, allOrderings);
820 }
821 }
822 else if (!bestScore.anyUnrouted) {
823 emit setProgressMessage(tr("Routing complete!"));
824 emit setProgressValue(m_maxCycles);
825 }
826 else {
827 emit setCycleMessage(tr("round %1 of:").arg(run));
828 QString msg;
829 if (run < m_maxCycles) msg = tr("Routing unsuccessful; stopping at round %1.").arg(run);
830 else msg = tr("Routing reached maximum round %1.").arg(m_maxCycles);
831 msg += " ";
832 msg += tr("Use best so far...");
833 emit setProgressMessage(msg);
834 printOrder("best ", bestScore.ordering.order);
835 routeNets(netList, true, bestScore, gridSize, allOrderings);
836 emit setProgressValue(m_maxCycles);
837 }
838 ProcessEventBlocker::processEvents();
839
840 if (m_grid) {
841 m_grid->free();
842 delete m_grid;
843 m_grid = NULL;
844 }
845 if (m_boardImage) {
846 delete m_boardImage;
847 m_boardImage = NULL;
848 }
849 if (m_spareImage) {
850 delete m_spareImage;
851 m_spareImage = NULL;
852 }
853
854 m_boardImage = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);
855 m_spareImage = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);
856 m_spareImage2 = new QImage(m_maxRect.width() * OptimizeFactor, m_maxRect.height() * OptimizeFactor, QImage::Format_Mono);
857
858 if (m_temporaryBoard) {
859 m_boardImage->fill(0xffffffff);
860 }
861 else {
862 m_boardImage->fill(0);
863 QRectF r2(0, 0, m_boardImage->width(), m_boardImage->height());
864 makeBoard(m_boardImage, m_keepoutPixels * 2, r2);
865 }
866 GraphicsUtils::drawBorder(m_boardImage, 2);
867
868 createTraces(netList, bestScore, parentCommand);
869
870 cleanUpNets(netList);
871 new CleanUpRatsnestsCommand(m_sketchWidget, CleanUpWiresCommand::RedoOnly, parentCommand);
872 new CleanUpWiresCommand(m_sketchWidget, CleanUpWiresCommand::RedoOnly, parentCommand);
873
874 m_sketchWidget->blockUI(true);
875 m_commandCount = BaseCommand::totalChildCount(parentCommand);
876 emit setMaximumProgress(m_commandCount);
877 emit setProgressMessage2(tr("Preparing undo..."));
878 if (m_displayItem[0]) {
879 m_displayItem[0]->setVisible(false);
880 }
881 if (m_displayItem[1]) {
882 m_displayItem[1]->setVisible(false);
883 }
884 ProcessEventBlocker::processEvents();
885 m_cleanupCount = 0;
886 m_sketchWidget->pushCommand(parentCommand, this);
887 m_sketchWidget->blockUI(false);
888 m_sketchWidget->repaint();
889 DebugDialog::debug("\n\n\nautorouting complete\n\n\n");
890
891 }
892
findPinsWithin(QList<ConnectorItem * > * net)893 int MazeRouter::findPinsWithin(QList<ConnectorItem *> * net) {
894 int count = 0;
895 QRectF r;
896 foreach (ConnectorItem * connectorItem, *net) {
897 r |= connectorItem->sceneBoundingRect();
898 }
899
900 foreach (QGraphicsItem * item, m_sketchWidget->scene()->items(r)) {
901 ConnectorItem * connectorItem = dynamic_cast<ConnectorItem *>(item);
902 if (connectorItem == NULL) continue;
903
904 if (net->contains(connectorItem)) continue;
905
906 count++;
907 }
908
909 return count;
910 }
911
makeBoard(QImage * boardImage,double keepoutGrid,const QRectF & renderRect)912 bool MazeRouter::makeBoard(QImage * boardImage, double keepoutGrid, const QRectF & renderRect) {
913 LayerList viewLayerIDs;
914 viewLayerIDs << ViewLayer::Board;
915 RenderThing renderThing;
916 renderThing.printerScale = GraphicsUtils::SVGDPI;
917 renderThing.blackOnly = true;
918 renderThing.dpi = GraphicsUtils::StandardFritzingDPI;
919 renderThing.hideTerminalPoints = true;
920 renderThing.selectedItems = renderThing.renderBlocker = false;
921 QString boardSvg = m_sketchWidget->renderToSVG(renderThing, m_board, viewLayerIDs);
922 if (boardSvg.isEmpty()) {
923 return false;
924 }
925
926 QByteArray boardByteArray;
927 QString tempColor("#ffffff");
928 QStringList exceptions;
929 exceptions << "none" << "";
930 if (!SvgFileSplitter::changeColors(boardSvg, tempColor, exceptions, boardByteArray)) {
931 return false;
932 }
933
934 QSvgRenderer renderer(boardByteArray);
935 QPainter painter;
936 painter.begin(boardImage);
937 painter.setRenderHint(QPainter::Antialiasing, false);
938 renderer.render(&painter, renderRect);
939 painter.end();
940
941 // board should be white, borders should be black
942
943 #ifndef QT_NO_DEBUG
944 //boardImage->save(FolderUtils::getUserDataStorePath("") + "/mazeMakeBoard.png");
945 #endif
946
947 // extend it given that the board image is * 4
948 DRC::extendBorder(keepoutGrid, boardImage);
949
950 #ifndef QT_NO_DEBUG
951 //boardImage->save(FolderUtils::getUserDataStorePath("") + "/mazeMakeBoard2.png");
952 #endif
953
954 return true;
955 }
956
makeMasters(QString & message)957 bool MazeRouter::makeMasters(QString & message) {
958 QList<ViewLayer::ViewLayerPlacement> layerSpecs;
959 layerSpecs << ViewLayer::NewBottom;
960 if (m_bothSidesNow) layerSpecs << ViewLayer::NewTop;
961
962 foreach (ViewLayer::ViewLayerPlacement viewLayerPlacement, layerSpecs) {
963 LayerList viewLayerIDs = m_sketchWidget->routingLayers(viewLayerPlacement);
964 RenderThing renderThing;
965 renderThing.printerScale = GraphicsUtils::SVGDPI;
966 renderThing.blackOnly = true;
967 renderThing.dpi = GraphicsUtils::StandardFritzingDPI;
968 renderThing.hideTerminalPoints = renderThing.selectedItems = renderThing.renderBlocker = false;
969 QString master = m_sketchWidget->renderToSVG(renderThing, m_board, viewLayerIDs);
970 if (master.isEmpty()) {
971 continue;
972 }
973
974 QDomDocument * masterDoc = new QDomDocument();
975 m_masterDocs.insert(viewLayerPlacement, masterDoc);
976
977 QString errorStr;
978 int errorLine;
979 int errorColumn;
980 if (!masterDoc->setContent(master, &errorStr, &errorLine, &errorColumn)) {
981 message = tr("Unexpected SVG rendering failure--contact fritzing.org");
982 return false;
983 }
984
985 ProcessEventBlocker::processEvents();
986 if (m_cancelled) {
987 message = CancelledMessage;
988 return false;
989 }
990
991 QDomElement root = masterDoc->documentElement();
992 SvgFileSplitter::forceStrokeWidth(root, 2 * m_keepoutMils, "#000000", true, true);
993 //QString forDebugging = masterDoc->toByteArray();
994 //DebugDialog::debug("master " + forDebugging);
995 }
996
997 return true;
998 }
999
routeNets(NetList & netList,bool makeJumper,Score & currentScore,const QSizeF gridSize,QList<NetOrdering> & allOrderings)1000 bool MazeRouter::routeNets(NetList & netList, bool makeJumper, Score & currentScore, const QSizeF gridSize, QList<NetOrdering> & allOrderings)
1001 {
1002 RouteThing routeThing;
1003 routeThing.netElements[0] = NetElements();
1004 routeThing.netElements[1] = NetElements();
1005 routeThing.r = QRectF(QPointF(0, 0), gridSize);
1006 routeThing.r4 = QRectF(QPointF(0, 0), gridSize * 4);
1007 routeThing.layerSpecs << ViewLayer::NewBottom;
1008 if (m_bothSidesNow) routeThing.layerSpecs << ViewLayer::NewTop;
1009
1010 bool result = true;
1011
1012 initTraceDisplay();
1013 bool previousTraces = false;
1014 foreach (int netIndex, currentScore.ordering.order) {
1015 if (m_cancelled || m_stopTracing) {
1016 return false;
1017 }
1018
1019 Net * net = netList.nets.at(netIndex);
1020 /*
1021 DebugDialog::debug(QString("routing net %1, subnets %2, traces %3, routed %4")
1022 .arg(netIndex)
1023 .arg(net->subnets.count())
1024 .arg(currentScore.traces.values(netIndex).count())
1025 .arg(currentScore.routedCount.value(netIndex))
1026 );
1027 */
1028
1029 if (currentScore.routedCount.value(netIndex) == net->subnets.count() - 1) {
1030 // this net was fully routed in a previous run
1031 foreach (Trace trace, currentScore.traces.values(netIndex)) {
1032 displayTrace(trace);
1033 }
1034 previousTraces = true;
1035 continue;
1036 }
1037
1038 if (previousTraces) {
1039 updateDisplay(0);
1040 if (m_bothSidesNow) updateDisplay(1);
1041 }
1042
1043 if (currentScore.routedCount.value(netIndex) > 0) {
1044 // should only be here when makeJumpers = true
1045 // remove the set of routed traces for this net--the net was not completely routed
1046 // we didn't get all the way through before
1047 currentScore.totalRoutedCount -= currentScore.routedCount.value(netIndex);
1048 currentScore.routedCount.insert(netIndex, 0);
1049 currentScore.totalViaCount -= currentScore.viaCount.value(netIndex);
1050 currentScore.viaCount.insert(netIndex, 0);
1051 currentScore.traces.remove(netIndex);
1052 }
1053
1054 //foreach (ConnectorItem * connectorItem, *(net->net)) {
1055 // if (connectorItem->attachedTo()->layerKinChief()->id() == 12407630) {
1056 // connectorItem->debugInfo("what");
1057 // break;
1058 // }
1059 //}
1060
1061 QList< QList<ConnectorItem *> > subnets;
1062 foreach (QList<ConnectorItem *> subnet, net->subnets) {
1063 QList<ConnectorItem *> copy(subnet);
1064 subnets.append(copy);
1065 }
1066
1067 //DebugDialog::debug("find nearest pair");
1068
1069 findNearestPair(subnets, routeThing.nearest);
1070 QPointF ip = routeThing.nearest.ic->sceneAdjustedTerminalPoint(NULL) - m_maxRect.topLeft();
1071 routeThing.gridSourcePoint = QPoint(ip.x() / m_gridPixels, ip.y() / m_gridPixels);
1072 QPointF jp = routeThing.nearest.jc->sceneAdjustedTerminalPoint(NULL) - m_maxRect.topLeft();
1073 routeThing.gridTargetPoint = QPoint(jp.x() / m_gridPixels, jp.y() / m_gridPixels);
1074
1075 m_grid->clear();
1076 m_grid->init4(0, 0, 0, m_grid->x, m_grid->y, m_boardImage, GridBoardObstacle, false);
1077 if (m_bothSidesNow) {
1078 m_grid->copy(0, 1);
1079 }
1080
1081 QList<Trace> traces = currentScore.traces.values();
1082 if (m_pcbType) {
1083 traceObstacles(traces, netIndex, m_grid, m_keepoutGridInt);
1084 }
1085 else {
1086 traceAvoids(traces, netIndex, routeThing);
1087 }
1088
1089 foreach (ViewLayer::ViewLayerPlacement viewLayerPlacement, routeThing.layerSpecs) {
1090 int z = viewLayerPlacement == ViewLayer::NewBottom ? 0 : 1;
1091
1092 QDomDocument * masterDoc = m_masterDocs.value(viewLayerPlacement);
1093
1094 //QString before = masterDoc->toString();
1095
1096 Markers markers;
1097 initMarkers(markers, m_pcbType);
1098 DRC::splitNetPrep(masterDoc, *(net->net), markers, routeThing.netElements[z].net, routeThing.netElements[z].alsoNet, routeThing.netElements[z].notNet, true);
1099 foreach (QDomElement element, routeThing.netElements[z].net) {
1100 element.setTagName("g");
1101 }
1102 foreach (QDomElement element, routeThing.netElements[z].alsoNet) {
1103 element.setTagName("g");
1104 }
1105
1106 //QString after = masterDoc->toString();
1107
1108 //DebugDialog::debug("obstacles from board");
1109 m_spareImage->fill(0xffffffff);
1110 ItemBase::renderOne(masterDoc, m_spareImage, routeThing.r4);
1111 #ifndef QT_NO_DEBUG
1112 //m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/obstacles%1_%2.png").arg(netIndex, 2, 10, QChar('0')).arg(viewLayerPlacement));
1113 #endif
1114 m_grid->init4(0, 0, z, m_grid->x, m_grid->y, m_spareImage, GridPartObstacle, false);
1115 //DebugDialog::debug("obstacles from board done");
1116
1117 prepSourceAndTarget(masterDoc, routeThing, subnets, z, viewLayerPlacement);
1118 }
1119
1120 //updateDisplay(m_grid, 0);
1121 //if (m_bothSidesNow) updateDisplay(m_grid, 1);
1122
1123 //DebugDialog::debug(QString("before route one %1").arg(netIndex));
1124 routeThing.unrouted = false;
1125 if (!routeOne(makeJumper, currentScore, netIndex, routeThing, allOrderings)) {
1126 result = false;
1127 }
1128 //DebugDialog::debug(QString("after route one %1 %2").arg(netIndex).arg(result));
1129
1130 while (result && subnets.count() > 2) {
1131
1132 /*
1133 DebugDialog::debug(QString("\nnearest %1 %2").arg(routeThing.nearest.i).arg(routeThing.nearest.j));
1134 routeThing.nearest.ic->debugInfo("\ti");
1135 routeThing.nearest.jc->debugInfo("\tj");
1136
1137 int ix = 0;
1138 foreach (QList<ConnectorItem *> subnet, subnets) {
1139 foreach(ConnectorItem * connectorItem, subnet) {
1140 connectorItem->debugInfo(QString::number(ix));
1141 }
1142 ix++;
1143 }
1144 */
1145
1146 result = routeNext(makeJumper, routeThing, subnets, currentScore, netIndex, allOrderings);
1147 }
1148
1149 routeThing.netElements[0].net.clear();
1150 routeThing.netElements[0].notNet.clear();
1151 routeThing.netElements[0].alsoNet.clear();
1152 routeThing.netElements[1].net.clear();
1153 routeThing.netElements[1].notNet.clear();
1154 routeThing.netElements[1].alsoNet.clear();
1155 routeThing.sourceQ = std::priority_queue<GridPoint>();
1156 routeThing.targetQ = std::priority_queue<GridPoint>();
1157
1158 if (result == false) break;
1159 }
1160
1161 return result;
1162 }
1163
routeOne(bool makeJumper,Score & currentScore,int netIndex,RouteThing & routeThing,QList<NetOrdering> & allOrderings)1164 bool MazeRouter::routeOne(bool makeJumper, Score & currentScore, int netIndex, RouteThing & routeThing, QList<NetOrdering> & allOrderings) {
1165
1166 //DebugDialog::debug("start route()");
1167 Trace newTrace;
1168 int viaCount;
1169 routeThing.bestDistanceToSource = routeThing.bestDistanceToTarget = std::numeric_limits<double>::max();
1170 //DebugDialog::debug(QString("jumper d %1, %2").arg(routeThing.bestDistanceToSource).arg(routeThing.bestDistanceToTarget));
1171
1172 newTrace.gridPoints = route(routeThing, viaCount);
1173 if (m_cancelled || m_stopTracing) {
1174 return false;
1175 }
1176
1177 //DebugDialog::debug("after route()");
1178
1179
1180 if (newTrace.gridPoints.count() == 0) {
1181 if (makeJumper) {
1182 routeJumper(netIndex, routeThing, currentScore);
1183 }
1184 else {
1185 routeThing.unrouted = true;
1186 if (currentScore.reorderNet < 0) {
1187 for (int i = 0; i < currentScore.ordering.order.count(); i++) {
1188 if (currentScore.ordering.order.at(i) == netIndex) {
1189 if (moveBack(currentScore, i, allOrderings)) {
1190 currentScore.reorderNet = netIndex;
1191 }
1192 break;
1193 }
1194 }
1195 }
1196
1197 currentScore.anyUnrouted = true;
1198 if (currentScore.reorderNet >= 0) {
1199 // rip up and reroute unless this net is already the first one on the list
1200 return false;
1201 }
1202 // unable to move the 0th net so keep going
1203 }
1204 }
1205 else {
1206 insertTrace(newTrace, netIndex, currentScore, viaCount, true);
1207 updateDisplay(0);
1208 if (m_bothSidesNow) updateDisplay(1);
1209 }
1210
1211 //DebugDialog::debug("end routeOne()");
1212
1213
1214 return true;
1215 }
1216
routeNext(bool makeJumper,RouteThing & routeThing,QList<QList<ConnectorItem * >> & subnets,Score & currentScore,int netIndex,QList<NetOrdering> & allOrderings)1217 bool MazeRouter::routeNext(bool makeJumper, RouteThing & routeThing, QList< QList<ConnectorItem *> > & subnets, Score & currentScore, int netIndex, QList<NetOrdering> & allOrderings)
1218 {
1219 bool result = true;
1220
1221 QList<ConnectorItem *> combined;
1222 if (routeThing.unrouted) {
1223 if (routeThing.nearest.i < routeThing.nearest.j) {
1224 subnets.removeAt(routeThing.nearest.j);
1225 combined = subnets.takeAt(routeThing.nearest.i);
1226 }
1227 else {
1228 combined = subnets.takeAt(routeThing.nearest.i);
1229 subnets.removeAt(routeThing.nearest.j);
1230 }
1231 }
1232 else {
1233 combined.append(subnets.at(routeThing.nearest.i));
1234 combined.append(subnets.at(routeThing.nearest.j));
1235 if (routeThing.nearest.i < routeThing.nearest.j) {
1236 subnets.removeAt(routeThing.nearest.j);
1237 subnets.removeAt(routeThing.nearest.i);
1238 }
1239 else {
1240 subnets.removeAt(routeThing.nearest.i);
1241 subnets.removeAt(routeThing.nearest.j);
1242 }
1243 }
1244 subnets.prepend(combined);
1245 routeThing.nearest.i = 0;
1246 routeThing.nearest.j = -1;
1247 routeThing.nearest.distance = std::numeric_limits<double>::max();
1248 findNearestPair(subnets, 0, combined, routeThing.nearest);
1249 QPointF ip = routeThing.nearest.ic->sceneAdjustedTerminalPoint(NULL) - m_maxRect.topLeft();
1250 routeThing.gridSourcePoint = QPoint(ip.x() / m_gridPixels, ip.y() / m_gridPixels);
1251 QPointF jp = routeThing.nearest.jc->sceneAdjustedTerminalPoint(NULL) - m_maxRect.topLeft();
1252 routeThing.gridTargetPoint = QPoint(jp.x() / m_gridPixels, jp.y() / m_gridPixels);
1253
1254 routeThing.sourceQ = std::priority_queue<GridPoint>();
1255 routeThing.targetQ = std::priority_queue<GridPoint>();
1256
1257 if (!m_pcbType) {
1258 QList<Trace> traces = currentScore.traces.values();
1259 traceAvoids(traces, netIndex, routeThing);
1260 }
1261
1262 foreach (ViewLayer::ViewLayerPlacement viewLayerPlacement, routeThing.layerSpecs) {
1263 int z = viewLayerPlacement == ViewLayer::NewBottom ? 0 : 1;
1264 QDomDocument * masterDoc = m_masterDocs.value(viewLayerPlacement);
1265 prepSourceAndTarget(masterDoc, routeThing, subnets, z, viewLayerPlacement);
1266 }
1267
1268 // redraw traces from this net
1269 foreach (Trace trace, currentScore.traces.values(netIndex)) {
1270 foreach (GridPoint gridPoint, trace.gridPoints) {
1271 m_grid->setAt(gridPoint.x, gridPoint.y, gridPoint.z, GridSource);
1272 gridPoint.qCost = gridPoint.baseCost = /* initialCost(QPoint(gridPoint.x, gridPoint.y), routeThing.gridTarget) + */ 0;
1273 gridPoint.flags = 0;
1274 //DebugDialog::debug(QString("pushing trace %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
1275 routeThing.sourceQ.push(gridPoint);
1276 }
1277 }
1278
1279 //updateDisplay(m_grid, 0);
1280 //if (m_bothSidesNow) updateDisplay(m_grid, 1);
1281
1282 routeThing.unrouted = false;
1283 result = routeOne(makeJumper, currentScore, netIndex, routeThing, allOrderings);
1284
1285 return result;
1286 }
1287
moveBack(Score & currentScore,int index,QList<NetOrdering> & allOrderings)1288 bool MazeRouter::moveBack(Score & currentScore, int index, QList<NetOrdering> & allOrderings) {
1289 if (index == 0) {
1290 return false; // nowhere to move back to
1291 }
1292
1293 QList<int> order(currentScore.ordering.order);
1294 //printOrder("start", order);
1295 int netIndex = order.takeAt(index);
1296 //printOrder("minus", order);
1297 for (int i = index - 1; i >= 0; i--) {
1298 bool done = true;
1299 order.insert(i, netIndex);
1300 //printOrder("plus ", order);
1301 foreach (NetOrdering ordering, allOrderings) {
1302 bool gotOne = true;
1303 for (int j = 0; j < order.count(); j++) {
1304 if (order.at(j) != ordering.order.at(j)) {
1305 gotOne = false;
1306 break;
1307 }
1308 }
1309 if (gotOne) {
1310 done = false;
1311 break;
1312 }
1313 }
1314 if (done == true) {
1315 NetOrdering newOrdering;
1316 newOrdering.order = order;
1317 allOrderings.append(newOrdering);
1318 //printOrder("done ", newOrdering.order);
1319
1320 /*
1321 const static int watch[] = { 0, 1, 2, 3, 6, 12, 14, 4, 5, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64 };
1322 // {0, 1, 2, 4, 3, 12, 6, 14, 5, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64};
1323
1324 bool matches = true;
1325 for (int i = 0; i < order.count(); i++) {
1326 if (order.at(i) != watch[i]) {
1327 matches = false;
1328 break;
1329 }
1330 }
1331 if (matches) {
1332 DebugDialog::debug("order matches");
1333 }
1334 */
1335 return true;
1336 }
1337 order.removeAt(i);
1338 }
1339
1340 return false;
1341 }
1342
prepSourceAndTarget(QDomDocument * masterDoc,RouteThing & routeThing,QList<QList<ConnectorItem * >> & subnets,int z,ViewLayer::ViewLayerPlacement viewLayerPlacement)1343 void MazeRouter::prepSourceAndTarget(QDomDocument * masterDoc, RouteThing & routeThing, QList< QList<ConnectorItem *> > & subnets, int z, ViewLayer::ViewLayerPlacement viewLayerPlacement)
1344 {
1345 foreach (QDomElement element, routeThing.netElements[z].notNet) {
1346 element.setTagName("g");
1347 }
1348 foreach (QDomElement element, routeThing.netElements[z].alsoNet) {
1349 element.setTagName("g");
1350 }
1351
1352 //QString debug = masterDoc->toString(4);
1353
1354 foreach (QDomElement element, routeThing.netElements[z].net) {
1355 // QString str;
1356 // QTextStream stream(&str);
1357 // element.save(stream, 0);
1358 // DebugDialog::debug(str);
1359 SvgFileSplitter::forceStrokeWidth(element, -2 * m_keepoutMils, "#000000", false, false);
1360 }
1361
1362 QList<ConnectorItem *> li = subnets.at(routeThing.nearest.i);
1363 QList<QPoint> sourcePoints = renderSource(masterDoc, z, viewLayerPlacement, m_grid, routeThing.netElements[z].net, li, GridSource, true, routeThing.r4);
1364
1365 foreach (QPoint p, sourcePoints) {
1366 GridPoint gridPoint(p, z);
1367 gridPoint.qCost = gridPoint.baseCost = /* initialCost(p, routeThing.gridTarget) + */ 0;
1368 //DebugDialog::debug(QString("pushing source %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
1369 routeThing.sourceQ.push(gridPoint);
1370 }
1371
1372 QList<ConnectorItem *> lj = subnets.at(routeThing.nearest.j);
1373 QList<QPoint> targetPoints = renderSource(masterDoc, z, viewLayerPlacement, m_grid, routeThing.netElements[z].net, lj, GridTarget, true, routeThing.r4);
1374 foreach (QPoint p, targetPoints) {
1375 GridPoint gridPoint(p, z);
1376 gridPoint.qCost = gridPoint.baseCost = /* initialCost(p, routeThing.gridTarget) + */ 0;
1377 //DebugDialog::debug(QString("pushing source %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
1378 routeThing.targetQ.push(gridPoint);
1379 }
1380
1381 foreach (QDomElement element, routeThing.netElements[z].net) {
1382 SvgFileSplitter::forceStrokeWidth(element, 2 * m_keepoutMils, "#000000", false, false);
1383 }
1384
1385 // restore masterdoc
1386 foreach (QDomElement element, routeThing.netElements[z].net) {
1387 element.setTagName(element.attribute("former"));
1388 element.removeAttribute("net");
1389 }
1390 foreach (QDomElement element, routeThing.netElements[z].notNet) {
1391 element.setTagName(element.attribute("former"));
1392 element.removeAttribute("net");
1393 }
1394 foreach (QDomElement element, routeThing.netElements[z].alsoNet) {
1395 element.setTagName(element.attribute("former"));
1396 element.removeAttribute("net");
1397 }
1398 }
1399
findNearestPair(QList<QList<ConnectorItem * >> & subnets,Nearest & nearest)1400 void MazeRouter::findNearestPair(QList< QList<ConnectorItem *> > & subnets, Nearest & nearest) {
1401 nearest.distance = std::numeric_limits<double>::max();
1402 nearest.i = nearest.j = -1;
1403 nearest.ic = nearest.jc = NULL;
1404 for (int i = 0; i < subnets.count() - 1; i++) {
1405 QList<ConnectorItem *> inet = subnets.at(i);
1406 findNearestPair(subnets, i, inet, nearest);
1407 }
1408 }
1409
findNearestPair(QList<QList<ConnectorItem * >> & subnets,int inetix,QList<ConnectorItem * > & inet,Nearest & nearest)1410 void MazeRouter::findNearestPair(QList< QList<ConnectorItem *> > & subnets, int inetix, QList<ConnectorItem *> & inet, Nearest & nearest) {
1411 for (int j = inetix + 1; j < subnets.count(); j++) {
1412 QList<ConnectorItem *> jnet = subnets.at(j);
1413 foreach (ConnectorItem * ic, inet) {
1414 QPointF ip = ic->sceneAdjustedTerminalPoint(NULL);
1415 ConnectorItem * icc = ic->getCrossLayerConnectorItem();
1416 foreach (ConnectorItem * jc, jnet) {
1417 ConnectorItem * jcc = jc->getCrossLayerConnectorItem();
1418 if (jc == ic || jcc == ic) continue;
1419
1420 QPointF jp = jc->sceneAdjustedTerminalPoint(NULL);
1421 double d = qSqrt(GraphicsUtils::distanceSqd(ip, jp)) / m_gridPixels;
1422 if (ic->attachedToViewLayerID() != jc->attachedToViewLayerID()) {
1423 if (jcc != NULL || icc != NULL) {
1424 // may not need a via
1425 d += CrossLayerCost;
1426 }
1427 else {
1428 // requires at least one via
1429 d += ViaCost;
1430 }
1431 }
1432 else {
1433 if (jcc != NULL && icc != NULL && ic->attachedToViewLayerID() == ViewLayer::Copper1) {
1434 // route on the bottom when possible
1435 d += Layer1Cost;
1436 }
1437 }
1438 if (d < nearest.distance) {
1439 nearest.distance = d;
1440 nearest.i = inetix;
1441 nearest.j = j;
1442 nearest.ic = ic;
1443 nearest.jc = jc;
1444 }
1445 }
1446 }
1447 }
1448 }
1449
renderSource(QDomDocument * masterDoc,int z,ViewLayer::ViewLayerPlacement viewLayerPlacement,Grid * grid,QList<QDomElement> & netElements,QList<ConnectorItem * > & subnet,GridValue value,bool clearElements,const QRectF & renderRect)1450 QList<QPoint> MazeRouter::renderSource(QDomDocument * masterDoc, int z, ViewLayer::ViewLayerPlacement viewLayerPlacement, Grid * grid, QList<QDomElement> & netElements, QList<ConnectorItem *> & subnet, GridValue value, bool clearElements, const QRectF & renderRect) {
1451 if (clearElements) {
1452 foreach (QDomElement element, netElements) {
1453 element.setTagName("g");
1454 }
1455 }
1456
1457 m_spareImage->fill(0xffffffff);
1458 QMultiHash<QString, QString> partIDs;
1459 QMultiHash<QString, QString> terminalIDs;
1460 QList<ConnectorItem *> terminalPoints;
1461 QRectF itemsBoundingRect;
1462 foreach (ConnectorItem * connectorItem, subnet) {
1463 ItemBase * itemBase = connectorItem->attachedTo();
1464 SvgIdLayer * svgIdLayer = connectorItem->connector()->fullPinInfo(itemBase->viewID(), itemBase->viewLayerID());
1465 partIDs.insert(QString::number(itemBase->id()), svgIdLayer->m_svgId);
1466 if (!svgIdLayer->m_terminalId.isEmpty()) {
1467 terminalIDs.insert(QString::number(itemBase->id()), svgIdLayer->m_terminalId);
1468 terminalPoints << connectorItem;
1469 }
1470 itemsBoundingRect |= connectorItem->sceneBoundingRect();
1471 }
1472 foreach (QDomElement element, netElements) {
1473 if (idsMatch(element, partIDs)) {
1474 element.setTagName(element.attribute("former"));
1475 }
1476 else if (idsMatch(element, terminalIDs)) {
1477 element.setTagName(element.attribute("former"));
1478 }
1479 }
1480
1481 int x1 = qFloor((itemsBoundingRect.left() - m_maxRect.left()) / m_gridPixels);
1482 int y1 = qFloor((itemsBoundingRect.top() - m_maxRect.top()) / m_gridPixels);
1483 int x2 = qCeil((itemsBoundingRect.right() - m_maxRect.left()) / m_gridPixels);
1484 int y2 = qCeil((itemsBoundingRect.bottom() - m_maxRect.top()) / m_gridPixels);
1485
1486 ItemBase::renderOne(masterDoc, m_spareImage, renderRect);
1487 #ifndef QT_NO_DEBUG
1488 //static int rsi = 0;
1489 //m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/rendersource%1_%2.png").arg(rsi++,3,10,QChar('0')).arg(z));
1490 #endif
1491 QList<QPoint> points = grid->init4(x1, y1, z, x2 - x1, y2 - y1, m_spareImage, value, true);
1492
1493
1494
1495 // terminal point hack (mostly for schematic view)
1496 foreach (ConnectorItem * connectorItem, terminalPoints) {
1497 if (ViewLayer::specFromID(connectorItem->attachedTo()->viewLayerID()) != viewLayerPlacement) {
1498 continue;
1499 }
1500
1501 QPointF p = connectorItem->sceneAdjustedTerminalPoint(NULL);
1502 QRectF r = connectorItem->attachedTo()->sceneBoundingRect().adjusted(-m_keepoutPixels, -m_keepoutPixels, m_keepoutPixels, m_keepoutPixels);
1503 QPointF closest(p.x(), r.top());
1504 double d = qAbs(p.y() - r.top());
1505 int dx = 0;
1506 int dy = -1;
1507 if (qAbs(p.y() - r.bottom()) < d) {
1508 d = qAbs(p.y() - r.bottom());
1509 closest = QPointF(p.x(), r.bottom());
1510 dy = 1;
1511 dx = 0;
1512 }
1513 if (qAbs(p.x() - r.left()) < d) {
1514 d = qAbs(p.x() - r.left());
1515 closest = QPointF(r.left(), p.y());
1516 dx = -1;
1517 dy = 0;
1518 }
1519 if (qAbs(p.x() - r.right()) < d) {
1520 d = qAbs(p.x() - r.right());
1521 closest = QPointF(r.right(), p.y());
1522 dy = 0;
1523 dx = 1;
1524 }
1525
1526 double y1, y2, x1, x2;
1527 double yp = (p.y() - m_maxRect.top()) / m_gridPixels;
1528 double xp = (p.x() - m_maxRect.left()) / m_gridPixels;
1529 double yc = (closest.y() - m_maxRect.top()) / m_gridPixels;
1530 double xc = (closest.x() - m_maxRect.left()) / m_gridPixels;
1531 if (closest.x() == p.x()) {
1532 x1 = x2 = qRound((p.x() - m_maxRect.left()) / m_gridPixels);
1533 y1 = (yp < yc) ? qFloor(yp) : qCeil(yp);
1534 y2 = (yp < yc) ? qCeil(yc) : qFloor(yc);
1535 if (y2 < y1) {
1536 double temp = y2;
1537 y2 = y1;
1538 y1 = temp;
1539 }
1540 }
1541 else {
1542 y1 = y2 = qRound((p.y() - m_maxRect.top()) / m_gridPixels);
1543 x1 = (xp < xc) ? qFloor(xp) : qCeil(xp);
1544 x2 = (xp < xc) ? qCeil(xc) : qFloor(xc);
1545 if (x2 < x1) {
1546 double temp = x2;
1547 x2 = x1;
1548 x1 = temp;
1549 }
1550 }
1551
1552 int xo = qRound(xc);
1553 int yo = qRound(yc);
1554 // remove obstacles we can draw through
1555 while (true) {
1556 xo += dx;
1557 yo += dy;
1558 if (grid->at(xo, yo, z) != GridAvoid) break;
1559
1560 grid->setAt(xo, yo, z, 0);
1561 }
1562
1563 for (int iy = y1; iy <= y2; iy++) {
1564 for (int ix = x1; ix <= x2; ix++) {
1565 GridValue val = grid->at(ix, iy, z);
1566 if (val == GridPartObstacle || val == GridAvoid) {
1567 // make an empty path up to the source point
1568 grid->setAt(ix, iy, z, 0);
1569 }
1570 }
1571 }
1572 int xr = qRound(xp);
1573 int yr = qRound(yp);
1574 if (grid->at(xr, yr, z) != GridBoardObstacle) {
1575 grid->setAt(xr, yr, z, value);
1576 points << QPoint(xr, yr);
1577 }
1578
1579 }
1580
1581 return points;
1582 }
1583
route(RouteThing & routeThing,int & viaCount)1584 QList<GridPoint> MazeRouter::route(RouteThing & routeThing, int & viaCount)
1585 {
1586 //DebugDialog::debug(QString("start route() %1").arg(routeNumber++));
1587 viaCount = 0;
1588 GridPoint done;
1589 bool result = false;
1590 while (!routeThing.sourceQ.empty() && !routeThing.targetQ.empty()) {
1591 GridPoint gp = routeThing.sourceQ.top();
1592 GridPoint gpt = routeThing.targetQ.top();
1593 if (gpt.qCost < gp.qCost) {
1594 gp = gpt;
1595 routeThing.targetQ.pop();
1596 routeThing.targetValue = GridSource;
1597 routeThing.sourceValue = GridTarget;
1598 }
1599 else {
1600 routeThing.sourceQ.pop();
1601 routeThing.targetValue = GridTarget;
1602 routeThing.sourceValue = GridSource;
1603 }
1604
1605 if (gp.flags & GridPointDone) {
1606 done = gp;
1607 result = true;
1608 break;
1609 }
1610
1611 expand(gp, routeThing);
1612 if (m_cancelled || m_stopTracing) {
1613 break;
1614 }
1615 }
1616
1617 //DebugDialog::debug(QString("routing result %1").arg(result));
1618
1619 QList<GridPoint> points;
1620 if (!result) {
1621 //updateDisplay(m_grid, 0);
1622 //DebugDialog::debug(QString("done routing no points"));
1623 return points;
1624 }
1625 done.baseCost = std::numeric_limits<GridValue>::max(); // make sure this is the largest value for either traceback
1626 QList<GridPoint> sourcePoints = traceBack(done, m_grid, viaCount, GridTarget, GridSource); // trace back to source
1627 QList<GridPoint> targetPoints = traceBack(done, m_grid, viaCount, GridSource, GridTarget); // trace back to target
1628 if (sourcePoints.count() == 0 || targetPoints.count() == 0) {
1629 DebugDialog::debug("traceback zero points");
1630 return points;
1631 }
1632 else {
1633 targetPoints.takeFirst(); // redundant point
1634 foreach (GridPoint gp, targetPoints) points.prepend(gp);
1635 points.append(sourcePoints);
1636 }
1637
1638 clearExpansion(m_grid);
1639
1640 //DebugDialog::debug(QString("done with route() %1").arg(points.count()));
1641
1642 return points;
1643 }
1644
traceBack(GridPoint gridPoint,Grid * grid,int & viaCount,GridValue sourceValue,GridValue targetValue)1645 QList<GridPoint> MazeRouter::traceBack(GridPoint gridPoint, Grid * grid, int & viaCount, GridValue sourceValue, GridValue targetValue) {
1646 //DebugDialog::debug(QString("traceback %1 %2 %3").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z));
1647 QList<GridPoint> points;
1648 points << gridPoint;
1649 while (true) {
1650 if (gridPoint.baseCost == targetValue) {
1651 // done
1652 break;
1653 }
1654
1655 // can only be one neighbor with lower value
1656 GridPoint next = traceBackOne(gridPoint, grid, -1, 0, 0, sourceValue, targetValue);
1657 if (next.baseCost == GridBoardObstacle) {
1658 next = traceBackOne(gridPoint, grid, 1, 0, 0, sourceValue, targetValue);
1659 if (next.baseCost == GridBoardObstacle) {
1660 next = traceBackOne(gridPoint, grid, 0, -1, 0, sourceValue, targetValue);
1661 if (next.baseCost == GridBoardObstacle) {
1662 next = traceBackOne(gridPoint, grid, 0, 1, 0, sourceValue, targetValue);
1663 if (next.baseCost == GridBoardObstacle) {
1664 next = traceBackOne(gridPoint, grid, 0, 0, -1, sourceValue, targetValue);
1665 if (next.baseCost == GridBoardObstacle) {
1666 next = traceBackOne(gridPoint, grid, 0, 0, 1, sourceValue, targetValue);
1667 if (next.baseCost == GridBoardObstacle) {
1668 // traceback failed--is this possible?
1669 points.clear();
1670 break;
1671 }
1672 }
1673 }
1674 }
1675 }
1676 }
1677
1678 //if (grid->at(next.x - 1, next.y, next.z) != GridObstacle) next.flags |= GridPointWest;
1679 //if (grid->at(next.x + 1, next.y, next.z) != GridObstacle) next.flags |= GridPointEast;
1680 //if (grid->at(next.x, next.y - 1, next.z) != GridObstacle) next.flags |= GridPointNorth;
1681 //if (grid->at(next.x, next.y + 1, next.z) != GridObstacle) next.flags |= GridPointSouth;
1682 points << next;
1683 if (next.z != gridPoint.z) viaCount++;
1684 gridPoint = next;
1685 }
1686
1687 /*
1688 QString costs("costs ");
1689 foreach (GridPoint gridPoint, points) {
1690 costs += QString::number(gridPoint.baseCost) + " ";
1691 }
1692 DebugDialog::debug(costs);
1693 */
1694
1695 return points;
1696 }
1697
traceBackOne(GridPoint & gridPoint,Grid * grid,int dx,int dy,int dz,GridValue sourceValue,GridValue targetValue)1698 GridPoint MazeRouter::traceBackOne(GridPoint & gridPoint, Grid * grid, int dx, int dy, int dz, GridValue sourceValue, GridValue targetValue) {
1699 GridPoint next;
1700 next.baseCost = GridBoardObstacle;
1701
1702 next.x = gridPoint.x + dx;
1703 if (next.x < 0 || next.x >= grid->x) {
1704 return next;
1705 }
1706
1707 next.y = gridPoint.y + dy;
1708 if (next.y < 0 || next.y >= grid->y) {
1709 return next;
1710 }
1711
1712 next.z = gridPoint.z + dz;
1713 if (next.z < 0 || next.z >= grid->z) {
1714 return next;
1715 }
1716
1717 GridValue nextval = grid->at(next.x, next.y, next.z);
1718 if (nextval == GridBoardObstacle || nextval == GridPartObstacle || nextval == sourceValue || nextval == 0 || nextval == GridTempObstacle) return next;
1719 if (nextval == targetValue) {
1720 // done!
1721 next.baseCost = targetValue;
1722 return next;
1723 }
1724
1725 if (targetValue == GridSource) {
1726 if ((nextval & GridSourceFlag) == 0) return next;
1727 nextval ^= GridSourceFlag;
1728 }
1729 else {
1730 if (nextval & GridSourceFlag) return next;
1731 }
1732
1733 if (nextval < gridPoint.baseCost) {
1734 next.baseCost = nextval;
1735 }
1736 return next;
1737 }
1738
expand(GridPoint & gridPoint,RouteThing & routeThing)1739 void MazeRouter::expand(GridPoint & gridPoint, RouteThing & routeThing)
1740 {
1741 //static bool debugit = false;
1742 //if (routeNumber > 41 && routeThing.pq.size() > 8200) debugit = true;
1743
1744 //if (debugit) {
1745 // DebugDialog::debug(QString("expand %1 %2 %3, %4").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(routeThing.pq.size()));
1746 //}
1747 if (gridPoint.x > 0) expandOne(gridPoint, routeThing, -1, 0, 0, false);
1748 if (gridPoint.x < m_grid->x - 1) expandOne(gridPoint, routeThing, 1, 0, 0, false);
1749 if (gridPoint.y > 0) expandOne(gridPoint, routeThing, 0, -1, 0, false);
1750 if (gridPoint.y < m_grid->y - 1) expandOne(gridPoint, routeThing, 0, 1, 0, false);
1751 if (m_bothSidesNow) {
1752 if (gridPoint.z > 0) expandOne(gridPoint, routeThing, 0, 0, -1, true);
1753 if (gridPoint.z < m_grid->z - 1) expandOne(gridPoint, routeThing, 0, 0, 1, true);
1754 }
1755 //if (debugit) {
1756 // DebugDialog::debug("expand done");
1757 //}
1758 }
1759
expandOne(GridPoint & gridPoint,RouteThing & routeThing,int dx,int dy,int dz,bool crossLayer)1760 void MazeRouter::expandOne(GridPoint & gridPoint, RouteThing & routeThing, int dx, int dy, int dz, bool crossLayer) {
1761 GridPoint next;
1762 next.x = gridPoint.x + dx;
1763 next.y = gridPoint.y + dy;
1764 next.z = gridPoint.z + dz;
1765
1766 //DebugDialog::debug(QString("expand one %1,%2,%3 cl:%4").arg(next.x).arg(next.y).arg(next.z).arg(crossLayer));
1767
1768 bool writeable = false;
1769 bool avoid = false;
1770 GridValue nextval = m_grid->at(next.x, next.y, next.z);
1771 if (nextval == GridPartObstacle || nextval == GridBoardObstacle || nextval == routeThing.sourceValue || nextval == GridTempObstacle) {
1772 //DebugDialog::debug("exit expand one");
1773 return;
1774 }
1775
1776 if (nextval == routeThing.targetValue) {
1777 //DebugDialog::debug("found grid target");
1778 next.flags |= GridPointDone;
1779 }
1780 else if (nextval == 0) {
1781 writeable = true;
1782 }
1783 else if (nextval == GridAvoid) {
1784 bool contains = true;
1785 for (int i = 1; i <= 3; i++) {
1786 if (!routeThing.avoids.contains(((next.y - (i * dy)) * m_grid->x) + next.x - (i * dx))) {
1787 contains = false;
1788 break;
1789 }
1790 }
1791
1792 if (contains) {
1793 // do not allow more than 3 in a row in the same direction?
1794 return;
1795 }
1796 avoid = writeable = true;
1797 if (dx == 0) {
1798 if (m_grid->at(next.x - 1, next.y, next.z) == GridAvoid) {
1799 m_grid->setAt(next.x - 1, next.y, next.z, GridTempObstacle);
1800 }
1801 if (m_grid->at(next.x + 1, next.y, next.z) == GridAvoid) {
1802 m_grid->setAt(next.x + 1, next.y, next.z, GridTempObstacle);
1803 }
1804 }
1805 else {
1806 if (m_grid->at(next.x, next.y - 1, next.z) == GridAvoid) {
1807 m_grid->setAt(next.x, next.y - 1, next.z, GridTempObstacle);
1808 }
1809 if (m_grid->at(next.x, next.y + 1, next.z) == GridAvoid) {
1810 m_grid->setAt(next.x, next.y + 1, next.z, GridTempObstacle);
1811 }
1812 }
1813 }
1814 else {
1815 // already been here: see if source and target expansions have intersected
1816 if (routeThing.sourceValue == GridSource) {
1817 if (nextval & GridSourceFlag) return;
1818
1819 next.flags |= GridPointDone;
1820 }
1821 else {
1822 if ((nextval & GridSourceFlag) == 0) return;
1823
1824 next.flags |= GridPointDone;
1825 }
1826 }
1827
1828 // any way to skip viaWillFit or put it off until actually needed?
1829 if (crossLayer) {
1830 if (!viaWillFit(next, m_grid)) return;
1831
1832 // only way to cross layers is with a via
1833 //QPointF center = getPixelCenter(next, m_maxRect.topLeft(), m_gridPixels);
1834 //DebugDialog::debug(QString("via will fit %1,%2,%3 %4,%5").arg(next.x).arg(next.y).arg(next.z).arg(center.x()).arg(center.y()));
1835 }
1836
1837 next.baseCost = gridPoint.baseCost;
1838 if (crossLayer) {
1839 next.baseCost += ViaCost;
1840 }
1841 else if (avoid) {
1842 next.baseCost += AvoidCost;
1843 }
1844 next.baseCost++;
1845
1846
1847 /*
1848 int increment = 5;
1849 // assume because of obstacles around the board that we can never be off grid from (next.x, next.y)
1850 switch(grid->at(next.x - 1, next.y, next.z)) {
1851 case GridObstacle:
1852 case GridSource:
1853 case GridTarget:
1854 increment--;
1855 default:
1856 break;
1857 }
1858 switch(grid->at(next.x + 1, next.y, next.z)) {
1859 case GridObstacle:
1860 case GridSource:
1861 case GridTarget:
1862 increment--;
1863 default:
1864 break;
1865 }
1866 switch(grid->at(next.x, next.y - 1, next.z)) {
1867 case GridObstacle:
1868 case GridSource:
1869 case GridTarget:
1870 increment--;
1871 default:
1872 break;
1873 }
1874 switch(grid->at(next.x, next.y + 1, next.z)) {
1875 case GridObstacle:
1876 case GridSource:
1877 case GridTarget:
1878 increment--;
1879 default:
1880 break;
1881 }
1882 next.cost += increment;
1883 */
1884
1885
1886 if (nextval == routeThing.targetValue) {
1887 next.qCost = next.baseCost;
1888 }
1889 else {
1890 double d = (m_costFunction)(QPoint(next.x, next.y), (routeThing.sourceValue == GridSource) ? routeThing.gridTargetPoint : routeThing.gridSourcePoint);
1891 next.qCost = next.baseCost + d;
1892 if (routeThing.sourceValue == GridSource) {
1893 if (d < routeThing.bestDistanceToTarget) {
1894 //DebugDialog::debug(QString("best d target %1, %2,%3").arg(d).arg(next.x).arg(next.y));
1895 routeThing.bestDistanceToTarget = d;
1896 routeThing.bestLocationToTarget = next;
1897 }
1898 }
1899 else {
1900 if (d < routeThing.bestDistanceToSource) {
1901 //DebugDialog::debug(QString("best d source %1, %2,%3").arg(d).arg(next.x).arg(next.y));
1902 routeThing.bestDistanceToSource = d;
1903 routeThing.bestLocationToSource = next;
1904 }
1905 }
1906 }
1907
1908 // can think about pushing multiple points here
1909 //DebugDialog::debug(QString("pushing next %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
1910 if (routeThing.sourceValue == GridSource) routeThing.sourceQ.push(next);
1911 else routeThing.targetQ.push(next);
1912
1913 if (writeable) {
1914 GridValue flag = (routeThing.sourceValue == GridSource) ? GridSourceFlag : 0;
1915 m_grid->setAt(next.x, next.y, next.z, next.baseCost | flag);
1916 }
1917
1918 //DebugDialog::debug("done expand one");
1919
1920
1921 //if (routeThing.searchForJumper) {
1922 // updateDisplay(next);
1923 //}
1924 }
1925
viaWillFit(GridPoint & gridPoint,Grid * grid)1926 bool MazeRouter::viaWillFit(GridPoint & gridPoint, Grid * grid) {
1927 for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
1928 int py = y + gridPoint.y;
1929 if (py < 0) return false;
1930 if (py >= grid->y) return false;
1931
1932 for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
1933 int px = x + gridPoint.x;
1934 if (px < 0) return false;
1935 if (px >= grid->x) return false;
1936
1937 for (int z = 0; z < grid->z; z++) {
1938 GridValue val = grid->at(px, py, z);
1939 if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget || val == GridTempObstacle || val == GridAvoid) return false;
1940 }
1941 }
1942 }
1943 return true;
1944 }
1945
updateDisplay(int iz)1946 void MazeRouter::updateDisplay(int iz) {
1947 QPixmap pixmap = QPixmap::fromImage(*m_displayImage[iz]);
1948 if (m_displayItem[iz] == NULL) {
1949 m_displayItem[iz] = new QGraphicsPixmapItem(pixmap);
1950 m_displayItem[iz]->setFlag(QGraphicsItem::ItemIsSelectable, false);
1951 m_displayItem[iz]->setFlag(QGraphicsItem::ItemIsMovable, false);
1952 //m_displayItem[iz]->setPos(iz == 1 ? m_maxRect.topLeft() : m_maxRect.topRight());
1953 m_displayItem[iz]->setPos(m_maxRect.topLeft());
1954 m_sketchWidget->scene()->addItem(m_displayItem[iz]);
1955 m_displayItem[iz]->setZValue(5000);
1956 //m_displayItem[iz]->setZValue(m_sketchWidget->viewLayers().value(iz == 0 ? ViewLayer::Copper0 : ViewLayer::Copper1)->nextZ());
1957 m_displayItem[iz]->setScale(m_gridPixels); // m_maxRect.width() / m_displayImage[iz]->width()
1958 m_displayItem[iz]->setVisible(true);
1959 }
1960 else {
1961 m_displayItem[iz]->setPixmap(pixmap);
1962 }
1963 ProcessEventBlocker::processEvents();
1964 }
1965
updateDisplay(Grid * grid,int iz)1966 void MazeRouter::updateDisplay(Grid * grid, int iz) {
1967 m_displayImage[iz]->fill(0);
1968 for (int y = 0; y < grid->y; y++) {
1969 for (int x = 0; x < grid->x; x++) {
1970 uint color = getColor(grid->at(x, y, iz));
1971 if (color) m_displayImage[iz]->setPixel(x, y, color);
1972 }
1973 }
1974
1975 updateDisplay(iz);
1976 }
1977
updateDisplay(GridPoint & gridPoint)1978 void MazeRouter::updateDisplay(GridPoint & gridPoint) {
1979 //static int counter = 0;
1980 //if (counter++ % 2 == 0) {
1981 uint color = getColor(m_grid->at(gridPoint.x, gridPoint.y, gridPoint.z));
1982 if (color) {
1983 m_displayImage[gridPoint.z]->setPixel(gridPoint.x, gridPoint.y, color);
1984 updateDisplay(gridPoint.z);
1985 }
1986 //}
1987 }
1988
clearExpansion(Grid * grid)1989 void MazeRouter::clearExpansion(Grid * grid) {
1990 // TODO: keep a list of expansion points instead?
1991
1992 for (int z = 0; z < grid->z; z++) {
1993 for (int y = 0; y < grid->y; y++) {
1994 for (int x = 0; x < grid->x; x++) {
1995 GridValue val = grid->at(x, y, z);
1996 if (val == 0 || val == GridPartObstacle || val == GridBoardObstacle) ;
1997 else grid->setAt(x, y, z, 0);
1998 }
1999 }
2000 }
2001 }
2002
initTraceDisplay()2003 void MazeRouter::initTraceDisplay() {
2004 m_displayImage[0]->fill(0);
2005 m_displayImage[1]->fill(0);
2006 }
2007
displayTrace(Trace & trace)2008 void MazeRouter::displayTrace(Trace & trace) {
2009 if (trace.gridPoints.count() == 0) {
2010 DebugDialog::debug("trace with no points");
2011 return;
2012 }
2013
2014 int lastz = trace.gridPoints.at(0).z;
2015 foreach (GridPoint gridPoint, trace.gridPoints) {
2016 if (gridPoint.z != lastz) {
2017 for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
2018 for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
2019 m_displayImage[1]->setPixel(x + gridPoint.x, y + gridPoint.y, 0x80ff0000);
2020 }
2021 }
2022 lastz = gridPoint.z;
2023 }
2024 else {
2025 m_displayImage[lastz]->setPixel(gridPoint.x, gridPoint.y, m_traceColors[lastz]);
2026 }
2027 }
2028
2029 if (trace.flags) {
2030 GridPoint gridPoint = trace.gridPoints.first();
2031 int xl, xr;
2032 if (trace.flags & JumperLeft) {
2033 xl = -(m_halfGridJumperSize * 2);
2034 xr = 0;
2035 }
2036 else if (trace.flags & JumperRight) {
2037 xl = 0;
2038 xr = m_halfGridJumperSize * 2;
2039 }
2040 else {
2041 xl = -m_halfGridJumperSize;
2042 xr = m_halfGridJumperSize;
2043 }
2044 for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
2045 for (int x = xl; x <= xr; x++) {
2046 m_displayImage[0]->setPixel(x + gridPoint.x, y + gridPoint.y, 0x800000ff);
2047 }
2048 }
2049 }
2050 }
2051
traceObstacles(QList<Trace> & traces,int netIndex,Grid * grid,int ikeepout)2052 void MazeRouter::traceObstacles(QList<Trace> & traces, int netIndex, Grid * grid, int ikeepout) {
2053 // treat traces from previous nets as obstacles
2054 foreach (Trace trace, traces) {
2055 if (trace.netIndex == netIndex) continue;
2056
2057 int lastZ = trace.gridPoints.at(0).z;
2058 foreach (GridPoint gridPoint, trace.gridPoints) {
2059 if (gridPoint.z != lastZ) {
2060 for (int y = -m_halfGridViaSize; y <= m_halfGridViaSize; y++) {
2061 for (int x = -m_halfGridViaSize; x <= m_halfGridViaSize; x++) {
2062 grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
2063 grid->setAt(gridPoint.x + x, gridPoint.y + y, 1, GridBoardObstacle);
2064 }
2065 }
2066 lastZ = gridPoint.z;
2067 }
2068 else {
2069 for (int y = -ikeepout; y <= ikeepout; y++) {
2070 for (int x = -ikeepout; x <= ikeepout; x++) {
2071 grid->setAt(gridPoint.x + x, gridPoint.y + y, gridPoint.z, GridBoardObstacle);
2072 }
2073 }
2074 }
2075
2076 }
2077
2078 if (trace.flags) {
2079 GridPoint gridPoint = trace.gridPoints.first();
2080 // jumper is always centered in this case
2081 for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
2082 for (int x = -m_halfGridJumperSize; x <= m_halfGridJumperSize; x++) {
2083 grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
2084 if (m_bothSidesNow) {
2085 grid->setAt(gridPoint.x + x, gridPoint.y + y, 1, GridBoardObstacle);
2086 }
2087 }
2088 }
2089 }
2090 }
2091 }
2092
traceAvoids(QList<Trace> & traces,int netIndex,RouteThing & routeThing)2093 void MazeRouter::traceAvoids(QList<Trace> & traces, int netIndex, RouteThing & routeThing) {
2094 // treat traces from previous nets as semi-obstacles
2095 routeThing.avoids.clear();
2096 foreach (Trace trace, traces) {
2097 if (trace.netIndex == netIndex) continue;
2098
2099 foreach (GridPoint gridPoint, trace.gridPoints) {
2100 for (int y = -m_keepoutGridInt; y <= m_keepoutGridInt; y++) {
2101 for (int x = -m_keepoutGridInt; x <= m_keepoutGridInt; x++) {
2102 GridValue val = m_grid->at(gridPoint.x + x, gridPoint.y + y, 0);
2103 if (val == GridPartObstacle || val == GridBoardObstacle || val == GridSource || val == GridTarget) continue;
2104
2105 m_grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridAvoid);
2106 routeThing.avoids.insert(((gridPoint.y + y) * m_grid->x) + x + gridPoint.x);
2107 }
2108 }
2109 }
2110
2111 if (trace.flags) {
2112 GridPoint gridPoint = trace.gridPoints.first();
2113 int xl, xr;
2114 if (gridPoint.flags & GridPointJumperLeft) {
2115 xl = -(m_halfGridJumperSize * 2);
2116 xr = 0;
2117 }
2118 else {
2119 xl = 0;
2120 xr = m_halfGridJumperSize * 2;
2121 }
2122
2123 for (int y = -m_halfGridJumperSize; y <= m_halfGridJumperSize; y++) {
2124 for (int x = xl; x <= xr; x++) {
2125 m_grid->setAt(gridPoint.x + x, gridPoint.y + y, 0, GridBoardObstacle);
2126 }
2127 }
2128 }
2129 }
2130 }
2131
cleanUpNets(NetList & netList)2132 void MazeRouter::cleanUpNets(NetList & netList) {
2133 foreach(Net * net, netList.nets) {
2134 delete net;
2135 }
2136 netList.nets.clear();
2137 Autorouter::cleanUpNets();
2138 }
2139
createTraces(NetList & netList,Score & bestScore,QUndoCommand * parentCommand)2140 void MazeRouter::createTraces(NetList & netList, Score & bestScore, QUndoCommand * parentCommand) {
2141 QPointF topLeft = m_maxRect.topLeft();
2142
2143 QMultiHash<int, Via *> allVias;
2144 QMultiHash<int, JumperItem *> allJumperItems;
2145 QMultiHash<int, SymbolPaletteItem *> allNetLabels;
2146 QMultiHash<int, QList< QPointer<TraceWire> > > allBundles;
2147
2148 ConnectionThing connectionThing;
2149
2150 emit setMaximumProgress(bestScore.ordering.order.count() * 2);
2151 emit setProgressMessage2(tr("Optimizing traces..."));
2152
2153 int progress = 0;
2154 foreach (int netIndex, bestScore.ordering.order) {
2155 emit setProgressValue(progress++);
2156 //DebugDialog::debug(QString("tracing net %1").arg(netIndex));
2157 QList<Trace> traces = bestScore.traces.values(netIndex);
2158 qSort(traces.begin(), traces.end(), byOrder);
2159
2160 TraceThing traceThing;
2161 traceThing.jumperItem = NULL;
2162 traceThing.netLabel = NULL;
2163 traceThing.topLeft = m_maxRect.topLeft();
2164 int newTraceIndex = 0;
2165
2166 Net * net = netList.nets.at(netIndex);
2167
2168 for (int tix = 0; tix < traces.count(); tix++) {
2169 Trace trace = traces.at(tix);
2170 QList<GridPoint> gridPoints = trace.gridPoints;
2171 // TODO: nicer curve-fitting
2172 removeColinear(gridPoints);
2173 removeSteps(gridPoints);
2174
2175 if (trace.flags & JumperStart) {
2176 Trace trace2 = traces.at(tix + 1);
2177 traceThing.nextTraceStart = trace2.gridPoints.first();
2178 }
2179
2180 createTrace(trace, gridPoints, traceThing, connectionThing, net);
2181 QList< QPointer<TraceWire> > bundle;
2182 if (traceThing.newTraces.count() > newTraceIndex) {
2183 ViewLayer::ViewLayerID viewLayerID = traceThing.newTraces.at(newTraceIndex)->viewLayerID();
2184 for (; newTraceIndex < traceThing.newTraces.count(); newTraceIndex++) {
2185 TraceWire * traceWire = traceThing.newTraces.at(newTraceIndex);
2186 if (traceWire->viewLayerID() != viewLayerID) {
2187 allBundles.insert(netIndex, bundle);
2188 bundle.clear();
2189 viewLayerID = traceWire->viewLayerID();
2190 }
2191 bundle << traceWire;
2192 }
2193 }
2194 else {
2195 DebugDialog::debug("create trace failed");
2196 }
2197 allBundles.insert(netIndex, bundle);
2198 }
2199 foreach (SymbolPaletteItem * netLabel, traceThing.newNetLabels) {
2200 allNetLabels.insert(netIndex, netLabel);
2201 }
2202 foreach (Via * via, traceThing.newVias) {
2203 allVias.insert(netIndex, via);
2204 }
2205 foreach (JumperItem * jumperItem, traceThing.newJumperItems) {
2206 allJumperItems.insert(netIndex, jumperItem);
2207 }
2208 }
2209
2210 //DebugDialog::debug("before optimize");
2211 optimizeTraces(bestScore.ordering.order, allBundles, allVias, allJumperItems, allNetLabels, netList, connectionThing);
2212 //DebugDialog::debug("after optimize");
2213
2214 foreach (SymbolPaletteItem * netLabel, allNetLabels) {
2215 addNetLabelToUndo(netLabel, parentCommand);
2216 }
2217 foreach (Via * via, allVias) {
2218 addViaToUndo(via, parentCommand);
2219 }
2220 foreach (JumperItem * jumperItem, allJumperItems) {
2221 addJumperToUndo(jumperItem, parentCommand);
2222 }
2223
2224 foreach (QList< QPointer<TraceWire> > bundle, allBundles) {
2225 foreach (TraceWire * traceWire, bundle) {
2226 addWireToUndo(traceWire, parentCommand);
2227 }
2228 }
2229
2230 foreach (ConnectorItem * source, connectionThing.sd.uniqueKeys()) {
2231 foreach (ConnectorItem * dest, connectionThing.values(source)) {
2232 addConnectionToUndo(source, dest, parentCommand);
2233 }
2234 }
2235
2236 QList<ModelPart *> modelParts;
2237 foreach (QList< QPointer<TraceWire> > bundle, allBundles) {
2238 foreach (TraceWire * traceWire, bundle) {
2239 if (traceWire) {
2240 modelParts << traceWire->modelPart();
2241 delete traceWire;
2242 }
2243 }
2244 }
2245
2246 foreach (Via * via, allVias.values()) {
2247 via->removeLayerKin();
2248 modelParts << via->modelPart();
2249 delete via;
2250 }
2251 foreach (JumperItem * jumperItem, allJumperItems.values()) {
2252 jumperItem->removeLayerKin();
2253 modelParts << jumperItem->modelPart();
2254 delete jumperItem;
2255 }
2256 foreach (SymbolPaletteItem * netLabel, allNetLabels.values()) {
2257 modelParts << netLabel->modelPart();
2258 delete netLabel;
2259 }
2260 foreach (ModelPart * modelPart, modelParts) {
2261 modelPart->setParent(NULL);
2262 delete modelPart;
2263 }
2264
2265 DebugDialog::debug("create traces complete");
2266 }
2267
createTrace(Trace & trace,QList<GridPoint> & gridPoints,TraceThing & traceThing,ConnectionThing & connectionThing,Net * net)2268 void MazeRouter::createTrace(Trace & trace, QList<GridPoint> & gridPoints, TraceThing & traceThing, ConnectionThing & connectionThing, Net * net)
2269 {
2270 //DebugDialog::debug(QString("create trace net:%1").arg(net->id));
2271 if (trace.flags & JumperStart) {
2272 if (m_pcbType) {
2273 long newID = ItemBase::getNextID();
2274 ViewGeometry viewGeometry;
2275 ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(ModuleIDNames::JumperModuleIDName),
2276 ViewLayer::NewTop, BaseCommand::SingleView, viewGeometry, newID, -1, NULL);
2277
2278 traceThing.jumperItem = dynamic_cast<JumperItem *>(itemBase);
2279 traceThing.jumperItem->setAutoroutable(true);
2280 m_sketchWidget->scene()->addItem(traceThing.jumperItem);
2281 QPointF c1 = getPixelCenter(trace.gridPoints.first(), traceThing.topLeft, m_gridPixels);
2282 QPointF c2 = getPixelCenter(traceThing.nextTraceStart, traceThing.topLeft, m_gridPixels);
2283 traceThing.jumperItem->resize(c1, c2);
2284 traceThing.newJumperItems << traceThing.jumperItem;
2285 }
2286 else {
2287 traceThing.netLabel = makeNetLabel(trace.gridPoints.first(), NULL, trace.flags);
2288 traceThing.newNetLabels << traceThing.netLabel;
2289 }
2290 }
2291 else if (trace.flags & JumperEnd) {
2292 if (m_pcbType) {
2293 // keep the jumperItem we have from JumperStart
2294 }
2295 else {
2296 traceThing.netLabel = makeNetLabel(trace.gridPoints.first(), traceThing.netLabel, trace.flags);
2297 traceThing.newNetLabels << traceThing.netLabel;
2298 }
2299 }
2300 else traceThing.jumperItem = NULL;
2301
2302 bool onTraceS, onTraceD;
2303 QPointF traceAnchorS, traceAnchorD;
2304 ConnectorItem * sourceConnectorItem = NULL;
2305 if (traceThing.jumperItem) {
2306 onTraceS = onTraceD = false;
2307 sourceConnectorItem = (trace.flags & JumperStart) ? traceThing.jumperItem->connector0() : traceThing.jumperItem->connector1();
2308 }
2309 else if (traceThing.netLabel) {
2310 sourceConnectorItem = traceThing.netLabel->connector0();
2311 }
2312 else {
2313 sourceConnectorItem = findAnchor(gridPoints.first(), traceThing, net, traceAnchorS, onTraceS, NULL);
2314 }
2315 if (sourceConnectorItem == NULL) {
2316 DebugDialog::debug("missing source connector");
2317 return;
2318 }
2319
2320 ConnectorItem * destConnectorItem = findAnchor(gridPoints.last(), traceThing, net, traceAnchorD, onTraceD, sourceConnectorItem);
2321 if (destConnectorItem == NULL) {
2322
2323 /*
2324 GridPoint gp = gridPoints.last();
2325 for (int x = gp.x - 5; x < gp.x + 5; x++) {
2326 m_displayImage[gp.z]->setPixel(x, gp.y, 0xff000000);
2327 }
2328 for (int y = gp.y - 5; y < gp.y + 5; y++) {
2329 m_displayImage[gp.z]->setPixel(gp.x, y, 0xff000000);
2330 }
2331 updateDisplay(gp.z);
2332 */
2333
2334 DebugDialog::debug("missing dest connector");
2335 return;
2336 }
2337
2338 //if (sourceConnectorItem->attachedTo() == destConnectorItem->attachedTo()) {
2339 // sourceConnectorItem->debugInfo("source");
2340 // destConnectorItem->debugInfo("dest");
2341 //}
2342
2343 QPointF sourcePoint = sourceConnectorItem->sceneAdjustedTerminalPoint(NULL);
2344 QPointF destPoint = destConnectorItem->sceneAdjustedTerminalPoint(NULL);
2345
2346 bool skipFirst = false;
2347 bool skipLast = false;
2348
2349 GridPoint gp = gridPoints.last();
2350 QPointF center = getPixelCenter(gp, traceThing.topLeft, m_gridPixels);
2351 if (!atLeast(center, destPoint)) {
2352 // don't need this last point
2353 skipLast = true;
2354 }
2355
2356 gp = gridPoints.first();
2357 center = getPixelCenter(gp, traceThing.topLeft, m_gridPixels);
2358 if (!atLeast(center, sourcePoint)) {
2359 skipFirst = true;
2360 }
2361
2362 // convert grid-based points to normal svg-space points and add the inbetween points necessitated by removeSteps()
2363 QList<PointZ> newPoints;
2364 for (int i = 0; i < gridPoints.count(); i++) {
2365 GridPoint gp1 = gridPoints.at(i);
2366 QPointF c1 = getPixelCenter(gp1, traceThing.topLeft, m_gridPixels);
2367 PointZ v1(c1, gp1.z);
2368 newPoints << v1;
2369 if ((gp1.flags & GridPointStepStart) == 0) continue;
2370
2371 GridPoint gp2 = gridPoints.at(i + 1);
2372 QPointF c2 = getPixelCenter(gp2, traceThing.topLeft, m_gridPixels);
2373
2374 QPointF p = getStepPoint(c1, gp1.flags, m_gridPixels);
2375 PointZ v2(p, gp1.z);
2376 newPoints << v2;
2377
2378 QPointF q = getStepPoint(c2, gp2.flags, m_gridPixels);
2379 PointZ v3(q, gp2.z);
2380 newPoints << v3;
2381
2382 //DebugDialog::debug(QString("remove2 %1,%2 %3,%4").arg(c1.x()).arg(c1.y()).arg(p.x()).arg(p.y()));
2383 //DebugDialog::debug(QString("\t%1,%2 %3,%4").arg(q.x()).arg(q.y()).arg(c2.x()).arg(c2.y()));
2384
2385 }
2386
2387 if (skipLast) {
2388 newPoints.takeLast();
2389 }
2390 PointZ point = newPoints.takeFirst();
2391 if (skipFirst) {
2392 point = newPoints.takeFirst();
2393 }
2394
2395 int lastz = point.z;
2396 ConnectorItem * nextSource = NULL;
2397 if (onTraceS) {
2398 if (!atLeast(sourcePoint, traceAnchorS)) {
2399 onTraceS = false;
2400 }
2401 else if (atLeast(point.p, traceAnchorS)) {
2402 onTraceS = false;
2403 }
2404 }
2405 if (onTraceS) {
2406 TraceWire * traceWire1 = drawOneTrace(sourcePoint, traceAnchorS, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2407 connectionThing.add(sourceConnectorItem, traceWire1->connector0());
2408 traceThing.newTraces << traceWire1;
2409
2410 TraceWire* traceWire2 = drawOneTrace(traceAnchorS, point.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2411 connectionThing.add(traceWire1->connector1(), traceWire2->connector0());
2412 nextSource = traceWire2->connector1();
2413 traceThing.newTraces << traceWire2;
2414 }
2415 else {
2416 TraceWire * traceWire = drawOneTrace(sourcePoint, point.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2417 connectionThing.add(sourceConnectorItem, traceWire->connector0());
2418 nextSource = traceWire->connector1();
2419 traceThing.newTraces << traceWire;
2420 }
2421
2422 foreach (PointZ newPoint, newPoints) {
2423 if (newPoint.z == lastz) {
2424 TraceWire * traceWire = drawOneTrace(point.p, newPoint.p, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2425 connectionThing.add(nextSource, traceWire->connector0());
2426 nextSource = traceWire->connector1();
2427 traceThing.newTraces << traceWire;
2428 }
2429 else {
2430 long newID = ItemBase::getNextID();
2431 ViewGeometry viewGeometry;
2432 double ringThickness, holeSize;
2433 m_sketchWidget->getViaSize(ringThickness, holeSize);
2434 double halfVia = (ringThickness + ringThickness + holeSize) / 2;
2435
2436 viewGeometry.setLoc(QPointF(newPoint.p.x() - halfVia - Hole::OffsetPixels, newPoint.p.y() - halfVia - Hole::OffsetPixels));
2437 ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(ModuleIDNames::ViaModuleIDName),
2438 ViewLayer::NewTop, BaseCommand::SingleView, viewGeometry, newID, -1, NULL);
2439
2440 //DebugDialog::debug(QString("back from adding via %1").arg((long) itemBase, 0, 16));
2441 Via * via = qobject_cast<Via *>(itemBase);
2442 via->setAutoroutable(true);
2443 via->setHoleSize(QString("%1in,%2in") .arg(holeSize / GraphicsUtils::SVGDPI) .arg(ringThickness / GraphicsUtils::SVGDPI), false);
2444
2445 connectionThing.add(nextSource, via->connectorItem());
2446 nextSource = via->connectorItem();
2447 traceThing.newVias << via;
2448 lastz = newPoint.z;
2449 }
2450 point = newPoint;
2451 }
2452 if (onTraceD) {
2453 if (!atLeast(destPoint, traceAnchorD)) {
2454 onTraceD = false;
2455 }
2456 else if (!atLeast(point.p, traceAnchorD)) {
2457 onTraceD = false;
2458 }
2459 }
2460 if (onTraceD) {
2461 TraceWire * traceWire1 = drawOneTrace(point.p, traceAnchorD, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2462 connectionThing.add(nextSource, traceWire1->connector0());
2463 traceThing.newTraces << traceWire1;
2464
2465 TraceWire * traceWire2 = drawOneTrace(traceAnchorD, destPoint, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2466 connectionThing.add(traceWire1->connector1(), traceWire2->connector0());
2467 connectionThing.add(traceWire2->connector1(), destConnectorItem);
2468 traceThing.newTraces << traceWire2;
2469 }
2470 else {
2471 TraceWire * traceWire = drawOneTrace(point.p, destPoint, m_standardWireWidth, lastz == 0 ? ViewLayer::NewBottom : ViewLayer::NewTop);
2472 connectionThing.add(nextSource, traceWire->connector0());
2473 connectionThing.add(traceWire->connector1(), destConnectorItem);
2474 traceThing.newTraces << traceWire;
2475 }
2476 }
2477
findAnchor(GridPoint gp,TraceThing & traceThing,Net * net,QPointF & p,bool & onTrace,ConnectorItem * already)2478 ConnectorItem * MazeRouter::findAnchor(GridPoint gp, TraceThing & traceThing, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already)
2479 {
2480 QRectF gridRect(gp.x * m_gridPixels + traceThing.topLeft.x(), gp.y * m_gridPixels + traceThing.topLeft.y(), m_gridPixels, m_gridPixels);
2481 ConnectorItem * connectorItem = findAnchor(gp, gridRect, traceThing, net, p, onTrace, already);
2482
2483 if (connectorItem != NULL) {
2484 //if (connectorItem->attachedToID() == 9781620) {
2485 // connectorItem->debugInfo("9781620");
2486 //}
2487
2488 if (connectorItem->attachedToItemType() != ModelPart::Wire) {
2489 return connectorItem;
2490 }
2491
2492 // otherwise keep looking
2493 }
2494
2495 gridRect.adjust(-m_gridPixels, -m_gridPixels, m_gridPixels, m_gridPixels);
2496 return findAnchor(gp, gridRect, traceThing, net, p, onTrace, already);
2497 }
2498
findAnchor(GridPoint gp,const QRectF & gridRect,TraceThing & traceThing,Net * net,QPointF & p,bool & onTrace,ConnectorItem * already)2499 ConnectorItem * MazeRouter::findAnchor(GridPoint gp, const QRectF & gridRect, TraceThing & traceThing, Net * net, QPointF & p, bool & onTrace, ConnectorItem * already)
2500 {
2501 ConnectorItem * alreadyCross = NULL;
2502 if (already != NULL) alreadyCross = already->getCrossLayerConnectorItem();
2503 QList<TraceWire *> traceWires;
2504 QList<ConnectorItem *> traceConnectorItems;
2505 foreach (QGraphicsItem * item, m_sketchWidget->scene()->items(gridRect)) {
2506 ConnectorItem * connectorItem = dynamic_cast<ConnectorItem *>(item);
2507 if (connectorItem) {
2508 if (!connectorItem->attachedTo()->isEverVisible()) continue;
2509 if (connectorItem == already) continue;
2510 if (connectorItem == alreadyCross) continue;
2511
2512 if (already != NULL && connectorItem->attachedTo() == already->attachedTo()) {
2513 ConnectorItem * cross = connectorItem->getCrossLayerConnectorItem();
2514 if (cross != NULL) {
2515 if (cross == already) continue;
2516 if (cross == alreadyCross) continue;
2517 }
2518 }
2519
2520 //connectorItem->debugInfo("candidate");
2521
2522 bool isCandidate =
2523 (gp.z == 0 && m_sketchWidget->attachedToBottomLayer(connectorItem)) ||
2524 (gp.z == 1 && m_sketchWidget->attachedToTopLayer(connectorItem))
2525 ;
2526 if (!isCandidate) continue;
2527
2528 bool traceConnector = false;
2529 if (net->net->contains(connectorItem)) ;
2530 else {
2531 TraceWire * traceWire = qobject_cast<TraceWire *>(connectorItem->attachedTo());
2532 if (traceWire == NULL) {
2533 Via * via = qobject_cast<Via *>(connectorItem->attachedTo()->layerKinChief());
2534 if (via == NULL) isCandidate = false;
2535 else isCandidate = traceThing.newVias.contains(via);
2536 }
2537 else {
2538 traceConnector = isCandidate = traceThing.newTraces.contains(traceWire);
2539 }
2540 }
2541 if (!isCandidate) continue;
2542
2543 if (traceConnector) {
2544 traceConnectorItems << connectorItem;
2545 continue;
2546 }
2547 else {
2548 //if (traceConnectorItems.count() > 0) {
2549 // connectorItem->debugInfo("chose not trace");
2550 //}
2551 onTrace = false;
2552 p = connectorItem->sceneAdjustedTerminalPoint(NULL);
2553 return connectorItem;
2554 }
2555 }
2556
2557 TraceWire * traceWire = dynamic_cast<TraceWire *>(item);
2558 if (traceWire == NULL) continue;
2559 if (!traceWire->isEverVisible()) continue;
2560
2561 // only do traces if no connectorItem is found
2562 traceWires.append(traceWire);
2563 }
2564
2565 if (traceConnectorItems.count() > 0) {
2566 //if (traceConnectorItems.count() > 1) {
2567 // foreach (ConnectorItem * connectorItem, traceConnectorItems) {
2568 // connectorItem->debugInfo("on trace");
2569 // }
2570 //}
2571 onTrace = false;
2572 ConnectorItem * connectorItem = traceConnectorItems.takeLast();
2573 p = connectorItem->sceneAdjustedTerminalPoint(NULL);
2574 return connectorItem;
2575 }
2576
2577 foreach (TraceWire * traceWire, traceWires) {
2578 //traceWire->debugInfo("trace candidate");
2579 bool isCandidate = (gp.z == 0 && m_sketchWidget->attachedToBottomLayer(traceWire->connector0()))
2580 || (gp.z == 1 && m_sketchWidget->attachedToTopLayer(traceWire->connector0()));
2581 if (!isCandidate) continue;
2582
2583 if (traceThing.newTraces.contains(traceWire)) ;
2584 else if (net->net->contains(traceWire->connector0())) ;
2585 else continue;
2586
2587 onTrace = true;
2588 QPointF center = gridRect.center();
2589 QPointF p0 = traceWire->connector0()->sceneAdjustedTerminalPoint(NULL);
2590 QPointF p1 = traceWire->connector1()->sceneAdjustedTerminalPoint(NULL);
2591 double d0 = GraphicsUtils::distanceSqd(p0, center);
2592 double d1 = GraphicsUtils::distanceSqd(p1, center);
2593 double dx, dy, distanceSegment;
2594 bool atEndpoint;
2595 GraphicsUtils::distanceFromLine(center.x(), center.y(), p0.x(), p0.y(), p1.x(), p1.y(), dx, dy, distanceSegment, atEndpoint);
2596 if (atEndpoint) {
2597 DebugDialog::debug("at endpoint shouldn't happen");
2598 }
2599 p.setX(dx);
2600 p.setY(dy);
2601 if (d0 <= d1) {
2602 return traceWire->connector0();
2603 }
2604 else {
2605 return traceWire->connector1();
2606 }
2607 }
2608
2609 DebugDialog::debug("overlap not found");
2610 return NULL;
2611 }
2612
removeColinear(QList<GridPoint> & gridPoints)2613 void MazeRouter::removeColinear(QList<GridPoint> & gridPoints) {
2614 // eliminate redundant colinear points
2615 int ix = 0;
2616 while (ix < gridPoints.count() - 2) {
2617 GridPoint p1 = gridPoints[ix];
2618 GridPoint p2 = gridPoints[ix + 1];
2619 if (p1.z == p2.z) {
2620 GridPoint p3 = gridPoints[ix + 2];
2621 if (p2.z == p3.z) {
2622 if (p1.x == p2.x && p2.x == p3.x) {
2623 gridPoints.removeAt(ix + 1);
2624 continue;
2625 }
2626 else if (p1.y == p2.y && p2.y == p3.y) {
2627 gridPoints.removeAt(ix + 1);
2628 continue;
2629 }
2630 }
2631 }
2632 ix++;
2633 }
2634 }
2635
removeSteps(QList<GridPoint> & gridPoints)2636 void MazeRouter::removeSteps(QList<GridPoint> & gridPoints) {
2637 // eliminate 45 degree runs
2638 for (int ix = 0; ix < gridPoints.count() - 2; ix++) {
2639 removeStep(ix, gridPoints);
2640 }
2641 }
2642
removeStep(int ix,QList<GridPoint> & gridPoints)2643 void MazeRouter::removeStep(int ix, QList<GridPoint> & gridPoints) {
2644 GridPoint p1 = gridPoints[ix];
2645 GridPoint p2 = gridPoints[ix + 1];
2646 if (p1.z != p2.z) return;
2647
2648 GridPoint p3 = gridPoints[ix + 2];
2649 if (p2.z != p3.z) return;
2650
2651 int dx1 = p2.x - p1.x;
2652 int dy1 = p2.y - p1.y;
2653 if ((qAbs(dx1) == 1 && dy1 == 0) || (dx1 == 0 && qAbs(dy1) == 1)) ;
2654 else return;
2655
2656 int dx2 = p3.x - p2.x;
2657 int dy2 = p3.y - p2.y;
2658 bool step = false;
2659 if (dx1 == 0) {
2660 step = (dy2 == 0 && qAbs(dx2) == 1);
2661 }
2662 else {
2663 step = (dx2 == 0 && qAbs(dy2) == 1);
2664 }
2665 if (!step) return;
2666
2667 int count = 1;
2668 int flag = 0;
2669 for (int jx = ix + 3; jx < gridPoints.count(); jx++, flag++) {
2670 GridPoint p4 = gridPoints[jx];
2671 int dx3 = p4.x - p3.x;
2672 int dy3 = p4.y - p3.y;
2673 if (flag % 2 == 0) {
2674 if (dx3 == dx1 && dy3 == dy1) {
2675 count++;
2676 }
2677 else break;
2678 }
2679 else {
2680 if (dx3 == dx2 && dy3 == dy2) {
2681 count++;
2682 }
2683 else break;
2684 }
2685 p2 = p3;
2686 p3 = p4;
2687 }
2688
2689 gridPoints[ix].flags = getStepFlag(gridPoints[ix], gridPoints[ix + 1]) | GridPointStepStart;
2690 int jx = ix + count + 1;
2691 gridPoints[jx].flags = getStepFlag(gridPoints[jx], gridPoints[jx - 1]);
2692
2693 /*
2694 QPointF topLeft = m_maxRect.topLeft();
2695 DebugDialog::debug(QString("removing %1").arg(count));
2696 for (int i = 0; i < count + 2; i++) {
2697 QPointF p = getPixelCenter(gridPoints[ix + i], topLeft, m_gridPixels);
2698 DebugDialog::debug(QString("\t%1,%2 %3,%4").arg(gridPoints[ix + i].x).arg(gridPoints[ix + i].y).arg(p.x()).arg(p.y()));
2699 }
2700 */
2701
2702 while (--count >= 0) {
2703 gridPoints.removeAt(ix + 1);
2704 }
2705
2706 }
2707
addConnectionToUndo(ConnectorItem * from,ConnectorItem * to,QUndoCommand * parentCommand)2708 void MazeRouter::addConnectionToUndo(ConnectorItem * from, ConnectorItem * to, QUndoCommand * parentCommand)
2709 {
2710 if (from == NULL || to == NULL) return;
2711
2712 ChangeConnectionCommand * ccc = new ChangeConnectionCommand(m_sketchWidget, BaseCommand::CrossView,
2713 from->attachedToID(), from->connectorSharedID(),
2714 to->attachedToID(), to->connectorSharedID(),
2715 ViewLayer::specFromID(from->attachedToViewLayerID()),
2716 true, parentCommand);
2717 ccc->setUpdateConnections(false);
2718 }
2719
addViaToUndo(Via * via,QUndoCommand * parentCommand)2720 void MazeRouter::addViaToUndo(Via * via, QUndoCommand * parentCommand) {
2721 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::ViaModuleIDName, via->viewLayerPlacement(), via->getViewGeometry(), via->id(), false, -1, parentCommand);
2722 new SetPropCommand(m_sketchWidget, via->id(), "hole size", via->holeSize(), via->holeSize(), true, parentCommand);
2723 new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, via->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
2724 }
2725
addJumperToUndo(JumperItem * jumperItem,QUndoCommand * parentCommand)2726 void MazeRouter::addJumperToUndo(JumperItem * jumperItem, QUndoCommand * parentCommand) {
2727 jumperItem->saveParams();
2728 QPointF pos, c0, c1;
2729 jumperItem->getParams(pos, c0, c1);
2730
2731 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::JumperModuleIDName, jumperItem->viewLayerPlacement(), jumperItem->getViewGeometry(), jumperItem->id(), false, -1, parentCommand);
2732 new ResizeJumperItemCommand(m_sketchWidget, jumperItem->id(), pos, c0, c1, pos, c0, c1, parentCommand);
2733 new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, jumperItem->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
2734 }
2735
addNetLabelToUndo(SymbolPaletteItem * netLabel,QUndoCommand * parentCommand)2736 void MazeRouter::addNetLabelToUndo(SymbolPaletteItem * netLabel, QUndoCommand * parentCommand) {
2737 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, netLabel->moduleID(), netLabel->viewLayerPlacement(), netLabel->getViewGeometry(), netLabel->id(), false, -1, parentCommand);
2738 new SetPropCommand(m_sketchWidget, netLabel->id(), "label", netLabel->getLabel(), netLabel->getLabel(), true, parentCommand);
2739 }
2740
insertTrace(Trace & newTrace,int netIndex,Score & currentScore,int viaCount,bool incRouted)2741 void MazeRouter::insertTrace(Trace & newTrace, int netIndex, Score & currentScore, int viaCount, bool incRouted) {
2742 if (newTrace.gridPoints.count() == 0) {
2743 DebugDialog::debug("trace with no points");
2744 return;
2745 }
2746
2747 //DebugDialog::debug(QString("insert trace %1").arg(newTrace.gridPoints.count()));
2748
2749 newTrace.netIndex = netIndex;
2750 newTrace.order = currentScore.traces.values(netIndex).count();
2751 currentScore.traces.insert(netIndex, newTrace);
2752 if (incRouted) {
2753 currentScore.routedCount.insert(netIndex, currentScore.routedCount.value(netIndex) + 1);
2754 currentScore.totalRoutedCount++;
2755 }
2756 currentScore.viaCount.insert(netIndex, currentScore.viaCount.value(netIndex, 0) + viaCount);
2757 currentScore.totalViaCount += viaCount;
2758 displayTrace(newTrace);
2759
2760 //DebugDialog::debug(QString("done insert trace"));
2761
2762 }
2763
incCommandProgress()2764 void MazeRouter::incCommandProgress() {
2765 emit setProgressValue(m_cleanupCount++);
2766
2767 int modulo = m_commandCount / 100;
2768 if (modulo > 0 && m_cleanupCount % modulo == 0) {
2769 ProcessEventBlocker::processEvents();
2770 }
2771 //DebugDialog::debug(QString("cleanup:%1, cc:%2").arg(m_cleanupCount).arg(m_commandCount));
2772 }
2773
setMaxCycles(int maxCycles)2774 void MazeRouter::setMaxCycles(int maxCycles)
2775 {
2776 Autorouter::setMaxCycles(maxCycles);
2777 emit setMaximumProgress(maxCycles);
2778 }
2779
makeNetLabel(GridPoint & center,SymbolPaletteItem * pairedNetLabel,uchar traceFlags)2780 SymbolPaletteItem * MazeRouter::makeNetLabel(GridPoint & center, SymbolPaletteItem * pairedNetLabel, uchar traceFlags) {
2781 // flags & JumperLeft means position the netlabel to the left of center, the netlabel points right
2782
2783 if (m_netLabelIndex < 0) {
2784 m_netLabelIndex = 0;
2785 foreach (QGraphicsItem * item, m_sketchWidget->scene()->items()) {
2786 SymbolPaletteItem * netLabel = dynamic_cast<SymbolPaletteItem *>(item);
2787 if (netLabel == NULL || !netLabel->isOnlyNetLabel()) continue;
2788
2789 bool ok;
2790 int ix = netLabel->getLabel().toInt(&ok);
2791 if (ok && ix > m_netLabelIndex) m_netLabelIndex = ix;
2792 }
2793 }
2794
2795 if (pairedNetLabel == NULL) {
2796 m_netLabelIndex++;
2797 }
2798
2799 long newID = ItemBase::getNextID();
2800 ViewGeometry viewGeometry;
2801 ItemBase * itemBase = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(traceFlags & JumperLeft ? ModuleIDNames::NetLabelModuleIDName : ModuleIDNames::LeftNetLabelModuleIDName),
2802 ViewLayer::NewBottom, BaseCommand::SingleView, viewGeometry, newID, -1, NULL);
2803
2804 SymbolPaletteItem * netLabel = dynamic_cast<SymbolPaletteItem *>(itemBase);
2805 netLabel->setAutoroutable(true);
2806 netLabel->setLabel(QString::number(m_netLabelIndex));
2807 QPointF tl = m_maxRect.topLeft();
2808 QPointF c1 = getPixelCenter(center, tl, m_gridPixels);
2809 QSizeF size = netLabel->boundingRect().size();
2810 int x = c1.x();
2811 if (traceFlags & JumperLeft) {
2812 x -= size.width();
2813 }
2814 netLabel->setPos(x, c1.y() - (size.height() / 2));
2815 //DebugDialog::debug(QString("ix:%1 tl:%2 %3,%4").arg(m_netLabelIndex).arg(traceFlags).arg(x).arg(c1.y() - (size.height() / 2)));
2816 netLabel->saveGeometry();
2817 return netLabel;
2818 }
2819
routeJumper(int netIndex,RouteThing & routeThing,Score & currentScore)2820 void MazeRouter::routeJumper(int netIndex, RouteThing & routeThing, Score & currentScore)
2821 {
2822 if (routeThing.bestDistanceToTarget == std::numeric_limits<double>::max() || routeThing.bestDistanceToSource == std::numeric_limits<double>::max()) {
2823 // never got started on this route
2824 return;
2825 }
2826
2827 //DebugDialog::debug(QString("route jumper %1, %2").arg(routeThing.bestDistanceToSource).arg(routeThing.bestDistanceToTarget));
2828
2829 //updateDisplay(0);
2830 //if (m_bothSidesNow) updateDisplay(1);
2831
2832 bool routeBothEnds = true;
2833 Trace sourceTrace;
2834 if (!m_pcbType) {
2835 // is there already a net label on this net?
2836
2837 // TODO: which subnet has the jumper?
2838 foreach (Trace trace, currentScore.traces.values(netIndex)) {
2839 if (trace.flags & JumperStart) {
2840 sourceTrace = trace;
2841 routeBothEnds = false;
2842 break;
2843 }
2844 }
2845 }
2846
2847 //updateDisplay(m_grid, 0);
2848 //if (m_bothSidesNow) updateDisplay(m_grid, 1);
2849
2850 GridPoint gp1 = lookForJumper(routeThing.bestLocationToTarget, GridSource, routeThing.gridTargetPoint);
2851 if (gp1.baseCost == GridBoardObstacle) return;
2852
2853 GridPoint gp2 = lookForJumper(routeThing.bestLocationToSource, GridTarget, routeThing.gridSourcePoint);
2854 if (gp2.baseCost == GridBoardObstacle) return;
2855
2856 int sourceViaCount;
2857 if (routeBothEnds) {
2858 sourceTrace.flags = JumperStart;
2859 if (gp1.flags & GridPointJumperLeft) sourceTrace.flags |= JumperLeft;
2860 else if (gp1.flags & GridPointJumperRight) sourceTrace.flags |= JumperRight;
2861 sourceTrace.gridPoints = traceBack(gp1, m_grid, sourceViaCount, GridTarget, GridSource); // trace back to source
2862 }
2863
2864 Trace destTrace;
2865 destTrace.flags = JumperEnd;
2866 if (gp2.flags & GridPointJumperLeft) destTrace.flags |= JumperLeft;
2867 else if (gp2.flags & GridPointJumperRight) destTrace.flags |= JumperRight;
2868 int targetViaCount;
2869 destTrace.gridPoints = traceBack(gp2, m_grid, targetViaCount, GridSource, GridTarget); // trace back to target
2870
2871 if (routeBothEnds) {
2872 insertTrace(sourceTrace, netIndex, currentScore, sourceViaCount, false);
2873 }
2874 insertTrace(destTrace, netIndex, currentScore, targetViaCount, true);
2875 updateDisplay(0);
2876 if (m_bothSidesNow) updateDisplay(1);
2877
2878 clearExpansion(m_grid);
2879 }
2880
lookForJumper(GridPoint initial,GridValue targetValue,QPoint targetLocation)2881 GridPoint MazeRouter::lookForJumper(GridPoint initial, GridValue targetValue, QPoint targetLocation) {
2882 QSet<int> already;
2883 std::priority_queue<GridPoint> pq;
2884 initial.qCost = 0;
2885 pq.push(initial);
2886 already.insert(gridPointInt(m_grid, initial));
2887 while (!pq.empty()) {
2888 GridPoint gp = pq.top();
2889 pq.pop();
2890
2891 gp.baseCost = m_grid->at(gp.x, gp.y, gp.z);
2892
2893 /*
2894 GridValue bc = gp.baseCost;
2895 if (targetValue == GridSource) bc ^= GridSourceFlag;
2896 bc *= 3;
2897 if (bc > 255) bc = 255;
2898 m_displayImage[gp.z]->setPixel(gp.x, gp.y, 0xff000000 | (bc << 16) | (bc << 8) | bc);
2899 updateDisplay(gp.z);
2900 */
2901
2902 if ((*m_jumperWillFitFunction)(gp, m_grid, m_halfGridJumperSize)) {
2903 if (targetValue == GridSource) gp.baseCost ^= GridSourceFlag;
2904
2905 //m_displayImage[gp.z]->setPixel(gp.x, gp.y, 0xff0000ff);
2906 //updateDisplay(gp.z);
2907 //updateDisplay(gp.z);
2908
2909 //QPointF p = getPixelCenter(gp, m_maxRect.topLeft(), m_gridPixels);
2910 //DebugDialog::debug(QString("jumper location %1").arg(gp.flags), p);
2911
2912 return gp;
2913 }
2914
2915 if (gp.x > 0) expandOneJ(gp, pq, -1, 0, 0, targetValue, targetLocation, already);
2916 if (gp.x < m_grid->x - 1) expandOneJ(gp, pq, 1, 0, 0, targetValue, targetLocation, already);
2917 if (gp.y > 0) expandOneJ(gp, pq, 0, -1, 0, targetValue, targetLocation, already);
2918 if (gp.y < m_grid->y - 1) expandOneJ(gp, pq, 0, 1, 0, targetValue, targetLocation, already);
2919 if (m_bothSidesNow) {
2920 if (gp.z > 0) expandOneJ(gp, pq, 0, 0, -1, targetValue, targetLocation, already);
2921 if (gp.z < m_grid->z - 1) expandOneJ(gp, pq, 0, 0, 1, targetValue, targetLocation, already);
2922 }
2923 }
2924
2925 GridPoint failed;
2926 failed.baseCost = GridBoardObstacle;
2927 return failed;
2928 }
2929
expandOneJ(GridPoint & gridPoint,std::priority_queue<GridPoint> & pq,int dx,int dy,int dz,GridValue targetValue,QPoint targetLocation,QSet<int> & already)2930 void MazeRouter::expandOneJ(GridPoint & gridPoint, std::priority_queue<GridPoint> & pq, int dx, int dy, int dz, GridValue targetValue, QPoint targetLocation, QSet<int> & already)
2931 {
2932 GridPoint next;
2933 next.x = gridPoint.x + dx;
2934 next.y = gridPoint.y + dy;
2935 next.z = gridPoint.z + dz;
2936 int gpi = gridPointInt(m_grid, next);
2937 if (already.contains(gpi)) return;
2938
2939 already.insert(gpi);
2940 GridValue nextval = m_grid->at(next.x, next.y, next.z);
2941 if (nextval == GridPartObstacle || nextval == GridBoardObstacle || nextval == GridSource || nextval == GridTempObstacle || nextval == GridTarget || nextval == GridAvoid) return;
2942 else if (nextval == 0) return;
2943 else {
2944 // already been here: see if it's the right expansion
2945 if (targetValue == GridSource) {
2946 if ((nextval & GridSourceFlag) == 0) return;
2947 }
2948 else {
2949 if (nextval & GridSourceFlag) return;
2950 }
2951 }
2952
2953 double d = (m_costFunction)(QPoint(next.x, next.y), targetLocation);
2954 next.qCost = d;
2955 next.baseCost = 0;
2956
2957 //DebugDialog::debug(QString("pushing next %1 %2 %3, %4, %5").arg(gridPoint.x).arg(gridPoint.y).arg(gridPoint.z).arg(gridPoint.qCost).arg(routeThing.pq.size()));
2958 pq.push(next);
2959 }
2960
removeOffBoardAnd(bool isPCBType,bool removeSingletons,bool bothSides)2961 void MazeRouter::removeOffBoardAnd(bool isPCBType, bool removeSingletons, bool bothSides) {
2962 QRectF boardRect;
2963 if (m_board) boardRect = m_board->sceneBoundingRect();
2964 // remove any vias or jumperItems that will be deleted, also remove off-board items
2965 for (int i = m_allPartConnectorItems.count() - 1; i >= 0; i--) {
2966 QList<ConnectorItem *> * connectorItems = m_allPartConnectorItems.at(i);
2967 if (removeSingletons) {
2968 if (connectorItems->count() < 2) {
2969 connectorItems->clear();
2970 }
2971 else if (connectorItems->count() == 2) {
2972 if (connectorItems->at(0) == connectorItems->at(1)->getCrossLayerConnectorItem()) {
2973 connectorItems->clear();
2974 }
2975 }
2976 }
2977 for (int j = connectorItems->count() - 1; j >= 0; j--) {
2978 ConnectorItem * connectorItem = connectorItems->at(j);
2979 //connectorItem->debugInfo("pci");
2980 bool doRemove = false;
2981 if (connectorItem->attachedToItemType() == ModelPart::Via) {
2982 Via * via = qobject_cast<Via *>(connectorItem->attachedTo()->layerKinChief());
2983 doRemove = via->getAutoroutable();
2984 }
2985 else if (connectorItem->attachedToItemType() == ModelPart::Jumper) {
2986 JumperItem * jumperItem = qobject_cast<JumperItem *>(connectorItem->attachedTo()->layerKinChief());
2987 doRemove = jumperItem->getAutoroutable();
2988 }
2989 else if (connectorItem->attachedToItemType() == ModelPart::Symbol) {
2990 SymbolPaletteItem * netLabel = qobject_cast<SymbolPaletteItem *>(connectorItem->attachedTo()->layerKinChief());
2991 doRemove = netLabel->getAutoroutable() && netLabel->isOnlyNetLabel();
2992 }
2993 if (!bothSides && connectorItem->attachedToViewLayerID() == ViewLayer::Copper1) doRemove = true;
2994 if (!doRemove && isPCBType) {
2995 if (!connectorItem->sceneBoundingRect().intersects(boardRect)) {
2996 doRemove = true;
2997 }
2998 }
2999 if (doRemove) {
3000 connectorItems->removeAt(j);
3001 }
3002 }
3003 if (connectorItems->count() == 0) {
3004 m_allPartConnectorItems.removeAt(i);
3005 delete connectorItems;
3006 }
3007 }
3008 }
3009
optimizeTraces(QList<int> & order,QMultiHash<int,QList<QPointer<TraceWire>>> & bundles,QMultiHash<int,Via * > & vias,QMultiHash<int,JumperItem * > & jumperItems,QMultiHash<int,SymbolPaletteItem * > & netLabels,NetList & netList,ConnectionThing & connectionThing)3010 void MazeRouter::optimizeTraces(QList<int> & order, QMultiHash<int, QList< QPointer<TraceWire> > > & bundles,
3011 QMultiHash<int, Via *> & vias, QMultiHash<int, JumperItem *> & jumperItems, QMultiHash<int, SymbolPaletteItem *> & netLabels,
3012 NetList & netList, ConnectionThing & connectionThing)
3013 {
3014 QList<ViewLayer::ViewLayerPlacement> layerSpecs;
3015 layerSpecs << ViewLayer::NewBottom;
3016 if (m_bothSidesNow) layerSpecs << ViewLayer::NewTop;
3017 QRectF r2(0, 0, m_boardImage->width(), m_boardImage->height());
3018 QPointF topLeft = m_maxRect.topLeft();
3019
3020 //QList<int> order2(order);
3021 //order2.append(order);
3022
3023 int progress = order.count();
3024
3025 foreach (int netIndex, order) {
3026 emit setProgressValue(progress++);
3027 Net * net = netList.nets.at(netIndex);
3028 foreach (ViewLayer::ViewLayerPlacement layerSpec, layerSpecs) {
3029 fastCopy(m_boardImage, m_spareImage);
3030
3031 QDomDocument * masterDoc = m_masterDocs.value(layerSpec);
3032 //QString before = masterDoc->toString();
3033 Markers markers;
3034 initMarkers(markers, m_pcbType);
3035 NetElements netElements;
3036 DRC::splitNetPrep(masterDoc, *(net->net), markers, netElements.net, netElements.alsoNet, netElements.notNet, true);
3037 foreach (QDomElement element, netElements.net) {
3038 element.setTagName("g");
3039 }
3040 foreach (QDomElement element, netElements.alsoNet) {
3041 element.setTagName("g");
3042 }
3043
3044 ItemBase::renderOne(masterDoc, m_spareImage, r2);
3045
3046 //QString after = masterDoc->toString();
3047
3048 foreach (QDomElement element, netElements.net) {
3049 element.setTagName(element.attribute("former"));
3050 element.removeAttribute("net");
3051 }
3052 foreach (QDomElement element, netElements.alsoNet) {
3053 element.setTagName(element.attribute("former"));
3054 element.removeAttribute("net");
3055 }
3056 foreach (QDomElement element, netElements.notNet) {
3057 element.removeAttribute("net");
3058 }
3059
3060 QPainter painter;
3061 painter.begin(m_spareImage);
3062 QPen pen = painter.pen();
3063 pen.setColor(0xff000000);
3064
3065 QBrush brush(QColor(0xff000000));
3066 painter.setBrush(brush);
3067 foreach (int otherIndex, order) {
3068 if (otherIndex == netIndex) continue;
3069
3070 foreach(QList< QPointer<TraceWire> > bundle, bundles.values(otherIndex)) {
3071 if (bundle.count() == 0) continue;
3072 if (ViewLayer::specFromID(bundle.at(0)->viewLayerID()) != layerSpec) continue;
3073
3074 pen.setWidthF((bundle.at(0)->width() + m_keepoutPixels + m_keepoutPixels) * OptimizeFactor);
3075 painter.setPen(pen);
3076 foreach (TraceWire * traceWire, bundle) {
3077 if (traceWire == NULL) continue;
3078
3079 QPointF p1 = (traceWire->connector0()->sceneAdjustedTerminalPoint(NULL) - topLeft) * OptimizeFactor;
3080 QPointF p2 = (traceWire->connector1()->sceneAdjustedTerminalPoint(NULL) - topLeft) * OptimizeFactor;
3081 painter.drawLine(p1, p2);
3082 }
3083 }
3084
3085 painter.setPen(Qt::NoPen);
3086
3087 foreach (Via * via, vias.values(otherIndex)) {
3088 QPointF p = (via->connectorItem()->sceneAdjustedTerminalPoint(NULL) - topLeft) * OptimizeFactor;
3089 double rad = ((via->connectorItem()->sceneBoundingRect().width() / 2) + m_keepoutPixels) * OptimizeFactor;
3090 painter.drawEllipse(p, rad, rad);
3091 }
3092 foreach (JumperItem * jumperItem, jumperItems.values(otherIndex)) {
3093 QPointF p = (jumperItem->connector0()->sceneAdjustedTerminalPoint(NULL) - topLeft) * OptimizeFactor;
3094 double rad = ((jumperItem->connector0()->sceneBoundingRect().width() / 2) + m_keepoutPixels) * OptimizeFactor;
3095 painter.drawEllipse(p, rad, rad);
3096 p = (jumperItem->connector1()->sceneAdjustedTerminalPoint(NULL) - topLeft) * OptimizeFactor;
3097 painter.drawEllipse(p, rad, rad);
3098 }
3099 foreach (SymbolPaletteItem * netLabel, netLabels.values(otherIndex)) {
3100 QRectF r = netLabel->sceneBoundingRect();
3101 painter.drawRect((r.left() - topLeft.x() - m_keepoutPixels) * OptimizeFactor,
3102 (r.top() - topLeft.y() - m_keepoutPixels) * OptimizeFactor,
3103 (r.width() + m_keepoutPixels) * OptimizeFactor,
3104 (r.height() + m_keepoutPixels) * OptimizeFactor);
3105 }
3106 }
3107
3108 foreach (SymbolPaletteItem * netLabel, netLabels.values(netIndex)) {
3109 QRectF r = netLabel->sceneBoundingRect();
3110 painter.drawRect((r.left() - topLeft.x() - m_keepoutPixels) * OptimizeFactor,
3111 (r.top() - topLeft.y() - m_keepoutPixels) * OptimizeFactor,
3112 (r.width() + m_keepoutPixels) * OptimizeFactor,
3113 (r.height() + m_keepoutPixels) * OptimizeFactor);
3114 }
3115
3116 painter.end();
3117
3118 #ifndef QT_NO_DEBUG
3119 //m_spareImage->save(FolderUtils::getUserDataStorePath("") + QString("/optimizeObstacles%1_%2.png").arg(netIndex, 2, 10, QChar('0')).arg(layerSpec));
3120 #endif
3121
3122 // finally test all combinations of each bundle
3123 // identify traces in bundles with source and dest that cannot be deleted
3124 // remove source/dest (delete and keep QPointers?)
3125 // schematic view must replace with two 90-degree lines
3126
3127 foreach(QList< QPointer<TraceWire> > bundle, bundles.values(netIndex)) {
3128 if (bundle.count() == 0) continue;
3129
3130 for (int i = bundle.count() - 1; i >= 0; i--) {
3131 TraceWire * traceWire = bundle.at(i);
3132 if (traceWire == NULL) bundle.removeAt(i);
3133 }
3134
3135 if (ViewLayer::specFromID(bundle.at(0)->viewLayerID()) != layerSpec) {
3136 // all wires in a single bundle are in the same layer
3137 continue;
3138 }
3139
3140 /*
3141 QList<ConnectorItem *> tos = connectionThing.values(bundle.first()->connector0());
3142 foreach (ConnectorItem * to, tos) {
3143 if (to->attachedToItemType() == ModelPart::Via) {
3144 to->debugInfo("start hooked to via");
3145 }
3146 }
3147 tos = connectionThing.values(bundle.last()->connector1());
3148 foreach (ConnectorItem * to, tos) {
3149 if (to->attachedToItemType() == ModelPart::Via) {
3150 to->debugInfo("end hooked to via");
3151 }
3152 }
3153 */
3154
3155 QVector<QPointF> points(bundle.count() + 1, QPointF(0, 0));
3156 QVector<bool> splits(bundle.count() + 1, false);
3157 int index = 0;
3158 foreach (TraceWire * traceWire, bundle) {
3159 if (connectionThing.multi(traceWire->connector0())) splits.replace(index, true);
3160 points.replace(index, traceWire->connector0()->sceneAdjustedTerminalPoint(NULL));
3161 index++;
3162 if (connectionThing.multi(traceWire->connector1())) splits.replace(index, true);
3163 points.replace(index, traceWire->connector1()->sceneAdjustedTerminalPoint(NULL));
3164 }
3165
3166 splits.replace(0, false);
3167 splits.replace(splits.count() - 1, true);
3168
3169 QList<QPointF> pointsSoFar;
3170 QList<TraceWire *> bundleSoFar;
3171 int startIndex = 0;
3172 for (int pix = 0; pix < points.count(); pix++) {
3173 pointsSoFar << points.at(pix);
3174 if (pix < points.count() - 1) {
3175 bundleSoFar << bundle.at(pix);
3176 }
3177 if (splits.at(pix)) {
3178 reducePoints(pointsSoFar, topLeft, bundleSoFar, startIndex, pix, connectionThing, netIndex, layerSpec);
3179 pointsSoFar.clear();
3180 bundleSoFar.clear();
3181 pointsSoFar << points.at(pix);
3182 if (pix < points.count() - 1) bundleSoFar << bundle.at(pix);
3183 startIndex = pix;
3184 }
3185 }
3186 }
3187 }
3188 }
3189 }
3190
reducePoints(QList<QPointF> & points,QPointF topLeft,QList<TraceWire * > & bundle,int startIndex,int endIndex,ConnectionThing & connectionThing,int netIndex,ViewLayer::ViewLayerPlacement layerSpec)3191 void MazeRouter::reducePoints(QList<QPointF> & points, QPointF topLeft, QList<TraceWire *> & bundle, int startIndex, int endIndex, ConnectionThing & connectionThing, int netIndex, ViewLayer::ViewLayerPlacement layerSpec) {
3192 Q_UNUSED(netIndex);
3193 Q_UNUSED(layerSpec);
3194 #ifndef QT_NO_DEBUG
3195 //int inc = 0;
3196 #endif
3197 double width = bundle.at(0)->width() * OptimizeFactor;
3198 for (int separation = endIndex - startIndex; separation > 1; separation--) {
3199 for (int ix = 0; ix < points.count() - separation; ix++) {
3200 QPointF p1 = (points.at(ix) - topLeft) * OptimizeFactor;
3201 QPointF p2 = (points.at(ix + separation) - topLeft) * OptimizeFactor;
3202 double minX = qMax(0.0, qMin(p1.x(), p2.x()) - width);
3203 double minY = qMax(0.0, qMin(p1.y(), p2.y()) - width);
3204 double maxX = qMin(m_spareImage2->width() - 1.0, qMax(p1.x(), p2.x()) + width);
3205 double maxY = qMin(m_spareImage2->height() - 1.0, qMax(p1.y(), p2.y()) + width);
3206 int corners = 1;
3207 if (!m_pcbType) {
3208 if (qAbs(p1.x() - p2.x()) >= 1 && qAbs(p1.y() - p2.y()) >= 1) {
3209 corners = 2;
3210 if (separation == 2) continue; // since we already have two lines, do nothing
3211 }
3212 }
3213 for (int corner = 0; corner < corners; corner++) {
3214 m_spareImage2->fill(0xffffffff);
3215 QPainter painter;
3216 painter.begin(m_spareImage2);
3217 QPen pen = painter.pen();
3218 pen.setColor(0xff000000);
3219 pen.setWidthF(width);
3220 painter.setPen(pen);
3221 if (corners == 1) {
3222 painter.drawLine(p1, p2);
3223 }
3224 else {
3225 if (corner == 0) {
3226 // vertical then horizontal
3227 painter.drawLine(p1.x(), p1.y(), p1.x(), p2.y());
3228 painter.drawLine(p1.x(), p2.y(), p2.x(), p2.y());
3229 }
3230 else {
3231 // horizontal then vertical
3232 painter.drawLine(p1.x(), p1.y(), p2.x(), p1.y());
3233 painter.drawLine(p2.x(), p1.y(), p2.x(), p2.y());
3234 }
3235 }
3236 painter.end();
3237 #ifndef QT_NO_DEBUG
3238 //m_spareImage2->save(FolderUtils::getUserDataStorePath("") + QString("/optimizeTrace%1_%2_%3.png").arg(netIndex,2,10,QChar('0')).arg(layerSpec).arg(inc++,3,10,QChar('0')));
3239 #endif
3240
3241 bool overlaps = false;
3242 for (int y = minY; y <= maxY && !overlaps; y++) {
3243 for (int x = minX; x <= maxX && !overlaps; x++) {
3244 if (m_spareImage->pixel(x, y) == 0xffffffff) continue;
3245 if (m_spareImage2->pixel(x, y) == 0xffffffff) continue;
3246 overlaps = true;
3247 }
3248 }
3249
3250 if (overlaps) continue;
3251
3252 TraceWire * traceWire = bundle.at(ix);
3253 TraceWire * last = bundle.at(ix + separation - 1);
3254 TraceWire * next = bundle.at(ix + 1);
3255 QList<ConnectorItem *> newDests = connectionThing.values(last->connector1());
3256 QPointF unop_p2 = (p2 / OptimizeFactor) + topLeft;
3257 if (corners == 2) {
3258 TraceWire * afterNext = bundle.at(ix + 2);
3259 QPointF middle;
3260 if (corner == 0) {
3261 middle.setX(p1.x());
3262 middle.setY(p2.y());
3263 }
3264 else {
3265 middle.setX(p2.x());
3266 middle.setY(p1.y());
3267 }
3268 middle = (middle / OptimizeFactor) + topLeft;
3269 traceWire->setLineAnd(QLineF(QPointF(0, 0), middle - traceWire->pos()), traceWire->pos(), true);
3270 traceWire->saveGeometry();
3271 traceWire->update();
3272 next->setLineAnd(QLineF(QPointF(0, 0), unop_p2 - middle), middle, true);
3273 next->saveGeometry();
3274 next->update();
3275 foreach (ConnectorItem * newDest, newDests) {
3276 connectionThing.add(next->connector1(), newDest);
3277 }
3278 connectionThing.remove(next->connector1(), afterNext->connector0());
3279 for (int i = 1; i < separation - 1; i++) {
3280 TraceWire * tw = bundle.takeAt(ix + 2);
3281 connectionThing.remove(tw->connector0());
3282 connectionThing.remove(tw->connector1());
3283 ModelPart * modelPart = tw->modelPart();
3284 delete tw;
3285 modelPart->setParent(NULL);
3286 delete modelPart;
3287 points.removeAt(ix + 2);
3288 }
3289 points.replace(ix + 1, middle);
3290 }
3291 else {
3292 traceWire->setLineAnd(QLineF(QPointF(0, 0), unop_p2 - traceWire->pos()), traceWire->pos(), true);
3293 traceWire->saveGeometry();
3294 traceWire->update();
3295 foreach (ConnectorItem * newDest, newDests) {
3296 connectionThing.add(traceWire->connector1(), newDest);
3297 }
3298 connectionThing.remove(traceWire->connector1(), next->connector0());
3299 for (int i = 0; i < separation - 1; i++) {
3300 TraceWire * tw = bundle.takeAt(ix + 1);
3301 connectionThing.remove(tw->connector0());
3302 connectionThing.remove(tw->connector1());
3303 ModelPart * modelPart = tw->modelPart();
3304 delete tw;
3305 modelPart->setParent(NULL);
3306 delete modelPart;
3307 points.removeAt(ix + 1);
3308 }
3309 }
3310 break;
3311 }
3312 }
3313 }
3314 }
3315