[core] Switch from background to foreground placement

 - Background placement code now just generates static symbol buffers
 - Don't render GeometryTiles until their symbols are loaded. This is necessary for the CrossTileSymbolIndex to successfully prevent flicker.
 - SymbolInstances are transferred to SymbolBucket for use on foreground during collision detection
 - Symbols are sorted on foreground by sorting their index buffer but leaving vertex buffers intact (only works within one segment)
 - Vertical glyphs are generated at same time as horizontal glyphs. `reprojectLineLabels` chooses which one to use at render time and hides the other.
 - Icons are now always represented with a single collision box, even if they're placed along a line (this means their rotation alignment may be wrong, but the approach of representing them with multiple collision boxes wasn't very accurate either).
 - Generate vertices for new debug collision boxes and collision circles
 - Only add symbols within tile boundaries (reduces work, avoids double-draw)
 - Update symbol_projection.cpp to support line label projection calls from CollisionIndex.

5 files changed, 64 insertions, 70 deletions

diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index 8c018ce3aa..576c23b682 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -15,7 +15,6 @@
 #include <mbgl/renderer/image_atlas.hpp>
 #include <mbgl/storage/file_source.hpp>
 #include <mbgl/geometry/feature_index.hpp>
-#include <mbgl/text/collision_tile.hpp>
 #include <mbgl/map/transform_state.hpp>
 #include <mbgl/style/filter_evaluator.hpp>
 #include <mbgl/util/logging.hpp>
@@ -33,7 +32,7 @@ using namespace style;
 
    GeometryTile's 'correlationID' is used for ensuring the tile will be flagged
    as non-pending only when the placement coming from the last operation (as in
-   'setData', 'setLayers',  'setPlacementConfig') occurs. This is important for
+   'setData', 'setLayers',  'setShowCollisionBoxes') occurs. This is important for
    still mode rendering as we want to render only when all layout and placement
    operations are completed.
 
@@ -52,13 +51,15 @@ GeometryTile::GeometryTile(const OverscaledTileID& id_,
       worker(parameters.workerScheduler,
              ActorRef<GeometryTile>(*this, mailbox),
              id_,
+             sourceID,
              obsolete,
              parameters.mode,
-             parameters.pixelRatio),
+             parameters.pixelRatio,
+             parameters.debugOptions & MapDebugOptions::Collision),
       glyphManager(parameters.glyphManager),
       imageManager(parameters.imageManager),
-      lastYStretch(1.0f),
-      mode(parameters.mode) {
+      mode(parameters.mode),
+      showCollisionBoxes(parameters.debugOptions & MapDebugOptions::Collision) {
 }
 
 GeometryTile::~GeometryTile() {
@@ -89,25 +90,6 @@ void GeometryTile::setData(std::unique_ptr<const GeometryTileData> data_) {
     worker.invoke(&GeometryTileWorker::setData, std::move(data_), correlationID);
 }
 
-void GeometryTile::setPlacementConfig(const PlacementConfig& desiredConfig) {
-    if (requestedConfig == desiredConfig) {
-        return;
-    }
-
-    // Mark the tile as pending again if it was complete before to prevent signaling a complete
-    // state despite pending parse operations.
-    pending = true;
-
-    ++correlationID;
-    requestedConfig = desiredConfig;
-    invokePlacement();
-}
-
-void GeometryTile::invokePlacement() {
-    if (requestedConfig) {
-        worker.invoke(&GeometryTileWorker::setPlacementConfig, *requestedConfig, correlationID);
-    }
-}
 
 void GeometryTile::setLayers(const std::vector<Immutable<Layer::Impl>>& layers) {
     // Mark the tile as pending again if it was complete before to prevent signaling a complete
@@ -134,14 +116,22 @@ void GeometryTile::setLayers(const std::vector<Immutable<Layer::Impl>>& layers)
     worker.invoke(&GeometryTileWorker::setLayers, std::move(impls), correlationID);
 }
 
+void GeometryTile::setShowCollisionBoxes(const bool showCollisionBoxes_) {
+    if (showCollisionBoxes != showCollisionBoxes_) {
+       showCollisionBoxes = showCollisionBoxes_;
+       ++correlationID;
+        worker.invoke(&GeometryTileWorker::setShowCollisionBoxes, showCollisionBoxes, correlationID);
+    }
+}
+
 void GeometryTile::onLayout(LayoutResult result, const uint64_t resultCorrelationID) {
-    loaded = true;
-    renderable = true;
+    // Don't mark ourselves loaded or renderable until the first successful placement
+    // TODO: Ideally we'd render this tile without symbols as long as this tile wasn't
+    //  replacing a tile at a different zoom that _did_ have symbols.
     (void)resultCorrelationID;
     nonSymbolBuckets = std::move(result.nonSymbolBuckets);
     featureIndex = std::move(result.featureIndex);
     data = std::move(result.tileData);
-    collisionTile.reset();
     observer->onTileChanged(*this);
 }
 
@@ -152,16 +142,13 @@ void GeometryTile::onPlacement(PlacementResult result, const uint64_t resultCorr
         pending = false;
     }
     symbolBuckets = std::move(result.symbolBuckets);
-    collisionTile = std::move(result.collisionTile);
     if (result.glyphAtlasImage) {
         glyphAtlasImage = std::move(*result.glyphAtlasImage);
     }
     if (result.iconAtlasImage) {
         iconAtlasImage = std::move(*result.iconAtlasImage);
     }
-    if (collisionTile.get()) {
-        lastYStretch = collisionTile->yStretch;
-    }
+
     observer->onTileChanged(*this);
 }
 
@@ -231,7 +218,8 @@ void GeometryTile::queryRenderedFeatures(
     const GeometryCoordinates& queryGeometry,
     const TransformState& transformState,
     const std::vector<const RenderLayer*>& layers,
-    const RenderedQueryOptions& options) {
+    const RenderedQueryOptions& options,
+    const CollisionIndex& collisionIndex) {
 
     if (!featureIndex || !data) return;
 
@@ -251,9 +239,10 @@ void GeometryTile::queryRenderedFeatures(
                         std::pow(2, transformState.getZoom() - id.overscaledZ),
                         options,
                         *data,
-                        id.canonical,
+                        id.toUnwrapped(),
+                        sourceID,
                         layers,
-                        collisionTile.get(),
+                        collisionIndex,
                         additionalRadius);
 }
 
@@ -293,11 +282,16 @@ void GeometryTile::querySourceFeatures(
     }
 }
 
