1 /*******************************************************************
2
3 Part of the Fritzing project - http://fritzing.org
4 Copyright (c) 2007-2014 Fachhochschule Potsdam - http://fh-potsdam.de
5
6 Fritzing is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 Fritzing is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Fritzing. If not, see <http://www.gnu.org/licenses/>.
18
19 ********************************************************************
20
21 This router is based on the one described in Contour: A Tile-based Gridless Router
22 http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-3.pdf
23
24 Plus additional ideas from An Efficient Tile-Based ECO Router with Routing Graph Reduction
25 http://www.cis.nctu.edu.tw/~ylli/paper/f69-li.pdf
26
27 The corner stitching code is a modified version of code from the Magic VLSI Layout Tool
28 http://opencircuitdesign.com/magic/
29
30 ********************************************************************
31
32 $Revision: 6976 $:
33 $Author: irascibl@gmail.com $:
34 $Date: 2013-04-21 09:50:09 +0200 (So, 21. Apr 2013) $
35
36 ********************************************************************/
37
38 // TODO:
39 //
40 // run separate beginning overlap check with half keepout width?
41 //
42 // would be nice to eliminate ratsnests as we go
43 //
44 // think of orderings like simulated annealing or genetic algorithms
45 //
46 // option to turn off propagation feedback?
47 // remove debugging output and extra calls to processEvents
48 //
49 // still seeing a few thin tiles going across the board:
50 // this is because the thick tiles above and below are wider than the thin tile
51 //
52 // slide corner: if dogleg is too close to other connectors, slide it more towards the middle
53 //
54 // bugs:
55 // why does the same routing task give different results (qSort?)
56 // especially annoying in schematic view when sometimes wires flow along wires and sometimes don't, for the same routing task
57 // border seems asymmetric
58 // still some funny shaped routes (thin tile problem?)
59 // jumper item: sometimes one end doesn't route
60 // schematic view: some lines still overlap
61 // split_original_wire.fz shouldn't have two jumpers
62 // stepper motor example: not putting jumper item in space to the left of a connector where there is clearly open space
63 // is this due to a blocking thin tile?
64 // some traces violate drc
65 //
66 // catching 1st repeat to end rip-up-and-reroute is not valid
67 //
68 // longer route than expected:
69 // It is possible that the shortest tile route is actually longer than the shortest crow-fly route.
70 // For example, in the following case, route ABC will reach goal before ABDEF:
71 // -------
72 // | A |
73 // ------------------------------------
74 // | B |
75 // ------------------------------------
76 // | | | D |
77 // | | --------------
78 // | C | | E |
79 // | | -------------------
80 // | | | F |
81 // ------------------------------------------
82 // | GOAL |
83 // ------------------------------------------
84 // There is a way to deal with this in the following paper: http://eie507.eie.polyu.edu.hk/projects/sp-tiles-00980255.pdf
85 //
86 //
87
88 #include "cmrouter.h"
89 #include "../../sketch/pcbsketchwidget.h"
90 #include "../../debugdialog.h"
91 #include "../../items/virtualwire.h"
92 #include "../../items/tracewire.h"
93 #include "../../items/jumperitem.h"
94 #include "../../items/via.h"
95 #include "../../items/resizableboard.h"
96 #include "../../utils/graphicsutils.h"
97 #include "../../utils/graphutils.h"
98 #include "../../utils/textutils.h"
99 #include "../../connectors/connectoritem.h"
100 #include "../../items/moduleidnames.h"
101 #include "../../processeventblocker.h"
102 #include "../../svg/groundplanegenerator.h"
103 #include "../../svg/svgfilesplitter.h"
104 #include "../../fsvgrenderer.h"
105
106 #include "tile.h"
107 #include "tileutils.h"
108
109 #include <qmath.h>
110 #include <limits>
111 #include <QApplication>
112 #include <QMessageBox>
113 //#include <QElapsedTimer> // forces a dependency on qt 4.7
114 #include <QSettings>
115 #include <QCryptographicHash>
116
117 static const int MaximumProgress = 1000;
118 static int TileStandardWireWidth = 0;
119 static int TileHalfStandardWireWidth = 0;
120 static double StandardWireWidth = 0;
121 static double HalfStandardWireWidth = 0;
122 static const double CloseEnough = 0.5;
123 static const int GridEntryAlpha = 128;
124
125 //static qint64 seedNextTime = 0;
126 //static qint64 propagateUnitTime = 0;
127
128 static const int DefaultMaxCycles = 10;
129
130 #ifndef QT_NO_DEBUG
131 #define DGI(item) drawGridItem(item)
132 #else
133 #define DGI(item) Q_UNUSED(item)
134 #endif
135
dot(const QPointF & p1,const QPointF & p2)136 static inline double dot(const QPointF & p1, const QPointF & p2)
137 {
138 return (p1.x() * p2.x()) + (p1.y() * p2.y());
139 }
140
tilePointRectXLessThan(TilePointRect * tpr1,TilePointRect * tpr2)141 bool tilePointRectXLessThan(TilePointRect * tpr1, TilePointRect * tpr2)
142 {
143 return tpr1->tilePoint.xi <= tpr2->tilePoint.xi;
144 }
145
tilePointRectYGreaterThan(TilePointRect * tpr1,TilePointRect * tpr2)146 bool tilePointRectYGreaterThan(TilePointRect * tpr1, TilePointRect * tpr2)
147 {
148 return tpr1->tilePoint.yi >= tpr2->tilePoint.yi;
149 }
150
151 ///////////////////////////////////////////////
152 //
153 // tile functions
154
infoTile(const QString & message,Tile * tile)155 static inline void infoTile(const QString & message, Tile * tile)
156 {
157 if (tile == NULL) {
158 DebugDialog::debug("infoTile: tile is NULL");
159 return;
160 }
161
162 DebugDialog::debug(QString("tile:%1 lb:%2 bl:%3 tr:%4 rt%5")
163 .arg((long) tile, 0, 16)
164 .arg((long) tile->ti_lb, 0, 16)
165 .arg((long) tile->ti_bl, 0, 16)
166 .arg((long) tile->ti_tr, 0, 16)
167 .arg((long) tile->ti_rt, 0, 16));
168
169 DebugDialog::debug(QString("%1 tile:%2 l:%3 t:%4 w:%5 h:%6 type:%7 body:%8")
170 .arg(message)
171 .arg((long) tile, 0, 16)
172 .arg(LEFT(tile))
173 .arg(YMIN(tile))
174 .arg(WIDTH(tile))
175 .arg(HEIGHT(tile))
176 .arg(TiGetType(tile))
177 .arg((long) TiGetBody(tile), 0, 16)
178 );
179 }
180
infoTileRect(const QString & message,const TileRect & tileRect)181 static inline void infoTileRect(const QString & message, const TileRect & tileRect)
182 {
183 DebugDialog::debug(QString("%1 l:%2 t:%3 w:%4 h:%5")
184 .arg(message)
185 .arg(tileRect.xmini)
186 .arg(tileRect.ymini)
187 .arg(tileRect.xmaxi - tileRect.xmini)
188 .arg(tileRect.ymaxi - tileRect.ymini)
189 );
190 }
191
manhattan(TileRect & tr1,TileRect & tr2)192 static inline int manhattan(TileRect & tr1, TileRect & tr2) {
193 int dx = qAbs(tr1.xmaxi - tr2.xmaxi);
194 dx = qMin(qAbs(tr1.xmaxi - tr2.xmini), dx);
195 dx = qMin(qAbs(tr1.xmini - tr2.xmaxi), dx);
196 dx = qMin(qAbs(tr1.xmini - tr2.xmini), dx);
197 int dy = qAbs(tr1.ymaxi - tr2.ymaxi);
198 dy = qMin(qAbs(tr1.ymaxi - tr2.ymini), dy);
199 dy = qMin(qAbs(tr1.ymini - tr2.ymaxi), dy);
200 dy = qMin(qAbs(tr1.ymini - tr2.ymini), dy);
201 return dx + dy;
202 }
203
TiGetGridEntry(Tile * tile)204 static inline GridEntry * TiGetGridEntry(Tile * tile) { return dynamic_cast<GridEntry *>(TiGetClient(tile)); }
205
extendToBounds(TileRect & from,TileRect & to)206 void extendToBounds(TileRect & from, TileRect & to) {
207 // bail if it already extends to or past the bounds
208 if (from.xmini <= to.xmini) return;
209 if (from.xmaxi >= to.xmaxi) return;
210 if (from.ymini <= to.ymini) return;
211 if (from.ymaxi >= to.ymaxi) return;
212
213 int which = 0;
214 int dmin = from.xmini - to.xmini;
215 if (to.xmaxi - from.xmaxi < dmin) {
216 which = 1;
217 dmin = to.xmaxi - from.xmaxi;
218 }
219 if (from.ymini - to.ymini < dmin) {
220 which = 2;
221 dmin = from.ymini - to.ymini;
222 }
223 if (to.ymaxi - from.ymaxi < dmin) {
224 which = 3;
225 dmin = to.ymaxi - from.ymaxi;
226 }
227 switch(which) {
228 case 0:
229 from.xmini = to.xmini;
230 return;
231 case 1:
232 from.xmaxi = to.xmaxi;
233 return;
234 case 2:
235 from.ymini = to.ymini;
236 return;
237 case 3:
238 from.ymaxi = to.ymaxi;
239 return;
240 default:
241 break;
242 }
243 }
244
245
246 ////////////////////////////////////////////////////////////////////
247 //
248 // tile crawling functions
249
checkAlready(Tile * tile,UserData userData)250 int checkAlready(Tile * tile, UserData userData) {
251 switch (TiGetType(tile)) {
252 case Tile::SPACE:
253 case Tile::SPACE2:
254 case Tile::SCHEMATICWIRESPACE:
255 case Tile::BUFFER:
256 return 0;
257 default:
258 break;
259 }
260
261 QList<Tile *> * tiles = (QList<Tile *> *) userData;
262 tiles->append(tile);
263 return 0;
264 }
265
prepDeleteTile(Tile * tile,UserData userData)266 int prepDeleteTile(Tile * tile, UserData userData) {
267 switch(TiGetType(tile)) {
268 case Tile::DUMMYLEFT:
269 case Tile::DUMMYRIGHT:
270 case Tile::DUMMYTOP:
271 case Tile::DUMMYBOTTOM:
272 return 0;
273 default:
274 break;
275 }
276
277 //infoTile("prep delete", tile);
278 QSet<Tile *> * tiles = (QSet<Tile *> *) userData;
279 tiles->insert(tile);
280
281 return 0;
282 }
283
284 ////////////////////////////////////////////////////////////////////
285
GridEntry(QRectF & r,QGraphicsItem * parent)286 GridEntry::GridEntry(QRectF & r, QGraphicsItem * parent) : QGraphicsRectItem(r, parent)
287 {
288 m_drawn = false;
289 setAcceptedMouseButtons(Qt::NoButton);
290 setAcceptHoverEvents(false);
291 }
292
drawn()293 bool GridEntry::drawn() {
294 return m_drawn;
295 }
296
setDrawn(bool d)297 void GridEntry::setDrawn(bool d) {
298 m_drawn = d;
299 }
300
301 ////////////////////////////////////////////////////////////////////
302
CMRouter(PCBSketchWidget * sketchWidget,ItemBase * board,bool adjustIf)303 CMRouter::CMRouter(PCBSketchWidget * sketchWidget, ItemBase * board, bool adjustIf) : QObject()
304 {
305 m_board = board;
306 m_sketchWidget = sketchWidget;
307
308 m_unionPlane = m_union90Plane = NULL;
309
310 if (m_board) {
311 m_maxRect = m_board->sceneBoundingRect();
312 }
313 else {
314 m_maxRect = m_sketchWidget->scene()->itemsBoundingRect();
315 if (adjustIf) {
316 m_maxRect.adjust(-m_maxRect.width() / 2, -m_maxRect.height() / 2, m_maxRect.width() / 2, m_maxRect.height() / 2);
317 }
318 }
319
320 QMatrix matrix90;
321 matrix90.rotate(90);
322 m_maxRect90 = matrix90.mapRect(m_maxRect);
323
324 qrectToTile(m_maxRect, m_tileMaxRect);
325
326 setUpWidths(m_sketchWidget->getAutorouterTraceWidth());
327 }
328
~CMRouter()329 CMRouter::~CMRouter()
330 {
331 }
332
initPlane(bool rotate90)333 Plane * CMRouter::initPlane(bool rotate90) {
334 Tile * bufferTile = TiAlloc();
335 TiSetType(bufferTile, Tile::BUFFER);
336 TiSetBody(bufferTile, NULL);
337
338 QRectF bufferRect(rotate90 ? m_maxRect90 : m_maxRect);
339
340 TileRect br;
341 qrectToTile(bufferRect, br);
342
343 bufferRect.adjust(-bufferRect.width(), -bufferRect.height(), bufferRect.width(), bufferRect.height());
344 //DebugDialog::debug("max rect", m_maxRect);
345 //DebugDialog::debug("max rect 90", m_maxRect90);
346
347
348 int l = fasterRealToTile(bufferRect.left());
349 int t = fasterRealToTile(bufferRect.top());
350 int r = fasterRealToTile(bufferRect.right());
351 int b = fasterRealToTile(bufferRect.bottom());
352 SETLEFT(bufferTile, l);
353 SETYMIN(bufferTile, t); // TILE is Math Y-axis not computer-graphic Y-axis
354
355 Plane * thePlane = TiNewPlane(bufferTile, br.xmini, br.ymini, br.xmaxi, br.ymaxi);
356
357 SETRIGHT(bufferTile, r);
358 SETYMAX(bufferTile, b); // TILE is Math Y-axis not computer-graphic Y-axis
359
360 // do not use InsertTile here
361 TiInsertTile(thePlane, &thePlane->maxRect, NULL, Tile::SPACE);
362 //infoTileRect("insert", thePlane->maxRect);
363
364 return thePlane;
365 }
366
367 /*
368 void CMRouter::shortenUs(QList<QPointF> & allPoints, JSubedge * subedge)
369 {
370 // TODO: this could be implemented recursively as a child tile space
371 // with the goals being the sides of the U-shape and the obstacles copied in from the parent tile space
372 // for now just look for a straight line
373 int ix = 0;
374 while (ix < allPoints.count() - 3) {
375 QPointF p0 = allPoints.at(ix);
376 QPointF p1 = allPoints.at(ix + 1);
377 QPointF p2 = allPoints.at(ix + 2);
378 QPointF p3 = allPoints.at(ix + 3);
379 ix += 1;
380
381 TileRect tileRect;
382 if (p1.x() == p2.x()) {
383 if ((p0.x() > p1.x() && p3.x() > p2.x()) || (p0.x() < p1.x() && p3.x() < p2.x())) {
384 // opening to left or right
385 bool targetGreater;
386 if (p0.x() < p1.x()) {
387 // opening left
388 targetGreater = false;
389 realsToTile(tileRect, qMax(p0.x(), p3.x()), qMin(p0.y(), p3.y()), p2.x(), qMax(p0.y(), p3.y()));
390 }
391 else {
392 // opening right
393 targetGreater = true;
394 realsToTile(tileRect, p2.x(), qMin(p0.y(), p3.y()), qMin(p0.x(), p3.x()), qMax(p0.y(), p3.y()));
395 }
396
397 if (findShortcut(tileRect, true, targetGreater, subedge, allPoints, ix - 1)) {
398 ix--;
399 }
400 }
401 else {
402 // not a U-shape
403 continue;
404 }
405 }
406 else if (p1.y() == p2.y()) {
407 if ((p0.y() > p1.y() && p3.y() > p2.y()) || (p0.y() < p1.y() && p3.y() < p2.y())) {
408 // opening to top or bottom
409 bool targetGreater;
410 if (p0.y() < p1.y()) {
411 // opening top
412 targetGreater = false;
413 realsToTile(tileRect, qMin(p0.x(), p3.x()), qMax(p0.y(), p3.y()), qMax(p0.x(), p3.x()), p2.y());
414 }
415 else {
416 // opening bottom
417 targetGreater = true;
418 realsToTile(tileRect, qMin(p0.x(), p3.x()), p2.y(), qMax(p0.x(), p3.x()), qMin(p0.y(), p3.y()));
419 }
420
421 if (findShortcut(tileRect, false, targetGreater, subedge, allPoints, ix - 1)) {
422 ix--;
423 }
424 }
425 else {
426 // not a U-shape
427 continue;
428 }
429 }
430
431 }
432 }
433 */
434
drawGridItem(Tile * tile)435 GridEntry * CMRouter::drawGridItem(Tile * tile)
436 {
437 return NULL;
438
439 if (tile == NULL) return NULL;
440
441 QRectF r;
442 tileToQRect(tile, r);
443
444 GridEntry * gridEntry = TiGetGridEntry(tile);
445 if (gridEntry == NULL) {
446 gridEntry = new GridEntry(r, NULL);
447 gridEntry->setZValue(m_sketchWidget->getTopZ());
448 TiSetClient(tile, gridEntry);
449 }
450 else {
451 QRectF br = gridEntry->boundingRect();
452 if (br != r) {
453 gridEntry->setRect(r);
454 gridEntry->setDrawn(false);
455 }
456 }
457
458 if (gridEntry->drawn()) return gridEntry;
459
460 QColor c;
461 switch (TiGetType(tile)) {
462 case Tile::SPACE:
463 c = QColor(255, 255, 0, GridEntryAlpha);
464 break;
465 case Tile::SPACE2:
466 c = QColor(200, 200, 0, GridEntryAlpha);
467 break;
468 case Tile::SOURCE:
469 c = QColor(0, 255, 0, GridEntryAlpha);
470 break;
471 case Tile::DESTINATION:
472 c = QColor(0, 0, 255, GridEntryAlpha);
473 break;
474 case Tile::SCHEMATICWIRESPACE:
475 c = QColor(255, 192, 203, GridEntryAlpha);
476 break;
477 case Tile::OBSTACLE:
478 c = QColor(60, 60, 60, GridEntryAlpha);
479 break;
480 default:
481 c = QColor(255, 0, 0, GridEntryAlpha);
482 break;
483 }
484
485 gridEntry->setPen(c);
486 gridEntry->setBrush(QBrush(c));
487 if (gridEntry->scene() == NULL) {
488 m_sketchWidget->scene()->addItem(gridEntry);
489 }
490 gridEntry->show();
491 gridEntry->setDrawn(true);
492 ProcessEventBlocker::processEvents();
493 return gridEntry;
494 }
495
addTile(NonConnectorItem * nci,Tile::TileType type,Plane * thePlane,QList<Tile * > & alreadyTiled,CMRouter::OverlapType overlapType)496 Tile * CMRouter::addTile(NonConnectorItem * nci, Tile::TileType type, Plane * thePlane, QList<Tile *> & alreadyTiled, CMRouter::OverlapType overlapType)
497 {
498 QRectF r = nci->attachedTo()->mapRectToScene(nci->rect());
499 TileRect tileRect;
500 realsToTile(tileRect, r.left() - m_keepoutPixels, r.top() - m_keepoutPixels, r.right() + m_keepoutPixels, r.bottom() + m_keepoutPixels);
501 Tile * tile = insertTile(thePlane, tileRect, alreadyTiled, nci, type, overlapType);
502 DGI(tile);
503 return tile;
504 }
505
hideTiles()506 void CMRouter::hideTiles()
507 {
508 foreach (QGraphicsItem * item, m_sketchWidget->items()) {
509 GridEntry * gridEntry = dynamic_cast<GridEntry *>(item);
510 if (gridEntry) gridEntry->setVisible(false);
511 }
512 }
513
clearPlane(Plane * thePlane)514 void CMRouter::clearPlane(Plane * thePlane)
515 {
516 if (thePlane == NULL) return;
517
518 QSet<Tile *> tiles;
519
520 //infoTileRect("clear", thePlane->maxRect);
521
522 TiSrArea(NULL, thePlane, &thePlane->maxRect, prepDeleteTile, &tiles);
523 foreach (Tile * tile, tiles) {
524 TiFree(tile);
525 }
526
527 TiFreePlane(thePlane);
528 }
529
displayBadTiles(QList<Tile * > & alreadyTiled)530 void CMRouter::displayBadTiles(QList<Tile *> & alreadyTiled) {
531 //hideTiles();
532 foreach (Tile * tile, alreadyTiled) {
533 TileRect tileRect;
534 TiToRect(tile, &tileRect);
535 displayBadTileRect(tileRect);
536 }
537 displayBadTileRect(m_overlappingTileRect);
538 }
539
displayBadTileRect(TileRect & tileRect)540 void CMRouter::displayBadTileRect(TileRect & tileRect) {
541 QRectF r;
542 tileRectToQRect(tileRect, r);
543 GridEntry * gridEntry = new GridEntry(r, NULL);
544 gridEntry->setZValue(m_sketchWidget->getTopZ());
545 QColor c(255, 0, 0, GridEntryAlpha);
546 gridEntry->setPen(c);
547 gridEntry->setBrush(QBrush(c));
548 m_sketchWidget->scene()->addItem(gridEntry);
549 gridEntry->show();
550 ProcessEventBlocker::processEvents();
551 }
552
553
insertTile(Plane * thePlane,QRectF & rect,QList<Tile * > & alreadyTiled,QGraphicsItem * item,Tile::TileType tileType,CMRouter::OverlapType overlapType)554 Tile * CMRouter::insertTile(Plane * thePlane, QRectF & rect, QList<Tile *> & alreadyTiled, QGraphicsItem * item, Tile::TileType tileType, CMRouter::OverlapType overlapType)
555 {
556 TileRect tileRect;
557 qrectToTile(rect, tileRect);
558 return insertTile(thePlane, tileRect, alreadyTiled, item, tileType, overlapType);
559 }
560
insertTile(Plane * thePlane,TileRect & tileRect,QList<Tile * > &,QGraphicsItem * item,Tile::TileType tileType,CMRouter::OverlapType overlapType)561 Tile * CMRouter::insertTile(Plane * thePlane, TileRect & tileRect, QList<Tile *> &, QGraphicsItem * item, Tile::TileType tileType, CMRouter::OverlapType overlapType)
562 {
563 //infoTileRect("insert tile", tileRect);
564 if (tileRect.xmaxi - tileRect.xmini <= 0 || tileRect.ymaxi - tileRect.ymini <= 0) {
565 DebugDialog::debug("attempting to insert zero width tile");
566 return NULL;
567 }
568
569 if (tileRect.xmaxi > thePlane->maxRect.xmaxi) {
570 tileRect.xmaxi = thePlane->maxRect.xmaxi;
571 }
572 if (tileRect.xmini < thePlane->maxRect.xmini) {
573 tileRect.xmini = thePlane->maxRect.xmini;
574 }
575
576 if (tileRect.ymaxi > thePlane->maxRect.ymaxi) {
577 tileRect.ymaxi = thePlane->maxRect.ymaxi;
578 }
579 if (tileRect.ymini < thePlane->maxRect.ymini) {
580 tileRect.ymini = thePlane->maxRect.ymini;
581 }
582
583 if (tileRect.xmaxi - tileRect.xmini <= 0 || tileRect.ymaxi - tileRect.ymini <= 0) {
584 return NULL;
585 }
586
587 bool gotOverlap = false;
588 if (overlapType != CMRouter::IgnoreAllOverlaps) {
589 //TiSrArea(NULL, thePlane, &tileRect, checkAlready, &alreadyTiled);
590 }
591
592 if (gotOverlap) {
593 m_overlappingTileRect = tileRect;
594 DebugDialog::debug("!!!!!!!!!!!!!!!!!!!!!!! overlaps not allowed !!!!!!!!!!!!!!!!!!!!!!");
595 return NULL;
596 }
597 Tile * newTile = TiInsertTile(thePlane, &tileRect, item, tileType);
598 insertUnion(tileRect, item, tileType);
599
600 DGI(newTile);
601 return newTile;
602 }
603
overlapsOnly(QGraphicsItem *,QList<Tile * > & alreadyTiled)604 bool CMRouter::overlapsOnly(QGraphicsItem *, QList<Tile *> & alreadyTiled)
605 {
606 bool doClip = false;
607 for (int i = alreadyTiled.count() - 1; i >= 0; i--) {
608 Tile * intersectingTile = alreadyTiled.at(i);
609 if (dynamic_cast<Wire *>(TiGetBody(intersectingTile)) != NULL || dynamic_cast<ConnectorItem *>(TiGetBody(intersectingTile)) != NULL) {
610 doClip = true;
611 continue;
612 }
613
614 alreadyTiled.removeAt(i);
615 }
616
617 return doClip;
618 }
619
allowEquipotentialOverlaps(QGraphicsItem * item,QList<Tile * > & alreadyTiled)620 bool CMRouter::allowEquipotentialOverlaps(QGraphicsItem * item, QList<Tile *> & alreadyTiled)
621 {
622 bool collected = false;
623 QList<ConnectorItem *> equipotential;
624 Wire * w = dynamic_cast<Wire *>(item);
625 if (w) {
626 equipotential.append(w->connector0());
627 }
628 else {
629 ConnectorItem * ci = dynamic_cast<ConnectorItem *>(item);
630 equipotential.append(ci);
631 }
632
633 foreach (Tile * intersectingTile, alreadyTiled) {
634 QGraphicsItem * bodyItem = TiGetBody(intersectingTile);
635 ConnectorItem * ci = dynamic_cast<ConnectorItem *>(bodyItem);
636 if (ci != NULL) {
637 if (!collected) {
638 ConnectorItem::collectEqualPotential(equipotential, false, ViewGeometry::NoFlag);
639 collected = true;
640 }
641 if (!equipotential.contains(ci)) {
642 // overlap not allowed
643 //infoTile("intersecting", intersectingTile);
644 return false;
645 }
646 }
647 else {
648 Wire * w = dynamic_cast<Wire *>(bodyItem);
649 if (w == NULL) return false;
650
651 if (!collected) {
652 ConnectorItem::collectEqualPotential(equipotential, false, ViewGeometry::NoFlag);
653 collected = true;
654 }
655
656 if (!equipotential.contains(w->connector0())) {
657 // overlap not allowed
658 //infoTile("intersecting", intersectingTile);
659 return false;
660 }
661 }
662 }
663
664 return true;
665
666 }
667
clearGridEntries()668 void CMRouter::clearGridEntries() {
669 foreach (QGraphicsItem * item, m_sketchWidget->scene()->items()) {
670 GridEntry * gridEntry = dynamic_cast<GridEntry *>(item);
671 if (gridEntry == NULL) continue;
672
673 delete gridEntry;
674 }
675 }
676
insideV(const QPointF & check,const QPointF & vertex)677 bool CMRouter::insideV(const QPointF & check, const QPointF & vertex)
678 {
679 // form the V from p2
680
681 QPointF lv(vertex.x() - 10 + vertex.y() - check.y(), check.y() + 10);
682 QPointF rv(vertex.x() + 10 - vertex.y() + check.y(), check.y() + 10);
683
684 // the rest of this from: http://www.blackpawn.com/texts/pointinpoly/default.html
685
686 QPointF v0 = rv - vertex;
687 QPointF v1 = lv - vertex;
688 QPointF v2 = check - vertex;
689
690 // Compute dot products
691 double dot00 = dot(v0, v0);
692 double dot01 = dot(v0, v1);
693 double dot02 = dot(v0, v2);
694 double dot11 = dot(v1, v1);
695 double dot12 = dot(v1, v2);
696
697 // Compute barycentric coordinates
698 double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
699 double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
700 double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
701
702 // Check if point is in or on triangle
703 return (u >= 0) && (v >= 0) && (u + v <= 1);
704 }
705
insertUnion(TileRect & tileRect,QGraphicsItem *,Tile::TileType tileType)706 void CMRouter::insertUnion(TileRect & tileRect, QGraphicsItem *, Tile::TileType tileType) {
707 if (m_unionPlane == NULL) return;
708 if (tileType == Tile::SPACE) return;
709 if (tileType == Tile::SPACE2) return;
710
711 TiInsertTile(m_unionPlane, &tileRect, NULL, Tile::OBSTACLE);
712 //infoTileRect("union", tileRect);
713
714 TileRect tileRect90;
715 tileRotate90(tileRect, tileRect90);
716
717 if (tileRect90.xmaxi > m_union90Plane->maxRect.xmaxi) {
718 tileRect90.xmaxi = m_union90Plane->maxRect.xmaxi;
719 }
720 if (tileRect90.xmini < m_union90Plane->maxRect.xmini) {
721 tileRect90.xmini = m_union90Plane->maxRect.xmini;
722 }
723
724 if (tileRect90.ymaxi > m_union90Plane->maxRect.ymaxi) {
725 tileRect90.ymaxi = m_union90Plane->maxRect.ymaxi;
726 }
727 if (tileRect90.ymini < m_union90Plane->maxRect.ymini) {
728 tileRect90.ymini = m_union90Plane->maxRect.ymini;
729 }
730
731 if (tileRect90.xmaxi - tileRect90.xmini <= 0 || tileRect90.ymaxi - tileRect90.ymini <= 0) {
732 return;
733 }
734
735 TiInsertTile(m_union90Plane, &tileRect90, NULL, Tile::OBSTACLE);
736 }
737
drawTileRect(TileRect & tileRect,QColor & color)738 void CMRouter::drawTileRect(TileRect & tileRect, QColor & color)
739 {
740 QRectF r;
741 tileRectToQRect(tileRect, r);
742 GridEntry * gridEntry = new GridEntry(r, NULL);
743 gridEntry->setZValue(m_sketchWidget->getTopZ());
744 gridEntry->setPen(color);
745 gridEntry->setBrush(QBrush(color));
746 m_sketchWidget->scene()->addItem(gridEntry);
747 gridEntry->show();
748 //ProcessEventBlocker::processEvents();
749 }
750
boardRect()751 TileRect CMRouter::boardRect() {
752 return m_tileMaxRect;
753 }
754
setUpWidths(double width)755 void CMRouter::setUpWidths(double width)
756 {
757 StandardWireWidth = width;
758 TileStandardWireWidth = fasterRealToTile(StandardWireWidth);
759 HalfStandardWireWidth = StandardWireWidth / 2;
760 TileHalfStandardWireWidth = fasterRealToTile(HalfStandardWireWidth);
761 }
762
setKeepout(double keepout)763 void CMRouter::setKeepout(double keepout)
764 {
765 m_keepoutPixels = keepout;
766 }
767
drcClean()768 void CMRouter::drcClean()
769 {
770 clearGridEntries();
771 if (m_unionPlane) {
772 clearPlane(m_unionPlane);
773 m_unionPlane = NULL;
774 }
775 if (m_union90Plane) {
776 clearPlane(m_union90Plane);
777 m_union90Plane = NULL;
778 }
779 }
780
781