From 737665bc070e9db4544b5d78ca69baf72ec958dc Mon Sep 17 00:00:00 2001
From: Mikhail Pozdnyakov <mikhail.pozdnyakov@mapbox.com>
Date: Thu, 6 Jun 2019 11:26:52 +0300
Subject: [core] Refactor tile pyramid

Tile pyramid is no longer operating with `RenderTiles` and does not perform
rendering operations (upload, finish render).

Render tiles belong to rendering, and tile pyramid belongs to orchestration.
---
 src/mbgl/algorithm/update_tile_masks.hpp           | 70 ++++++++-------
 src/mbgl/renderer/render_tile.cpp                  |  2 +-
 src/mbgl/renderer/render_tile.hpp                  |  2 -
 .../renderer/sources/render_raster_dem_source.cpp  |  6 +-
 .../renderer/sources/render_raster_dem_source.hpp  |  2 -
 src/mbgl/renderer/sources/render_raster_source.cpp |  2 +-
 src/mbgl/renderer/sources/render_tile_source.cpp   | 18 +++-
 src/mbgl/renderer/sources/render_tile_source.hpp   |  1 +
 src/mbgl/renderer/tile_pyramid.cpp                 | 99 +++++++++-------------
 src/mbgl/renderer/tile_pyramid.hpp                 | 10 +--
 src/mbgl/tile/tile.hpp                             |  4 +
 11 files changed, 101 insertions(+), 115 deletions(-)

