diff options
-rw-r--r-- | CMakeLists.txt | 6 | ||||
-rw-r--r-- | common/nextpnr.h | 5 | ||||
-rw-r--r-- | common/placer1.cc | 11 | ||||
-rw-r--r-- | gui/basewindow.cc | 8 | ||||
-rw-r--r-- | gui/designwidget.cc | 28 | ||||
-rw-r--r-- | gui/designwidget.h | 8 | ||||
-rw-r--r-- | gui/fpgaviewwidget.cc | 506 | ||||
-rw-r--r-- | gui/fpgaviewwidget.h | 170 | ||||
-rw-r--r-- | gui/lineshader.cc | 2 | ||||
-rw-r--r-- | gui/quadtree.h | 425 | ||||
-rw-r--r-- | tests/gui/quadtree.cc | 127 | ||||
-rw-r--r-- | tests/ice40/hx1k.cc | 2 | ||||
-rw-r--r-- | tests/ice40/hx8k.cc | 2 | ||||
-rw-r--r-- | tests/ice40/lp1k.cc | 2 | ||||
-rw-r--r-- | tests/ice40/lp384.cc | 2 | ||||
-rw-r--r-- | tests/ice40/lp8k.cc | 2 | ||||
-rw-r--r-- | tests/ice40/up5k.cc | 2 |
17 files changed, 1192 insertions, 116 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 55e57763..cc712e72 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -191,8 +191,12 @@ foreach (family ${ARCH}) # Add any new per-architecture targets here if (BUILD_TESTS) aux_source_directory(tests/${family}/ ${ufamily}_TEST_FILES) + if (BUILD_GUI) + aux_source_directory(tests/gui/ GUI_TEST_FILES) + endif() - add_executable(nextpnr-${family}-test ${${ufamily}_TEST_FILES} ${COMMON_FILES} ${${ufamily}_FILES}) + add_executable(nextpnr-${family}-test ${${ufamily}_TEST_FILES} + ${COMMON_FILES} ${${ufamily}_FILES} ${GUI_TEST_FILES}) target_link_libraries(nextpnr-${family}-test PRIVATE gtest_main) add_sanitizers(nextpnr-${family}-test) diff --git a/common/nextpnr.h b/common/nextpnr.h index 5e32d5b6..908b8266 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -204,6 +204,11 @@ struct DecalXY { DecalId decal; float x = 0, y = 0; + + bool operator==(const DecalXY &other) const + { + return (decal == other.decal && x == other.x && y == other.y); + } }; struct BelPin diff --git a/common/placer1.cc b/common/placer1.cc index 4659da11..ee7225b5 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -75,10 +75,10 @@ class SAPlacer bool place() { log_break(); + ctx->lock(); size_t placed_cells = 0; // Initial constraints placer - ctx->lock(); for (auto &cell_entry : ctx->cells) { CellInfo *cell = cell_entry.second.get(); auto loc = cell->attrs.find(ctx->id("BEL")); @@ -112,6 +112,7 @@ class SAPlacer } int constr_placed_cells = placed_cells; log_info("Placed %d cells based on constraints.\n", int(placed_cells)); + ctx->yield(); // Sort to-place cells for deterministic initial placement std::vector<CellInfo *> autoplaced; @@ -123,28 +124,25 @@ class SAPlacer } std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; }); ctx->shuffle(autoplaced); - ctx->unlock(); // Place cells randomly initially log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size())); for (auto cell : autoplaced) { - ctx->lock(); place_initial(cell); placed_cells++; if ((placed_cells - constr_placed_cells) % 500 == 0) log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells), int(autoplaced.size())); - ctx->unlock(); } if ((placed_cells - constr_placed_cells) % 500 != 0) log_info(" initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells), int(autoplaced.size())); + ctx->yield(); log_info("Running simulated annealing placer.\n"); // Calculate metric after initial placement - ctx->lock(); curr_metric = 0; curr_tns = 0; for (auto &net : ctx->nets) { @@ -152,7 +150,6 @@ class SAPlacer metrics[net.first] = wl; curr_metric += wl; } - ctx->unlock(); int n_no_progress = 0; double avg_metric = curr_metric; @@ -249,7 +246,7 @@ class SAPlacer ctx->yield(); } // Final post-pacement validitiy check - ctx->lock(); + ctx->yield(); for (auto bel : ctx->getBels()) { IdString cell = ctx->getBoundBelCell(bel); if (!ctx->isBelLocationValid(bel)) { diff --git a/gui/basewindow.cc b/gui/basewindow.cc index e07200de..6e997011 100644 --- a/gui/basewindow.cc +++ b/gui/basewindow.cc @@ -2,6 +2,7 @@ * nextpnr -- Next Generation Place and Route
*
* Copyright (C) 2018 Miodrag Milanovic <miodrag@symbioticeda.com>
+ * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
@@ -80,8 +81,11 @@ BaseMainWindow::BaseMainWindow(std::unique_ptr<Context> context, QWidget *parent centralTabWidget->tabBar()->tabButton(0, QTabBar::RightSide)->resize(0, 0);
connect(this, SIGNAL(contextChanged(Context *)), fpgaView, SLOT(newContext(Context *)));
- connect(designview, SIGNAL(selected(std::vector<DecalXY>)), fpgaView,
- SLOT(onSelectedArchItem(std::vector<DecalXY>)));
+ connect(designview, SIGNAL(selected(std::vector<DecalXY>, bool)), fpgaView,
+ SLOT(onSelectedArchItem(std::vector<DecalXY>, bool)));
+ connect(fpgaView, SIGNAL(clickedBel(BelId, bool)), designview, SLOT(onClickedBel(BelId, bool)));
+ connect(fpgaView, SIGNAL(clickedWire(WireId, bool)), designview, SLOT(onClickedWire(WireId, bool)));
+ connect(fpgaView, SIGNAL(clickedPip(PipId, bool)), designview, SLOT(onClickedPip(PipId, bool)));
connect(designview, SIGNAL(highlight(std::vector<DecalXY>, int)), fpgaView,
SLOT(onHighlightGroupChanged(std::vector<DecalXY>, int)));
diff --git a/gui/designwidget.cc b/gui/designwidget.cc index 43964edf..d55c84e9 100644 --- a/gui/designwidget.cc +++ b/gui/designwidget.cc @@ -2,6 +2,7 @@ * nextpnr -- Next Generation Place and Route
*
* Copyright (C) 2018 Miodrag Milanovic <miodrag@symbioticeda.com>
+ * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
@@ -507,6 +508,27 @@ QtProperty *DesignWidget::addSubGroup(QtProperty *topItem, const QString &name) return item;
}
+void DesignWidget::onClickedBel(BelId bel, bool keep)
+{
+ QTreeWidgetItem *item = nameToItem[getElementIndex(ElementType::BEL)].value(ctx->getBelName(bel).c_str(ctx));
+ treeWidget->setCurrentItem(item);
+ Q_EMIT selected(getDecals(ElementType::BEL, ctx->getBelName(bel)), keep);
+}
+
+void DesignWidget::onClickedWire(WireId wire, bool keep)
+{
+ QTreeWidgetItem *item = nameToItem[getElementIndex(ElementType::WIRE)].value(ctx->getWireName(wire).c_str(ctx));
+ treeWidget->setCurrentItem(item);
+ Q_EMIT selected(getDecals(ElementType::WIRE, ctx->getWireName(wire)), keep);
+}
+
+void DesignWidget::onClickedPip(PipId pip, bool keep)
+{
+ QTreeWidgetItem *item = nameToItem[getElementIndex(ElementType::PIP)].value(ctx->getPipName(pip).c_str(ctx));
+ treeWidget->setCurrentItem(item);
+ Q_EMIT selected(getDecals(ElementType::PIP, ctx->getPipName(pip)), keep);
+}
+
void DesignWidget::onItemSelectionChanged()
{
if (treeWidget->selectedItems().size() == 0)
@@ -520,7 +542,7 @@ void DesignWidget::onItemSelectionChanged() std::vector<DecalXY> d = getDecals(type, value);
std::move(d.begin(), d.end(), std::back_inserter(decals));
}
- Q_EMIT selected(decals);
+ Q_EMIT selected(decals, false);
return;
}
@@ -541,7 +563,7 @@ void DesignWidget::onItemSelectionChanged() clearProperties();
IdString c = static_cast<IdStringTreeItem *>(clickItem)->getData();
- Q_EMIT selected(getDecals(type, c));
+ Q_EMIT selected(getDecals(type, c), false);
if (type == ElementType::BEL) {
BelId bel = ctx->getBelByName(c);
@@ -833,7 +855,7 @@ void DesignWidget::prepareMenuProperty(const QPoint &pos) std::vector<DecalXY> d = getDecals(type, value);
std::move(d.begin(), d.end(), std::back_inserter(decals));
}
- Q_EMIT selected(decals);
+ Q_EMIT selected(decals, false);
});
menu.addAction(selectAction);
diff --git a/gui/designwidget.h b/gui/designwidget.h index 6d4b7fe1..60291cf3 100644 --- a/gui/designwidget.h +++ b/gui/designwidget.h @@ -37,7 +37,8 @@ enum class ElementType WIRE,
PIP,
NET,
- CELL
+ CELL,
+ GROUP
};
class DesignWidget : public QWidget
@@ -63,7 +64,7 @@ class DesignWidget : public QWidget void updateHighlightGroup(QList<QTreeWidgetItem *> item, int group);
Q_SIGNALS:
void info(std::string text);
- void selected(std::vector<DecalXY> decal);
+ void selected(std::vector<DecalXY> decal, bool keep);
void highlight(std::vector<DecalXY> decal, int group);
private Q_SLOTS:
@@ -74,6 +75,9 @@ class DesignWidget : public QWidget public Q_SLOTS:
void newContext(Context *ctx);
void updateTree();
+ void onClickedBel(BelId bel, bool keep);
+ void onClickedWire(WireId wire, bool keep);
+ void onClickedPip(PipId pip, bool keep);
private:
Context *ctx;
diff --git a/gui/fpgaviewwidget.cc b/gui/fpgaviewwidget.cc index de73e27b..ed25a187 100644 --- a/gui/fpgaviewwidget.cc +++ b/gui/fpgaviewwidget.cc @@ -31,11 +31,9 @@ NEXTPNR_NAMESPACE_BEGIN -FPGAViewWidget::FPGAViewWidget(QWidget *parent) : - QOpenGLWidget(parent), ctx_(nullptr), paintTimer_(this), - lineShader_(this), zoom_(500.0f), - rendererData_(new FPGAViewWidget::RendererData), - rendererArgs_(new FPGAViewWidget::RendererArgs) +FPGAViewWidget::FPGAViewWidget(QWidget *parent) + : QOpenGLWidget(parent), ctx_(nullptr), paintTimer_(this), lineShader_(this), zoom_(10.0f), + rendererArgs_(new FPGAViewWidget::RendererArgs), rendererData_(new FPGAViewWidget::RendererData) { colors_.background = QColor("#000000"); colors_.grid = QColor("#333"); @@ -44,6 +42,7 @@ FPGAViewWidget::FPGAViewWidget(QWidget *parent) : colors_.inactive = QColor("#303030"); colors_.active = QColor("#f0f0f0"); colors_.selected = QColor("#ff6600"); + colors_.hovered = QColor("#906030"); colors_.highlight[0] = QColor("#6495ed"); colors_.highlight[1] = QColor("#7fffd4"); colors_.highlight[2] = QColor("#98fb98"); @@ -53,7 +52,8 @@ FPGAViewWidget::FPGAViewWidget(QWidget *parent) : colors_.highlight[6] = QColor("#ff69b4"); colors_.highlight[7] = QColor("#da70d6"); - rendererArgs_->highlightedOrSelectedChanged = false; + rendererArgs_->changed = false; + rendererArgs_->flags.zoomOutbound = true; auto fmt = format(); fmt.setMajorVersion(3); @@ -75,6 +75,7 @@ FPGAViewWidget::FPGAViewWidget(QWidget *parent) : renderRunner_ = std::unique_ptr<PeriodicRunner>(new PeriodicRunner(this, [this] { renderLines(); })); renderRunner_->start(); renderRunner_->startTimer(1000 / 2); // render lines 2 times per second + setMouseTracking(true); } FPGAViewWidget::~FPGAViewWidget() {} @@ -82,9 +83,13 @@ FPGAViewWidget::~FPGAViewWidget() {} void FPGAViewWidget::newContext(Context *ctx) { ctx_ = ctx; - onSelectedArchItem(std::vector<DecalXY>()); + onSelectedArchItem(std::vector<DecalXY>(), false); for (int i = 0; i < 8; i++) onHighlightGroupChanged(std::vector<DecalXY>(), i); + { + QMutexLocker lock(&rendererArgsLock_); + rendererArgs_->flags.zoomOutbound = true; + } pokeRenderer(); } @@ -102,36 +107,112 @@ void FPGAViewWidget::initializeGL() 0.0); } -void FPGAViewWidget::drawGraphicElement(LineShaderData &out, const GraphicElement &el, float x, float y) +float FPGAViewWidget::PickedElement::distance(Context *ctx, float wx, float wy) const { - const float scale = 1.0; + // Get DecalXY for this element. + DecalXY dec = decal(ctx); + + // Coordinates within decal. + float dx = wx - dec.x; + float dy = wy - dec.y; + + auto graphics = ctx->getDecalGraphics(dec.decal); + if (graphics.size() == 0) + return -1; + + // TODO(q3k): For multi-line decals, find intersections and also calculate distance to them. + + // Go over its' GraphicElements, and calculate the distance to them. + std::vector<float> distances; + std::transform(graphics.begin(), graphics.end(), std::back_inserter(distances), + [&](const GraphicElement &ge) -> float { + switch (ge.type) { + case GraphicElement::TYPE_BOX: { + // If outside the box, return unit distance to closest border. + float outside_x = -1, outside_y = -1; + if (dx < ge.x1 || dx > ge.x2) { + outside_x = std::min(std::abs(dx - ge.x1), std::abs(dx - ge.x2)); + } + if (dy < ge.y1 || dy > ge.y2) { + outside_y = std::min(std::abs(dy - ge.y1), std::abs(dy - ge.y2)); + } + if (outside_x != -1 && outside_y != -1) + return std::min(outside_x, outside_y); + + // If in box, return 0. + return 0; + } + case GraphicElement::TYPE_LINE: + case GraphicElement::TYPE_ARROW: { + // Return somewhat primitively calculated distance to segment. + // TODO(q3k): consider coming up with a better algorithm + QVector2D w(wx, wy); + QVector2D a(ge.x1, ge.y1); + QVector2D b(ge.x2, ge.y2); + float dw = a.distanceToPoint(w) + b.distanceToPoint(w); + float dab = a.distanceToPoint(b); + return std::abs(dw - dab) / dab; + } + default: + // Not close to antyhing. + return -1; + } + }); + + // Find smallest non -1 distance. + // Find closest element. + return *std::min_element(distances.begin(), distances.end(), [&](float a, float b) { + if (a == -1) + return false; + if (b == -1) + return true; + return a < b; + }); +} +void FPGAViewWidget::renderGraphicElement(LineShaderData &out, PickQuadTree::BoundingBox &bb, const GraphicElement &el, + float x, float y) +{ if (el.type == GraphicElement::TYPE_BOX) { auto line = PolyLine(true); - line.point(x + scale * el.x1, y + scale * el.y1); - line.point(x + scale * el.x2, y + scale * el.y1); - line.point(x + scale * el.x2, y + scale * el.y2); - line.point(x + scale * el.x1, y + scale * el.y2); + line.point(x + el.x1, y + el.y1); + line.point(x + el.x2, y + el.y1); + line.point(x + el.x2, y + el.y2); + line.point(x + el.x1, y + el.y2); line.build(out); + + bb.setX0(std::min(bb.x0(), x + el.x1)); + bb.setY0(std::min(bb.y0(), y + el.y1)); + bb.setX1(std::max(bb.x1(), x + el.x2)); + bb.setY1(std::max(bb.y1(), y + el.y2)); + return; } if (el.type == GraphicElement::TYPE_LINE || el.type == GraphicElement::TYPE_ARROW) { - PolyLine(x + scale * el.x1, y + scale * el.y1, x + scale * el.x2, y + scale * el.y2) - .build(out); + PolyLine(x + el.x1, y + el.y1, x + el.x2, y + el.y2).build(out); + bb.setX0(std::min(bb.x0(), x + el.x1)); + bb.setY0(std::min(bb.y0(), y + el.y1)); + bb.setX1(std::max(bb.x1(), x + el.x2)); + bb.setY1(std::max(bb.y1(), y + el.y2)); + return; } } -void FPGAViewWidget::drawDecal(LineShaderData &out, const DecalXY &decal) +void FPGAViewWidget::renderDecal(LineShaderData &out, PickQuadTree::BoundingBox &bb, const DecalXY &decal) { + if (decal.decal == DecalId()) + return; + float offsetX = decal.x; float offsetY = decal.y; for (auto &el : ctx_->getDecalGraphics(decal.decal)) { - drawGraphicElement(out, el, offsetX, offsetY); + renderGraphicElement(out, bb, el, offsetX, offsetY); } } -void FPGAViewWidget::drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], const DecalXY &decal) +void FPGAViewWidget::renderArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], PickQuadTree::BoundingBox &bb, + const DecalXY &decal) { float offsetX = decal.x; float offsetY = decal.y; @@ -141,7 +222,7 @@ void FPGAViewWidget::drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX] case GraphicElement::STYLE_FRAME: case GraphicElement::STYLE_INACTIVE: case GraphicElement::STYLE_ACTIVE: - drawGraphicElement(out[el.style], el, offsetX, offsetY); + renderGraphicElement(out[el.style], bb, el, offsetX, offsetY); break; default: break; @@ -149,13 +230,48 @@ void FPGAViewWidget::drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX] } } +void FPGAViewWidget::populateQuadTree(RendererData *data, const DecalXY &decal, const PickedElement &element) +{ + float x = decal.x; + float y = decal.y; + + for (auto &el : ctx_->getDecalGraphics(decal.decal)) { + if (el.style == GraphicElement::STYLE_HIDDEN || el.style == GraphicElement::STYLE_FRAME) { + continue; + } + + if (el.type == GraphicElement::TYPE_BOX) { + // Boxes are bounded by themselves. + data->qt->insert(PickQuadTree::BoundingBox(x + el.x1, y + el.y1, x + el.x2, y + el.y2), element); + } + + if (el.type == GraphicElement::TYPE_LINE || el.type == GraphicElement::TYPE_ARROW) { + // Lines are bounded by their AABB slightly enlarged. + float x0 = x + el.x1; + float y0 = y + el.y1; + float x1 = x + el.x2; + float y1 = y + el.y2; + if (x1 < x0) + std::swap(x0, x1); + if (y1 < y0) + std::swap(y0, y1); + + x0 -= 0.01; + y0 -= 0.01; + x1 += 0.01; + y1 += 0.01; + + data->qt->insert(PickQuadTree::BoundingBox(x0, y0, x1, y1), element); + } + } +} + QMatrix4x4 FPGAViewWidget::getProjection(void) { QMatrix4x4 matrix; const float aspect = float(width()) / float(height()); - matrix.perspective(3.14 / 2, aspect, zoomNear_, zoomFar_); - matrix.translate(0.0f, 0.0f, -zoom_); + matrix.perspective(90, aspect, zoomNear_, zoomFar_); return matrix; } @@ -167,12 +283,14 @@ void FPGAViewWidget::paintGL() gl->glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); QMatrix4x4 matrix = getProjection(); + matrix.translate(0.0f, 0.0f, -zoom_); matrix *= viewMove_; // Calculate world thickness to achieve a screen 1px/1.1px line. - float thick1Px = mouseToWorldCoordinates(1, 0).x(); - float thick11Px = mouseToWorldCoordinates(1.1, 0).x(); + float thick1Px = mouseToWorldDimensions(1, 0).x(); + float thick11Px = mouseToWorldDimensions(1.1, 0).x(); + float thick2Px = mouseToWorldDimensions(2, 0).x(); // Render grid. auto grid = LineShaderData(); @@ -180,23 +298,40 @@ void FPGAViewWidget::paintGL() PolyLine(-100.0f, i, 100.0f, i).build(grid); PolyLine(i, -100.0f, i, 100.0f).build(grid); } + // Flags from pipeline. + PassthroughFlags flags; // Draw grid. lineShader_.draw(grid, colors_.grid, thick1Px, matrix); - rendererDataLock_.lock(); + { + QMutexLocker locker(&rendererDataLock_); - // Render Arch graphics. - lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_FRAME], colors_.frame, thick11Px, matrix); - lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_HIDDEN], colors_.hidden, thick11Px, matrix); - lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_INACTIVE], colors_.inactive, thick11Px, matrix); - lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_ACTIVE], colors_.active, thick11Px, matrix); + // Render Arch graphics. + lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_FRAME], colors_.frame, thick11Px, matrix); + lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_HIDDEN], colors_.hidden, thick11Px, matrix); + lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_INACTIVE], colors_.inactive, thick11Px, + matrix); + lineShader_.draw(rendererData_->gfxByStyle[GraphicElement::STYLE_ACTIVE], colors_.active, thick11Px, matrix); - // Draw highlighted items. - for (int i = 0; i < 8; i++) - lineShader_.draw(rendererData_->gfxHighlighted[i], colors_.highlight[i], thick11Px, matrix); + // Draw highlighted items. + for (int i = 0; i < 8; i++) + lineShader_.draw(rendererData_->gfxHighlighted[i], colors_.highlight[i], thick11Px, matrix); - lineShader_.draw(rendererData_->gfxSelected, colors_.selected, thick11Px, matrix); - rendererDataLock_.unlock(); + lineShader_.draw(rendererData_->gfxSelected, colors_.selected, thick11Px, matrix); + lineShader_.draw(rendererData_->gfxHovered, colors_.hovered, thick2Px, matrix); + + flags = rendererData_->flags; + } + + { + QMutexLocker locker(&rendererArgsLock_); + rendererArgs_->flags.clear(); + } + + // Check flags passed through pipeline. + if (flags.zoomOutbound) { + zoomOutbound(); + } } void FPGAViewWidget::pokeRenderer(void) { renderRunner_->poke(); } @@ -207,10 +342,10 @@ void FPGAViewWidget::renderLines(void) return; // Data from Context needed to render all decals. - std::vector<DecalXY> belDecals; - std::vector<DecalXY> wireDecals; - std::vector<DecalXY> pipDecals; - std::vector<DecalXY> groupDecals; + std::vector<std::pair<DecalXY, BelId>> belDecals; + std::vector<std::pair<DecalXY, WireId>> wireDecals; + std::vector<std::pair<DecalXY, PipId>> pipDecals; + std::vector<std::pair<DecalXY, GroupId>> groupDecals; bool decalsChanged = false; { // Take the UI/Normal mutex on the Context, copy over all we need as @@ -248,52 +383,86 @@ void FPGAViewWidget::renderLines(void) // Local copy of decals, taken as fast as possible to not block the P&R. if (decalsChanged) { for (auto bel : ctx_->getBels()) { - belDecals.push_back(ctx_->getBelDecal(bel)); + belDecals.push_back({ctx_->getBelDecal(bel), bel}); } for (auto wire : ctx_->getWires()) { - wireDecals.push_back(ctx_->getWireDecal(wire)); + wireDecals.push_back({ctx_->getWireDecal(wire), wire}); } for (auto pip : ctx_->getPips()) { - pipDecals.push_back(ctx_->getPipDecal(pip)); + pipDecals.push_back({ctx_->getPipDecal(pip), pip}); } for (auto group : ctx_->getGroups()) { - groupDecals.push_back(ctx_->getGroupDecal(group)); + groupDecals.push_back({ctx_->getGroupDecal(group), group}); } } } // Arguments from the main UI thread on what we should render. std::vector<DecalXY> selectedDecals; + DecalXY hoveredDecal; std::vector<DecalXY> highlightedDecals[8]; bool highlightedOrSelectedChanged; + PassthroughFlags flags; { // Take the renderer arguments lock, copy over all we need. QMutexLocker lock(&rendererArgsLock_); + selectedDecals = rendererArgs_->selectedDecals; + hoveredDecal = rendererArgs_->hoveredDecal; + for (int i = 0; i < 8; i++) highlightedDecals[i] = rendererArgs_->highlightedDecals[i]; - highlightedOrSelectedChanged = rendererArgs_->highlightedOrSelectedChanged; - rendererArgs_->highlightedOrSelectedChanged = false; + + highlightedOrSelectedChanged = rendererArgs_->changed; + rendererArgs_->changed = false; + + flags = rendererArgs_->flags; } // Render decals if necessary. if (decalsChanged) { auto data = std::unique_ptr<FPGAViewWidget::RendererData>(new FPGAViewWidget::RendererData); + // Reset bounding box. + data->bbGlobal.clear(); + // Draw Bels. for (auto const &decal : belDecals) { - drawArchDecal(data->gfxByStyle, decal); + renderArchDecal(data->gfxByStyle, data->bbGlobal, decal.first); } // Draw Wires. for (auto const &decal : wireDecals) { - drawArchDecal(data->gfxByStyle, decal); + renderArchDecal(data->gfxByStyle, data->bbGlobal, decal.first); } // Draw Pips. for (auto const &decal : pipDecals) { - drawArchDecal(data->gfxByStyle, decal); + renderArchDecal(data->gfxByStyle, data->bbGlobal, decal.first); } // Draw Groups. for (auto const &decal : groupDecals) { - drawArchDecal(data->gfxByStyle, decal); + renderArchDecal(data->gfxByStyle, data->bbGlobal, decal.first); + } + + // Bounding box should be calculated by now. + NPNR_ASSERT(data->bbGlobal.w() != 0); + NPNR_ASSERT(data->bbGlobal.h() != 0); + + // Populate picking quadtree. + data->qt = std::unique_ptr<PickQuadTree>(new PickQuadTree(data->bbGlobal)); + for (auto const &decal : belDecals) { + populateQuadTree(data.get(), decal.first, + PickedElement::fromBel(decal.second, decal.first.x, decal.first.y)); + } + for (auto const &decal : wireDecals) { + populateQuadTree(data.get(), decal.first, + PickedElement::fromWire(decal.second, decal.first.x, decal.first.y)); + } + for (auto const &decal : pipDecals) { + populateQuadTree(data.get(), decal.first, + PickedElement::fromPip(decal.second, decal.first.x, decal.first.y)); + } + for (auto const &decal : groupDecals) { + populateQuadTree(data.get(), decal.first, + PickedElement::fromGroup(decal.second, decal.first.x, decal.first.y)); } // Swap over. @@ -304,6 +473,7 @@ void FPGAViewWidget::renderLines(void) // copy them over from teh current object. if (!highlightedOrSelectedChanged) { data->gfxSelected = rendererData_->gfxSelected; + data->gfxHovered = rendererData_->gfxHovered; for (int i = 0; i < 8; i++) data->gfxHighlighted[i] = rendererData_->gfxHighlighted[i]; } @@ -315,28 +485,48 @@ void FPGAViewWidget::renderLines(void) if (highlightedOrSelectedChanged) { QMutexLocker locker(&rendererDataLock_); + // Whether the currently being hovered decal is also selected. + bool hoveringSelected = false; // Render selected. + rendererData_->bbSelected.clear(); rendererData_->gfxSelected.clear(); for (auto &decal : selectedDecals) { - drawDecal(rendererData_->gfxSelected, decal); + if (decal == hoveredDecal) + hoveringSelected = true; + renderDecal(rendererData_->gfxSelected, rendererData_->bbSelected, decal); + } + + // Render hovered. + rendererData_->gfxHovered.clear(); + if (!hoveringSelected) { + renderDecal(rendererData_->gfxHovered, rendererData_->bbGlobal, hoveredDecal); } // Render highlighted. for (int i = 0; i < 8; i++) { rendererData_->gfxHighlighted[i].clear(); for (auto &decal : highlightedDecals[i]) { - drawDecal(rendererData_->gfxHighlighted[i], decal); + renderDecal(rendererData_->gfxHighlighted[i], rendererData_->bbGlobal, decal); } } } + + { + QMutexLocker locker(&rendererDataLock_); + rendererData_->flags = flags; + } } -void FPGAViewWidget::onSelectedArchItem(std::vector<DecalXY> decals) +void FPGAViewWidget::onSelectedArchItem(std::vector<DecalXY> decals, bool keep) { { QMutexLocker locker(&rendererArgsLock_); - rendererArgs_->selectedDecals = decals; - rendererArgs_->highlightedOrSelectedChanged = true; + if (keep) { + std::copy(decals.begin(), decals.end(), std::back_inserter(rendererArgs_->selectedDecals)); + } else { + rendererArgs_->selectedDecals = decals; + } + rendererArgs_->changed = true; } pokeRenderer(); } @@ -346,20 +536,156 @@ void FPGAViewWidget::onHighlightGroupChanged(std::vector<DecalXY> decals, int gr { QMutexLocker locker(&rendererArgsLock_); rendererArgs_->highlightedDecals[group] = decals; - rendererArgs_->highlightedOrSelectedChanged = true; + rendererArgs_->changed = true; } pokeRenderer(); } void FPGAViewWidget::resizeGL(int width, int height) {} -void FPGAViewWidget::mousePressEvent(QMouseEvent *event) { lastDragPos_ = event->pos(); } +boost::optional<FPGAViewWidget::PickedElement> FPGAViewWidget::pickElement(float worldx, float worldy) +{ + // Get elements from renderer whose BBs correspond to the pick. + std::vector<PickedElement> elems; + { + QMutexLocker locker(&rendererDataLock_); + if (rendererData_->qt == nullptr) { + return {}; + } + elems = rendererData_->qt->get(worldx, worldy); + } + + if (elems.size() == 0) { + return {}; + } + + // Calculate distances to all elements picked. + using ElemDist = std::pair<const PickedElement *, float>; + std::vector<ElemDist> distances; + std::transform(elems.begin(), elems.end(), std::back_inserter(distances), [&](const PickedElement &e) -> ElemDist { + return std::make_pair(&e, e.distance(ctx_, worldx, worldy)); + }); + + // Find closest non -1 element. + auto closest = std::min_element(distances.begin(), distances.end(), [&](const ElemDist &a, const ElemDist &b) { + if (a.second == -1) + return false; + if (b.second == -1) + return true; + return a.second < b.second; + }); + + // All out of reach? + if (closest->second < 0) { + return {}; + } + + return *(closest->first); +} + +void FPGAViewWidget::mousePressEvent(QMouseEvent *event) +{ + if (event->buttons() & Qt::RightButton || event->buttons() & Qt::MidButton) { + lastDragPos_ = event->pos(); + } + if (event->buttons() & Qt::LeftButton) { + bool ctrl = QApplication::keyboardModifiers().testFlag(Qt::ControlModifier); + + auto world = mouseToWorldCoordinates(event->x(), event->y()); + auto closestOr = pickElement(world.x(), world.y()); + if (!closestOr) { + // If we clicked on empty space and aren't holding down ctrl, + // clear the selection. + if (!ctrl) { + QMutexLocker locked(&rendererArgsLock_); + rendererArgs_->selectedDecals.clear(); + rendererArgs_->changed = true; + pokeRenderer(); + } + return; + } + + auto closest = closestOr.value(); + if (closest.type == ElementType::BEL) { + clickedBel(closest.bel, ctrl); + } else if (closest.type == ElementType::WIRE) { + clickedWire(closest.wire, ctrl); + } else if (closest.type == ElementType::PIP) { + clickedPip(closest.pip, ctrl); + } + } +} + +void FPGAViewWidget::mouseMoveEvent(QMouseEvent *event) +{ + if (event->buttons() & Qt::RightButton || event->buttons() & Qt::MidButton) { + const int dx = event->x() - lastDragPos_.x(); + const int dy = event->y() - lastDragPos_.y(); + lastDragPos_ = event->pos(); + + auto world = mouseToWorldDimensions(dx, dy); + viewMove_.translate(world.x(), -world.y()); + + update(); + return; + } + + auto world = mouseToWorldCoordinates(event->x(), event->y()); + auto closestOr = pickElement(world.x(), world.y()); + // No elements? No decal. + if (!closestOr) { + QMutexLocker locked(&rendererArgsLock_); + rendererArgs_->hoveredDecal = DecalXY(); + rendererArgs_->changed = true; + pokeRenderer(); + return; + } + + auto closest = closestOr.value(); + + { + QMutexLocker locked(&rendererArgsLock_); + rendererArgs_->hoveredDecal = closest.decal(ctx_); + rendererArgs_->changed = true; + pokeRenderer(); + } + update(); +} // Invert the projection matrix to calculate screen/mouse to world/grid // coordinates. QVector4D FPGAViewWidget::mouseToWorldCoordinates(int x, int y) { + const qreal retinaScale = devicePixelRatio(); + + auto projection = getProjection(); + + QMatrix4x4 vp; + vp.viewport(0, 0, width() * retinaScale, height() * retinaScale); + + QVector4D vec(x, y, 1, 1); + vec = vp.inverted() * vec; + vec = projection.inverted() * QVector4D(vec.x(), vec.y(), -1, 1); + + // Hic sunt dracones. + // TODO(q3k): grab a book, remind yourselfl linear algebra and undo this + // operation properly. + QVector3D ray = vec.toVector3DAffine(); + ray.normalize(); + ray.setX((ray.x() / -ray.z()) * zoom_); + ray.setY((ray.y() / ray.z()) * zoom_); + ray.setZ(1.0); + + vec = viewMove_.inverted() * QVector4D(ray.x(), ray.y(), ray.z(), 1.0); + vec.setZ(0); + + return vec; +} + +QVector4D FPGAViewWidget::mouseToWorldDimensions(float x, float y) +{ QMatrix4x4 p = getProjection(); + p.translate(0.0f, 0.0f, -zoom_); QVector2D unit = p.map(QVector4D(1, 1, 0, 1)).toVector2DAffine(); float sx = (((float)x) / (width() / 2)); @@ -367,18 +693,6 @@ QVector4D FPGAViewWidget::mouseToWorldCoordinates(int x, int y) return QVector4D(sx / unit.x(), sy / unit.y(), 0, 1); } -void FPGAViewWidget::mouseMoveEvent(QMouseEvent *event) -{ - const int dx = event->x() - lastDragPos_.x(); - const int dy = event->y() - lastDragPos_.y(); - lastDragPos_ = event->pos(); - - auto world = mouseToWorldCoordinates(dx, dy); - viewMove_.translate(world.x(), -world.y()); - - update(); -} - void FPGAViewWidget::wheelEvent(QWheelEvent *event) { QPoint degree = event->angleDelta() / 8; @@ -389,26 +703,64 @@ void FPGAViewWidget::wheelEvent(QWheelEvent *event) void FPGAViewWidget::zoom(int level) { - if (zoom_ < zoomNear_) { - zoom_ = zoomNear_; - } else if (zoom_ < zoomLvl1_) { - zoom_ -= level / 10.0; + if (zoom_ < zoomLvl1_) { + zoom_ -= level / 500.0; } else if (zoom_ < zoomLvl2_) { - zoom_ -= level / 5.0; - } else if (zoom_ < zoomFar_) { - zoom_ -= level; + zoom_ -= level / 100.0; } else { - zoom_ = zoomFar_; + zoom_ -= level / 10.0; } + + if (zoom_ < zoomNear_) + zoom_ = zoomNear_; + else if (zoom_ > zoomFar_) + zoom_ = zoomFar_; update(); } +void FPGAViewWidget::clampZoom() +{ + if (zoom_ < zoomNear_) + zoom_ = zoomNear_; + else if (zoom_ > zoomFar_) + zoom_ = zoomFar_; +} + void FPGAViewWidget::zoomIn() { zoom(10); } void FPGAViewWidget::zoomOut() { zoom(-10); } -void FPGAViewWidget::zoomSelected() {} +void FPGAViewWidget::zoomToBB(const PickQuadTree::BoundingBox &bb, float margin) +{ + if (bb.w() < 0.00005 && bb.h() < 0.00005) + return; + + viewMove_.setToIdentity(); + viewMove_.translate(-(bb.x0() + bb.w() / 2), -(bb.y0() + bb.h() / 2)); -void FPGAViewWidget::zoomOutbound() {} + // Our FOV is π/2, so distance for camera to see a plane of width H is H/2. + // We add 1 unit to cover half a unit of extra space around. + float distance_w = bb.w() / 2 + margin; + float distance_h = bb.h() / 2 + margin; + zoom_ = std::max(distance_w, distance_h); + clampZoom(); +} + +void FPGAViewWidget::zoomSelected() +{ + { + QMutexLocker lock(&rendererDataLock_); + zoomToBB(rendererData_->bbSelected, 0.5f); + } + update(); +} + +void FPGAViewWidget::zoomOutbound() +{ + { + QMutexLocker lock(&rendererDataLock_); + zoomToBB(rendererData_->bbGlobal, 1.0f); + } +} NEXTPNR_NAMESPACE_END diff --git a/gui/fpgaviewwidget.h b/gui/fpgaviewwidget.h index 260ebf05..c35821d9 100644 --- a/gui/fpgaviewwidget.h +++ b/gui/fpgaviewwidget.h @@ -31,9 +31,12 @@ #include <QThread> #include <QTimer> #include <QWaitCondition> +#include <boost/optional.hpp> -#include "nextpnr.h" +#include "designwidget.h" #include "lineshader.h" +#include "nextpnr.h" +#include "quadtree.h" NEXTPNR_NAMESPACE_BEGIN @@ -105,10 +108,9 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions QSize minimumSizeHint() const override; QSize sizeHint() const override; - public Q_SLOTS: void newContext(Context *ctx); - void onSelectedArchItem(std::vector<DecalXY> decals); + void onSelectedArchItem(std::vector<DecalXY> decals, bool keep); void onHighlightGroupChanged(std::vector<DecalXY> decals, int group); void pokeRenderer(void); void zoomIn(); @@ -116,11 +118,103 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions void zoomSelected(); void zoomOutbound(); + Q_SIGNALS: + void clickedBel(BelId bel, bool add); + void clickedWire(WireId wire, bool add); + void clickedPip(PipId pip, bool add); + private: - const float zoomNear_ = 1.0f; // do not zoom closer than this - const float zoomFar_ = 10000.0f; // do not zoom further than this - const float zoomLvl1_ = 100.0f; - const float zoomLvl2_ = 50.0f; + const float zoomNear_ = 0.1f; // do not zoom closer than this + const float zoomFar_ = 30.0f; // do not zoom further than this + const float zoomLvl1_ = 1.0f; + const float zoomLvl2_ = 5.0f; + + struct PickedElement + { + ElementType type; + + // These are not in an union (and thus this structure is very verbose + // and somewhat heavy) because the Id types are typedef'd to StringIds + // in the generic architecture. Once that changes (or we get an AnyId + // construct from Arches), this should go away. + BelId bel; + WireId wire; + PipId pip; + GroupId group; + + float x, y; // Decal X and Y + + PickedElement(ElementType type, float x, float y) : type(type), x(x), y(y) {} + + static PickedElement fromBel(BelId bel, float x, float y) + { + PickedElement e(ElementType::BEL, x, y); + e.bel = bel; + return e; + } + static PickedElement fromWire(WireId wire, float x, float y) + { + PickedElement e(ElementType::WIRE, x, y); + e.wire = wire; + return e; + } + static PickedElement fromPip(PipId pip, float x, float y) + { + PickedElement e(ElementType::PIP, x, y); + e.pip = pip; + return e; + } + static PickedElement fromGroup(GroupId group, float x, float y) + { + PickedElement e(ElementType::GROUP, x, y); + e.group = group; + return e; + } + + PickedElement(const PickedElement &other) : type(other.type) + { + switch (type) { + case ElementType::BEL: + bel = other.bel; + break; + case ElementType::WIRE: + wire = other.wire; + break; + case ElementType::PIP: + pip = other.pip; + break; + case ElementType::GROUP: + group = other.group; + break; + default: + NPNR_ASSERT_FALSE("Invalid ElementType"); + } + } + + DecalXY decal(Context *ctx) const + { + DecalXY decal; + switch (type) { + case ElementType::BEL: + decal = ctx->getBelDecal(bel); + break; + case ElementType::WIRE: + decal = ctx->getWireDecal(wire); + break; + case ElementType::PIP: + decal = ctx->getPipDecal(pip); + break; + case ElementType::GROUP: + decal = ctx->getGroupDecal(group); + break; + default: + NPNR_ASSERT_FALSE("Invalid ElementType"); + } + return decal; + } + float distance(Context *ctx, float wx, float wy) const; + }; + using PickQuadTree = QuadTree<float, PickedElement>; Context *ctx_; QTimer paintTimer_; @@ -140,33 +234,75 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions QColor inactive; QColor active; QColor selected; + QColor hovered; QColor highlight[8]; } colors_; - struct RendererData + // Flags that are passed through from renderer arguments to renderer data. + // These are used by the UI code to signal events that will only fire when + // the next frame gets rendered. + struct PassthroughFlags { - LineShaderData gfxByStyle[GraphicElement::STYLE_MAX]; - LineShaderData gfxSelected; - LineShaderData gfxHighlighted[8]; + bool zoomOutbound; + + PassthroughFlags() : zoomOutbound(false) {} + PassthroughFlags &operator=(const PassthroughFlags &other) noexcept + { + zoomOutbound = other.zoomOutbound; + return *this; + } + + void clear() { zoomOutbound = false; } }; - std::unique_ptr<RendererData> rendererData_; - QMutex rendererDataLock_; struct RendererArgs { + // Decals that he user selected. std::vector<DecalXY> selectedDecals; + // Decals that the user highlighted. std::vector<DecalXY> highlightedDecals[8]; - bool highlightedOrSelectedChanged; + // Decals that the user's mouse is hovering in. + DecalXY hoveredDecal; + // Whether to render the above three or skip it. + bool changed; + + // Flags to pass back into the RendererData. + PassthroughFlags flags; }; std::unique_ptr<RendererArgs> rendererArgs_; QMutex rendererArgsLock_; + struct RendererData + { + LineShaderData gfxByStyle[GraphicElement::STYLE_MAX]; + LineShaderData gfxSelected; + LineShaderData gfxHovered; + LineShaderData gfxHighlighted[8]; + // Global bounding box of data from Arch. + PickQuadTree::BoundingBox bbGlobal; + // Bounding box of selected items. + PickQuadTree::BoundingBox bbSelected; + // Quadtree for picking objects. + std::unique_ptr<PickQuadTree> qt; + // Flags from args. + PassthroughFlags flags; + }; + std::unique_ptr<RendererData> rendererData_; + QMutex rendererDataLock_; + + void clampZoom(); + void zoomToBB(const PickQuadTree::BoundingBox &bb, float margin); void zoom(int level); void renderLines(void); - void drawGraphicElement(LineShaderData &out, const GraphicElement &el, float x, float y); - void drawDecal(LineShaderData &out, const DecalXY &decal); - void drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], const DecalXY &decal); + void renderGraphicElement(LineShaderData &out, PickQuadTree::BoundingBox &bb, const GraphicElement &el, float x, + float y); + void renderDecal(LineShaderData &out, PickQuadTree::BoundingBox &bb, const DecalXY &decal); + void renderArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], PickQuadTree::BoundingBox &bb, + const DecalXY &decal); + void populateQuadTree(RendererData *data, const DecalXY &decal, const PickedElement &element); + boost::optional<PickedElement> pickElement(float worldx, float worldy); QVector4D mouseToWorldCoordinates(int x, int y); + QVector4D mouseToWorldDimensions(float x, float y); QMatrix4x4 getProjection(void); }; diff --git a/gui/lineshader.cc b/gui/lineshader.cc index 94a7a010..eba96020 100644 --- a/gui/lineshader.cc +++ b/gui/lineshader.cc @@ -17,8 +17,8 @@ * */ -#include "log.h" #include "lineshader.h" +#include "log.h" NEXTPNR_NAMESPACE_BEGIN diff --git a/gui/quadtree.h b/gui/quadtree.h new file mode 100644 index 00000000..b3ebf81c --- /dev/null +++ b/gui/quadtree.h @@ -0,0 +1,425 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef QUADTREE_H +#define QUADTREE_H + +// This file implements a quad tree used for comitting 2D axis aligned +// bounding boxes and then retrieving them by 2D point. + +NEXTPNR_NAMESPACE_BEGIN + +// A node of a QuadTree. Internal. +template <typename CoordinateT, typename ElementT> class QuadTreeNode +{ + public: + class BoundingBox + { + friend class QuadTreeNode; + + private: + CoordinateT x0_, y0_, x1_, y1_; + + static constexpr float pinf = std::numeric_limits<CoordinateT>::infinity(); + static constexpr float ninf = -std::numeric_limits<CoordinateT>::infinity(); + + public: + // Standard constructor for a given (x0,y0), (x1,y1) bounding box + // + // @param x0 x coordinate of top-left corner of box + // @param y0 y coordinate of top-left corner of box + // @param x1 x coordinate of bottom-right corner of box + // @param y1 y coordinate of bottom-right corner of box + BoundingBox(CoordinateT x0, CoordinateT y0, CoordinateT x1, CoordinateT y1) : x0_(x0), y0_(y0), x1_(x1), y1_(y1) + { + } + + + BoundingBox() : x0_(pinf), y0_(pinf), x1_(ninf), y1_(ninf) {} + + BoundingBox(const BoundingBox &other) : x0_(other.x0_), y0_(other.y0_), x1_(other.x1_), y1_(other.y1_) {} + + // Whether a bounding box contains a given points. + // A point is defined to be in a bounding box when it's not lesser than + // the lower coordinate or greater than the higher coordinate, eg: + // A BoundingBox of x0: 20, y0: 30, x1: 100, y1: 130 fits the following + // points: + // [ (50, 50), (20, 50), (20, 30), (100, 130) ] + inline bool contains(CoordinateT x, CoordinateT y) const + { + if (x < x0_ || x > x1_) + return false; + if (y < y0_ || y > y1_) + return false; + return true; + } + + // Sort the bounding box coordinates. + void fixup() + { + if (x1_ < x0_) + std::swap(x0_, x1_); + if (y1_ < y0_) + std::swap(y0_, y1_); + } + + CoordinateT x0() const { return x0_; } + CoordinateT y0() const { return y0_; } + CoordinateT x1() const { return x1_; } + CoordinateT y1() const { return y1_; } + + void setX0(CoordinateT v) { x0_ = v; } + void setY0(CoordinateT v) { y0_ = v; } + void setX1(CoordinateT v) { x1_ = v; } + void setY1(CoordinateT v) { y1_ = v; } + + void clear() + { + x0_ = pinf; + y0_ = pinf; + x1_ = ninf; + y1_ = ninf; + } + + CoordinateT w() const { return x1_ - x0_; } + CoordinateT h() const { return y1_ - y0_; } + }; + + private: + // A pair of Element and BoundingBox that contains it. + class BoundElement + { + friend class QuadTreeNode; + + private: + BoundingBox bb_; + ElementT elem_; + + public: + BoundElement(BoundingBox bb, ElementT elem) : bb_(bb), elem_(elem) {} + }; + + // The bounding box that this node describes. + BoundingBox bound_; + // How many elements should be contained in this node until it splits into + // sub-nodes. + const size_t max_elems_; + // Four sub-nodes or nullptr if it hasn't split yet. + std::unique_ptr<QuadTreeNode<CoordinateT, ElementT>[]> children_ = nullptr; + // Coordinates of the split. + // Anything < split_x is west. + CoordinateT splitx_; + // Anything < split_y is north. + CoordinateT splity_; + + // Elements contained directly within this node and not part of children + // nodes. + std::vector<BoundElement> elems_; + // Depth at which this node is - root is at 0, first level at 1, etc. + int depth_; + + // Checks whether a given bounding box fits within this node - used for + // sanity checking on insertion. + // @param b bounding box to check + // @returns whether b fits in this node entirely + bool fits(const BoundingBox &b) const + { + if (b.x0_ < bound_.x0_ || b.x0_ > bound_.x1_) { + return false; + } else if (b.x1_ < bound_.x0_ || b.x1_ > bound_.x1_) { + return false; + } else if (b.y0_ < bound_.y0_ || b.y0_ > bound_.y1_) { + return false; + } else if (b.y1_ < bound_.y0_ || b.y1_ > bound_.y1_) { + return false; + } + return true; + } + + // Used to describe one of 5 possible places an element can exist: + // - the node itself (THIS) + // - any of the 4 children nodes. + enum Quadrant + { + THIS_NODE = -1, + NW = 0, + NE = 1, + SW = 2, + SE = 3 + }; + + // Finds the quadrant to which a bounding box should go (if the node + // is / were to be split). + // @param b bounding box to check + // @returns quadrant in which b belongs to if the node is were to be split + Quadrant quadrant(const BoundingBox &b) const + { + if (children_ == nullptr) { + return THIS_NODE; + } + + bool west0 = b.x0_ < splitx_; + bool west1 = b.x1_ < splitx_; + bool north0 = b.y0_ < splity_; + bool north1 = b.y1_ < splity_; + + if (west0 && west1 && north0 && north1) + return NW; + if (!west0 && !west1 && north0 && north1) + return NE; + if (west0 && west1 && !north0 && !north1) + return SW; + if (!west0 && !west1 && !north0 && !north1) + return SE; + return THIS_NODE; + } + + // Checks whether this node should split. + bool should_split() const + { + // The node shouldn't split if it's not large enough to merit it. + if (elems_.size() < max_elems_) + return false; + + // The node shouldn't split if its' level is too deep (this is true for + // 100k+ entries, where the amount of splits causes us to lose + // significant CPU time on traversing the tree, or worse yet causes a + // stack overflow). + if (depth_ > 5) + return false; + + return true; + } + + public: + // Standard constructor for node. + // @param b BoundingBox this node covers. + // @param depth depth at which this node is in the tree + // @max_elems how many elements should this node contain before it splits + QuadTreeNode(BoundingBox b, int depth, size_t max_elems = 4) : bound_(b), max_elems_(max_elems), depth_(depth) {} + // Disallow copies. + QuadTreeNode(const QuadTreeNode &other) = delete; + QuadTreeNode &operator=(const QuadTreeNode &other) = delete; + // Allow moves. + QuadTreeNode(QuadTreeNode &&other) + : bound_(other.bound_), max_elems_(other.max_elems_), children_(std::move(other.children_)), + splitx_(other.splitx_), splity_(other.splity_), elems_(std::move(other.elems_)), depth_(other.depth_) + { + other.children_ = nullptr; + } + QuadTreeNode &operator=(QuadTreeNode &&other) + { + if (this == &other) + return *this; + bound_ = other.bound_; + max_elems_ = other.max_elems_; + children_ = other.max_children_; + children_ = other.children_; + splitx_ = other.splitx_; + splity_ = other.splity_; + elems_ = std::move(other.elems_); + depth_ = other.depth_; + other.children_ = nullptr; + return *this; + } + + // Insert an element at a given bounding box. + bool insert(const BoundingBox &k, ElementT v) + { + // Fail early if this BB doesn't fit us at all. + if (!fits(k)) { + return false; + } + + // Do we have children? + if (children_ != nullptr) { + // Put the element either recursively into a child if it fits + // entirely or keep it for ourselves if not. + auto quad = quadrant(k); + if (quad == THIS_NODE) { + elems_.push_back(BoundElement(k, std::move(v))); + } else { + return children_[quad].insert(k, std::move(v)); + } + } else { + // No children and not about to have any. + if (!should_split()) { + elems_.push_back(BoundElement(k, std::move(v))); + return true; + } + // Splitting. Calculate the split point. + splitx_ = (bound_.x1_ - bound_.x0_) / 2 + bound_.x0_; + splity_ = (bound_.y1_ - bound_.y0_) / 2 + bound_.y0_; + // Create the new children. + children_ = decltype(children_)(new QuadTreeNode<CoordinateT, ElementT>[4] { + // Note: not using [NW] = QuadTreeNode because that seems to + // crash g++ 7.3.0. + /* NW */ QuadTreeNode<CoordinateT, ElementT>(BoundingBox(bound_.x0_, bound_.y0_, splitx_, splity_), + depth_ + 1, max_elems_), + /* NE */ + QuadTreeNode<CoordinateT, ElementT>(BoundingBox(splitx_, bound_.y0_, bound_.x1_, splity_), + depth_ + 1, max_elems_), + /* SW */ + QuadTreeNode<CoordinateT, ElementT>(BoundingBox(bound_.x0_, splity_, splitx_, bound_.y1_), + depth_ + 1, max_elems_), + /* SE */ + QuadTreeNode<CoordinateT, ElementT>(BoundingBox(splitx_, splity_, bound_.x1_, bound_.y1_), + depth_ + 1, max_elems_), + }); + // Move all elements to where they belong. + auto it = elems_.begin(); + while (it != elems_.end()) { + auto quad = quadrant(it->bb_); + if (quad != THIS_NODE) { + // Move to one of the children. + if (!children_[quad].insert(it->bb_, std::move(it->elem_))) + return false; + // Delete from ourselves. + it = elems_.erase(it); + } else { + // Keep for ourselves. + it++; + } + } + // Insert the actual element now that we've split. + return insert(k, std::move(v)); + } + return true; + } + + // Dump a human-readable representation of the tree to stdout. + void dump(int level) const + { + for (int i = 0; i < level; i++) + printf(" "); + printf("loc: % 3d % 3d % 3d % 3d\n", bound_.x0_, bound_.y0_, bound_.x1_, bound_.y1_); + if (elems_.size() != 0) { + for (int i = 0; i < level; i++) + printf(" "); + printf("elems: %zu\n", elems_.size()); + } + + if (children_ != nullptr) { + for (int i = 0; i < level; i++) + printf(" "); + printf("children:\n"); + children_[NW].dump(level + 1); + children_[NE].dump(level + 1); + children_[SW].dump(level + 1); + children_[SE].dump(level + 1); + } + } + + // Return count of BoundingBoxes/Elements contained. + // @returns count of elements contained. + size_t size() const + { + size_t res = elems_.size(); + if (children_ != nullptr) { + res += children_[NW].size(); + res += children_[NE].size(); + res += children_[SW].size(); + res += children_[SE].size(); + } + return res; + } + + // Retrieve elements whose bounding boxes cover the given coordinates. + // + // @param x X coordinate of points to query. + // @param y Y coordinate of points to query. + // @returns vector of found bounding boxes + void get(CoordinateT x, CoordinateT y, std::vector<ElementT> &res) const + { + if (!bound_.contains(x, y)) + return; + + for (const auto &elem : elems_) { + const auto &bb = elem.bb_; + if (bb.contains(x, y)) { + res.push_back(elem.elem_); + } + } + if (children_ != nullptr) { + children_[NW].get(x, y, res); + children_[NE].get(x, y, res); + children_[SW].get(x, y, res); + children_[SE].get(x, y, res); + } + } +}; + +// User facing method to manage a quad tree. +// +// @param CoodinateT scalar type of the coordinate system - int, float, ... +// @param ElementT type of the contained element. Must be movable or copiable. +template <typename CoordinateT, typename ElementT> class QuadTree +{ + private: + // Root of the tree. + QuadTreeNode<CoordinateT, ElementT> root_; + + public: + // To let user create bounding boxes of the correct type. + // Bounding boxes are composed of two 2D points, which designate their + // top-left and bottom-right corners. All its' edges are axis aligned. + using BoundingBox = typename QuadTreeNode<CoordinateT, ElementT>::BoundingBox; + + // Standard constructor. + // + // @param b Bounding box of the entire tree - all comitted elements must + // fit within in. + QuadTree(BoundingBox b) : root_(b, 0) {} + + // Inserts a new value at a given bounding box.e + // BoundingBoxes are not deduplicated - if two are pushed with the same + // coordinates, the first one will take precendence. + // + // @param k Bounding box at which to store value. + // @param v Value at a given bounding box. + // @returns Whether the insert was succesful. + bool insert(BoundingBox k, ElementT v) + { + k.fixup(); + return root_.insert(k, v); + } + + // Dump a human-readable representation of the tree to stdout. + void dump() const { root_.dump(0); } + + // Return count of BoundingBoxes/Elements contained. + // @returns count of elements contained. + size_t size() const { return root_.size(); } + + // Retrieve elements whose bounding boxes cover the given coordinates. + // + // @param x X coordinate of points to query. + // @param y Y coordinate of points to query. + // @returns vector of found bounding boxes + std::vector<ElementT> get(CoordinateT x, CoordinateT y) const + { + std::vector<ElementT> res; + root_.get(x, y, res); + return res; + } +}; + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/tests/gui/quadtree.cc b/tests/gui/quadtree.cc new file mode 100644 index 00000000..083a0057 --- /dev/null +++ b/tests/gui/quadtree.cc @@ -0,0 +1,127 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Serge Bazanski <q3k@symbioticeda.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "gtest/gtest.h" +#include "nextpnr.h" +#include "quadtree.h" + +USING_NEXTPNR_NAMESPACE + +using QT = QuadTree<int, int>; + +class QuadTreeTest : public ::testing::Test +{ + protected: + virtual void SetUp() + { + qt_ = new QT(QT::BoundingBox(0, 0, width_, height_)); + } + virtual void TearDown() + { + delete qt_; + } + + int width_ = 100; + int height_ = 100; + QT *qt_; +}; + +// Test that we're doing bound checking correctly. +TEST_F(QuadTreeTest, insert_bound_checking) +{ + ASSERT_TRUE(qt_->insert(QT::BoundingBox(10, 10, 20, 20), 10)); + ASSERT_TRUE(qt_->insert(QT::BoundingBox(0, 0, 100, 100), 10)); + ASSERT_FALSE(qt_->insert(QT::BoundingBox(10, 10, 101, 20), 10)); + ASSERT_FALSE(qt_->insert(QT::BoundingBox(-1, 10, 101, 20), 10)); + ASSERT_FALSE(qt_->insert(QT::BoundingBox(-1, -1, 20, 20), 10)); +} + +// Test whether we are not losing any elements. +TEST_F(QuadTreeTest, insert_count) +{ + auto rng = NEXTPNR_NAMESPACE::DeterministicRNG(); + + // Add 10000 random rectangles. + for (unsigned int i = 0; i < 10000; i++) { + int x0 = rng.rng(width_); + int y0 = rng.rng(height_); + int w = rng.rng(width_ - x0); + int h = rng.rng(width_ - y0); + int x1 = x0 + w; + int y1 = y0 + h; + ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i)); + ASSERT_EQ(qt_->size(), i+1); + } + // Add 100000 random points. + for (unsigned int i = 0; i < 100000; i++) { + int x0 = rng.rng(width_); + int y0 = rng.rng(height_); + int x1 = x0; + int y1 = y0; + ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i)); + ASSERT_EQ(qt_->size(), i+10001); + } +} + +// Test that we can insert and retrieve the same element. +TEST_F(QuadTreeTest, insert_retrieve_same) +{ + auto rng = NEXTPNR_NAMESPACE::DeterministicRNG(); + + // Add 10000 small random rectangles. + rng.rngseed(0); + for (int i = 0; i < 10000; i++) { + int x0 = rng.rng(width_); + int y0 = rng.rng(height_); + int w = rng.rng(width_ - x0); + int h = rng.rng(width_ - y0); + int x1 = x0 + w/4; + int y1 = y0 + h/4; + ASSERT_TRUE(qt_->insert(QT::BoundingBox(x0, y0, x1, y1), i)); + } + + // Restart RNG, make sure we get the same rectangles back. + rng.rngseed(0); + for (int i = 0; i < 10000; i++) { + int x0 = rng.rng(width_); + int y0 = rng.rng(height_); + int w = rng.rng(width_ - x0); + int h = rng.rng(width_ - y0); + int x1 = x0 + w/4; + int y1 = y0 + h/4; + + // try to find something in the middle of the square + int x = (x1-x0)/2+x0; + int y = (y1-y0)/2+y0; + + auto res = qt_->get(x, y); + // Somewhat arbirary test to make sure we don't return obscene + // amounts of data. + ASSERT_LT(res.size(), 200UL); + bool found = false; + for (auto elem : res) { + // Is this what we're looking for? + if (elem == i) { + found = true; + break; + } + } + ASSERT_TRUE(found); + } +} diff --git a/tests/ice40/hx1k.cc b/tests/ice40/hx1k.cc index 6c3205f3..b7990a82 100644 --- a/tests/ice40/hx1k.cc +++ b/tests/ice40/hx1k.cc @@ -59,7 +59,7 @@ TEST_F(HX1KTest, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 27682); + ASSERT_EQ(wire_count, 27690); } TEST_F(HX1KTest, pip_names) diff --git a/tests/ice40/hx8k.cc b/tests/ice40/hx8k.cc index 485a2d31..d5b489eb 100644 --- a/tests/ice40/hx8k.cc +++ b/tests/ice40/hx8k.cc @@ -59,7 +59,7 @@ TEST_F(HX8KTest, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 135174); + ASSERT_EQ(wire_count, 135182); } TEST_F(HX8KTest, pip_names) diff --git a/tests/ice40/lp1k.cc b/tests/ice40/lp1k.cc index b1092700..b258d115 100644 --- a/tests/ice40/lp1k.cc +++ b/tests/ice40/lp1k.cc @@ -59,7 +59,7 @@ TEST_F(LP1KTest, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 27682); + ASSERT_EQ(wire_count, 27690); } TEST_F(LP1KTest, pip_names) diff --git a/tests/ice40/lp384.cc b/tests/ice40/lp384.cc index 287293d9..a2d91e7d 100644 --- a/tests/ice40/lp384.cc +++ b/tests/ice40/lp384.cc @@ -59,7 +59,7 @@ TEST_F(LP384Test, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 8294); + ASSERT_EQ(wire_count, 8302); } TEST_F(LP384Test, pip_names) diff --git a/tests/ice40/lp8k.cc b/tests/ice40/lp8k.cc index efe61b5b..a1c8c88c 100644 --- a/tests/ice40/lp8k.cc +++ b/tests/ice40/lp8k.cc @@ -59,7 +59,7 @@ TEST_F(LP8KTest, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 135174); + ASSERT_EQ(wire_count, 135182); } TEST_F(LP8KTest, pip_names) diff --git a/tests/ice40/up5k.cc b/tests/ice40/up5k.cc index 342a7c0a..6761db2e 100644 --- a/tests/ice40/up5k.cc +++ b/tests/ice40/up5k.cc @@ -59,7 +59,7 @@ TEST_F(UP5KTest, wire_names) assert(wire == ctx->getWireByName(name)); wire_count++; } - ASSERT_EQ(wire_count, 103383); + ASSERT_EQ(wire_count, 103391); } TEST_F(UP5KTest, pip_names) |