[core] Add `symbol-placement: line-center`

- Remove unused/vestigial 'maxCameraDistance'
- Create a single collision circle for line labels that are less than half the width of a collision circle

11 files changed, 114 insertions, 47 deletions

diff --git a/include/mbgl/style/types.hpp b/include/mbgl/style/types.hpp
index 44c11186b8..805cff118c 100644
--- a/include/mbgl/style/types.hpp
+++ b/include/mbgl/style/types.hpp
@@ -63,9 +63,10 @@ enum class CirclePitchScaleType : bool {
     Viewport,
 };
 
-enum class SymbolPlacementType : bool {
+enum class SymbolPlacementType : uint8_t {
     Point,
     Line,
+    LineCenter
 };
 
 enum class AlignmentType : uint8_t {
diff --git a/src/mbgl/layout/symbol_layout.cpp b/src/mbgl/layout/symbol_layout.cpp
index d4df58b67c..41469f293d 100644
--- a/src/mbgl/layout/symbol_layout.cpp
+++ b/src/mbgl/layout/symbol_layout.cpp
@@ -57,7 +57,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
     layout = leader.layout.evaluate(PropertyEvaluationParameters(zoom));
 
     if (layout.get<IconRotationAlignment>() == AlignmentType::Auto) {
-        if (layout.get<SymbolPlacement>() == SymbolPlacementType::Line) {
+        if (layout.get<SymbolPlacement>() != SymbolPlacementType::Point) {
             layout.get<IconRotationAlignment>() = AlignmentType::Map;
         } else {
             layout.get<IconRotationAlignment>() = AlignmentType::Viewport;
@@ -65,7 +65,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
     }
 
     if (layout.get<TextRotationAlignment>() == AlignmentType::Auto) {
-        if (layout.get<SymbolPlacement>() == SymbolPlacementType::Line) {
+        if (layout.get<SymbolPlacement>() != SymbolPlacementType::Point) {
             layout.get<TextRotationAlignment>() = AlignmentType::Map;
         } else {
             layout.get<TextRotationAlignment>() = AlignmentType::Viewport;
@@ -117,7 +117,7 @@ SymbolLayout::SymbolLayout(const BucketParameters& parameters,
 
             ft.text = applyArabicShaping(util::utf8_to_utf16::convert(u8string));
             const bool canVerticalizeText = layout.get<TextRotationAlignment>() == AlignmentType::Map
-                                         && layout.get<SymbolPlacement>() == SymbolPlacementType::Line
+                                         && layout.get<SymbolPlacement>() != SymbolPlacementType::Point
                                          && util::i18n::allowsVerticalWritingMode(*ft.text);
 
             FontStack fontStack = layout.evaluate<TextFont>(zoom, ft);
@@ -156,7 +156,7 @@ bool SymbolLayout::hasSymbolInstances() const {
 void SymbolLayout::prepare(const GlyphMap& glyphMap, const GlyphPositions& glyphPositions,
                            const ImageMap& imageMap, const ImagePositions& imagePositions) {
     const bool textAlongLine = layout.get<TextRotationAlignment>() == AlignmentType::Map &&
-        layout.get<SymbolPlacement>() == SymbolPlacementType::Line;
+        layout.get<SymbolPlacement>() != SymbolPlacementType::Point;
 
     for (auto it = features.begin(); it != features.end(); ++it) {
         auto& feature = *it;
@@ -181,7 +181,7 @@ void SymbolLayout::prepare(const GlyphMap& glyphMap, const GlyphPositions& glyph
                 const float oneEm = 24.0f;
                 const Shaping result = getShaping(
                     /* string */ text,
-                    /* maxWidth: ems */ layout.get<SymbolPlacement>() != SymbolPlacementType::Line ?
+                    /* maxWidth: ems */ layout.get<SymbolPlacement>() == SymbolPlacementType::Point ?
                         layout.evaluate<TextMaxWidth>(zoom, feature) * oneEm : 0,
                     /* lineHeight: ems */ layout.get<TextLineHeight>() * oneEm,
                     /* anchor */ layout.evaluate<TextAnchor>(zoom, feature),
@@ -258,6 +258,10 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
     const float textMaxBoxScale = tilePixelRatio * textMaxSize / glyphSize;
     const float iconBoxScale = tilePixelRatio * layoutIconSize;
     const float symbolSpacing = tilePixelRatio * layout.get<SymbolSpacing>();
+    // CJL: I'm not sure why SymbolPlacementType::Line -> avoidEdges = false. It seems redundant since
+    // getAnchors will already avoid generating anchors outside the tile bounds.
+    // However, SymbolPlacementType::LineCenter allows anchors outside tile boundaries, so its behavior
+    // here should match SymbolPlacement::Point
     const bool avoidEdges = layout.get<SymbolAvoidEdges>() && layout.get<SymbolPlacement>() != SymbolPlacementType::Line;
     const float textPadding = layout.get<TextPadding>() * tilePixelRatio;
     const float iconPadding = layout.get<IconPadding>() * tilePixelRatio;
@@ -319,6 +323,24 @@ void SymbolLayout::addFeature(const std::size_t layoutFeatureIndex,
                 }
             }
         }
+    } else if (layout.get<SymbolPlacement>() == SymbolPlacementType::LineCenter) {
+        // No clipping, multiple lines per feature are allowed
+        // "lines" with only one point are ignored as in clipLines
+        for (const auto& line : feature.geometry) {
+            if (line.size() > 1) {
+                optional<Anchor> anchor = getCenterAnchor(line,
+                                                          textMaxAngle,
+                                                          (shapedTextOrientations.second ?: shapedTextOrientations.first).left,
+                                                          (shapedTextOrientations.second ?: shapedTextOrientations.first).right,
+                                                          (shapedIcon ? shapedIcon->left() : 0),
+                                                          (shapedIcon ? shapedIcon->right() : 0),
+                                                          glyphSize,
+                                                          textMaxBoxScale);
+                if (anchor) {
+                    addSymbolInstance(line, *anchor);
+                }
+            }
+        }
     } else if (type == FeatureType::Polygon) {
         for (const auto& polygon : classifyRings(feature.geometry)) {
             Polygon<double> poly;
diff --git a/src/mbgl/programs/symbol_program.cpp b/src/mbgl/programs/symbol_program.cpp
index 8df3b4ae3c..07d07ff0dd 100644
--- a/src/mbgl/programs/symbol_program.cpp
+++ b/src/mbgl/programs/symbol_program.cpp
@@ -94,7 +94,6 @@ Values makeValues(const bool isText,
         uniforms::u_camera_to_center_distance::Value{ state.getCameraToCenterDistance() },
         uniforms::u_pitch::Value{ state.getPitch() },
         uniforms::u_pitch_with_map::Value{ pitchWithMap },
-        uniforms::u_max_camera_distance::Value{ values.maxCameraDistance },
         uniforms::u_rotate_symbol::Value{ rotateInShader },
         uniforms::u_aspect_ratio::Value{ state.getSize().aspectRatio() },
         std::forward<Args>(args)...
diff --git a/src/mbgl/programs/symbol_program.hpp b/src/mbgl/programs/symbol_program.hpp
index 35b5821918..653fce9d4c 100644
--- a/src/mbgl/programs/symbol_program.hpp
+++ b/src/mbgl/programs/symbol_program.hpp
@@ -41,7 +41,6 @@ MBGL_DEFINE_UNIFORM_SCALAR(bool, u_is_size_zoom_constant);
 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_max_camera_distance);
 MBGL_DEFINE_UNIFORM_SCALAR(bool, u_rotate_symbol);
 MBGL_DEFINE_UNIFORM_SCALAR(float, u_aspect_ratio);
 } // namespace uniforms
@@ -356,7 +355,6 @@ class SymbolIconProgram : public SymbolProgram<
         uniforms::u_camera_to_center_distance,
         uniforms::u_pitch,
         uniforms::u_pitch_with_map,
-        uniforms::u_max_camera_distance,
         uniforms::u_rotate_symbol,
         uniforms::u_aspect_ratio>,
     style::IconPaintProperties>
@@ -396,7 +394,6 @@ class SymbolSDFProgram : public SymbolProgram<
         uniforms::u_camera_to_center_distance,
         uniforms::u_pitch,
         uniforms::u_pitch_with_map,
-        uniforms::u_max_camera_distance,
         uniforms::u_rotate_symbol,
         uniforms::u_aspect_ratio,
         uniforms::u_gamma_scale,
@@ -418,8 +415,7 @@ public:
             uniforms::u_is_text,
             uniforms::u_camera_to_center_distance,
             uniforms::u_pitch,
-            uniforms::u_pitch_with_map,            
-            uniforms::u_max_camera_distance,
+            uniforms::u_pitch_with_map,
             uniforms::u_rotate_symbol,
             uniforms::u_aspect_ratio,
             uniforms::u_gamma_scale,
diff --git a/src/mbgl/renderer/layers/render_symbol_layer.cpp b/src/mbgl/renderer/layers/render_symbol_layer.cpp
index 3a3545122e..861112526b 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.cpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.cpp
@@ -130,7 +130,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
             auto values = iconPropertyValues(layout);
             auto paintPropertyValues = iconPaintProperties();
 
-            const bool alongLine = layout.get<SymbolPlacement>() == SymbolPlacementType::Line &&
+            const bool alongLine = layout.get<SymbolPlacement>() != SymbolPlacementType::Point &&
                 layout.get<IconRotationAlignment>() == AlignmentType::Map;
 
             if (alongLine) {
@@ -191,7 +191,7 @@ void RenderSymbolLayer::render(PaintParameters& parameters, RenderSource*) {
             auto values = textPropertyValues(layout);
             auto paintPropertyValues = textPaintProperties();
 
-            const bool alongLine = layout.get<SymbolPlacement>() == SymbolPlacementType::Line &&
+            const bool alongLine = layout.get<SymbolPlacement>() != SymbolPlacementType::Point &&
                 layout.get<TextRotationAlignment>() == AlignmentType::Map;
 
             if (alongLine) {
@@ -335,24 +335,11 @@ style::SymbolPropertyValues RenderSymbolLayer::iconPropertyValues(const style::S
             evaluated.get<style::IconTranslateAnchor>(),
             evaluated.get<style::IconHaloColor>().constantOr(Color::black()).a > 0 &&
             evaluated.get<style::IconHaloWidth>().constantOr(1),
-            evaluated.get<style::IconColor>().constantOr(Color::black()).a > 0,
-            10.0f
+            evaluated.get<style::IconColor>().constantOr(Color::black()).a > 0
     };
 }
 
 style::SymbolPropertyValues RenderSymbolLayer::textPropertyValues(const style::SymbolLayoutProperties::PossiblyEvaluated& layout_) const {
-    // We hide line labels with viewport alignment as they move into the distance
-    // because the approximations we use for drawing their glyphs get progressively worse
-    // The "1.5" here means we start hiding them when the distance from the label
-    // to the camera is 50% greater than the distance from the center of the map
-    // to the camera. Depending on viewport properties, you might expect this to filter
-    // the top third of the screen at pitch 60, and do almost nothing at pitch 45
-    // "10" is effectively infinite at any pitch we support
-    const bool limitMaxDistance =
-        layout_.get<style::SymbolPlacement>() == style::SymbolPlacementType::Line
-        && layout_.get<style::TextRotationAlignment>() == style::AlignmentType::Map
-        && layout_.get<style::TextPitchAlignment>() == style::AlignmentType::Viewport;
-
     return style::SymbolPropertyValues {
             layout_.get<style::TextPitchAlignment>(),
             layout_.get<style::TextRotationAlignment>(),
@@ -361,8 +348,7 @@ style::SymbolPropertyValues RenderSymbolLayer::textPropertyValues(const style::S
             evaluated.get<style::TextTranslateAnchor>(),
             evaluated.get<style::TextHaloColor>().constantOr(Color::black()).a > 0 &&
             evaluated.get<style::TextHaloWidth>().constantOr(1),
-            evaluated.get<style::TextColor>().constantOr(Color::black()).a > 0,
-            limitMaxDistance ? 1.5f : 10.0f
+            evaluated.get<style::TextColor>().constantOr(Color::black()).a > 0
     };
 }
 
diff --git a/src/mbgl/renderer/layers/render_symbol_layer.hpp b/src/mbgl/renderer/layers/render_symbol_layer.hpp
index 83709b5122..5b73b30294 100644
--- a/src/mbgl/renderer/layers/render_symbol_layer.hpp
+++ b/src/mbgl/renderer/layers/render_symbol_layer.hpp
@@ -48,8 +48,6 @@ public:
 
     bool hasHalo;
     bool hasFill;
-    
-    float maxCameraDistance; // 1.5 for road labels, or 10 (essentially infinite) for everything else
 };
 
 } // namespace style
diff --git a/src/mbgl/style/types.cpp b/src/mbgl/style/types.cpp
index bcaa9e87c7..46de0173de 100644
--- a/src/mbgl/style/types.cpp
+++ b/src/mbgl/style/types.cpp
@@ -62,6 +62,7 @@ MBGL_DEFINE_ENUM(LineJoinType, {
 MBGL_DEFINE_ENUM(SymbolPlacementType, {
     { SymbolPlacementType::Point, "point" },
     { SymbolPlacementType::Line, "line" },
+    { SymbolPlacementType::LineCenter, "line-center" },
 });
 
 MBGL_DEFINE_ENUM(SymbolAnchorType, {
diff --git a/src/mbgl/text/collision_feature.cpp b/src/mbgl/text/collision_feature.cpp
index 9c934624d4..ac4dbff2af 100644
--- a/src/mbgl/text/collision_feature.cpp
+++ b/src/mbgl/text/collision_feature.cpp
@@ -16,7 +16,7 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
                                    IndexedSubfeature indexedFeature_,
                                    const float overscaling)
         : indexedFeature(std::move(indexedFeature_))
-        , alongLine(placement == style::SymbolPlacementType::Line) {
+        , alongLine(placement != style::SymbolPlacementType::Point) {
     if (top == 0 && bottom == 0 && left == 0 && right == 0) return;
 
     const float y1 = top * boxScale - padding;
@@ -42,7 +42,8 @@ CollisionFeature::CollisionFeature(const GeometryCoordinates& line,
 void CollisionFeature::bboxifyLabel(const GeometryCoordinates& line, GeometryCoordinate& anchorPoint,
                                     const int segment, const float labelLength, const float boxSize, const float overscaling) {
     const float step = boxSize / 2;
-    const int nBoxes = std::floor(labelLength / step);
+    const int nBoxes = std::max(static_cast<int>(std::floor(labelLength / step)), 1);
+
     // We calculate line collision circles out to 300% of what would normally be our
     // max size, to allow collision detection to work on labels that expand as
     // they move into the distance
diff --git a/src/mbgl/text/get_anchors.cpp b/src/mbgl/text/get_anchors.cpp
index d41faf2a71..160ee21edf 100644
--- a/src/mbgl/text/get_anchors.cpp
+++ b/src/mbgl/text/get_anchors.cpp
@@ -7,6 +7,20 @@
 #include <cmath>
 
 namespace mbgl {
+  
+float getAngleWindowSize(const float textLeft, const float textRight, const float glyphSize, const float boxScale) {
+    return (textLeft - textRight) != 0.0f ?
+        3.0f / 5.0f * glyphSize * boxScale :
+        0;
+}
+
+float getLineLength(const GeometryCoordinates& line) {
+    float lineLength = 0;
+    for (auto it = line.begin(), end = line.end() - 1; it != end; it++) {
+        lineLength += util::dist<float>(*(it), *(it + 1));
+    }
+    return lineLength;
+}
 
 static Anchors resample(const GeometryCoordinates& line,
                         const float offset,
@@ -17,10 +31,7 @@ static Anchors resample(const GeometryCoordinates& line,
                         const bool continuedLine,
                         const bool placeAtMiddle) {
     const float halfLabelLength = labelLength / 2.0f;
-    float lineLength = 0;
-    for (auto it = line.begin(), end = line.end() - 1; it != end; it++) {
-        lineLength += util::dist<float>(*(it), *(it + 1));
-    }
+    const float lineLength = getLineLength(line);
 
     float distance = 0;
     float markedDistance = offset - spacing;
@@ -91,19 +102,18 @@ Anchors getAnchors(const GeometryCoordinates& line,
     // potential label passes text-max-angle check and has enough froom to fit
     // on the line.
 
-    const float angleWindowSize = (textLeft - textRight) != 0.0f ?
-        3.0f / 5.0f * glyphSize * boxScale :
-        0;
+    const float angleWindowSize = getAngleWindowSize(textLeft, textRight, glyphSize, boxScale);
 
-    const float labelLength = fmax(textRight - textLeft, iconRight - iconLeft);
+    const float shapedLabelLength = fmax(textRight - textLeft, iconRight - iconLeft);
+    const float labelLength = shapedLabelLength * boxScale;
 
     // Is the line continued from outside the tile boundary?
     const bool continuedLine = (line[0].x == 0 || line[0].x == util::EXTENT || line[0].y == 0 || line[0].y == util::EXTENT);
 
     // Is the label long, relative to the spacing?
     // If so, adjust the spacing so there is always a minimum space of `spacing / 4` between label edges.
-    if (spacing - labelLength * boxScale  < spacing / 4) {
-        spacing = labelLength * boxScale + spacing / 4;
+    if (spacing - labelLength < spacing / 4) {
+        spacing = labelLength + spacing / 4;
     }
 
     // Offset the first anchor by:
@@ -114,10 +124,53 @@ Anchors getAnchors(const GeometryCoordinates& line,
     const float fixedExtraOffset = glyphSize * 2;
 
     const float offset = !continuedLine ?
-    std::fmod((labelLength / 2 + fixedExtraOffset) * boxScale * overscaling, spacing) :
+    std::fmod((shapedLabelLength / 2 + fixedExtraOffset) * boxScale * overscaling, spacing) :
     std::fmod(spacing / 2 * overscaling, spacing);
 
-    return resample(line, offset, spacing, angleWindowSize, maxAngle, labelLength * boxScale, continuedLine, false);
+    return resample(line, offset, spacing, angleWindowSize, maxAngle, labelLength, continuedLine, false);
+}
+
+optional<Anchor> getCenterAnchor(const GeometryCoordinates& line,
+                                 const float maxAngle,
+                                 const float textLeft,
+                                 const float textRight,
+                                 const float iconLeft,
+                                 const float iconRight,
+                                 const float glyphSize,
+                                 const float boxScale) {
+    if (line.empty()) {
+        return {};
+    }
+    
+    const float angleWindowSize = getAngleWindowSize(textLeft, textRight, glyphSize, boxScale);
+    const float labelLength = fmax(textRight - textLeft, iconRight - iconLeft) * boxScale;
+    
+    float prevDistance = 0;
+    const float centerDistance = getLineLength(line) / 2;
+    
+    int i = 0;
+    for (auto it = line.begin(), end = line.end() - 1; it != end; it++, i++) {
+        const GeometryCoordinate& a = *(it);
+        const GeometryCoordinate& b = *(it + 1);
+        
+        const auto segmentDistance = util::dist<float>(a, b);
+        
+        if (prevDistance + segmentDistance > centerDistance) {
+            // The center is on this segment
+            float t = (centerDistance - prevDistance) / segmentDistance,
+                  x = util::interpolate(float(a.x), float(b.x), t),
+                  y = util::interpolate(float(a.y), float(b.y), t);
+            
+            Anchor anchor(::round(x), ::round(y), util::angle_to(b, a), 0.5f, i);
+            
+            if (!angleWindowSize || checkMaxAngle(line, anchor, labelLength, angleWindowSize, maxAngle)) {
+                return anchor;
+            }
+        }
+        
+        prevDistance += segmentDistance;
+    }
+    return {};
 }
 
 } // namespace mbgl
diff --git a/src/mbgl/text/get_anchors.hpp b/src/mbgl/text/get_anchors.hpp
index 48f3013093..8fd22051a4 100644
--- a/src/mbgl/text/get_anchors.hpp
+++ b/src/mbgl/text/get_anchors.hpp
@@ -17,4 +17,14 @@ Anchors getAnchors(const GeometryCoordinates& line,
                    const float boxScale,
                    const float overscaling);
 
+optional<Anchor> getCenterAnchor(const GeometryCoordinates& line,
+                                 const float maxAngle,
+                                 const float textLeft,
+                                 const float textRight,
+                                 const float iconLeft,
+                                 const float iconRight,
+                                 const float glyphSize,
+                                 const float boxScale);
+    
+
 } // namespace mbgl
diff --git a/src/mbgl/text/quads.cpp b/src/mbgl/text/quads.cpp
index 0014ae8d01..ec4461ac6d 100644
--- a/src/mbgl/text/quads.cpp
+++ b/src/mbgl/text/quads.cpp
@@ -117,7 +117,7 @@ SymbolQuads getGlyphQuads(const Shaping& shapedText,
         const float rectBuffer = 3.0f + glyphPadding;
 
         const float halfAdvance = glyph.metrics.advance / 2.0;
-        const bool alongLine = layout.get<TextRotationAlignment>() == AlignmentType::Map && placement == SymbolPlacementType::Line;
+        const bool alongLine = layout.get<TextRotationAlignment>() == AlignmentType::Map && placement != SymbolPlacementType::Point;
 
         const Point<float> glyphOffset = alongLine ?
             Point<float>{ positionedGlyph.x + halfAdvance, positionedGlyph.y } :