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.a
10
11 Fritzing is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Fritzing. If not, see <http://www.gnu.org/licenses/>.
18
19 ********************************************************************
20
21 $Revision: 6947 $:
22 $Author: irascibl@gmail.com $:
23 $Date: 2013-04-03 06:45:22 +0200 (Mi, 03. Apr 2013) $
24
25 ********************************************************************/
26
27 #include "autorouter.h"
28 #include "../sketch/pcbsketchwidget.h"
29 #include "../debugdialog.h"
30 #include "../items/symbolpaletteitem.h"
31 #include "../items/virtualwire.h"
32 #include "../items/tracewire.h"
33 #include "../items/jumperitem.h"
34 #include "../items/via.h"
35 #include "../utils/graphicsutils.h"
36 #include "../connectors/connectoritem.h"
37 #include "../items/moduleidnames.h"
38 #include "../processeventblocker.h"
39 #include "../referencemodel/referencemodel.h"
40
41 #include <qmath.h>
42 #include <QApplication>
43 #include <QSettings>
44
45 const QString Autorouter::MaxCyclesName("cmrouter/maxcycles");
46
Autorouter(PCBSketchWidget * sketchWidget)47 Autorouter::Autorouter(PCBSketchWidget * sketchWidget)
48 {
49 m_sketchWidget = sketchWidget;
50 m_useBest = m_stopTracing = m_cancelTrace = m_cancelled = false;
51 }
52
~Autorouter(void)53 Autorouter::~Autorouter(void)
54 {
55 }
56
cleanUpNets()57 void Autorouter::cleanUpNets() {
58 foreach (QList<ConnectorItem *> * connectorItems, m_allPartConnectorItems) {
59 delete connectorItems;
60 }
61 m_allPartConnectorItems.clear();
62 }
63
updateRoutingStatus()64 void Autorouter::updateRoutingStatus() {
65 RoutingStatus routingStatus;
66 routingStatus.zero();
67 m_sketchWidget->updateRoutingStatus(routingStatus, true);
68 }
69
drawOneTrace(QPointF fromPos,QPointF toPos,double width,ViewLayer::ViewLayerPlacement viewLayerPlacement)70 TraceWire * Autorouter::drawOneTrace(QPointF fromPos, QPointF toPos, double width, ViewLayer::ViewLayerPlacement viewLayerPlacement)
71 {
72 //DebugDialog::debug(QString("trace %1,%2 %3,%4").arg(fromPos.x()).arg(fromPos.y()).arg(toPos.x()).arg(toPos.y()));
73 #ifndef QT_NO_DEBUG
74 if (qAbs(fromPos.x() - toPos.x()) < 0.01 && qAbs(fromPos.y() - toPos.y()) < 0.01) {
75 DebugDialog::debug("zero length trace", fromPos);
76 }
77 #endif
78
79 long newID = ItemBase::getNextID();
80 ViewGeometry viewGeometry;
81 viewGeometry.setWireFlags(m_sketchWidget->getTraceFlag());
82 viewGeometry.setAutoroutable(true);
83 viewGeometry.setLoc(fromPos);
84 QLineF line(0, 0, toPos.x() - fromPos.x(), toPos.y() - fromPos.y());
85 viewGeometry.setLine(line);
86
87 ItemBase * trace = m_sketchWidget->addItem(m_sketchWidget->referenceModel()->retrieveModelPart(ModuleIDNames::WireModuleIDName),
88 viewLayerPlacement, BaseCommand::SingleView, viewGeometry, newID, -1, NULL);
89 if (trace == NULL) {
90 // we're in trouble
91 DebugDialog::debug("autorouter unable to draw one trace");
92 return NULL;
93 }
94
95 // addItem calls trace->setSelected(true) so unselect it (TODO: this may no longer be necessar)
96 trace->setSelected(false);
97 TraceWire * traceWire = dynamic_cast<TraceWire *>(trace);
98 if (traceWire == NULL) {
99 DebugDialog::debug("autorouter unable to draw one trace as trace");
100 return NULL;
101 }
102
103
104 m_sketchWidget->setClipEnds(traceWire, false);
105 traceWire->setColorString(m_sketchWidget->traceColor(viewLayerPlacement), 1.0, false);
106 traceWire->setWireWidth(width, m_sketchWidget, m_sketchWidget->getWireStrokeWidth(traceWire, width));
107
108 return traceWire;
109 }
110
cancel()111 void Autorouter::cancel() {
112 m_cancelled = true;
113 }
114
cancelTrace()115 void Autorouter::cancelTrace() {
116 m_cancelTrace = true;
117 }
118
stopTracing()119 void Autorouter::stopTracing() {
120 m_stopTracing = true;
121 }
122
useBest()123 void Autorouter::useBest() {
124 m_useBest = m_stopTracing = true;
125 }
126
initUndo(QUndoCommand * parentCommand)127 void Autorouter::initUndo(QUndoCommand * parentCommand)
128 {
129 // autoroutable traces, jumpers and vias are saved on the undo command and deleted
130 // non-autoroutable traces, jumpers and via are not deleted
131
132 QList<ItemBase *> toDelete;
133 QList<QGraphicsItem *> collidingItems;
134 if (m_pcbType) {
135 collidingItems = m_sketchWidget->scene()->collidingItems(m_board);
136 foreach (QGraphicsItem * item, collidingItems) {
137 JumperItem * jumperItem = dynamic_cast<JumperItem *>(item);
138 if (jumperItem == NULL) continue;
139
140 if (jumperItem->getAutoroutable()) {
141 addUndoConnection(false, jumperItem, parentCommand);
142 toDelete.append(jumperItem);
143 continue;
144 }
145
146 // deal with the traces connecting the jumperitem to the part
147 QList<ConnectorItem *> both;
148 foreach (ConnectorItem * ci, jumperItem->connector0()->connectedToItems()) both.append(ci);
149 foreach (ConnectorItem * ci, jumperItem->connector1()->connectedToItems()) both.append(ci);
150 foreach (ConnectorItem * connectorItem, both) {
151 TraceWire * w = qobject_cast<TraceWire *>(connectorItem->attachedTo());
152 if (w == NULL) continue;
153 if (!w->isTraceType(m_sketchWidget->getTraceFlag())) continue;
154
155 QList<Wire *> wires;
156 QList<ConnectorItem *> ends;
157 w->collectChained(wires, ends);
158 foreach (Wire * wire, wires) {
159 // make sure the jumper item doesn't lose its wires
160 wire->setAutoroutable(false);
161 }
162 }
163 }
164 foreach (QGraphicsItem * item, collidingItems) {
165 Via * via = dynamic_cast<Via *>(item);
166 if (via == NULL) continue;
167
168 if (via->getAutoroutable()) {
169 addUndoConnection(false, via, parentCommand);
170 toDelete.append(via);
171 continue;
172 }
173
174 // deal with the traces connecting the via to the part
175 QList<ConnectorItem *> both;
176 foreach (ConnectorItem * ci, via->connectorItem()->connectedToItems()) both.append(ci);
177 foreach (ConnectorItem * ci, via->connectorItem()->getCrossLayerConnectorItem()->connectedToItems()) both.append(ci);
178 foreach (ConnectorItem * connectorItem, both) {
179 TraceWire * w = qobject_cast<TraceWire *>(connectorItem->attachedTo());
180 if (w == NULL) continue;
181 if (!w->isTraceType(m_sketchWidget->getTraceFlag())) continue;
182
183 QList<Wire *> wires;
184 QList<ConnectorItem *> ends;
185 w->collectChained(wires, ends);
186 foreach (Wire * wire, wires) {
187 // make sure the via doesn't lose its wires
188 wire->setAutoroutable(false);
189 }
190 }
191 }
192 }
193 else {
194 collidingItems = m_sketchWidget->scene()->items();
195 foreach (QGraphicsItem * item, collidingItems) {
196 SymbolPaletteItem * netLabel = dynamic_cast<SymbolPaletteItem *>(item);
197 if (netLabel == NULL) continue;
198 if (!netLabel->isOnlyNetLabel()) continue;
199
200 if (netLabel->getAutoroutable()) {
201 addUndoConnection(false, netLabel, parentCommand);
202 toDelete.append(netLabel);
203 continue;
204 }
205
206 // deal with the traces connecting the netlabel to the part
207 foreach (ConnectorItem * connectorItem, netLabel->connector0()->connectedToItems()) {
208 TraceWire * w = qobject_cast<TraceWire *>(connectorItem->attachedTo());
209 if (w == NULL) continue;
210 if (!w->isTraceType(m_sketchWidget->getTraceFlag())) continue;
211
212 QList<Wire *> wires;
213 QList<ConnectorItem *> ends;
214 w->collectChained(wires, ends);
215 foreach (Wire * wire, wires) {
216 // make sure the netlabel doesn't lose its wires
217 wire->setAutoroutable(false);
218 }
219 }
220 }
221 }
222
223 QList<TraceWire *> visited;
224 foreach (QGraphicsItem * item, collidingItems) {
225 TraceWire * traceWire = dynamic_cast<TraceWire *>(item);
226 if (traceWire == NULL) continue;
227 if (!traceWire->isTraceType(m_sketchWidget->getTraceFlag())) continue;
228 if (traceWire->getAutoroutable()) continue;
229 if (visited.contains(traceWire)) continue;
230
231 QList<Wire *> wires;
232 QList<ConnectorItem *> ends;
233 traceWire->collectChained(wires, ends);
234 foreach (Wire * wire, wires) {
235 visited << qobject_cast<TraceWire *>(wire);
236 if (wire->getAutoroutable()) {
237 wire->setAutoroutable(false);
238 }
239 }
240 }
241
242 foreach (QGraphicsItem * item, collidingItems) {
243 TraceWire * traceWire = dynamic_cast<TraceWire *>(item);
244 if (traceWire == NULL) continue;
245 if (!traceWire->isTraceType(m_sketchWidget->getTraceFlag())) continue;
246 if (!traceWire->getAutoroutable()) continue;
247
248 toDelete.append(traceWire);
249 addUndoConnection(false, traceWire, parentCommand);
250 }
251
252 foreach (ItemBase * itemBase, toDelete) {
253 m_sketchWidget->makeDeleteItemCommand(itemBase, BaseCommand::CrossView, parentCommand);
254 }
255
256 foreach (ItemBase * itemBase, toDelete) {
257 m_sketchWidget->deleteItem(itemBase, true, true, false);
258 }
259 }
260
addUndoConnection(bool connect,Via * via,QUndoCommand * parentCommand)261 void Autorouter::addUndoConnection(bool connect, Via * via, QUndoCommand * parentCommand) {
262 addUndoConnection(connect, via->connectorItem(), BaseCommand::CrossView, parentCommand);
263 addUndoConnection(connect, via->connectorItem()->getCrossLayerConnectorItem(), BaseCommand::CrossView, parentCommand);
264 }
265
addUndoConnection(bool connect,SymbolPaletteItem * netLabel,QUndoCommand * parentCommand)266 void Autorouter::addUndoConnection(bool connect, SymbolPaletteItem * netLabel, QUndoCommand * parentCommand) {
267 addUndoConnection(connect, netLabel->connector0(), BaseCommand::CrossView, parentCommand);
268 }
269
addUndoConnection(bool connect,JumperItem * jumperItem,QUndoCommand * parentCommand)270 void Autorouter::addUndoConnection(bool connect, JumperItem * jumperItem, QUndoCommand * parentCommand) {
271 addUndoConnection(connect, jumperItem->connector0(), BaseCommand::CrossView, parentCommand);
272 addUndoConnection(connect, jumperItem->connector1(), BaseCommand::CrossView, parentCommand);
273 }
274
addUndoConnection(bool connect,TraceWire * traceWire,QUndoCommand * parentCommand)275 void Autorouter::addUndoConnection(bool connect, TraceWire * traceWire, QUndoCommand * parentCommand) {
276 addUndoConnection(connect, traceWire->connector0(), BaseCommand::CrossView, parentCommand);
277 addUndoConnection(connect, traceWire->connector1(), BaseCommand::CrossView, parentCommand);
278 }
279
addUndoConnection(bool connect,ConnectorItem * connectorItem,BaseCommand::CrossViewType crossView,QUndoCommand * parentCommand)280 void Autorouter::addUndoConnection(bool connect, ConnectorItem * connectorItem, BaseCommand::CrossViewType crossView, QUndoCommand * parentCommand)
281 {
282 foreach (ConnectorItem * toConnectorItem, connectorItem->connectedToItems()) {
283 VirtualWire * vw = qobject_cast<VirtualWire *>(toConnectorItem->attachedTo());
284 if (vw != NULL) continue;
285
286 ChangeConnectionCommand * ccc = new ChangeConnectionCommand(m_sketchWidget, crossView,
287 toConnectorItem->attachedToID(), toConnectorItem->connectorSharedID(),
288 connectorItem->attachedToID(), connectorItem->connectorSharedID(),
289 ViewLayer::specFromID(toConnectorItem->attachedToViewLayerID()),
290 connect, parentCommand);
291 ccc->setUpdateConnections(false);
292 }
293 }
294
restoreOriginalState(QUndoCommand * parentCommand)295 void Autorouter::restoreOriginalState(QUndoCommand * parentCommand) {
296 QUndoStack undoStack;
297 undoStack.push(parentCommand);
298 undoStack.undo();
299 }
300
clearTracesAndJumpers()301 void Autorouter::clearTracesAndJumpers() {
302 QList<ItemBase *> toDelete;
303
304 foreach (QGraphicsItem * item, (m_board == NULL) ? m_sketchWidget->scene()->items() : m_sketchWidget->scene()->collidingItems(m_board)) {
305 if (m_pcbType) {
306 JumperItem * jumperItem = dynamic_cast<JumperItem *>(item);
307 if (jumperItem != NULL) {
308 if (jumperItem->getAutoroutable()) {
309 toDelete.append(jumperItem);
310 }
311 continue;
312 }
313 Via * via = dynamic_cast<Via *>(item);
314 if (via != NULL) {
315 if (via->getAutoroutable()) {
316 toDelete.append(via);
317 }
318 continue;
319 }
320 }
321 else {
322 SymbolPaletteItem * netLabel = dynamic_cast<SymbolPaletteItem *>(item);
323 if (netLabel != NULL && netLabel->isOnlyNetLabel()) {
324 if (netLabel->getAutoroutable()) {
325 toDelete.append(netLabel);
326 }
327 continue;
328 }
329 }
330
331 TraceWire * traceWire = dynamic_cast<TraceWire *>(item);
332 if (traceWire != NULL) {
333 if (traceWire->isTraceType(m_sketchWidget->getTraceFlag()) && traceWire->getAutoroutable()) {
334 toDelete.append(traceWire);
335 }
336 continue;
337 }
338 }
339
340 foreach (ItemBase * itemBase, toDelete) {
341 m_sketchWidget->deleteItem(itemBase, true, true, false);
342 }
343 }
344
doCancel(QUndoCommand * parentCommand)345 void Autorouter::doCancel(QUndoCommand * parentCommand) {
346 emit setProgressMessage(tr("Routing canceled! Now cleaning up..."));
347 ProcessEventBlocker::processEvents();
348 restoreOriginalState(parentCommand);
349 cleanUpNets();
350 }
351
addToUndo(QUndoCommand * parentCommand)352 void Autorouter::addToUndo(QUndoCommand * parentCommand)
353 {
354 QList<TraceWire *> wires;
355 QList<JumperItem *> jumperItems;
356 QList<Via *> vias;
357 QList<SymbolPaletteItem *> netLabels;
358 foreach (QGraphicsItem * item, (m_board == NULL) ? m_sketchWidget->scene()->items() : m_sketchWidget->scene()->collidingItems(m_board)) {
359 TraceWire * wire = dynamic_cast<TraceWire *>(item);
360 if (wire != NULL) {
361 if (!wire->getAutoroutable()) continue;
362 if (!wire->isTraceType(m_sketchWidget->getTraceFlag())) continue;
363
364 m_sketchWidget->setClipEnds(wire, true);
365 wire->update();
366 addWireToUndo(wire, parentCommand);
367 wires.append(wire);
368 continue;
369 }
370 if (m_pcbType) {
371 JumperItem * jumperItem = dynamic_cast<JumperItem *>(item);
372 if (jumperItem != NULL) {
373 jumperItems.append(jumperItem);
374 if (!jumperItem->getAutoroutable()) {
375 continue;
376 }
377
378 jumperItem->saveParams();
379 QPointF pos, c0, c1;
380 jumperItem->getParams(pos, c0, c1);
381
382 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::JumperModuleIDName, jumperItem->viewLayerPlacement(), jumperItem->getViewGeometry(), jumperItem->id(), false, -1, parentCommand);
383 new ResizeJumperItemCommand(m_sketchWidget, jumperItem->id(), pos, c0, c1, pos, c0, c1, parentCommand);
384 new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, jumperItem->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
385
386 continue;
387 }
388 Via * via = dynamic_cast<Via *>(item);
389 if (via != NULL) {
390 vias.append(via);
391 if (!via->getAutoroutable()) {
392 continue;
393 }
394
395 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::ViaModuleIDName, via->viewLayerPlacement(), via->getViewGeometry(), via->id(), false, -1, parentCommand);
396 new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, via->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
397 new SetPropCommand(m_sketchWidget, via->id(), "hole size", via->holeSize(), via->holeSize(), true, parentCommand);
398
399 continue;
400 }
401 }
402 else {
403 SymbolPaletteItem * netLabel = dynamic_cast<SymbolPaletteItem *>(item);
404 if (netLabel != NULL && netLabel->isOnlyNetLabel()) {
405 netLabels.append(netLabel);
406 if (!netLabel->getAutoroutable()) {
407 continue;
408 }
409
410 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, netLabel->moduleID(), netLabel->viewLayerPlacement(), netLabel->getViewGeometry(), netLabel->id(), false, -1, parentCommand);
411 new SetPropCommand(m_sketchWidget, netLabel->id(), "label", netLabel->label(), netLabel->label(), true, parentCommand);
412
413 continue;
414 }
415
416 }
417 }
418
419 foreach (TraceWire * traceWire, wires) {
420 //traceWire->debugInfo("trace");
421 addUndoConnection(true, traceWire, parentCommand);
422 }
423 foreach (JumperItem * jumperItem, jumperItems) {
424 addUndoConnection(true, jumperItem, parentCommand);
425 }
426 foreach (Via * via, vias) {
427 addUndoConnection(true, via, parentCommand);
428 }
429 foreach (SymbolPaletteItem * netLabel, netLabels) {
430 addUndoConnection(true, netLabel, parentCommand);
431 }
432 }
433
addWireToUndo(Wire * wire,QUndoCommand * parentCommand)434 void Autorouter::addWireToUndo(Wire * wire, QUndoCommand * parentCommand)
435 {
436 if (wire == NULL) return;
437
438 new AddItemCommand(m_sketchWidget, BaseCommand::CrossView, ModuleIDNames::WireModuleIDName, wire->viewLayerPlacement(), wire->getViewGeometry(), wire->id(), false, -1, parentCommand);
439 new CheckStickyCommand(m_sketchWidget, BaseCommand::SingleView, wire->id(), false, CheckStickyCommand::RemoveOnly, parentCommand);
440
441 new WireWidthChangeCommand(m_sketchWidget, wire->id(), wire->width(), wire->width(), parentCommand);
442 new WireColorChangeCommand(m_sketchWidget, wire->id(), wire->colorString(), wire->colorString(), wire->opacity(), wire->opacity(), parentCommand);
443 }
444
setMaxCycles(int maxCycles)445 void Autorouter::setMaxCycles(int maxCycles)
446 {
447 m_maxCycles = maxCycles;
448 QSettings settings;
449 settings.setValue(MaxCyclesName, maxCycles);
450 }
451
452