-float GeometryTile::yStretch() const {
-    // collisionTile gets reset in onLayout but we don't clear the symbolBuckets
-    // until a new placement result comes along, so keep the yStretch value in
-    // case we need to render them.
-    return lastYStretch;
+void GeometryTile::resetCrossTileIDs() {
+    for (auto& bucket : symbolBuckets) {
+        auto symbolBucket = dynamic_cast<SymbolBucket*>(bucket.second.get());
+        if (symbolBucket && symbolBucket->bucketInstanceId) {
+            symbolBucket->bucketInstanceId = 0;
+            for (auto& symbolInstance : symbolBucket->symbolInstances) {
+                symbolInstance.crossTileID = 0;
+            }
+        }
+    }
 }
 
 } // namespace mbgl
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index a478aad504..3f4b36984b 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -4,12 +4,11 @@
 #include <mbgl/tile/geometry_tile_worker.hpp>
 #include <mbgl/renderer/image_manager.hpp>
 #include <mbgl/text/glyph_manager.hpp>
-#include <mbgl/text/placement_config.hpp>
-#include <mbgl/text/collision_tile.hpp>
 #include <mbgl/util/feature.hpp>
 #include <mbgl/util/throttler.hpp>
 #include <mbgl/actor/actor.hpp>
 #include <mbgl/geometry/feature_index.hpp>
+#include <mbgl/layout/symbol_layout.hpp>
 
 #include <atomic>
 #include <memory>
@@ -36,9 +35,9 @@ public:
     void setError(std::exception_ptr);
     void setData(std::unique_ptr<const GeometryTileData>);
 
-    void setPlacementConfig(const PlacementConfig&) override;
     void setLayers(const std::vector<Immutable<style::Layer::Impl>>&) override;
-    
+    void setShowCollisionBoxes(const bool showCollisionBoxes) override;
+
     void onGlyphsAvailable(GlyphMap) override;
     void onImagesAvailable(ImageMap, uint64_t imageCorrelationID) override;
     
@@ -56,7 +55,8 @@ public:
             const GeometryCoordinates& queryGeometry,
             const TransformState&,
             const std::vector<const RenderLayer*>& layers,
