[core] improve legibility of labels that follow lines

port https://github.com/mapbox/mapbox-gl-js/pull/4781

This improves legibility of labels that follow lines in pitched views.
The previous approach used the limited information in the shader to
calculate put the glyph in approximatelyright place. The new approach
does this more accurately by doing it on the cpu where we have access to
the entire line geometry.

3 files changed, 55 insertions, 297 deletions

diff --git a/src/mbgl/text/quads.cpp b/src/mbgl/text/quads.cpp
index ab10c5a6b7..7908ea4abc 100644
--- a/src/mbgl/text/quads.cpp
+++ b/src/mbgl/text/quads.cpp
@@ -13,14 +13,9 @@ namespace mbgl {
 
 using namespace style;
 
-const float globalMinScale = 0.5f; // underscale by 1 zoom level
-
-SymbolQuad getIconQuad(const Anchor& anchor,
-                       const PositionedIcon& shapedIcon,
-                       const GeometryCoordinates& line,
+SymbolQuad getIconQuad(const PositionedIcon& shapedIcon,
                        const SymbolLayoutProperties::Evaluated& layout,
                        const float layoutTextSize,
-                       const style::SymbolPlacementType placement, 
                        const Shaping& shapedText) {
     const ImagePosition& image = shapedIcon.image();
 
@@ -71,18 +66,7 @@ SymbolQuad getIconQuad(const Anchor& anchor,
         bl = {left, bottom};
     }
 
-    float angle = shapedIcon.angle();
-    if (placement == style::SymbolPlacementType::Line) {
-        assert(static_cast<unsigned int>(anchor.segment) < line.size());
-        const GeometryCoordinate &prev= line[anchor.segment];
-        if (anchor.point.y == prev.y && anchor.point.x == prev.x &&
-            static_cast<unsigned int>(anchor.segment + 1) < line.size()) {
-            const GeometryCoordinate &next= line[anchor.segment + 1];
-            angle += std::atan2(anchor.point.y - next.y, anchor.point.x - next.x) + M_PI;
-        } else {
-            angle += std::atan2(anchor.point.y - prev.y, anchor.point.x - prev.x);
-        }
-    }
+    const float angle = shapedIcon.angle();
 
     if (angle) {
         // Compute the transformation matrix.
@@ -104,212 +88,19 @@ SymbolQuad getIconQuad(const Anchor& anchor,
         static_cast<uint16_t>(image.textureRect.h + border * 2)
     };
 
-    return SymbolQuad { tl, tr, bl, br, textureRect, 0, 0, anchor.point, globalMinScale, std::numeric_limits<float>::infinity(), shapedText.writingMode };
-}
-
-struct GlyphInstance {
-    explicit GlyphInstance(Point<float> anchorPoint_) : anchorPoint(std::move(anchorPoint_)) {}
-    explicit GlyphInstance(Point<float> anchorPoint_, bool upsideDown_, float minScale_, float maxScale_,
-            float angle_)
-        : anchorPoint(std::move(anchorPoint_)), upsideDown(upsideDown_), minScale(minScale_), maxScale(maxScale_), angle(angle_) {}
-
-    const Point<float> anchorPoint;
-    const bool upsideDown = false;
-    const float minScale = globalMinScale;
-    const float maxScale = std::numeric_limits<float>::infinity();
-    const float angle = 0.0f;
-};
-
-using GlyphInstances = std::vector<GlyphInstance>;
-    
-struct VirtualSegment {
-    Point<float> anchor;
-    Point<float> end;
-    size_t index;
-    float minScale;
-    float maxScale;
-};
-    
-inline void insertSegmentGlyph(std::back_insert_iterator<GlyphInstances> glyphs,
-                        const VirtualSegment& virtualSegment,
-                        const bool glyphIsLogicallyForward,
-                        const bool upsideDown) {
-    float segmentAngle = std::atan2(virtualSegment.end.y - virtualSegment.anchor.y, virtualSegment.end.x - virtualSegment.anchor.x);
-    // If !glyphIsLogicallyForward, we're iterating through the segments in reverse logical order as well, so we need to flip the segment angle
-    float glyphAngle = glyphIsLogicallyForward ? segmentAngle : segmentAngle + M_PI;
-    
-    // Insert a glyph rotated at this angle for display in the range from [scale, previous(larger) scale].
-    glyphs = GlyphInstance{
-        /* anchor */ virtualSegment.anchor,
-        /* upsideDown */ upsideDown,
-        /* minScale */ virtualSegment.minScale,
-        /* maxScale */ virtualSegment.maxScale,
-        /* angle */ static_cast<float>(std::fmod((glyphAngle + 2.0 * M_PI), (2.0 * M_PI)))};
-}
-
-/**
- Given the distance along the line from the label anchor to the beginning of the current segment,
- project a "virtual anchor" point at the same distance along the line extending out from this segment.
- 
-                B <-- beginning of current segment
-* . . . . . . . *--------* E <-- end of current segment
-VA              |      
-                /        VA = "virtual segment anchor"
-               /
-     ---*-----`
-        A = label anchor
- 
- Distance _along line_ from A to B == straight-line distance from VA to B.
- */
-inline Point<float> getVirtualSegmentAnchor(const Point<float>& segmentBegin, const Point<float>& segmentEnd, float distanceFromAnchorToSegmentBegin) {
-    Point<float> segmentDirectionUnitVector = util::normal<float>(segmentBegin, segmentEnd);
-    return segmentBegin - (segmentDirectionUnitVector * distanceFromAnchorToSegmentBegin);
-}
-
-/*
- Given the segment joining `segmentAnchor` and `segmentEnd` and a desired offset
- `glyphDistanceFromAnchor` at which a glyph is to be placed, calculate the minimum
- "scale" at which the glyph will fall on the segment (i.e., not past the end)
-
- "Scale" here refers to the ratio between the *rendered* zoom level and the text-layout
- zoom level, which is 1 + (source tile's zoom level).  `glyphDistanceFromAnchor`, although
- passed in units consistent with the text-layout zoom level, is based on text size.  So
- when the tile is being rendered at z < text-layout zoom, the glyph's actual distance from
- the anchor is larger relative to the segment's length than at layout time:
- 
- 
-                                                                   GLYPH
- z == layout-zoom, scale == 1:        segmentAnchor *--------------^-------------* segmentEnd
- z == layout-zoom - 1, scale == 0.5:  segmentAnchor *--------------^* segmentEnd
- 
-                                                    <-------------->
-                                                    Anchor-to-glyph distance stays visually fixed,
-                                                    so it changes relative to the segment.
-*/
-inline float getMinScaleForSegment(const float glyphDistanceFromAnchor,
-                         const Point<float>& segmentAnchor,
-                         const Point<float>& segmentEnd) {
-    const auto distanceFromAnchorToEnd = util::dist<float>(segmentAnchor, segmentEnd);
-    return glyphDistanceFromAnchor / distanceFromAnchorToEnd;
-}
-
-inline Point<float> getSegmentEnd(const bool glyphIsLogicallyForward,
-                           const GeometryCoordinates& line,
-                           const size_t segmentIndex) {
-    return convertPoint<float>(glyphIsLogicallyForward ? line[segmentIndex+1] : line[segmentIndex]);
-}
-
-optional<VirtualSegment> getNextVirtualSegment(const VirtualSegment& previousVirtualSegment,
-                                               const GeometryCoordinates& line,
-                                               const float glyphDistanceFromAnchor,
-                                               const bool glyphIsLogicallyForward) {
-    auto nextSegmentBegin = previousVirtualSegment.end;
-    
-    auto end = nextSegmentBegin;
-    size_t index = previousVirtualSegment.index;
-
-    // skip duplicate nodes
-    while (end == nextSegmentBegin) {
-        // look ahead by 2 points in the line because the segment index refers to the beginning
-        // of the segment, and we need an endpoint too
-        if (glyphIsLogicallyForward && (index + 2 < line.size())) {
-            index += 1;
-        } else if (!glyphIsLogicallyForward && index != 0) {
-            index -= 1;
-        } else {
-            return {};
-        }
-        
-        end = getSegmentEnd(glyphIsLogicallyForward, line, index);
-    }
-    
-    const auto anchor = getVirtualSegmentAnchor(nextSegmentBegin, end,
-                                                util::dist<float>(previousVirtualSegment.anchor,
-                                                                  previousVirtualSegment.end));
-    return VirtualSegment {
-        anchor,
-        end,
-        index,
-        getMinScaleForSegment(glyphDistanceFromAnchor, anchor, end),
-        previousVirtualSegment.minScale
-    };
-}
-    
-/*
- Given (1) a glyph positioned relative to an anchor point and (2) a line to follow,
- calculates which segment of the line the glyph will fall on for each possible
- scale range, and for each range produces a "virtual" anchor point and an angle that will
- place the glyph on the right segment and rotated to the correct angle.
- 
- Because one glyph quad is made ahead of time for each possible orientation, the
- symbol_sdf shader can quickly handle changing layout as we zoom in and out
- 
- If the "keepUpright" property is set, we call getLineGlyphs twice (once upright and 
- once "upside down"). This will generate two sets of glyphs following the line in opposite
- directions. Later, SymbolLayout::place will look at the glyphs and based on the placement
- angle determine if their original anchor was "upright" or not -- based on that, it throws
- away one set of glyphs or the other (this work has to be done in the CPU, but it's just a
- filter so it's fast)
- */
-void getLineGlyphs(std::back_insert_iterator<GlyphInstances> glyphs,
-                      Anchor& anchor,
-                      float glyphHorizontalOffsetFromAnchor,
-                      const GeometryCoordinates& line,
-                      size_t anchorSegment,
-                      bool upsideDown) {
-    assert(line.size() > anchorSegment+1);
-    
-    // This is true if the glyph is "logically forward" of the anchor point, based on the ordering of line segments
-    //  The actual angle of the line is irrelevant
-    //  If "upsideDown" is set, everything is flipped
-    const bool glyphIsLogicallyForward = (glyphHorizontalOffsetFromAnchor >= 0) ^ upsideDown;
-    const float glyphDistanceFromAnchor = std::fabs(glyphHorizontalOffsetFromAnchor);
-    
-    const auto initialSegmentEnd = getSegmentEnd(glyphIsLogicallyForward, line, anchorSegment);
-    VirtualSegment virtualSegment = {
-        anchor.point,
-        initialSegmentEnd,
-        anchorSegment,
-        getMinScaleForSegment(glyphDistanceFromAnchor, anchor.point, initialSegmentEnd),
-        std::numeric_limits<float>::infinity()
-    };
-    
-    while (true) {
-        insertSegmentGlyph(glyphs,
-                           virtualSegment,
-                           glyphIsLogicallyForward,
-                           upsideDown);
-        
-        if (virtualSegment.minScale <= anchor.scale) {
-            // No need to calculate below the scale where the label starts showing
-            return;
-        }
-        
-        optional<VirtualSegment> nextVirtualSegment = getNextVirtualSegment(virtualSegment,
-                                                                            line,
-                                                                            glyphDistanceFromAnchor,
-                                                                            glyphIsLogicallyForward);
-        if (!nextVirtualSegment) {
-            // There are no more segments, so we can't fit this glyph on the line at a lower scale
-            // This implies we can't show the label at all at lower scale, so we update the anchor's min scale
-            anchor.scale = virtualSegment.minScale;
-            return;
-        } else {
-            virtualSegment = *nextVirtualSegment;
-        }
-    }
-    
+    return SymbolQuad { tl, tr, bl, br, textureRect, shapedText.writingMode, { 0.0f, 0.0f } };
 }
 
-SymbolQuads getGlyphQuads(Anchor& anchor,
-                          const Shaping& shapedText,
-                          const float boxScale,
-                          const GeometryCoordinates& line,
+SymbolQuads getGlyphQuads(const Shaping& shapedText,
                           const SymbolLayoutProperties::Evaluated& layout,
                           const style::SymbolPlacementType placement,
                           const GlyphPositionMap& positions) {
     const float textRotate = layout.get<TextRotate>() * util::DEG2RAD;
-    const bool keepUpright = layout.get<TextKeepUpright>();
+
+    const float oneEm = 24.0;
+    std::array<float, 2> textOffset = layout.get<TextOffset>();
+    textOffset[0] *= oneEm;
+    textOffset[1] *= oneEm;
 
     SymbolQuads quads;
 
@@ -320,67 +111,55 @@ SymbolQuads getGlyphQuads(Anchor& anchor,
 
         const GlyphPosition& glyph = positionsIt->second;
         const Rect<uint16_t>& rect = glyph.rect;
-        const float centerX = (positionedGlyph.x + glyph.metrics.advance / 2.0f) * boxScale;
-
-        GlyphInstances glyphInstances;
-        if (placement == style::SymbolPlacementType::Line) {
-            getLineGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, false);
-            if (keepUpright)
-                getLineGlyphs(std::back_inserter(glyphInstances), anchor, centerX, line, anchor.segment, true);
-        } else {
-            glyphInstances.emplace_back(GlyphInstance{anchor.point});
-        }
 
         // The rects have an addditional buffer that is not included in their size;
         const float glyphPadding = 1.0f;
         const float rectBuffer = 3.0f + glyphPadding;
 
-        const float x1 = positionedGlyph.x + glyph.metrics.left - rectBuffer;
-        const float y1 = positionedGlyph.y - glyph.metrics.top - rectBuffer;
+        const float halfAdvance = glyph.metrics.advance / 2.0;
+        const bool alongLine = layout.get<TextRotationAlignment>() == AlignmentType::Map && placement == SymbolPlacementType::Line;
+
+        const Point<float> glyphOffset = alongLine ?
+            Point<float>{ positionedGlyph.x + halfAdvance, positionedGlyph.y } :
+            Point<float>{ 0.0f, 0.0f };
+
+        const Point<float> builtInOffset = alongLine ?
+            Point<float>{ 0.0f, 0.0f } :
+            Point<float>{ positionedGlyph.x + halfAdvance + textOffset[0], positionedGlyph.y + textOffset[1] };
+
+
+        const float x1 = glyph.metrics.left - rectBuffer - halfAdvance + builtInOffset.x;
+        const float y1 = -glyph.metrics.top - rectBuffer + builtInOffset.y;
         const float x2 = x1 + rect.w;
         const float y2 = y1 + rect.h;
 
-        const Point<float> center{positionedGlyph.x, static_cast<float>(static_cast<float>(glyph.metrics.advance) / 2.0)};
+        const Point<float> center{builtInOffset.x - halfAdvance, static_cast<float>(static_cast<float>(glyph.metrics.advance) / 2.0)};
 
-        Point<float> otl{x1, y1};
-        Point<float> otr{x2, y1};
-        Point<float> obl{x1, y2};
-        Point<float> obr{x2, y2};
+        Point<float> tl{x1, y1};
+        Point<float> tr{x2, y1};
+        Point<float> bl{x1, y2};
+        Point<float> br{x2, y2};
 
         if (positionedGlyph.angle != 0) {
-            otl = util::rotate(otl - center, positionedGlyph.angle) + center;
-            otr = util::rotate(otr - center, positionedGlyph.angle) + center;
-            obl = util::rotate(obl - center, positionedGlyph.angle) + center;
-            obr = util::rotate(obr - center, positionedGlyph.angle) + center;
+            tl = util::rotate(tl - center, positionedGlyph.angle) + center;
+            tr = util::rotate(tr - center, positionedGlyph.angle) + center;
+            bl = util::rotate(bl - center, positionedGlyph.angle) + center;
+            br = util::rotate(br - center, positionedGlyph.angle) + center;
         }
 
-        for (const GlyphInstance &instance : glyphInstances) {
-            Point<float> tl = otl;
-            Point<float> tr = otr;
-            Point<float> bl = obl;
-            Point<float> br = obr;
+        if (textRotate) {
+            // Compute the transformation matrix.
+            float angle_sin = std::sin(textRotate);
+            float angle_cos = std::cos(textRotate);
+            std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
 
-            if (textRotate) {
-                // Compute the transformation matrix.
-                float angle_sin = std::sin(textRotate);
-                float angle_cos = std::cos(textRotate);
-                std::array<float, 4> matrix = {{angle_cos, -angle_sin, angle_sin, angle_cos}};
-
-                tl = util::matrixMultiply(matrix, tl);
-                tr = util::matrixMultiply(matrix, tr);
-                bl = util::matrixMultiply(matrix, bl);
-                br = util::matrixMultiply(matrix, br);
-            }
-
-            // Prevent label from extending past the end of the line
-            const float glyphMinScale = std::max(instance.minScale, anchor.scale);
-
-            // All the glyphs for a label are tagged with either the "right side up" or "upside down" anchor angle,
-            //  which is used at placement time to determine which set to show
-            const float anchorAngle = std::fmod((anchor.angle + (instance.upsideDown ? M_PI : 0.0) + 2 * M_PI), (2 * M_PI));
-            const float glyphAngle = std::fmod((instance.angle + (instance.upsideDown ? M_PI : 0.0) + 2 * M_PI), (2 * M_PI));
-            quads.emplace_back(tl, tr, bl, br, rect, anchorAngle, glyphAngle, instance.anchorPoint, glyphMinScale, instance.maxScale, shapedText.writingMode);
+            tl = util::matrixMultiply(matrix, tl);
+            tr = util::matrixMultiply(matrix, tr);
+            bl = util::matrixMultiply(matrix, bl);
+            br = util::matrixMultiply(matrix, br);
         }
+
+        quads.emplace_back(tl, tr, bl, br, rect, shapedText.writingMode, glyphOffset);
     }
 
     return quads;
diff --git a/src/mbgl/text/quads.hpp b/src/mbgl/text/quads.hpp
index b29f6b0ad3..33d003c935 100644
--- a/src/mbgl/text/quads.hpp
+++ b/src/mbgl/text/quads.hpp
@@ -19,50 +19,33 @@ public:
                Point<float> bl_,
                Point<float> br_,
                Rect<uint16_t> tex_,
-               float anchorAngle_,
-               float glyphAngle_,
-               Point<float> anchorPoint_,
-               float minScale_,
-               float maxScale_,
-               WritingModeType writingMode_)
+               WritingModeType writingMode_,
+               Point<float> glyphOffset_)
         : tl(std::move(tl_)),
         tr(std::move(tr_)),
         bl(std::move(bl_)),
         br(std::move(br_)),
         tex(std::move(tex_)),
-        anchorAngle(anchorAngle_),
-        glyphAngle(glyphAngle_),
-        anchorPoint(std::move(anchorPoint_)),
-        minScale(minScale_),
-        maxScale(maxScale_),
-        writingMode(writingMode_) {}
+        writingMode(writingMode_),
+        glyphOffset(glyphOffset_) {}
 
     Point<float> tl;
     Point<float> tr;
     Point<float> bl;
     Point<float> br;
     Rect<uint16_t> tex;
-    float anchorAngle, glyphAngle;
-    Point<float> anchorPoint;
-    float minScale;
-    float maxScale;
     WritingModeType writingMode;
+    Point<float> glyphOffset;
 };
 
 using SymbolQuads = std::vector<SymbolQuad>;
 
-SymbolQuad getIconQuad(const Anchor& anchor,
-                       const PositionedIcon& shapedIcon,
-                       const GeometryCoordinates& line,
+SymbolQuad getIconQuad(const PositionedIcon& shapedIcon,
                        const style::SymbolLayoutProperties::Evaluated&,
                        const float layoutTextSize,
-                       style::SymbolPlacementType placement,
                        const Shaping& shapedText);
 
-SymbolQuads getGlyphQuads(Anchor& anchor,
-                          const Shaping& shapedText,
-                          const float boxScale,
-                          const GeometryCoordinates& line,
+SymbolQuads getGlyphQuads(const Shaping& shapedText,
                           const style::SymbolLayoutProperties::Evaluated&,
                           style::SymbolPlacementType placement,
                           const GlyphPositionMap& positions);
diff --git a/src/mbgl/text/shaping.cpp b/src/mbgl/text/shaping.cpp
index 338abe2e43..c81f25d4eb 100644
--- a/src/mbgl/text/shaping.cpp
+++ b/src/mbgl/text/shaping.cpp
@@ -27,12 +27,9 @@ void align(Shaping& shaping,
            const float verticalAlign,
            const float maxLineLength,
            const float lineHeight,
-           const std::size_t lineCount,
-           const Point<float>& translate) {
-    const float shiftX =
-    (justify - horizontalAlign) * maxLineLength + ::round(translate.x);
-    const float shiftY =
-    (-verticalAlign * lineCount + 0.5) * lineHeight + ::round(translate.y);
+           const std::size_t lineCount) {
+    const float shiftX = (justify - horizontalAlign) * maxLineLength;
+    const float shiftY = (-verticalAlign * lineCount + 0.5) * lineHeight;
     
     for (auto& glyph : shaping.positionedGlyphs) {
         glyph.x += shiftX;
@@ -205,7 +202,6 @@ void shapeLines(Shaping& shaping,
                           const float horizontalAlign,
                           const float verticalAlign,
                           const float justify,
-                          const Point<float>& translate,
                           const float verticalHeight,
                           const WritingModeType writingMode,
                           const Glyphs& glyphs) {
@@ -259,7 +255,7 @@ void shapeLines(Shaping& shaping,
     }
     
     align(shaping, justify, horizontalAlign, verticalAlign, maxLineLength, lineHeight,
-          lines.size(), translate);
+          lines.size());
     const uint32_t height = lines.size() * lineHeight;
     
     // Calculate the bounding box
@@ -288,7 +284,7 @@ const Shaping getShaping(const std::u16string& logicalInput,
                      determineLineBreaks(logicalInput, spacing, maxWidth, writingMode, glyphs));
     
     shapeLines(shaping, reorderedLines, spacing, lineHeight, horizontalAlign, verticalAlign,
-               justify, translate, verticalHeight, writingMode, glyphs);
+               justify, verticalHeight, writingMode, glyphs);
     
     return shaping;
 }