aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CMakeLists.txt6
-rw-r--r--common/nextpnr.h5
-rw-r--r--gui/basewindow.cc2
-rw-r--r--gui/designwidget.cc14
-rw-r--r--gui/designwidget.h5
-rw-r--r--gui/fpgaviewwidget.cc357
-rw-r--r--gui/fpgaviewwidget.h69
-rw-r--r--gui/quadtree.h397
-rw-r--r--tests/gui/quadtree.cc127
-rw-r--r--tests/ice40/hx1k.cc2
-rw-r--r--tests/ice40/hx8k.cc2
-rw-r--r--tests/ice40/lp1k.cc2
-rw-r--r--tests/ice40/lp384.cc2
-rw-r--r--tests/ice40/lp8k.cc2
-rw-r--r--tests/ice40/up5k.cc2
15 files changed, 925 insertions, 69 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/gui/basewindow.cc b/gui/basewindow.cc
index e07200de..c7e637f6 100644
--- a/gui/basewindow.cc
+++ b/gui/basewindow.cc
@@ -82,6 +82,8 @@ BaseMainWindow::BaseMainWindow(std::unique_ptr<Context> context, QWidget *parent
connect(this, SIGNAL(contextChanged(Context *)), fpgaView, SLOT(newContext(Context *)));
connect(designview, SIGNAL(selected(std::vector<DecalXY>)), fpgaView,
SLOT(onSelectedArchItem(std::vector<DecalXY>)));
+ connect(fpgaView, SIGNAL(clickedBel(BelId)), designview, SLOT(onClickedBel(BelId)));
+ connect(fpgaView, SIGNAL(clickedWire(WireId)), designview, SLOT(onClickedWire(WireId)));
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..34f7a656 100644
--- a/gui/designwidget.cc
+++ b/gui/designwidget.cc
@@ -507,6 +507,20 @@ QtProperty *DesignWidget::addSubGroup(QtProperty *topItem, const QString &name)
return item;
}
+void DesignWidget::onClickedBel(BelId bel)
+{
+ 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)));
+}
+
+void DesignWidget::onClickedWire(WireId wire)
+{
+ 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)));
+}
+
void DesignWidget::onItemSelectionChanged()
{
if (treeWidget->selectedItems().size() == 0)
diff --git a/gui/designwidget.h b/gui/designwidget.h
index 6d4b7fe1..fec0d069 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
@@ -74,6 +75,8 @@ class DesignWidget : public QWidget
public Q_SLOTS:
void newContext(Context *ctx);
void updateTree();
+ void onClickedBel(BelId bel);
+ void onClickedWire(WireId wire);
private:
Context *ctx;
diff --git a/gui/fpgaviewwidget.cc b/gui/fpgaviewwidget.cc
index de73e27b..46008ece 100644
--- a/gui/fpgaviewwidget.cc
+++ b/gui/fpgaviewwidget.cc
@@ -44,6 +44,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 +54,7 @@ FPGAViewWidget::FPGAViewWidget(QWidget *parent) :
colors_.highlight[6] = QColor("#ff69b4");
colors_.highlight[7] = QColor("#da70d6");
- rendererArgs_->highlightedOrSelectedChanged = false;
+ rendererArgs_->changed = false;
auto fmt = format();
fmt.setMajorVersion(3);
@@ -75,6 +76,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() {}
@@ -102,36 +104,102 @@ 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(RendererData *data, LineShaderData &out, 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);
+
+ data->bbX0 = std::min(data->bbX0, x + el.x1);
+ data->bbY0 = std::min(data->bbY0, x + el.y1);
+ data->bbX1 = std::max(data->bbX1, x + el.x2);
+ data->bbY1 = std::max(data->bbY1, x + 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);
+ return;
}
}
-void FPGAViewWidget::drawDecal(LineShaderData &out, const DecalXY &decal)
+void FPGAViewWidget::renderDecal(RendererData *data, LineShaderData &out, const DecalXY &decal)
{
float offsetX = decal.x;
float offsetY = decal.y;
for (auto &el : ctx_->getDecalGraphics(decal.decal)) {
- drawGraphicElement(out, el, offsetX, offsetY);
+ renderGraphicElement(data, out, el, offsetX, offsetY);
}
}
-void FPGAViewWidget::drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], const DecalXY &decal)
+void FPGAViewWidget::renderArchDecal(RendererData *data, const DecalXY &decal)
{
float offsetX = decal.x;
float offsetY = decal.y;
@@ -141,7 +209,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(data, data->gfxByStyle[el.style], el, offsetX, offsetY);
break;
default:
break;
@@ -149,6 +217,42 @@ 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) {
+ 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;
@@ -171,8 +275,9 @@ void FPGAViewWidget::paintGL()
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();
@@ -183,20 +288,22 @@ void FPGAViewWidget::paintGL()
// 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);
+ }
}
void FPGAViewWidget::pokeRenderer(void) { renderRunner_->poke(); }
@@ -207,10 +314,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 +355,81 @@ 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;
{
// 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;
}
+
// Render decals if necessary.
if (decalsChanged) {
auto data = std::unique_ptr<FPGAViewWidget::RendererData>(new FPGAViewWidget::RendererData);
+ // Reset bounding box.
+ data->bbX0 = 0;
+ data->bbY0 = 0;
+ data->bbX1 = 0;
+ data->bbY1 = 0;
+
// Draw Bels.
for (auto const &decal : belDecals) {
- drawArchDecal(data->gfxByStyle, decal);
+ renderArchDecal(data.get(), decal.first);
}
// Draw Wires.
for (auto const &decal : wireDecals) {
- drawArchDecal(data->gfxByStyle, decal);
+ renderArchDecal(data.get(), decal.first);
}
// Draw Pips.
for (auto const &decal : pipDecals) {
- drawArchDecal(data->gfxByStyle, decal);
+ renderArchDecal(data.get(), decal.first);
}
// Draw Groups.
for (auto const &decal : groupDecals) {
- drawArchDecal(data->gfxByStyle, decal);
+ renderArchDecal(data.get(), decal.first);
+ }
+
+ // Bounding box should be calculated by now.
+ NPNR_ASSERT((data->bbX1 - data->bbX0) != 0);
+ NPNR_ASSERT((data->bbY1 - data->bbY0) != 0);
+ auto bb = PickQuadTree::BoundingBox(data->bbX0, data->bbY0, data->bbX1, data->bbY1);
+
+ // Populate picking quadtree.
+ data->qt = std::unique_ptr<PickQuadTree>(new PickQuadTree(bb));
+ for (auto const &decal : belDecals) {
+ populateQuadTree(data.get(), decal.first, PickedElement(decal.second, decal.first.x, decal.first.y));
+ }
+ for (auto const &decal : wireDecals) {
+ populateQuadTree(data.get(), decal.first, PickedElement(decal.second, decal.first.x, decal.first.y));
+ }
+ for (auto const &decal : pipDecals) {
+ populateQuadTree(data.get(), decal.first, PickedElement(decal.second, decal.first.x, decal.first.y));
+ }
+ for (auto const &decal : groupDecals) {
+ populateQuadTree(data.get(), decal.first, PickedElement(decal.second, decal.first.x, decal.first.y));
}
// Swap over.
@@ -304,6 +440,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,17 +452,27 @@ void FPGAViewWidget::renderLines(void)
if (highlightedOrSelectedChanged) {
QMutexLocker locker(&rendererDataLock_);
+ // Whether the currently being hovered decal is also selected.
+ bool hoveringSelected = false;
// Render selected.
rendererData_->gfxSelected.clear();
for (auto &decal : selectedDecals) {
- drawDecal(rendererData_->gfxSelected, decal);
+ if (decal == hoveredDecal)
+ hoveringSelected = true;
+ renderDecal(rendererData_.get(), rendererData_->gfxSelected, decal);
+ }
+
+ // Render hovered.
+ rendererData_->gfxHovered.clear();
+ if (!hoveringSelected) {
+ renderDecal(rendererData_.get(), rendererData_->gfxHovered, 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_.get(), rendererData_->gfxHighlighted[i], decal);
}
}
}
@@ -336,7 +483,7 @@ void FPGAViewWidget::onSelectedArchItem(std::vector<DecalXY> decals)
{
QMutexLocker locker(&rendererArgsLock_);
rendererArgs_->selectedDecals = decals;
- rendererArgs_->highlightedOrSelectedChanged = true;
+ rendererArgs_->changed = true;
}
pokeRenderer();
}
@@ -346,19 +493,127 @@ 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) {
+ auto world = mouseToWorldCoordinates(event->x(), event->y());
+ auto closestOr = pickElement(world.x(), world.y());
+ if (!closestOr)
+ return;
+
+ auto closest = closestOr.value();
+ if (closest.type == ElementType::BEL) {
+ clickedBel(closest.element.bel);
+ } else if (closest.type == ElementType::WIRE) {
+ clickedWire(closest.element.wire);
+ }
+ }
+}
+
+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());
+ if (!closestOr)
+ 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, 0, 1);
+ vec = vp.inverted() * vec;
+ vec = projection.inverted() * vec;
+
+ auto ray = vec.toVector3DAffine();
+ auto world = QVector4D(ray.x()*ray.z(), -ray.y()*ray.z(), 0, 1);
+ world = viewMove_.inverted() * world;
+
+ return world;
+}
+
+QVector4D FPGAViewWidget::mouseToWorldDimensions(float x, float y)
+{
QMatrix4x4 p = getProjection();
QVector2D unit = p.map(QVector4D(1, 1, 0, 1)).toVector2DAffine();
@@ -367,18 +622,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;
diff --git a/gui/fpgaviewwidget.h b/gui/fpgaviewwidget.h
index 260ebf05..b1eda33a 100644
--- a/gui/fpgaviewwidget.h
+++ b/gui/fpgaviewwidget.h
@@ -20,6 +20,7 @@
#ifndef MAPGLWIDGET_H
#define MAPGLWIDGET_H
+#include <boost/optional.hpp>
#include <QMainWindow>
#include <QMutex>
#include <QOpenGLBuffer>
@@ -33,7 +34,9 @@
#include <QWaitCondition>
#include "nextpnr.h"
+#include "quadtree.h"
#include "lineshader.h"
+#include "designwidget.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -116,12 +119,60 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
void zoomSelected();
void zoomOutbound();
+ Q_SIGNALS:
+ void clickedBel(BelId bel);
+ void clickedWire(WireId wire);
+
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;
+ struct PickedElement {
+ ElementType type;
+ union Inner {
+ BelId bel;
+ WireId wire;
+ PipId pip;
+ GroupId group;
+
+ Inner(BelId _bel) : bel(_bel) {}
+ Inner(WireId _wire) : wire(_wire) {}
+ Inner(PipId _pip) : pip(_pip) {}
+ Inner(GroupId _group) : group(_group) {}
+ } element;
+ float x, y; // Decal X and Y
+ PickedElement(BelId bel, float x, float y) : type(ElementType::BEL), element(bel), x(x), y(y) {}
+ PickedElement(WireId wire, float x, float y) : type(ElementType::WIRE), element(wire), x(x), y(y) {}
+ PickedElement(PipId pip, float x, float y) : type(ElementType::PIP), element(pip), x(x), y(y) {}
+ PickedElement(GroupId group, float x, float y) : type(ElementType::GROUP), element(group), x(x), y(y) {}
+
+ DecalXY decal(Context *ctx) const
+ {
+ DecalXY decal;
+ switch (type) {
+ case ElementType::BEL:
+ decal = ctx->getBelDecal(element.bel);
+ break;
+ case ElementType::WIRE:
+ decal = ctx->getWireDecal(element.wire);
+ break;
+ case ElementType::PIP:
+ decal = ctx->getPipDecal(element.pip);
+ break;
+ case ElementType::GROUP:
+ decal = ctx->getGroupDecal(element.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_;
std::unique_ptr<PeriodicRunner> renderRunner_;
@@ -140,6 +191,7 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
QColor inactive;
QColor active;
QColor selected;
+ QColor hovered;
QColor highlight[8];
} colors_;
@@ -147,7 +199,12 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
{
LineShaderData gfxByStyle[GraphicElement::STYLE_MAX];
LineShaderData gfxSelected;
+ LineShaderData gfxHovered;
LineShaderData gfxHighlighted[8];
+ // Global bounding box of data from Arch.
+ float bbX0, bbY0, bbX1, bbY1;
+ // Quadtree for picking objects.
+ std::unique_ptr<PickQuadTree> qt;
};
std::unique_ptr<RendererData> rendererData_;
QMutex rendererDataLock_;
@@ -156,17 +213,21 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
{
std::vector<DecalXY> selectedDecals;
std::vector<DecalXY> highlightedDecals[8];
- bool highlightedOrSelectedChanged;
+ DecalXY hoveredDecal;
+ bool changed;
};
std::unique_ptr<RendererArgs> rendererArgs_;
QMutex rendererArgsLock_;
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(RendererData *data, LineShaderData &out, const GraphicElement &el, float x, float y);
+ void renderDecal(RendererData *data, LineShaderData &out, const DecalXY &decal);
+ void renderArchDecal(RendererData *data, 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/quadtree.h b/gui/quadtree.h
new file mode 100644
index 00000000..f803f770
--- /dev/null
+++ b/gui/quadtree.h
@@ -0,0 +1,397 @@
+/*
+ * 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_, x1_, y0_, y1_;
+ 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), x1_(x1), y0_(y0), y1_(y1) {}
+
+ BoundingBox(const BoundingBox &other) :
+ x0_(other.x0_), x1_(other.x1_), y0_(other.y0_), 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_);
+ }
+ };
+
+ 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 = -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;
+ }
+
+ 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;
+ }
+
+ // 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) {
+ 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) {
+ // 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)
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-10 08:31:16 +0000