-            const RenderedQueryOptions& options) override;
+            const RenderedQueryOptions& options,
+            const CollisionIndex& collisionIndex) override;
 
     void querySourceFeatures(
         std::vector<Feature>& result,
@@ -82,16 +82,13 @@ public:
     class PlacementResult {
     public:
         std::unordered_map<std::string, std::shared_ptr<Bucket>> symbolBuckets;
-        std::unique_ptr<CollisionTile> collisionTile;
         optional<AlphaImage> glyphAtlasImage;
         optional<PremultipliedImage> iconAtlasImage;
 
         PlacementResult(std::unordered_map<std::string, std::shared_ptr<Bucket>> symbolBuckets_,
-                        std::unique_ptr<CollisionTile> collisionTile_,
                         optional<AlphaImage> glyphAtlasImage_,
                         optional<PremultipliedImage> iconAtlasImage_)
             : symbolBuckets(std::move(symbolBuckets_)),
-              collisionTile(std::move(collisionTile_)),
               glyphAtlasImage(std::move(glyphAtlasImage_)),
               iconAtlasImage(std::move(iconAtlasImage_)) {}
     };
@@ -99,7 +96,7 @@ public:
 
     void onError(std::exception_ptr, uint64_t correlationID);
     
-    float yStretch() const override;
+    void resetCrossTileIDs() override;
     
 protected:
     const GeometryTileData* getData() {
@@ -108,7 +105,6 @@ protected:
 
 private:
     void markObsolete();
-    void invokePlacement();
 
     const std::string sourceID;
 
@@ -122,7 +118,6 @@ private:
     ImageManager& imageManager;
 
     uint64_t correlationID = 0;
-    optional<PlacementConfig> requestedConfig;
 
     std::unordered_map<std::string, std::shared_ptr<Bucket>> nonSymbolBuckets;
     std::unique_ptr<FeatureIndex> featureIndex;
@@ -132,10 +127,11 @@ private:
     optional<PremultipliedImage> iconAtlasImage;
 
     std::unordered_map<std::string, std::shared_ptr<Bucket>> symbolBuckets;
-    std::unique_ptr<CollisionTile> collisionTile;
+    std::unordered_map<std::string, std::unique_ptr<SymbolLayout>> symbolLayouts;
 
-    float lastYStretch;
     const MapMode mode;
+    
+    bool showCollisionBoxes;
 
 public:
     optional<gl::Texture> glyphAtlasTexture;
diff --git a/src/mbgl/tile/geometry_tile_worker.cpp b/src/mbgl/tile/geometry_tile_worker.cpp
index 50429420c3..969b137c1f 100644
--- a/src/mbgl/tile/geometry_tile_worker.cpp
+++ b/src/mbgl/tile/geometry_tile_worker.cpp
@@ -1,7 +1,6 @@
 #include <mbgl/tile/geometry_tile_worker.hpp>
 #include <mbgl/tile/geometry_tile_data.hpp>
 #include <mbgl/tile/geometry_tile.hpp>
-#include <mbgl/text/collision_tile.hpp>
 #include <mbgl/layout/symbol_layout.hpp>
 #include <mbgl/renderer/bucket_parameters.hpp>
 #include <mbgl/renderer/group_by_layout.hpp>
@@ -24,15 +23,19 @@ using namespace style;
 GeometryTileWorker::GeometryTileWorker(ActorRef<GeometryTileWorker> self_,
                                        ActorRef<GeometryTile> parent_,
                                        OverscaledTileID id_,
+                                       const std::string& sourceID_,
                                        const std::atomic<bool>& obsolete_,
                                        const MapMode mode_,
-                                       const float pixelRatio_)
+                                       const float pixelRatio_,
+                                       const bool showCollisionBoxes_)
     : self(std::move(self_)),
       parent(std::move(parent_)),
       id(std::move(id_)),
+      sourceID(sourceID_),
       obsolete(obsolete_),
       mode(mode_),
-      pixelRatio(pixelRatio_) {
+      pixelRatio(pixelRatio_),
+      showCollisionBoxes(showCollisionBoxes_) {
 }
 
 GeometryTileWorker::~GeometryTileWorker() = default;
@@ -116,9 +119,9 @@ void GeometryTileWorker::setLayers(std::vector<Immutable<Layer::Impl>> layers_,
     }
 }
 
-void GeometryTileWorker::setPlacementConfig(PlacementConfig placementConfig_, uint64_t correlationID_) {
+void GeometryTileWorker::setShowCollisionBoxes(bool showCollisionBoxes_, uint64_t correlationID_) {
     try {
-        placementConfig = std::move(placementConfig_);
+        showCollisionBoxes = showCollisionBoxes_;
         correlationID = correlationID_;
 
         switch (state) {
@@ -372,7 +375,7 @@ bool GeometryTileWorker::hasPendingSymbolDependencies() const {
 }
 
 void GeometryTileWorker::attemptPlacement() {
-    if (!data || !layers || !placementConfig || hasPendingSymbolDependencies()) {
+    if (!data || !layers || hasPendingSymbolDependencies()) {
         return;
     }
     
@@ -392,13 +395,13 @@ void GeometryTileWorker::attemptPlacement() {
             }
 
             symbolLayout->prepare(glyphMap, glyphAtlas.positions,
-                                  imageMap, imageAtlas.positions);
+                                  imageMap, imageAtlas.positions,
+                                  id, sourceID);
         }
 
         symbolLayoutsNeedPreparation = false;
     }
 
-    auto collisionTile = std::make_unique<CollisionTile>(*placementConfig);
     std::unordered_map<std::string, std::shared_ptr<Bucket>> buckets;
 
     for (auto& symbolLayout : symbolLayouts) {
@@ -410,7 +413,7 @@ void GeometryTileWorker::attemptPlacement() {
             continue;
         }
 
-        std::shared_ptr<Bucket> bucket = symbolLayout->place(*collisionTile);
+        std::shared_ptr<Bucket> bucket = symbolLayout->place(showCollisionBoxes);
         for (const auto& pair : symbolLayout->layerPaintProperties) {
             buckets.emplace(pair.first, bucket);
         }
@@ -418,7 +421,6 @@ void GeometryTileWorker::attemptPlacement() {
 
     parent.invoke(&GeometryTile::onPlacement, GeometryTile::PlacementResult {
         std::move(buckets),
-        std::move(collisionTile),
         std::move(glyphAtlasImage),
         std::move(iconAtlasImage),
     }, correlationID);
diff --git a/src/mbgl/tile/geometry_tile_worker.hpp b/src/mbgl/tile/geometry_tile_worker.hpp
index 1425daa7a1..cc86248cec 100644
--- a/src/mbgl/tile/geometry_tile_worker.hpp
+++ b/src/mbgl/tile/geometry_tile_worker.hpp
@@ -4,7 +4,6 @@
 #include <mbgl/tile/tile_id.hpp>
 #include <mbgl/style/image_impl.hpp>
 #include <mbgl/text/glyph.hpp>
-#include <mbgl/text/placement_config.hpp>
 #include <mbgl/actor/actor_ref.hpp>
 #include <mbgl/util/optional.hpp>
 #include <mbgl/util/immutable.hpp>
@@ -28,14 +27,16 @@ public:
     GeometryTileWorker(ActorRef<GeometryTileWorker> self,
                        ActorRef<GeometryTile> parent,
                        OverscaledTileID,
+                       const std::string&,
                        const std::atomic<bool>&,
                        const MapMode,
-                       const float pixelRatio);
+                       const float pixelRatio,
+                       const bool showCollisionBoxes_);
     ~GeometryTileWorker();
 
     void setLayers(std::vector<Immutable<style::Layer::Impl>>, uint64_t correlationID);
     void setData(std::unique_ptr<const GeometryTileData>, uint64_t correlationID);
-    void setPlacementConfig(PlacementConfig, uint64_t correlationID);
+    void setShowCollisionBoxes(bool showCollisionBoxes_, uint64_t correlationID_);
     
     void onGlyphsAvailable(GlyphMap glyphs);
     void onImagesAvailable(ImageMap images, uint64_t imageCorrelationID);
@@ -57,6 +58,7 @@ private:
     ActorRef<GeometryTile> parent;
 
     const OverscaledTileID id;
+    const std::string sourceID;
     const std::atomic<bool>& obsolete;
     const MapMode mode;
     const float pixelRatio;
@@ -75,7 +77,6 @@ private:
     // Outer optional indicates whether we've received it or not.
     optional<std::vector<Immutable<style::Layer::Impl>>> layers;
     optional<std::unique_ptr<const GeometryTileData>> data;
-    optional<PlacementConfig> placementConfig;
 
     bool symbolLayoutsNeedPreparation = false;
     std::vector<std::unique_ptr<SymbolLayout>> symbolLayouts;
@@ -83,6 +84,8 @@ private:
     ImageDependencies pendingImageDependencies;
     GlyphMap glyphMap;
     ImageMap imageMap;
+    
+    bool showCollisionBoxes;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index 8be7c4d862..65a497aaae 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -23,7 +23,6 @@ namespace mbgl {
 class DebugBucket;
 class TransformState;
 class TileObserver;
-class PlacementConfig;
 class RenderLayer;
 class RenderedQueryOptions;
 class SourceQueryOptions;
@@ -47,7 +46,7 @@ public:
     virtual void upload(gl::Context&) = 0;
     virtual Bucket* getBucket(const style::Layer::Impl&) const = 0;
 
-    virtual void setPlacementConfig(const PlacementConfig&) {}
+    virtual void setShowCollisionBoxes(const bool) {}
     virtual void setLayers(const std::vector<Immutable<style::Layer::Impl>>&) {}
     virtual void setMask(TileMask&&) {}
 
@@ -92,6 +91,8 @@ public:
     bool isComplete() const {
         return loaded && !pending;
     }
+    
+    virtual void resetCrossTileIDs() {};
 
     void dumpDebugLogs() const;
 
@@ -101,8 +102,6 @@ public:
 
     // Contains the tile ID string for painting debug information.
     std::unique_ptr<DebugBucket> debugBucket;
-    
-    virtual float yStretch() const { return 1.0f; }
 
 protected:
     bool triedOptional = false;