diff --git a/src/mbgl/algorithm/update_tile_masks.hpp b/src/mbgl/algorithm/update_tile_masks.hpp
index c475473cb6..80e0a39be1 100644
--- a/src/mbgl/algorithm/update_tile_masks.hpp
+++ b/src/mbgl/algorithm/update_tile_masks.hpp
@@ -11,26 +11,38 @@ namespace algorithm {
 
 namespace {
 
-template <typename Renderable>
+template <typename T>
+bool tileNeedsMask(const std::reference_wrapper<T>& tile) { return tile.get().usedByRenderedLayers; }
+template <typename T> 
+void setTileMask(const std::reference_wrapper<T>& tile, TileMask&& mask ) { return tile.get().setMask(std::move(mask)); }
+
+// Overloads for tests
+template <typename T> bool tileNeedsMask(const T& tile) { return tile.usedByRenderedLayers; }
+template <typename T> void setTileMask(T& tile, TileMask&& mask ) { return tile.setMask(std::move(mask)); }
+
+template <typename Iterator>
 void computeTileMasks(
     const CanonicalTileID& root,
-    const UnwrappedTileID ref,
-    typename std::vector<std::reference_wrapper<Renderable>>::const_iterator it,
-    const typename std::vector<std::reference_wrapper<Renderable>>::const_iterator end,
+    const UnwrappedTileID& ref,
+    const Iterator begin,
+    const Iterator end,
     TileMask& mask) {
     // If the reference or any of its children is found in the list, we need to recurse.
-    for (; it != end; ++it) {
-        auto& renderable = it->get();
-        if (!renderable.used) {
+    for (auto it = begin; it != end; ++it) {
+        const UnwrappedTileID& id = it->first;
+        if (!tileNeedsMask(it->second)) {
             continue;
         }
-        if (ref == renderable.id) {
+
+        if (ref == id) {
             // The current tile is masked out, so we don't need to add them to the mask set.
             return;
-        } else if (renderable.id.isChildOf(ref)) {
+        } 
+
+        if (id.isChildOf(ref)) {
             // There's at least one child tile that is masked out, so recursively descend.
             for (const auto& child : ref.children()) {
-                computeTileMasks<Renderable>(root, child, it, end, mask);
+                computeTileMasks(root, child, it, end, mask);
             }
             return;
         }
@@ -45,10 +57,10 @@ void computeTileMasks(
 
 } // namespace
 
-// Updates the TileMasks for all renderables. Renderables are objects that have an UnwrappedTileID
-// property indicating where they should be rendered on the screen. A TileMask describes all regions
-// within that tile that are *not* covered by other Renderables.
-// Example: Renderables in our list are 2/1/3, 3/3/6, and 4/5/13. The schematic for creating the
+// Updates the TileMasks for all renderable tiles. Each renderable tile has a corresponding UnwrappedTileID
+// indicating where it should be rendered on the screen. A TileMask describes all regions
+// within a renderable tile that are *not* covered by other renderable tiles.
+// Example: Renderable tiles in our list are 2/1/3, 3/3/6, and 4/5/13. The schematic for creating the
 // TileMask for 2/1/3 looks like this:
 //
 //    ┌────────┬────────┬─────────────────┐
@@ -70,7 +82,7 @@ void computeTileMasks(
 //    └─────────────────┴─────────────────┘
 //
 // The TileMask for 2/1/3 thus consists of the tiles 4/4/12, 4/5/12, 4/4/13, 3/2/7, and 3/3/7,
-// but it does *not* include 4/5/13, and 3/3/6, since these are other Renderables.
+// but it does *not* include 4/5/13, and 3/3/6, since these are other renderable tiles.
 // A TileMask always contains TileIDs *relative* to the tile it is generated for, so 2/1/3 is
 // "subtracted" from these TileIDs. The final TileMask for 2/1/3 will thus be:
 //
@@ -92,21 +104,16 @@ void computeTileMasks(
 //    │                 │                 │
 //    └─────────────────┴─────────────────┘
 //
-// Only other Renderables that are *children* of the Renderable we are generating the mask for will
-// be considered. For example, adding a Renderable with TileID 4/8/13 won't affect the TileMask for
+// Only other renderable tiles that are *children* of the renderable tile we are generating the mask for will
+// will be considered. For example, adding a renderable tile with TileID 4/8/13 won't affect the TileMask for
 // 2/1/3, since it is not a descendant of it.
-//
-// The given |renderables| must be sorted by id.
-template <typename Renderable>
-void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables) {
-    assert(std::is_sorted(renderables.begin(), renderables.end(),
-        [](const Renderable& a, const Renderable& b) { return a.id < b.id; }));
-
+template <typename RenderableTilesMap>
+void updateTileMasks(RenderableTilesMap& renderables) {
     TileMask mask;
     const auto end = renderables.end();
-    for (auto it = renderables.begin(); it != end; it++) {
-        auto& renderable = it->get();
-        if (!renderable.used) {
+    for (auto it = renderables.begin(); it != end; ++it) {
+        const UnwrappedTileID& id = it->first;
+        if (!tileNeedsMask(it->second)) {
             continue;
         }
         // Try to add all remaining ids as children. We sorted the tile list
@@ -116,13 +123,12 @@ void updateTileMasks(std::vector<std::reference_wrapper<Renderable>> renderables
         auto child_it = std::next(it);
         const auto children_end = std::lower_bound(
             child_it, end,
-            UnwrappedTileID{ static_cast<int16_t>(renderable.id.wrap + 1), { 0, 0, 0 } },
-            [](auto& a, auto& b) { return a.get().id < b; });
+            UnwrappedTileID{ static_cast<int16_t>(id.wrap + 1), { 0, 0, 0 } },
+            [](auto& a, auto& b) { return a.first < b; });
 
         mask.clear();
-        computeTileMasks<Renderable>(renderable.id.canonical, renderable.id, child_it, children_end,
-                                     mask);
-        renderable.setMask(std::move(mask));
+        computeTileMasks(id.canonical, id, child_it, children_end, mask);
+        setTileMask(it->second, std::move(mask));
     }
 }
 
diff --git a/src/mbgl/renderer/render_tile.cpp b/src/mbgl/renderer/render_tile.cpp
index b8fb4b2a11..f1f6a4ac45 100644
--- a/src/mbgl/renderer/render_tile.cpp
+++ b/src/mbgl/renderer/render_tile.cpp
@@ -130,7 +130,7 @@ void RenderTile::prepare(const SourcePrepareParameters& parameters) {
 }
 
 void RenderTile::finishRender(PaintParameters& parameters) {
-    if (!used || parameters.debugOptions == MapDebugOptions::NoDebug)
+    if (!tile.usedByRenderedLayers || parameters.debugOptions == MapDebugOptions::NoDebug)
         return;
 
     static const style::Properties<>::PossiblyEvaluated properties {};
diff --git a/src/mbgl/renderer/render_tile.hpp b/src/mbgl/renderer/render_tile.hpp
index 6f78d2cd87..f0abb4150c 100644
--- a/src/mbgl/renderer/render_tile.hpp
+++ b/src/mbgl/renderer/render_tile.hpp
@@ -39,7 +39,6 @@ public:
     UnwrappedTileID id;
     mat4 matrix;
     mat4 nearClippedMatrix;
-    bool used = false;
     // Contains the tile ID string for painting debug information.
     std::unique_ptr<DebugBucket> debugBucket;
 
@@ -72,7 +71,6 @@ public:
                             const TransformState& state,
                             const bool inViewportPixelUnits) const;
 private:
-    friend class TilePyramid;
     Tile& tile;
 };
 
diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.cpp b/src/mbgl/renderer/sources/render_raster_dem_source.cpp
index 3ec544a845..96e4e1d2cc 100644
--- a/src/mbgl/renderer/sources/render_raster_dem_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_dem_source.cpp
@@ -52,6 +52,7 @@ void RenderRasterDEMSource::update(Immutable<style::Source::Impl> baseImpl_,
                        [&] (const OverscaledTileID& tileID) {
                            return std::make_unique<RasterDEMTile>(tileID, parameters, *tileset);
                        });
+    algorithm::updateTileMasks(tilePyramid.getRenderTiles());
 }
 
 void RenderRasterDEMSource::onTileChanged(Tile& tile){
@@ -121,11 +122,6 @@ void RenderRasterDEMSource::onTileChanged(Tile& tile){
     RenderTileSource::onTileChanged(tile);
 }
 
-void RenderRasterDEMSource::prepare(const SourcePrepareParameters& parameters) {
-    algorithm::updateTileMasks(tilePyramid.getRenderTiles());
-    RenderTileSource::prepare(parameters);
-}
-
 std::unordered_map<std::string, std::vector<Feature>>
 RenderRasterDEMSource::queryRenderedFeatures(const ScreenLineString&,
                                           const TransformState&,
diff --git a/src/mbgl/renderer/sources/render_raster_dem_source.hpp b/src/mbgl/renderer/sources/render_raster_dem_source.hpp
index dcec53e04a..d1e7f03e10 100644
--- a/src/mbgl/renderer/sources/render_raster_dem_source.hpp
+++ b/src/mbgl/renderer/sources/render_raster_dem_source.hpp
@@ -16,8 +16,6 @@ public:
                 bool needsRelayout,
                 const TileParameters&) final;
 
-    void prepare(const SourcePrepareParameters&) override;
-
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
                           const TransformState& transformState,
diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp
index 588009faa8..8b460de3f8 100644
--- a/src/mbgl/renderer/sources/render_raster_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_source.cpp
@@ -50,10 +50,10 @@ void RenderRasterSource::update(Immutable<style::Source::Impl> baseImpl_,
                        [&] (const OverscaledTileID& tileID) {
                            return std::make_unique<RasterTile>(tileID, parameters, *tileset);
                        });
+    algorithm::updateTileMasks(tilePyramid.getRenderTiles());
 }
 
 void RenderRasterSource::prepare(const SourcePrepareParameters& parameters) {
-    algorithm::updateTileMasks(tilePyramid.getRenderTiles());
     RenderTileSource::prepare(parameters);
 }
 
diff --git a/src/mbgl/renderer/sources/render_tile_source.cpp b/src/mbgl/renderer/sources/render_tile_source.cpp
index a906945e4f..b1fa824e68 100644
--- a/src/mbgl/renderer/sources/render_tile_source.cpp
+++ b/src/mbgl/renderer/sources/render_tile_source.cpp
@@ -1,4 +1,6 @@
 #include <mbgl/renderer/sources/render_tile_source.hpp>
+
+#include <mbgl/renderer/buckets/debug_bucket.hpp>
 #include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/renderer/paint_parameters.hpp>
 #include <mbgl/tile/vector_tile.hpp>
@@ -19,15 +21,23 @@ bool RenderTileSource::isLoaded() const {
 }
 
 void RenderTileSource::upload(gfx::UploadPass& parameters) {
-    tilePyramid.upload(parameters);
+    for (auto& tile : renderTiles) {
+        tile.upload(parameters);
+    }
 }
 
 void RenderTileSource::prepare(const SourcePrepareParameters& parameters) {
-    tilePyramid.prepare(parameters);
+    renderTiles.clear();
+    for (auto& entry : tilePyramid.getRenderTiles()) {
+        renderTiles.emplace_back(entry.first, entry.second);
+        renderTiles.back().prepare(parameters);
+    }
 }
 
 void RenderTileSource::finishRender(PaintParameters& parameters) {
-    tilePyramid.finishRender(parameters);
+    for (auto& tile : renderTiles) {
+        tile.finishRender(parameters);
+    }
 }
 
 void RenderTileSource::updateFadingTiles() {
@@ -39,7 +49,7 @@ bool RenderTileSource::hasFadingTiles() const {
 }
 
 std::vector<std::reference_wrapper<RenderTile>> RenderTileSource::getRenderTiles() {
-    return tilePyramid.getRenderTiles();
+    return { renderTiles.begin(), renderTiles.end() };
 }
 
 std::unordered_map<std::string, std::vector<Feature>>
diff --git a/src/mbgl/renderer/sources/render_tile_source.hpp b/src/mbgl/renderer/sources/render_tile_source.hpp
index c1a1f76242..a84c9fbbfe 100644
--- a/src/mbgl/renderer/sources/render_tile_source.hpp
+++ b/src/mbgl/renderer/sources/render_tile_source.hpp
@@ -39,6 +39,7 @@ public:
 
 protected:
     TilePyramid tilePyramid;
+    std::vector<RenderTile> renderTiles;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index 4f095ed97d..81da42b526 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -1,5 +1,4 @@
 #include <mbgl/renderer/tile_pyramid.hpp>
-#include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/renderer/paint_parameters.hpp>
 #include <mbgl/renderer/render_source.hpp>
 #include <mbgl/renderer/tile_parameters.hpp>
@@ -40,31 +39,9 @@ bool TilePyramid::isLoaded() const {
     return true;
 }
 
-void TilePyramid::upload(gfx::UploadPass& parameters) {
-    for (auto& tile : renderTiles) {
-        tile.upload(parameters);
-    }
-}
-
-void TilePyramid::prepare(const SourcePrepareParameters& parameters) {
-    for (auto& tile : renderTiles) {
-        tile.prepare(parameters);
-    }
-}
-
-void TilePyramid::finishRender(PaintParameters& parameters) {
-    for (auto& tile : renderTiles) {
-        tile.finishRender(parameters);
-    }
-}
-
-std::vector<std::reference_wrapper<RenderTile>> TilePyramid::getRenderTiles() {
-    return { renderTiles.begin(), renderTiles.end() };
-}
-
 Tile* TilePyramid::getTile(const OverscaledTileID& tileID){
-        auto it = tiles.find(tileID);
-        return it == tiles.end() ? cache.get(tileID) : it->second.get();
+    auto it = tiles.find(tileID);
+    return it == tiles.end() ? cache.get(tileID) : it->second.get();
 }
 
 void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& layers,
@@ -176,10 +153,7 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
         return tiles.emplace(tileID, std::move(tile)).first->second.get();
     };
 
-    std::map<UnwrappedTileID, Tile*> previouslyRenderedTiles;
-    for (auto& renderTile : renderTiles) {
-        previouslyRenderedTiles[renderTile.id] = &renderTile.tile;
-    }
+    auto previouslyRenderedTiles = std::move(renderTiles);
 
     auto renderTileFn = [&](const UnwrappedTileID& tileID, Tile& tile) {
         addRenderTile(tileID, tile);
@@ -198,7 +172,7 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
                                  idealTiles, zoomRange, tileZoom);
     
     for (auto previouslyRenderedTile : previouslyRenderedTiles) {
-        Tile& tile = *previouslyRenderedTile.second;
+        Tile& tile = previouslyRenderedTile.second;
         tile.markRenderedPreviously();
         if (tile.holdForFade()) {
             // Since it was rendered in the last frame, we know we have it
@@ -244,10 +218,11 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
 
     fadingTiles = false;
 
-    // Initialize render tiles fields and update the tile contained layer render data.
-    for (RenderTile& renderTile : renderTiles) {
-        Tile& tile = renderTile.tile;
+    // Initialize renderable tiles and update the contained layer render data.
+    for (auto& entry : renderTiles) {
+        Tile& tile = entry.second;
         assert(tile.isRenderable());
+        tile.usedByRenderedLayers = false;
 
         const bool holdForFade = tile.holdForFade();
         fadingTiles = (fadingTiles || holdForFade);
@@ -260,7 +235,7 @@ void TilePyramid::update(const std::vector<Immutable<style::LayerProperties>>& l
             bool layerRenderableInTile = tile.isComplete() ? tile.updateLayerProperties(layerProperties)
                                                            : static_cast<bool>(tile.getBucket(*layerProperties->baseImpl));
             if (layerRenderableInTile) {
-                renderTile.used = true;
+                tile.usedByRenderedLayers = true;
             }
         }
     }
@@ -290,6 +265,7 @@ void TilePyramid::handleWrapJump(float lng) {
 
     if (wrapDelta) {
         std::map<OverscaledTileID, std::unique_ptr<Tile>> newTiles;
+        std::map<UnwrappedTileID, std::reference_wrapper<Tile>> newRenderTiles;
         for (auto& tile : tiles) {
             auto newID = tile.second->id.unwrapTo(tile.second->id.wrap + wrapDelta);
             tile.second->id = newID;
@@ -297,9 +273,11 @@ void TilePyramid::handleWrapJump(float lng) {
         }
         tiles = std::move(newTiles);
 
-        for (auto& renderTile : renderTiles) {
-            renderTile.id = renderTile.id.unwrapTo(renderTile.id.wrap + wrapDelta);
+        for (auto& tile : renderTiles) {
+            UnwrappedTileID newID = tile.first.unwrapTo(tile.first.wrap + wrapDelta);
+            newRenderTiles.emplace(newID, tile.second);
         }
+        renderTiles = std::move(newRenderTiles);
     }
 }
 
@@ -322,26 +300,29 @@ std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRendered
     }
 
     mapbox::geometry::box<double> box = mapbox::geometry::envelope(queryGeometry);
-    // TODO: Find out why we need a special sorting algorithm here.
-    std::vector<std::reference_wrapper<const RenderTile>> sortedTiles{ renderTiles.begin(),
-                                                                       renderTiles.end() };
-    std::sort(sortedTiles.begin(), sortedTiles.end(), [](const RenderTile& a, const RenderTile& b) {
-        return std::tie(a.id.canonical.z, a.id.canonical.y, a.id.wrap, a.id.canonical.x) <
-            std::tie(b.id.canonical.z, b.id.canonical.y, b.id.wrap, b.id.canonical.x);
-    });
+
+    auto cmp = [](const UnwrappedTileID& a, const UnwrappedTileID& b) {
+        return std::tie(a.canonical.z, a.canonical.y, a.wrap, a.canonical.x) <
+            std::tie(b.canonical.z, b.canonical.y, b.wrap, b.canonical.x);
+    };
+
+    std::map<UnwrappedTileID, std::reference_wrapper<Tile>, decltype(cmp)> sortedTiles{renderTiles.begin(), renderTiles.end(), cmp};
 
     auto maxPitchScaleFactor = transformState.maxPitchScaleFactor();
 
-    for (const RenderTile& renderTile : sortedTiles) {
-        const float scale = std::pow(2, transformState.getZoom() - renderTile.id.canonical.z);
-        auto queryPadding = maxPitchScaleFactor * renderTile.tile.getQueryPadding(layers) * util::EXTENT / util::tileSize / scale;
+    for (const auto& entry : sortedTiles) {
+        const UnwrappedTileID& id = entry.first;
+        Tile& tile = entry.second;
+
+        const float scale = std::pow(2, transformState.getZoom() - id.canonical.z);
+        auto queryPadding = maxPitchScaleFactor * tile.getQueryPadding(layers) * util::EXTENT / util::tileSize / scale;
 
-        GeometryCoordinate tileSpaceBoundsMin = TileCoordinate::toGeometryCoordinate(renderTile.id, box.min);
+        GeometryCoordinate tileSpaceBoundsMin = TileCoordinate::toGeometryCoordinate(id, box.min);
         if (tileSpaceBoundsMin.x - queryPadding >= util::EXTENT || tileSpaceBoundsMin.y - queryPadding >= util::EXTENT) {
             continue;
         }
 
-        GeometryCoordinate tileSpaceBoundsMax = TileCoordinate::toGeometryCoordinate(renderTile.id, box.max);
+        GeometryCoordinate tileSpaceBoundsMax = TileCoordinate::toGeometryCoordinate(id, box.max);
         if (tileSpaceBoundsMax.x + queryPadding < 0 || tileSpaceBoundsMax.y + queryPadding < 0) {
             continue;
         }
@@ -349,15 +330,15 @@ std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRendered
         GeometryCoordinates tileSpaceQueryGeometry;
         tileSpaceQueryGeometry.reserve(queryGeometry.size());
         for (const auto& c : queryGeometry) {
-            tileSpaceQueryGeometry.push_back(TileCoordinate::toGeometryCoordinate(renderTile.id, c));
+            tileSpaceQueryGeometry.push_back(TileCoordinate::toGeometryCoordinate(id, c));
         }
 
-        renderTile.tile.queryRenderedFeatures(result,
-                                              tileSpaceQueryGeometry,
-                                              transformState,
-                                              layers,
-                                              options,
-                                              projMatrix);
+        tile.queryRenderedFeatures(result,
+                                   tileSpaceQueryGeometry,
+                                   transformState,
+                                   layers,
+                                   options,
+                                   projMatrix);
     }
 
     return result;
@@ -399,14 +380,12 @@ void TilePyramid::clearAll() {
 
 void TilePyramid::addRenderTile(const UnwrappedTileID& tileID, Tile& tile) {
     assert(tile.isRenderable());
-    auto it = std::lower_bound(renderTiles.begin(), renderTiles.end(), tileID,
-        [](const RenderTile& a, const UnwrappedTileID& id) { return a.id < id; });
-    renderTiles.emplace(it, tileID, tile);
+    renderTiles.emplace(tileID, tile);
 }
 
 void TilePyramid::updateFadingTiles() {
-    for (auto& renderTile : renderTiles) {
-        Tile& tile = renderTile.tile;
+    for (auto& entry : renderTiles) {
+        Tile& tile = entry.second;
         if (tile.holdForFade()) {
             tile.performedFadePlacement();
         }
diff --git a/src/mbgl/renderer/tile_pyramid.hpp b/src/mbgl/renderer/tile_pyramid.hpp
index 5f5492ede4..2c2c43c347 100644
--- a/src/mbgl/renderer/tile_pyramid.hpp
+++ b/src/mbgl/renderer/tile_pyramid.hpp
@@ -20,7 +20,6 @@ namespace mbgl {
 
 class PaintParameters;
 class TransformState;
-class RenderTile;
 class RenderLayer;
 class RenderedQueryOptions;
 class SourceQueryOptions;
@@ -44,11 +43,7 @@ public:
                 optional<LatLngBounds> bounds,
                 std::function<std::unique_ptr<Tile> (const OverscaledTileID&)> createTile);
 
-    void upload(gfx::UploadPass&);
-    void prepare(const SourcePrepareParameters&);
-    void finishRender(PaintParameters&);
-
-    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles();
+    const std::map<UnwrappedTileID, std::reference_wrapper<Tile>>& getRenderTiles() const { return renderTiles; }
     Tile* getTile(const OverscaledTileID&);
 
     void handleWrapJump(float lng);
@@ -80,8 +75,7 @@ private:
     std::map<OverscaledTileID, std::unique_ptr<Tile>> tiles;
     TileCache cache;
 
-    std::list<RenderTile> renderTiles;
-
+    std::map<UnwrappedTileID, std::reference_wrapper<Tile>> renderTiles; // Sorted by tile id.
     TileObserver* observer = nullptr;
 
     float prevLng = 0;
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index 1bb38f5c96..95ee0bc37e 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -131,6 +131,9 @@ public:
     OverscaledTileID id;
     optional<Timestamp> modified;
     optional<Timestamp> expires;
+    // Indicates whether this tile is used for the currently visible layers on the map.
+    // Re-initialized at every source update.
+    bool usedByRenderedLayers = false;
 
 protected:
     bool triedOptional = false;
@@ -138,6 +141,7 @@ protected:
     bool pending = false;
     bool loaded = false;
 
+
     TileObserver* observer = nullptr;
 };
 
-- 
cgit v1.2.1