[core] Improved label pitch-scaling: approximate collision box shapes based on tile distance from camera.

11 files changed, 82 insertions, 25 deletions

diff --git a/src/mbgl/map/transform_state.cpp b/src/mbgl/map/transform_state.cpp
index f052e30a6b..4606e3eece 100644
--- a/src/mbgl/map/transform_state.cpp
+++ b/src/mbgl/map/transform_state.cpp
@@ -385,4 +385,16 @@ void TransformState::setScalePoint(const double newScale, const ScreenCoordinate
     Cc = Projection::worldSize(scale) / util::M2PI;
 }
 
+float TransformState::getCameraToTileDistance(const UnwrappedTileID& tileID) const {
+    mat4 projectionMatrix;
+    getProjMatrix(projectionMatrix);
+    mat4 tileProjectionMatrix;
+    matrixFor(tileProjectionMatrix, tileID);
+    matrix::multiply(tileProjectionMatrix, projectionMatrix, tileProjectionMatrix);
+    vec4 tileCenter = {{util::tileSize / 2, util::tileSize / 2, 0, 1}};
+    vec4 projectedCenter;
+    matrix::transformMat4(projectedCenter, tileCenter, tileProjectionMatrix);
+    return projectedCenter[3];
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/map/transform_state.hpp b/src/mbgl/map/transform_state.hpp
index e6464aeacc..f35f570549 100644
--- a/src/mbgl/map/transform_state.hpp
+++ b/src/mbgl/map/transform_state.hpp
@@ -86,6 +86,8 @@ public:
         return !size.isEmpty() && (scale >= min_scale && scale <= max_scale);
     }
 
+    float getCameraToTileDistance(const UnwrappedTileID&) const;
+
 private:
     bool rotatedNorth() const;
     void constrain(double& scale, double& x, double& y) const;
diff --git a/src/mbgl/programs/symbol_program.cpp b/src/mbgl/programs/symbol_program.cpp
index cdbd6b9713..789eed0dd8 100644
--- a/src/mbgl/programs/symbol_program.cpp
+++ b/src/mbgl/programs/symbol_program.cpp
@@ -2,6 +2,7 @@
 #include <mbgl/renderer/render_tile.hpp>
 #include <mbgl/map/transform_state.hpp>
 #include <mbgl/style/layers/symbol_layer_impl.hpp>
+#include <mbgl/tile/tile.hpp>
 #include <mbgl/util/enum.hpp>
 #include <mbgl/math/clamp.hpp>
 
@@ -57,6 +58,7 @@ Values makeValues(const bool isText,
         uniforms::u_texture::Value{ 0 },
         uniforms::u_fadetexture::Value{ 1 },
         uniforms::u_is_text::Value{ isText },
+        uniforms::u_collision_y_stretch::Value{ tile.tile.yStretch() },
         std::forward<Args>(args)...
     };
 }
diff --git a/src/mbgl/programs/symbol_program.hpp b/src/mbgl/programs/symbol_program.hpp
index c11e0b5ca1..d1a6b4b994 100644
--- a/src/mbgl/programs/symbol_program.hpp
+++ b/src/mbgl/programs/symbol_program.hpp
@@ -42,6 +42,7 @@ MBGL_DEFINE_UNIFORM_SCALAR(bool, u_is_size_feature_constant);
 MBGL_DEFINE_UNIFORM_SCALAR(float, u_size_t);
 MBGL_DEFINE_UNIFORM_SCALAR(float, u_size);
 MBGL_DEFINE_UNIFORM_SCALAR(float, u_layout_size);
+MBGL_DEFINE_UNIFORM_SCALAR(float, u_collision_y_stretch);
 } // namespace uniforms
 
 struct SymbolLayoutAttributes : gl::Attributes<
@@ -389,7 +390,8 @@ class SymbolIconProgram : public SymbolProgram<
         uniforms::u_rotate_with_map,
         uniforms::u_texture,
         uniforms::u_fadetexture,
