Switch GridIndex to use float coordinates instead of int16s: fast way to prevent flicker from coordinate rounding.

4 files changed, 24 insertions, 21 deletions

diff --git a/src/mbgl/geometry/feature_index.cpp b/src/mbgl/geometry/feature_index.cpp
index f7dbbfb8b3..cef531f1fd 100644
--- a/src/mbgl/geometry/feature_index.cpp
+++ b/src/mbgl/geometry/feature_index.cpp
@@ -26,8 +26,10 @@ void FeatureIndex::insert(const GeometryCollection& geometries,
                           const std::string& sourceLayerName,
                           const std::string& bucketName) {
     for (const auto& ring : geometries) {
+        // TODO: Templatize grid units so feature index can stick with integers?
+        auto envelope = mapbox::geometry::envelope(ring);
         grid.insert(IndexedSubfeature { index, sourceLayerName, bucketName, sortIndex++ },
-                    mapbox::geometry::envelope(ring));
+                    {convertPoint<float>(envelope.min), convertPoint<float>(envelope.max)});
     }
 }
 
@@ -58,7 +60,8 @@ void FeatureIndex::query(
 
     // Query the grid index
     mapbox::geometry::box<int16_t> box = mapbox::geometry::envelope(queryGeometry);
-    std::vector<IndexedSubfeature> features = grid.query({ box.min - additionalRadius, box.max + additionalRadius });
+    std::vector<IndexedSubfeature> features = grid.query({ convertPoint<float>(box.min - additionalRadius),
+                                                           convertPoint<float>(box.max + additionalRadius) });
 
 
     std::sort(features.begin(), features.end(), topDown);
diff --git a/src/mbgl/text/collision_index.hpp b/src/mbgl/text/collision_index.hpp
index 65bd5baf2b..f074ea7d2b 100644
--- a/src/mbgl/text/collision_index.hpp
+++ b/src/mbgl/text/collision_index.hpp
@@ -16,7 +16,7 @@ struct TileDistance;
 class CollisionIndex {
 public:
     using CollisionGrid = GridIndex<IndexedSubfeature>;
-    using GridUnit = int16_t;
+    using GridUnit = float;
 
     explicit CollisionIndex(const TransformState&);
 
diff --git a/src/mbgl/util/grid_index.cpp b/src/mbgl/util/grid_index.cpp
index ee1be32352..1472325676 100644
--- a/src/mbgl/util/grid_index.cpp
+++ b/src/mbgl/util/grid_index.cpp
@@ -9,13 +9,13 @@ namespace mbgl {
 
 
 template <class T>
-GridIndex<T>::GridIndex(int32_t width_, int32_t height_, int32_t cellSize_) :
+GridIndex<T>::GridIndex(const float width_, const float height_, const int16_t cellSize_) :
     width(width_),
     height(height_),
-    xCellCount(std::ceil(float(width_) / cellSize_)),
-    yCellCount(std::ceil(float(height_) / cellSize_)),
-    xScale(float(xCellCount) / width_),
-    yScale(float(yCellCount) / height_)
+    xCellCount(std::ceil(width_ / cellSize_)),
+    yCellCount(std::ceil(height_ / cellSize_)),
+    xScale(xCellCount / width_),
+    yScale(yCellCount / height_)
     {
         boxCells.resize(xCellCount * yCellCount);
         circleCells.resize(xCellCount * yCellCount);
@@ -30,7 +30,7 @@ void GridIndex<T>::insert(T&& t, const BBox& bbox) {
     auto cx2 = convertToXCellCoord(bbox.max.x);
     auto cy2 = convertToYCellCoord(bbox.max.y);
 
-    int32_t x, y, cellIndex;
+    int16_t x, y, cellIndex;
     for (x = cx1; x <= cx2; ++x) {
         for (y = cy1; y <= cy2; ++y) {
             cellIndex = xCellCount * y + x;
@@ -50,7 +50,7 @@ void GridIndex<T>::insert(T&& t, const BCircle& bcircle) {
     auto cx2 = convertToXCellCoord(bcircle.center.x + bcircle.radius);
     auto cy2 = convertToYCellCoord(bcircle.center.y + bcircle.radius);
 
-    int32_t x, y, cellIndex;
+    int16_t x, y, cellIndex;
     for (x = cx1; x <= cx2; ++x) {
         for (y = cy1; y <= cy2; ++y) {
             cellIndex = xCellCount * y + x;
@@ -113,7 +113,7 @@ void GridIndex<T>::query(const BBox& queryBBox, std::function<bool (const T&)> r
     auto cx2 = convertToXCellCoord(queryBBox.max.x);
     auto cy2 = convertToYCellCoord(queryBBox.max.y);
 
-    int32_t x, y, cellIndex;
+    int16_t x, y, cellIndex;
     for (x = cx1; x <= cx2; ++x) {
         for (y = cy1; y <= cy2; ++y) {
             cellIndex = xCellCount * y + x;
@@ -160,7 +160,7 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
     auto cx2 = convertToXCellCoord(queryBCircle.center.x + queryBCircle.radius);
     auto cy2 = convertToYCellCoord(queryBCircle.center.y + queryBCircle.radius);
 
-    int32_t x, y, cellIndex;
+    int16_t x, y, cellIndex;
     for (x = cx1; x <= cx2; ++x) {
         for (y = cy1; y <= cy2; ++y) {
             cellIndex = xCellCount * y + x;
@@ -198,12 +198,12 @@ void GridIndex<T>::query(const BCircle& queryBCircle, std::function<bool (const
 }
 
 template <class T>
-int32_t GridIndex<T>::convertToXCellCoord(int32_t x) const {
+int16_t GridIndex<T>::convertToXCellCoord(const float x) const {
     return util::max(0.0, util::min(xCellCount - 1.0, std::floor(x * xScale)));
 }
 
 template <class T>
-int32_t GridIndex<T>::convertToYCellCoord(int32_t y) const {
+int16_t GridIndex<T>::convertToYCellCoord(const float y) const {
     return util::max(0.0, util::min(yCellCount - 1.0, std::floor(y * yScale)));
 }
 
diff --git a/src/mbgl/util/grid_index.hpp b/src/mbgl/util/grid_index.hpp
index d7f9bf14f1..9c1b1524e6 100644
--- a/src/mbgl/util/grid_index.hpp
+++ b/src/mbgl/util/grid_index.hpp
@@ -57,10 +57,10 @@ namespace mbgl {
 template <class T>
 class GridIndex {
 public:
-    GridIndex(int32_t width_, int32_t height_, int32_t cellSize_);
+    GridIndex(const float width_, const float height_, const int16_t cellSize_);
 
-    using BBox = mapbox::geometry::box<int16_t>;
-    using BCircle = mapbox::geometry::circle<int16_t>;
+    using BBox = mapbox::geometry::box<float>;
+    using BCircle = mapbox::geometry::circle<float>;
 
     void insert(T&& t, const BBox&);
     void insert(T&& t, const BCircle&);
@@ -78,15 +78,15 @@ private:
     void query(const BBox&, std::function<bool (const T&)>) const;
     void query(const BCircle&, std::function<bool (const T&)>) const;
 
-    int32_t convertToXCellCoord(int32_t x) const;
-    int32_t convertToYCellCoord(int32_t y) const;
+    int16_t convertToXCellCoord(const float x) const;
+    int16_t convertToYCellCoord(const float y) const;
     
     bool boxesCollide(const BBox&, const BBox&) const;
     bool circlesCollide(const BCircle&, const BCircle&) const;
     bool circleAndBoxCollide(const BCircle&, const BBox&) const;
 
-    const int32_t width;
-    const int32_t height;
+    const float width;
+    const float height;
     
     const int16_t xCellCount;
     const int16_t yCellCount;