diff options
author | John Firebaugh <john.firebaugh@gmail.com> | 2016-01-29 15:21:32 -0800 |
---|---|---|
committer | John Firebaugh <john.firebaugh@gmail.com> | 2016-02-10 15:40:20 -0800 |
commit | 7d6c6c00cac53a3864f0dfd399e64fd862d017e1 (patch) | |
tree | 0cbd724297db689cf07c79123b9a19e17c856e62 /src | |
parent | f52b6105db22aeafab0737ba2202d79ca60896f7 (diff) | |
download | qtlocation-mapboxgl-7d6c6c00cac53a3864f0dfd399e64fd862d017e1.tar.gz |
[core] Refactor tileCover
Diffstat (limited to 'src')
-rw-r--r-- | src/mbgl/map/source.cpp | 73 | ||||
-rw-r--r-- | src/mbgl/map/source.hpp | 10 | ||||
-rw-r--r-- | src/mbgl/map/tile_id.hpp | 19 | ||||
-rw-r--r-- | src/mbgl/map/transform_state.cpp | 13 | ||||
-rw-r--r-- | src/mbgl/map/transform_state.hpp | 4 | ||||
-rw-r--r-- | src/mbgl/util/box.hpp | 16 | ||||
-rw-r--r-- | src/mbgl/util/tile_coordinate.hpp | 16 | ||||
-rw-r--r-- | src/mbgl/util/tile_cover.cpp | 76 | ||||
-rw-r--r-- | src/mbgl/util/tile_cover.hpp | 12 |
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([¢er](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 |