-        uniforms::u_is_text>,
+        uniforms::u_is_text,
+        uniforms::u_collision_y_stretch>,
     style::IconPaintProperties>
 {
 public:
@@ -422,6 +424,7 @@ class SymbolSDFProgram : public SymbolProgram<
         uniforms::u_texture,
         uniforms::u_fadetexture,
         uniforms::u_is_text,
+        uniforms::u_collision_y_stretch,
         uniforms::u_gamma_scale,
         uniforms::u_pitch,
         uniforms::u_bearing,
@@ -443,6 +446,7 @@ public:
             uniforms::u_texture,
             uniforms::u_fadetexture,
             uniforms::u_is_text,
+            uniforms::u_collision_y_stretch,
             uniforms::u_gamma_scale,
             uniforms::u_pitch,
             uniforms::u_bearing,
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index a8e6c128ba..57e7f6d375 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -175,11 +175,16 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
 
     removeStaleTiles(retain);
 
-    const PlacementConfig config { parameters.transformState.getAngle(),
-                                   parameters.transformState.getPitch(),
-                                   parameters.debugOptions & MapDebugOptions::Collision };
-
     for (auto& pair : tiles) {
+        // TODO: Calculating yStretch based on tile distance means we can no longer use the same collision tile for two wrapped
+        // copies of the same data tile. For now the assumption that we're always at "wrap = 0" means collision detection is broken
+        // for wrapped tiles.
+        const PlacementConfig config { parameters.transformState.getAngle(),
+                                       parameters.transformState.getPitch(),
+                                       parameters.transformState.getCameraToCenterDistance(),
+                                       parameters.transformState.getCameraToTileDistance(pair.first.unwrapTo(0)),
+                                       parameters.debugOptions & MapDebugOptions::Collision };
+        
         pair.second->setPlacementConfig(config);
     }
 }
