[core] Refactor tileCover

9 files changed, 117 insertions, 122 deletions

diff --git a/src/mbgl/map/source.cpp b/src/mbgl/map/source.cpp
index 55d87d988e..e763674040 100644
--- a/src/mbgl/map/source.cpp
+++ b/src/mbgl/map/source.cpp
@@ -11,8 +11,6 @@
 #include <mbgl/storage/resource.hpp>
 #include <mbgl/storage/response.hpp>
 #include <mbgl/util/math.hpp>
-#include <mbgl/util/box.hpp>
-#include <mbgl/util/tile_coordinate.hpp>
 #include <mbgl/storage/file_source.hpp>
 #include <mbgl/style/style_layer.hpp>
 #include <mbgl/style/style_update_parameters.hpp>
@@ -294,47 +292,6 @@ TileData::State Source::addTile(const TileID& tileID, const StyleUpdateParameter
     return newState;
 }
 
-double Source::getZoom(const TransformState& state) const {
-    double offset = std::log(util::tileSize / tileSize) / std::log(2);
-    return state.getZoom() + offset;
-}
-
-int32_t Source::coveringZoomLevel(const TransformState& state) const {
-    double zoom = getZoom(state);
-    if (type == SourceType::Raster || type == SourceType::Video) {
-        zoom = ::round(zoom);
-    } else {
-        zoom = std::floor(zoom);
-    }
-    return util::clamp(zoom, state.getMinZoom(), state.getMaxZoom());
-}
-
-std::forward_list<TileID> Source::coveringTiles(const TransformState& state) const {
-    int32_t z = coveringZoomLevel(state);
-
-    auto actualZ = z;
-    const bool reparseOverscaled =
-        type == SourceType::Vector ||
-        type == SourceType::Annotations;
-
-    if (z < info->minZoom) return {{}};
-    if (z > info->maxZoom) z = info->maxZoom;
-
-    // Map four viewport corners to pixel coordinates
-    box points = state.cornersToBox(z);
-    const TileCoordinate center = state.pointToCoordinate({ state.getWidth() / 2.0f, state.getHeight()/ 2.0f }).zoomTo(z);
-
-    std::forward_list<TileID> covering_tiles = tileCover(z, points, reparseOverscaled ? actualZ : z);
-
-    covering_tiles.sort([&center](const TileID& a, const TileID& b) {
-        // Sorts by distance from the box center
-        return std::fabs(a.x - center.column) + std::fabs(a.y - center.row) <
-               std::fabs(b.x - center.column) + std::fabs(b.y - center.row);
-    });
-
-    return covering_tiles;
-}
-
 /**
  * Recursively find children of the given tile that are already loaded.
  *
@@ -344,14 +301,14 @@ std::forward_list<TileID> Source::coveringTiles(const TransformState& state) con
  *
  * @return boolean Whether the children found completely cover the tile.
  */
