aboutsummaryrefslogtreecommitdiffstats
path: root/gui
diff options
context:
space:
mode:
Diffstat (limited to 'gui')
-rw-r--r--gui/basewindow.cc1
-rw-r--r--gui/designwidget.cc7
-rw-r--r--gui/designwidget.h1
-rw-r--r--gui/fpgaviewwidget.cc61
-rw-r--r--gui/fpgaviewwidget.h21
-rw-r--r--gui/quadtree.h387
6 files changed, 469 insertions, 9 deletions
diff --git a/gui/basewindow.cc b/gui/basewindow.cc
index e07200de..cc6ef4a5 100644
--- a/gui/basewindow.cc
+++ b/gui/basewindow.cc
@@ -82,6 +82,7 @@ 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(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 2bba8532..989b55fe 100644
--- a/gui/designwidget.cc
+++ b/gui/designwidget.cc
@@ -507,6 +507,13 @@ 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::onItemSelectionChanged()
{
if (treeWidget->selectedItems().size() == 0)
diff --git a/gui/designwidget.h b/gui/designwidget.h
index 6d4b7fe1..85c326d0 100644
--- a/gui/designwidget.h
+++ b/gui/designwidget.h
@@ -74,6 +74,7 @@ class DesignWidget : public QWidget
public Q_SLOTS:
void newContext(Context *ctx);
void updateTree();
+ void onClickedBel(BelId bel);
private:
Context *ctx;
diff --git a/gui/fpgaviewwidget.cc b/gui/fpgaviewwidget.cc
index de73e27b..ed3a0bce 100644
--- a/gui/fpgaviewwidget.cc
+++ b/gui/fpgaviewwidget.cc
@@ -171,8 +171,8 @@ 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();
// Render grid.
auto grid = LineShaderData();
@@ -276,10 +276,13 @@ void FPGAViewWidget::renderLines(void)
rendererArgs_->highlightedOrSelectedChanged = false;
}
+ QuadTreeBels::BoundingBox globalBB = QuadTreeBels::BoundingBox(-1000, -1000, 1000, 1000);
+
// Render decals if necessary.
if (decalsChanged) {
auto data = std::unique_ptr<FPGAViewWidget::RendererData>(new FPGAViewWidget::RendererData);
// Draw Bels.
+ data->qtBels = std::unique_ptr<QuadTreeBels>(new QuadTreeBels(globalBB));
for (auto const &decal : belDecals) {
drawArchDecal(data->gfxByStyle, decal);
}
@@ -353,12 +356,50 @@ void FPGAViewWidget::onHighlightGroupChanged(std::vector<DecalXY> decals, int gr
void FPGAViewWidget::resizeGL(int width, int height) {}
-void FPGAViewWidget::mousePressEvent(QMouseEvent *event) { lastDragPos_ = event->pos(); }
+void FPGAViewWidget::mousePressEvent(QMouseEvent *event)
+{
+ if (event->buttons() & Qt::RightButton || event->buttons() & Qt::MidButton) {
+ lastDragPos_ = event->pos();
+ }
+ if (event->buttons() & Qt::LeftButton) {
+ int x = event->x();
+ int y = event->y();
+ auto world = mouseToWorldCoordinates(x, y);
+ rendererDataLock_.lock();
+ if (rendererData_->qtBels != nullptr) {
+ auto elems = rendererData_->qtBels->get(world.x(), world.y());
+ if (elems.size() > 0) {
+ clickedBel(elems[0]);
+ }
+ }
+ rendererDataLock_.unlock();
+ }
+}
// 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(int x, int y)
+{
QMatrix4x4 p = getProjection();
QVector2D unit = p.map(QVector4D(1, 1, 0, 1)).toVector2DAffine();
@@ -369,14 +410,16 @@ QVector4D FPGAViewWidget::mouseToWorldCoordinates(int x, int y)
void FPGAViewWidget::mouseMoveEvent(QMouseEvent *event)
{
- const int dx = event->x() - lastDragPos_.x();
- const int dy = event->y() - lastDragPos_.y();
- lastDragPos_ = event->pos();
+ 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 = mouseToWorldCoordinates(dx, dy);
- viewMove_.translate(world.x(), -world.y());
+ auto world = mouseToWorldDimensions(dx, dy);
+ viewMove_.translate(world.x(), -world.y());
- update();
+ update();
+ }
}
void FPGAViewWidget::wheelEvent(QWheelEvent *event)
diff --git a/gui/fpgaviewwidget.h b/gui/fpgaviewwidget.h
index 260ebf05..a360eea7 100644
--- a/gui/fpgaviewwidget.h
+++ b/gui/fpgaviewwidget.h
@@ -33,6 +33,7 @@
#include <QWaitCondition>
#include "nextpnr.h"
+#include "quadtree.h"
#include "lineshader.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -116,6 +117,9 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
void zoomSelected();
void zoomOutbound();
+ Q_SIGNALS:
+ void clickedBel(BelId bel);
+
private:
const float zoomNear_ = 1.0f; // do not zoom closer than this
const float zoomFar_ = 10000.0f; // do not zoom further than this
@@ -126,6 +130,21 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
QTimer paintTimer_;
std::unique_ptr<PeriodicRunner> renderRunner_;
+ using QuadTreeBels = QuadTree<float, BelId>;
+
+ template <typename T>
+ void commitToQuadtree(T *tree, const DecalXY &decal, BelId bel)
+ {
+ float offsetX = decal.x;
+ float offsetY = decal.y;
+
+ for (auto &el : ctx_->getDecalGraphics(decal.decal)) {
+ if (el.type == GraphicElement::TYPE_BOX) {
+ tree->insert(typename T::BoundingBox(offsetX + el.x1, offsetY + el.y1, offsetX + el.x2, offsetY + el.y2), bel);
+ }
+ }
+ }
+
QPoint lastDragPos_;
LineShader lineShader_;
QMatrix4x4 viewMove_;
@@ -148,6 +167,7 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
LineShaderData gfxByStyle[GraphicElement::STYLE_MAX];
LineShaderData gfxSelected;
LineShaderData gfxHighlighted[8];
+ std::unique_ptr<QuadTreeBels> qtBels;
};
std::unique_ptr<RendererData> rendererData_;
QMutex rendererDataLock_;
@@ -167,6 +187,7 @@ class FPGAViewWidget : public QOpenGLWidget, protected QOpenGLFunctions
void drawDecal(LineShaderData &out, const DecalXY &decal);
void drawArchDecal(LineShaderData out[GraphicElement::STYLE_MAX], const DecalXY &decal);
QVector4D mouseToWorldCoordinates(int x, int y);
+ QVector4D mouseToWorldDimensions(int x, int y);
QMatrix4x4 getProjection(void);
};
diff --git a/gui/quadtree.h b/gui/quadtree.h
new file mode 100644
index 00000000..2b5a9df5
--- /dev/null
+++ b/gui/quadtree.h
@@ -0,0 +1,387 @@
+/*
+ * 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;
+ }
+ };
+
+ 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(void) 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(const BoundingBox &k, ElementT v)
+ {
+ return root_.insert(k, v);
+ }
+
+ // Dump a human-readable representation of the tree to stdout.
+ void dump(void) const
+ {
+ root_.dump(0);
+ }
+
+ // Return count of BoundingBoxes/Elements contained.
+ // @returns count of elements contained.
+ size_t size(void) 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 std::move(res);
+ }
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-02 21:12:54 +0000