diff --git a/src/mbgl/text/collision_tile.cpp b/src/mbgl/text/collision_tile.cpp
index 368750c89f..520f66ead8 100644
--- a/src/mbgl/text/collision_tile.cpp
+++ b/src/mbgl/text/collision_tile.cpp
@@ -20,12 +20,17 @@ CollisionTile::CollisionTile(PlacementConfig config_) : config(std::move(config_
     rotationMatrix = { { angle_cos, -angle_sin, angle_sin, angle_cos } };
     reverseRotationMatrix = { { angle_cos, angle_sin, -angle_sin, angle_cos } };
 
-    // Stretch boxes in y direction to account for the map tilt.
-    const float _yStretch = 1.0f / std::cos(config.pitch);
-
-    // The amount the map is squished depends on the y position.
-    // Sort of account for this by making all boxes a bit bigger.
-    yStretch = std::pow(_yStretch, 1.3f);
+    perspectiveRatio = 1.0f + 0.5f * ((config.cameraToTileDistance / config.cameraToCenterDistance) - 1.0f);
+    minScale /= perspectiveRatio;
+    maxScale /= perspectiveRatio;
+
+    // We can only approximate here based on the y position of the tile
+    // The shaders calculate a more accurate "incidence_stretch"
+    // at render time to calculate an effective scale for collision
+    // purposes, but we still want to use the yStretch approximation
+    // here because we can't adjust the aspect ratio of the collision
+    // boxes at render time.
+    yStretch = util::max(1.0f, config.cameraToTileDistance / (config.cameraToCenterDistance * std::cos(config.pitch)));
 }
 
 
@@ -157,13 +162,21 @@ void CollisionTile::insertFeature(CollisionFeature& feature, float minPlacementS
 Box CollisionTile::getTreeBox(const Point<float>& anchor, const CollisionBox& box, const float scale) {
     assert(box.x1 <= box.x2 && box.y1 <= box.y2);
     return Box{
+        // When the 'perspectiveRatio' is high, we're effectively underzooming
+        // the tile because it's in the distance.
+        // In order to detect collisions that only happen while underzoomed,
+        // we have to query a larger portion of the grid.
+        // This extra work is offset by having a lower 'maxScale' bound
+        // Note that this adjustment ONLY affects the bounding boxes
+        // in the grid. It doesn't affect the boxes used for the
+        // minPlacementScale calculations.
         CollisionPoint{
-            anchor.x + box.x1 / scale,
-            anchor.y + box.y1 / scale * yStretch
+            anchor.x + box.x1 / scale * perspectiveRatio,
+            anchor.y + box.y1 / scale * yStretch * perspectiveRatio,
         },
         CollisionPoint{
-            anchor.x + box.x2 / scale,
-            anchor.y + box.y2 / scale * yStretch
+            anchor.x + box.x2 / scale * perspectiveRatio,
+            anchor.y + box.y2 / scale * yStretch * perspectiveRatio
         }
     };
 }
@@ -190,8 +203,14 @@ std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const Geometr
         return seenFeatures.find(feature.index) == seenFeatures.end();
     };
 
+    // "perspectiveRatio" is a tile-based approximation of how much larger symbols will
+    // be in the distance. It won't line up exactly with the actually rendered symbols
+    // Being exact would require running the collision detection logic in symbol_sdf.vertex
+    // in the CPU
+    const float perspectiveScale = scale / perspectiveRatio;
+
     // Account for the rounding done when updating symbol shader variables.
-    const float roundedScale = std::pow(2.0f, std::ceil(util::log2(scale) * 10.0f) / 10.0f);
+    const float roundedScale = std::pow(2.0f, std::ceil(util::log2(perspectiveScale) * 10.0f) / 10.0f);
 
     // Check if feature is rendered (collision free) at current scale.
     auto visibleAtScale = [&] (const CollisionTreeBox& treeBox) -> bool {
@@ -203,10 +222,11 @@ std::vector<IndexedSubfeature> CollisionTile::queryRenderedSymbols(const Geometr
     auto intersectsAtScale = [&] (const CollisionTreeBox& treeBox) -> bool {
         const CollisionBox& collisionBox = std::get<1>(treeBox);
         const auto anchor = util::matrixMultiply(rotationMatrix, collisionBox.anchor);
-        const int16_t x1 = anchor.x + collisionBox.x1 / scale;
-        const int16_t y1 = anchor.y + collisionBox.y1 / scale * yStretch;
-        const int16_t x2 = anchor.x + collisionBox.x2 / scale;
-        const int16_t y2 = anchor.y + collisionBox.y2 / scale * yStretch;
+
+        const int16_t x1 = anchor.x + (collisionBox.x1 / perspectiveScale);
+        const int16_t y1 = anchor.y + (collisionBox.y1 / perspectiveScale) * yStretch;
+        const int16_t x2 = anchor.x + (collisionBox.x2 / perspectiveScale);
+        const int16_t y2 = anchor.y + (collisionBox.y2 / perspectiveScale) * yStretch;
         auto bbox = GeometryCoordinates {
             { x1, y1 }, { x2, y1 }, { x2, y2 }, { x1, y2 }
         };
diff --git a/src/mbgl/text/collision_tile.hpp b/src/mbgl/text/collision_tile.hpp
index 59fd1a3927..dbff6a007b 100644
--- a/src/mbgl/text/collision_tile.hpp
+++ b/src/mbgl/text/collision_tile.hpp
@@ -49,8 +49,8 @@ public:
 
     const PlacementConfig config;
 
-    const float minScale = 0.5f;
-    const float maxScale = 2.0f;
+    float minScale = 0.5f;
+    float maxScale = 2.0f;
     float yStretch;
 
     std::array<float, 4> rotationMatrix;
@@ -64,6 +64,8 @@ private:
 
     Tree tree;
     Tree ignoredTree;
+    
+    float perspectiveRatio;
 };
 
 } // namespace mbgl
diff --git a/src/mbgl/text/placement_config.hpp b/src/mbgl/text/placement_config.hpp
index 7e61cabc24..c5c013055a 100644
--- a/src/mbgl/text/placement_config.hpp
+++ b/src/mbgl/text/placement_config.hpp
@@ -4,12 +4,12 @@ namespace mbgl {
 
 class PlacementConfig {
 public:
-    PlacementConfig(float angle_ = 0, float pitch_ = 0, bool debug_ = false)
-        : angle(angle_), pitch(pitch_), debug(debug_) {
+    PlacementConfig(float angle_ = 0, float pitch_ = 0, float cameraToCenterDistance_ = 0, float cameraToTileDistance_ = 0, bool debug_ = false)
+        : angle(angle_), pitch(pitch_), cameraToCenterDistance(cameraToCenterDistance_), cameraToTileDistance(cameraToTileDistance_), debug(debug_) {
     }
 
     bool operator==(const PlacementConfig& rhs) const {
-        return angle == rhs.angle && pitch == rhs.pitch && debug == rhs.debug;
+        return angle == rhs.angle && pitch == rhs.pitch && cameraToCenterDistance == rhs.cameraToCenterDistance && cameraToTileDistance == rhs.cameraToTileDistance && debug == rhs.debug;
     }
 
     bool operator!=(const PlacementConfig& rhs) const {
@@ -19,6 +19,8 @@ public:
 public:
     float angle;
     float pitch;
+    float cameraToCenterDistance;
+    float cameraToTileDistance;
     bool debug;
 };
 
diff --git a/src/mbgl/tile/geometry_tile.cpp b/src/mbgl/tile/geometry_tile.cpp
index 4ab11d79fe..ad5c2edd4c 100644
--- a/src/mbgl/tile/geometry_tile.cpp
+++ b/src/mbgl/tile/geometry_tile.cpp
@@ -264,4 +264,8 @@ void GeometryTile::querySourceFeatures(
     }
 }
 
+float GeometryTile::yStretch() const {
+    return collisionTile->yStretch;
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/tile/geometry_tile.hpp b/src/mbgl/tile/geometry_tile.hpp
index 77202d20b6..3e2efe1093 100644
--- a/src/mbgl/tile/geometry_tile.hpp
+++ b/src/mbgl/tile/geometry_tile.hpp
@@ -86,6 +86,8 @@ public:
 
     void onError(std::exception_ptr);
     
+    float yStretch() const override;
+    
 protected:
     const GeometryTileData* getData() {
         return data.get();
diff --git a/src/mbgl/tile/tile.hpp b/src/mbgl/tile/tile.hpp
index a925d88af3..1898f76849 100644
--- a/src/mbgl/tile/tile.hpp
+++ b/src/mbgl/tile/tile.hpp
@@ -105,6 +105,8 @@ 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;