Merge remote-tracking branch 'origin/master' into redist_slack

7 files changed, 1045 insertions, 102 deletions

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