-bool Source::findLoadedChildren(const TileID& tileID, int32_t maxCoveringZoom, std::forward_list<TileID>& retain) {
+bool Source::findLoadedChildren(const TileID& tileID, int32_t maxCoveringZoom, std::vector<TileID>& retain) {
     bool complete = true;
     int32_t z = tileID.z;
     auto ids = tileID.children(info->maxZoom);
     for (const auto& child_id : ids) {
         const TileData::State state = hasTile(child_id);
         if (TileData::isReadyState(state)) {
-            retain.emplace_front(child_id);
+            retain.emplace_back(child_id);
         }
         if (state != TileData::State::parsed) {
             complete = false;
@@ -373,12 +330,12 @@ bool Source::findLoadedChildren(const TileID& tileID, int32_t maxCoveringZoom, s
  *
  * @return boolean Whether a parent was found.
  */
-void Source::findLoadedParent(const TileID& tileID, int32_t minCoveringZoom, std::forward_list<TileID>& retain) {
+void Source::findLoadedParent(const TileID& tileID, int32_t minCoveringZoom, std::vector<TileID>& retain) {
     for (int32_t z = tileID.z - 1; z >= minCoveringZoom; --z) {
         const TileID parent_id = tileID.parent(z, info->maxZoom);
         const TileData::State state = hasTile(parent_id);
         if (TileData::isReadyState(state)) {
-            retain.emplace_front(parent_id);
+            retain.emplace_back(parent_id);
             if (state == TileData::State::parsed) {
                 return;
             }
@@ -393,17 +350,29 @@ bool Source::update(const StyleUpdateParameters& parameters) {
         return allTilesUpdated;
     }
 
-    double zoom = coveringZoomLevel(parameters.transformState);
-    std::forward_list<TileID> required = coveringTiles(parameters.transformState);
-
-    // Determine the overzooming/underzooming amounts.
+    // Determine the overzooming/underzooming amounts and required tiles.
+    std::vector<TileID> required;
+    int32_t zoom = coveringZoomLevel(parameters.transformState.getZoom(), type, tileSize);
     int32_t minCoveringZoom = util::clamp<int32_t>(zoom - 10, info->minZoom, info->maxZoom);
     int32_t maxCoveringZoom = util::clamp<int32_t>(zoom + 1,  info->minZoom, info->maxZoom);
 
+    if (zoom >= info->minZoom) {
+        const bool reparseOverscaled =
+            type == SourceType::Vector ||
+            type == SourceType::Annotations;
+
+        const auto actualZ = zoom;
+        if (zoom > info->maxZoom) {
+            zoom = info->maxZoom;
+        }
+
+        required = tileCover(parameters.transformState, zoom, reparseOverscaled ? actualZ : zoom);
+    }
+
     // Retain is a list of tiles that we shouldn't delete, even if they are not
     // the most ideal tile for the current viewport. This may include tiles like
     // parent or child tiles that are *already* loaded.
-    std::forward_list<TileID> retain(required);
+    std::vector<TileID> retain(required);
 
     // Add existing child/parent tiles if the actual tile is not yet loaded
     for (const auto& tileID : required) {
diff --git a/src/mbgl/map/source.hpp b/src/mbgl/map/source.hpp
index cca160a726..7f69fc2881 100644
--- a/src/mbgl/map/source.hpp
+++ b/src/mbgl/map/source.hpp
@@ -7,7 +7,7 @@
 #include <mbgl/util/mat4.hpp>
 #include <mbgl/util/rapidjson.hpp>
 
-#include <forward_list>
+#include <vector>
 #include <map>
 
 namespace mapbox {
@@ -82,17 +82,13 @@ private:
                              std::exception_ptr,
                              bool isNewTile);
     bool handlePartialTile(const TileID&);
-    bool findLoadedChildren(const TileID&, int32_t maxCoveringZoom, std::forward_list<TileID>& retain);
-    void findLoadedParent(const TileID&, int32_t minCoveringZoom, std::forward_list<TileID>& retain);
-    int32_t coveringZoomLevel(const TransformState&) const;
-    std::forward_list<TileID> coveringTiles(const TransformState&) const;
+    bool findLoadedChildren(const TileID&, int32_t maxCoveringZoom, std::vector<TileID>& retain);
+    void findLoadedParent(const TileID&, int32_t minCoveringZoom, std::vector<TileID>& retain);
 
     TileData::State addTile(const TileID&, const StyleUpdateParameters&);
     TileData::State hasTile(const TileID&);
     void updateTilePtrs();
 
-    double getZoom(const TransformState &state) const;
-
 private:
     std::unique_ptr<const SourceInfo> info;
 
diff --git a/src/mbgl/map/tile_id.hpp b/src/mbgl/map/tile_id.hpp
index 3ecc5c6cef..a193b63392 100644
--- a/src/mbgl/map/tile_id.hpp
+++ b/src/mbgl/map/tile_id.hpp
@@ -26,12 +26,6 @@ public:
         return ((std::pow(2, z) * y + x) * 32) + z;
     }
 
-    struct Hash {
-        std::size_t operator()(const TileID& id) const {
-            return std::hash<uint64_t>()(id.to_uint64());
-        }
-    };
-
     inline bool operator==(const TileID& rhs) const {
         return w == rhs.w && z == rhs.z && x == rhs.x && y == rhs.y;
     }
@@ -53,9 +47,20 @@ public:
     children(int8_t sourceMaxZoom = std::numeric_limits<int8_t>::max()) const;
     bool isChildOf(const TileID&) const;
     operator std::string() const;
-
 };
 
 } // namespace mbgl
 
+namespace std {
+template <>
+struct hash<mbgl::TileID> {
+    typedef mbgl::TileID argument_type;
+    typedef std::size_t result_type;
+
+    result_type operator()(const mbgl::TileID& id) const {
+            return std::hash<uint64_t>()(id.to_uint64());
+    }
+};
+} // namespace std
+
 #endif
diff --git a/src/mbgl/map/transform_state.cpp b/src/mbgl/map/transform_state.cpp
index 5e74f76229..42fbd9af87 100644
--- a/src/mbgl/map/transform_state.cpp
+++ b/src/mbgl/map/transform_state.cpp
@@ -1,7 +1,6 @@
 #include <mbgl/map/transform_state.hpp>
 #include <mbgl/map/tile_id.hpp>
 #include <mbgl/util/constants.hpp>
-#include <mbgl/util/box.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
 #include <mbgl/util/interpolate.hpp>
 #include <mbgl/util/math.hpp>
@@ -54,18 +53,6 @@ void TransformState::getProjMatrix(mat4& projMatrix) const {
             pixel_y() - getHeight() / 2.0f, 0);
 }
 
-box TransformState::cornersToBox(uint32_t z) const {
-    double w = width;
-    double h = height;
-    box b(
-    pointToCoordinate({ 0, 0 }).zoomTo(z),
-    pointToCoordinate({ w, 0 }).zoomTo(z),
-    pointToCoordinate({ w, h }).zoomTo(z),
-    pointToCoordinate({ 0, h }).zoomTo(z));
-    return b;
-}
-
-
 #pragma mark - Dimensions
 
 uint16_t TransformState::getWidth() const {
diff --git a/src/mbgl/map/transform_state.hpp b/src/mbgl/map/transform_state.hpp
index 2aef5707fa..a276c08868 100644
--- a/src/mbgl/map/transform_state.hpp
+++ b/src/mbgl/map/transform_state.hpp
@@ -15,8 +15,7 @@
 namespace mbgl {
 
 class TileID;
-struct box;
-struct TileCoordinate;
+class TileCoordinate;
 
 class TransformState {
     friend class Transform;
@@ -27,7 +26,6 @@ public:
     // Matrix
     void matrixFor(mat4& matrix, const TileID& id, const int8_t z) const;
     void getProjMatrix(mat4& matrix) const;
-    box cornersToBox(uint32_t z) const;
 
     // Dimensions
     uint16_t getWidth() const;
diff --git a/src/mbgl/util/box.hpp b/src/mbgl/util/box.hpp
deleted file mode 100644
index 2806fb95fc..0000000000
--- a/src/mbgl/util/box.hpp
+++ /dev/null
@@ -1,16 +0,0 @@
-#ifndef MBGL_UTIL_BOX
-#define MBGL_UTIL_BOX
-
-#include <mbgl/util/tile_coordinate.hpp>
-
-namespace mbgl {
-
-struct box {
-    box(TileCoordinate tl_, TileCoordinate tr_, TileCoordinate br_, TileCoordinate bl_) :
-        tl(tl_), tr(tr_), br(br_), bl(bl_) {}
-    TileCoordinate tl, tr, br, bl;
-};
-
-} // namespace mbgl
-
-#endif
diff --git a/src/mbgl/util/tile_coordinate.hpp b/src/mbgl/util/tile_coordinate.hpp
index 4710e08d0a..a989bef0c9 100644
--- a/src/mbgl/util/tile_coordinate.hpp
+++ b/src/mbgl/util/tile_coordinate.hpp
@@ -5,23 +5,11 @@
 
 namespace mbgl {
 
-struct TileCoordinate {
+class TileCoordinate {
+public:
     double column;
     double row;
     double zoom;
-
-    TileCoordinate(double column_, double row_, double zoom_) :
-        column(column_), row(row_), zoom(zoom_) {}
-
-    TileCoordinate zoomTo(double targetZoom) {
-        double scale = std::pow(2, targetZoom - zoom);
-        return { column * scale, row * scale, targetZoom };
-    }
-
-    TileCoordinate operator-(TileCoordinate c) {
-        c = c.zoomTo(zoom);
-        return { column - c.column, row - c.row, zoom };
-    };
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/util/tile_cover.cpp b/src/mbgl/util/tile_cover.cpp
index 803aa53eee..a9c265089b 100644
--- a/src/mbgl/util/tile_cover.cpp
+++ b/src/mbgl/util/tile_cover.cpp
@@ -1,7 +1,9 @@
 #include <mbgl/util/tile_cover.hpp>
 #include <mbgl/util/vec.hpp>
-#include <mbgl/util/box.hpp>
 #include <mbgl/util/tile_coordinate.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/map/source_info.hpp>
+#include <mbgl/map/transform_state.hpp>
 
 namespace mbgl {
 
@@ -66,7 +68,27 @@ static void scanTriangle(const mbgl::vec2<double> a, const mbgl::vec2<double> b,
     if (bc.dy) scanSpans(ca, bc, ymin, ymax, scanLine);
 }
 
-std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds, int8_t actualZ) {
+int32_t coveringZoomLevel(double zoom, SourceType type, uint16_t tileSize) {
+    zoom += std::log(util::tileSize / tileSize) / std::log(2);
+    if (type == SourceType::Raster || type == SourceType::Video) {
+        return ::round(zoom);
+    } else {
+        return std::floor(zoom);
+    }
+}
+
+static mbgl::vec2<double> zoomTo(const TileCoordinate& c, double z) {
+    double scale = std::pow(2, z - c.zoom);
+    return { c.column * scale, c.row * scale };
+}
+
+std::vector<TileID> tileCover(const TileCoordinate& tl_,
+                              const TileCoordinate& tr_,
+                              const TileCoordinate& br_,
+                              const TileCoordinate& bl_,
+                              const TileCoordinate& center,
+                              int32_t z,
+                              int32_t actualZ) {
     int32_t tiles = 1 << z;
     std::forward_list<mbgl::TileID> t;
 
@@ -79,10 +101,11 @@ std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds, int8_t ac
         }
     };
 
-    mbgl::vec2<double> tl = { bounds.tl.column, bounds.tl.row };
-    mbgl::vec2<double> tr = { bounds.tr.column, bounds.tr.row };
-    mbgl::vec2<double> br = { bounds.br.column, bounds.br.row };
-    mbgl::vec2<double> bl = { bounds.bl.column, bounds.bl.row };
+    mbgl::vec2<double> tl = zoomTo(tl_, z);
+    mbgl::vec2<double> tr = zoomTo(tr_, z);
+    mbgl::vec2<double> br = zoomTo(br_, z);
+    mbgl::vec2<double> bl = zoomTo(bl_, z);
+    mbgl::vec2<double> c  = zoomTo(center, z);
 
     // Divide the screen up in two triangles and scan each of them:
     // \---+
@@ -94,7 +117,46 @@ std::forward_list<TileID> tileCover(int8_t z, const mbgl::box &bounds, int8_t ac
     t.sort();
     t.unique();
 
-    return t;
+    t.sort([&](const TileID& a, const TileID& b) {
+        // Sorts by distance from the box center
+        return std::fabs(a.x - c.x) + std::fabs(a.y - c.y) <
+               std::fabs(b.x - c.x) + std::fabs(b.y - c.y);
+    });
+
+    return std::vector<TileID>(t.begin(), t.end());
+}
+
+std::vector<TileID> tileCover(const LatLngBounds& bounds_, int32_t z, int32_t actualZ) {
+    if (bounds_.isEmpty() ||
+        bounds_.south() >  util::LATITUDE_MAX ||
+        bounds_.north() < -util::LATITUDE_MAX) {
+        return {};
+    }
+
+    LatLngBounds bounds = LatLngBounds::hull(
+        { std::max(bounds_.south(), -util::LATITUDE_MAX), bounds_.west() },
+        { std::min(bounds_.north(),  util::LATITUDE_MAX), bounds_.east() });
+
+    const TransformState state;
+    return tileCover(
+        state.latLngToCoordinate(bounds.northwest()),
+        state.latLngToCoordinate(bounds.northeast()),
+        state.latLngToCoordinate(bounds.southeast()),
+        state.latLngToCoordinate(bounds.southwest()),
+        state.latLngToCoordinate(bounds.center()),
+        z, actualZ);
+}
+
+std::vector<TileID> tileCover(const TransformState& state, int32_t z, int32_t actualZ) {
+    const double w = state.getWidth();
+    const double h = state.getHeight();
+    return tileCover(
+        state.pointToCoordinate({ 0,   0   }),
+        state.pointToCoordinate({ w,   0   }),
+        state.pointToCoordinate({ w,   h   }),
+        state.pointToCoordinate({ 0,   h   }),
+        state.pointToCoordinate({ w/2, h/2 }),
+        z, actualZ);
 }
 
 } // namespace mbgl
diff --git a/src/mbgl/util/tile_cover.hpp b/src/mbgl/util/tile_cover.hpp
index 0514c36b62..a489964abf 100644
--- a/src/mbgl/util/tile_cover.hpp
+++ b/src/mbgl/util/tile_cover.hpp
@@ -2,13 +2,19 @@
 #define MBGL_UTIL_TILE_COVER
 
 #include <mbgl/map/tile_id.hpp>
-#include <mbgl/util/box.hpp>
+#include <mbgl/style/types.hpp>
 
-#include <forward_list>
+#include <vector>
 
 namespace mbgl {
 
-std::forward_list<TileID> tileCover(int8_t z, const box& bounds, int8_t actualZ);
+class TransformState;
+class LatLngBounds;
+
+int32_t coveringZoomLevel(double z, SourceType type, uint16_t tileSize);
+
+std::vector<TileID> tileCover(const TransformState&, int32_t z, int32_t actualZ);
+std::vector<TileID> tileCover(const LatLngBounds&,   int32_t z, int32_t actualZ);
 
 } // namespace mbgl